An Improved Approximation Algorithm for Maximin Shares

Jugal Garg, Setareh Taki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery
Pages379-380
Number of pages2
ISBN (Electronic)9781450379755
DOIs
StatePublished - Jul 13 2020
Event21st ACM Conference on Economics and Computation, EC 2020 - Virtual, Online, Hungary
Duration: Jul 13 2020Jul 17 2020

Publication series

NameEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation

Conference

Conference21st ACM Conference on Economics and Computation, EC 2020
Country/TerritoryHungary
CityVirtual, Online
Period7/13/207/17/20

Keywords

  • fair division
  • maximin shares
  • strongly polynomial algorithm

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Economics and Econometrics
  • Statistics and Probability
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'An Improved Approximation Algorithm for Maximin Shares'. Together they form a unique fingerprint.

Cite this