Fair item allocation method works for two types of chores and goods
Maximin share allocations for two types of items
Computer Science and Game Theory
Summary
Dividing items fairly among people is hard, especially when items can't be split and are disliked chores. The authors show that if items are split into two groups of chores, there is always a fair way to allocate them, based on a fairness idea called maximin share, and it can be found quickly using a new geometric method. They also explain how this method works if the items are two types of desirable goods or a mix of one good type and one chore type.
What this means in practice
- •For resource managers: Allocate undesirable tasks fairly among workers when tasks fall into two distinct categories using a computable maximin share method.
- •For logistics planners: Divide two types of delivery items or responsibilities fairly and efficiently among teams using the geometric allocation technique.
Authors
Yu Chen, Kai Jie Wong, Xiaorui Zhang
Abstract
We study the fair allocation of indivisible items among $n$ agents with additive valuations (or costs) using the fairness notion of maximin share (MMS). Since MMS allocations do not always exist when $n > 2$, one direction in the literature has been to identify special classes of instances in which exact MMS allocations can be guaranteed. We show that, when items can be divided into two types of chores, MMS allocations always exist and can be computed in polynomial time using a novel geometric approach inspired by prior work in job scheduling. We further discuss how our technique extends to instances with two types of goods, as well as mixed instances consisting of one type of objective good and one type of objective chore.