Residential College | false |
Status | 已發表Published |
Almost (Weighted) Proportional Allocations for Indivisible Chores | |
Li, Bo1; Li, Yingkai2; Wu, Xiaowei3 | |
2022-04-25 | |
Conference Name | The ACM Web Conference 2022 (WWW 2022) |
Source Publication | WWW 2022 - Proceedings of the ACM Web Conference 2022 |
Pages | 122-131 |
Conference Date | 2022/04/25-29 |
Conference Place | Online, hosted by Lyon, France |
Publisher | Association 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. |
Keyword | Fair Allocation Partial Information Price Of Fairness Proportionality |
DOI | 10.1145/3485447.3512057 |
URL | View the original |
Indexed By | CPCI-S |
Language | 英語English |
WOS Research Area | Computer Science |
WOS Subject | Computer Science, Cybernetics ; Computer Science, Software Engineering ; Computer Science, Theory & Methods |
WOS ID | WOS:000852713000015 |
Scopus ID | 2-s2.0-85129855908 |
Fulltext Access | |
Citation statistics | |
Document Type | Conference paper |
Collection | THE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU) |
Affiliation | 1.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. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment