A Survey on Fair Allocation of Chores

Abstract

Wherever there is group life, there has been a social division of labor and resource allocation, since ancient times. Examples include ant colonies, bee colonies, and wolf colonies. Different roles are responsible for different tasks. The same is true of human beings. Human beings are the largest social group in nature, among whom there are intricate social networks and interest networks between individuals. In such a complex relationship, how do decision makers allocate resources or tasks to individuals in a fair way? This is a topic worthy of further study. In recent decades, fair allocation has been at the core of research in economics, mathematics and other fields. The fair allocation problem is to assign a set of items to a set of agents so that each agent’s allocation is as fair as possible to satisfy each agent. The fairness measurements followed in current research include envy-freeness, proportionality, equitability, maximin share fairness, competitive equilibrium, maximum Nash social diswelfare, and so on. In this paper, the main concern is the allocation of chores. We discuss this problem in two parts: divisible and indivisible. We comprehensively review the existing results, algorithms, and approximations that meet various fairness criteria in chronological order. The relevant results of achieving fairness and efficiency are also discussed. In addition, we propose some open questions and future research directions for this problem based on existing research.

1. Introduction

The fair allocation problem refers to the allocation of a set of items to a set of agents such that each agent is satisfied with the items they obtain. Although this problem is an extremely old one, academic research on fair allocation was initiated by Steinhaus (1948) [1] at the meeting of the Society of Econometrics in 1947. Since then, a large number of scholars in the fields of economics and mathematics have devoted themselves to theoretical research on fair allocation among agents. In international disputes and daily life, there is always a fair allocation problem. Traxler (2002) [2] studied how to allocate the cost of climate change mitigation and adaptation among countries in international cooperation. In the absence of a public supervisory organization that monitors the implementation of relevant agreements by countries, only the allocation of equal shares can better promote the achievement of international cooperation. Traxler solved this problem based on the principles of responsibility and fair allocation. Bulmer et al. (2020) [3] considered the problem of student allocation projects, assigning several students to a project, ensuring that all the requirements of the project are met and taking into account the social relationship between students. Payan (2022) [4] applied fair allocation technology to the allocation of reviewers. The cost of mitigating and adapting to climate change, the projects to be allocated, and the reviewers in the above examples can all be considered as items to be allocated in the fair allocation problem. This paper focuses on the fair allocation problem of chores, where the cost of mitigating and adapting to climate change can be seen as the allocation of chores among countries. However, many allocation problems in real life have not been formally defined, and no more fairness criteria have been proposed to measure the fairness of allocation. Because of the wide applicability of fair allocation and the lack of relevant content, researchers have paid increasing attention to it.

The objective of the fair allocation problem is to calculate a fair allocation, i.e., an allocation that meets a desired fairness criterion. In this paper, we summarize different definitions to measure the fairness of allocation, including envy-freeness (EF), proportionality (PROP), equitability (EQ), and maximin share (MMS) fairness. EF and PROP were also fairness criteria that were the focus of early research on this problem. However, some fair allocations of chores do not always exist. The simplest example is to consider assigning two single-person tasks with significant cost differences to two workers. The worker assigned to the high-cost task must envy those assigned to the low-cost task. Obviously, the EF allocation in this example does not exist. This is also one of the reasons why many researchers have studied the relaxation of fairness. In addition, compared with the fair allocation of goods, some properties of the fair allocation of chores may not have or need to be explained in a different way, for example, the well-known envy-cycle elimination algorithm (Lipton et al. (2004) [5]). For indivisible goods, we only need to construct a general envy graph and then eliminate the envy-cycle in the graph to obtain an allocation of envy-free up to one chore (EF1). For indivisible chores, EF1 is defined as removing the chores in the envy agent’s bundle to ensure EF. Therefore, using the general envy graph can lead to an irreparable envious relationship between agents (detailed details can be found in Example 11). To avoid this, EF1 allocation of indivisible chores can only be achieved by eliminating the top-trading envy-cycle (Bhaskar et al. (2020) [6]) in the top-trading envy graph. (The top-trading envy graph is also constructed through the envious relationship between agents. The difference is that, among all envious objects of an agent, the agent only forms a directed edge with its most envious object).

The difference between this paper and existing relevant reviews is that we focus on existing research on the fair allocation of divisible and indivisible chores. To help readers understand the relevant research comprehensively, we classify the existing research using different concepts of fairness. In this paper, we introduce the main contributions of the relevant literature in order of publication time, including algorithm technology and improvement of existing results. In addition, we put forward some relevant open questions and future research directions for readers’ reference.

This section mainly introduces the research background of the fair allocation problem of chores. The rest of the survey is organized as follows. In Section 2, we review surveys from different perspectives on the fair allocation problem and the current research status of the unrelated parallel machine scheduling problem, which is similar to the fair allocation of chores. In Section 3, we first introduce the fair allocation problem of divisible and indivisible chores, as well as some concepts of fairness. In Section 4, we present the research results of envy-freeness and its relaxation forms in recent years. In Section 5, the research results of proportionality and its relaxation forms in recent years are introduced. In Section 6, we introduce the research status of equitability and its relaxation forms in recent years. The research status of maximin share fairness and its variant forms in recent years is presented in Section 7. In Section 8, we introduce research related to the fair allocation of chores from three aspects: competitive equilibrium, maximum Nash social diswelfare, and the Fisher market. We summarize our survey and propose some future research directions for this problem in Section 9. Finally, we list the symbols used in this paper and corresponding instructions in the Appendix A.

2. Related Work

The fair allocation of chores can be seen as a scheduling problem for unrelated parallel machines ($R\left|\right|C_{max}$). The chore corresponds to the job. The agent corresponds to the unrelated parallel machine. In the fair allocation problem of chores, the disutility of each agent for each chore can be seen as the time consumed by each machine to process each job in the scheduling problem. Similar to the fair allocation problem of chores, scheduling problems require assigning each job to one of the machines for processing. For $R\left|\right|C_{max}$, Lenstra et al. (1990) [7] designed a 2-approximation algorithm by using techniques such as linear programming relaxation and rounding. It is also proven that, unless P = NP, there is no approximation algorithm whose approximation ratio is strictly less than 3/2. When the machine processing time for the job in problem $R\left|\right|C_{max}$ is $p_{ij}=p_j$, then the problem is transformed into a scheduling problem for the identical parallel machine ($P\left|\right|C_{max}$). McNaughton (1959) [8] studied the parallel machine problem for the first time. Hochbaum and Shmoys (1987) [9] designed the first polynomial time approximation scheme (PTAS), that is, given instance I, for $\forall ϵ>0$, there is a family of algorithms $A_{ϵ}$, where the approximation ratio of the algorithms in $A_{ϵ}$ does not exceed $1+ϵ$—these are polynomial time $poly\left(\right|I\left|\right)$ algorithms. The same authors in the following year provided PTAS for uniform parallel machine scheduling problems (Hochbaum and Shmoys (1988) [10]). Alon et al. (1998) [11] first proposed an efficient polynomial time scheme (EPTAS). Compared to PTAS, its running time has been improved to $f\left(\frac{1}{ϵ}\right)+poly\left(\right|I\left|\right)$. Jansen et al. (2020) [12] further improved the algorithm runtime, reducing it to $2^{(1/ϵ){log}^{O\left(1\right)}(1/ϵ)}+n^{O\left(1\right)}$.

Research on fair allocation has not stopped since it was proposed. There are several papers investigating the fair allocation problem from different perspectives. Brams (2008) [13] discussed the fair allocation problem from the perspective of political science. Procaccia (2013) [14] introduced research on cake cutting in the field of computer science. In addition, how to design efficient and unaffected cake-cutting algorithms and how to apply cake-cutting research to the allocation of computing resources were discussed. Moulin (2019) [15] conducted a review from an economic perspective. Walsh (2020) [16] analyzed how to allocate items fairly and efficiently from a computational perspective. Aleksandrov and Walsh (2020) [17] focused on the fair allocation problem in the online context. The review provided by Aziz et al. (2022) [18] mainly focused on the fair allocation of indivisible items. They conducted a survey of the literature in recent years by the prism of algorithms. Amanatidis et al. (2022) [19] surveyed some important results regarding the fair allocation of indivisible goods. However, this paper focused on the fair allocation of chores, which was first proposed by Gardner (1978) [20]. The difference between this fair allocation study and the fair allocation study proposed in 1947 is that the fair allocation of chores proposed in 1978 has negative utilities in the allocation of items. The problem proposed in 1947 has nonnegative utilities on the allocation of items. For the fair allocation of goods, each agent wants to obtain the most utility goods. For the fair allocation of chores, each agent prefers low disutility chores. Liu et al. (2023) [21] discussed fair division with mixed types of resources, which has received growing attention, and focused on three mixed fair division domains. Amanatidis et al. (2023) [22] conducted a comprehensive review of the latest developments in the literature on fair allocation problems, emphasizing different methods for relaxing the concept of fairness, common algorithm design techniques, and the most interesting problems in future research.

3. Preliminaries

In this section, we introduce a mathematical model for the fair allocation of chores. According to the divisible and indivisible characteristics of chores, the fair allocation problem of chores can be divided into two categories. In the following text, we introduce the models of these two types of problems separately.

The fair allocation problem can be regarded as a multi-agent system. In this paper, we use agents to represent the individuals participating in the allocation. A multi-agent system refers to a group system composed of many agents (Dorri et al., 2018 [23]). It completes a large and complex amount of work that a single agent cannot complete by means of mutual communication, cooperation and competition among agents.

Consider an instance of divisible chores $<N,\mathcal{C},\mathcal{F}>$, where N represents a set of n agents, divisible chores $\mathcal{C}$ are represented by the interval $[0,1]$, and $\mathcal{F}$ represents a nonnegative density function family of divisible chores. For divisible chores, each agent $i\in N$ has its own density function $f_i:[0,1]\to {\mathbb{R}}_{⩾0}$, so that, for any measurable subset $S\subset [0,1]$, the disutility [6] of agent i to S is

$$d_i\left(S\right)={\int }_S{f}_i\left(x\right)dx.$$

For the allocation problem of divisible chores, the most classic example is the problem of cutting a bad cake. Every agent does not want to obtain more bad cakes. If an agent is not satisfied with the bad cake assigned, the allocator can cut off a part of the agent’s cake or cut a part of the unallocated cake to other agents for fairness. Note that the cake can be cut at will.

