Abstract
We consider fair allocation of indivisible items in a model with goods, chores, and copies, as a unified framework for studying: (1) the existence of EFX and other solution concepts for goods with copies; (2) the existence of EFX and other solution concepts for chores. We establish a tight relation between these issues via two conceptual contributions: First, a refinement of envy-based fairness notions that we term envy without commons (denoted EFX WC when applied to EFX). Second, a formal duality theorem relating the existence of a host of (refined) fair allocation concepts for copies to their existence for chores. We demonstrate the usefulness of our duality result by using it to characterize the existence of EFX for chores through the dual environment, as well as to prove EFX existence in the special case of leveled preferences over the chores. We further study the hierarchy among envy-freeness notions without commons and their α-MMS guarantees, showing, for example, that any EFX WC allocation guarantees at least 11 4 -MMS for goods with copies.
Original language | English |
---|---|
Article number | 10 |
Number of pages | 26 |
Journal | ACM Transactions on Economics and Computation |
Volume | 11 |
Issue number | 3-4 |
Early online date | 22 Sept 2023 |
DOIs | |
Publication status | Published - 19 Dec 2023 |
Funding
Yotam Gafni and Ron Lavi were partially supported by the ISF-NSFC joint research program (grant No. 2560/17). Xin Huang was partially supported by the Aly-Kaufman Fellowship. This research was supported by the Israel Science Foundation (grant No. 336/18).
Funders | Funder number |
---|---|
ISF-NSFC | 2560/17 |
Israel Science Foundation | 336/18 |
Keywords
- Fair division
- approximate envy-freeness
- resource allocation
ASJC Scopus subject areas
- Computer Science (miscellaneous)
- Computational Mathematics
- Economics and Econometrics
- Marketing
- Statistics and Probability