Computing Epistemtic EF1 and Pareto-Optimal Allocations of Indivisible Chores

1 Introduction

Fair division is a discipline at the intersection of algorithms, economics, and social choice. In a typical setting, the problem is to divide a set of resources or tasks in a fair manner among a set of agents with varying preferences. Our focus in this paper is the fair and efficient allocation of indivisible chores - indivisible items which impose a disutility to agents, such as household tasks or teaching responsibilities - to agents with additive preferences. Unlike the allocation of goods, where agents seek to maximize utility, chore division problems involves minimizing disutility, leading to both conceptual and technical challenges that are distinct from their goods counterparts.

A central fairness notion is envy-freeness (EF) [Foley, 1967], which requires that no agent strictly prefers another While envy-freeness and its relaxations capture fairness from an agent's realized outcome, they become less appealing in environments where agents have uncertain or incomplete knowledge about others' allocations. Such settings naturally arise in applications with a large number of agents or with privacy constraints, where an agent may know the full instance but have access only to her own bundle. To model fairness under such uncertainty, [Caragiannis et al., 2023] and [Aziz et al., 2018] proposed notions of epistemic fairness. For any notion of "fairness" such as EF1/EFX, an allocation X is said to satisfy epistemic fairness if for every agent i, there is a way to re-allocate the items outside i's bundle Xi among the other agents such that i perceives the resulting allocation as fair.

Thus, epistemic fairness notions capture a optimistic interpretation of fairness under epistemic uncertainty: an agent can rationalize their outcome as fair under some plausible completion of the unknown parts of the allocation. Although epistemic fairness is a weaker notion, it is strong enough to yield meaningful fairness guarantees when agents lack full information. In fact, experimental findings indicate that "allocations based on epistemic EF are perceived as fairer than those based on counterfactual relaxations" [Hosseini et al., 2025]. Epistemic fairness notions also offer a existential advantage. For instance, while the existence of EFX allocations remains open despite extensive research, epistemic EFX allocations are known to exist for monotone valuations [Akrami and Rathi, 2025].

Fairness alone, however, is insufficient for guaranteeing desirable outcomes, as an allocation may be fair yet highly inefficient. This motivates the study of fair allocations that also satisfy Pareto optimality (PO), a central notion of economic efficiency which requires that no other allocation can make some agent strictly better off without making any agent worse off. In the context of indivisible chores, the question of whether EF1 and PO can be achieved simultaneously has received considerable attention [Aziz et al., 2019; Aziz et al., 2023; Ebadian et al., 2022; Garg et al., 2022; Garg et al., 2023b; Garg et al., 2024]. Although recent work [Mahara, 2025] has established the existence of such allocations, the proof relies on highly non-constructive fixed-point arguments and thus offers no algorithmic procedure for computing them.

Given the lack of computational progress on EF1 and PO allocations for chores, and the appeal of epistemic fairness notions, [Garg and Sharma, 2025] posed the following open question:

Is there an (efficient) algorithm for computing an allocation of chores that is simultaneously epistemic EF1 and Pareto-optimal?

1.1 Our Results

Our main result answers this question in the affirmative.

Result 1 (Main Result). There exists a pseudo-polynomial time algorithm for computing an epistemic EF1 and Paretooptimal allocation of indivisible chores to agents with additive disutilities.

The running time of our algorithm is polynomial in the number of agents n, the number of chores m, and the maximum disutility value ∆. We emphasize that even in the setting of indivisible goods, the best-known algorithmic result for computing allocations that are both EF1 and Pareto optimal is pseudo-polynomial [Barman et al., 2018a], and the existence of a fully polynomial-time algorithm remains open. Although our running-time bound is pseudo-polynomial, we expect the algorithm to perform efficiently in practice: it avoids computationally intensive subroutines such as solving integer or convex programs, and the parameter ∆ is typically small in real-world instances.

Certifying epistemic EF1. A natural question is whether agents can verify for themselves if the outcome of our algorithm indeed satisfies epistemic EF1. Surprisingly, we show:

Result 2. The problem of verifying if a given allocation is epistemic EF1 for particular agent is NP-complete.

Fortunately, our algorithm can provide agents with certificate allocations that enable them to verify that the allocation returned by the algorithm is indeed epistemic EF1. Concretely, along with the epistemic EF1 and PO allocation X, our algorithm additionally gives each agent i an bundle Yi such that Xi = Yi and i is EF1 in Y .

Asymmetric Fair Division. We extend our results to the chore allocation problems with asymmetric agents. Many applications involve agents with differing entitlements, accountability, or capacities for handling workload. For example, in a university, teaching faculty may be responsible for teaching twice as many courses as research faculty, and would therefore be envious only if they believe their workload exceeds twice that of a research faculty.

