Residential College | false |
Status | 已發表Published |
Approximately EFX Allocations for Indivisible Chores | |
Zhou,Shengwei; Wu, Xiaowei | |
2022-07 | |
Conference Name | 31st International Joint Conference on Artificial Intelligence (IJCAI 2022) |
Source Publication | Proceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022 |
Conference Date | 23-29 July 2022 |
Conference Place | Vienna, 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. |
Keyword | Efx Allocation Indivisible Chores Approximation Algorithm |
DOI | 10.1016/j.artint.2023.104037 |
URL | View the original |
Language | 英語English |
WOS ID | WOS:001115036200001 |
Scopus ID | 2-s2.0-85136693915 |
Fulltext Access | |
Citation statistics | |
Document Type | Conference paper |
Collection | THE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU) |
Corresponding Author | Zhou,Shengwei; Wu, Xiaowei |
Affiliation | IOTSC, University of Macau |
First Author Affilication | University of Macau |
Corresponding Author Affilication | University 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. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment