Residential Collegefalse
Status已發表Published
Almost (Weighted) Proportional Allocations for Indivisible Chores
Li, Bo1; Li, Yingkai2; Wu, Xiaowei3
2022-04-25
Conference NameThe ACM Web Conference 2022 (WWW 2022)
Source PublicationWWW 2022 - Proceedings of the ACM Web Conference 2022
Pages122-131
Conference Date2022/04/25-29
Conference PlaceOnline, hosted by Lyon, France
PublisherAssociation for Computing Machinery, Inc
Abstract

In this paper, we study how to fairly allocate a set of indivisible chores to a number of (asymmetric) agents with additive cost functions. We consider the fairness notion of (weighted) proportionality up to any item (PROPX), and show that a (weighted) PROPX allocation always exists and can be computed efficiently. We also consider the partial information setting, where the algorithms can only use agents' ordinal preferences. We design algorithms that achieve 2-approximate (weighted) PROPX, and the approximation ratio is optimal. We complement the algorithmic results by investigating the relationship between (weighted) PROPX and other fairness notions such as maximin share and AnyPrice share, and bounding the social welfare loss by enforcing the allocations to be (weighted) PROPX.

KeywordFair Allocation Partial Information Price Of Fairness Proportionality
DOI10.1145/3485447.3512057
URLView the original
Indexed ByCPCI-S
Language英語English
WOS Research AreaComputer Science
WOS SubjectComputer Science, Cybernetics ; Computer Science, Software Engineering ; Computer Science, Theory & Methods
WOS IDWOS:000852713000015
Scopus ID2-s2.0-85129855908
Fulltext Access
Citation statistics
Document TypeConference paper
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Affiliation1.Department of Computing, Hong Kong Polytechnic University, Hong Kong, Hong Kong
2.Department of Computer Science, Northwestern University, Evanston, United States
3.State Key Lab of Iotsc, University of Macau, Macao
Recommended Citation
GB/T 7714
Li, Bo,Li, Yingkai,Wu, Xiaowei. Almost (Weighted) Proportional Allocations for Indivisible Chores[C]:Association for Computing Machinery, Inc, 2022, 122-131.
APA Li, Bo., Li, Yingkai., & Wu, Xiaowei (2022). Almost (Weighted) Proportional Allocations for Indivisible Chores. WWW 2022 - Proceedings of the ACM Web Conference 2022, 122-131.
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
[Li, Bo]'s Articles
[Li, Yingkai]'s Articles
[Wu, Xiaowei]'s Articles
Baidu academic
Similar articles in Baidu academic
[Li, Bo]'s Articles
[Li, Yingkai]'s Articles
[Wu, Xiaowei]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Li, Bo]'s Articles
[Li, Yingkai]'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.