This motivates the notion of weighted EF1 (wEF1). Given agent weights {wi}i∈N, an allocation X is said to be wEF1

if for every agent i, there exists some chore j ∈ Xi s.t. the disutility to i fromXi \ {j} is at most wi/wh times the disutility to i from the bundle Xh of any h ̸= i. Epistemic wEF1 is defined analogously. We show:

Result 3. There exists a pseudo-polynomial time algorithm for computing an epistemic wEF1 and Pareto-optimal allocation of indivisible chores to asymmetric agents with additive disutilities.

1.2 Technical Contributions

We highlight the technical contributions of our work, situating it within related work. The problem of simultaneously achieving EF1 and PO has attracted tremendous interest in recent years. The fact that merely certifying if an allocation is Pareto-optimal is coNP-complete [de Keijzer et al., 2009] adds to the challenge of computing such an allocation.

[Caragiannis et al., 2019] showed that for goods, an allocation that maximizes the Nash welfare, i.e., product of utilities, is EF1 and PO. However, this approach is not computationally efficient as maximizing the Nash welfare is APX-hard [Lee, 2015; Garg et al., 2023a]. The first computational result was a pseudo-polynomial time algorithm for computing an EF1 and PO allocation of goods [Barman et al., 2018a]. The main idea is to use competitive equilibria (CE): an allocation X with goods prices p such that each agent only receives goods that Maximize Bang-per-Buck (MBB), i.e., the utility-to-price ratio. Such an allocation (X, p) offers a two-fold advantage: X is guaranteed to be PO, and the associated prices provide a common scale for comparing agents' utilities across bundles. Then, a natural approach is to iteratively adjust the allocation and prices to maintain the MBB condition while making progress towards EF1 by transferring items between envied and envious agents.

For chores, however, this natural approach falls short, as price updates can cause bundle prices to diverge significantly across agents, which makes termination unclear. For restricted domains such as bivalued instances or three agents, several works [Ebadian et al., 2022; Garg et al., 2022; Aziz et al., 2023; Garg et al., 2023b; Garg et al., 2024] adopt the above approach using domain specific arguments to prove convergence. The existence of EF1 and PO allocations of chores was finally settled by [Mahara, 2025], who used a novel fixed-point argument to directly identify a price vector p that guarantees the existence of an EF1 allocation X such that (X, p) satisfies the chores equivalent of the MBB condition (minimum pain-per-buck). However, this approach is not constructive and does not lead to an effective algorithm.

We employ a natural iterative approach to compute an epistemic EF1 and PO allocation of chores. To establish the convergence of our algorithm, we develop several novel technical insights that both leverage the distinctive structure of epistemic EF1 and address the unique challenges it introduces.

• Transferring a chore from one agent to another does not cause any agent outside the transfer to violate epistemic EF1. This robustness property is specific to epistemic EF1 and does not hold for classical EF1.
• Unlike EF1, determining whether an agent satisfies epistemic EF1 for a given allocation is NP-hard. Consequently,

epistemic EF1 violators cannot even be efficiently identified! To address this challenge, we carefully maintain a set V that is always guaranteed to contain all epistemic EF1 violators, and progressively eliminate agents from V .

• Agents in the set V never gain chores and never undergo price updates during the algorithm. This invariant allows us to establish lower bounds on chore prices, which plays a central role in the termination argument.

We expect these technical insights to be useful for designing algorithms that guarantee both epistemic fairness and efficiency. Indeed, we adapt these ideas to design a pseudo-polynomial time algorithm for computing a epistemic weighted EF1 and PO allocation.

1.3 Other RelatedWork

We mention additional related work not discussed so far, and refer the reader to surveys [Aziz et al., 2022; Amanatidis et al., 2023; Liu et al., 2024; Suksompong, 2025].

EF1 and PO. For goods, computing an EF1 and PO allocation in polynomial time is an open question, but is known for binary instances [Barman et al., 2018b] and for constant number of agents [Mahara, 2024]. An EFX and PO allocation can be computed in polynomial time [Garg and Murhekar, 2023] for bivalued instances. For chores, an (weighted) EF1 and PO allocation can be computed in polynomial time for constant number of agents [Mahara, 2025]. Polynomial time algorithms are known for other special cases, such as bivalued instances [Ebadian et al., 2022; Garg et al., 2022; Wu et al., 2023], three types of agents [Garg et al., 2024], two types of chores [Aziz et al., 2023; Garg et al., 2024].

