Approximately EFX and fPO Allocations for Bivalued Chores

1 Introduction

Fair allocation has received significant attention over the past few decades in the fields of computer science, economics, and mathematics. The problem focuses on allocating a set M of m items among a group N of n agents, where agents have heterogeneous valuation functions for the items. When the valuation functions assign positive values, the items are considered as goods, such as resources; when the valuation functions assign negative values, the items are regarded as chores, such as tasks. The goal is to compute an allocation of the items that is fair to all agents. In this work, we focus on the allocation of chores, where each agent has an additive cost function that assigns a non-negative cost to every item, and explore the existence of allocations that are fair and efficient.

Envy-freeness (EF) is one of the most well-studied fairness notions. An allocation is envy-free if no agent wants to exchange her bundle of items with any other agent. Unfortunately, envy-free allocations are not guaranteed to exist for indivisible items. Consequently, researchers have focused on the relaxations of envy-freeness. Envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two widely studied relaxations. Generally speaking, EF1 allocations require that the envy between any two agents can be eliminated by removing some item, while EFX allocations require that the envy can be eliminated by removing any item. In addition to fairness, efficiency is another important measure of the quality of allocations. The existence of fair and efficient allocations has recently drawn significant attention. Unfortunately, efficiency and fairness often compete with each other, and many fair allocations exhibit poor efficiency guarantees. Pareto optimality (PO) is one of the most widely used measures for efficiency. An allocation is called PO if no other allocation can improve the outcome for one agent without making another agent worse off. A stronger notion called fractional Pareto optimality (fPO) requires that no other fractional allocation can improve the outcome without making someone else worse off. Note that any fPO allocation also satisfies PO but not vice-versa.

∗The authors are ordered alphabetically.

It has been shown that EF1 allocations always exist for goods [Lipton et al., 2004], chores, and the mixture of goods and chores [Aziz et al., 2022a; Bhaskar et al., 2021]. There are several simple polynomial-time algorithms for computing EF1 allocations such as envy-cycle elimination and roundrobin [Lipton et al., 2004; Bhaskar et al., 2021]. Compared to the well-established results for EF1 allocations, the existence of EFX allocations remains a major open problem. For general cost functions, the divide-and-choose algorithm can be applied to compute EFX allocations when n = 2. However, it is still unknown whether EFX allocations exist for chore instances with more than two agents. So far, EFX allocations for chores are shown to exist for two types of chore [Aziz et al., 2023], the case of m ≤ 2n [Garg et al., 2024; Kobayashi et al., 2023], and agents with leveled preferences [Gafni et al., 2023]. Aziz et al. [2024] show that EFX allocations can be computed for identical ordering (IDO) instances, which is extended by Kobayashi et al. [2023] to the case when the cost functions of all but one agent are IDO. For bi-valued instances (where the cost of any item to any agent can only take one of two fixed values), Zhou and Wu [2024] propose a polynomial-time algorithm that computes EFX allocations for three agents. The result is generalized by Kobayashi et al. [2023] to the case of three agents with personalized bi-valued cost functions and improved by Garg et al. [2023], who show the existence of EFX and fPO allocations for three bi-valued agents.

Given the challenges in computing EFX allocations, many studies focus on the approximations of EFX allocations. Zhou and Wu [2024] demonstrate the existence of a polynomial-time algorithm that computes (2 + √6)- approximate EFX ((2 + √6)-EFX) allocations for three agents. Recently, Afshinmehr et al. [2024] and Christoforidis et al. [2024] improve this result, showing that 2-EFX allocations can be computed in polynomial time for three agents. For a general number of agents, the state-of-the-art results are by Garg et al. [2024], who show the existence of 4-EFX allocations for general additive instances, and 3-EFX and fPO allocations for bi-valued instances.

1.1 Our Results and Techniques

In this work, we consider the allocation of chores for bivalued instances, where the cost of any item on any agent is either 1 or k, where k > 1. We call them {1, k}-instances. In our first result, we improve the state-of-the-art approximation ratio for EFX and fPO allocations for bi-valued chores to (2 - 1/k).

Result 1 (Theorem 3.14). For {1, k}-instances of indivisible chores, there exists an algorithm that computes (2-1/k)-EFX and fPO allocations in polynomial time.

