Reaching Fairness by Reallocating Goods
2026-08-31 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to make divisions of items fair when there is already an existing, possibly unfair way the items are divided. They focus on three fairness ideas: envy-freeness (no one prefers someone else's share), envy-freeness up to one good (envy can be fixed by removing one item), and envy-freeness up to any good (a stronger version). They try to achieve these fairness goals by changing the allocation of as few items as possible. The authors analyze how hard these problems are to solve using different computational approaches.
indivisible goodsfair allocationenvy-freeness (EF)EF1 (envy-freeness up to one good)EFX (envy-freeness up to any good)reallocationcomplexity theoryparameterized complexityfairness notionsalgorithmic fairness
Authors
Robert Bredereck, Eva Deltl, Tanmay Inamdar, Pallavi Jain, Pranjal Pandey, Bin Sun
Abstract
Fair allocation of indivisible goods has largely been studied under the assumption that no prior allocation exists. Motivated by practical settings with pre-existing (and possibly unfair) allocations, we study how to achieve fairness through limited reallocations. Building on recent work on reformability/reallocations, we consider three fairness notions---envy-freeness (EF), envy-freeness up to one good (EF1), and envy-freeness up to any good (EFX)---and optimize the number of goods reallocated. We analyze both the classical and parameterized complexity of these problems, providing a comprehensive analysis across multiple fairness notions.