Online Fair Division: A Survey

Martin Aleksandrov, Toby WalshAAAI 2020 · DOI

Introduction

In classical fair division theory, researchers typically assume a "God's eye view" where all items, participants, and preferences are known upfront. However, real-world scenarios—such as food bank donations, organ matching, or airport slot allocation—are inherently sequential and uncertain. This survey explores the field of online fair division, where resources or agents arrive over time, necessitating decisions without full knowledge of the future.

The core challenge is managing uncertainty. Allocating a resource immediately might prevent a better match later, but waiting too long might lead to resource expiration. This paper categorizes these problems by resource type (divisible vs. indivisible), arrival patterns (items, agents, or both), and the information available to the mechanism (informed vs. uninformed).

Taxonomy of Online Mechanisms

The authors classify online fair division along three primary dimensions:

  1. Resource Types: Distinguishing between single vs. multiple items and divisible (e.g., cake) vs. indivisible (e.g., discrete goods) resources.
  2. Online Features: Identifying whether items arrive over time (e.g., food banks), agents arrive over time (e.g., party guests), or both (e.g., organ matching).
  3. Mechanism Features: Evaluating whether a system is "informed" (possessing probabilistic data about future arrivals) or "uninformed" (acting without prior knowledge).

Commonly analyzed mechanisms include:

  • LIKE: Randomly allocates an item to an agent who expresses interest.
  • Balanced LIKE: Prioritizes agents who have received fewer items to maintain balance.
  • Online Serial Dictator (OSD): Allocates items based on a fixed priority queue.

Key Insights: The Fairness-Efficiency Trade-off

A central theme in online fair division is the tension between different axiomatic properties. Unlike offline settings, achieving perfect fairness and efficiency simultaneously is often impossible.

Relationships between fairness and efficiency properties for various online mechanisms.
  • The Strategy-Proofness Paradox: While preventing manipulation is difficult offline, Online Strategy-Proofness (OSP) is often easier to achieve because agents are committed to past choices and cannot predict future arrivals.
  • Fairness vs. Efficiency: Theorem 1 establishes that with general utilities, no online mechanism can be both perfectly envy-free (EFA) and Pareto efficient (PEA/PEP) before all items are distributed.
  • Vanishing Envy: Since perfect fairness is elusive, researchers focus on "asymptotic guarantees," where the ratio of envy to the number of items approaches zero as the system scales.
  • Reallocation: Fairness can sometimes be restored by reallocating items, though this may require moving a significant number of goods ($\Theta(m)$).

Comparative Analysis of Mechanisms

The paper provides a rigorous comparison of mechanism properties under different utility models (general, identical, and binary).

Table 1: Properties of online mechanisms under various cardinal utility assumptions.

Key findings from this analysis include:

  • LIKE maintains strategy-proofness and envy-freeness in expectation but fails on Pareto efficiency.
  • Balanced LIKE improves long-term fairness but sacrifices strategy-proofness. Interestingly, the complexity of "gaming" this mechanism often serves as a natural deterrent to dishonest reporting.
  • Randomization: Simple random allocation remains a robust baseline, particularly when the mechanism has no information about future arrivals.

Future Directions

The survey identifies several open challenges for the field:

  • Correlated Preferences: Most models assume independent preferences, yet in many real-world cases (like charities), multiple agents may value the same resources similarly.
  • Online Chore Division: While most research focuses on "goods," there is a growing need to study the fair distribution of "bads" or tasks.
  • Artificial Arrivals: Applying online mechanisms to offline problems by imposing a synthetic arrival order could offer new computational efficiencies for complex fair division tasks.

Summary updated

BibTeX
@inproceedings{aleksandrov2020online,
  author = {Martin Aleksandrov and Toby Walsh},
  title = {{Online Fair Division: A Survey}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i09.7081},
}
Figure