As in recent works [Ebadian et al., 2022; Garg et al., 2022; Wu et al., 2023], our analysis follows the Fisher market analysis framework, a classic and widely used approach for computing allocations that are both fair and fPO. By associating a payment to every chore and computing an equilibrium, we can focus on achieving fairness, where the Pareto optimality will be implied by the equilibrium. Following this framework, Garg et al. [2024] start with an envy-free fractional earning restricted equilibrium (where the earning of an agent from any item is bounded) and devise a rounding scheme that computes a 3-EFX and fPO allocation 1 . Instead, in this work we start with the pEF1 integral equilibrium 2 for bi-valued chores [Garg et al., 2022; Wu et al., 2023], and design an algorithm that executes a sequence of item reallocations and returns a (2-1/k)-EFX and fPO allocation in polynomial time. A crucial difference between our analysis and that of Garg et al. [2024] is that since we start with a pEF1 equilibrium, to compute a (2 - 1/k)- EFX and fPO allocation, it suffices to consider the case when every agent possesses at most one high payment item. Therefore, by partitioning the agents into two groups depending on whether they have high payment items, we show that it suffices to reallocate items across the two groups. Since our algorithm and analysis do not require rounding fractional items, it is much simpler than that of Garg et al. [2024].

Moreover, we show that better results can be obtained for the case when k = 2.

Result 2 (Theorem 4.1). For {1, 2}-instances of indivisible chores, there exists an algorithm that computes EFX and fPO allocations in polynomial time.

We note that very few results are known for EFX and fPO allocations for chores. In fact, even the existence of EF1

1 As an intermediate step, they first round the equilibrium to a 2-EF2 and fPO allocation.

2 See the definition of pEF1 equilibrium in the Preliminaries.

and PO allocations for chores remains a major open problem, which is in sharp contrast to the allocation of goods [Caragiannis et al., 2019]. The existence of EFX and fPO allocations for chores has only been established for some special cases, e.g., for three bi-valued agents [Garg et al., 2023], for bi-valued instances with m ≤ 2n [Garg et al., 2024] and for binary instances ({0, 1}-instances) [Tao et al., 2025]. For some slightly more general cases, it has been shown that EFX is incompatible with (fractional) Pareto optimality. For example, Garg et al. [2023] show that EFX and fPO allocations do not always exist for the case with two agents, and the case with two types of chores. Tao et al. [2025] demonstrate that EFX and PO allocations do not always exist for ternary instances, where the cost of any item on any agent can only take values in {0, 1, 2}.

Our algorithm and analysis follow a similar framework as our first result, e.g., we start with the pEF1 equilibrium and reallocate items to strengthen the fairness guarantee. However, to improve the approximation ratio further, we need a finer classification of the agents into groups. Fortunately, for the pEF1 equilibrium for {1, 2}-instances, it can be shown that the earning of agents can only take values in {z, z +1, z +2}, for some integer z. Therefore, it suffices to reallocate items between agents with earning z and those with earning z + 2, until one of the two groups becomes empty, or the allocation becomes EFX. By proving that every agent with earning z will participate in item reallocation at most once, we show that our algorithm returns an EFX and fPO allocation in polynomial time.

1.2 Other RelatedWork

Due to the vast literature on the fair allocation problem, in the following we only review the results regarding the approximation and computation of EFX allocations. For a comprehensive overview of other related works, please refer to the surveys by Aziz et al. [2022b], Amanatidis et al. [2023].

EFX Allocations for Goods. Compared to the allocation of chores, the case of goods admits more fruitful results. The EFX allocations are shown to exist for two agents with arbitrary valuations or any number of agents with identical valuations by Plaut et al. [2020]; for three agents by Chaudhury et al. [2024] and Akrami et al. [2025]; and for two types of agents by Mahara [2023]. For bi-valued instances, Amanatidis et al. [2021] establish the existence of EFX and PO allocations. Furthermore, Garg and Murhekar [2023] introduce a polynomial-time algorithm for the computation of EFX and fPO allocations. Regarding the approximation of EFX allocations, Chan et al. [2019] demonstrate the existence of 0.5-EFX allocations, while Amanatidis et al. [2020] improve the approximation ratio to 0.618. Recently, Amanatidis et al. [2024] improve this ratio further to 2/3 for some special cases, e.g., seven agents or tri-valued goods.

EFX Allocations with Unallocated Items. For the allocation of goods, Chaudhury et al. [2021] show that EFX allocations exist if we are allowed to leave at most (n - 1) items unallocated. The result is improved to (n - 2) items by Berger et al. [2022], who also show that EFX allocations with at most one unallocated item can be computed for four agents. For the allocation of chores, EFX allocations with at most (n - 1) unallocated items have been shown to exist for bi-valued instances by Zhou and Wu [2024].

2 Preliminaries