Consider an instance of indivisible chores $<N,\mathcal{C},\mathcal{D}>$, where N represents a set of n agents, $\mathcal{C}$ represents a set of m indivisible chores, and $\mathcal{D}=\{d_1,d_2,\cdots ,d_n\}$ represents the nonnegative disutility function set of each agent, where $d_i:2^{\mathcal{C}}\to {\mathbb{R}}_{⩾0}$ and $d_i\left(j\right)$ represents the disutility of agent $i\in N$ on chore $j\in \mathcal{C}$.

For the allocation problem of indivisible chores, we consider the example of assigning individual tasks, where a task can only be completed independently by one player. No player wants to be assigned more tasks or high-cost tasks. However, individual tasks cannot be divided and assigned to multiple players. Nurse scheduling and course matching are both such problems.

The difference between the allocation of divisible and indivisible chores lies in the characteristics of the chores to be allocated. During the allocation process, divisible chores can be split for allocation, while indivisible chores cannot be split. This leads to the allocation of divisible chores satisfying some fair properties, while the allocation of indivisible chores does not.

For disutility functions, researchers mainly focus on the following four classes in the literature on the fair allocation of chores.

The first is the binary disutility function, which is the simplest class function among all disutility functions. The value range of this class function can only take two numbers.

Definition 1

([6]). A disutility function $d_i$ is binary if, for $\forall i\in N,j\in \mathcal{C},d_i\left(j\right)\in \left\{0,1\right\}$.

The second is the additive disutility function, which is the most commonly used disutility function.

Definition 2

([24]). A disutility function $d_i$ is additive if, for $\forall S\subseteq \mathcal{C},d_i\left(S\right)={\sum }_{j\in S}{d}_i\left(j\right)$.

The third is the submodular disutility function, which reflects the decline in marginal disutility.

Definition 3

([25]). A disutility function $d_i$ is submodular if, for $\forall S_1\subseteq S_2\subseteq \mathcal{C}$ and $c\in \mathcal{C}\setminus S_2,d_i(S_2\cup \left\{c\right\})-d_i\left(S_2\right)⩽d_i(S_1\cup \left\{c\right\})-d_i\left(S_1\right)$.

The fourth is the subadditive disutility function. The value returned by the sum of any two elements in the domain of the function is less than or equal to the sum of the values returned by the two elements.

Definition 4

([25]). A disutility function $d_i$ is subadditive if, for $\forall S_1,S_2\subseteq \mathcal{C},d_i(S_1\cup S_2)⩽d_i\left(S_1\right)+d_i\left(S_2\right)$.

Figure 1 shows the applicability of the four disutility functions. All four disutility functions are applicable to the fair allocation problem of indivisible chores, while only additive disutility functions are applicable to the fair allocation problem of divisible chores. In addition, some studies only consider the partially ordered relation between the disutility of agents, without considering the specific disutility value of each agent.

Suppose an allocation $A=(A_1,A_2,\cdots ,A_n)$ is an n partition of set $\mathcal{C}$, where $A_i$ is the bundle assigned to agent i. We define the set of all feasible allocations through $\mathcal{A}$. If $A\in \mathcal{A}$, $A_i$ needs to satisfy

$$A_i\cap A_j=⌀,i\ne j,\mathrm{and}\bigcup _{i\in N}{A}_i=\mathcal{C}.$$

The goal of the fair allocation problem is to find a fair allocation, that is, the allocation needs to meet an ideal fairness. To measure fairness, the literature proposes different definitions. The commonly used definitions are EF, PROP, MMS, and their relaxation forms. In addition, other types of concepts for measuring fairness are also discussed.

To quantify the social diswelfare of fair allocation loss, the concept of the price of fairness is applied. First, there are two ways to define the allocation A of social diswelfare.

The first is utilitarian social diswelfare, which takes into account the disutility of all agents.

Definition 5

([26]). The utilitarian social diswelfare of allocation A is $u\left(A\right)={\sum }_{i\in N}{d}_i\left(A_i\right)$.

To quantify the loss of utilitarian social diswelfare due to fair allocation, the concept of fair price with utilitarian diswelfare is defined as follows.

Definition 6

([27]). For any given fairness property F, the price of fairness with utilitarian diswelfare on a given instance $\mathcal{I}$ is

$$PO{F}_u=\underset{\mathcal{I}}{sup}\underset{A\in F\left(\mathcal{I}\right)}{min}\frac{u\left(A\right)}{OPT\left(\mathcal{I}\right)}$$

where $F\left(\mathcal{I}\right)$ represents all fair allocations corresponding to fair property F under this instance $\mathcal{I}$. The fairness property F can be envy-freeness, envy-free up to one chore, envy-free up to any chore, proportionality, proportionality up to one chore, proportionality up to any chore, maximin share fairness, and so on. OPT($\mathcal{I}$) is defined as the optimal social diswelfare of instance $\mathcal{I}$, which is the minimum social diswelfare among all allocations in that instance.

The second is egalitarian social diswelfare, which reflects the disutility of the worst-off agent.

Definition 7

([26]). The egalitarian social diswelfare of allocation A is $eq\left(A\right)={max}_{i\in N}{d}_i\left(A_i\right)$.

To quantify the loss of egalitarian social diswelfare due to fair allocation, the concept of fair price with egalitarian diswelfare is defined as follows:

Definition 8

([27]). For any given fairness property F, the price of fairness with egalitarian diswelfare at a given instance $\mathcal{I}$ is

$$PO{F}_e=\underset{\mathcal{I}}{sup}\underset{A\in F\left(\mathcal{I}\right)}{min}\frac{eq\left(A\right)}{OPT\left(\mathcal{I}\right)}$$

where $F\left(\mathcal{I}\right)$ represents all fair allocations corresponding to fair property F under this instance $\mathcal{I}$. The fairness property F can be envy-freeness, envy-free up to one chore, envy-free up to any chore, proportionality, proportionality up to one chore, proportionality up to any chore, maximin share fairness, and so on. OPT($\mathcal{I}$) is defined as the optimal social diswelfare of instance $\mathcal{I}$, which is the minimum social diswelfare among all allocations in that instance.

Next, we introduce relevant research based on fairness criteria and their relaxations. Our introduction in each section is based on the publication date of the paper.

4. Envy-Freeness and Its Relaxations

In this section, we mainly introduce relevant research on envy-freeness (EF) and its relaxations in fair allocation. EF is one of the fairness criteria that received much attention in early research.

4.1. Envy-Freeness

If no agent in an allocation thinks that the bundle received by other agents is better than his own, the allocation is said to be envy-free. In 1930, Tinbergen [28] first proposed the fair concept of EF.

Definition 9

([27]). An allocation $A\in \mathcal{A}$ is envy-free if, $\forall i,j\in N,d_i\left(A_i\right)⩽d_i\left(A_j\right)$.

For divisible chores, the most classic problem is the problem of cutting bad cakes. Some studies discuss the existence of EF allocation of chores. Su (1999) [29] gave an envy-free chore allocation algorithm for n agents, but it is $ϵ$-approximate. Peterson and Su (2002) [30] designed a simple and bounded algorithm for EF allocation among four agents. This algorithm is also a bad cake-cutting algorithm, which requires 16 cuts at most. The main core of the algorithm is to irretrievably trim and mark the smallest block considered by two agents based on the last allocation until the two agents have no consensus on which block is the smallest. Peterson and Su (2009) [31] designed an n-agents EF chore division procedure. However, this procedure may require any number of cuts to solve the problem. Based on the generalization of Sperner’s lemma (Su (1999) [29]), Segal-Halevi (2018) [32] proved that there is EF division in cutting the cake between three agents. Dehghani et al. (2018) [33] provided a discrete and bounded EF algorithm for fair allocation among arbitrary numbers of agents. In addition, they provided a powerful tool design algorithm of disutility objects for fair allocation. At the same time, it was also found that the application of these tools simplifies the core protocol proposed by Aziz and Mackenzie (2016) [34]. Bogomolnaia et al. (2019) [35] defined two chore allocation rules and proved that, in the case of dividing at least two bad cakes between at least four agents, if one rule is single-valued and continuous, then the other rule cannot also be efficient and EF. Nyman et al. (2020) [36] considered the EF allocation problem of collections of k pieces from a given chore set among n agents. They combined the topological method in hypergraph theory to prove that at least a number of agents proportional to the value obtains the most-desired k cakes when n takes a different value. Bhaskar et al. (2020) [6] proved that determining the existence of an EF allocation is NP-complete even for binary disuility. Sanpui (2023) [37] wais concerned about the problem of externality chore division (the concept of externality comes from psychological research, where each agent believes that their disutility is influenced by both their own bundle and the bundles of other agents). He proved that at least n cuts are required to obtain swap envy-free allocation and that $n-1$ cuts are required when needed individually.

Another segment of articles studied algorithms for achieving fairness and efficiency. To quantify social diswelfare losses, some researchers have introduced fair prices. Caragiannis et al. (2012) [27] found that the price of EF with utilitarian diswelfare is $\frac{9}{8}$ for the divisible chore allocation problem of two agents, and the price of EF with utilitarian diswelfare is at least $\frac{{(n+1)}^2}{4n}$ for the divisible chore allocation problem of n agents. Heydrich and van Stee (2015) [26] observed that the price of EF with utilitarian diswelfare and egalitarian diswelfare is ∞ under continuous allocation. Sandomirskiy and Segal-Halevi (2022) [38] studied a fair and fractional Pareto optimal (fPO) allocation algorithm problem that minimizes the number of shares. They proved that there exists an EF+fPO division with at most $n-1$ shares in any instance with n agents. Azharuddin (2023) [39] proved that, even if every agent has a nonzero disutility, there is no deterministically truthful EF mechanism.

For indivisible chores, Caragiannis et al. (2012) [27] proved that the price of EF with utilitarian diswelfare is infinite for the indivisible chore allocation problem of n agents, and the price of EF with utilitarian diswelfare is two for the indivisible chore allocation problem of two agents. Bouveret et al. (2019) [40] analyzed the existence of EF allocation of indivisible chores based on different graph structures. The constructed graph is an undirected graph with chores as its vertex, and the chores in the bundle allocated by each agent are connected on the graph. This document discusses three graph structures: complete graphs, paths, and stars. For additive disutility and maximization disutility, the problem is NP-complete (NP means nondeterministic polynomial) on complete graphs and stars. For additive disutility, maximum disutility, and binary disutility, the problem is NP-complete on the paths. The graph structure of the path is shown in Figure 2.

