Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods

Xiaolin Bu, Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai TaoarXiv 2024 · arXiv

TL;DR

This paper tackles the "Best-of-Both-Worlds" (BoBW) fair division problem, designing randomized algorithms that guarantee resource allocation fairness both in expectation (ex-ante) and in the actual realized outcome (ex-post). The authors provide the first polynomial-time algorithms to achieve ex-ante envy-freeness and ex-post EFX/EFM for two agents, and extend these guarantees to $n$ agents with bi-valued utilities while maintaining economic efficiency.

What Problem Does This Paper Address?

Fair division is the study of how to allocate resources among agents with differing preferences (e.g., dividing an estate or splitting assets in a divorce). Two classic gold standards of fairness are Envy-Freeness (EF), where no agent prefers someone else's bundle over their own, and Proportionality (PROP), where every agent gets at least $1/n$ of the total value.

When resources are indivisible (like a car or a house), achieving perfect deterministic EF or PROP is often mathematically impossible. To fix this, researchers use randomization—for example, flipping a coin to give a car to Agent A or Agent B. Ex-ante (before the coin flip), this is perfectly fair because both have an expected value of 0.5. However, ex-post (after the flip), one agent gets the car and the other gets nothing, which feels inherently unfair.

The Best-of-Both-Worlds (BoBW) framework attempts to bridge this gap by finding a lottery over allocations that is perfectly fair ex-ante, but also guarantees approximate fairness ex-post using relaxations like EFX (envy-free up to the removal of any single good) or EFM (envy-free for mixed divisible and indivisible goods). Prior to this paper, finding such allocations either required solving NP-hard problems or was restricted to purely indivisible goods without considering economic efficiency.

Methods

The paper introduces several novel polynomial-time algorithms tailored to different agent and resource settings:

  • Two-Agent Local Search: For two agents with general additive utilities, the authors introduce a LocalSearch subroutine. It takes an arbitrary allocation and iteratively shifts goods from a higher-value bundle to a lower-value bundle. This reduces the utility gap between bundles while preserving EFX properties, turning a previously known NP-hard existential proof into an efficient algorithm.
  • Minimal Unmatchable Groups: For $n$ agents, the authors model the allocation of indivisible goods as a bipartite matching problem between agents and items. When a perfect matching fails (violating Hall's Marriage Theorem), the algorithm identifies a minimal unmatchable group of agents who are "mostly satisfied" with high-value goods. The algorithm isolates this group, recursively solves the remaining matching problem, and uses a baseline comparison technique to guarantee ex-ante proportionality.
  • Market Clearing & Water-Filling: For mixed goods, the algorithm layers a "water-filling" process on top of indivisible allocations to distribute divisible goods fairly. For the $n$-agent indivisible setting, they integrate a "Match & Freeze" technique with Fisher market equilibrium concepts to ensure the ex-post allocations are not only fair but also fractionally Pareto optimal (fPO).

Datasets

Not discussed in the paper. This is a purely theoretical computer science and microeconomics paper; no empirical datasets or experimental benchmarks were used.

Key Insights and Ideas

  • The Bi-Valued Sweet Spot: While finding EFX allocations for general utilities remains one of the biggest open problems in fair division for $n \ge 4$ agents, restricting agent preferences to bi-valued utilities (where an item is worth either a high value $b$ or a low value $a$) unlocks simultaneous guarantees for ex-ante EF, ex-post EFX, and ex-post economic efficiency (fPO).
  • Decomposition via Matching Failures: The introduction of "minimal unmatchable groups" allows the algorithm to gracefully handle situations where demand outstrips supply for premium goods. By isolating these bottleneck groups, the algorithm ensures that no agent's ex-ante expected utility drops below their fair proportional share.
  • Reducing Mixed to Indivisible: The paper demonstrates that mixed-goods problems can often be simplified by treating the entire pool of divisible goods as a single, highly flexible pseudo-indivisible item, which can then be fractionally adjusted later to eliminate envy.

Key Results

  • Two Agents: Devised the first polynomial-time randomized algorithms achieving (i) ex-ante EF and ex-post EFX for indivisible goods, and (ii) ex-ante EF and ex-post EFM for mixed goods.
  • $n$ Agents with Bi-Valued Utilities:
    • Mixed Goods: Proven existence of a polynomial-time algorithm that is ex-ante proportional (PROP) and ex-post EFM.
  • Indivisible Goods: Proven existence of a polynomial-time algorithm that is ex-ante EF, ex-post EFX, and ex-post fractionally Pareto optimal (fPO).
  • Impossibility Boundary: These results establish a sharp contrast with tri-valued utilities, where prior work proved that combining ex-ante PROP and ex-post EF1 is impossible, highlighting that bi-valued utilities are the frontier for BoBW efficiency.

Limitations and Future Work

  • The Bi-Valued Restriction: The $n$-agent algorithms rely heavily on the assumption of bi-valued utilities. Extending these BoBW results to general additive utilities remains an open and highly challenging problem.
  • Ex-Ante EF vs. PROP for Mixed Goods: For $n$ agents with mixed goods, the paper achieves ex-ante proportionality, but whether an algorithm can achieve the stronger property of ex-ante envy-freeness alongside ex-post EFM remains unknown.
  • Alternative Fairness Metrics: The authors suggest extending the BoBW paradigm in mixed-goods settings to other popular fairness concepts, such as the Maximin Share (MMS) guarantee.

Summary updated

Abstract

We study the problem of fairly allocating either a set of indivisible goods or a set of mixed divisible and indivisible goods (i.e., mixed goods) to agents with additive utilities, taking the best-of-both-worlds perspective of guaranteeing fairness properties both ex ante and ex post. The ex-post fairness notions considered in this paper are relaxations of envy-freeness, specifically, EFX for indivisible-goods allocation, and EFM for mixed-goods allocation. For two agents, we show that there is a polynomial-time randomized algorithm that achieves ex-ante envy-freeness and ex-post EFX / EFM simultaneously. For $n$ agents with bi-valued utilities, we show there exist randomized allocations that are (i) ex-ante proportional and ex-post EFM, and (ii) ex-ante envy-free, ex-post EFX, and ex-post fractionally Pareto optimal.
BibTeX
@misc{bu2024best,
  author = {Xiaolin Bu and Zihao Li and Shengxin Liu and Xinhang Lu and Biaoshuai Tao},
  title = {{Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods}},
  year = {2024},
  eprint = {2410.06877},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.06877},
}
Figure