We consider how to fairly allocate a set of m indivisible items (chores) M to a group of n agents N. We call a subset of items, e.g. X ⊆ M, a bundle. Each agent i ∈ N has an additive cost function ci : 2M → R+ ∪ {0} that assigns a cost to every bundle of items. For convenience, we use ci(e) to denote ci({e}), the cost of agent i ∈ N on item e ∈ M, thus ci(X) = ∑e∈X ci(e) for all X ⊆ M. We use c = (c1, . . . , cn) to denote the cost functions of agents. For any subset of items X ⊆ M and item e ∈ M, we use X + e and X - e to denote X ∪ {e} and X \ {e}, respectively. An allocation X = (X1, . . . ,Xn) is an n-partition of the items M such that Xi ∩Xj = ∅ for all i ̸= j and ∪i∈NXi = M, where agent i receives bundle Xi. Given an instance I = (N,M, c), our goal is to find an allocation X that is fair to all agents and also efficient.

Definition 2.1 (EF). An allocation X is envy-free (EF) if for any i, j ∈ N we have ci(Xi) ≤ ci(Xj).

Definition 2.2 (EF1). An allocation X is called envy-free up to one item (EF1) if for any agents i, j ∈ N, either Xi = ∅, or there exists an item e ∈ Xi such that ci(Xi -e) ≤ ci(Xj).

Definition 2.3 (β-EFX). For any β ≥ 1, an allocation X is β-approximate envy-free up to any item (β-EFX) if for any agents i, j ∈ N, either Xi = ∅, or for any e ∈ Xi, we have ci(Xi - e) ≤ β · ci(Xj). When β = 1, the allocation is EFX.

Notice that all the fairness notions mentioned above are scale-free, i.e., if an allocation satisfies one of these notions, then it remains to satisfy the same notion if we rescale any cost function.

Definition 2.4 (fPO). A (fractional) allocation X′ Pareto dominates another allocation X if ci(X′ i ) ≤ ci(Xi) for all i ∈ N and the inequality is strict for at least one agent. An allocation X is fractional Pareto optimal (fPO) if X is not dominated by any other fractional allocation.

Definition 2.5 (Bi-valued Instances). An instance is called bi-valued if there exist constants a, b ≥ 0 such that for any agent i ∈ N and item e ∈ M, we have ci(e) ∈ {a, b}.

We remark that when a = 0 or b = 0, such instances reduce to binary instances, for which EFX and PO allocations exist and can be computed in polynomial time [Tao et al., 2025]. Hence, in the following, we assume w.l.o.g. that a ̸= 0 and b ̸= 0. Additionally, we can rescale all the cost functions such that ci(e) ∈ {1, k}, where k > 1 can be arbitrary number and does not have to be an integer. Note that for all i ∈ N, there exists at least one item e ∈ M with cost ci(e) = 1 as otherwise we can rescale the cost functions so that ci(e) = 1 for all e ∈ M. For convenience, we refer to bi-valued instances mentioned above as {1, k}-instances.

Fisher Market. In the Fisher market, there is a payment vector p that assigns each chore e ∈ M a payment p(e) > 0. For any subset X ⊆ M, let p(X) = ∑e∈X p(e). Given the payment vector p, we define the pain-per-buck ratio

αi,e of agent i for chore e as αi,e = ci(e) p(e) , and the minimum pain-per-buck (MPB) ratio αi of agent i to be αi = mine∈M{αi,e}. Intuitively, when agent i receives chore e, she needs to perform ci(e) units of work and receives p(e) units of payment in return. Therefore every agent would like to receive items with low cost and high payment. Note that while the costs are subjective, the payments are objective. For each agent i, we define MPBi = {e ∈ M : αi,e = αi} as the set of items with the minimum pain-per-buck ratios and we call each item e ∈ MPBi an MPB item of agent i. An allocation X with payment p forms a (Fisher market) equilibrium (X, p) if each agent only receives her MPB items.

Following the First Welfare Theorem [Mas-Colell et al., 1995], for any market equilibrium (X, p), the allocation X is fPO. For completeness, we provide a short proof here.

Lemma 2.6. For any market equilibrium (X, p), the allocation X is fPO.

Proof. If the allocation Xwith payment p is an equilibrium, then for any agent i ∈ N, any item e ∈ Xi and any agent j ̸= i we have

Thus, the allocation minimizes the objective ∑i∈N ci(Xi) αi . Suppose that there exists another allocation Y with payment p that fractionally Pareto dominates X; this would strictly decrease the objective, i.e., ∑i∈N ci(Yi) αi < ∑i∈N ci(Xi) αi , leading to a contradiction. Therefore, the allocation X is fPO.