Höhne and Stee (2021) [41] arranged chores in a line and allocated them to seek a fair allocation of chores. They showed that the prices of EF with utilitarian and egalitarian diswelfare are unbounded. Aziz et al. (2022a) [42] proved that there is a polynomial-time algorithm to verify whether there is EF allocation for two types of chores. Note that, for the general example of indivisible chores, this problem is NP-hard. Hosseini et al. (2022) [43] proved that, even for lexicographic chore-only instances, determining the existence of EF allocation is NP-complete.

4.2. Envy-Free up to One Chore

EF is an ideal criterion to measure fairness in fair allocation. Unfortunately, in some scenarios, EF allocation may not exist, so envy-free up to one chore (EF1) was introduced (Conitzer et al. (2017) [44]).

Definition 10

([24]). An allocation $A\in \mathcal{A}$ is envy-free up to one chore if $\forall i,j\in N,d_i(A_i\backslash c\})⩽d_i\left(A_j\right)$, where c represents some chore allocated by agent i.

For indivisible chores, Aleksandrov (2018) [24] proved that EF1 allocation always exists for additive disutility and can be calculated in polynomial time $O\left(m\right)$ by a responsive draft algorithm. For anti-monotone identical disutility, the Lipton algorithm (Lipton et al. (2004) [5]) can be applied to solve the problem. However, the result will not be ideal, as it will allocate all the chores to a single agent. For this reason, by improving the Lipton algorithm, the new algorithm can also obtain the EF1 allocation for general cases. Bhaskar et al. (2020) [6] provided a polynomial-time algorithm for computing an EF1 allocation under monotone disuility. A counterexample (see Example 1 for details) is given to illustrate that, even when each agent has additive disutility, it is difficult for the envy-cycle elimination algorithm to find an EF1 allocation, and the conclusion is contrary to that in Aziz et al. (2022b) [45]. Finally, to calculate the EF1 allocation of indivisible chores, they improved the famous envy-cycle elimination algorithm for indivisible goods by Lipton et al. (2004) [5] and obtained the top-trading envy-cycle elimination algorithm.

Example 1

([45]). Consider the following example: there are six indivisible chores and three agents with additive disutility.

	${\mathbf{c}}_{\mathbf{1}}$	${\mathbf{c}}_{\mathbf{2}}$	${\mathbf{c}}_{\mathbf{3}}$	${\mathbf{c}}_{\mathbf{4}}$	${\mathbf{c}}_{\mathbf{5}}$	${\mathbf{c}}_{\mathbf{6}}$
$a_1$	1	2	2	3	1	3
$a_2$	1	4	3	1	4	4
$a_3$	3	1	1	2	2	3

Assume that the allocation order of the algorithm is to allocate the chores to three agents in the order of increasing the number of chores, so agent 1 obtains chores 1 and 4, agent 2 obtains chores 2 and 5, and agent 3 obtains chores 3 and 6. This allocation scheme is called allocation A. It is verified that the allocation is EF1, not EF, and its envy graph is shown in Figure 3a.

In the envy graph of allocation A, there are two envy cycles: the first is formed between agent 1 and agent 2, and the second is formed between agent 2 and agent 3. Then, the envy-cycle elimination algorithm is run on the two envy cycles, and the allocations X and Y are obtained. The envy graphs are shown in Figure 3b,c. Although these two envy graphs are acyclic, the allocation Y violates the property of EF1.

Sun et al. (2021a) [46] proved that, when the cost function is additive, one fairness is approximately guaranteed to the other fairness. In addition, the efficiency of fair allocation is compared with that of optimal allocation. To quantify the efficiency loss, the concept of the price of fairness is applied. When $n=2$, the fair price of EF1 is $\frac{5}{4}$. When $n>2$, the fair price of EF1 is unbounded. Garg et al. (2021) [47] gave a strong polynomial-time algorithm to calculate the EF1 allocation of the bivalued instance. Aziz et al. (2022b) [45] considered a circular algorithm. In this algorithm, agents take turns selecting their favorite unallocated chores. This algorithm can be used to find the EF1 allocation of indivisible chores. However, if some are goods and others are chores, this algorithm cannot find EF1 allocation. For the general example of bivalued disutilities, Ebadian et al. (2022) [48] divided chores into categories of easy and difficult for each agent, and the cost of easy chores was lower than that of difficult chores for each agent. In this context, EF1 allocation is found in polynomial time using the Fisher market-based algorithm.

In addition to computing a fair allocation, another natural requirement is efficiency. Some studies have explored the relationship between EF1 and Pareto optimality (PO). Chaudhury et al. (2022a) [49] verified that, when the disutility function of the agent is a binary disutility, there is always an allocation that satisfies both EF1 and PO. Aziz et al. (2022a) [42] gave a polynomial-time algorithm for calculating the EF1+fPO allocation for two types of chores. Garg et al. (2022) [50] proved that EF1+fPO allocation always exists in the case of three agents and at most two binary disutility functions, where fPO requires PO in all fractional results. In the generalized binary disutility (a disutility function $d_i$ is generalized binary if, for $\forall i\in N,j\in \mathcal{C},d_i\left(j\right)\in \left\{0,1\right\}$ and $d_i$ is an additive disutility function) scenario of chores, the algorithm of Camacho et al. (2023) [51] can give the allocation of EF1+PO in polynomial time $O\left(mn\right)$. The problem discussed by Barman et al. (2023) [52] is the fair allocation of indivisible chores under binary supermodular disuility functions. They proved that EF1 allocation always exists for these disuility functions. Akrami et al. (2023) [53] introduced the concept of $k⩽n$ surplus and proposed a polynomial-time algorithm to obtain EF1 and PO allocation with $(n-1)$ surplus, which corresponds to surplus in the setting where good is charity (Caragiannis et al. (2019) [54]). For a lexicographic mixed instance with at least $n-1$ common terrible chores, Hosseini et al. (2023) [55] proved the existence of EF1 and PO allocation, which can be computed in polynomial time.

4.3. Envy-Free up to Any Chore

The allocation of envy-free up to any chore (EFX) was introduced by Aleksandrov (2018) [24]. However, EFX is a stronger form of EF1.

Definition 11

([24]). An allocation $A\in \mathcal{A}$ is envy-free up to any chore if, $\forall i,j\in N,d_i(A_i\backslash \left\{c\right\}\})⩽d_i\left(A_j\right)$, where c represents any chores allocated by agent i when allocating indivisible chores.

For indivisible chores, Aleksandrov (2018) [24] proved that the Leximax solution (it selects an allocation that maximizes the minimum disutility, and then the second minimum disutility, and so on) is an EFX allocation for the same antimonotone disutility, the antimonotone disutility, and the case with two agents. For the case of the additive disutility function, the EFX allocation can be calculated in polynomial time $O\left(m\right)$. Chen and Liu (2020) [56] promoted the Leximax solution and verified that the EFX allocation of goods and chores combination always exists for agents with general and the same disutility. Gafni et al. (2021) [57] showed that EFX allocation exists when each agent has a leveled disutility function, where the larger set of chores is always more burdensome than the smaller set. In addition, they established a new characteristic for the important problem of the existence of EFX allocation. This characteristic incurs the rationality of the new fairness criterion EFXwc, which requires each agent i to prefer her own bundle more than any other agent j’s bundle if any chore that is not in the bundle of i is removed from j’s bundle. Aziz et al. (2022a) [42] proved that EFX allocation always exists and can be calculated in polynomial time for instances with two types of chores. Kobayashi et al. (2023) [58] studied the existence of EFX allocation in three special cases: cases with $m⩽2n$ chores and each agent having an additive disutility, cases with $n-1$ agents having identical ordering disutility, and cases with $n=3$ and each agent having a personalized bi-valued disutility.

To quantify the social diswelfare of EFX allocation loss, the concept of the price of EFX is applied. Sun et al. (2021a) [46] proved that, when $n=2$, the fair price of EFX is 2. When $n>2$, the fair price of EFX is unbounded. Zhou and Wu (2022) [59] proved that, for three agents, five-approximation EFX allocation can be calculated in polynomial time. For $n>3$ agents, the algorithm proposed in this paper can always obtain an allocation that is a $3n^2$-approximation EFX allocation. In addition, for bivalued instances, each agent has at most two disutility values for each chore, which verifies that EFX allocation can be obtained in polynomial time when $n=3$ and $(n-1)$-approximation EFX allocation when $n>3$.

To further explore the properties of EFX, Yin and Mehta (2022) [60] introduced the relaxation form of EFX, tEFX (an allocation $A\in \mathcal{A}$ is tEFX if, for any $i,j\in N,d_i(A_i\backslash \left\{c\right\}\})⩽d_i(A_j\cup \left\{c\right\}),\forall c\in A_i$). For this relaxation, they considered the problem of assigning a set of indivisible chores to three agents, two of which have additive disutilities. In addition, it was proven that EFX allocation always exists if two of the three agents share the same chore ordering and the disutility function is additive. It was also proven that, if two of the three agents have an additive disutility function, the tEFX allocation always exists. Based on the research of Yin and Mehta, Akrami et al. (2023) [53] proposed a polynomial-time algorithm that returns proportional allocation or tEFX allocation in the case of chores with three agents.

Some studies have explored the relationship between EFX and PO. Given a chore instance, Hosseini et al. (2022) [43] proved that EFX and PO allocation can be obtained in polynomial time. In the generalized binary disutility scenario of chores, the algorithm of Garg et al. (2022) [50] proved that EFX+fPO allocation always exists for three agents with bivalue disutility. Camacho et al. (2023) [51] can give the EFX+PO allocation in $O(mlogm+mn)$ time.

4.4. Other Relaxation of Envy-Free

Group envy-freeness (GEF) implies both EF and PO, which are the core concepts of fairness and efficiency.

Definition 12

([61]). An allocation $A\in \mathcal{A}$ is group envy-free if, for every $S,T\subset N$, such that $\left|S\right|=\left|T\right|\ne 0$, there is no $A^{\prime }\in \Pi (A_T,S)$, such that $\frac{\left|S\right|}{\left|T\right|}{d}_i\left(A_i^{\prime }\right)⩽d_i\left(A_i\right),\forall i\in S$, with one inequality is strict, where $\Pi (A_T,S)$ is the set of all the allocations over $A_T$ and S, and $A_T$ is the set of chores allocated to all agents in T.

