An improved approximation algorithm for maximin shares

Fair division is a fundamental problem in various multi-agent settings, where the goal is to divide a set of resources 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). An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist [1, 2], a series of remarkable work [1, 3–6] 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. More recently, Ghodsi et al. [7] showed the existence of a 3 4 -MMS allocation and a PTAS to find a ( 3 4 − ϵ )-MMS allocation for an ϵ > 0. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain. In this paper, we develop a new approach that 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 12 n ) -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.

Authors

• Jugal Garg University of Illinois at Urbana-Champaign
• Setareh Taki

Keywords

• Fair division
• Maximin shares
• Strongly polynomial algorithm