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

CREATORAlviona Mancho, Evangelos Markakis, Nicos Protopapas
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-20899

Browse the full library · About the Tower of Babel