In the same spirit as EF1 and EFX, group envy-freeness up to one chore (GEF1) and group envy-freeness up to any chore (GEFX) can be defined similarly to GEF. Aziz and Rey (2019a) [61] combined the GEF proposed by Berliant et al. (1992) [62] to further relax EF1, yielding GEF1 (an allocation $A\in \mathcal{A}$ is GEF1 if, for every $S,T\subset N$, such that $\left|S\right|=\left|T\right|\ne 0$, there is no $A^{\prime }\in \Pi (A_T,S)$, and for every $i\in S$, there exists $c_i\in A_i$, $|c_i|⩽1$, such that $\frac{\left|S\right|}{\left|T\right|}{d}_i(A_i^{\prime }\backslash \left\{c_i\right\})⩽d_i(A_i\backslash \left\{c_i\right\}),\forall i\in S$, with one inequality being strict) and s-GEF1 (compared to GEF1, s-GEF1 has no condition of $\left|S\right|=\left|T\right|$). The nature of s-GEF1 is stronger than that of GEF1, which is not limited by the size of the group. They designed a polynomial-time algorithm and proved that the allocation returned by the algorithm is GEF1 by invoking Hall’s marriage theorem. In addition, it is proven that determining whether a given allocation satisfies GEF1 is coNP-complete. Segal-Halevi and Suksompong (2023) [63] divided all agents into groups and found EF allocation between the groups. In addition, they demonstrated that the result is not applicable to the mixed cake (for a certain part of a cake, some agents believe that it is good, while others believe that it is bad).

To obtain a more fine-grained approximate EF allocation, the concept of envy-free up to k dubious chores (DEF-k) was introduced. It takes an epistemic approach utilizing information asymmetry by introducing dubious chores.

Definition 13

([64]). An allocation $A\in \mathcal{A}$ is envy-free up to k dubious chores if ∃ a dubious multiset D and dubious allocation $A^D$, such that D consists of up to k dubious chores copied from $\mathcal{C}$ and $A\cup A^D$ is envy-free, where dubious chores do not have any cost to the receiving agent, while other agents consider them expensive, and $A^D$ is an n-partition of the multiset D.

Hosseini et al. (2023) [64] defined a new concept of fairness called DEF-k. It achieves disutility information asymmetry by introducing dubious chores. They proved that, for binary disutility instances, determining an allocation that is DEF-k is NP-complete, every EF1 allocation is DEF-$n(n-1)$, and RoundRobin always returns a DEF-$(n-1)$ allocation. In addition, they also demonstrated that the allocation satisfying DEF-$(2n-2)$ and PO always exists, and, for instances with two types of chores, the allocation satisfying DEF-$(n-1)$ and PO always exists and can be calculated in polynomial time.

For a general fair allocation problem, each agent has equal obligations. In real life, this is often not the case, as each agent will have different obligations due to their different social statuses. The weight in weighted envy-freeness (WEF) represents the obligation of each agent on the chores.

Definition 14

([65]). An allocation $A\in \mathcal{A}$ is weighted envy-free if, for $\forall i,j\in N,$

$$\frac{d_i\left(A_i\right)}{w_i}⩽\frac{d_i\left(A_j\right)}{w_j},$$

where each agent $i\in N$ has a weight $w_i>0$, and ${\sum }_{i\in N}{w}_i=1$.

According to the definition of WEF, EF1 can naturally be extended to weighted envy-free up to one chore (WEF1).

Definition 15

([65]). An allocation $A\in \mathcal{A}$ is weighted envy-free up to one chore if, for $\forall i,j\in N,$ either $A_i=⌀$ or ∃ a chore $c\in A_i$, such that

$$\frac{d_i(A_i\backslash \left\{c\right\})}{w_i}⩽\frac{d_i\left(A_j\right)}{w_j},$$

where each agent $i\in N$ has a weight $w_i>0$, and ${\sum }_{i\in N}{w}_i=1$.

Wu et al. (2023) [65] proved that there exists a polynomial-time algorithm that computes WEF1 allocations for the allocation of chores to weighted agents, and there exists a polynomial-time algorithm that computes WEF1 and PO allocations for bivalued instances. The price of WEF1 is unbounded for three or more agents and is $\frac{4+\alpha }{4}$ for two agents, where $\alpha =\frac{max\{w_1,w_2\}}{min\{w_1,w_2\}}$.

Next, we will consider the more natural relaxation form of WEF1, weighted envy-free up to removal of a chore in the first bundle and addition of another chore from the other bundle (weighted-$E{F}_1^1$).

Definition 16

([66]). An allocation $A\in \mathcal{A}$ is weighted envy-free up to removal of a chore in the first bundle and addition of another chore from the other bundle if, for $\forall i,j\in N,$∃ an item $c\in A_i$ and $c^{\prime }\in \mathcal{C}$, such that

$$\frac{d_i(A_i\backslash \left\{c\right\})}{w_i}⩽\frac{d_i(A_j\cup \left\{c^{\prime }\right\})}{w_j},$$

where each agent $i\in N$ has a weight $w_i>0$, and ${\sum }_{i\in N}{w}_i=1$.

Brânzei and Sandomirskiy (2023) [66] proved that there exists an indivisible allocation A that is Pareto optimal in the divisible problem and satisfies weighted-$E{F}_1^1$ for any chore allocation problem.

To quantify the social diswelfare of EF allocation loss, the concept of the price of EF is applied. The fair prices with utilitarian diswelfare related to the EF and relaxation forms of EF are shown in

Table 1. The prices of EF with utilitarian diswelfare ($\alpha =\frac{max\{w_1,w_2\}}{min\{w_1,w_2\}}$, where $w_i$ is the weight of agent i).

	EF	EF1	WEF1	EFX
Indivisible	2 for $n=2$	5/4 for $n=2$	(4 + $\alpha$)/4 for $n=2$	2 for $n=2$
	∞ for $n⩾3$	∞ for $n⩾3$	∞ for $n⩾3$	∞ for $n⩾3$
	Caragiannis et al. [27]	Sun et al. [46]	Wu et al. [65]	Sun et al. [46]
Divisible	9/8 for $n=2$
	${(n+1)}^2/4n$ for $n⩾3$
	Caragiannis et al. [27]

. Because there are only a few results of EF prices with egalitarian diswelfare, they are not displayed here.

Recently, more scholars have focused on envy-free up to k goods (EFk) (an allocation $A\in \mathcal{A}$ is EFk if, $\forall i,j\in N$ and ∃ goods $c_1,\cdots ,c_k,u_i\left(A_i\right)⩾u_i(A_j\backslash \{c_1,\cdots ,c_k\})$, where $u_i$ is the utility function of agent i on the goods, Warut (2021) [67]). The fair allocation problem of goods has been addressed and some related algorithms have been designed. For example, Barman et al. (2023) [68] designed a simple, greedy, polynomial-time algorithm that finds EF2 allocation under budget constraints.

Open problem 1.

For fair allocation of chores, does the definition of EFk need to differ from the fair allocation of goods?

5. Proportionality and Its Relaxations

In this section, we mainly introduce relevant research on proportionality (PROP) and its relaxations in fair allocation. PROP is one of the fairness criteria that received much attention in early research.

5.1. Proportionality

To compare the relationship between evenly allocating all chores and the agent’s own bundle, the fair concept of PROP was introduced. If the agent prefers the bundle they are assigned to more than the even allocation, the allocation is called PROP allocation.

Definition 17

([27]). An allocation $A\in \mathcal{A}$ satisfies proportionality to n agents (PROP) if, $\forall i\in N,d_i\left(A_i\right)⩽\frac{d_i\left(\mathcal{C}\right)}{n}$.

For divisible chores, Caragiannis et al. (2012) [27] found that the price of PROP with utilitarian diswelfare is $\frac{9}{8}$ for two agents, and, for n agents, the price of PROP with utilitarian diswelfare is at least $\frac{{(n+1)}^2}{4n}$ and at most n. Farhadi and Hajiaghayi (2017) [69] gave a lower bound $\Omega \left(nlogn\right)$ for PROP allocation. In the proof process, the dual concept of the disutility function was introduced, and they demonstrated how to use the dual function to simplify some problems in chore allocation to similar problems in cake cutting. Yedidsion et al. (2021) [70] considered a new variant of fair allocation called sequential online chore division (when the agent performs chores, they arrive and depart online). It was also found that the best fairness and efficiency can be guaranteed in the centralized setting. For a single game in a distributed environment, there is only relatively weak fairness, that is, ex ante PROP share and ex-post PROP share (the variants of PROP in a dynamic environment). Francis (2022) [71] proposed a deterministic algorithm with a piecewise uniform disutility function called the split rulership algorithm, which can return PROP and strategy-proof chore allocation. The algorithm allocates all the chores, and there is no overlap between the bundles, which is PO. Sanpui (2023) [37] proved that PROP allocation can require at least $n-1$ cuts and that at most n cuts are required to obtain PROP allocation when needed individually.

For indivisible chores, Caragiannis et al. (2012) [27] found that the price of PROP with utilitarian diswelfare is at most two for two agents, and the price of PROP with utilitarian diswelfare is at least n and at most n for the indivisible chore allocation problem of n agents. Bouveret et al. (2019) [40] analyzed the existence of PROP allocation based on different graph structures. This document discusses three graph structures: complete graphs, paths, and stars. For additive disutility, the PROP allocation problem on the complete graphs is NP-complete. For additive disutility, maximum disutility, and even binary disutility, the problem on the paths is NP-complete. Segal-Halevi et al. (2020) [72] assumed a preference order called diminishing differences (DD). According to this assumption, the complete characteristics of allocation that are necessary PROP or possibly PROP are given. Based on this feature, a polynomial-time algorithm, the balanced round-robin allocation algorithm, is designed, which can find the necessary DD-PROP allocation at any time. Höhne and Stee (2021) [41] used fair prices to express the social diswelfare of allocating losses. The results of this paper show that, for divisible and indivisible chores, their PROP prices with utilitarian diswelfare are n and their PROP prices with egalitarian diswelfare are 1. Mishra et al. (2022) [73] introduced PROP-E (n allocation $A\in \mathcal{A}$ satisfies PROP-E if, $\forall i\in N,d_i\left(A_i\right)⩽\frac{1}{n}{\sum }_{j\in N}{d}_i\left(A_j\right)$) for general valuations in the presence of full externalities and derived relations with existing PROP extensions.

