Fairness under Equal-Sized Bundles: Impossibility Results and Approximation Guarantees
Alviona Mancho, Evangelos Markakis, Nicos Protopapas · 2025
Read Fairness under Equal-Sized Bundles: Impossibility Results and Approximation Guarantees by Alviona Mancho, Evangelos Markakis, Nicos Protopapas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20899.txt.
Description
Mancho, Markakis, and Protopapas study fair division when every person must receive the same number of items. This fixed-size rule fits real tasks such as assigning shifts or forming equal teams. The usual idea of fairness has to be reworked, because swapping items, called flips, is the only way to fix envy here.
The authors define envy-freeness up to one or any helpful flip and show that standard methods fail to guarantee the strong version. On the bright side, a known envy-cycle method gives a constant-factor guarantee when people rank items the same way. A method that maximizes Nash welfare reaches half of the one-flip standard, and that bound cannot be improved.
Catalog record
| CREATOR | Alviona Mancho, Evangelos Markakis, Nicos Protopapas |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-20899