Fair and Efficient Chore Allocation: Existence and Computation

1 Introduction

The question of fairly allocating a set of indivisible items to agents with additive preferences has been widely studied across various disciplines such as computer science, AI, economics, and social choice. Among various definitions of fairness, the central one is envy-freeness (EF) [Foley, 1967]. An allocation is EF if every agent prefers the items allocated to her at least as much as those allocated to any other agent. The simple example of allocating one indivisible task among two agents shows that EF allocations need not exist, implying the need for relaxations of EF in the discrete setting. Envy-freeness up to one item (EF1) is one such popular relaxation. Unlike EF, EF1 allocations are known to always exist and are efficiently computable [Lipton et al., 2004; Bhaskar et al., 2020].

Pareto-optimality (PO) is a classic notion of economic efficiency, whereby an allocation is considered PO if there is no allocation in which no agent is worse off while at least one agent is strictly better off. While fairness is desirable, a fair allocation can have poor overall efficiency. Thus, obtaining allocations that achieve fairness in conjunction with efficiency is the ideal goal. Indeed, the existence of allocations that are both EF1 and PO is an important problem in discrete fair division. Note that merely checking if an allocation is PO is coNP-hard [de Keijzer et al., 2009], highlighting the challenge of this problem.

EF1 andPOfor goods. For goods (items that provide value to agents), [Caragiannis et al., 2016] showed that an EF1 and PO allocation always exists: they showed that the allocation with the maximum Nash welfare, i.e., the geometric mean of the utilities of the agents, is both EF1 and PO. However, their result does not lead to fast computation, since the Nash welfare is NP-hard to compute, even approximately [Lee, 2015]. [Barman et al., 2018] and later [Garg and Murhekar, 2021] used another approach of using competitive equilibria (CE) to design pseudo-polynomial time algorithms for computing an EF1 and PO allocation of goods. In a CE allocation, agents have a fictitious amount of money, goods are assigned prices, and each agent is only allocated goods that have the maximum value to price ratio. The latter property ensures that the allocation is fractionally PO (fPO), which is an efficiency property stronger than PO.

EF1 and PO for chores. In contrast to goods, the problem is significantly harder for chores (items that impose a cost to agents). Indeed, the existence of an EF1 and PO allocation of chores is a major open question, let alone its computation.

Formally, an instance of the problem for chores is a tuple (N,M,D), where N = [n] is a set of n agents, M = [m] is a set of m indivisible chores, and D = {di}i∈N is a list with di : 2M → R≥0 denoting agent i's disutility function over the chores. Let di(j) denote the disutility of chore j for agent i. Since disutility functions are additive, we have di(S) = ∑j∈S di(j) for every i ∈ N and S ⊆ M. An allocation x = (x1, x2, . . . , xn) is a partition of the chores into n bundles, where agent i receives bundle xi ⊆ M and gets disutility di(xi). An allocation x is said to be:

• EF1 if for all i, h ∈ N, ∃j ∈ xi s.t. di(xi \ {j}) ≤ di(xh).
• PO if there is no allocation y that dominates x. An allocation y dominates an allocation x if for all i ∈ N, di(yi) ≤ di(xi), and there exists h ∈ N such that dh(yh) < dh(xh).

Main Question. Does every chore allocation instance (N,M,D) admit an allocation that is both EF1 and PO?

Preliminary approaches of extending techniques from goods to chores reveal that the settings of goods and chores are only superficially similar. First, it is unknown whether a welfare function like Nash welfare which ensures EF1 and PO exists for chores. Second, it is not known whether the CE approach terminates for all instances. This motivates us to consider instances with special structure, which can potentially point us to the 'source of hardness' for this problem.

2 Contributions

We show that an EF1 and PO allocation of chores exists and can be computed in polynomial time for:

1. Bivalued instances [Garg et al., 2022]. In a bivalued instance, there exists a, b ∈ R≥0 s.t. di(j) ∈ {a, b} for all i ∈ N, j ∈M.
2. Three agents [Garg et al., 2023]. Note each agent can have a different disutlity function.
3. Three types of agents [Garg et al., 2024], where agents of the same type have the same disutility function.
4. Two types of chores [Garg et al., 2024; Aziz et al., 2023].

Techniques. We design algorithms which use the CE framework. In a CE of chores, agents aim to earn a money by doing chores in exchange for payment. Each agent is only assigned chores that minimize the disutility to payment ratio, which ensures the allocation is fPO and hence PO. Our algorithms move in the space of PO allocations by maintaining a CE allocation. To obtain EF1, we perform chore transfers from one agent to another while performing chore payment updates (either payment raises or drops) to maintain a competitive allocation. These steps are carefully designed depending on the specific structured instance in consideration. Likewise, the potential function arguments developed to prove the termination of our algorithms are involved and invoke the specialized structure of the instance.

3 Future Directions

In light of our results, the following are important questions for future investigation.

1. The existence of EF1 and PO allocations for n = 4 agents. The algorithm for n = 3 agents has the property that one agent i only loses chores in the course of the algorithm. This property is crucial, and it is unclear if such a property can be maintained for n = 4 agents.
2. The existence of EF1 and PO allocations for 2-ary instances, where di(j) ∈ {ai, bi}. This class generalizes bivalued instances.
3. The existence of an allocation that is approximately EFk and PO, i.e., α-EFk+PO, for α ≥ 1. In an α-EFk allocation, no agent envies another up to a factor of α after removing k chores. To the best of our knowledge, no results are known for any constants α, k.
4. The (non-)existence of weighted EF1 (wEF1) and PO allocations in the case of asymmetric agents with entitlements. Our recent work [Garg et al., 2024] shows that a wEF1 and PO allocation exists and can be computed for structured instances.