Definition 2.7 (pEF1). An equilibrium (X, p) is called payment envy-free up to one item (pEF1) if for any i, j ∈ N, either Xi = ∅, or there exists an item e ∈ Xi, such that p(Xi - e) ≤ p(Xj ).

Definition 2.8 (β-pEFX). For any β ≥ 1, an equilibrium (X, p) is called β-approximate envy-free up to any item (βEFX), if for any two agents i, j ∈ N either Xi = ∅ or for any item e ∈ Xi, we have

when β = 1, the equilibrium is pEFX.

Next, we establish a few lemmas showing that the approximate payment envy-freeness implies approximate envyfreeness. Note that vice-versa is not true, e.g., it is possible that an allocation is EFX but not pEFX. In other words, the payment envy-freeness is strictly stronger than envy-freeness.

Lemma 2.9. If an equilibrium (X, p) is pEF1, then the allocation X is EF1.

Proof. Since (X, p) is pEF1, for any i, j ∈ N, there exists an item e ∈ Xi, such that p(Xi - e) ≤ p(Xj). Therefore, according to the definition of MPB allocation, we have:

where the last inequality holds since the pain-per-buck ratio of agent i on any item is at least αi.

Lemma 2.10. Given any equilibrium (X, p), if agent i ∈ N is β-pEFX towards agent j ∈ N, then i is β-EFX towards j.

Proof. Since i is β-pEFX towards j, for any e ∈ Xi, we have p(Xi - e) ≤ β · p(Xj). Given that (X, p) is an equilibrium, we have:

Corollary 2.10.1. Given any equilibrium (X, p), if agent i is not β-EFX towards j, then i is not β-pEFX towards j.

3 (2 - 1/k)-EFX and fPO for {1, k}-Instances

In this section we present a polynomial-time algorithm for computing (2 - 1/k)-EFX and fPO allocations for {1, k}- valued instances. For bi-valued instances, several works showed that EF1 and fPO allocations exist and can be computed in polynomial time [Ebadian et al., 2022; Garg et al., 2022; Wu et al., 2023] based on the Fisher market framework. For any given bi-valued instance, they compute a pEF1 equilibrium, which implies an EF1 and fPO allocation. Specifically, the equilibrium has the following properties.

Lemma 3.1 ([Garg et al., 2022; Ebadian et al., 2022]). There exists an algorithm that given any {1, k}-instance (N,M, c) computes an equilibrium (X, p) that is pEF1, and satisfies p(e) ∈ {1, k} for all e ∈ M in polynomial time.

For an equilibrium satisfying p(e) ∈ {1, k} for all e ∈ M, we call it a {1, k}-payment equilibrium.

3.1 Properties of {1, k}-Payment Equilibrium

Depending on the payment vector p, we divide the items into two groups L and H, where L contains all items with low payment and H contains all items with high payment. We further categorize agents according to whether they receive high payment items.

Definition 3.2. Chores are categorized as:

• L = {e ∈M : p(e) = 1},
• H = {e ∈ M : p(e) = k}.

Agents are categorized as:

• NL = {i ∈ N : Xi ⊆ L},
• NH = {i ∈ N : |Xi ∩H| ≥ 1}.

We can assume that both L and H are non-empty; otherwise, all items will have the same payment, and the equilibrium will already be pEFX. Therefore, NH is non-empty. We can further assume that NL is non-empty because otherwise the equilibrium is (2 - 1/k)-pEFX: for all agents i, j ∈ N = NH and any e ∈ Xi, we have

where the first inequality holds since (X, p) is pEF1 and the second inequality holds since Xj ∩ H ̸= ∅. Next we establish some useful properties for {1, k}-payment equilibrium (X, p). Note that these properties hold for any {1, k}- payment equilibrium, regardless of whether it is pEF1 or not.

Lemma 3.3. For any {1, k}-payment equilibrium (X, p), we have the following properties:

1. For any agent i ∈ N, we have αi ∈ {1, 1k };
2. For any agent i ∈ NL, we have αi = 1;
3. For any agent i ∈ NL and item e ∈ H, we have ci(e) = k and e ∈ MPBi.

Proof. We prove these properties one by one.

• Fix any agent i ∈ N. Since ci(e) ∈ {1, k} and p(e) ∈ {1, k} for all e ∈ M, we have αi,e ∈ {k, 1, 1k }. As there exists at least one item e with ci(e) = 1, we have αi ≤ αi,e = 1 p(e) ≤ 1, which implies the first property.
• Fix any i ∈ NL. Since p(e) = 1 for all e ∈ Xi, we have αi = ci(e) p(e) = ci(e) ≥ 1. Combining this with the first property, we have αi = 1.
• Fix any agent i ∈ NL and item e ∈ H, we have ci(e) = αi,e · p(e) ≥ αi · k = k. Therefore we have ci(e) = k and αi,e = 1 = αi, which implies e ∈ MPBi.

