TY - GEN
T1 - Logarithmic Comparison-Based Query Complexity for Fair Division of Indivisible Goods
AU - Bu, Xiaolin
AU - Li, Zihao
AU - Liu, Shengxin
AU - Song, Jiaxin
AU - Tao, Biaoshuai
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.
PY - 2026
Y1 - 2026
N2 - We study the problem of fairly allocating m indivisible goods to n agents, where agents may have different preferences over the goods. In the traditional setting, agents’ valuations are provided as inputs to the algorithm. In this paper, we adopt the query model, which has been widely considered for other similar problems (such as matching [28], graph isomorphism [30], and equilibrium in game [7]), to our fair division problem. In particular, we consider a new comparison-based query model where the algorithm presents two bundles of goods to an agent and the agent responds by telling the algorithm which bundle she prefers. We investigate the query complexity for computing allocations with several fairness notions including proportionality up to one good (PROP1), envy-freeness up to one good (EF1), and maximin share (MMS). Our main result is an algorithm that computes an allocation that satisfies both PROP1 and 12-MMS within O(logm) queries with a constant number of n agents. For identical and additive valuation, we present an algorithm for computing an EF1 allocation within O(logm) queries with a constant number of n agents. To complement the positive results, we show that the lower bound of the query complexity for any of the three fairness notions is Ω(logm) even with two agents.
AB - We study the problem of fairly allocating m indivisible goods to n agents, where agents may have different preferences over the goods. In the traditional setting, agents’ valuations are provided as inputs to the algorithm. In this paper, we adopt the query model, which has been widely considered for other similar problems (such as matching [28], graph isomorphism [30], and equilibrium in game [7]), to our fair division problem. In particular, we consider a new comparison-based query model where the algorithm presents two bundles of goods to an agent and the agent responds by telling the algorithm which bundle she prefers. We investigate the query complexity for computing allocations with several fairness notions including proportionality up to one good (PROP1), envy-freeness up to one good (EF1), and maximin share (MMS). Our main result is an algorithm that computes an allocation that satisfies both PROP1 and 12-MMS within O(logm) queries with a constant number of n agents. For identical and additive valuation, we present an algorithm for computing an EF1 allocation within O(logm) queries with a constant number of n agents. To complement the positive results, we show that the lower bound of the query complexity for any of the three fairness notions is Ω(logm) even with two agents.
KW - Comparison-based Query
KW - Fair Division
KW - Indivisible Goods
UR - https://www.scopus.com/pages/publications/105027120790
U2 - 10.1007/978-3-032-08560-3_20
DO - 10.1007/978-3-032-08560-3_20
M3 - 会议稿件
AN - SCOPUS:105027120790
SN - 9783032085597
T3 - Lecture Notes in Computer Science
SP - 348
EP - 365
BT - Web and Internet Economics - 20th International Conference, WINE 2024, Proceedings
A2 - Mavronicolas, Marios
A2 - Qi, Qi
A2 - Schoenebeck, Grant
PB - Springer Science and Business Media Deutschland GmbH
T2 - 20th International Conference on Web and Internet Economics, WINE 2024
Y2 - 2 December 2024 through 5 December 2024
ER -