Rival-Injective Allocations: Support-List Structure and Maximum-Anchor EFX$_0$ Certificates
2026-08-31 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors explore ways to fairly divide goods among agents who each value the goods differently, focusing on a fairness concept called all-good envy-freeness up to any good (EFX₀). They introduce a method called rival-injective (RI) ownership, which assigns goods so that each item valued by multiple agents is given in a controlled way to those who value it, using ideas from graph coloring. They provide precise conditions and an algorithm to find such fair allocations efficiently under certain assumptions, and describe examples that challenge previous methods. However, determining if such fair divisions exist in all general cases remains an open problem.
EFX (Envy-Freeness up to any good)Additive valuationsRival-injective ownershipGraph coloringProper list coloringPair-capacity criterionConstraint satisfaction problem (CSP)Fair divisionMaximum-valued singletonAlgorithmic complexity
Authors
Junshuo Wang
Abstract
We study complete allocations under nonnegative additive valuations through the positive supports of goods, focusing on the all-good form of envy-freeness up to any good (EFX$_0$). We define rival-injective (RI) endpoint ownership: every good with nonempty positive support is assigned to an agent who values it positively, and every ordered observer--owner pair is used by at most one good. RI ownership is exactly proper list coloring of the graph joining goods whose positive supports overlap in at least two agents. For pair-supported goods with arbitrary exceptional goods, fixing the exceptional owners yields a necessary-and-sufficient pair-capacity criterion and an exact finite-domain owner constraint satisfaction problem (CSP). Every RI allocation in which each agent's own bundle is worth at least her maximum-valued singleton is all-good EFX$_0$. A specified injective choice of maximum-singleton anchors, together with residual support-list degeneracy, constructs such an allocation by reverse greedy coloring in $O(nm^2)$ time. We give two explicit witness families: a nonempty relatively open, 22-dimensional cone on a fixed $4\times10$ support face, and a family for every $n\ge4$ with two universal-support goods and $m=(n-1)(n-2)+2$ goods. Both fail unanchored list degeneracy and are not implied by the explicit pure-multigraph or published high-girth/controlled-multiplicity hypotheses compared here. We also study recognition of the maximum-anchor certificate class, leaving its general complexity unresolved. The exact list-coloring and pair-capacity results concern RI ownership, not general EFX$_0$ existence; unrestricted four-agent, ten-good all-good EFX$_0$ remains unresolved.