Residential College | false |
Status | 已發表Published |
Almost proportional allocations of indivisible chores: Computation, approximation and efficiency | |
Aziz, Haris1; Li, Bo2; Moulin, Hervé3; Wu, Xiaowei4; Zhu, Xinran1 | |
2024-06-01 | |
Source Publication | Artificial Intelligence |
ISSN | 0004-3702 |
Volume | 331Pages:104118 |
Abstract | Proportionality (PROP) is one of the simplest and most intuitive fairness criteria used for allocating items among agents with additive utilities. However, when the items are indivisible, ensuring PROP becomes unattainable, leading to increased focus on its relaxations. In this paper, we focus on the relaxation of proportionality up to any item (PROPX), where proportionality is satisfied if an arbitrary item is removed from every agent's allocation. We show that PROPX is an appealing fairness notion for the allocation of indivisible chores, which approximately implies some share-based notions, such as maximin share (MMS) and AnyPrice share (APS). We further provide a comprehensive understanding of PROPX allocations, regarding the computation, approximation, and compatibility with efficiency. On top of these, we extend the study to scenarios where agents do not share equal liability towards the chores, and approximate PROPX allocations using partial information about agents' utilities. |
Keyword | Indivisible Chores Ordinal Preferences Pareto Optimal Propx |
DOI | 10.1016/j.artint.2024.104118 |
URL | View the original |
Indexed By | SCIE |
Language | 英語English |
WOS Research Area | Computer Science |
WOS Subject | Computer Science, Artificial Intelligence |
WOS ID | WOS:001217616700001 |
Publisher | ELSEVIER, RADARWEG 29, 1043 NX AMSTERDAM, NETHERLANDS |
Scopus ID | 2-s2.0-85189366408 |
Fulltext Access | |
Citation statistics | |
Document Type | Journal article |
Collection | THE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU) |
Corresponding Author | Li, Bo |
Affiliation | 1.UNSW Sydney, Australia 2.The Hong Kong Polytechnic University, Hong Kong 3.University of Glasgow, Ireland 4.University of Macau, Macao |
Recommended Citation GB/T 7714 | Aziz, Haris,Li, Bo,Moulin, Hervé,et al. Almost proportional allocations of indivisible chores: Computation, approximation and efficiency[J]. Artificial Intelligence, 2024, 331, 104118. |
APA | Aziz, Haris., Li, Bo., Moulin, Hervé., Wu, Xiaowei., & Zhu, Xinran (2024). Almost proportional allocations of indivisible chores: Computation, approximation and efficiency. Artificial Intelligence, 331, 104118. |
MLA | Aziz, Haris,et al."Almost proportional allocations of indivisible chores: Computation, approximation and efficiency".Artificial Intelligence 331(2024):104118. |
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