Unified Fair Allocation of Goods and Chores via Copies

Yotam Gafni, Xin Huang, R Lavi, Inbal Talgam-Cohen

Research output: Contribution to journalArticlepeer-review

1 Citation (SciVal)
80 Downloads (Pure)

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 languageEnglish
Article number10
Number of pages26
JournalACM Transactions on Economics and Computation
Volume11
Issue number3-4
Early online date22 Sept 2023
DOIs
Publication statusPublished - 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).

FundersFunder number
ISF-NSFC2560/17
Israel Science Foundation336/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

    Fingerprint

    Dive into the research topics of 'Unified Fair Allocation of Goods and Chores via Copies'. Together they form a unique fingerprint.

    Cite this