Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.20899 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912505687703552 |
|---|---|
| author | Mancho, Alviona Markakis, Evangelos Protopapas, Nicos |
| author_facet | Mancho, Alviona Markakis, Evangelos Protopapas, Nicos |
| contents | We study the fair allocation of indivisible goods under cardinality constraints, where each agent must receive a bundle of fixed size. This models practical scenarios, such as assigning shifts or forming equally sized teams. Recently, variants of envy-freeness up to one/any item (EF1, EFX) were introduced for this setting, based on flips or exchanges of items. Namely, one can define envy-freeness up to one/any flip (EFF1, EFFX), meaning that an agent $i$ does not envy another agent $j$ after performing one or any one-item flip between their bundles that improves the value of $i$.
We explore algorithmic aspects of this notion, and our contribution is twofold: we present both algorithmic and impossibility results, highlighting a stark contrast between the classic EFX concept and its flip-based analogue. First, we explore standard techniques used in the literature and show that they fail to guarantee EFFX approximations. On the positive side, we show that we can achieve a constant factor approximation guarantee when agents share a common ranking over item values, based on the well-known envy cycle elimination technique. This idea also leads to a generalized algorithm with approximation guarantees when agents agree on the top $n$ items and their valuation functions are bounded. Finally, we show that an algorithm that maximizes the Nash welfare guarantees a 1/2-EFF1 allocation, and that this bound is tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20899 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fairness under Equal-Sized Bundles: Impossibility Results and Approximation Guarantees Mancho, Alviona Markakis, Evangelos Protopapas, Nicos Computer Science and Game Theory We study the fair allocation of indivisible goods under cardinality constraints, where each agent must receive a bundle of fixed size. This models practical scenarios, such as assigning shifts or forming equally sized teams. Recently, variants of envy-freeness up to one/any item (EF1, EFX) were introduced for this setting, based on flips or exchanges of items. Namely, one can define envy-freeness up to one/any flip (EFF1, EFFX), meaning that an agent $i$ does not envy another agent $j$ after performing one or any one-item flip between their bundles that improves the value of $i$. We explore algorithmic aspects of this notion, and our contribution is twofold: we present both algorithmic and impossibility results, highlighting a stark contrast between the classic EFX concept and its flip-based analogue. First, we explore standard techniques used in the literature and show that they fail to guarantee EFFX approximations. On the positive side, we show that we can achieve a constant factor approximation guarantee when agents share a common ranking over item values, based on the well-known envy cycle elimination technique. This idea also leads to a generalized algorithm with approximation guarantees when agents agree on the top $n$ items and their valuation functions are bounded. Finally, we show that an algorithm that maximizes the Nash welfare guarantees a 1/2-EFF1 allocation, and that this bound is tight. |
| title | Fairness under Equal-Sized Bundles: Impossibility Results and Approximation Guarantees |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2507.20899 |