Note that while it is possible that αi = 1k for some i ∈ NH, it happens only if ci(e) = 1 and p(e) = k for all e ∈ Xi. Moreover, all low payment items are not in MPBi.

Next, we establish more properties for pEF1 {1, k}- payment equilibrium.

Lemma 3.4. For any {1, k}-payment equilibrium (X, p), if (X, p) is pEF1 for agent i ∈ NH (i.e., i is pEF1 towards all other agents), then we have |Xi ∩ L| ≤ minj∈NL {|Xj |}.

Proof. Assume otherwise that |Xi ∩L| > |Xj| for some j ∈ NL. Since |Xi ∩H| > 0, we have

which implies that agent i is not pEF1 towards agent j and is a contradiction.

Lemma 3.5. For any {1, k}-payment equilibrium (X, p), if there exists an agent i that is pEF1 but not (2 - 1/k)-pEFX towards another agent j, then we have p(Xj) < k.

Proof. Since i is pEF1 towards j, we have p(Xi) ≤ p(Xj)+ k. Suppose that p(Xj) ≥ k. We have

In other words, i is (2 - 1/k)-pEFX towards agent j, which leads to a contradiction.

3.2 The Reallocation Algorithm

Now we are ready to introduce our algorithm. We begin with the {1, k}-payment pEF1 equilibrium (X0 , p) as described in Lemma 3.1. As long as the allocation is not (2 - 1/k)- EFX, we find an agent i that is not (2-1/k)-EFX towards an agent j, and reallocate some items between i and j (see Algorithm 1). During these reallocations, we do not change the payment of any item. Throughout the execution of the algorithm, we maintain the property that (X, p) is an equilibrium. Specifically, we ensure that when we reallocate an item e to agent i, we have e ∈ MPBi.

Note that if X0 is not (2 - 1/k)-EFX, then (X0 , p) is not (2 - 1/k)-pEFX. We first show that if (X0 , p) is not (2 - 1/k)-pEFX, we have some useful properties regarding the earnings of agents.

Lemma 3.6. If the equilibrium (X0 , p) is not (2 - 1/k)- pEFX, then we have mini∈NL {p(X0 i )} < k.

Proof. Since (X0 , p) is pEF1 and not (2-1/k)-pEFX, there exist i, j ∈ N such that agent i is not (2-1/k)-pEFX towards j. Following Lemma 3.5, we have p(X0 j ) < k. Recall that every agent in NH has at least one high payment item. Hence we have j ∈ NL and mini∈NL {p(X0 i )} ≤ p(X0 j ) < k.

Given the above lemma and that (X0 , p) is pEF1, we have the following property for (X0 , p).

Corollary 3.6.1. If (X0 , p) is not (2-1/k)-pEFX, then there exists an integer z < k such that

• for all agent j ∈ NL, p(Xj) ∈ {z, z +1};
• for all agent i ∈ NH, p(Xi) ∈ [k, k + z].

Proof. By Lemma 3.6, let z = minl∈NL p(X0 l ) < k. For agents j ∈ NL, since they only receive low payment items, z must be an integer. Combined with the fact that X0 is pEF1, we have p(Xj) ∈ {z, z + 1}. Moreover, for every agent i ∈ NH, since i possesses at least one high payment item, we have p(Xi) ∈ [k, k + z] by the pEF1 property.

Corollary 3.6.1 highlights that our starting point, the pEF1 equilibrium, possesses several useful properties, e.g., agents in NL are pEFX towards each other and agents in NH are (2 - 1/k)-pEFX towards each other. Therefore, to compute an allocation that is (2 - 1/k)-EFX and fPO, it suffices to eliminate the strong envy from agents in NH to agents in NL.