Epistemic EFX. [Caragiannis et al., 2023] introduced the notion of epistemic EFX, adapting similar concepts from [Aziz et al., 2018]. They gave a polynomial-time algorithm for computing an EEFX allocation for additive preference; [Akrami and Rathi, 2025] improved this to monotone preferences. [Garg and Sharma, 2025] discuss implications between EEFX and other fairness properties, e.g., they show EEF1 implies proportionality up to one chore (Prop1).

Due to space constraints, we defer missing proofs to the full version of the paper.

2 Preliminaries

Let [n] = {1, 2, . . . , n}, for any n ∈ N. For brevity, we use S ∪ j and S \ j in place of S ∪ {j} and S \ {j}, respectively.

ProblemInstance. An instance of the fair division problem with chores is specified by 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 = (d1, . . . , dn) is a list of agent disutility functions. The disutility function di : 2M → Z≥0 specifies the disutility di(S) incurred by agent i on doing the set S of chores. We assume that agents have additive disutilities, i.e., di(S) = ∑j∈S dij, where dij ∈ Z≥0 is the disutility of chore j for agent i. Define ∆ = maxi∈N,j∈M dij . Naturally, ∆ ≥ 1.

Allocation. An allocation X = (X1,X2, . . . ,Xn) is a complete partition of the chores, i.e. Xi ∩ Xh = ∅ for all distinct i, h ∈ N, and M = ⋃i∈N Xi. Here, Xi is the bundle of chores allocated to agent i. In a fractional allocation y ∈ [0, 1]n×m, chores can be allocated fractionally, with yij ∈ [0, 1] denoting the fraction of chore j allocated to agent i. In a fractional allocation y, agent i receives disutility di(yi) = ∑j∈M dijyij. We assume allocations are integral unless specified.

EF1 and ε-EF1. We define the fairness notions of EF1 and approximate-EF1. Let ε ≥ 0.

Definition 1 (EF1). An allocation X is said to be ε-envy-free up to one chore (ε-EF1) for an agent i if Xi = ∅ or there exists j ∈ Xi s.t. for all h ∈ N, di(Xi \ j) ≤ (1+ε)di(Xh). If X is not ε-EF1 for i, then i is said to be an ε-EF1 violator in X. An allocation X is said to satisfy ε-EF1 if no agent is an ε-EF1 violator in X.

Throughout the paper as well as the subsequent definitions, when ε = 0 we the drop ε from the fairness notion, e.g., we write X is EF1 instead of writing X is 0-EF1.

Epistemic EF1. We now define the epistemic relaxation.

Definition 2 (Epistemic EF1). An allocation X is said to be epistemic ε-EF1 (ε-EEF1) for an agent i if there exists an allocation Y = (Y1, . . . , Yn) where Xi = Yi and Y is ε-EF1 for i. We refer to such an allocation Y as a ε-EEF1-certificate for i in X, or simply certificate when the context is clear.

If X is not ε-EEF1 for i, then i is said to be an epistemic εEF1 violator, or simply violator. An allocation X is ε-EEF1 if no agent is an ε-EEF1 violator in X.

From the definitions it is clear that ε-EF1 implies epistemic ε-EF1, but not vice-versa.

Pareto-optimality. An allocationX is said to be Pareto optimal (PO) if there is no allocation Y s.t. for all i ∈ N, di(Yi) ≤ di(Xi), and there exists h ∈ N such that dh(Yh) < dh(Xh).

A fractional allocation x is said to be fractionally Paretooptimal (fPO) if there is no fractional allocation y s.t. for all i ∈ N, di(yi) ≤ di(xi), and there exists h ∈ N such that dh(yh) < dh(xh).

An fPO allocation is clearly PO, but not vice-versa.

Competitive Equilibrium. A Fisher market for chores is specified by a tuple (N,M,D, e) where N,M,D are as defined earlier, and e = (e1, . . . , en) ∈ Rn>0 is a list of agent earning requirements. Each agent i aims to earn an amount ei > 0 by performing chores in exchange for payment. Each chore j has a price pj > 0 which specifies the payment per unit of the chore. In a fractional allocation x and a price vector p = (p1, . . . , pm), the earning of agent i is p(xi) = ∑j∈M pj · xij.

Given prices p ∈ Rm>0 , the minimum-pain-per-buck (MPB) ratio of agent i is αi = minj∈M dij/pj. The set MPBi := {j ∈ M | dij/pj = αi} comprises chores that minimize the disutility-to-payment ratio for agent i. We refer to any chore j ∈ MPBi as an MPB chore for i. For an allocation X and prices p, we say (X, p) is an MPB allocation if Xi ⊆ MPBi for all i ∈ N.

