URL: https://illinois.zoom.us/j/85236768481?pwd=RndkQzd2Vk5WMDNTdC9MQWZUemVjdz09
Meeting ID: 852 3676 8481
Password: theorycs
The details of the talk are:
Title : Fair Division of Indivisibles: On the Computability of Maximin Share (MMS) Allocations
Abstract: Fair division is a fundamental problem in various multi-agent settings, where the goal is to divide a set of items among agents in a fair manner. We study the case where m indivisible items need to be divided among n agents with additive valuations using the popular fairness notion of maximin share (MMS). Defined by Budish in 2011, Maximin share of an agent is the value she can guarantee herself under the classical cut-and-choose mechanism when she is the cutter. An allocation is called MMS if each agent receives a bundle worth at least her maximin share. While it is known that such an allocation need not exist (Kurokawa et al. (2016)), a series of remarkable work provided approximation algorithms for a 2/3 -MMS allocation in which each agent receives a bundle worth at least 2/3 times her maximin share. Later, Ghodsi et al. (2018) showed the existence of a 3/4 -MMS allocation and a PTAS to find a ( 3/4 −\epsilon)- MMS allocation for an \epsilon > 0. Most of the previous works utilize intricate algorithms and require agents’ approximate MMS values, which are computationally expensive to obtain. In this work, we first propose an alternative 2/3 -MMS allocation which offers both a simple algorithm and straightforward analysis. In contrast to other algorithms, our approach allows for a simple and intuitive understanding of why it works. Then we extend our approach so that it gives a simple algorithm for showing the existence of a 3/4 -MMS allocation. Furthermore, our approach is powerful enough to be easily extended in two directions: First, we get a strongly polynomial time algorithm to find a 3/4 -MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that there always exists a (3/4 + 1/12n)-MMS allocation, improving the best previous factor. This improves the approximation guarantee, most notably for small n. We note that 3/4 was the best factor known for n > 4. Allocating chores, a.k.a. negatively valued items, fairly is as important as allocating goods. Recently, we initiated the study of the MMS problem for mixed manna, where the set of items includes both goods and chores, and additionally an item can be a good for some agents and a chore for others. I will briefly cover our work on mixed manna where in addition to MMS we also ensure Pareto-optimality.
