Comparison queries enable fair chore division without exact costs
Comparison-Based Fair Division of Indivisible Chores
Computer Science and Game Theory
Summary
This work looks at how to fairly split up chores among people without knowing exact values for how bad each chore is. Instead, the authors use only comparisons, asking who prefers which chore bundle instead of requiring exact numbers. They develop methods that find nearly fair divisions efficiently using these comparison queries. For example, they can ensure everyone feels they have a mostly fair share or is not too envious of others, even with only these comparisons. Their approach matches some of the best-known fairness results that use exact costs.
What this means in practice
- •For task assignment teams: Assign indivisible chores fairly among members using only preference comparisons, reducing the need for exact cost measurements.
- •For workflow automation developers: Implement algorithms that allocate duties fairly with minimal input by querying relative preferences instead of precise costs or durations.
A theory result. No direct application yet.
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.