Approximately EFX Allocations for Indivisible Chores

• DOI: 10.48550/arxiv.2109.07313
• Publication Date: 2022-07-01
• Authors: Shengwei Zhou; Xiaowei Wu
• Keywords: FOS: Computer and information sciences; Computer Science - Computer Science and Game Theory; 0202 electrical engineering, electronic engineering, information engineering; 0102 computer and information sciences; 02 engineering and technology; 01 natural sciences; Computer Science and Game Theory (cs.GT)

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.