5.2. Proportionality up to One Chore

The relaxed form of PROP, proportionality up to one chore (PROP1) was first proposed by Conitzer et al. (2017) [44]. This fairness relaxation weakens both EF1 and PROP.

Definition 18

([45]). An allocation $A\in \mathcal{A}$ satisfies proportionality up to one chore if, $\forall i\in N,d_i\left(A_i\right)⩽\frac{d_i\left(\mathcal{C}\right)}{n}$ or $d_i\left(A_i\right)+d_i\left(c\right)⩽\frac{d_i\left(\mathcal{C}\right)}{n},$ for some chore c $\in \mathcal{C}\backslash A_i$, or $d_i\left(A_i\right)-d_i\left(c\right)⩽\frac{d_i\left(\mathcal{C}\right)}{n},$ for some chore $c\in A_i$.

For the allocation of indivisible chores, Aziz et al. (2022b) [45] reduced EF1 to PROP1, found that there is a PROP1 and continuous allocation, and verified that, for the additive utility function, an EF1 allocation satisfies PROP1. The relationship within the above fairness is shown in Figure 4. This figure illustrates that an EF allocation satisfies EF1 and PROP, a PROP allocation satisfies PROP1, and an EF1 allocation satisfies PROP1.

Chen and Liu (2020) [56] found through Leximin solutions that, for three or four agents with additive valuation, there are always chore allocations of PROP1 and PO. Similar to the PROP price, Sun and Li (2022) [74] received the price of PROP1 with egalitarian of $\Theta \left(n\right)$, the price of PROP1 with utilitarian is $\frac{n}{2}$ for $n\ne 3$, and the price of PROP1 with utilitarian is 2 for $n=3$. Li et al. (2022a) [25] considered PROP1 allocation and proved that no algorithm is better than the n-approximation for the valuation of packing and job scheduling, and any allocation algorithm can achieve this tight approximation. The following provides an allocation that satisfies PROP1 but not PROP.

Example 2.

Consider the following example (similar to the example in Section 4.2): there are six indivisible chores and three agents with additive disutility.

	${\mathbf{c}}_{\mathbf{1}}$	${\mathbf{c}}_{\mathbf{2}}$	${\mathbf{c}}_{\mathbf{3}}$	${\mathbf{c}}_{\mathbf{4}}$	${\mathbf{c}}_{\mathbf{5}}$	${\mathbf{c}}_{\mathbf{6}}$
$a_1$	1	2	2	3	1	3
$a_2$	1	2	3	1	6	4
$a_3$	3	1	1	2	2	3

Assume that the allocation order of the algorithm is to allocate the chores to three agents in the order of increasing the number of chores, so agent 1 obtains chores 1 and 4, agent 2 obtains chores 2 and 5, and agent 3 obtains chores 3 and 6. This allocation scheme is called allocation A. It is verified that the allocation is PROP1, but not PROP. The disutility of agent 2’s bundle is greater than $\frac{d_2\left(\mathcal{C}\right)}{3}$. We can only make the disutility of agent 2 less than $\frac{d_2\left(\mathcal{C}\right)}{3}$ by removing chore 5 from its bundle.

For a general fair allocation problem, each agent has equal obligations. In real life, this is often not the case, as each agent will have different obligations due to their different social statuses. The weight in weighted-proportional up to one chore (weighted-PROP1) represents the obligation of each agent on the chores.

Definition 19

([66]). An allocation $A\in \mathcal{A}$ is weighted-proportional up to one chore if, for $\forall i,j\in N,$ ∃ an item $c\in A_i$, such that

$$d_i(A_i\backslash \left\{c\right\})⩽\frac{w_i}{{\sum }_{j=1}^n{w}_j}{d}_i\left(\mathcal{C}\right),$$

where each agent $i\in N$ has a weight $w_i>0$, and ${\sum }_{i\in N}{w}_i=1$.

Brânzei and Sandomirskiy (2023) [66] proved the existence of weighted-PROP1 allocation.

5.3. Proportionality up to Any Chore

Regarding the allocation of goods, Aziz et al. (2020) [75] pointed out that the existence of allocation proportionality up to any good cannot be guaranteed. For the fair allocation of chores, Moulin (2019) [15] first proposed the concept of proportionality up to any chore (PROPX).

Definition 20

([15]). An allocation $A\in \mathcal{A}$ satisfies proportionality up to any chore (PROPX) if, $\forall i\in N,d_i(A_i\backslash \left\{c\right\})⩽\frac{d_i\left(\mathcal{C}\right)}{n},\forall c\in A_i$.

Li et al. (2022b) [76] proved the existence of PROPX allocation for symmetric agents (the agents may have the same share for the chores) and verified that the allocation returned by the bid-and-take algorithm is weighted PROPX and two-approximate anyprice share fairness (APS; first introduced by Babaioff et al. [77] in 2021). They also found the tight approximation ratio of the optimal social cost constrained by PROPX. For the unweighted case, the tight bound of the price of PROPX is $\Theta \left(n\right)$. For the weighted and same-order case, the tight bound of the price of PROPX is $\Theta \left(m\right)$. For the weighted case, the price of PROPX is unbounded. For both symmetric and asymmetric agents (the agents may have different shares for the chores), the algorithm designed by Aziz et al. (2023) [78] returns an allocation of two-approximate (weighted) PROPX under ordinal preferences. In addition, they proved that PROPX and PO are not compatible in general.

To quantify the social diswelfare of PROP allocation loss, the concept of the price of PROP is applied. The fair prices with utilitarian diswelfare related to the PROP and relaxation forms of PROP are shown in

Table 2. The prices of PROP with utilitarian diswelfare (the IDO instance indicates that all agents have the same ordinal preference for the chores).

	PROP	PROP1	PROPX	Weighted-PROPX
Indivisible	2 for $n=2$	2 for $n=3$	$\Theta \left(n\right)$	$\Theta \left(m\right)$ (IDO)
	n for $n⩾3$	$n/2$ for $n\ne 3$		∞
	Caragiannis et al. [27]	Sun and Li [74]	Li et al. [76]	Li et al. [76]
Divisible	9/8 for $n=2$
	${(n+1)}^2/4n$ for $n⩾3$
	Caragiannis et al. [27]

. Because there are only a few results of PROP price with egalitarian diswelfare, they are not displayed here.

6. Equitability and Its Relaxations

In this section, we mainly introduce relevant research on equitability (EQ) and its relaxations in fair allocation. EQ can ensure that the overall level of fairness among all agents is consistent.

6.1. Equitability

EQ requires all agents to obtain the same value in the allocation. As a standard of interpersonal fairness, it also affects the choice and behavior of agents when facing one-shot distribution problems (Engelmann and Strobel (2004) [79]) and voluntary cooperative games (Fehr and Schmidt (1999) [80]). However, the goal of EQ is difficult to achieve in general cases.

Definition 21

([27]). An allocation $A\in \mathcal{A}$ is said to be equitable if, for $\forall i,j\in N$, we have $d_i\left(A_i\right)=d_j\left(A_j\right)$.

Caragiannis et al. (2012) [27] proved that, for divisible chores, the price of EQ for two agents is two and the price of EQ for n agents is n. For indivisible chores, the price of EQ is ∞. Heydrich and van Stee (2015) [26] observed that, under continuous allocation, the utilitarian of EQ is n and the egalitarian of EQ is one for divisible chores. Bei and Suksompong (2019) [81] studied approximate EQ allocation. Freeman et al. (2020) [82] proved that, for instances with identical disutilities, an allocation satisfies EF if and only if it satisfies EQ, and it is strongly NP-complete to determine whether a given fair allocation instance allows EQ allocation even for identical disutility. Bouveret et al. (2019) [40] analyzed the existence of EQ allocation of indivisible chores based on different graph structures. This paper discusses three graph structures: complete graphs, paths, and stars. For additive disutility, the EQ allocation problem on the complete graphs, paths, and stars is NP-complete. For maximum disutility and even binary disutility, the EQ allocation problem on the paths is NP-complete. For maximum disutility, the EQ allocation problem on the complete graphs and stars is P. Höhne and Stee (2021) [41] observed that, under continuous allocation, the price of EQ is ∞ for indivisible chores.

6.2. Equitable up to One Chore

In the context of EQ, chores can be similar to the definition of goods (Freeman et al. (2019) [83]). Equitability up to one chore (EQ1) requires the elimination of paired violations of equality by removing a chore from the bundle of less happy agents.

Definition 22

([82]). An allocation $A\in \mathcal{A}$ is said to be equitable up to one chore if, for $\forall i,j\in N$ such that $A_i\ne ⌀$, there exists a chore $c\in A_i$, such that $d_i(A_i\backslash \left\{c\right\})⩽d_j\left(A_j\right)$.

Freeman et al. (2020) [82] proved that, for instances with identical disutilities, an allocation satisfies EF1 if and only if it satisfies EQ1, and, for any chore instance with additive and integral disutilities, an allocation of EQ1 and PO always exists and can be computed in $O\left(ploy\right(m,n,|d_{min}\left|\right))$ time, where $d_{min}=mi{n}_{i,j}{d}_{i,j}$. They showed that no chore allocation is simultaneously EQ1, EF1, and PO. In addition, they adjusted the definition of EQ1 (duplicate a chore from an agent’s bundle to the bundle of its jealous agent to eliminate the envy relationship between the two agents), obtained DEQ1 (an allocation $A\in \mathcal{A}$ satisfies DEQ1 if, for $\forall i,j\in N$ such that $A_i\ne ⌀$, there exists a chore $c\in A_i$, such that $d_i\left(A_i\right)⩽d_j(A_j\cup \left\{c\right\})$), and verified the existence of DEQ1 allocation. Sun et al. (2023) [84] verified that the prices of EQ1 with respect to utilitarian and egalitarian diswelfare are both ∞. They proved that, when focusing on utilitarian diswelfare, the problems E(UW×EQ1) (which represents the problem of deciding whether there exists an EQ1 allocation that maximizes utilitarian diswelfare among all allocations) can be answered in time $O\left(m{V}^{2n+1}\right)$, and that the decision problem E(UW×EQ1) is P for two agents and is NP-complete for even three agents. The problem C(UW/EQ1) (which represents the problem of computing an EQ1 allocation that also maximizes utilitarian diswelfare among all EQ1 allocations) is NP-hard for even two agents is shown. When focusing on egalitarian diswelfare, the problem E(EW×EQ1) (which represents the problem of deciding whether there exists an EQ1 allocation that maximizes egalitarian diswelfare among all allocations) is NP-hard for even three agents and can be answered in time $O\left(m^{n+2}{V}^n\right)$ was proven. The following provides an allocation that satisfies EQ1 but not EQ.

