Metraipolis › archive › dc_a92fdca17258
A Polynomial Time Characterization For Strongly EFX Orientable Graphs — arXiv:2609.36498
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.36498
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T17:25:51.790Z
- SHA-256 of the archived text
72133e37d3944b644f1a8b2e4dd01206e8a3fc3c6ca56770fedefaa9004de5b3- Stable URL of this page
https://metraipolis.com/documento/dc_a92fdca17258
How to cite
A Polynomial Time Characterization For Strongly EFX Orientable Graphs — arXiv:2609.36498 — arXiv (en), https://arxiv.org/abs/2609.36498 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a92fdca17258 (Metraipolis archive dc_a92fdca17258, sha256 72133e37d3944b644f1a8b2e4dd01206e8a3fc3c6ca56770fedefaa9004de5b3)
BibTeX
@misc{dca92fdca17258,
title = {A Polynomial Time Characterization For Strongly EFX Orientable Graphs — arXiv:2609.36498},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.36498},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a92fdca17258; sha256 72133e37d3944b644f1a8b2e4dd01206e8a3fc3c6ca56770fedefaa9004de5b3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.36498. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Discrete fair division is the problem of dividing a discrete set of goods among agents in a fair manner. In this setting, one of the most sought-after notions of fairness is envy-freeness up to any good (EFX). In 2023, Christodoulou, Fiat, Koutsoupias, and Sgouritsa introduced the idea of a graphical valuation, where the fair division problem is represented by a simple graph where vertices are the agents and the edges are the goods, and each vertex only values incident edges. They showed that an EFX allocation always exists, while determining the existence of an EFX orientation is NP-hard. They posed a open question of determining which graphs always admit an EFX orientation regardless of valuation. These graphs, called strongly EFX orientable graphs, were first studied by Zeng and Mehta in 2025, who demonstrated that all such graphs have chromatic number at most 3, and bipartite graphs always admit an EFX orientation regardless of valuation. In this manuscript, we finish resolving this question by giving a polynomial time characterization of strongly EFX orientable graphs. In particular, we show that a connected graph $G$ is strongly EFX orientable if and only if either of the following is true: (1) $G$ is bipartite, or (2) the block decomposition of $G$ contains exactly one nonbipartite block $B$, and there exists a vertex $v \in B$ such that the degree of $v$ within $B$ is 2 and $G-v$ is bipartite. This proof was discovered by AI, with human intervention to break the problem into the appropriate subproblems. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-30 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2609.36498 — 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-07T16:57:11.431Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).