Approximate and strategyproof maximin share allocation of chores with ordinal preferences

• 成果类型: Article
• 署名作者: Aziz, Haris; Li, Bo; Wu, Xiaowei
• 署名单位: University of New South Wales Sydney; Hong Kong Polytechnic University; University of Macau
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01855-y
• 发表日期: 2024
• 页码: 319-345
• 关键词: fair division; envy; assignment

摘要

We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The previous best-known approximation ratio using ordinal preferences is 2 - 1/n by Aziz et al. [AAAI 2017]. We improve this result by giving a deterministic 5/3-approximation algorithm that determines an allocation sequence of agents, according to which items are allocated one by one. By a tighter analysis, we show that for n = 2 and 3, our algorithm achieves better approximation ratios, and is actually optimal. We also consider the setting with strategic agents, where agents may misreport their preferences to manipulate the outcome. We first provide a strategyproof O(log(m/n))-approximation consecutive picking algorithm, and then improve the approximation ratio to O(root log n) by a randomized algorithm. Both algorithms only use the ordinal preferences of agents. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods.