Maximin share allocations on cycles

Zbigniew Lonc, Miroslaw Truszczynski

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

The problem of fair division of indivisible goods is a fundamental problem of resource allocation in multi-agent systems, also studied extensively in social choice. Recently, the problem was generalized to the case when goods form a graph and the goal is to allocate goods to agents so that each agent's bundle forms a connected subgraph. For the maximin share fairness criterion, researchers proved that if goods form a tree, an allocation offering each agent a bundle of at least her maximin share value always exists. Moreover, it can be found in polynomial time. In this paper we consider the problem of maximin share allocations of goods on a cycle. Despite the simplicity of the graph, the problem turns out to be significantly harder than its tree version. We present cases when maximin share allocations of goods on cycles exist and provide in this case results on allocations guaranteeing each agent a certain fraction of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.

Original languageEnglish
Pages (from-to)613-655
Number of pages43
JournalJournal of Artificial Intelligence Research
Volume69
DOIs
StatePublished - Oct 2020

Bibliographical note

Funding Information:
A preliminary version of the paper appeared in the proceedings of IJCAI 2018. second author was partially supported by the NSF grant IIS-1618783.

Publisher Copyright:
© 2020 AI Access Foundation.

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Maximin share allocations on cycles'. Together they form a unique fingerprint.

Cite this