High Level Idea. The most natural idea is to reallocate items from agents in NH to those in NL, until the allocation is (2 - 1/k)-pEFX (which implies (2 - 1/k)-EFX and fPO, by Lemma 2.10). However, such reallocation must be "MPBfeasible", i.e., whenever we allocate an item e to agent i, we need to ensure that e ∈ MPBi, as otherwise the equilibrium property ceases to hold. As we have shown in Lemma 3.3, all high payment items are MPB to agents in NL. However, reallocating these items does not help achieving (2 - 1/k)- pEFX. On the other hand, there might not be sufficient low payment items fromNH that can be reallocated to NL, and it is difficult to maintain (2-1/k)-pEFX between agents in NL. To get around these difficulties, we instead focus on ensuring (2 - 1/k)-EFX, while guaranteeing that all reallocations are MPB-feasible (which maintains the equilibrium and the fPO property). We establish a useful property in Lemma 3.11 that if agent i is not (2-1/k)-EFX towards agent j, then we have Xj ⊆ MPBi. That means, while we cannot guarantee the MPB-feasibility for allocating the low payment items from Xi to Xj, we can instead exchange all low payment items in Xj with the high payment item in Xi, which preserves the equilibrium property and balances the earning between agents i and j. Note that throughout the whole execution of the algorithm, we do not change the payment of any item.

Algorithm 1: Computation of (2-1/k)-EFX and fPO

• allocations for {1, k}-instances Input: A pEF1 {1, k}-payment equilibrium (X, p) for {1, k}-instances 1 while exists agent i that is not (2-1/k)-EFX towards agent j do 2 j ← argmin{p(Xj ′) : i strongly envies j ′ }; // i ∈ NH, j ∈ NL, by Lemma 3.11 3 let e ∈ Xi ∩ H be the high payment item in Xi; 4 update Xi ←Xi ∪Xj - e; // Xj ⊆MPBi, by Lemma 3.11 5 update Xj ← {e}; // e ∈ MPBj, by Lemma 3.3 6 NH ←NH \ {i} ∪ {j}; 7 NL ←NL \ {j} ∪ {i}; Output: Allocation X

In the following, we say that agent i strongly envies agent j if i is not (2-1/k)-EFX towards j.

We use Xt to denote the allocation at the beginning of round t. During the item reallocations, we may reallocate high-payment items, and thus agents may shift between NL and NH. We use N tH and N tL to denote the set of agents with and without high payment items at the beginning of round t, respectively. Specifically, N 0L,N 0H denote the responding agent sets in the initial equilibrium (X0 , p). As an illustration, we give an example of the execution of Algorithm 1.

Example 3.7. Consider the following {1, k}-instance with seven agents and k = 6. At the beginning of round t, p(Xt1 ) = 2, p(Xt2 ) = 2, p(Xt3 ) = 3, p(Xt4 ) = 6, p(Xt5 ) = 7, p(Xt6 ) = 8, and p(Xt7 ) = 8. In this instance, agents 1, 2, and 3 are in group N tL while agents 4, 5, 6, and 7 are in group N tH . Agent 7 is not (2 - 1/k)-EFX towards some agents, with agent 1 having the minimum earning among them. Then, following Algorithm 1, agent 1 receives Xt7 ∩ H and agent 7 receives all items in Xt1 . See the illustration of the example in Figure 1.

3.3 Invariants and Analysis of Algorithm

Note that Xt+1 , N t+1 H , N t+1 L denote the allocation, the set of agents with and without high payment items at the end of round t, respectively. Before analyzing the algorithm, we first introduce several invariants that will be useful for our subsequent analysis. In our algorithm, we ensure that the equilibrium property is never violated, i.e., (Xt , p) is an equilibrium for all t, which guarantees that the allocation is fPO.

Invariant 3.8 (Equilibrium Invariant). For all t ≥ 0, (Xt , p) is a {1, k}-payment equilibrium.

In addition, our algorithm maintains the invariant that agents within the same group are always (2 - 1/k)-EFX towards each other. This means that we can focus solely on eliminating envy between different groups. Furthermore, their earnings are always bounded within the specified ranges.

Invariant 3.9 (Low Group Invariant). For all t ≥ 0, agents in N tL are (2 - 1/k)-EFX towards each other. Moreover, for all j ∈ NL, we have p(Xt j ) ∈ [z, k + z].

Invariant 3.10 (High Group Invariant). For all t ≥ 0, i ∈ N tH , we have p(Xt i ) ∈ [k, k + z].

Note that Invariant 3.10 implies that the allocation is pEF1 for agents in N tH . Moreover, agents in N tH are (2 - 1/k)- pEFX towards each other (which is stronger than being (2 - 1/k)-EFX), because for any two agents i, j ∈ N tH we have (recall that z < k)

In the following, we show that if the invariants are maintained (for (Xt , p), N tL and N tH ) when round t begins, then they remain to hold when round t ends. Particularly, all in-

variants hold when round 1 begins, for (X0 , p), N 0L and N 0H . Lemma 3.11. If there exists an agent i that is not (2-1/k)- EFX towards another agent j in round t, then we have i ∈ N tH , j ∈ N tL, αi = 1, and Xt j ⊆MPBi.

