Whoever Said Money Won’t Solve All Your Problems? Weighted Envy-free Allocation with Subsidy

Noga Klein Elmalem, Haris Aziz, Rica Gonen, Xin Huang, Kei Kimura, Indrajit Saha, Erel Segal-Halevi, Zhaohong Sun, Mashbat Suzuki, Makoto Yokoo · 2025

Read Whoever Said Money Won’t Solve All Your Problems? Weighted Envy-free Allocation with Subsidy by Noga Klein Elmalem, Haris Aziz, Rica Gonen, Xin Huang, Kei Kimura, Indrajit Saha, Erel Segal-Halevi, Zhaohong Sun, Mashbat Suzuki, Makoto Yokoo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09006.txt.

Description

Noga Klein Elmalem and co-authors solve a fairness puzzle in a 2025 paper on sharing goods. Items that cannot be split must go to agents with unequal entitlements, set by weights. A fair split means each agent, judged against their own weight, finds their share at least as good as anyone else's.

Often no such split exists from goods alone. Cash paid by a third party can close the gap, but the bill should stay bounded. Past tools for the equal weight case fail once weights enter. The authors give fast algorithms that find a fair split with bounded subsidy in this harder weighted setting.

Catalog record

CREATORNoga Klein Elmalem, Haris Aziz, Rica Gonen, Xin Huang, Kei Kimura, Indrajit Saha, Erel Segal-Halevi, Zhaohong Sun, Mashbat Suzuki, Makoto Yokoo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE132 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-09006

Browse the full library · About the Tower of Babel