Residential Collegefalse
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 PublicationArtificial Intelligence
ISSN0004-3702
Volume331Pages: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.

KeywordIndivisible Chores Ordinal Preferences Pareto Optimal Propx
DOI10.1016/j.artint.2024.104118
URLView the original
Indexed BySCIE
Language英語English
WOS Research AreaComputer Science
WOS SubjectComputer Science, Artificial Intelligence
WOS IDWOS:001217616700001
PublisherELSEVIER, RADARWEG 29, 1043 NX AMSTERDAM, NETHERLANDS
Scopus ID2-s2.0-85189366408
Fulltext Access
Citation statistics
Document TypeJournal article
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Corresponding AuthorLi, Bo
Affiliation1.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.
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
[Moulin, Hervé]'s Articles
Baidu academic
Similar articles in Baidu academic
[Aziz, Haris]'s Articles
[Li, Bo]'s Articles
[Moulin, Hervé]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Aziz, Haris]'s Articles
[Li, Bo]'s Articles
[Moulin, Hervé]'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.