Maximin share allocations on cycles

Zbigniew Lonc, Miroslaw Truszczynski

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

Abstract

The problem of fair division of indivisible goods is a fundamental problem of social choice. Recently, the problem was extended 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, allocations offering each agent a bundle of at least her maximin share value always exist. Moreover, they can be found in polynomial time. We consider here 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 results on allocations guaranteeing each agent a certain portion of her maximin share. We also study algorithms for computing maximin share allocations of goods on cycles.

Original languageEnglish
Title of host publicationProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
EditorsJerome Lang
Pages410-416
Number of pages7
ISBN (Electronic)9780999241127
DOIs
StatePublished - 2018
Event27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sweden
Duration: Jul 13 2018Jul 19 2018

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
Volume2018-July
ISSN (Print)1045-0823

Conference

Conference27th International Joint Conference on Artificial Intelligence, IJCAI 2018
Country/TerritorySweden
CityStockholm
Period7/13/187/19/18

Bibliographical note

Funding Information:
The work of the second author was partially supported by the NSF grant IIS-1618783.

Publisher Copyright:
© 2018 International Joint Conferences on Artificial Intelligence. All right reserved.

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