Example 3.

Consider the following example, which is the same as the example in Section 5.2: there are six indivisible chores and three agents with additive disutility.

	${\mathbf{c}}_{\mathbf{1}}$	${\mathbf{c}}_{\mathbf{2}}$	${\mathbf{c}}_{\mathbf{3}}$	${\mathbf{c}}_{\mathbf{4}}$	${\mathbf{c}}_{\mathbf{5}}$	${\mathbf{c}}_{\mathbf{6}}$
$a_1$	1	2	2	3	1	3
$a_2$	1	2	3	1	6	4
$a_3$	3	1	1	2	2	3

Assume that the allocation order of the algorithm is to allocate the chores to three agents in the order of increasing number of chores, so agent 1 obtains chores 1 and 4, agent 2 obtains chores 2 and 5, and agent 3 obtains chores 3 and 6. This allocation scheme is called allocation A. It is verified that the allocation is EQ1, not EQ. Because the disutility of agent 2 is different from the other two agents, it does not meet the EQ. We can only make the allocation meet the conditions of EQ1 by removing chore 5 from agent 2’s bundle.

6.3. Equitable up to Any Chore

In the context of EQ, chores can be similar to the definition of goods (Freeman et al. (2019) [83]). Equitability up to any chore (EQX) requires the elimination of paired violations of equality by removing any chore from the bundle of less happy agents.

Definition 23

([82]). An allocation $A\in \mathcal{A}$ is said to be equitable up to any chore if, for $\forall i,j\in N$ such that $A_i\ne ⌀$ and for every chore $c\in A_i$, such that $d_i(A_i\backslash \left\{c\right\})⩽d_j\left(A_j\right)$.

Freeman et al. (2020) [82] proved that, for instances with identical valuations, an allocation satisfies EFX if and only if it satisfies EQX, and EQX allocation of chores always exists and can be calculated in polynomial time. They showed that, even for strictly negative and normalized disutilities, determining whether a given fair allocation instance admits an allocation that is EQX and PO is strongly NP-hard, and determining whether a given fair allocation instance admits an allocation that is simultaneously EQX+PO+EF/EF1/EFX is strongly NP-hard. In addition, they adjusted the definition of EQX (duplicate any chore from an agent’s bundle to the bundle of its jealous agent to eliminate the envy relationship between the two agents), obtained DEQX (an allocation $A\in \mathcal{A}$ satisfies DEQX if, for $\forall i,j\in N$ such that $A_i\ne ⌀$ and for every chore $c\in A_i$, such that $d_i\left(c\right)>0$, we have $d_i\left(A_i\right)⩽d_j(A_j\cup \left\{c\right\})$), and verified the existence of DEQX+PO allocation. Sun et al. (2023) [84] verified that the prices of EQX with respect to utilitarian and egalitarian diswelfare are both ∞. They proved that, when focusing on utilitarian diswelfare, the problems E(UW×EQX) can be answered in time $O\left(m{V}^{2n+1}\right)$, and the decision problem E(UW×EQX) is NP-complete even for two agents. The problem C(UW/EQX) is NP-hard even with two agents. When focusing on egalitarian diswelfare, the problem E(EW×EQX) is NP-hard even for two agents and can be answered in time $O\left(m^{n+2}{V}^n\right)$.

To quantify efficiency loss, the concept of the price of fairness is applied. The fair prices related to EQ are shown in

Table 3. The fair prices of equitability.

	Price of	Utilitarian	Egalitarian
Divisible	EQ	n	1
		Heydrich and van Stee (2015) [26]	Heydrich and van Stee (2015) [26]
	EQ1	∞	∞
		Sun et al. (2023) [84]	Sun et al. (2023) [84]
	EQX	∞	∞
		Sun et al. (2023) [84]	Sun et al. (2023) [84]
Indivisible	EQ	∞	∞
		Höhne and Stee (2021) [41]	Höhne and Stee (2021) [41]
	EQ1	∞	∞
		Sun et al. (2023) [84]	Sun et al. (2023) [84]
	EQX	∞	∞
		Sun et al. (2023) [84]	Sun et al. (2023) [84]

.

7. Maximin Share Fairness and Its Variants

In this section, we mainly introduce relevant research on maximin share (MMS) fairness and its variants in fair allocation. MMS fairness can ensure the best utility of the agent. It is an important concept of fairness in the field of economics.

7.1. Maximin Share Fairness

The MMS of an agent is the best utility that the agent can guarantee. If the agent has the opportunity to divide all items into n bundles, it can only be allocated to the bundle finally, that is, it receives the most unpopular bundle, which is proposed by Budish (2011) [85].

Definition 24

([86]). The maximin share fairness of agent i ($MM{S}_i$) is

$$MM{S}_i=\underset{(A_1,A_2,\cdots ,A_n)\in \Pi \left(C\right)}{min}\underset{j\in N}{max}{d}_i\left(A_j\right),$$

where $\Pi \left(C\right)$ represents the set of all allocations of C.

Definition 25

([86]). An allocation $A\in \mathcal{A}$ is called an α-approximate maximin share fairness (α-MMS) allocation if there are $d_i\left(A_i\right)⩽\alpha ·MM{S}_i$ for each agent $i\in N$.

MMS mainly targets indivisible chores. Some researchers have discussed the existence of MMS allocation. Aziz et al. (2017) [86] proved that it is NP-hard to calculate the MMS allocation of chores. A new concept, the optimal MMS of chores, is introduced. If the allocation represents the best possible approximation of the MMS guarantee, then the allocation is the optimal MMS allocation. The optimal MMS allocation has two ideal properties: it always exists, and an optimal MMS allocation is always an MMS allocation if the latter exists. In addition, a polynomial-time greedy round-robin algorithm is designed, which provides a two-approximate MMS guarantee for chores, and is combined with parallel machine scheduling to design an algorithm, which gives the polynomial-time approximation schemes (PTAS) for the optimal MMS when the number of agents is fixed. Searns (2020) [87] proved that, for every $n⩾4$, there exists an instance with $O\left(n^2\right)$ chores where every optimal-MMS allocation guarantees at most 3 (4 if n is odd) agents their MMS value. Barman et al. (2023) [52] proved that, for binary supermodular cost functions, MMS allocations always exist, and proved that EF1 and MMS are incompatible. Hummel (2023) [88] proved that MMS allocation exists for all instances with $n⩾n_c$ agents and no more than $n+c$ chores, where $n_c⩽\lfloor {0.7838}^c(c!)\rfloor$, $\forall c\in {\mathbb{N}}^{+}$.

Some papers also study the approximation ratio. Barman and Krishnamurthy (2020) [89] proved that, when the agent has an additive disuility, it can effectively calculate the $\frac{4}{3}$-approximate MMS allocation, which improves Aziz’s results. Sun et al. (2020) [90] discussed the case of multidimensional task costs. They improved the famous round-robin algorithm and proved that the approximate ratio of the MMS algorithm is $2+\frac{m·{\alpha }_i(1+n)-n}{n^2}$, where ${\alpha }_i=1-{\beta }_i$ and ${\beta }_i$ is a parameter related to the disutility weight of agent i, and the time complexity of the algorithm is $O(mlogm)$. Feige et al. (2021) [91] proved that, for the allocation of three agents and nine chores, the value of at least one agent will not be less than $\frac{44}{43}$ of his MMS value, that is, the MMS gap of the case is $\frac{1}{43}$. Huang and Lu (2021) [92] designed an algorithm framework based on the famous first-fit decreasing algorithm of the packing problem and proved that there is always an $\frac{11}{9}$-approximate MMS allocation for any instance. According to existing results, an efficient polynomial-time algorithm for MMS allocation with $\frac{5}{4}$-approximation was further proposed. In addition, a polynomial time $O(mlogm+n)$ algorithm was designed for the job scheduling problem, and the optimal scheduling scheme of $\frac{11}{9}$-approximate was obtained. Under cardinality constraints, Hummel and Hetland (2022) [93] proved that there is a 2-approximate MMS allocation in general and that there is a $\frac{3}{2}$-approximate MMS allocation in single-category instances. Feige and Norkin (2022) [94] considered the problem of approximate MMS allocation between three agents with additive disutility and proved that there is always a $\frac{19}{18}$-approximate MMS allocation. Aziz et al. (2022c) [95] analyzed it from the perspective of algorithm and mechanism design. Under the constraint of ordinal preference, by using the round-robin algorithm, it was calculated that $\frac{4}{3}$-approximate MMS allocation exists when $n=2$, $\frac{7}{5}$-approximate MMS allocation when $n=3$, and $\frac{5}{3}$-approximate MMS allocation when $n>3$. They also considered the situation of strategy-proof, provided a strategy-proof $O(log\left(\frac{m}{n}\right))$-approximate continuous picking algorithm, and then improved the approximate ratio to $O\left(\sqrt{logn}\right)$ through a random algorithm. Huang and Segal-Halevi (2023) [96] developed a fully polynomial-time approximation scheme (FPTAS) using a binary search. By using two techniques, heterogeneous first-fit decreasing and binary search, they discovered the allocation of $\frac{15}{13}$-maximin-share in polynomial time $O\left(n^{2}mlog\left(V_{max}\right)\right)$ when $n=3$ and $(\frac{13}{11}+ϵ)$-maximin-share in polynomial time $O\left(\frac{1}{ϵ}{n}^{2}mlog\left(V_{max}\right)\right)$ when $n⩾2$, where $V_{max}$ is the maximum disutility of an agent to all chores.