A fractional allocation x and prices p together constitute a competitive equilibrium (CE) if each agent i receives a bundle of lowest disutility subject to their earning requirement ei, and every chore is allocated. For additive disutilities, a CE can be equivalently be characterized in terms of MPB ratios: (x, p) is a CE iff:

• For all i ∈ N, p(xi) = ei.
• For all j ∈ M, ∑i∈N xij = 1.
• For all i ∈ N and j ∈ M, if xij > 0 then j ∈ MPBi.

The First Welfare Theorem shows that competitive equilibria are efficient [Mas-Colell et al., 1995].

Proposition 1 (First Welfare Theorem). Let (x, p) be an MPB allocation. Then x is fPO.

Price EF1. Let X be an integral allocation and p be a price vector. Let ˆ p(Xi) := minj∈Xi p(Xi \ j) denote the earning of agent i from the bundle Xi excluding her highest paying chores, and let ˆ di(Xi \ {j}) = minj∈Xi di(Xi \ {j}). [Barman et al., 2018a] introduced the notion of price-EF1 as a sufficient condition for computing an EF1 and PO allocation for goods. It has since been used in several works on computing EF1 and PO for goods and chores [Barman and Krishnamurthy, 2019; Ebadian et al., 2022; Garg and Murhekar, 2023; Garg et al., 2022; Garg et al., 2023b; Garg et al., 2024; Garg et al., 2025; Mahara, 2024; Mahara, 2025].

Definition 3 (Price EF1). An allocation (X, p) is said to be ε-price-envy-free up to one chore (ε-pEF1) if for all i, h ∈ N we have ˆ p(Xi) ≤ (1 + ε)p(Xh).

Lemma 1. Let (X, p) be an MPB allocation where X is integral. If (X, p) is ε-pEF1, then X is ε-EF1 and fPO.

Proof. Since (X, p) is an MPB allocation, it follows from Proposition 1 that X is fPO. Let αi denote the MPB ratio of agent i at prices p. For any i, h ∈ N, we have:

An agent i is said to be a ε-pEF1 violator in an allocation (X, p) if ˆ p(Xi) > (1 + ε) · minh p(Xh).

Lemma 2. Let (X, p) be an MPB allocation. If i is an epistemic ε-EF1 violator in X, then i is an ε-EF1 violator in X and a ε-pEF1 violator in (X, p).

Proof. This follows by taking the contrapositive of the chain of implications: If for any agent i, (X, p) is ε-pEF1, then X is ε-EF1, and hence epistemic ε-EF1.

MPB Graph and Alternating Paths. Given a price vector p, its associated MPB graph is a bipartite graph (N,M,E) where (i, j) ∈ E iff j ∈ MPBi. For an MPB allocation (X, p), the augmented MPB graph G is obtained from the MPB graph by additionally marking the allocation, i.e., edges (i, j) s.t. j ∈ Xi. Thus, the augmented MPB graph captures information about the MPB edges as well as the current allocation.

Let i0 ∈ argminℓ∈N p(Xℓ) denote the least-earner (LE), with ties broken arbitrarily. Let L = p(Xi0 ). An alternating path P = (i0, j1, i1, . . . , jr, ir) is a path in the augmented MPB graph beginning at the LE i0, where jk ∈ Xk∩MPBk-1 for each k ∈ [r]. Thus, the path alternates between MPB edges and allocation edges. Let R(i0) denote the set of agents and chores reachable from i0 through alternating paths in G.

Perturbation. For some arguments pertaining to the runtime analysis of our algorithm, it is useful to work with a perturbed instance.

Definition 4. Given an instance I = (N, M, D) and a parameter ε ∈ (0, 1), the ε-perturbed instance I ε = (N,M,D′ ) is constructed by rounding the disutilities to the nearest higher powers of (1+ε). Formally, for any i, j set d′ij = 0 if dij = 0. Otherwise, let ℓij = ⌈log1+ε dij⌉ and set d′ij = (1 + ε)ℓij .

Lemma 3. Let I = (N,M,D) be a given instance, and let I ε be an ε-perturbation of I for ε ≤ 1 6m∆ . If an allocation X is ε-EF1 and fPO for I ε , then X is EF1 and PO for I.

3 Epistemic EF1 and PO

In this section, we state and prove our main result.

Theorem 2. Given a chores instance (N,M,D), an epistemic EF1 and PO allocation can be computed in poly(n, m, ∆)-time.

We prove Theorem 2 by presenting Algorithm 1 for computing an epistemic EF1 and PO allocation of chores. We perturb the given instance as defined in Definition 4, for ε = 1 6m∆ . In the following discussion, we assume we are working with an ε-perturbed instance.

3.1 AlgorithmOverview

