Maximin Share Allocations on Cycles

Maximin Share Allocations on Cycles

Zbigniew Lonc, Miroslaw Truszczynski

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 410-416. https://doi.org/10.24963/ijcai.2018/57

The problem of fair division of indivisible goods is a fundamental problem of social choice. Recently, the problem was extended to the setting when goods form a graph and the goal is to allocate goods to agents so that each agent's bundle forms a connected subgraph. Researchers proved that, unlike in the original problem (which corresponds to the case of the complete graph in the extended setting), in the case of the goods-graph being a tree, allocations offering each agent a bundle of or exceeding 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 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.
Keywords:
Knowledge Representation and Reasoning: Preference Modelling and Preference-Based Reasoning
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Resource Allocation