Fair division of chores using only comparisons achieves strong guarantees
Comparison-Based Fair Division of Indivisible Chores
Computer Science and Game Theory
Summary
Dividing a set of chores fairly among several people is tricky when chores cannot be split and we only know who prefers which chores without exact numbers. This paper looks at how to fairly assign chores when you can only ask which set of chores one finds less costly, but never see exact costs. The researchers created methods to guarantee each person gets a fair share, close to how they would if exact costs were known, using only a small number of such comparison questions. They also show that for three people, it’s possible to avoid envy fairly easily with just a few comparisons.
fair divisionindivisible choresadditive cost functionscomparison queriesproportionality up to one item (PROP1)maximin share (MMS)envy-freeness up to one item (EF1)query complexitycontiguous allocationdistortion
Authors
Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou
Abstract
We investigate the query complexity of fairly allocating $m$ indivisible chores among $n$ agents with additive cost functions. We depart from the standard cardinal model and assume only comparison access: an algorithm may ask an agent which of two bundles is less costly, but never observes numerical costs. Our first results concern proportionality up to one item (PROP1). We design comparison-based algorithms that compute PROP1 allocations using $O(n^3\log m)$ comparison queries. When the chores are arranged in a fixed order and allocations are required to be contiguous, we compute a contiguous PROP1 allocation using $O(n^3 \log^2 m)$ comparison queries. Our main result concerns the maximin share (MMS) guarantee. We show that for any fixed number of agents $n$ and constant $\varepsilon>0$, a $\left(13/11 +\varepsilon\right)$-MMS allocation can be computed with a comparison complexity logarithmic in $m$. Remarkably, comparison access suffices to match the state-of-the-art $13/11$ cardinal-access guarantee of Huang and Segal-Halevi up to an arbitrarily small loss. Furthermore, our result implies that the MMS distortion of comparison access (i.e., the worst-case multiplicative loss in MMS fairness incurred by observing only comparisons rather than numerical costs) is at most $13/11$. Finally, we show that, for three agents, an allocation satisfying envy-freeness up to one item (EF1) can be computed using $O(\log m)$ comparison queries.