TLDR: A new research paper explores the existence of fair allocations for indivisible items under EFX and PMMS criteria. It establishes a formal separation, showing PMMS allocations don’t always exist where EFX does. Conversely, it proves the existence of EFX for personalized bivalued valuations and PMMS for factored bivalued, binary-valued MMS-feasible, and pair-demand valuations, providing polynomial-time algorithms for these cases.
The age-old problem of fair division, from the biblical story of Abraham and Lot to modern resource allocation, seeks to distribute resources among individuals in a way that satisfies certain fairness criteria. While infinitely divisible resources like cake have well-established solutions, the challenge intensifies when dealing with indivisible items, such as houses or cars, where splitting is not an option. This is the realm of discrete fair division, a complex area of study that has seen significant recent advancements.
A new research paper, titled “Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division,” delves into two prominent fairness concepts: Envy-Freeness up to any Good (EFX) and Pairwise Maximin Share (PMMS). EFX is a widely recognized standard where no individual prefers another’s share even after removing a single item from that share. PMMS, a stricter condition, ensures that for any two individuals, neither would prefer to be the “cutter” in a hypothetical two-way split of their combined items, guaranteeing them at least their maximin share.
The paper, authored by Jaros law Byrka, Franciszek Malinka, and Tomasz Ponitka, provides crucial new insights into these fairness notions, presenting both instances where fair allocations do not exist and, more optimistically, cases where they do. Their findings are particularly significant because they offer constructive proofs, meaning they not only show that an allocation exists but also provide polynomial-time algorithms to find it.
Separating EFX and PMMS
One of the paper’s most striking contributions is a formal separation between EFX and PMMS. While PMMS is generally considered a stronger condition that often implies EFX, the researchers constructed a specific scenario involving three agents (one with an additive valuation and two with arbitrary monotone valuations) where no PMMS allocation exists. This is notable because EFX allocations are known to exist under these very assumptions. This discovery highlights that proving the existence of PMMS allocations might require fundamentally different approaches compared to EFX.
Also Read:
- Unpacking the Nuances of AI Explanations: Facets and Diversity in Abductive Reasoning
- Unlocking Conditional Causal Effects in Complex Causal Graphs
New Existence Results for PMMS and EFX
Despite the non-existence result, the paper also brings good news by proving the existence of fair allocations for several important special cases. These positive results are particularly valuable as they come with practical, polynomial-time algorithms:
- Personalized Bivalued Valuations: For situations where each agent values items at one of two specific amounts (e.g., a high value ‘A’ or a low value ‘B’ for each item), the paper proves that EFX allocations always exist. Furthermore, if these valuations are “factored” (meaning the higher value is a multiple of the lower value), then PMMS allocations are also guaranteed to exist. This generalizes previous work that only considered non-personalized bivalued valuations.
- Binary-Valued MMS-Feasible Valuations: In scenarios where an agent values any bundle as either ‘desirable’ (value 1) or ‘non-desirable’ (value 0), and their valuations satisfy a condition called MMS-feasibility, the paper shows that PMMS allocations exist. Crucially, this result holds even without assuming that agents prefer more items to fewer (monotonicity), making it applicable to the fair division of “chores” (undesirable items) or “mixed manna” (a mix of goods and chores).
- Pair-Demand Valuations: This class of valuations extends the well-studied “unit-demand” case (where agents want at most one item) to situations where agents derive value from at most two items. The research demonstrates that PMMS allocations exist in this setting.
The methods used for these proofs are innovative, including an adaptation of the “Match-and-Freeze” algorithm for personalized bivalued valuations and a novel “Cut-and-Choose-Graph” procedure for binary-valued valuations. These algorithmic approaches ensure that the fair allocations can be computed efficiently.
This research significantly advances our understanding of fair division with indivisible items, particularly concerning the less-explored PMMS criterion. While addressing several long-standing questions, the paper also opens new avenues for future research, including exploring the existence of PMMS under different valuation structures and refining the conditions for EFX. For a deeper dive into the technical details, you can access the full research paper here.
