Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909334616670208 |
|---|---|
| author | Salem, Jad Tate, Reuben Eidenbenz, Stephan |
| author_facet | Salem, Jad Tate, Reuben Eidenbenz, Stephan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02589 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems Salem, Jad Tate, Reuben Eidenbenz, Stephan Data Structures and Algorithms Computers and Society Optimization and Control 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. |
| title | Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems |
| topic | Data Structures and Algorithms Computers and Society Optimization and Control |
| url | https://arxiv.org/abs/2410.02589 |