Residential Collegefalse
Status已發表Published
Approximate and strategyproof maximin share allocation of chores with ordinal preferences
Aziz Haris1; Li Bo2; Wu Xiaowei3
2022-07-05
Source PublicationMATHEMATICAL PROGRAMMING
ABS Journal Level4
ISSN0025-5610
Volume203Issue:1-2Pages:319-345
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 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(√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.

KeywordFair Allocation Maximin Share Chores Ordinal Preferences Strategyproofness
DOI10.1007/s10107-022-01855-y
URLView the original
Indexed BySCIE
Language英語English
WOS Research AreaComputer Science ; Operations Research & Management Science ; Mathematics
WOS SubjectComputer Science, Software Engineering ; Operations Research & Management Science ; Mathematics, Applied
WOS IDWOS:000821972700001
PublisherSPRINGER HEIDELBERG, TIERGARTENSTRASSE 17, D-69121 HEIDELBERG, GERMANY
Scopus ID2-s2.0-85133427924
Fulltext Access
Citation statistics
Document TypeJournal article
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Corresponding AuthorAziz Haris; Li Bo; Wu Xiaowei
Affiliation1.School of Computer Science and Engineering, UNSW, Sydney, Australia
2.Department of Computing, The Hong Kong Polytechnic University, Hong Kong, China
3.IOTSC, University of Macau, Macau, China
Corresponding Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Aziz Haris,Li Bo,Wu Xiaowei. Approximate and strategyproof maximin share allocation of chores with ordinal preferences[J]. MATHEMATICAL PROGRAMMING, 2022, 203(1-2), 319-345.
APA Aziz Haris., Li Bo., & Wu Xiaowei (2022). Approximate and strategyproof maximin share allocation of chores with ordinal preferences. MATHEMATICAL PROGRAMMING, 203(1-2), 319-345.
MLA Aziz Haris,et al."Approximate and strategyproof maximin share allocation of chores with ordinal preferences".MATHEMATICAL PROGRAMMING 203.1-2(2022):319-345.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Aziz Haris]'s Articles
[Li Bo]'s Articles
[Wu Xiaowei]'s Articles
Baidu academic
Similar articles in Baidu academic
[Aziz Haris]'s Articles
[Li Bo]'s Articles
[Wu Xiaowei]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Aziz Haris]'s Articles
[Li Bo]'s Articles
[Wu Xiaowei]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.