Fairly allocating indivisible goods to strategic agents

27^th October 2023, 14:00 Ashton Lecture Theatre
Georgios Birmpas

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 a relaxation of envy-freeness, namely envy-freeness up to one good (EF1), and we positively answer the above question. In particular, we study an algorithm that is known to produce such allocations in the non-strategic setting: Round-Robin. We show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while we also prove that surprisingly, a version of this result holds even for agents with cancelable or submodular valuation functions.