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 - 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 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/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. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

This paper investigates fair division in the case of indivisible items with additive valuations, focusing on the concept of maximin share (MMS). It presents a simple algorithm for the existence of a 3/4-MMS allocation and shows that there is always a (3/4 + 1/12n)-MMS allocation, improving previous factors. The approach introduced in the paper can be easily extended to a strongly polynomial time algorithm and better approximation guarantees.