LFCS Seminar: Tuesday 25 November: Georgios Birmpas

Title: Fair Division of Indivisible Items under Strategic Agents

Abstract: We consider the problem of fairly allocating a set of indivisible goods
to a set of strategic agents with additive valuation functions and
beyond. 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 study two algorithms that are known to produce such
allocations in the non-strategic setting: Round-Robin and Envy Cycle
Elimination. We show several positive and negative results for both
mechanisms, with some highlights being, the existence of fair pure
Nash equilibria in the case of Round Robin, and fair best responses in
the case of Envy Cycle Elimination.

----------------------------------------------------------------------


If you would like to propose a speaker, or speak yourself, please contact me.
The seminar webpages:
http://web.inf.ed.ac.uk/lfcs/events/lfcs-seminars