(Almost Full) EFX for Three (and More) Types of Agents

Pratik Ghosal, Vishwa Prakash Hv, Prajakta Nimbhorkar, Nithin VarmaAAAI 2025 · DOI

Abstract

This paper advances the study of fair division by proving the existence of Envy-Free up to Any good (EFX) allocations in settings with heterogeneous agents. The authors demonstrate that for any number of agents $n$ partitioned into $k$ distinct valuation types, an EFX allocation exists that leaves at most $k-2$ goods unallocated. Furthermore, they prove that a complete EFX allocation—where every item is distributed—is guaranteed to exist if at least $n-2$ agents share the same valuation function. These results generalize recent breakthroughs in the field and provide a new framework for addressing agent heterogeneity through the lens of valuation types.

Introduction

In the field of computational social choice, fair division explores how to distribute indivisible resources among agents such that the resulting allocation is perceived as fair. While Envy-Freeness (EF)—a state where no agent prefers another's bundle over their own—is the gold standard, it is often mathematically impossible when items cannot be split. This has led researchers to focus on relaxations, most notably Envy-Freeness up to Any good (EFX).

An allocation is considered EFX if, for any two agents $i$ and $j$, agent $i$ does not envy agent $j$ after the removal of any single item from $j$'s bundle. Despite being viewed as the most natural and robust fairness notion for indivisible goods, proving that an EFX allocation always exists for more than three agents has remained one of the most significant open challenges in the field. This paper approaches the problem by focusing on the complexity of agent preferences, specifically looking at scenarios where many agents share identical valuation types.

Results for $k$ Valuation Types

The authors first address the general case of $n$ agents who share $k$ distinct valuation functions. Their findings suggest that the difficulty of finding EFX allocations scales with the number of preference types rather than the total number of agents.

Theorem 1: For $n$ agents with $k$ distinct additive (or nice-cancelable) valuations, an EFX allocation exists with at most $k-2$ unallocated goods. Importantly, in this allocation, no agent envies the pile of leftover goods.

To prove this, the authors utilize a "Leading Agent" strategy. By grouping agents by their valuation type, they identify a "leading agent" within each group—the individual currently holding the least valuable bundle according to that group's specific preferences. The authors prove that if these leading agents are satisfied (EFX), the remaining agents in their respective groups will also be satisfied. By applying Pareto-dominating improvements on a reduced envy graph, the algorithm iteratively refines the allocation until the number of unallocated items is minimized to $k-2$.

The Case of Two Outliers

A second major contribution of the paper is the resolution of the "two outliers" case, where the vast majority of agents share identical preferences.

Theorem 2: If at least $n-2$ agents have identical valuations, a complete EFX allocation always exists.

This proof relies on a sophisticated potential function analysis. The authors define a potential based on the minimum value assigned to bundles by the majority group. Starting from an "almost EFX-feasible" allocation, they demonstrate that it is always possible to perform a swap or a re-allocation (utilizing the Plaut-Roughgarden algorithm) that strictly increases the potential function. Because the potential cannot increase indefinitely, the process is guaranteed to terminate in a complete EFX allocation. This result shows that the existence of EFX is robust even when two agents have entirely unique and arbitrary preferences.

Significance and Generalization

These findings represent a significant step forward in the EFX existence problem. By focusing on valuation types, the authors generalize several recent high-profile results:

  • The proof that EFX exists for 3 agents (Chaudhury et al., 2024) is a special case of this paper's $k=3$ result.
  • The result for 4 agents with one unallocated good (Berger et al., 2022) is encompassed by the $k=4$ theorem.

Furthermore, the results are not limited to simple additive valuations. They extend to broader classes of functions, including "nice-cancelable" and "MMS-feasible" valuations, which better capture the nuances of complex human preferences.

Limitations and Future Directions

While the paper significantly narrows the gap toward a general existence proof, several challenges remain. The theorem for $k$ types still leaves a small number of goods ($k-2$) unallocated. Closing this gap to achieve a complete allocation for any $k$ remains an open problem. Additionally, while the "complete" result holds for two outliers, extending this to three or more agents with unique valuations likely requires the development of even more complex potential functions. Finally, while the paper focuses on the mathematical existence of these allocations, future work could further explore the computational time complexity of these algorithms in various edge cases.

Summary updated

BibTeX
@inproceedings{ghosal2025almost,
  author = {Pratik Ghosal and Vishwa Prakash HV and Prajakta Nimbhorkar and Nithin Varma},
  title = {{(Almost Full) EFX for Three (and More) Types of Agents}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33519},
}
Figure