Fair Division: The Computer Scientist's Perspective

Toby WalshIJCAI 2020 · DOI

TL;DR

This paper surveys how computer science, particularly AI, has revolutionized the classic problem of fair division. By applying computational tools and framing it as an algorithmic challenge, researchers have gained new insights into how to divide indivisible goods fairly and efficiently, leading to a deeper understanding of its complexity and the development of practical mechanisms.

What Problem Does This Paper Address?

The paper tackles the age-old problem of "fair division," which concerns how to allocate resources (items) among multiple individuals (agents) in a way that is both equitable and efficient. This problem arises in countless real-world scenarios, from allocating donated organs to patients and distributing food to charities, to dividing water rights among farmers. While the concept of fairness has been debated for centuries, the advent of computer science has brought a new computational perspective, asking not just what constitutes a fair division, but how we can computationally achieve it, and what the inherent limitations are. The paper specifically focuses on the division of indivisible items, meaning items that cannot be split into smaller parts.

Methods

The paper highlights a range of computational techniques and approaches that computer scientists have brought to bear on fair division problems:

  • Knowledge Representation and Reasoning: This involves finding compact ways to represent agents' preferences over potentially exponentially many combinations of items, and developing efficient algorithms to reason about these preferences to find fair and efficient allocations.
  • Computational Complexity: Analyzing the inherent difficulty of fair division problems. This includes identifying problems that are NP-hard, PSPACE-hard, or even coNP-complete, suggesting that finding exact optimal solutions might be computationally infeasible for large instances.
  • Approximation Methods: When exact solutions are intractable, computer scientists develop algorithms that find "good enough" solutions. This includes relaxations of strict fairness notions like envy-freeness (e.g., envy-freeness up to one good - EF1) and developing mechanisms that guarantee these approximate fairness properties.
  • Game Theory: Modeling the interactions between agents as a game, and analyzing strategic behavior. This involves studying concepts like Nash equilibria and strategy-proofness, and understanding how agents might try to manipulate mechanisms to their advantage.
  • Online Algorithms: Addressing scenarios where items or agents arrive over time, and decisions must be made without complete information about the future. This introduces challenges in balancing immediate fairness with long-term efficiency.
  • Parameterized Complexity: Identifying specific parameters (e.g., the number of "multi-valued" items) that, if small, allow for efficient computation even if the general problem is hard.
  • Communication Complexity: Analyzing the amount of information that agents need to exchange to reach a fair allocation, particularly in distributed settings.
  • Empirical Analysis: Testing algorithms and mechanisms on real-world data and synthetic benchmarks to understand their performance in practice and identify patterns, such as phase transitions in the existence of fair allocations.

Datasets

Not discussed in the paper. The paper focuses on theoretical and algorithmic aspects rather than empirical evaluation on specific datasets. It mentions the existence of real-world data from websites like spliddit.org and PrefLib.org that have driven empirical analysis in the field.

Key Insights and Ideas

  • Computational Perspective is Key: Framing fair division as a computational problem has unlocked new avenues of research, revealing complexities and enabling the design of practical algorithms that were previously unimaginable.
  • Trade-offs are Inevitable: Achieving perfect fairness (like envy-freeness) and perfect efficiency simultaneously is often impossible, especially in online settings. This necessitates exploring approximations and understanding the cost of fairness.
  • Complexity Varies Wildly: Even simple preference structures (like additive utilities) can lead to computationally intractable problems for finding exact fair and efficient allocations. However, specific parameters can make these problems tractable.
  • Strategic Behavior is Complex: While agents might have incentives to behave strategically, computing optimal strategic play can be computationally very hard, sometimes even more so than finding a fair allocation directly.
  • Approximations are Powerful: Relaxations of strict fairness notions, like envy-freeness up to one good (EF1), are often achievable and provide a practical path towards fair outcomes when exact solutions are out of reach.
  • Online Settings Introduce New Challenges: The uncertainty inherent in online problems makes it impossible to guarantee both Pareto efficiency and envy-freeness ex ante, forcing a choice between them.

Key Results

  • Intractability of Exact Solutions: Deciding the existence of an efficient and envy-free allocation is generally NP-hard, even under strong domain restrictions. Computing subgame perfect Nash equilibria for sequential allocation games is PSPACE-hard.
  • Tractability of Approximations: Mechanisms like sequential allocation in a round-robin fashion are guaranteed to produce envy-free up to one good (EF1) allocations. Maximizing Nash welfare is also EF1 and Pareto efficient.
  • Parameterized Tractability: For sequential allocation, the problem of computing optimal play becomes polynomial if the number of items with differing agent utilities is bounded.
  • Online Impossibility: No online mechanism can guarantee both Pareto efficiency and envy-freeness ex ante.
  • Price of Envy-Freeness: The welfare cost of insisting on envy-freeness can grow with the number of agents.

Limitations and Future Work

  • Bads and Mixed Manna: The paper notes that fair division of "bads" (items agents dislike) and "mixed manna" (both goods and bads) is an emerging area with unique challenges, as results for goods don't always translate.
  • Open Questions: Several open questions remain, including whether EFX allocations always exist for three agents, how to compute optimal play efficiently for sequential allocation with three agents, and identifying other appealing approximations of fairness.
  • Computational vs. Practical: While theoretical results show tractability for certain parameterized problems, the practical efficiency of algorithms designed for specific problems often outperforms general approaches like solving bounded-dimension Integer Linear Programs.
  • Understanding Phase Transitions: Further empirical and theoretical work is needed to understand phase transitions in the existence of fair allocations and how their difficulty compares across different properties.
  • Applying CS/AI Tools: The paper suggests exploring the application of other CS/AI tools like automated reasoning and machine learning to design better fair division mechanisms and to understand other social choice problems.

Summary updated

BibTeX
@inproceedings{walsh2020fair,
  author = {Toby Walsh},
  title = {{Fair Division: The Computer Scientist's Perspective}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/691},
}
Figure