1 Search Results for "Taki, Setareh"

Document

DOI: 10.4230/OASIcs.SOSA.2019.20

Approximating Maximin Share Allocations

Authors: Jugal Garg, Peter McGlaughlin, and Setareh Taki

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

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 [Procaccia and Wang, 2014; Kurokawa et al., 2016], a series of work [Procaccia and Wang, 2014; David Kurokawa et al., 2018; Amanatidis et al., 2017; Barman and Krishna Murthy, 2017] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times their maximin share. Recently, [Ghodsi et al., 2018] improved the approximation guarantee to 3/4. Prior works utilize intricate algorithms, with an exception of [Barman and Krishna Murthy, 2017] 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.

Cite as

Jugal Garg, Peter McGlaughlin, and Setareh Taki. Approximating Maximin Share Allocations. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 20:1-20:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:OASIcs.SOSA.2019.20,
  author =	{Garg, Jugal and McGlaughlin, Peter and Taki, Setareh},
  title =	{{Approximating Maximin Share Allocations}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{20:1--20:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.20},
  URN =		{urn:nbn:de:0030-drops-100465},
  doi =		{10.4230/OASIcs.SOSA.2019.20},
  annote =	{Keywords: Fair division, Maximin share, Approximation algorithm}
}

Refine by Author
1 Garg, Jugal
1 McGlaughlin, Peter
1 Taki, Setareh

Refine by Classification

Refine by Keyword
1 Approximation algorithm
1 Fair division
1 Maximin share

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Taki, Setareh"

Approximating Maximin Share Allocations

Abstract

Cite as

Thanks for your feedback!

Could not send message