Throughout its execution, Algorithm 1 maintains an integral allocation X and chore prices p such that (X, p) satisfies the MPB condition. Due to Lemma 1, this guarantees that the allocation X is fPO. The algorithm is initialized an fPO allocation (X0 , p0 ) as follows. For every j ∈ M, we assign j to an agent i with minimum dij and set p0j = dij . Thus, p0j ≥ 1 for all j ∈M.

Let Et be the set of agents who are not epistemic EF1 in the allocation Xt in iteration t of Algorithm 1. We refer to such agents as epistemic EF1 violators, or simply violators in Xt . Unfortunately, as we show in Theorem 4, it is NPhard to certify if a given agent i is epistemic EF1 in a given allocation X. Therefore, the set Et cannot even be identified in polynomial time. Instead, we keep track of violators by maintaining a set V t of agents that is guaranteed to contain the violators. That is, we maintain the invariant (proved in Lemma 7):

Invariant 1. At any iteration t of Algorithm 1, Et ⊆ V t .

By Lemma 2, we know that any agent i who is an epistemic EF1 violator must also be an EF1 violator. Therefore, we initialize V as the set of EF1 violators in (X0 , p0 ), which is guaranteed to contain the epistemic EF1 violators in X0 . Further, if at any time t, some agent i satisfies EF1 in the allocation Xt , then i is also epistemic EF1 in Xt . Whenever this happens, we remove i from the set V .

Algorithm 1 Epistemic EF1 and PO

Input: An ε-perturbed instance (N,M,D) Output: An allocation X that is epistemic EF1 and PO 1: X ← (∅, ∅, . . . , ∅) 2: for each j ∈M do 3: i ← arg minh∈N dhj 4: Xi ←Xi ∪ j 5: pj ← dij 6: V ← {i ∈ N : i is not EF1 in X} 7: while V ̸= ∅ do 8: i0 ← arg minℓ∈N p(Xℓ) ▷ Least earner 9: L← p(Xi0 ) 10: G←Augmented MPB graph of (X, p) 11: R(i0) ←Reachable set of i0 in G 12: if V ∩R(i0) ̸= ∅ then 13: P = (i0, j1, i1, . . . , ir, jr) be the shortest alternating path s.t. p(Xir \ jr) > (1 + ε)L 14: k ← max{ℓ ∈ [r - 1] : p(Xiℓ ∪ jℓ+1 \ jℓ) ≤ L} 15: if no such k exists then k ← 0 16: X′ ir ←Xir \ jr 17: for t = k + 1 to r - 1 do 18: X′ it ← Xit ∪ jt+1 \ jt 19: X′ ik ← Xik ∪ {jk+1} 20: X ← X′ 21: for each i ∈ V do 22: if i satisfies EF1 in X then 23: V ← V \ {i} 24: else 25: Uniformly decrease pj for all chores in R(i0) until a new MPB edge appears

26: return (X, p)

Algorithm 1 continues until the set V becomes empty. Lemma 7 therefore ensures that the allocation upon termination is epistemic EF1. While V is non-empty, Algorithm 1 iteratively takes one of two steps: transfer and price drop.

Transfer step. Let i0 be a least earner: an agent i with minimum p(Xi). Let R(i0) be the set of agents and goods reachable from i0 in the MPB graph constructed at (X, p). We execute a transfer step if a violator is reachable from i0, i.e., V ∩R(i0) ̸= ∅.

A transfer step on the allocation (X, p) works as follows. Let L = p(Xi0 ). Let P = (i0, j1, i1, . . . , jr, ir) be the shortest alternating path from i0 to a path violator ir. That is, ir is the agent closest to i0 in R(i0) with p(Xir \ jr) > (1 + ε)L. Such an agent ir must exist: if not, then it means that for all i ∈ R(i0), we have ˆ p(Xi) ≤ (1 + ε)p(Xi0 ). Thus, every agent i ∈ R(i0) is pEF1 in (X, p). By Lemma 2 and Lemma 3, i is EF1 and also epistemic EF1 in X. This contradicts V ∩R(i0) ̸= ∅.

Next, we identify k ∈ [r - 1] to be the maximum index s.t. p(Xik ∪ jk+1 \ jk) ≤ L. If there is no such k ∈ [r - 1], we set k = 0. We now perform the following transfers of chores to obtain the allocation X′ fromX:

• Set X′ ir =Xir \ jr.
• For ℓ ∈ {k + 1, . . . , r - 1}, set X′ iℓ = Xiℓ ∪ jℓ+1 \ jℓ.
• Set X′ ik = Xik ∪ jk+1.
• Set X′h =Xh for h not in P.

