Maximin Share Allocations and Other Solution Concepts in Fair Division

We study fair division problems, where a set of resources needs to be allocated to a set of agents in some fair manner. The first part of the talk will give an overview of some solution concepts that are used in fair division, along with existing results (in particular, we will mainly discuss the notions of proportionality, envy-freeness, maximin fair shares, and competitive equilibrium from equal incomes). In the second part of the talk, we will focus on the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of n agents, the maximin share of a single agent is the best that he can guarantee to himself, if he partitions the goods into n bundles and then let other agents choose a bundle before him (i.e., running a generalization of the cut-and-choose protocol). The objective then is to find a partition, so that each player is guaranteed his maximin share. In the presence of indivisible goods, such allocations are not guaranteed to exist, hence, we resort to approximation algorithms. I will present a 2/3-approximation algorithm, which runs in polynomial time for any number of agents and goods, improving upon previous results in the literature. We will also investigate some special cases where we can provide better guarantees. Finally, I will conclude the talk with some more open problems on fair division with either divisible or
indivisible items.

Parts of this talk are based on joint work with Georgios Amanatidis, Afshin Nikzad, and Amin Saberi.