Metraipolis › archive › dc_894dea99d60d
Rival-Injective Allocations: Support-List Structure and Maximum-Anchor EFX$_0$ Certificates — arXiv:2608.30203
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.30203
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T08:19:27.224Z
- SHA-256 of the archived text
e928be4b2da91a146e85b2affd0db07d12a907d20c7807614ffbf1bd150e6d88- Stable URL of this page
https://metraipolis.com/documento/dc_894dea99d60d
How to cite
Rival-Injective Allocations: Support-List Structure and Maximum-Anchor EFX$_0$ Certificates — arXiv:2608.30203 — arXiv (en), https://arxiv.org/abs/2608.30203 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_894dea99d60d (Metraipolis archive dc_894dea99d60d, sha256 e928be4b2da91a146e85b2affd0db07d12a907d20c7807614ffbf1bd150e6d88)
BibTeX
@misc{dc894dea99d60d,
title = {Rival-Injective Allocations: Support-List Structure and Maximum-Anchor EFX$_0$ Certificates — arXiv:2608.30203},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.30203},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_894dea99d60d; sha256 e928be4b2da91a146e85b2affd0db07d12a907d20c7807614ffbf1bd150e6d88},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.30203. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-01 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2608.30203 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-17T08:08:10.912Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).