In other words, agent ir loses chore jr to ir-1, for each ℓ ∈ {k + 1, . . . , r - 1}, agent iℓ gains jℓ+1 and loses jℓ, and ik receives jk+1. In effect, a transfer step removes chores away from agents who may potentially be epistemic EF1 violators. Crucially, we show in Lemma 6 that a transfer step does not create new epistemic EF1 violators. After completing the transfer step, we remove from V any agent who is EF1 in the new allocation X′ .

Price drop step. Algorithm 1 executes a price drop step in the event that V ∩ R(i0) = ∅. In this case, the prices of all chores in R(i0) are uniformly scaled down until a new edge (i, j) in the MPB graph is created. By the definition of MPB ratio for chores, this edge must be between an agent i ∈ R(i0) and a chore j /∈ R(i0). This is because lowering the prices of chores in R(i0) makes the chores outside R(i0) relatively attractive for agents in R(i0).

Concretely, for each chore j ∈ R(i0), we update pt+1 j = ptj /βt, where βt ≥ 1 is the price drop factor given by:

Note that the price drop step only affects prices and not the allocation, and hence the set V remains unaltered in this step. The algorithm continues executing transfer or price drop steps until V becomes empty.

3.2 AlgorithmAnalysis

We prove that Algorithm 1 maintains the MPB condition throughout its execution.

Lemma 4. For every t, the allocation (Xt , pt ) satisfies the MPB condition.

Proof. Clearly, every transfer step maintains an MPB allocation by design since it exchanges chores along MPB edges. For price drop steps, the choice of βt as defined in Eq. (1) ensures that the MPB condition is satisfied for all agents even after the price drop.

We first show that transfer steps do not cause a drop in the minimum agent earning.

Lemma 5. The minimum agent earning does not decrease after a transfer step.

Proof. Consider a transfer step on the allocation (X, p) and let X′ be the resulting allocation. Let i0 be the least earner i0 with L = p(Xi0 ). Let P = (i0, j1, i1, . . . , jr, ir) be the chosen alternating path, with k chosen as described. We prove that p(X′ i ) ≥ L for all i ∈ N.

• i = ir. Since ir is a path violator, we know p(Xir \ jr) > (1 + ε)L. Since X′ ir = Xir \ jr, we obtain p(X′ ir ) > L.
• i = iℓ for ℓ ∈ {k + 1, . . . , r - 1}. By the choice of k, we know p(Xiℓ ∪jℓ+1\{jℓ}) > L. Since X′ iℓ =Xiℓ ∪jℓ+1\jℓ, we obtain p(X′ iℓ ) > L.

• i = ik. Since X′ ik = Xik ∪ jk+1, we have p(X′ ik ) ≥ p(Xik ) ≥ L.
• i /∈ P. Since X′

Next, we prove that the transfer step cannot create new epistemic EF1 violators.

Lemma 6. The set of epistemic EF1 violators cannot increase after a transfer step.

Proof. Consider a transfer step on the allocation (X, p). Let i0 be the least earner i0 with L = p(Xi0 ). Let P = (i0, j1, i1, . . . , jr, ir) be the chosen alternating path, with k chosen as described. Let X′ be the allocation resulting from the transfer.

We prove that the transfer step does not create new violator by proving that any agent i who is epistemic EF1 in X must also be epistemic EF1 in X′ . We consider the following cases for agent i.

• i = ir. Since ir is epistemic EF1 in the allocation X, there is some certificate Y which is EF1 for ir and Xir = Yir . We construct a certificate Y ′ for ir from Y . Let i ̸= i be an arbitrary agent. Set Y ′ ir = Yir \ {jr}, Y ′h = Yh for all h /∈ {i, ir} and Y ′ i = Yi ∪{jr}. It is easy to observe that ir is EF1 towards any h ̸= ir in the certificate Y ′ :

Since Y ′ ir = Xir \ jr = X′ ir , we conclude that ir is epistemic EF1 in X′ with the certificate Y ′ .

• i = iℓ for ℓ ∈ {k + 1, . . . , r - 1}. By the choice of ir as the closest path violator reachable from i0, we know that p(Xiℓ \jℓ) ≤ (1+ε)L. Recall that X′ iℓ =Xiℓ ∪jℓ+1\jℓ.We argue that iℓ is pEF1 towards any i in (X′ , p) as follows:

Since iℓ is ε-pEF1 in X′ , by Lemma 2 and Lemma 3, iℓ is EF1 and hence epistemic EF1 in X′ with the certificate X′ .

• i = ik. By the choice of k, we knowp(Xik ∪jk+1\jk) ≤ L. Recall that X′ ik = Xik ∪ jk+1. We observe that ik is pEF1 towards any agent i in (X′ , p) as follows:

