Tuesday, February 7, 2017. 12:00PM. NSH 3305.

Back to Lunch Schedule

David Kurokawa - Fairness Notions in the Indivisible Good Setting: Comparisons and their Approximations

Fair division of indivisible goods is the study of allocating a set of discrete goods among several interested parties. Often in such settings a desired allocation is hoped to satisfy some notion of fairness. In this talk we investigate several such notions studied in the literature: maximin share guarantee (MMS), pairwise maximin share guarantee (PMMS), and envy-freeness up to any good (EFX).

We begin by first defining MMS and exploring the pros and cons of it as the benchmark for fairness in the setting. We then define PMMS and EFX and demonstrate their potential as answers to these shortcomings of MMS. We further demonstrate a hierarchical nature between these and relevant notions from the literature --- namely envy-freeness (EF) and envy-freeness up to one good (EF1) as well as give approximation existence results. We close by examining the age-old method of drafting (such as in American sports leagues) and show that there exist far fairer approaches to this problem.

This is a joint work with Ariel Procaccia and Junxing Wang.