Researchers Find Optimal Way to Fix Unfair Allocations via Exchanges

Fair division of indivisible goods is a classic problem, but real-world allocations often start unfair. A new theoretical paper by Sheung Man Yuen, Ayumi Igarashi, Naoyuki Kamiyama, and Warut Suksompong tackles this by asking: how many exchanges (swaps of goods between agents) are needed to reach an envy-free up to one good (EF1) allocation from an arbitrary starting point? EF1 ensures every agent prefers their own bundle over any other bundle after removing at most one item, a widely accepted fairness criterion. The authors present comprehensive complexity results, showing that the problem ranges from polynomial-time solvable to NP-hard depending on the number of agents and whether utilities are additive, identical, or lexicographic. This provides a clear map of when reformation is computationally feasible.

One standout result is essentially tight bounds on the worst-case number of exchanges required when the initial allocation is balanced (each agent starts with the same number of items). In many settings, the number of swaps needed is at most the number of agents times a constant, meaning fair outcomes are achievable with surprisingly little disruption. The work, appearing in the 36th International Symposium on Algorithms and Computation (ISAAC 2025) and later in Algorithmica, bridges theoretical computer science and practical resource allocation, offering guidance for real-world disputes over inheritances, divorce settlements, or shared assets.