Since ik is pEF1 in X′ , by Lemma 2, ik is EF1 and hence epistemic EF1 in X′ with certificate X′ .

• i /∈ P. Since agent i is epistemic EF1 in X, we know there is a certificate Y where Yi = Xi and i is EF1 in Y . Moreover, since i /∈ P, we have X′ i = Xi. Therefore i is epistemic EF1 in X′ with certificate Y ′ = Y .

The above four cases show that the transfer step does not create any new epistemic EF1 violators. In addition, we can also compute the certificate allocation that certifies an agent i is EF1: either using the previous certificate for i, or the present allocation itself.

This allows us to show Invariant 1.

Lemma 7. At any iteration t of Algorithm 1, the set of epistemic EF1 violators Et is contained in the set V t .

Proof. Let Et and V t denote the set of epistemic EF1 violators in allocation Xt and the set V maintained by the algorithm in iteration t, respectively. We inductively prove that Et ⊆ V t . Initially, we know E0 ⊆ V 0 by definition of E0 and V 0 . Suppose Et ⊆ V t for some t ≥ 0.

Suppose a transfer step takes place at t. Consider any agent i ∈ Et+1 . We will show that i ∈ V t+1 . Lemma 6 shows that transfer steps do not create new violators, and hence Et+1 ⊆ Et . By the inductive hypothesis, Et ⊆ V t . Thus, i ∈ V t . Since i ∈ Et+1 , by Lemma 2, i is not EF1 in Xt+1 . Since Algorithm 1 removes the agents who are EF1 after the transfer from the set V , we have i /∈ V t \V t+1 . Together with the fact that i ∈ V t , this means i ∈ V t+1 .

Suppose a price drop step takes place at t. Then Et+1 = Et and V t+1 = V t since the allocation does not change. Hence Et+1 ⊆ V t+1 .

Algorithm 1 terminates when V = ∅. Due to Lemma 7, this means that the allocation upon termination has no epistemic EF1 violators, i.e., is epistemic EF1. Having argued correctness, we proceed to analyze the running time of Algorithm 1. The following lemma will be useful.

Lemma 8. The following hold in every iteration t of Algorithm 1.

• (i) Any agent in V t does not undergo price drop.
• (ii) For any i ∈ V t , Xt i ⊆X0 i .
• (iii) For any i ∈ V t and j ∈ Xt i , ptj = p0j .

Proof. (i) Let i be an agent who undergoes a price drop step in iteration t, when the state of the algorithm is (X, p). Let i0 be the least earner at time t. Clearly, i ∈ R(i0). If p(Xi \ jr) > (1 + ε)p(Xi0 ) for some alternating path P = (i0, j1, i1, . . . , jr, ir = i) in the MPB graph at (X, p), then Algorithm 1 will execute a transfer step along P . Thus, it must be that p(Xi \ jr) ≤ (1 + ε)p(Xi0 ). Lemma 2 and Lemma 3 imply that i is EF1 in X. Consequently i is EF1 in X and cannot be in V t . Thus, any agent in V t does not participate in the price drop.

(ii) We prove this by induction. Suppose for some t ≥ 0, we have Xt i ⊆ Xt0 for any i ∈ V t . This is vacuously true for t = 0. We will prove that any agent i who gains a chore cannot remain a violator. In other words, for any i ∈ V t+1 , Xt+1 ⊆ Xt .

If t is a price drop step, then Xt+1 = Xt and V t+1 = V t , so the claim is clearly true. Suppose t is a transfer step involving the alternating path P = (i0, j1, i1, . . . , jr, ir), with k ∈ [r -1] chosen as described. We showed in Lemma 6 that any agent iℓ where ℓ ∈ {k + 1, . . . , r - 1} is EF1 after the transfer. Hence, such an agent iℓ does not belong to V t+1 . For ir, we have Xt+1 ir ⊂ Xt ir . For any agent h /∈ P , we have Xt+1 h =Xth . Thus for any i ∈ V t+1 , Xt+1 i ⊆Xt i holds.

By the inductive hypothesis, we conclude that for any i ∈ V t+1 , Xt+1 i ⊆Xt i ⊆Xt0 .

(iii) Consider i ∈ V t and j ∈ Xt i . By the proof of (ii), we have Xt′ i ⊆ Xt′-1 i for all t′ ≤ t. Thus, j ∈ Xt′ i for all t′ ≤ t. That is, j remains with i in all steps until time t. By (i), i ∈ V t and has not undergone any price-drop until t. Thus, it must be that ptj = p0j .

