将不可分割物品分配给策略性智能体：纯 Nash 均衡与公平性

View PDF HTML (experimental)

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.

Comments:	The claim that every pure Nash equilibrium of Round-Robin is EF1 (Theorem 3.3 here; Theorem 3 in the conference version and Theorem 4 in the journal version) is incorrect; the gap is in the proof of Lemma 3.5 (inequality (2)). A counterexample and corrected guarantees are given in arXiv:2610.23686. The remaining results are not affected
Subjects:	Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM)
Cite as:	arXiv:2109.08644 [cs.GT]
	(or arXiv:2109.08644v3 [cs.GT] for this version)
	https://doi.org/10.48550/arXiv.2109.08644 arXiv-issued DOI via DataCite
Related DOI:	https://doi.org/10.1287/moor.2022.0058 DOI(s) linking to related resources

Submission history

From: Georgios Amanatidis [view email]
[v1] Fri, 17 Sep 2021 16:57:20 UTC (37 KB)
[v2] Mon, 11 Dec 2023 16:33:10 UTC (99 KB)
[v3] Wed, 21 Oct 2026 10:44:03 UTC (95 KB)