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

CREATOREva Deltl
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-11372

Browse the full library · About the Tower of Babel