Incentive Ratios for Fairly Allocating Indivisible Goods: Simple Mechanisms Prevail

Biaoshuai Tao, Mingwei YangarXiv 2023 · arXiv · OpenReview

Abstract

We study the problem of fairly allocating indivisible goods among strategic agents. Amanatidis et al. show that truthfulness is incompatible with any meaningful fairness notions. Thus we adopt the notion of incentive ratio, which is defined as the ratio between the largest possible utility that an agent can gain by manipulation and his utility in honest behavior under a given mechanism. We select four of the most fundamental mechanisms in the literature on discrete fair division, which are Round-Robin, a cut-and-choose mechanism of Plaut and Roughgarden, Maximum-Nash-Welfare and Envy-Graph Procedure, and obtain extensive results regarding the incentive ratios of them and their variants. For Round-Robin, we establish the incentive ratio of $2$ for additive and subadditive cancelable valuations, the unbounded incentive ratio for cancelable valuations, and the incentive ratios of $n$ and $\lceil m / n \rceil$ for submodular and XOS valuations, respectively. Moreover, the incentive ratio is unbounded for a variant that provides the $1/n$-approximate maximum social welfare guarantee. For the algorithm of Plaut and Roughgarden, the incentive ratio is either unbounded or $3$ with lexicographic tie-breaking and is $2$ with welfare maximizing tie-breaking. This separation exhibits the essential role of tie-breaking rules in the design of mechanisms with low incentive ratios. For Maximum-Nash-Welfare, the incentive ratio is unbounded. Furthermore, the unboundedness can be bypassed by restricting agents to have a strictly positive value for each good. For Envy-Graph Procedure, both of the two possible ways of implementation lead to an unbounded incentive ratio. Finally, we complement our results with a proof that the incentive ratio of every mechanism satisfying envy-freeness up to one good is at least $1.074$, and thus is larger than $1$ by a constant.

Introduction

This research addresses the fundamental tension between fairness and truthfulness in the allocation of indivisible goods. In fair division problems—such as dividing an inheritance or assigning tasks—the goal is typically to achieve fairness (ensuring no agent envies another) and truthfulness (ensuring no agent has an incentive to misreport their preferences). However, for indivisible items, it is mathematically impossible to guarantee both simultaneously.

To navigate this impossibility, researchers relax these requirements. Instead of perfect envy-freeness, they target EF1 (envy-freeness up to one good), where envy can be eliminated by removing a single item from another agent's bundle. Instead of perfect truthfulness, they analyze the incentive ratio: the factor by which an agent can increase their utility through strategic manipulation. For instance, an incentive ratio of 2 implies a liar can at most double their utility compared to reporting truthfully. This paper establishes achievable incentive ratios for valuation classes beyond simple additive models, including submodular and cancelable valuations.

Methodology

The study employs theoretical proofs and "hard instance" constructions to determine upper and lower bounds for incentive ratios across several mechanisms:

  • Lower Bound Constructions: The authors design specific valuation profiles where any mechanism meeting a certain fairness threshold (e.g., EF1) must inevitably yield a high incentive ratio.
  • Mechanism Analysis: The research evaluates the Round-Robin mechanism—where agents take turns selecting items—and its variants. It also examines the Maximum-Nash-Welfare (MNW), the Envy-Graph Procedure, and the Plaut-Roughgarden cut-and-choose algorithm.
  • Black-Box Reductions: Lower bounds from simpler additive valuation classes are used to derive impossibility results for more complex classes, such as cancelable valuations.

Key Insights

The Cost of Fairness

For additive valuations, the authors demonstrate that even a minimal fairness requirement, such as $\frac{1}{2}$-EF1, necessitates an incentive ratio of at least 1.5. This indicates that a fair mechanism cannot be "almost" perfectly truthful.

The "Cancelable" Trap

Cancelable valuations, which encompass common types like budget-additive or unit-demand preferences, present significant challenges. The authors prove that any fair mechanism for this class results in an infinite incentive ratio, meaning agents can potentially gain unlimited utility by misreporting.

Subadditivity as a Mitigant

Interestingly, when the property of subadditivity (where the value of a bundle is less than or equal to the sum of its parts) is added to cancelable valuations, the incentive ratio for the Round-Robin mechanism drops to a manageable 2.

Robustness of Simple Mechanisms

Despite its simplicity, Round-Robin remains one of the most robust mechanisms. It provides bounded incentive ratios in scenarios where more complex procedures, like the Envy-Graph method, fail and result in infinite ratios.

Results

The paper provides a comprehensive mapping of the incentive ratio landscape across different valuation classes and fairness levels.

Summary of incentive ratios and fairness levels across different valuation classes.

Key theoretical milestones include:

  • Theorem 3.1: Establishing the 1.5 lower bound for additive valuations.
  • Theorem 4.1: Proving the impossibility result (infinite ratio) for general cancelable valuations.
  • Theorem 6.1: Demonstrating that for submodular valuations, a generalized Round-Robin achieves an incentive ratio of $n$ (the number of agents).

Discussion and Future Work

While this work significantly clarifies the bounds of strategic manipulation in fair division, several avenues for future research remain. There are still gaps between lower and upper bounds, particularly the [1.5, 2] range for additive valuations. Additionally, the authors suggest exploring XOS (fractionally subadditive) valuations and the potential for randomized mechanisms to provide better incentive guarantees.

Finally, while theoretical incentive ratios can be high, the authors note that calculating the optimal "lie" is often computationally hard (NP-hard). This suggests that the practical risk of manipulation may be lower than the theoretical maximums imply.

Summary updated

Abstract

We study the problem of fairly allocating indivisible goods among strategic agents. Amanatidis et al. show that truthfulness is incompatible with any meaningful fairness notions. Thus we adopt the notion of incentive ratio, which is defined as the ratio between the largest possible utility that an agent can gain by manipulation and his utility in honest behavior under a given mechanism. We select four of the most fundamental mechanisms in the literature on discrete fair division, which are Round-Robin, a cut-and-choose mechanism of Plaut and Roughgarden, Maximum-Nash-Welfare and Envy-Graph Procedure, and obtain extensive results regarding the incentive ratios of them and their variants. For Round-Robin, we establish the incentive ratio of $2$ for additive and subadditive cancelable valuations, the unbounded incentive ratio for cancelable valuations, and the incentive ratios of $n$ and $\lceil m / n \rceil$ for submodular and XOS valuations, respectively. Moreover, the incentive ratio is unbounded for a variant that provides the $1/n$-approximate maximum social welfare guarantee. For the algorithm of Plaut and Roughgarden, the incentive ratio is either unbounded or $3$ with lexicographic tie-breaking and is $2$ with welfare maximizing tie-breaking. This separation exhibits the essential role of tie-breaking rules in the design of mechanisms with low incentive ratios. For Maximum-Nash-Welfare, the incentive ratio is unbounded. Furthermore, the unboundedness can be bypassed by restricting agents to have a strictly positive value for each good. For Envy-Graph Procedure, both of the two possible ways of implementation lead to an unbounded incentive ratio. Finally, we complement our results with a proof that the incentive ratio of every mechanism satisfying envy-freeness up to one good is at least $1.074$, and thus is larger than $1$ by a constant.
BibTeX
@misc{tao2023incentive,
  author = {Biaoshuai Tao and Mingwei Yang},
  title = {{Incentive Ratios for Fairly Allocating Indivisible Goods: Simple Mechanisms Prevail}},
  year = {2023},
  eprint = {2306.15920},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.15920},
}
Figure