The next lemma shows that Algorithm 1 cannot execute too many price drop steps. Intuitively, this follows from two observations: first, that each price drop step drops the price of at least one chore, and second, the price of each chore is bounded below due to the MPB condition and the fact that there exist chores assigned to agents in V who have not undergone a price drop. To obtain the pseudo-polynomial bound, we assume the instance is ε-perturbed (Definition 4).

Lemma 9. Algorithm 1 executes at most 2mlog1+ε ∆ price drop steps.

Next, we prove that Algorithm 1 cannot execute too many consecutive transfer steps without executing a price drop step. We prove this using two lemmas. First, we analyze consecutive price drops with a fixed least earner.

Lemma 10. The number of consecutive transfer steps with a fixed least earner and no price drop steps is at most O(n3 ).

Second, we analyze the number of times an agent can cease to be a least earner and become one again, in the absence of price drop steps.

Lemma 11. Suppose agent i ceases to be the least earner after a transfer step at time t. Let t′ be the earliest iteration after t when i becomes the least earner again. If no price drop steps occurred between t and t′ and the price vector remains p, then it is either the case that Xt′ i ⊋ Xt i , or p(Xt′ i ) ≥ (1 + ε)p(Xt i ).

Using the above two lemmas, we bound the number of successive transfer steps in Algorithm 1.

Lemma 12. The number of consecutive transfer steps without any price drop steps is at most O(n4m log1+ε ∆).

We can now bound the running time of Algorithm 1 using Lemmas 9 and 12.

Lemma 13. Algorithm 1 terminates in at most O(n4m2 (log1+ε ∆)2 ) iterations.

Together, Lemma 13 and Lemma 3 show that with ε = 1 6m∆ , Algorithm 1 computes an epistemic EF1 and PO allocation in O(n4m4∆2 log2 ∆) time. This proves Theorem 2.

4 Epistemic wEF1 and PO

We consider the case of asymmetric agents in this section. An instance is described by the tuple (N,M,D,w) where N,M, and D represent the agents, chores, and the disutility functions, and w ∈ Rn>0 represents the agent entitlements.

An allocation X is said to be wEF1 if for all i, h ∈ N, there is some j ∈ Xi s.t. di(Xi\j) wi ≤ di(Xh) wh . An allocation X is said to be epistemic wEF1 if for all i ∈ N, there is an allocation Y such that Yi = Xi, and for some j ∈ Xi, it holds that di(Xi\j) wi ≤ di(Xh) wh for any h ∈ N.

Our main result for the asymmetric setting is a pseudopolynomial time algorithm for computing an epistemic wEF1 and PO allocation, analogous to Theorem 2.

Theorem 3. Given an asymmetric chore division instance (N, M, D, w), an epistemic wEF1 and PO allocation can be computed in poly(n, m, ∆)-time.

The main difference with Algorithm 1 is that instead of the least earner, we consider the weighted least earner and the weighted earning while determining alterning paths for chore transfers. At a high-level, the run-time analysis of the algorithm uses same ingredients as that of Algorithm 1. In particular, Lemmas 3, 4, 7, 8, 9, and 10 continue to hold or extend to the asymmetric case in a straightforward manner. However, Lemmas 5, 6 and 11 need to be adapted carefully to the weighted setting.

5 Certifying Epistemic EF1

In this section, we study the computational complexity of the problem of certifying if a given allocation X is epistemic EF1 for a given agent i. We show that:

Theorem 4. The problem of determining if a given an allocation X is epistemic EF1 for a given agent i is NP-complete.

We note that this uses the same reduction used by [Caragiannis et al., 2023] for proving that determining if a given allocation is epistemic EFX for a given agent is NP-hard.

6 Discussion

In this paper, we presented a pseudo-polynomial time algorithm for computing an epistemic EF1 and Pareto-optimal allocation of indivisible chores under additive disutilities. Our approach builds on the competitive equilibrium framework, which guarantees economic efficiency and guides the transfer of chores from envious to envied agents. Establishing convergence requires overcoming various challenges; to this end, we develop several novel technical insights that exploit the distinctive structure of epistemic EF1 while carefully addressing the difficulties it introduces.

We conclude by highlighting several promising directions for future work. First, it remains open whether an epistemic EF1 and PO allocation can be computed in polynomial time, or whether it is computationally hard. Second, it would be interesting to investigate the compatibility of Pareto optimality with stronger or alternative fairness notions, such as epistemic EFX, approximate-EFX, or epistemic approximate-EFX. Finally, extending these guarantees to mixed manna settings involving both goods and chores poses a challenging and worthwhile direction for further research.

Acknowledgements

Jugal Garg was supported by NSF Grant CCF-2334461.