Metraipolis › archive › dc_2f8c35cc33ea
Computing EF1 Allocations under Budget Constraints in Polynomial Time — arXiv:2611.12740
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.12740
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-10T18:47:20.021Z
- SHA-256 of the archived text
021f2a4913094f0ffc69cb264784abf1e615a15e72ec48ba7f63ae1a8cd2fd7c- Stable URL of this page
https://metraipolis.com/documento/dc_2f8c35cc33ea
How to cite
Computing EF1 Allocations under Budget Constraints in Polynomial Time — arXiv:2611.12740 — arXiv (en), https://arxiv.org/abs/2611.12740 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2f8c35cc33ea (Metraipolis archive dc_2f8c35cc33ea, sha256 021f2a4913094f0ffc69cb264784abf1e615a15e72ec48ba7f63ae1a8cd2fd7c)
BibTeX
@misc{dc2f8c35cc33ea,
title = {Computing EF1 Allocations under Budget Constraints in Polynomial Time — arXiv:2611.12740},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.12740},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2f8c35cc33ea; sha256 021f2a4913094f0ffc69cb264784abf1e615a15e72ec48ba7f63ae1a8cd2fd7c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.12740. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the fair allocation of indivisible items to agents with budget constraints and additive valuations. Each agent compares its own bundle with the subsets of another bundle that fit its budget. An allocation is envy-free up to one item (EF1) if, for every agent and every nonempty subset under comparison, removing an item of maximum value to that agent eliminates its envy. We require EF1 both between agents and towards the charity, which contains all unallocated items. EF1 allocations exist, but computing them in polynomial time has remained open even for homogeneous valuations. We resolve this problem with a polynomial-time algorithm for EF1 allocations under heterogeneous valuations. We also prove that detecting an EF1 violation is NP-complete. Equivalently, checking whether a given allocation is EF1 is coNP-complete. Finally, we give polynomial-time algorithms for envy-freeness up to any item (EFX) both when each agent's valuation is proportional to item size and when each agent has a fixed number of distinct positive item values. As an application, for homogeneous valuations and any $\varepsilon>0$, we obtain an EF1 allocation with at least a $(1/2-\varepsilon)$ fraction of the maximum social welfare in time polynomial in the input length and $1/\varepsilon$. Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno). Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2611.12740 — 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-11-10T18:39:07.429Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).