Residential Collegefalse
Status已發表Published
Approximately EFX Allocations for Indivisible Chores
Zhou,Shengwei; Wu, Xiaowei
2022-07
Conference Name31st International Joint Conference on Artificial Intelligence (IJCAI 2022)
Source PublicationProceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022
Conference Date23-29 July 2022
Conference PlaceVienna, Austria
Abstract

In this paper we study how to fairly allocate a set of m indivisible chores to a group of n agents, each of which has a general additive cost function on the items. Since envy-free (EF) allocation is not guaranteed to exist, we consider the notion of envy-freeness up to any item (EFX). In contrast to the fruitful results regarding the (approximation of) EFX allocations for goods, very little is known for the allocation of chores. Prior to our work, for the allocation of chores, it is known that EFX allocations always exist for two agents, or general number of agents with identical ordering cost functions. For general instances, no non-trivial approximation result regarding EFX allocation is known. In this paper we make some progress in this direction by showing that for three agents we can always compute a 5-approximation of EFX allocation in polynomial time. For n>=4 agents, our algorithm always computes an allocation that achieves an approximation ratio of 3n^2 regarding EFX. We also study the bi-valued instances, in which agents have at most two cost values on the chores, and provide polynomial time algorithms for the computation of EFX allocation when n=3, and (n-1)-approximation of EFX allocation when n>=4.

KeywordEfx Allocation Indivisible Chores Approximation Algorithm
DOI10.1016/j.artint.2023.104037
URLView the original
Language英語English
WOS IDWOS:001115036200001
Scopus ID2-s2.0-85136693915
Fulltext Access
Citation statistics
Document TypeConference paper
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Corresponding AuthorZhou,Shengwei; Wu, Xiaowei
AffiliationIOTSC, University of Macau
First Author AffilicationUniversity of Macau
Corresponding Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Zhou,Shengwei,Wu, Xiaowei. Approximately EFX Allocations for Indivisible Chores[C], 2022.
APA Zhou,Shengwei., & Wu, Xiaowei (2022). Approximately EFX Allocations for Indivisible Chores. Proceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022.
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
[Zhou,Shengwei]'s Articles
[Wu, Xiaowei]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhou,Shengwei]'s Articles
[Wu, Xiaowei]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhou,Shengwei]'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.