Computing Envy-Free up to Any Good (EFX) Allocations via Local Search

Simina BrânzeiarXiv 2025 · DOI · arXiv

Introduction

In the field of fair division, the challenge of allocating indivisible goods among agents is a fundamental problem. While Envy-Freeness (EF) is the ideal standard, it is often unattainable. Researchers have turned to relaxations like EFX (Envy-Free up to Any Good), which requires that no agent envies another after the removal of any single item from the other's bundle. Despite its theoretical appeal, the existence of EFX allocations for more than three agents remains one of the most significant open questions in the field. This paper presents a simple yet powerful local search algorithm that empirically finds EFX allocations for a wide variety of instances.

The Local Search Framework

The proposed approach utilizes Simulated Annealing to navigate the space of possible allocations. The algorithm aims to minimize an objective function representing the total number of EFX violations across all agent pairs. By employing "single-transfer" moves—shifting one item from one agent to another—the search explores the landscape. To avoid local minima, the algorithm occasionally accepts moves that increase violations, with a probability controlled by a decreasing "temperature" parameter.

Theoretically, the paper provides a new proof of existence for the specific case of identical valuations, showing that a strict-descent process on a potential function (the variance of bundle values) always leads to an EFX state.

The Complexity of the Item-to-Agent Ratio

A key finding of the research is that the difficulty of finding an EFX allocation is primarily driven by the item-to-agent ratio ($m/n$). Experimental results reveal a distinct "hardness peak" when $m/n \approx 3.5$. In this regime, the average runtime for the algorithm reaches its maximum.

Runtime analysis across different item-to-agent ratios, highlighting the hardness peak and the transition to easier regimes as items become abundant.

Interestingly, as the number of items increases relative to agents ($m/n > 25$), the problem becomes computationally trivial. In these "item-abundant" scenarios, EFX allocations are prevalent, and the algorithm converges almost instantaneously.

Scalability and Empirical Performance

The algorithm demonstrated remarkable robustness, achieving 100% convergence across thousands of synthetic test cases, including uniform random and correlated valuations. This perfect success rate provides strong empirical evidence for the general existence of EFX allocations.

Average number of steps required for convergence as the number of agents ($n$) increases, demonstrating the algorithm's scalability.

The search scales efficiently to large instances. For example, with $n=15$ agents and $m=1000$ items, the algorithm typically finds a solution in just 2.2 seconds. As shown in the scaling analysis, the number of steps required grows predictably with the number of agents, allowing the method to handle hundreds of agents and thousands of items.

Conclusion

This work suggests that EFX allocations, while theoretically elusive, are practically accessible through simple local search techniques. The consistent success of simulated annealing across diverse regimes—from item-scarce to item-abundant—indicates that EFX states are not rare anomalies but common features of the allocation space. Future research may extend these findings to more complex preference structures beyond additive valuations.

Summary updated

BibTeX
@misc{branzei2025computing,
  author = {Simina Brânzei},
  title = {{Computing Envy-Free up to Any Good (EFX) Allocations via Local Search}},
  year = {2025},
  eprint = {2510.05429},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.05429},
}
Figure