Minimizing the Cost of EFx Allocations
Eva Deltl · 2026
Read Minimizing the Cost of EFx Allocations by Eva Deltl (2026) 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-2601-11372.txt.
Description
Eva Deltl joins fairness and low cost in one allocation problem. Her 2026 preprint defines the minCost-EFx allocation task. Fair sharing often ignores what a sharing plan costs. Cost cutting, in turn, often ignores what is fair.
Costs here can be transport, storage, or the like. The fairness bar is EFx, envy-free up to any item. It means no agent envies another once one item is dropped. The goal is an EFx split with the least cost of all. Deltl studies how hard that joint task is to solve. It is NP-hard even with just two agents in the split. That result sets a clear limit on exact solvers.
Catalog record
| CREATOR | Eva Deltl |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-11372