Metraipolis › archive › dc_d28586bbf6ad
Weighted Fair Division of Indivisible Mixed Manna — arXiv:2609.01580
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.01580
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T06:42:46.102Z
- SHA-256 of the archived text
2f5b70ee2cc01865b3c321e4ea5133011181bb593062bdf7cfe6fa6d4bbcbf88- Stable URL of this page
https://metraipolis.com/documento/dc_d28586bbf6ad
How to cite
Weighted Fair Division of Indivisible Mixed Manna — arXiv:2609.01580 — arXiv (en), https://arxiv.org/abs/2609.01580 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d28586bbf6ad (Metraipolis archive dc_d28586bbf6ad, sha256 2f5b70ee2cc01865b3c321e4ea5133011181bb593062bdf7cfe6fa6d4bbcbf88)
BibTeX
@misc{dcd28586bbf6ad,
title = {Weighted Fair Division of Indivisible Mixed Manna — arXiv:2609.01580},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.01580},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d28586bbf6ad; sha256 2f5b70ee2cc01865b3c321e4ea5133011181bb593062bdf7cfe6fa6d4bbcbf88},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.01580. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study weighted fair division of indivisible mixed manna under additive valuations. First, we resolve the general existence open question for weighted envy-freeness up to one item (WEF1), and show that every instance with arbitrary positive entitlements admits a complete WEF1 allocation computable in polynomial time. We then show that existence does not imply any welfare guarantee, i.e., the utilitarian price of WEF1 is infinite, even for two unweighted agents with normalized valuations, common item signs, and singleton values in a fixed four-value set; a welfare-maximizing WEF1 allocation in the construction is fractionally Pareto optimal. Second, suppose each agent $i$ has a number $a_i>0$ such that their valuation for any item is $-a_i$, $0$, or $a_i$. Then, for arbitrary entitlements, a weighted maximin share (WMMS) allocation always exists, is computable in polynomial time, and can be chosen to be fractionally Pareto optimal. An exact formula for each WMMS value leads to a polynomial-time flow algorithm. In this class, every WEF1 allocation satisfies a best possible additive WMMS guarantee whose loss depends on the agent's entitlement relative to the largest entitlement. Thus maximum entitlement agents receive exact WMMS and, under equal entitlements, every WEF1 allocation is also MMS-fair. Allowing a second positive magnitude can violate exact WMMS, while unrestricted entitlement ratios rule out any fixed multiplicative WMMS guarantee compatible with WEF1 for chores. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-02 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2609.01580 — 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-17T06:37:13.272Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).