Source-linked AI summary
Reaching Fairness by Reallocating Goods
Robert Bredereck, Eva Deltl, Tanmay Inamdar, Pallavi Jain, Pranjal Pandey, Bin Sun
TL;DR
The paper asks how to repair a possibly unfair existing allocation while changing only a limited number of goods. It defines GOOD-BOUNDED reformability for EF, EF1, and EFX and analyzes its classical and parameterized complexity. Under a reallocation budget, these fairness notions largely share the same hardness behavior, with algorithms and complexity results mapped across valuation classes and parameters.
Problem
Prior fair-division research largely assumes goods are initially unallocated, although practical allocations may already exist and require fairness repairs with few assignment changes.
Method
The paper studies GOOD-BOUNDED β-REFORMABILITY, asking whether a β-fair allocation can be reached by changing the owners of at most k goods, for β ∈ {EF, EF1, EFX}.
Results
EF, EF1, and EFX exhibit essentially the same hardness behavior under a reallocation budget, alongside a comprehensive classical and parameterized complexity map.
Takeaways & Limitations
The computational separation between EF and its relaxations largely disappears when fairness is achieved through bounded reallocations.
Takeaways & Limitations
The study leaves other fairness notions, mixed manna, approximation algorithms, and structurally restricted reallocation models for future work.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies achieving EF, EF1, or EFX from an existing allocation while changing at most k goods, mapping the classical and parameterized complexity of this objective. Its central finding is that the usual computational gap between EF1 and stronger fairness notions largely disappears under a reallocation budget.
- Motivation: Existing allocations may become unfair after preferences, agents, goods, or fairness requirements change, motivating repairs that alter few assignments.Applications include computational resources, courses or rooms, and employee tasks or projects.
- Problem formulation: The model differs fundamentally from sequential-transfer restoration because intermediate allocations need not preserve fairness or follow valid transfers.Consequently, an instance can be solvable under this paper’s objective but impossible under the prior valid-transfer model.
- Problem formulation: GOOD-BOUNDED β-REFORMABILITY asks whether a β-allocation can be reached from an initial allocation by reallocating at most k goods, for β ∈ {EF, EF1, EFX}.The reallocation cost counts goods whose owners change, and only the final allocation is constrained.
- Classical complexity: NP-hardness holds for GOOD-BOUNDED EF1-REFORMABILITY and GOOD-BOUNDED EFX-REFORMABILITY even with two agents.The paper also maps tractable and hard cases for identical, binary, and identical-binary valuations.
- Parameterized complexity: All variants have FPT algorithms parameterized by m, while n + vmax and n + k + vmax also yield FPT algorithms; parameter k has W[2]-hardness and an XP algorithm.The n + k + vmax algorithms are singly exponential in the parameters, improving on doubly-exponential ILP-based algorithms for n + vmax.
- Main results: EF1, EF, and EFX have essentially the same hardness behavior across valuation classes and parameterizations, unlike their classical complexity separation.The main stated exception is two agents with identical valuations, where EF1 remains tractable.
2 Preliminaries
The preliminaries define additive valuations, allocations, fairness notions, reallocation distance, and parameterized-complexity terminology. They also establish a reduction connecting EF and EFX and distinguish Hamming-distance reformability from sequential valid-transfer restoration.
- Model: An allocation partitions the indivisible goods among agents, and additive valuations assign a bundle the sum of its agents’ values for its goods.Binary valuations restrict each good’s value to {0,1}, while identical valuations use the same valuation function for every agent.
- Fairness notions: EF forbids envy, EF1 permits removing one good from an envied bundle, and EFX requires fairness after removing every good from that bundle.These definitions are stated pairwise for agents and use the evaluating agent’s valuation.
- Reallocation: Reallocation distance is the Hamming distance between allocations, counting goods whose assigned agents change.GOOD-BOUNDED reformability therefore constrains the number of changed owners rather than the number or validity of intermediate transfers.
- Parameterized complexity: FPT algorithms run in f(κ)·|x|^O(1), XP algorithms run in |x|^f(κ), and para-NP-hardness at a fixed parameter value rules out XP unless P = NP.The W-hierarchy provides a scale of parameterized intractability, including W[2]-hardness.
- Relation between fairness criteria: EF reformability reduces in polynomial time to EFX reformability by adding |A|(k + 1) zero-value dummy goods per construction.The reduction preserves the agents, budget, and maximum single-good valuation.
- Comparison to prior models: The paper’s Hamming-distance model can reach EF1 in two reallocations even when no valid-transfer sequence reaches EF1.Sequential restoration instead requires every single-good move not to create new EF1-envy.
3 Classical Complexity
The paper establishes broad classical hardness for GOOD-BOUNDED reformability, while identifying tractable exceptions for two agents with identical valuations and for identical binary valuations.
- NP-hardness holds for GOOD-BOUNDED EF1-REFORMABILITY even with two agents.
- NP-hardness holds for GOOD-BOUNDED β-REFORMABILITY with binary valuations for β ∈ {EF, EFX}, including two-agent identical valuations.
- O(m log m) time suffices for GOOD-BOUNDED EF1-REFORMABILITY with two agents and identical additive valuations.
- Three identical agents make GOOD-BOUNDED EF1-REFORMABILITY weakly NP-hard, while arbitrary agent counts yield NP-completeness under identical valuations.
- The problems are W[2]-hard parameterized by the number of reallocations k under binary valuations for EF, EF1, and EFX.
- O(n + m) time solves GOOD-BOUNDED β-REFORMABILITY for identical binary valuations when β ∈ {EF, EF1}, while EFX is solvable in O(m + n log n) time.
4 Parameterized Algorithms
The paper develops parameterized algorithms for GOOD-BOUNDED β-REFORMABILITY across EF, EF1, and EFX, using agent reduction, type-count representations, ILP, and dynamic programming. The resulting algorithms are fixed-parameter tractable under several parameterizations, with different runtime trade-offs depending on whether the budget k is small.
- Agent reduction: O(m^3) agents suffice after a polynomial-time reduction for EF1 and EFX reformability instances.The reduction marks agents associated with the initial allocation, individual goods, and pairs of goods, preserving equivalence.
- Parameter m and budget k: FPT in m and XP in k hold for GOOD-BOUNDED EF, EF1, and EFX-REFORMABILITY.For EF1 and EFX, exhaustive enumeration of reallocations takes O((nm)^k) time after reduction; EF uses a separate bound on relevant agents.
- Type-count representation: Type-count vectors represent allocations because goods with identical valuation vectors are interchangeable for valuation-based fairness criteria.The number of good types is bounded by (vmax + 1)^n, enabling formulations whose variable count depends on n and vmax.
- Dynamic programming: GOOD-BOUNDED β-REFORMABILITY is FPT in n + vmax + k, with a dynamic-programming state count linear in m for fixed parameters.The state bound is m · (k + 1) · (2kvmax + 1)^n^2 · (vmax + 1)^n^2, and the resulting algorithm applies to EF, EF1, and EFX.
5 Conclusion
The paper provides a comprehensive complexity map for GOOD-BOUNDED β-REFORMABILITY across EF, EF1, and EFX. Under a reallocation budget, these fairness notions usually exhibit the same hardness behavior, while approximation and broader reallocation models remain open directions.
- The study maps the complexity of GOOD-BOUNDED β-REFORMABILITY for β ∈{EF, EF1, EFX} across valuation classes and parameterizations.
- Under a reallocation budget, EF1, EFX, and EF usually exhibit the same hardness behavior, and their algorithmic approaches require only minor modifications.
- Extending the analysis to proportionality, maximin share, and mixed manna remains an open direction.
- Approximation algorithms for minimum reallocation distance and structurally restricted reallocation models remain appealing directions for future work.