In addition, the social diswelfare loss of MMS allocation, the algorithm to achieve fairness and efficiency, and the MMS allocation on the graph structure have been discussed. Sun and Li (2022) [74] found that the price of MMS with egalitarian is $\Theta \left(n\right)$ and that the price of MMS with utilitarian is $\frac{n}{2}$. The previously considered task cost is one-dimensional. Kulkarni (2022) [97] designed a PTAS for finding $\alpha$-MMS+PO allocation when the number of agents is a constant, where $\alpha >0$. Xiao et al. (2023) [98] paid attention to the MMS allocation problem on trees and cycles. Figure 5 shows an instance of seven chores on a tree, where an agent’s MMS partition divides the tree into three bundles. They combined the group-satisfied method and the matching technology in graph theory to prove that there is MMS allocation on trees with depth at most three and spiders, and used the linear programming method to find the $\frac{7}{6}$-MMS allocation on the cycle in polynomial time for instances with three agents, proving that $\alpha$-MMS allocation does not exist for any $\alpha <\frac{7}{6}$.

7.2. The Variant of Maximin Share Fairness

For asymmetric agents, weighted maximin share (WMMS) appears in the research. There is a similar concept for the fair allocation of goods (Farhadi (2019) [99]).

Definition 26

([100]). For every agent $i\in N$, the weighted maximin share value of i is defined as

$$WMM{S}_i=\underset{(A_1,A_2,\cdots ,A_n)\in \Pi \left(C\right)}{min}\underset{j\in N}{max}{d}_i\left(A_j\right)\frac{w_i}{w_j},$$

where $w_i\in (0,1]$ is the weight of agent i to chores. The weights add up to 1, i.e., ${\sum }_{i\in N}{w}_i=1.$

Note that, when each agent has the same share, then WMMS is MMS. Because there is no precise WMMS allocation, it is natural for its relaxed form optimal weighted maximin share (OWMMS) to emerge.

Definition 27

([100]). For every agent $i\in N$, the optimal weighted maximin share value of i is defined as

$$OWMM{S}_i={\alpha }^{*}WMM{S}_i,$$

where ${\alpha }^{*}$ is the OWMMS ratio, that is, the minimal $\alpha \in [1,\infty )$ for which an α-WMMS allocation always exists.

Aziz et al. (2019b) [100] were concerned about the fair allocation of asymmetric agents, who have no right to allocate but have a relative share. If the agent’s share is higher, it will be allocated to higher chores. In addition, two extensions of MMS–WMMS and OWMS are introduced. It was also verified that there is an approximation ratio of at least $\frac{4}{3}$ for any WMMS fairness algorithm. For general settings, it designs a polynomial time-constant approximation algorithm to obtain a $(4+ϵ)$-approximate OWMS allocation. For the case of two agents, the WMMS allocation obtained by using the divide-and-choose style algorithm is $\frac{3}{2}$-approximate, and, when the disutility function for agents is binary, the WMMS allocation always exists and can be found in polynomial time.

PMMS is similar to the maximin share and differs from MMS because each agent divides its combined bundle with any other agent into two bundles, and the agent chooses the bundle with the highest cost inside.

Definition 28

([46]). An allocation $A\in \mathcal{A}$ is pairwise maximin share (PMMS), if for $\forall i,j\in N,$

$$d_i\left(A_i\right)⩽\underset{B_1,B_2\in {\Pi }_2(A_i\cup A_j)}{min}max\{d_i\left(B_1\right),d_i\left(B_2\right)\},$$

where ${\Pi }_k\left(C\right)$ is the set of all k-partitions of C.

Sun et al. (2021a) [46] introduced the promotion form of MMS, PMMS. When $n=2$, the price of PMMS with utilitarian diswelfare is 2, the price of 2-MMS with utilitarian diswelfare is 1, and the price of $\frac{3}{2}$-PMMS with utilitarian diswelfare is $\frac{7}{6}$. When $n>2$, the price of PMMS and $\frac{3}{2}$-PMMS is unbounded, and the price of 2-MMS is $\Theta \left(n\right)$. Sun et al. (2021b) [101] further generalized the results of Sun et al. (2021a) [46]. For the case where the disutility function is a submodule function, when $n=2$, the price of PMMS is 3, the price of 2-MMS is 1, and the price of $\frac{3}{2}$-PMMS is $\left[\frac{4}{3},\frac{8}{3}\right)$. When $n>2$, the price of PMMS and $\frac{3}{2}$-PMMS is unbounded, and the price of 2-MMS is $\left[\frac{n+3}{6},\frac{n^2}{2}\right)$, where interval $[a,b)$ means that the lower bound is equal to a and the upper bound is less than b.

To quantify the social diswelfare of MMS allocation loss, the concept of the price of MMS is applied. The fair prices with utilitarian diswelfare related to the MMS and variant forms of MMS (Sun et al. (2021a) [46]) are shown in

Table 4. The prices of MMS with utilitarian diswelfare.

	PMMS	$\frac{3}{2}$-PMMS	2-MMS
Additive	2 for $n=2$	7/6 for $n=2$	1 for $n=2$
	∞ for $n⩾3$	∞ for $n⩾3$	$\left[\frac{n+3}{6},n\right)$ for $n⩾3$
Submodular	3 for $n=2$	$\left[\frac{4}{3},\frac{8}{3}\right)$ for $n=2$	1 for $n=2$
	∞ for $n⩾3$	∞ for $n⩾3$	$\left[\frac{n+3}{6},\frac{n^2}{2}\right)$ for $n⩾3$

.

The definition of 1-out-of-k maximum share is similar to that of the MMS, except that the MMS can only be divided into n bundles, which can be divided into k (⩽n) bundles.

Definition 29

([102]). For every agent $i\in N$, the 1-out-of-k maximin share value $MM{S}_i^k\left(\mathcal{C}\right)$ of i on $\mathcal{C}$ is defined as

$$MM{S}_i^k\left(\mathcal{C}\right)=\underset{(A_1,A_2,\cdots ,A_k)\in {\Pi }_k\left(\mathcal{C}\right)}{min}\underset{j\in \left[k\right]}{max}{d}_i\left(A_j\right)$$

where ${\Pi }_k\left(\mathcal{C}\right)$ is the set of all k-partitions of $\mathcal{C}$, $k⩽n$ is an integer, and $\left[k\right]=1,2,\cdots ,k$.

Aigner-Horev and Segal-Halevi (2022) [102] proved the existence of 1-out-of-$\lfloor \frac{2n}{3}\rfloor$ MMS allocation, but they needed to calculate the specific value of MMS. Therefore, this was definitely not polynomial time. Hosseini et al. (2022) [103] considered the extension of a new 1-out-of-d MMS. The polynomial-time algorithm of 1-out-of-$\lfloor \frac{2n}{3}\rfloor$ MMS was proposed, and the existence of 1-out-of-$\lfloor \frac{3n}{4}\rfloor$ MMS allocation was proven.

For any disutility, the anyprice share (APS) is always at least the pessimistic share. This concept of fairness was first proposed by Babaioff et al. [77] in 2021.

Definition 30

([77]). The anyprice share fairness of agent i ($AP{S}_i$) is

$$AP{S}_i=\underset{(A_1,A_2,\cdots ,A_n)\in \Pi \left(C\right)}{max}\underset{j\in N}{min}{d}_i\left(A_j\right),$$

where $\Pi \left(C\right)$ represents the set of all allocations of C.

Feige and Huang (2022) [104] introduced the concept of chore share and the strategic preliminary stage of the picking sequence, and explained its use to enhance picking sequences with strong ex-post sharing guarantees, thus making them also have ex ante EF guarantees. In addition, they also demonstrated that, when indivisible chores are allocated to agents with additive disutility and arbitrary entitlements, each agent receives a bundle of up to 1.733 times the disvalue of APS. Li et al. (2022) [76] proved that APS allocation can be as bad as $\Theta \left(n\right)$-approximation regarding PROPX.

The latest results for MMS, WMMS, and OWMMS are shown in

Table 5. The latest results about MMS.

	MMS
	Lower	Upper
Ordinal	4/3 for $n=2$	15/13 for $n=3$
	7/5 for $n=3$	$(13/11)+ϵ$ for $n⩾2$
	Aziz et al. (2022c) [95]	Huang and Segal-Halevi (2023) [96]
Cardinal	44/43
	Feige et al. (2021) [91]
	WMMS	OWMMS
	$4+ϵ$ for any agents	3/2 for $n=2$
	Aziz et al. (2019b) [100]	Aziz et al. (2019b) [100]

.

Open problem 2.

Is there any other type of disutility function to ensure the existence of MMS?

8. Others

In this section, we mainly introduce relevant research that focuses on relatively few fairness criteria, including competitive equilibrium (CE), maximum Nash social diswelfare (MNDW), and the Fisher market.

8.1. Competitive Equilibrium

