cs.GTSep 17, 2021

Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

Authors: Georgios Amanatidis, Georgios Birmpas, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenhäuser

Organizations: School of Mathematics, Statistics and Actuarial Science, University of Essex, UK. · Archimedes/Athena RC, Greece. · Department of Computer Science, University of Liverpool, UK. · Department of Computer, Control, and Management Engineering, Sapienza University of Rome, Italy. · 

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefore, a mechanism in our setting is an algorithm that takes as input the reported -- rather than the true -- values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely envy-freeness up to one good (EF1), and envy-freeness up to any good (EFX), and we positively answer the above question. In particular, we study two algorithms that are known to produce such allocations in the non-strategic setting: Round-Robin (EF1 allocations for any number of agents) and a cut-and-choose algorithm of Plaut and Roughgarden [SIAM Journal of Discrete Mathematics, 2020] (EFX allocations for two agents). For Round-Robin we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while for the algorithm of Plaut and Roughgarden we show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria which all induce EFX allocations.

Figures & tables

Figure 1: Each row is a visual abstraction of the preference ranking of the corresponding auxiliary bid during the transformation we perform for round rr . Note that for r=kr=k , or an arbitrary r<kr<k that falls under Case 1, only the first two rows are relevant. The purple blocks represent the goods which are more valuable than λr\lambda_{r} but come after it in ≻1\succ_{1} , i.e., they are all unavailable at the beginning of round rr . Moving those up to the left of hnrh_{n_{r}} corresponds to constructing bˉˉ1r\bar{\bar{\bm{b}}}^{r}_{1} (or bˉ1r{\bar{\bm{b}}}^{r}_{1} for round kk ). Then, we replace the bids with the corresponding v1r+1v^{r+1}_{1} values for all goods on the green part and scale the bids of the goods in the orange part to keep the ordering consistent. For r=kr=k or in Case 1 for r<kr<k , we already obtain b1r{\bm{b}}^{r}_{1} this way and we are done for the round. In Case 2, however, there still are goods on the right of hnrh_{n_{r}} that are better (at least one, as λr≠hnr\lambda_{r}\neq h_{n_{r}} in this case), yet we want to keep hnrh_{n_{r}} in place. This temporary inconsistency is represented by bˉ1r{\bar{\bm{b}}}^{r}_{1} in Case 2. In order to fix that and move to b1r{\bm{b}}^{r}_{1} , we transfer enough value from hnr+1,hnr+2,…,hnkh_{n_{r+1}},h_{n_{r+2}},\ldots,h_{n_{k}} to hnrh_{n_{r}} , without compromising their position in the ordering; Claim 3.9 guarantees that the latter is always possible in this case.
More in this topic

Fair Resource Allocation

Fair resource allocation studies how to distribute scarce goods, services, and computing capacity equitably while accounting for efficiency and constraints.

See all 56 papers

Explore similar work

CardsList

  1. Simultaneous Envy and Equitability Guarantees

    Aug 26, 2026Hadi Hosseini, Shraddha Pathak, Lirong Xia +1Social Choice TheoryFair Resource Allocation

    Penn State University · Rutgers University

  2. Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO

    Jul 25, 2026Nicholas TehSocial Choice TheoryFair Resource Allocation

    University of Oxford, UK

  3. EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments

    Sep 3, 2026Zih-Sian Yang, Yi-Hao Chen, Yu-Te Kuan +3Fair Resource AllocationOnline Resource Allocation

    National Taiwan Ocean University, Keelung City 202301, Taiwan · National Yang Ming Chiao Tung University, Hsinchu City 300, Taiwan