Approximating maximin share allocations

Jugal Garg, Peter McGlaughlin, 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 using the popular notion of maximin share as our measure of fairness. The maximin share of an agent is the largest value she can guarantee herself if she is allowed to choose a partition of the items into N bundles (one for each agent), on the condition that she receives her least preferred bundle. A maximin share allocation provides each agent a bundle worth at least their maximin share. While it is known that such an allocation need not exist [9, 7], a series of work [9, 8, 1, 2] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times their maximin share. Recently, [6] improved the approximation guarantee to 3/4. Prior works utilize intricate algorithms, with an exception of [2] which is a simple greedy solution but relies on sophisticated analysis techniques. In this paper, we propose an alternative 2/3 maximin share approximation which offers both a simple algorithm and straightforward analysis. In contrast to other algorithms, our approach allows for a simple and intuitive understanding of why it works.

Original languageEnglish (US)
Title of host publication2nd Symposium on Simplicity in Algorithms, SOSA 2019 - Co-located with the 30th ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
EditorsJeremy T. Fineman, Michael Mitzenmacher
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770996
DOIs
StatePublished - Jan 2019
Event2nd Symposium on Simplicity in Algorithms, SOSA 2019 - San Diego, United States
Duration: Jan 8 2019Jan 9 2019

Publication series

NameOpenAccess Series in Informatics
Volume69
ISSN (Print)2190-6807

Conference

Conference2nd Symposium on Simplicity in Algorithms, SOSA 2019
CountryUnited States
CitySan Diego
Period1/8/191/9/19

Keywords

  • Approximation algorithm
  • Fair division
  • Maximin share

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Modeling and Simulation

Fingerprint Dive into the research topics of 'Approximating maximin share allocations'. Together they form a unique fingerprint.

Cite this