When Can the Maximin Share Guarantee Be Guaranteed?

David Kurokawa, Ariel D. Procaccia, Junxing Wang

AAAI 2016 pp. 523-529

doi:10.1609/AAAI.V30I1.10041 /aaai/2016/kurokawa2016aaai-maximin/

Abstract

The fairness notion of maximin share (MMS) guarantee underlies a deployed algorithm for allocating indivisible goods under additive valuations. Our goal is to understand when we can expect to be able to give each player his MMS guarantee. Previous work has shown that such an MMS allocation may not exist, but the counterexample requires a number of goods that is exponential in the number of players; we give a new construction that uses only a linear number of goods. On the positive side, we formalize the intuition that these counterexamples are very delicate by designing an algorithm that provably finds an MMS allocation with high probability when valuations are drawn at random.

PDF AAAI Semantic Scholar

Cite

Text

Kurokawa et al. "When Can the Maximin Share Guarantee Be Guaranteed?." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10041

Markdown

[Kurokawa et al. "When Can the Maximin Share Guarantee Be Guaranteed?." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/kurokawa2016aaai-maximin/) doi:10.1609/AAAI.V30I1.10041

BibTeX

@inproceedings{kurokawa2016aaai-maximin,
  title     = {{When Can the Maximin Share Guarantee Be Guaranteed?}},
  author    = {Kurokawa, David and Procaccia, Ariel D. and Wang, Junxing},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {523-529},
  doi       = {10.1609/AAAI.V30I1.10041},
  url       = {https://mlanthology.org/aaai/2016/kurokawa2016aaai-maximin/}
}