TY - GEN
T1 - An Improved Approximation Algorithm for Maximin Shares
AU - Garg, Jugal
AU - Taki, Setareh
N1 - Funding Information:
Work on this paper supported by NSF Grants CCF-1755619 (CRII) and CCF-1942321 (CAREER).
PY - 2020/7/13
Y1 - 2020/7/13
N2 - We study the problem of fair allocation of m indivisible items among n agents with additive valuations using the popular notion of maximin share (MMS) as our measure of fairness. 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 [5, 7], a series of remarkable work [1-3, 6, 7] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times her maximin share. More recently, [4] showed the existence of 3/4 MMS allocations and a PTAS to find a 3/4 - ϵ MMS allocation. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain.
AB - We study the problem of fair allocation of m indivisible items among n agents with additive valuations using the popular notion of maximin share (MMS) as our measure of fairness. 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 [5, 7], a series of remarkable work [1-3, 6, 7] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times her maximin share. More recently, [4] showed the existence of 3/4 MMS allocations and a PTAS to find a 3/4 - ϵ MMS allocation. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain.
KW - fair division
KW - maximin shares
KW - strongly polynomial algorithm
UR - http://www.scopus.com/inward/record.url?scp=85089263674&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089263674&partnerID=8YFLogxK
U2 - 10.1145/3391403.3399526
DO - 10.1145/3391403.3399526
M3 - Conference contribution
AN - SCOPUS:85089263674
T3 - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
SP - 379
EP - 380
BT - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PB - Association for Computing Machinery
T2 - 21st ACM Conference on Economics and Computation, EC 2020
Y2 - 13 July 2020 through 17 July 2020
ER -