Proof. By Invariant 3.9 and 3.10, if i is not (2-1/k)-EFX towards j, then they must be from different groups. Moreover, if i ∈ N tL and j ∈ N tH , then we have

where the first inequality holds since p(Xt i ) ∈ [z, k + z] by Invariant 3.9 and the last inequality holds since p(Xt j ) ∈

[k, k + z] by Invariant 3.10. Therefore we must have i ∈ N tH and j ∈ N tL.

Next we show that Xt j ⊆ MPBi. First, observe that we must have αi = 1, as otherwise αi = 1/k and we have ci(e) = 1 and p(e) = k for all e ∈ Xt i . It implies that |Xt i | = 1, which is a contradiction with i being not (2-1/k)- EFX towards j. Second, we show that ci(e) = 1 for all e ∈ Xt j . Suppose otherwise, then we have

where the last inequality holds from the fact that ci(Xt j ) ≥ k. It's a contradiction with i being not (2 - 1/k)-EFX towards j. Therefore we have αi,e = 1 for all e ∈ Xt j , which implies Xt j ⊆MPBi.

Lemma 3.12. Invariants 3.8, 3.9 and 3.10 are maintained at the end of round t.

Proof. In round t, we identify two agents i ∈ N tH , j ∈ N tL, and exchange some items. By Lemma 3.11 and 3.3, we can guarantee that both agents receive items that are in their MPB set. Hence (Xt , p) is an equilibrium. As our algorithm does not change the payment of any item, the equilibrium remains {1, k}-payment. Hence Invariant 3.8 is maintained.

Next, we show that Invariant 3.9 is maintained. We remark that there is only one high payment item in Xt i since p(Xt i ) ≤ k + z < 2k, which implies that agent i only holds low payment items at the end of round t. Since in round t only i and j exchange items, it suffices to show that at the end of round t, (1) agent i (who joins N t+1 L ) is (2 - 1/k)-EFX towards all other agents in N t+1 L ; (2) all other agents in N t+1 L \ {i} is (2 - 1/k)-EFX towards i; (3) p(Xt+1 i ) ∈ [z, k + z].

1. For any agent l ∈ N t+1 L \ {i}, if agent i is (2 - 1/k)- EFX towards agent l in allocation Xt , then we have ci(Xt i ) - 1 ≤ (2 - 1/k) · ci(Xt l ). Since αi = 1 and Xt j ⊆ MPBi by Lemma 3.11, we have ci(Xt j ) = αi · p(Xt j ) < k by Lemma 3.5. Hence after exchanging a high payment item with Xt j , the bundle cost of agent i does not increase, and therefore agent i is still (2-1/k)- EFX towards l (whose bundle does not change) at the end of round t.

Suppose that agent i is not (2-1/k)-EFX towards agent l in allocation Xt . By Lemma 3.5 we have p(Xt l ) < k. Recall that j is the agent with the minimum earning such that i is not (2 - 1/k)-EFX towards. Hence p(Xt j ) ≤ p(Xt l ) = p(Xt+1 l ). Following Lemma 3.4, we have

where the first inequality holds since the allocation Xt is pEF1 for agent i and the last inequality holds from the fact that p(Xt+1 l ) = p(Xt l ) < k.

1. Following Invariant 3.9, any agent l ∈ N t+1 L \{i} is (21/k)-EFX towards agent j in the allocation Xt . Since Xt j ⊆ Xt+1 i , agent l is also (2 - 1/k)-EFX towards i at the end of round t.
2. At the end of round t we have

where the first inequality holds following p(Xt i ) ≤ k+z and |Xt i ∩ H| = 1, the second inequality holds from the fact that p(Xt j ) < k by Lemma 3.5. On the other hand, we have p(Xt+1 i ) ≥ p(Xt j ) ≥ z. In conclusion, p(Xt+1 i ) ∈ [z, k + z].

Finally, we show that Invariant 3.10 is maintained. It's clear that at the end of round t, Xt+1 j only contains an item with high payment, i.e., p(Xt+1 j ) = k ∈ [k, k + z]. For any l ∈ N t+1 H \ {j}, we have p(Xt l ) = p(Xt+1 l ), which implies that Invariant 3.10 is maintained at the end of round t.

Next, we will analyze the time complexity of the algorithm and demonstrate that it terminates in polynomial time.

Lemma 3.13. The algorithm computes a (2-1/k)-EFX and fPO allocation in O(n2m) time.

