Fair Division of Indivisible Goods: A Survey

Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros A. VoudourisIJCAI 2022 · DOI

TL;DR

This survey provides a comprehensive overview of the latest advancements in the field of fair division for indivisible goods, focusing on additive valuation functions and progress made in the last decade. It highlights key fairness notions like envy-freeness and maximin share fairness, along with their relaxations (EF1, EFX), and discusses the challenges and open problems in achieving these fairness criteria computationally.

What Problem Does This Paper Address?

The fundamental problem of fair division, which aims to allocate resources equitably among individuals, has a long history. While early work focused on infinitely divisible resources, the allocation of indivisible goods presents significant computational challenges. Ensuring fairness in such scenarios often requires defining and achieving specific criteria, such as envy-freeness (no one envies another's bundle) or maximin share fairness (each person gets at least their guaranteed minimum share). However, achieving these ideals perfectly can be impossible or computationally intractable. This paper surveys the recent progress in defining and achieving relaxed notions of fairness for indivisible goods, particularly focusing on additive valuation functions, and identifies key open questions in the field.

Methods

The paper surveys various algorithmic and theoretical approaches to fair division of indivisible goods. Key methods discussed include:

  • Envy-Cycle Elimination: An algorithmic technique for achieving EF1 allocations by iteratively identifying and resolving envy cycles among agents.
  • Round-Robin: A simple drafting algorithm where agents take turns selecting their most preferred available good, which is shown to achieve EF1 allocations for additive valuations.
  • Nash Welfare Maximization: The concept of finding allocations that maximize the product of agents' valuations, which has been shown to be related to EF1 and Pareto optimality.
  • Relaxations of Fairness Notions: The core of the survey lies in discussing various relaxations of envy-freeness and proportionality, such as EF1 (envy-freeness up to one good) and EFX (envy-freeness up to any good). These relaxations are crucial for making the problem tractable.
  • Approximation Algorithms: For notions where exact fairness is hard to achieve, the paper discusses algorithms that guarantee allocations that are "close" to fair, often expressed as an $\alpha$-approximation.
  • Mechanism Design: The survey touches upon strategic aspects, where agents might misreport their preferences, and the design of mechanisms that incentivize truthful reporting while ensuring fairness.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and algorithmic approaches rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Indivisibility is Hard: The core takeaway is that allocating indivisible goods is fundamentally harder than allocating divisible ones. Simple notions like envy-freeness are often impossible to achieve, necessitating the exploration of relaxations.
  • Relaxations are Key: Concepts like EF1 and EFX are not just theoretical curiosities; they represent crucial steps towards practical fair division algorithms. EF1 is relatively easy to achieve algorithmically, while EFX remains a significant open challenge.
  • The Trade-off Between Fairness and Computability: There's a constant tension between achieving strong fairness guarantees and the computational feasibility of finding such allocations. Many problems that are NP-hard for exact fairness become tractable with relaxations or approximations.
  • Connections Between Notions: The paper highlights interesting relationships between different fairness notions (e.g., envy-freeness implies EFX, which implies EF1) and their connections to other desirable properties like Pareto optimality and Nash welfare.
  • Open Problems Drive Research: The survey explicitly lists several open problems, indicating active areas of research and the frontiers of the field. These problems often involve pushing the boundaries of approximation ratios or proving general existence/non-existence results.

Key Results

  • EF1 is Achievable: Algorithms like Envy-Cycle Elimination and Round-Robin can efficiently compute EF1 allocations for agents with additive valuations.
  • EFX is Challenging: While EFX allocations are known to exist for two and three agents, their existence and efficient computation for four or more agents with general additive valuations remain open problems.
  • MMS Approximations: For Maximin Share Fairness (MMS), exact allocations are not always guaranteed, but approximation algorithms exist. The best known approximation bound for additive valuations is around 3/4, with a lower bound of 39/40 for inapproximability.
  • MNW and EF1/PO: Maximum Nash Welfare (MNW) allocations are always EF1 and Pareto optimal, but computing them is generally hard.

Limitations and Future Work

  • General EFX Existence: The most significant open problem is whether an EFX allocation always exists for $n \ge 4$ agents with unrestricted additive valuations.
  • Approximation Ratios: Improving the approximation ratios for MMS and other notions, and establishing tighter inapproximability bounds, are active research directions.
  • Strategic Agents: While some progress has been made, understanding fair division in the presence of strategic agents and designing truthful mechanisms remains a complex area.
  • Other Valuation Functions: The survey primarily focuses on additive valuations. Extending results to more general valuation functions (e.g., submodular, XOS) is an ongoing area of research.
  • Fairness with Constraints: Incorporating real-world constraints (e.g., connectivity, budget) into fair division problems is a growing area.
  • Group Fairness and Online Settings: The paper briefly touches upon group fairness and online fair division, suggesting these are also fertile grounds for future research.

Summary updated

BibTeX
@inproceedings{amanatidis2022fair,
  author = {Georgios Amanatidis and Georgios Birmpas and Aris Filos-Ratsikas and Alexandros A. Voudouris},
  title = {{Fair Division of Indivisible Goods: A Survey}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/756},
}
Figure