Group fairness for the allocation of indivisible goods

Conference Paper

We consider the problem of fairly dividing a collection of indivisible goods among a set of players. Much of the existing literature on fair division focuses on notions of individual fairness. For instance, envy-freeness requires that no player prefer the set of goods allocated to another player to her own allocation. We observe that an algorithm satisfying such individual fairness notions can still treat groups of players unfairly, with one group desiring the goods allocated to another. Our main contribution is a notion of group fairness, which implies most existing notions of individual fairness. Group fairness (like individual fairness) cannot be satisfied exactly with indivisible goods. Thus, we introduce two “up to one good” style relaxations. We show that, somewhat surprisingly, certain local optima of the Nash welfare function satisfy both relaxations and can be computed in pseudo-polynomial time by local search. Our experiments reveal faster computation and stronger fairness guarantees in practice.

Duke Authors

Cited Authors

  • Conitzer, V; Freeman, R; Shah, N; Vaughan, JW

Published Date

  • January 1, 2019

Published In

  • 33rd Aaai Conference on Artificial Intelligence, Aaai 2019, 31st Innovative Applications of Artificial Intelligence Conference, Iaai 2019 and the 9th Aaai Symposium on Educational Advances in Artificial Intelligence, Eaai 2019

Start / End Page

  • 1853 - 1860

International Standard Book Number 13 (ISBN-13)

  • 9781577358091

Citation Source

  • Scopus