Proof. By the above analysis, in each while-loop of the algorithm, an agent i ∈ N tH and an agent j ∈ N tL will be selected, and after item reallocations, agent j receives one item with payment k and agent i receives all other low payment items. Therefore the number of agents in NH that receive at least one low payment item will decrease by one after each whileloop, which implies that the total number of while-loops is at most n. Given agent i, finding the agent j that is most envied by agent i can be done in O(m) time. Moreover, checking whether the allocation is (2 - 1/k)-EFX can be done in O(nm) time. Hence the algorithm runs in O(n2m) time.

In conclusion, for any given {1, k}-instance, we first compute the pEF1 {1, k}-payment equilibrium in O(kn2m2 ) time [Wu et al., 2023]. Subsequently, we apply Algorithm 1 to iteratively reallocate the items until the allocation is (2 - 1/k)-EFX. Since we maintain an equilibrium, fPO is guaranteed. As demonstrated in the previous sections, our algorithm guarantees this outcome in polynomial time, leading to the following main result.

Theorem 3.14. There exists a polynomial-time algorithm that computes a (2 - 1/k)-EFX and fPO allocation for every given bi-valued instance.

4 EFX and fPO for {1, 2}-Instances

In this section, we consider the case that k = 2 and propose an algorithm that computes EFX and fPO allocations. The main result of this section is summarized as follows.

Theorem 4.1. For any {1, 2}-instance of indivisible chores, we can compute EFX and fPO allocations in polynomial time.

Due to the page limit, the algorithm and analysis are deferred to the full version of the paper 3 . In the following, we provide a sketch of the algorithm and main ideas.

As in Section 3, our algorithm begins with the pEF1 {1, k}- payment equilibrium (X, p) for {1, k}-instances by existing works 4 . Note that for k = 2, we have |p(Xi) - p(Xj)| ≤ 2 for any two agents i, j ∈ N since the equilibrium (X, p) is pEF1. Hence, we can partition the agents into three groups N z ,N z+1 and N z+2 for some integer z, where an agent i is contained in N t if p(Xi) = t. Moreover, if N z = ∅ or N z+2 = ∅, then the allocation is already pEFX (thus EFX and fPO). Therefore, a natural idea is to reallocate items between agents in N z and N z+2 until one of the two groups is empty. However, due to similar difficulties we mentioned in the previous section, achieving pEFX could be very difficult. We therefore focus on achieving EFX while maintaining the equilibrium property. However, in order to further improve the approximation guarantee (regarding EFX), we need more structural properties. Remark that the algorithm presented by [Wu et al., 2023] divides agents into two groups, unraised agents U and raised agents N \ U. For any i ∈ U, we have αi = 1 while for j ∈ N \ U we have αj = 1k . We show that as long as the allocation is not EFX, we can find an agent i ∈ N z+2 that is not EFX towards an agent j ∈ N z , where both agents i, j are unraised. Therefore we can reallocate items between the two agents without violating the MPB feasibility. We show that by reallocating at most two items between agent i and agent j, we can ensure that either both of them join N z+1 , or one of them receives only high payment items and will never participate in any item reallocation in the future. Therefore, such reallocation can happen at most O(n) times, and an EFX and fPO allocation will be returned.

5 Conclusion and Open Problems

In this work, we present a polynomial-time algorithm that computes (2 - 1/k)-EFX and fPO allocations for {1, k}- instances, improving the state-of-the-art approximation ratio for EFX allocations for bi-valued instances. We also present a polynomial-time algorithm for the computation of EFX and fPO allocations for {1, 2}-instances. Our results enrich and expand the growing literature on the computation and approximation of EFX allocations for chores. However, it remains a fascinating open problem whether EFX allocations (even without the fPO requirement) exist for bi-valued instances. Our algorithm and analysis framework (and that of Garg et al. [2024]) start from an equilibrium for chores and reallocate items maintaining MPB feasibility, which seem to have a great potential in improving other results regarding EF1/EFX and fPO allocations for chores. It would be an interesting open question to study which type of equilibrium and which specific properties of the equilibrium would be most helpful for approximating EF1/EFX and fPO allocations.

3 See the full version at https://arxiv.org/abs/2501.04550.

4 In this paper, we mainly follow the algorithm of [Wu et al., 2023], which originally works for the weighted setting in which each agent has a non-negative weight wi > 0 and returns a pWEF1 equilibrium. Here we let all agents' weight be 1/n.

Acknowledgments

• Xiaowei Wu is funded by the Science and Technology Development Fund (FDCT), Macau SAR (file no. 0147/2024/RIA2, 0014/2022/AFJ, 0085/2022/A, 001/2024/SKL and SKL-IOTSC-2024-2026).