Approximate and strategyproof maximin share allocation of chores with ordinal preferences

DOI10.1007/S10107-022-01855-YMaRDI QIDQ6120928zbMATH OpenOpenAlexFDO

Authors Haris Aziz, Bo Li, Xiaowei Wu

Publication date 21 February 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.13884

zbMATH Keywords

choresfair allocationmaximin shareordinal preferencesstrategyproofness

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Social choice (91B14) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: 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 is 2-1/n by Aziz et al. [IJCAI 2017]. We improve this result by giving a simple 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,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 O(log (m/n))-approximation consecutive picking algorithm, and then improve the approximation ratio to O(sqrt{log n}) by a randomized algorithm. Our results uncover some interesting contrasts between the approximation ratios achieved for chores versus goods.

Cites work

• A Class of Sequential Games
• An improved approximation algorithm for maximin shares
• Approximation Algorithms for Computing Maximin Share Allocations
• Envy-free cake divisions cannot be found by finite protocols
• Equilibria in sequential allocation
• Fair Allocation of Indivisible Goods
• Fair assignment of indivisible objects under ordinal preferences
• Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
• Fair enough: guaranteeing approximate maximin shares
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 6902543 (Why is no real title available?)
• Manipulating picking sequences
• On Low-Envy Truthful Allocations
• Optimal social choice functions: a utilitarian view
• Subset selection via implicit utilitarian voting
• Truth, justice, and cake cutting
• Truthful Mechanisms for Matching and Clustering in an Ordinal World

Cited in

(3)

• When is truthfully allocating chores no harder than goods?
• Randomized strategyproof mechanisms with best of both worlds fairness and efficiency
• Approximating EFX through a new notion of fairness

This page was built for publication: Approximate and strategyproof maximin share allocation of chores with ordinal preferences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6120928)