TY - JOUR
T1 - An improved approximation algorithm for maximin shares
AU - Garg, Jugal
AU - Taki, Setareh
N1 - Funding Information:
We would like to thank anonymous referees for their comments and suggestions that have helped to improve the presentation of the paper. Work on this paper supported by NSF Grant CCF-1942321 (CAREER).
Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2021/11
Y1 - 2021/11
N2 - 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 [Formula presented]-MMS allocation in which each agent receives a bundle worth at least [Formula presented] times her maximin share. More recently, Ghodsi et al. [7] showed the existence of a [Formula presented]-MMS allocation and a PTAS to find a ([Formula presented])-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 [Formula presented]-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 [Formula presented]-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that there always exists a [Formula presented]-MMS allocation, improving the best previous factor. This improves the approximation guarantee, most notably for small n. We note that [Formula presented] was the best factor known for n>4.
AB - 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 [Formula presented]-MMS allocation in which each agent receives a bundle worth at least [Formula presented] times her maximin share. More recently, Ghodsi et al. [7] showed the existence of a [Formula presented]-MMS allocation and a PTAS to find a ([Formula presented])-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 [Formula presented]-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 [Formula presented]-MMS allocation, where we do not need to approximate the MMS values at all. Second, we show that there always exists a [Formula presented]-MMS allocation, improving the best previous factor. This improves the approximation guarantee, most notably for small n. We note that [Formula presented] was the best factor known for n>4.
KW - Fair division
KW - Maximin shares
KW - Strongly polynomial algorithm
UR - http://www.scopus.com/inward/record.url?scp=85107740875&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85107740875&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2021.103547
DO - 10.1016/j.artint.2021.103547
M3 - Article
AN - SCOPUS:85107740875
SN - 0004-3702
VL - 300
JO - Artificial Intelligence
JF - Artificial Intelligence
M1 - 103547
ER -