Fair and Truthful Mechanisms for Dichotomous Valuations

Moshe Babaioff, Tomer Ezra, Uriel FeigeAAAI 2021 · DOI

The allocation of indivisible goods—such as tasks, shifts, or shared resources—presents a fundamental challenge in algorithmic game theory when monetary transfers are prohibited. In these "no-money" settings, designers face a persistent trilemma: how to simultaneously ensure Truthfulness (incentivizing honest reporting), Efficiency (maximizing total welfare), and Fairness (ensuring equitable distribution).

This paper addresses this challenge by focusing on submodular dichotomous valuations. In this setting, an agent's marginal value for any additional item is either 0 or 1, and their preferences exhibit diminishing returns. The authors demonstrate that for this specific class of valuations, it is indeed possible to satisfy all three goals through a novel mechanism: the Prioritized Egalitarian (PE) mechanism.

The Valuation Model: Matroids and Dichotomy

A critical insight of this work is the mathematical equivalence between submodular dichotomous valuations and Matroid Rank Functions (MRFs). This connection allows the authors to leverage the robust structural properties of matroids. In practical terms, these valuations represent scenarios where items are substitutable to a degree—for example, a worker who needs any two shifts but finds a third redundant. This mathematical grounding is what allows the mechanism to guarantee both efficiency and fairness.

The Prioritized Egalitarian (PE) Mechanism

The PE mechanism operates by seeking an allocation that is Lorenz dominating. Lorenz domination is a stringent fairness criterion; a Lorenz-dominating allocation is one where the vector of utilities (sorted from smallest to largest) is lexicographically largest. Essentially, it prioritizes the "poorest" agents first, then the second poorest, and so on, making the distribution as equal as possible.

Because multiple allocations might be Lorenz-dominating, the PE mechanism uses a fixed priority order (a "queue") of agents to break ties. The authors prove that this specific combination—Lorenz domination followed by priority tie-breaking—results in a mechanism that is both truthful and welfare-maximizing.

Key Theoretical Results

The paper establishes several landmark results for the PE mechanism:

  • Deterministic Truthfulness: PE is the first deterministic mechanism for MRF valuations that is simultaneously truthful, welfare-maximizing, and satisfies EFX (Envy-Free up to any item).
  • Social Welfare: The mechanism maximizes Nash Social Welfare (the product of agents' utilities), a common proxy for balancing efficiency and fairness.
  • Maximin Share: For additive dichotomous valuations, the mechanism guarantees every player at least their maximin share (MMS), ensuring a baseline level of fairness.
  • Computational Feasibility: The authors show that the PE mechanism can be implemented in polynomial time, provided the agents' preferences are represented succinctly.

Randomization and Ex-Ante Fairness

To address potential inequities inherent in a fixed priority order, the authors introduce the Random Priority Egalitarian (RPE) mechanism. By selecting the priority order uniformly at random, RPE achieves "best-of-both-worlds" fairness. It is universally truthful (truthful regardless of the random draw) and provides fairness guarantees both before the allocation (ex-ante) and after the items are distributed (ex-post).

The Limits of Mechanism Design: The XOS Boundary

A significant contribution of the paper is identifying the "frontier" of what is possible. While the PE mechanism succeeds for submodular valuations, the authors prove an impossibility result for the slightly broader class of XOS valuations. They demonstrate that for XOS dichotomous valuations, no randomized mechanism can be both truthful-in-expectation and welfare-maximizing. This establishes a sharp boundary for the feasibility of ideal mechanisms in fair division.

Conclusion and Future Directions

The PE and RPE mechanisms represent a significant step forward in the study of fair allocation without money. By bridging matroid theory and mechanism design, the authors provide a practical and theoretically sound solution for submodular dichotomous preferences.

However, the authors note that the results rely heavily on the dichotomous (0/1) assumption. Future research may look toward relaxing this assumption or exploring mechanisms that achieve approximate welfare maximization for XOS valuations. Additionally, the challenge of maintaining truthfulness when all items (including those with zero value) must be allocated remains an open problem.

Summary updated

BibTeX
@inproceedings{babaioff2021fair,
  author = {Moshe Babaioff and Tomer Ezra and Uriel Feige},
  title = {{Fair and Truthful Mechanisms for Dichotomous Valuations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16647},
}
Figure