Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems
- URL: http://arxiv.org/abs/2410.02589v1
- Date: Thu, 3 Oct 2024 15:32:04 GMT
- Title: Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems
- Authors: Jad Salem, Reuben Tate, Stephan Eidenbenz,
- Abstract summary: We show that optimal maximin-fair solutions are bounded by non-maximin-fair optimal solutions.
In the paper, we use the special case of Max-Cut to demonstrate challenges in defining and implementing maximin fairness.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Maximin fairness is the ideal that the worst-off group (or individual) should be treated as well as possible. Literature on maximin fairness in various decision-making settings has grown in recent years, but theoretical results are sparse. In this paper, we explore the challenges inherent to maximin fairness in combinatorial optimization. We begin by showing that (1) optimal maximin-fair solutions are bounded by non-maximin-fair optimal solutions, and (2) stochastic maximin-fair solutions exceed their deterministic counterparts in expectation for a broad class of combinatorial optimization problems. In the remainder of the paper, we use the special case of Max-Cut to demonstrate challenges in defining and implementing maximin fairness.
Related papers
- Multi-Objective Bayesian Optimization with Active Preference Learning [18.066263838953223]
We propose a Bayesian optimization (BO) approach to identifying the most preferred solution in a multi-objective optimization (MOO) problem.
To minimize the interaction cost with the decision maker (DM), we also propose an active learning strategy for the preference estimation.
arXiv Detail & Related papers (2023-11-22T15:24:36Z) - Optimization on Pareto sets: On a theory of multi-objective optimization [7.907376287850398]
In multi-objective optimization, a single decision vector must balance the trade-offs between many objectives.
We consider a more practically significant optimization problem, where the goal is to optimize a constrained set.
arXiv Detail & Related papers (2023-08-04T05:55:52Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs.
A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual.
The proposed approach is shown to converge (with linear rate) to the global optimum.
arXiv Detail & Related papers (2022-06-03T16:26:38Z) - Efficient Algorithms for Extreme Bandits [20.68824391770909]
We contribute to the Extreme Bandit problem, a variant of Multi-Armed Bandits in which the learner seeks to collect the largest possible reward.
We first study the concentration of the maximum of i.i.d random variables under mild assumptions on the tail of the rewards distributions.
We then propose and analyze a more adaptive, anytime algorithm, QoMax-SDA, which combines QoMax with a subsampling method recently introduced by Baudry et al.
arXiv Detail & Related papers (2022-03-21T11:09:34Z) - Max-Min Grouped Bandits [48.62520520818357]
We introduce a multi-armed bandit problem termed max-min grouped bandits.
The goal is to find a group whose worst arm has the highest mean reward.
This problem is of interest to applications such as recommendation systems.
arXiv Detail & Related papers (2021-11-17T01:59:15Z) - Bayesian Optimization for Min Max Optimization [77.60508571062958]
We propose algorithms that perform Min Max Optimization in a setting where the function that should be optimized is not known a priori.
We extend the two acquisition functions Expected Improvement and Gaussian Process Upper Confidence Bound.
We show that these acquisition functions allow for better solutions - converging faster to the optimum than the benchmark settings.
arXiv Detail & Related papers (2021-07-29T06:49:34Z) - Maxmin-Fair Ranking: Individual Fairness under Group-Fairness
Constraints [11.3077234652777]
We study a novel problem of fairness in ranking aimed at minimizing the amount of individual unfairness introduced when enforcing group-fairness constraints.
Our proposal is rooted in the distributional maxminmin theory which uses randomization to maximize the expected satisfaction of the worst-off individuals.
arXiv Detail & Related papers (2021-06-16T09:27:12Z) - Preference learning along multiple criteria: A game-theoretic
perspective [97.94912276610002]
We generalize the notion of a von Neumann winner to the multi-criteria setting by taking inspiration from Blackwell's approachability.
Our framework allows for non-linear aggregation of preferences across criteria, and generalizes the linearization-based approach from multi-objective optimization.
We show that the Blackwell winner of a multi-criteria problem instance can be computed as the solution to a convex optimization problem.
arXiv Detail & Related papers (2021-05-05T03:23:11Z) - Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
We argue for the use of neural generative models to characterize the worst-case distribution.
This approach poses a number of implementation and optimization challenges.
We find that the proposed approach yields models that are more robust than comparable baselines.
arXiv Detail & Related papers (2021-03-18T14:26:26Z) - Are we Forgetting about Compositional Optimisers in Bayesian
Optimisation? [66.39551991177542]
This paper presents a sample methodology for global optimisation.
Within this, a crucial performance-determiningtrivial is maximising the acquisition function.
We highlight the empirical advantages of the approach to optimise functionation across 3958 individual experiments.
arXiv Detail & Related papers (2020-12-15T12:18:38Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.