Logarithmic queries enable fair item division for any fixed number of agents
Logarithmic Comparison-Query Complexity for EF1 Allocations
Computer Science and Game Theory
Summary
The paper looks at how to fairly divide a number of items among multiple people so that no one feels strongly unfairly treated, as long as you can ignore the value of a single item. The authors show that for any fixed number of people, it’s possible to find such a fair division using only a small number of simple comparison questions about preferences, even without knowing exact values. This improves on earlier work that only handled up to three people efficiently. Their methods work whether the items are considered good or bad, like chores.
What this means in practice
- •For resource allocation engineers: Design algorithms that fairly split resources among fixed groups using minimal preference queries, improving efficiency without detailed valuations.
- •For multiagent system developers: Implement fair division protocols in automated systems with limited preference information, supporting both positive and negative item allocations.
A theory result. No direct application yet.
Authors
Zehan Lin, Shengxin Liu, Biaoshuai Tao, Shengwei Zhou
Abstract
We study the comparison-query complexity of computing allocations that are envy-free up to one item (EF1) for $n$ agents with heterogeneous additive preferences over $m$ indivisible items. In this model, the algorithm may only query which of two bundles an agent prefers, without ever observing numerical valuations or costs. Prior work established $O(\log m)$ query bounds for at most three agents, leaving open whether query complexity logarithmic in $m$ is achievable for every fixed $n \ge 4$. We resolve this open question in the affirmative: for every fixed $n\ge2$, we design algorithms that compute EF1 allocations using $O(\log m)$ comparison queries, matching the known $Ω(\log m)$ lower bound. Our results hold for both chores with nonnegative costs and goods with nonnegative valuations.