Approximation Guarantees for Fairness Notions under Indivisible Resources

9^th November 2020, 11:00 Microsoft Teams
Dr. Vangelis Markakis
Department of Informatics, Athens University of Economics and Business

Abstract

We consider fair division problems where a set of resources needs to be allocated to a set of agents. Within the last decade, several fairness criteria have been introduced, that are tailored to settings with indivisible goods. However, due to the lack of general existence results for most of these concepts, great attention has been paid to establishing approximation guarantees.

The talk will begin with an overview of such fairness notions. Out of these, we will first focus on the EFX criterion (envy-freeness up to any item) and propose a simple algorithm that achieves a 0.618-approximation (i.e., equal to \phi-1, with \phi being the golden ratio). This improves upon the previously known ½-approximation algorithms. We then exhibit that our algorithm is “universally” fair in the sense that it returns allocations that have good guarantees with respect to other notions as well. In particular, the same algorithm achieves at the same time a better than ½-approximation for the criteria of GMMS and PMMS (groupwise and pairwise maximin share fairness) and also satisfies EF1 (envy-freeness up to one item). Finally, we will elaborate on further connections between these fairness notions, and conclude with open problems that stem from this line of research.