For a century, the theory of CE was one of the most basic concepts in mathematical economics. In this field, researchers have studied resource pricing and allocation to agents based on the interaction between demand and supply. The economic theory of general equilibrium originated from the ideas of Walras (1954) [105]. Allocation based on CE has become one of the best mechanisms to solve this problem because of its significant fairness and efficiency guarantee (Varian (1974) [106]). The existence and calculation of CE have been widely studied in several economic models (e.g., the Arrow–Debreu model, Jain (2007) [107], and the Fisher model [Walras (1954) [105]).

In the instance of chore allocation, each agent i brings $w_{ij}$ units of chore j to be performed. Given prices $p=\{p_1,p_2,\cdots ,p_m\}\in {\mathbb{R}}_{⩾0}^m$ for chores, where $p_j$ is the payment for performing a unit amount of chore j, agent i needs to earn ${\sum }_{j\in \mathcal{C}}{w}_{ij}{p}_j$ in order to pay to complete her own chores. Let $O{B}_i\left(p\right)=argmi{n}_{A_i\in {\mathbb{R}}_{⩾0}^m:<A_i,p>⩾<w_i,p>}\left\{{\sum }_{j\in \mathcal{C}}{d}_{ij}{A}_{ij}\right\}$ be the optimal bundle of agent i, where agent i is assigned a bundle $A_i=(A_{i1},A_{i2},\cdots ,A_{im})$ under feasible allocation $A\in \mathcal{A}$.

Definition 31

([106]). The price vector p is said to be a competitive equilibrium (CE) if all chores are completely assigned when every agent obtains one of her optimal bundles, that is, $A_i\in O{B}_i\left(p\right),\forall i\in N$, and ${\sum }_{i\in N}{A}_{ij}={\sum }_{i\in N}{w}_{ij},\forall j\in \mathcal{C}$.

The CE of chores is more challenging. Contrary to the case of goods, even in the (most general) exchange model, CE sets are convex. In the CE with equal income (CEEI) model, CE sets with chores can be nonconvex sets containing many disconnected sets (Bogomolnaia et al. (2017) [108]). Bogomolnaia et al. (2019) [35] compared the egalitarian equivalent and CEEI to divide bads. They were both welfarist. Chaudhury et al. (2020) [109] proved that it is strongly NP-hard to determine whether there is a competitive allocation (no agent is assigned to a chore that they dislike), and finding a competitive allocation is PPAD-hard (PPAD is polynomial parity arguments on directed graphs). Segal-Halevi (2020b) [110] proved that goods allocation and chores allocation are equivalent for two agents. This means that the positive and negative results of the allocation of goods between the two agents also apply to chores. If there are three or more agents, a CE for almost all incomes may not have any amount of chores. Boodaghians et al. (2022) [111] presented a $\mathcal{O}(n^6{m}^3/{ϵ}^2)$ time-exterior point algorithm for determining an $(1-ϵ)$-approximate CE in the CEEI model. Chaudhury et al. (2022a) [49] gave the first combinatorial algorithm for determining a $(1-ϵ)$-approximate CE in the CEEI model. In addition, they also showed that finding a $(1-1/ploy(n\left)\right)$-approximate CE in the exchange model under sufficient conditions is PPAD-hard. Chaudhury et al. (2022b) [112] analyzed the existence of CE in the exchange model, where the agent may have infinite disutility for some chores, and showed that it is NP-hard to determine the existence in both exchange and CEEI. Brânzei and Sandomirskiy (2023) [66] proved that all the results of the competitive rule of chores can be calculated in strongly polynomial time if the number of agents or the number of chores is fixed.

8.2. Maximum Nash Social Diswelfare

Consider a classic bargaining game where two agents 1 and 2 decide what movie to watch. Agent 1 likes movie A the most and does not like movie B. In contrast, Agent 2 likes movie B instead of movie A. When there is only one decision that can be made, it is necessary to obtain a mutually agreed solution from both agents. Nash (1950) [113] proposed the concept of Nash social welfare, which is the product of maximizing agent utility. It is considered a unique solution that satisfies certain attractive properties. Nash social welfare is a measure used to balance two objectives. The solution of maximizing Nash welfare (MNW) among all possible allocations is called the Nash optimal (Caragiannis et al. (2019) [114]). The problem of maximizing Nash welfare is NP-hard, even for two agents with identical additive valuations (Lee (2017) [115]). To distinguish from goods, this paper uses Nash social diswelfare as a representation. Formally, the definition of maximum Nash social diswelfare (MNDW) is as follows.

Definition 32

([44]). The Nash diswelfare of an allocation A is the product of disutilities to all agents under A: $NDW\left(A\right)={\prod }_{i\in N}{d}_i\left(A_i\right)$.

Bogomolnaia et al. (2017) [108] showed that the conditions of an exact CE hold if and only if the disutility profile is a critical point for the Nash social diswelfare on the boundary of the feasible region. Aleksandrov (2018) [24] proved that the allocation of MNDW is an EFX and PO allocation with identical disutility similar to good and MNW. To minimize Nash social diswelfare, its allocation is guaranteed to be PE. When dividing bads, Bogomolnaia et al. (2019) [35] used the competitive rule to select all critical points of their Nash social diswelfare among effective and feasible profiles of disutility. Aziz and Rey (2019) [61] believe that Nash social diswelfare is not applicable to the fair allocation of chores. Maximizing or minimizing Nash social diswelfare does not necessarily mean EF1 when only considering chores. Garg et al. (2020) [116] extended the problem of approximating maximum Nash social diswelfare to more general settings. They mainly designed two approximation algorithms for asymmetric agents under additive disutility and submodular disutility. Boodaghians et al. (2022) [111] used Nash social diswelfare to depict the numerical changes when searching for KKT points (the strictly positive local-minima of a nonconvex formulation). Chaudhury et al. (2022) [49] proved that the Nash diswelfare of the allocation can be improved by some multiplication factors at the end of each iteration.

When only considering the allocation of goods, Darmann and Schauer (2015) [117] proposed the Nash flow algorithm. When utility is binary, it calculates the allocation of maximizing Nash social welfare in polynomial time.

Open problem 3.

Can an algorithm be designed to calculate the allocation of approximate maximum Nash social diswelfare when considering only allocating chores?

8.3. The Fisher Market

The concept of CE, also known as market or Walrasian equilibrium, is an important economic concept. It simulates the allocation of resources in a stable economic state when supply equals demand. Walras (1954) [105] believed that the market is called the Fisher market in the computer science literature. The Fisher market of chores is an economic model that consists of a set of divisible chores and a set of agents, each of whom is given a budget of virtual money (Brainard and Scarf (2005) [118]). Formally, a Fisher market is given by adding a vector of endowments or budgets to the original fair allocation problem. Correspondingly, a market should not only output an allocation but also output a price vector. Varian (1974) [106] proved that a Fisher market equilibrium allocation exists and is EF+PO. A large number of studies have studied the properties of the Fisher market and found algorithms for calculating equilibrium and hardness results (e.g., Eisenberg and Gale (1959) [119]).

Definition 33

([118]). In the setup of the Fisher market, in addition to the agent set N, chores set $\mathcal{C}$, and disutility function profile $\mathcal{D}$, each agent also has an initial liability $l_i>0$, which represents how much money the agent needs to earn in the market. The Fisher market is defined as $F=<N,\mathcal{C},\mathcal{D},\mathcal{L}>$, where $\mathcal{L}=(l_1,l_2,\cdots ,l_n)$.

Given the Fisher market instance F, the market outcome is a pair of fractional allocation and payment vectors $<x,p>$. For all agents $i\in N$ and chore $c\in \mathcal{C}$, $x_{i,c}$ represents which fraction of chore c is assigned to agent i, and $p_c$ represents the price of chore c. The income obtained by agent i from market outcome $<x,p>$ is $p\left(x_i\right)={\sum }_{c\in \mathcal{C}}{x}_{i,c}{p}_c$. We can also consider the integral bundles as a vector with 0 and 1 entries. Given the payment vector p, the pain of agent i for every buck of chores c is $d_i\left(c\right)/p_c$. We use $MP{B}_i$ to represent the minimum pain per buck for agent i when paying p, i.e., $MP{B}_i={min}_{c\in \mathcal{C}}{d}_i\left(c\right)/p_c$.

Bogomolnaia et al. (2017) [108] defined the competitive rules of chores, considered the Fisher market simulation of chores, and analyzed their properties. Even in the case of additional disutility, the competitive rules of chores are no longer single-valued. The equilibrium allocation forms a disconnected set and can be obtained as the critical point of Nash social diswelfare on the Pareto frontier of the feasible disutility set. Barman et al. (2019) [120] studied the Fisher market that allows for integral equilibrium. Freeman et al. (2020) [82] provided proof of the well-known first diswelfare theorem for Fisher markets of chores (for a Fisher market with linear disutilities, any equilibrium outcome is fPO). Boodaghians et al. (2022) [111] designed an FPTAS for the Fisher market. Ebadian et al. (2022) [48] obtained an EF1+PO allocation of chores with bivalued disutilities by using the framework of Fisher markets and CE. Chaudhury et al. (2022a) [49] proved that the problem of finding CE in the Fisher model is in polynomial local search (PLS). Chaudhury et al. (2022b) [112] showed that determining whether an instance of chore division in the Fisher model admits a CE is strongly NP-hard, even for the case of equal incomes (CEEI). This also holds for the constant-approximate CE. Brânzei and Sandomirskiy (2023) [66] constructed a Fisher market framework for allocating chores. The difference between this framework and that for allocating goods is that all the prices and budgets are negative. In addition, they stated that, when either the number of agents or the number of chores is bounded, all the outcomes of the competitive rule are a computationally tractable problem. Hosseini et al. (2023) [64] used two variants of the Fisher market algorithm to find the PO allocation in polynomial time for instances where chores are limited to two types.

Definition 34

([53]). Given a Fisher market instance F, the outcome of the Fisher market $<x,p>$ is Fisher market equilibrium if ${\sum }_{i\in N}{x}_{i,c}=1$, for all chores $c\in \mathcal{C}$, ${\sum }_{c\in \mathcal{C}}{x}_{i,c}·p_c=l_i$, for all agents $i\in N$, and if $x_{i,c}>0$, then $MP{B}_i=d_i\left(c\right)/p_c$, for all agents $i\in N$ and chores $c\in \mathcal{C}$.

If $l_i=1$, for all agents $i\in N$, then the Fisher market equilibrium is CE. Akrami et al. (2023) [53] proved that, for additive disutility instances, any Fisher market equilibrium is fPO.

Open problem 4.

What is the relationship between Fisher market equilibrium and other concepts of fairness?

9. Conclusions

In this paper, we conduct a comprehensive investigation into the fair allocation problem of chores. We divide the fair allocation problem of chores into the following aspects: EF, PROP, EQ, MMS fairness, CE, MNDW, Fisher market, etc. We have summarized the results of various algorithms under different fairness concepts from the perspectives of divisible and indivisible chores. According to different definitions, some concepts of fairness can be used in the allocation of divisible and indivisible chores, while others can only be used in the allocation of indivisible chores, as shown in Figure 6, where the arrow points to fair relaxation, for example, EF and its relaxed form. EF can be used in the allocation of divisible and indivisible chores, while EF1 and EFX can only be used in the allocation of indivisible chores. The purpose of our research is to provide a valuable reference for researchers and engineers working on practical problems.

Overall, this survey provides a comprehensive overview of the latest methods for the fair allocation of chores and emphasizes the need for further research in this field. In addition to the above research, research on the fair allocation of chores can also introduce different constraints by combining more life examples and exploring more concepts of fairness. In addition, we summarize three future research directions in this field: (1) For instances with a fixed number of agents, the runtime complexity of the algorithm can be further improved; (2) To achieve approximate maximum utilitarian diswelfare and egalitarian diswelfare, faster algorithms for restricted domains can be designed; (3) Combined with the concept of fairness, research on allocation mechanisms can be considered.