Fair-Share Allocations for Agents with Arbitrary Entitlements

Moshe Babaioff (), Tomer Ezra () and Uriel Feige ()
Additional contact information
Moshe Babaioff: The Hebrew University of Jerusalem, Jerusalem 9190501, Israel
Tomer Ezra: Sapienza University of Rome, 00185 Rome, Italy
Uriel Feige: Weizmann Institute, Rehovot 7610001, Israel

Mathematics of Operations Research, 2024, vol. 49, issue 4, 2180-2211

Abstract: We consider the problem of fair allocation of indivisible goods to n agents with no transfers. When agents have equal entitlements, the well-established notion of the maximin share (MMS) serves as an attractive fairness criterion for which, to qualify as fair, an allocation needs to give every agent at least a substantial fraction of the agent’s MMS. In this paper, we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. Even for the equal entitlements case, this notion is new and satisfies APS ⩾ MMS , for which the inequality is sometimes strict. We present two equivalent definitions for the APS (one as a minimization problem, the other as a maximization problem) and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a 3 5 - fraction of the agent’s APS. This algorithm can also be viewed as providing strategies in a certain natural bidding game, and these strategies secure each agent at least a 3 5 - fraction of the agent’s APS.

Keywords: Primary: 91B32; 91B15; fair division; indivisible goods; unequal entitlements; maximin share (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.0199 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:4:p:2180-2211

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().