Abstract
We study the problem of fairly allocating indivisible goods among $n$ strategic agents. It is well-known that truthfulness is incompatible with any meaningful fairness notions. We bypass the strong negative result by considering the concept of incentive ratio, a relaxation of truthfulness quantifying agents' incentive to misreport. Previous studies show that Round-Robin, which satisfies envy-freeness up to one good (EF1), achieves an incentive ratio of $2$ for additive valuations. In this paper, we explore the incentive ratio achievable by fair mechanisms for various classes of valuations besides additive ones. We first show that, for arbitrary $\epsilon > 0$, every $(\frac{1}{2} + \epsilon)$-EF1 mechanism for additive valuations admits an incentive ratio of at least $1.5$. Then, using the above lower bound for additive valuations in a black-box manner, we show that for arbitrary $\epsilon > 0$, every $\epsilon$-EF1 mechanism for cancelable valuations admits an infinite incentive ratio. Moreover, for subadditive cancelable valuations, we show that Round-Robin, which satisfies EF1, achieves an incentive ratio of $2$, and every $(\phi - 1)$-EF1 mechanism admits an incentive ratio of at least $\phi$ with $\phi = (1 + \sqrt{5}) / 2 \approx 1.618$. Finally, for submodular valuations, we show that Round-Robin, which satisfies $\frac{1}{2}$-EF1, admits an incentive ratio of $n$.
Introduction
In the field of Algorithmic Game Theory, "Fair Division" is a classic problem: how do we divide a set of indivisible items among agents so that everyone feels they received a fair deal? The gold standard for fairness is Envy-Freeness (EF), where no agent prefers another's bundle over their own. However, with indivisible goods, EF often does not exist. Researchers instead utilize Envy-Freeness up to One good (EF1), where any envy can be removed by deleting a single item from the envied agent's bundle.
A major challenge is truthfulness. In most fair mechanisms, agents have an incentive to misreport their valuations to secure better outcomes. Since perfect truthfulness is mathematically incompatible with fairness in this setting, this paper employs the Incentive Ratio: the worst-case ratio of the utility an agent obtains by lying versus reporting truthfully. A ratio of 1 is perfectly truthful, while a ratio of 2 means an agent can at most double their utility by misreporting.
Methodology
The authors establish theoretical upper and lower bounds for the incentive ratio across several valuation classes:
- Additive: The value of a set is the sum of the values of the individual items.
- Submodular/Subadditive: These represent "diminishing returns," where the marginal value of an item decreases as an agent acquires more goods.
- Cancelable: A technical class that generalizes many common economic models, such as budget-additive or unit-demand valuations.
The paper analyzes the Round-Robin mechanism and the Envy-Graph Procedure. They also introduce a "black-box" reduction technique, using lower bounds from simple additive valuations to prove impossibility results for more complex valuation structures.
Key Insights and Results
The paper provides a comprehensive map of the fairness-incentive landscape, identifying fundamental limits to strategic manipulation.
- The 1.5 Barrier: For additive valuations, the authors show that any mechanism providing even slightly more fairness than "half-EF1" must have an incentive ratio of at least 1.5. This establishes a fundamental "cost of lying" inherent in fair systems.
- The Cancelable Impossibility: For general "cancelable" valuations, any mechanism providing even minimal fairness ($\epsilon$-EF1) admits an infinite incentive ratio. In these settings, strategic manipulation can yield unbounded benefits for the agent.
- Subadditivity as a Shield: Interestingly, if the property of "subadditivity" is added to cancelable valuations, the incentive ratio collapses back to a manageable 2 using the Round-Robin mechanism.
- Strategic Failure of Envy-Graph: Despite its popularity for finding EF1 allocations, the authors prove the Envy-Graph Procedure has an infinite incentive ratio even for simple additive valuations, making it unsuitable for strategic environments.
Conclusion
Round-Robin remains a "hero" mechanism in this study, achieving an incentive ratio of 2 for additive and subadditive cancelable valuations. However, for submodular valuations, its performance degrades to an incentive ratio of $n$. Future work remains to close the gap between the 1.5 lower bound and 2 upper bound for additive valuations and to explore whether randomized mechanisms can offer superior incentive guarantees.
Summary updated