betaFeedback

WorksComputer Science

A Polynomial-Time Algorithm for Constant-Factor EFX Allocations of Chores

Abstract

We study the fair division of indivisible chores among agents with additive disutilities, focusing on the central fairness notion of envy-freeness up to any chore (EFX), and its multiplicative approximations. Although the existence of constant-factor approximations to EFX are known, computing such an allocation in polynomial time remained open. We resolve this question by giving an algorithm that, for every ε∈(0,1)\varepsilon\in(0,1), computes a (3+ε)(3+\varepsilon)-EFX allocation in time polynomial in the input length and 1/ε1/\varepsilon. Our result relies on two algorithmic contributions. First, we give a fully polynomial-time approximation scheme (FPTAS) for earning-restricted (ER) equilibria with equal earning requirements and arbitrary feasible chore earning limits. We develop a new nonconvex program with chore payouts and money-flow variables, and prove that every local maximum yields an exact ER equilibrium. We then give a mirror-ascent algorithm for this program and prove that it converges to an approximate ER equilibrium in polynomial time. Second, we give a new procedure that converts the approximate equilibrium into a (3+ε)(3+\varepsilon)-EFX-friendly allocation, a suitable starting point for the chore-swap framework of Garg and Murhekar (2026). The procedure uses a flexible price threshold to choose swap chores and their recipients together, overcoming a factor-four bottleneck in the earlier approaches while accommodating approximate earnings. We expect these ideas to be useful more broadly in fair division, including for goods and other fairness notions.

Introduction

Fair allocation is a fundamental problem studied across computer science, economics, operations research, and mathematics. It is concerned with allocating resources or responsibilities to agents with heterogeneous preferences in a fair manner. In this paper, we study the fair division of indivisible chores, which impose a disutility or cost on the agents receiving them. Examples include assigning household tasks, work shifts, and maintenance responsibilities. We assume agents have additive disutilities: every chore imposes a positive cost, and the disutility an agent incurs from a set of chores is the sum of her disutilities for its individual chores.

Envy-freeness (EF) is one of the most fundamental notions of fairness [14]. An allocation is envy-free if every agent prefers her own bundle to the bundle assigned to any other agent. Unfortunately, EF allocations need not exist when chores are indivisible, as can be seen by considering a single chore and two agents. This motivates relaxations of EF for the discrete setting. A compelling relaxation is envy-freeness up to any chore (EFX), which requires that every agent prefers her own bundle to any other agent’s bundle after the removal of any chore from her own bundle. Formally, an allocation X=(X1,…,Xn)X = (X_1,\ldots,X_n) is EFX if di(Xi∖{j})≤di(Xh)d_i(X_i \setminus\{j\}) \le d_i(X_h) for all agents i,hi,h and j∈Xij \in X_i; here did_i denotes agent ii’s additive disutility function and nn is the number of agents. EFX allocations of chores need not exist even for additive disutilities [21].

To provide meaningful fairness guarantees, it is therefore natural and important to investigate multiplicative approximations to EFX. In a λ\lambda-EFX allocation, where λ≥1\lambda\ge1, the above inequality is relaxed to di(Xi∖{j})≤λ⋅di(Xh)d_i(X_i \setminus\{j\}) \le\lambda\cdot d_i(X_h). Smaller values of λ\lambda give stronger fairness guarantees, with λ=1\lambda= 1 corresponding to exact EFX.

The first non-trivial approximation for general additive chores was obtained by Zhou and Wu [29], who gave a polynomial-time algorithm for computing an O(n2)O(n^2)-EFX allocation. Garg et al. [20] gave the first constant-factor existence result showing 4-EFX allocations always exist. Their approach was to define and prove the existence of fractional earning-restricted (ER) equilibria, round an ER equilibrium to a suitable integral allocation, and perform chore swaps until obtaining a 4-EFX allocation. More recently, Garg and Murhekar [16] improved the existence guarantee to 2-EFX through a general framework for chore swaps. Their framework begins with an allocation satisfying certain properties and converts it to an approximate-EFX allocation in polynomial time.

Despite these existence results, the question of computing a constant-approximate EFX allocation remained open. The main difficulty in extending previous approaches lies in finding a suitable initial solution. The approach of Garg et al. [20] begins with an ER equilibrium, whose existence proof uses a linear complementarity problem and a finite pivoting procedure. The 2-EFX result of Garg and Murhekar [16] instead uses price-supported allocations that are envy-free up to one chore (EF1), supplied by the existence theorem of Mahara [25], whose proof uses a fixed-point argument. For a constant number of agents, ER equilibria can be computed in polynomial time [20], as can EF1 and Pareto-optimal (PO) allocations [25]. These initial allocations enable polynomial time computation of constant-EFX allocations when nn is constant.

For general nn, however, these results do not give polynomial-time algorithms for the starting solutions. In particular, Garg et al. [20] identify approximate ER computation as the missing step that would turn their existence results into polynomial-time algorithms, with a small loss in the guarantees. Thus the constant-factor existence results have left a substantial gap from the O(n2)O(n^2) approximation attainable in polynomial time.

In this paper, we resolve this computational question for additive chores and any number of agents.

Theorem 1. For any chore division instance with positive additive disutilities and any ε∈(0,1)\varepsilon\in(0,1), a (3+ε)(3+\varepsilon)-EFX allocation can be computed in time polynomial in the input length and 1/ε1/\varepsilon.

Our result relies on two algorithmic contributions. First, we give a fully polynomial-time approximation scheme (FPTAS) for ER equilibria, resolving the computational obstacle identified by Garg et al. [20]. Second, we give a new polynomial-time algorithm that uses an approximate ER equilibrium to obtain a (3+ε)(3+\varepsilon)-EFX allocation. Our construction overcomes a factor-four bottleneck in the earlier method for reallocating chores, which persists even when the starting equilibrium is exact. We describe these contributions below.

Computing an Approximate ER Equilibrium. In an earning restricted market, agent ii aims to earn eie_i by performing chores of least disutility per unit of payment. Thus, agents are only assigned chores that minimize their disutility-to-price ratio, called the minimum pain-per-buck (MPB) condition. Each chore jj has an earning limit cjc_j on the total amount it can pay to the agents. At prices pp, it pays out min⁡{pj,cj}\min\{p_j,c_j\}; when its price exceeds this limit, it is only partially allocated. When earning caps cjc_j are large, this reduces to the standard Fisher market for chores.

Garg et al. [20] prove that an ER equilibrium exists if and only if ∑jcj≥∑iei\sum_j c_j \ge\sum_i e_i, using a linear complementarity formulation and a pivoting algorithm that terminates in finite time. However, polynomial-time computation of even an approximate ER equilibrium remained open. We give an FPTAS for ER markets with equal earning requirements ei=1e_i = 1 and arbitrary positive earning limits satisfying ∑jcj≥n\sum_j c_j \ge n.

Theorem 2. For every δ∈(0,1)\delta\in(0,1), an approximate ER equilibrium with unit earning requirements and arbitrary feasible positive chore limits can be computed in time polynomial in the input length and 1/δ1/\delta. Each agent earns an amount in [1−δ,1+δ][1-\delta,1+\delta], and MPB optimality, capped chore payouts, and total earnings hold exactly.

Earning limits separate a chore’s price from its total payout. In ordinary chore equilibria, every chore is fully allocated, so prices sum to the total earning requirement nn. With earning limits, a chore can be partially allocated and its payout is qj=min⁡{pj,cj}q_j = \min\{p_j,c_j\}, so prices need no longer sum to nn. We therefore work with the chore payouts qjq_j, which still sum to nn and satisfy the simple bounds qj≤cjq_j \le c_j.

These payout variables also appear in the spending-restricted extension of Shmyrev’s convex program for goods (Shmyrev, [28]; Cole et al., [11]). The program uses money flows bijb_{ij}, denoting the amount agent ii spends on good jj, and total spending qj=∑ibijq_j = \sum_i b_{ij}. It maximizes ∑i,jbijlog⁡vij−∑jqjlog⁡qj\sum_{i,j} b_{ij} \log v_{ij} - \sum_j q_j \log q_j over nonnegative money flows bb and total spending qq, subject to each agent spending one and the caps qj≤cjq_j \le c_j; here vijv_{ij} is agent ii’s value for good jj. Thus, the objective combines a term linear in the money flows with an entropy term depending only on total spending.

A natural adaptation of the goods program to chores replaces values by disutilities and maximization by minimization. Here, bijb_{ij} denotes the money agent ii earns from chore jj, and qj=∑ibijq_j = \sum_i b_{ij} is its total payout. However, minimizing this objective over both money flows and payouts need not give an equilibrium. Even with one agent and two identical chores with unit earning limits, it concentrates the entire payout on one chore, leaving the other unpaid.

Our key insight is to minimize over money flows for fixed payouts, while maximizing over the payouts themselves. For fixed qq, minimizing ∑i,jbijlog⁡dij\sum_{i,j} b_{ij} \log d_{ij}, subject to each agent earning one and each chore jj paying out qjq_j, is a minimum-cost flow problem. Its optimal dual supplies prices supporting MPB assignments. We then maximize this minimum flow cost minus the entropy term ∑jqjlog⁡qj\sum_j q_j \log q_j over feasible payouts. The resulting program, ERER-MaxMinMaxMin, is nonconvex, but we prove that every local maximum yields an exact ER equilibrium.

To obtain an efficient algorithm, we apply mirror ascent to this program. Each iteration computes an optimal flow and its supporting MPB prices. The mirror-ascent step has a simple market interpretation: scale these prices so that their capped payouts sum to nn. Since the new payouts can differ from those prescribed to the flow computation, we rescale the money received from each chore to match its new payout. This preserves MPB assignments and satisfies the earning restrictions exactly, but may change individual earnings. We stop when every agent’s earning is within δ\delta of one; otherwise, we repeat with the new payouts. The main analytical challenge is to relate these earning errors to progress in the objective and thereby bound the number of iterations, even when some chore payouts are arbitrarily small. Our analysis in § 3 establishes polynomial-time convergence, yielding an FPTAS for ER equilibria.

Constructing an EFX-Friendly Allocation. To obtain a (3+ε)(3+\varepsilon)-EFX allocation from the approximate equilibrium, we use the chore-swap framework of Garg and Mulherkar [16]. An agent can exchange one chore, called her swap chore, for a least-disutility bundle while retaining her other chores, which form her residual bundle. The framework computes a λ\lambda-EFX allocation in polynomial time from a suitable starting allocation, called λ\lambda-EFX-friendly. In such an allocation, the inactive agents are already λ\lambda-envy-free, while each active agent has one swap chore and a residual bundle of small disutility relative to every inactive bundle and every swap chore. Our task is therefore to construct a (3+ε)(3+\varepsilon)-EFX-friendly allocation.

Garg et al. [20] show that an exact ER equilibrium can be rounded to an integral allocation, which is subsequently modified to yield a 4-EFX-friendly allocation. There are two challenges in extending this approach. First, our FPTAS gives only an approximate ER equilibrium. Second, the reallocation must improve upon factor four. We address the first challenge by extending the analysis of their rounding algorithm to approximate earnings. With earning limits 1/21/2 and exact earnings, each agent receives at most two chores of price above 1/21/2. However, an arbitrarily small earning error can cause a discrete jump from two such chores to three.

The earlier reallocation uses a fixed price threshold of 1/21/2 to determine which chores are eligible to serve as swap chores. Unfortunately, this approach has a concrete bottleneck at factor four, even when the starting equilibrium is exact. Our key insight is to choose the swap chores and their recipients together using a flexible price threshold determined by the rounded allocation. As the threshold increases, some chores initially eligible for swaps rejoin their original residual bundles, allowing agents with large residual bundles to remain inactive. The challenge is to satisfy two requirements simultaneously: every remaining swap chore needs a recipient with a sufficiently small residual bundle, and every agent whose residual bundle has price below the threshold must receive a swap chore. Our algorithm ensures that every remaining swap chore has an eligible recipient; a counting argument guarantees that enough chores remain for all agents who need one.

Together with the rounding bounds, this construction gives a 3-EFX-friendly allocation from an exact ER equilibrium, with the factor increasing by only O(δ)O(\delta) for a δ\delta-approximate ER equilibrium. Choosing δ\delta sufficiently small relative to ε\varepsilon and applying the chore-swap framework yields a (3+ε)(3+\varepsilon)-EFX allocation in polynomial time, proving Theorem 1. We present the rounding analysis and the new construction in § 4.

Related Work

EFX for restricted chore instances. Several works obtain stronger EFX guarantees by restricting the number of agents, the number of chores, or the disutility functions. For m≤2nm \le2n, Kobayashi et al. [22] give a matching-based polynomial-time algorithm for exact EFX; Garg et al. [20] subsequently give a simpler algorithm based on chore swaps. For three agents, Afshinmehr et al. [1] compute a 2-EFX allocation in polynomial time, even for subadditive cost functions. For bivalued instances, where every disutility is in {1,k}\{1,k\} for some k>1k>1, Lin et al. [23] compute a (2−1/k)(2-1/k)-EFX allocation while preserving fractional Pareto optimality.

Fair and efficient chore allocations. Prior to the general existence result of Mahara [25], polynomial-time algorithms for simultaneously achieving EF1 and PO were known for structured instances, including bivalued preferences ([17, 12]). Mahara proves the existence of EF1 and fractionally Pareto-optimal allocations for general additive chores, combining the KKM lemma with a discrete allocation procedure. The fixed-point argument supplies suitable supporting weights and prices, after which the discrete procedure obtains the fairness guarantee. He also gives a polynomial-time algorithm for EF1 and PO when the number of agents is constant. His existence result supplies the starting point used by Garg and Murhekar [16] to obtain 2-EFX. Exact EFX and PO, however, can be incompatible even for bivalued chores ([21]). Computing EF1 and PO allocations in polynomial time for general instances remains an interesting open question.

Computing fractional chore equilibria. For ordinary chore markets, Boodaghians et al. [6] give an FPTAS for competitive equilibrium with equal incomes using an exterior-point method. Chaudhury et al. [7] give a combinatorial FPTAS based on price updates and reallocations along MPB edges. Chaudhury et al. [8] develop a dual equilibrium formulation and a greedy Frank–Wolfe algorithm whose iterations solve linear programs. Chen et al. [9] give a log-price difference-of-convex formulation, study a regularized algorithm, and develop a smoothed gradient method. These works establish several approaches for approximating chore equilibria, but their market model requires full allocation of every chore. Earning restrictions instead make the allocated supply of a capped chore depend on its price. Our algorithm uses minimum-cost flows and a mirror-ascent step to maintain exact MPB optimality and exact capped payouts, while allowing small errors in individual earnings. § 3.1 explains why earning restrictions require a different formulation, and § 3 gives the algorithm and its analysis.

Spending-restricted equilibria for goods. The goods analogue of an earning limit is a spending limit on each good. Cole and Gkatzelis [10] introduce spending-restricted equilibria and use them to obtain a constant-factor approximation for maximizing Nash social welfare with indivisible goods. Cole et al. [11] give convex programming formulations of these markets, including an extension of Shmyrev’s money formulation (Shmyrev, [28]). Our max-min program retains the capped payout domain and entropy term of this formulation. The difference lies in agent optimality: for chores, the inner flow problem minimizes the disutility-based cost, and its value is convex in the payouts. The resulting outer maximization is nonconcave. We use an optimal flow dual and a mirror-ascent step to increase its objective, with progress controlled by the error in agent earnings.

Independent work. In independent contemporaneous work, Qin et al. [27] obtain the same polynomial-time (3+ε)(3 + \varepsilon)-EFX guarantee. Their “capped-price structure” reformulates the ER conditions of Garg et al. [20] using normalized chore shares and an approximate MPB condition. Their FPTAS uses multiplicative weight updates guided by max-flow-min-cut, and is stated for a common earning limit for the chores. Our conceptual contribution is a non-convex program whose local maxima yield ER equilibria. Mirror ascent on this program gives an FPTAS, and moreover maintains exact MPB and supports arbitrary earning limits.

For the conversion from approximate ER to approximate EFX, their “adaptive packet reallocation” extends the chore-swap framework of Garg and Murhekar [16] to agents with two swap chores. Our conversion retains the rounding algorithm of Garg et al. [20] and uses a flexible price threshold to select swap chores and their recipients, constructing an EFX-friendly allocation with one swap chore per active agent.

Organization of the Paper. § 2 introduces our notation and formal definitions. We describe and analyze the FPTAS for ER with equal earnings in § 3. § 4 gives the rounding analysis and the construction of an EFX-friendly allocation.

Preliminaries

Let [n]={1,2,…,n}[n] = \{1,2,\ldots,n\} for a positive integer nn.

Problem instance. A chore division instance (N,M,D)(N,M,D) consists of a set N=[n]N = [n] of agents, a set M=[m]M = [m] of indivisible chores, and a list D={di}i∈ND = \{d_i\}_{i \in N} of additive disutility functions.

We let dij∈Q>0d_{ij} \in\mathbb{Q}_{>0} denote the disutility of chore jj for agent ii, and define the disutility ratio

R=max⁡i∈Nmax⁡j∈Mdijmin⁡j∈Mdij.R = \max_{i \in N} \frac{\max_{j \in M} d_{ij}}{\min_{j \in M} d_{ij}}.

For S⊆MS \subseteq M, we have di(S)=∑j∈Sdijd_i(S) = \sum_{j \in S} d_{ij}.

An allocation X=(X1,…,Xn)X = (X_1, \ldots, X_n) is a partition of the chores, where XiX_i denotes the bundle assigned to agent ii. A fractional allocation x∈R≥0n×mx \in\mathbb{R}_{\geq0}^{n \times m} assigns a fraction xijx_{ij} of chore jj to agent ii, with ∑ixij≤1\sum_i x_{ij} \leq1 for each chore jj. Agent ii’s disutility under fractional allocation xx is di(xi)=∑jdijxijd_i(x_i) = \sum_j d_{ij}x_{ij}. Allocations are integral unless stated otherwise.

Fairness notions. For λ≥1\lambda\geq1, agent ii is λ\lambda-envy-free (λ\lambda-EF) in allocation XX if di(Xi)≤λ⋅di(Xh)d_i(X_i) \leq\lambda\cdot d_i(X_h) for every h∈Nh \in N. Agent ii is λ\lambda-EFX in allocation XX if

di(Xi∖{j})≤λ⋅di(Xh)for every h∈N and every j∈Xi.d_i(X_i \setminus\{j\}) \leq\lambda\cdot d_i(X_h) \qquad\text{for every } h \in N \text{ and every } j \in X_i.

An allocation is λ\lambda-EF or λ\lambda-EFX if the above condition holds for every agent. By definition, an agent assigned a singleton bundle is EFX. For a positive integer kk, an allocation XX is λ\lambda-EFkk, if, for every i,h∈Ni,h \in N, there exists S⊆XiS \subseteq X_i with ∣S∣≤k|S| \leq k such that di(Xi∖S)≤λ⋅di(Xh)d_i(X_i \setminus S) \leq\lambda\cdot d_i(X_h). When λ=k=1\lambda= k = 1, this becomes the well-studied EF1 fairness notion.

Prices and MPB allocations. Let p=(p1,…,pm)∈R>0mp = (p_1, \ldots, p_m) \in\mathbb{R}_{>0}^{m} be chore prices, where pjp_j is the payment per unit of chore jj. Let p(S)=∑j∈Spjp(S) = \sum_{j \in S} p_j and p(xi)=∑jpjxijp(x_i) = \sum_j p_jx_{ij} denote the prices of bundles SS and xix_i, respectively. The minimum pain-per-buck (MPB) ratio of agent ii and her set of MPB chores are

αi=min⁡j∈Mdijpj,MPBi={j∈M:dijpj=αi}.\alpha_i = \min_{j \in M} \frac{d_{ij}}{p_j}, \qquad\mathrm{MPB}_i = \left\{j \in M : \frac{d_{ij}}{p_j} = \alpha_i\right\}.

An allocation-price pair (x,p)(x,p) is MPB if xij>0x_{ij} > 0 implies j∈MPBij \in\mathrm{MPB}_i for all i,ji,j, i.e., an agent only performs chores that minimize her disutility to payment ratio. For an integral allocation, this means Xi⊆MPBiX_i \subseteq\mathrm{MPB}_i for every ii.

Scaling an agent’s disutilities by a positive constant preserves all her multiplicative fairness comparisons and her MPB chores. Thus, given an MPB allocation, we may divide agent ii’s disutilities by αi\alpha_i and obtain

dij≥pjfor all i,j,dij=pjwhen j∈MPBi.(1)d_{ij} \geq p_j \quad\text{for all } i,j, \qquad d_{ij} = p_j \quad\text{when } j \in\mathrm{MPB}_i. \tag*{(1)}

We use this normalization when analyzing the rounding and chore-swap algorithms.

For an integral allocation XX and a positive integer kk, let

p−k(Xi)=min⁡S⊆Xi∣S∣≤kp(Xi∖S).p_{-k}(X_i) = \min_{\substack{S \subseteq X_i\\ |S| \leq k}} p(X_i \setminus S).

This is the price remaining after removing up to kk highest-price chores from XiX_i. The pair (X,p)(X,p) is λ\lambda-price-EFkk (λ\lambda-pEFkk) if p−k(Xi)≤λp(Xh)p_{-k}(X_i) \leq\lambda p(X_h) for all i,hi,h. An MPB allocation that is λ\lambda-pEFkk is also λ\lambda-EFkk, by (1). For λ=k=1\lambda= k = 1, this becomes the price-EF1 (pEF1) condition introduced by Barman et al. [3] and used in several works on fair and efficient allocation Barman and Krishnamurthy [2]; Ebadian et al. [12]; Garg and Murhekar [18]; Garg et al. [17, 19, 20] (2023); Mahara [24, 25].

Pareto Optimality. An allocation XX is Pareto-optimal (PO) if no integral allocation YY satisfies di(Yi)≤di(Xi)d_i(Y_i) \leq d_i(X_i) for every agent ii, with strict inequality for at least one agent. It is fractionally Pareto-optimal (fPO) if no complete fractional allocation yy satisfies di(yi)≤di(Xi)d_i(y_i) \leq d_i(X_i) for every agent ii, with strict inequality for at least one agent. Here, completeness means that ∑iyij=1\sum_i y_{ij} = 1 for every chore jj. Thus fPO implies PO.

By the First Welfare Theorem [26], every complete MPB allocation is fPO. The Second Welfare Theorem [26] gives the converse: for every fPO allocation XX, there exists a positive price vector pp such that (X,p)(X,p) is MPB. Thus an allocation is fPO if and only if it admits supporting MPB prices.

Earning-Restricted Equilibria

An earning-restricted (ER) market (N,M,D,e,c)(N, M, D, e, c) consists of a chore division instance (N,M,D)(N, M, D), agent earning requirements ei∈Q>0e_i \in\mathbb{Q}_{>0}, and chore earning limits or caps cj∈Q>0c_j \in\mathbb{Q}_{>0}. Each agent ii aims to earn eie_i by performing chores of least possible disutility, while the agents are restricted to collectively receive at most cjc_j from chore jj. An equilibrium specifies a fractional allocation and prices that meet these requirements.

Definition 1 (ER equilibrium, Garg et al., [20]). A pair (x,p)(x,p) is an earning-restricted equilibrium if

(i) (x,p)(x,p) is MPB and p(xi)=eip(x_i)=e_i for every agent ii;

(ii) ∑ixij=min⁡{1,cj/pj}\sum_i x_{ij}=\min\{1,c_j/p_j\} for every chore jj.

Condition (i) requires each agent to earn her requirement using only MPB chores. It enforces agent optimality: the bundle xix_i minimizes ii’s disutility among all bundles z≥0z \ge0 that meet its earning requirement through p(z)≥eip(z) \ge e_i.

Condition (ii) imposes the earning restriction: if pj≤cjp_j \le c_j, chore jj is fully allocated and pays out pjp_j; otherwise, only a cj/pjc_j/p_j fraction is allocated and the payout is cjc_j. Garg et al. [20] show that an ER equilibrium exists if and only if ∑iei≤∑jcj\sum_i e_i \le\sum_j c_j. Our algorithmic result concerns equal earning requirements. Hence, we normalize them to ei=1e_i=1 for all ii, and assume ∑jcj≥n\sum_j c_j \ge n.

We use the following approximation of ER equilibrium, which allows small errors in the agent earnings while retaining the MPB condition and the earning restrictions exactly.

Definition 2 (Approximate ER equilibrium). For δ∈(0,1)\delta\in(0,1), a pair (x,p)(x,p) is a δ\delta-approximate ER equilibrium with unit earning requirements if

1−δ≤p(xi)≤1+δ(∀i∈N),(2)1-\delta\le p(x_i) \le1+\delta\qquad(\forall i \in N), \tag*{(2)}
xij>0⟹j∈MPBi,(∀i∈N, ∀j∈M),(3)x_{ij}>0 \Longrightarrow j \in\mathrm{MPB}_i,\qquad(\forall i \in N,\ \forall j \in M), \tag*{(3)}
∑ixij=min⁡{1,cj/pj}(∀j∈M),(4)\sum_i x_{ij}=\min\{1,c_j/p_j\}\qquad(\forall j \in M), \tag*{(4)}
∑ip(xi)=n.(5)\sum_i p(x_i)=n. \tag*{(5)}

Remark 1 (The total earning constraint). Summing Eq. (2) over all agents gives n(1−δ)≤∑ip(xi)≤n(1+δ)n(1-\delta) \le\sum_i p(x_i) \le n(1+\delta). The usual relaxation of ER equilibrium allows the total earning to vary within this range, whereas Eq. (5) requires it to equal nn. Our algorithm maintains this stronger property, so we include it in the definition for convenience, and use it throughout the paper.

Money Flows. It is convenient to describe our algorithm and its analysis in terms of money flow variables instead of allocation variables. Let bijb_{ij} denote the earning of agent ii from chore jj, and let qjq_j denote the total payout of chore jj. For an allocation (x,p)(x,p), these quantities are given by

bij=pjxij,qj=∑ibij.(6)b_{ij}=p_jx_{ij},\qquad q_j=\sum_i b_{ij}. \tag*{(6)}

In these variables, the agent earning requirement becomes ∑jbij=ei\sum_j b_{ij}=e_i, and the earning restriction becomes qj=min⁡{pj,cj}q_j=\min\{p_j,c_j\}. Since prices are positive, bij>0b_{ij}>0 if and only if xij>0x_{ij}>0, so the MPB condition is preserved as well. Consequently, the approximate ER conditions can equivalently be written as

1−δ≤∑jbij≤1+δ(i∈N),bij>0⟹j∈MPBi(i∈N, j∈M),∑ibij=qj=min⁡{pj,cj}(j∈M),∑jqj=n.(7)\begin{aligned} 1-\delta&\le\sum_j b_{ij} \le1+\delta&& (i\in N),\\ b_{ij}>0 &\Longrightarrow j\in\mathrm{MPB}_i && (i\in N,\ j\in M),\\ \sum_i b_{ij} &=q_j=\min\{p_j,c_j\} && (j\in M),\\ \sum_j q_j&=n. \tag*{(7)} \end{aligned}

We will describe our equilibrium algorithm using these money flows. When bb and pp are specified, each chore’s payout is qj=∑ibijq_j=\sum_i b_{ij}, and we abbreviate the solution as (p,b)(p,b). Conversely, given money flows and prices satisfying the above conditions, define xij=bij/pjx_{ij}=b_{ij}/p_j. The total fraction of chore jj allocated is qj/pj=min⁡{1,cj/pj}≤1q_j/p_j=\min\{1,c_j/p_j\}\le1, and the earnings and MPB assignments are unchanged. Thus (x,p)(x,p) satisfies Definition 2.

An FPTAS for ER Equilibria

In this section, we design Algorithm 1 for computing an approximate ER equilibrium and prove its polynomial running time. We assume that ei=1e_i=1 for every agent, that all disutilities and earning limits are positive, and that ∑jcj≥n\sum_j c_j\ge n. Our algorithm returns money flows and prices satisfying (7), which are equivalent to the conditions in Definition 2. Let R=max⁡i(max⁡jdij/min⁡jdij)R=\max_i(\max_j d_{ij}/\min_j d_{ij}) denote the largest ratio between an agent’s maximum and minimum disutility.

Theorem 3. Let (N,M,D,e,c)(N,M,D,e,c) be an ER market with unit earning requirements and ∑jcj≥n\sum_j c_j\ge n. For any δ∈(0,1)\delta\in(0,1), Algorithm 1 computes a δ\delta-approximate ER equilibrium using at most

1+⌈4nlog⁡(mR)δ2⌉1+\left\lceil\frac{4n\log(mR)}{\delta^2}\right\rceil

minimum-cost flow computations. Each iteration takes polynomial time, so the algorithm is an FPTAS. If ∑jcj=n\sum_j c_j=n, one minimum-cost flow computation gives an exact ER equilibrium.

A Mathematical Program for ER Equilibria

A natural source of inspiration for computing an approximate ER equilibrium lies in algorithms for competitive equilibrium (CE) of chores without earning limits [6, 8, 9]. These algorithms build on adaptations of convex programming formulations for goods. To build intuition, we first describe these formulations and the difficulties that arise when adapting them to ER equilibria.

Consider a goods market in which every agent has budget one and value vij>0v_{ij}>0 for good jj.1 Write vi(xi)=∑jvijxijv_i(x_i)=\sum_j v_{ij}x_{ij}. A CE maximizes the Nash product of agent values, or equivalently their sum of logarithms, as captured by the Eisenberg–Gale (EG) convex program [13]. The program and its dual are shown below; we omit an additive constant from the dual objective.

(EG)max⁡x∑ilog⁡vi(xi)subject to∑ixij≤1(j∈M),x≥0(EG-Dual)min⁡p,β∑jpj−∑ilog⁡βisubject topj≥βivij(i,j),p≥0,β>0.(8)\begin{aligned} \text{(EG)}\qquad&\max_x && \sum_i \log v_i(x_i) \\ &\text{subject to} && \sum_i x_{ij} \le1 \quad(j \in M),\\ &&& x \ge0 \end{aligned} \qquad \begin{aligned} \text{(EG-Dual)}\qquad&\min_{p,\beta} && \sum_j p_j-\sum_i\log\beta_i\\ &\text{subject to} && p_j\ge\beta_i v_{ij}\quad(i,j),\\ &&& p\ge0,\quad\beta>0. \tag*{(8)} \end{aligned}

The primal variables describe the allocation, while the dual variables pjp_j are the prices of goods and βi\beta_i is the reciprocal of agent ii’s maximum bang-per-buck (MBB) ratio. Their optimality conditions ensure that every agent spends her budget on MBB goods and every good is fully allocated.

For chores, the analogous primal program minimizes the sum of log disutilities, and is shown below as EG-Chores. Bogomolnaia et al. [5] show that the KKT points of EG-Chores with positive disutility for every agent correspond to CE. In particular, every local minimum in this positive-disutility domain yields a CE. At these points, the supply constraints are tight and all chores are fully allocated.

(EG-Chores)min⁡x∑ilog⁡di(xi)subject to∑ixij≥1(j∈M),x≥0(EG-Chores-Dual)max⁡p,β∑jpj−∑ilog⁡βisubject topj≤βidij(i,j),p≥0,β>0.(9)\begin{aligned} \text{(EG-Chores)}\qquad&\min_x && \sum_i\log d_i(x_i)\\ &\text{subject to} && \sum_i x_{ij}\ge1\quad(j\in M),\\ &&&x\ge0 \end{aligned} \qquad \begin{aligned} \text{(EG-Chores-Dual)}\qquad&\max_{p,\beta} && \sum_jp_j-\sum_i\log\beta_i\\ &\text{subject to} &&p_j\le\beta_i d_{ij}\quad(i,j),\\ &&&p\ge0,\quad\beta>0. \tag*{(9)} \end{aligned}

Chaudhury et al. [8] introduce a corresponding dual-like program by reversing the direction of optimization and the price inequalities in EG-Dual, shown above as EG-Chores-Dual. Here βi\beta_i represents the reciprocal MPB ratio, and the name EG-Chores-Dual refers to the analogy with goods; it is not a Lagrangian dual of EG-Chores. Chaudhury et al. [8] establish the corresponding KKT characterization for EG-Chores-Dual.

However, both chore programs have difficulties for iterative optimization. The primal objective tends to −∞-\infty as an agent’s disutility approaches zero, and the dual-like objective tends to +∞+\infty as some βi\beta_i approaches zero. These divergent values near zero are called poles. The dual-like objective is also unbounded along directions in which prices increase. Thus improving either objective can lead away from an equilibrium. To avoid these directions, Chaudhury et al. [8] add the constraint ∑jpj=n\sum_j p_j=n to EG-Chores-Dual. This constraint is redundant at CE since all chores are fully allocated and each agent earns one. Chaudhury et al. [8] show that adding it preserves the KKT characterization while removing the poles and unbounded improving directions, thereby enabling an algorithm for approximate CE.

Unfortunately, it is not clear how to extend these formulations to accommodate earning restrictions. In an ER equilibrium, only a min⁡{1,cj/pj}\min\{1,c_j/p_j\} fraction of chore jj is allocated, so the total earning condition becomes ∑jmin⁡{pj,cj}=n\sum_j\min\{p_j,c_j\}=n. Adding pj≤cjp_j\le c_j would bound prices rather than payouts and could exclude valid ER equilibria with pj>cjp_j>c_j. Moreover, the price-sum constraint ∑jpj=n\sum_jp_j=n may exclude every ER equilibrium, as the following example shows.

Example 1 (Price normalization). Consider two chores and one agent with disutilities (1,4)(1,4), earning requirement one, and earning limits (1/2,1/2)(1/2,1/2). The ordinary chore equilibrium has prices (1/5,4/5)(1/5,4/5). If we impose the earning limits at these prices, the total payout is 1/5+1/2=7/101/5+1/2=7/10, and the agent cannot earn one. In an ER equilibrium, both chores must pay out 1/21/2, and the MPB condition requires their prices to be in ratio 1:41 : 4. Thus prices (1/2,2)(1/2, 2) support an ER equilibrium with allocation (1,1/4)(1, 1/4). Moreover, every ER price vector has price sum at least 5/25/2. Hence, imposing a price sum of one would exclude every ER equilibrium.

Earning limits also prevent a direct adaptation of price updates that preserve the allocated quantities by scaling prices and money flows together. Once a chore’s payout reaches its earning limit, increasing its price must reduce its total quantity allocated.

Example 2 (Scaling prices and money flows). Consider two chores and two agents with identical disutilities (1,3)(1, 3), unit earning requirements, and earning limits (1,1)(1, 1). Prices (1,3)(1, 3) and earnings bij=1/2b_{ij}=1/2 for all i,ji,j form an ER equilibrium. The first chore is fully allocated, while one-third of the second chore is allocated. Doubling the second chore’s price and all earnings from it preserves this allocation, but increases its payout to two and violates its earning limit. If we instead keep its payout at one, doubling its price halves the quantity allocated.

The two examples suggest that we should work with the total payout qjq_j of a chore jj, keeping it distinct from its price pjp_j. In these variables, we can impose the earning limits directly through qj≤cjq_j \le c_j and maintain the total payout ∑jqj=n\sum_j q_j = n. We must then find supporting MPB prices that satisfy qj=min⁡{pj,cj}q_j = \min\{p_j,c_j\}.

Connection to Spending-Restricted Equilibria for Goods. For goods, the spending-restricted (SR) equilibrium has precisely this relation between prices and total spending. In this model, an agent with unit budget buys goods to maximize her value, while the total spending on good jj is restricted to cjc_j. If its price exceeds cjc_j, only a cj/pjc_j/p_j fraction of the good is sold. Cole et al. [11] connect this model to the convex program of Shmyrev [28]. Applying the change of variables (p,β)↦(log⁡p,−log⁡β)(p,\beta) \mapsto(\log p,-\log\beta) to EG-Dual and then taking its dual gives Shmyrev’s formulation for ordinary goods markets. Its variables are qjq_j and bijb_{ij}, denoting the total spending on good jj and the money agent ii spends on good jj, respectively. Since this program has money-flow variables, it can be adapted to incorporate spending limits. Adding the constraints qj≤cjq_j \le c_j to Shmyrev’s program gives the SR program of Cole et al. [11]:

max⁡b,q∑i,jbijlog⁡vij−∑jqjlog⁡qjsubject to∑jbij=1(i∈N),∑ibij=qj(j∈M),0≤qj≤cj(j∈M),bij≥0(i∈N, j∈M).(10)\begin{aligned} \max_{b,q}\quad& \sum_{i,j} b_{ij}\log v_{ij} - \sum_j q_j\log q_j \\ \text{subject to}\quad& \sum_j b_{ij}=1 && (i\in N),\\ & \sum_i b_{ij}=q_j && (j\in M),\\ & 0\le q_j\le c_j && (j\in M),\\ & b_{ij}\ge0 && (i\in N,\ j\in M). \tag*{(10)} \end{aligned}

We use the convention 0log⁡0=00\log0=0 for the entropy term H(q)=∑jqjlog⁡qjH(q)=\sum_j q_j\log q_j. The first two constraints already imply ∑jqj=n\sum_j q_j=n. With these bounds, prices are recovered from the dual variables and satisfy qj=min⁡{pj,cj}q_j=\min\{p_j,c_j\}. The optimality conditions also ensure that agents buy only MBB goods.

Adapting Shmyrev’s Program to Chores. Similar to EG-Chores-Dual, an adaptation of the SR program to chores replaces values by disutilities and maximization by minimization, giving

(Shmyrev-Chores)

min⁡b,q ∑i,jbijlog⁡dij−∑jqjlog⁡qjsubject to∑jbij=1(i∈N),\min_{b,q}\ \sum_{i,j} b_{ij}\log d_{ij}-\sum_j q_j\log q_j \quad\text{subject to}\quad \sum_j b_{ij}=1\quad(i\in N),
∑ibij=qj(j∈M),\sum_i b_{ij}=q_j\quad(j\in M),
0≤qj≤cj(j∈M),0\le q_j\le c_j\quad(j\in M),
bij≥0(i∈N, j∈M).(11)b_{ij}\ge0\quad(i\in N,\ j\in M). \tag*{(11)}

At first glance, this program may seem promising since it has a bounded objective, unlike EG-Chores. However, its optima need not be ER equilibria!

Example 3. Consider two chores and one agent with disutilities (1,1)(1,1) and earning limits (1,1)(1,1). Its objective is −q1log⁡q1−q2log⁡q2-q_1\log q_1-q_2\log q_2, which is minimized at payouts (1,0)(1,0) or (0,1)(0,1). However, the ER equilibrium has payouts and prices (1/2,1/2)(1/2,1/2).

Thus reversing the direction of optimization for the entire program does not give the desired characterization. This example isolates the choice of chore payouts: with only one agent, the money she receives from each chore is necessarily b1j=qjb_{1j}=q_j. Minimizing the objective concentrates all the payout on one chore, leaving the other with no payment. On the other hand, maximizing it gives equal payouts, as required for these identical chores. The reason for maximizing becomes clearer when the chores have different disutilities. A payout specifies how much money a chore provides; it is not the disutility incurred by an agent. An uncapped chore with higher disutility must have a proportionally higher price to be equally attractive to the agent. The following example shows how the maximization achieves this and how earning limits change the resulting allocation.

Example 4 (Choosing chore payouts). Consider two chores and one agent with disutilities (1,2)(1,2) and earning limits (1,1)(1,1). Since b1j=qjb_{1j}=q_j, maximizing the objective amounts to

max⁡q1,q2 q1log⁡1q1+q2log⁡2q2\max_{q_1,q_2}\ q_1\log\frac{1}{q_1}+q_2\log\frac{2}{q_2}
subject toq1+q2=1,\text{subject to}\quad q_1+q_2=1,
q1,q2≥0.q_1,q_2\ge0.

The maximizer is (q1,q2)=(1/3,2/3)(q_1,q_2)=(1/3,2/3). Taking these payouts as prices makes both chores MPB, since d11/p1=d12/p2=3d_{11}/p_1=d_{12}/p_2=3. Both chores are fully allocated and the agent earns one.

Now reduce the second chore’s earning limit to 1/21/2. Maximizing the same objective subject to this cap gives payouts (1/2,1/2)(1/2,1/2). These payouts cannot themselves serve as prices, since at equal prices the agent would prefer the first chore. Instead, prices (1/2,1)(1/2,1) make both chores MPB and induce precisely these payouts. The agent performs all of the first chore and half of the second. Thus the capped chore retains a higher price even though its payout cannot exceed 1/21/2.

The above examples suggest that maximizing over chore payouts, rather than minimizing, is the better choice. Unfortunately, the picture is more complicated with several agents, since we must also decide how to distribute each chore’s payout among them. Agent ii receives bijb_{ij} of the total payout qjq_j from chore jj, and earns one in total. For fixed payouts qq, we must choose the money flows bijb_{ij} to ensure agent optimality, i.e., the MPB condition. We show that minimizing ∑i,jbijlog⁡dij\sum_{i,j} b_{ij}\log d_{ij} over these money flows achieves this purpose: its optimal flows are exactly those that admit supporting MPB prices. Having obtained these assignments, we choose the chore payouts by maximizing the resulting value minus the entropy term, as motivated by Example 4.

A Mathematical Program for ER Equilibrium. With the above intuition, we introduce our program for ER equilibria. We set up some notation first. Let QQ be the set of feasible chore payouts:

Q={q∈R≥0m:qj≤cj, ∑jqj=n}.(12)Q = \left\{q \in\mathbb{R}_{\ge0}^{m} : q_j \le c_j,\ \sum_j q_j = n\right\}. \tag*{(12)}

For fixed q∈Qq \in Q, we distribute the payouts by solving the following program:

C(q)=min⁡b≥0∑i,jbijlog⁡dijC(q) = \min_{b \ge0} \sum_{i,j} b_{ij}\log d_{ij}
subject to∑jbij=1(i∈N),∑ibij=qj(j∈M).(13)\begin{aligned} \text{subject to}\quad&\sum_j b_{ij} = 1 && (i \in N),\\ &\sum_i b_{ij} = q_j && (j \in M). \tag*{(13)} \end{aligned}

This is a minimum-cost flow problem: the constraints require each agent to earn one and each chore jj to pay out qjq_j, and sending one unit from chore jj to agent ii has cost log⁡dij\log d_{ij}. The problem is feasible for every q∈Qq \in Q, since bij=qj/nb_{ij} = q_j/n satisfies these constraints. Let B(q)B(q) denote its set of feasible money flows.

Our program for ER equilibria, termed ER-MaxMin, is presented below.

(ER-MaxMin)

max⁡q{min⁡b∈B(q)∑i,jbijlog⁡dij−∑jqjlog⁡qj}\max_q \left\{\min_{b \in B(q)} \sum_{i,j} b_{ij}\log d_{ij} - \sum_j q_j\log q_j\right\}
subject to∑jqj=n,0≤qj≤cj(j∈M).(14)\begin{aligned} \text{subject to}\quad&\sum_j q_j = n,\\ &0 \le q_j \le c_j && (j \in M). \tag*{(14)} \end{aligned}

Unlike the SR program for goods Eq. (10), ER-MaxMin is generally nonconvex. Nevertheless, we prove that every local maximum of the ER-MaxMin program can be transformed to an ER equilibrium. To prove this, we first establish the MPB guarantee of the solution to the flow problem Eq. (13) via its dual. Writing its variables as log⁡αi\log\alpha_i and log⁡wj\log w_j corresponding to the agent and chore constraints in Eq. (13), we obtain

C(q)=max⁡α,w∑ilog⁡αi+∑jqjlog⁡wjC(q) = \max_{\alpha,w} \sum_i \log\alpha_i + \sum_j q_j \log w_j
subject toαiwj≤dij(i∈N, j∈M),α>0,w>0.(15)\begin{aligned} \text{subject to}\quad&\alpha_i w_j \le d_{ij} && (i \in N,\ j \in M),\\ &\alpha> 0,\quad w > 0. \tag*{(15)} \end{aligned}

This is a linear program in log⁡αi\log\alpha_i and log⁡wj\log w_j. The logarithmic costs are what give the desired MPB guarantee: the additive dual inequalities become αiwj≤dij\alpha_i w_j \le d_{ij} after exponentiation.

Lemma 1 (Minimum-cost flows and MPB prices). For every q∈Qq \in Q, a flow b∈B(q)b \in\mathcal{B}(q) is optimal if and only if it admits supporting MPB prices. Every optimal dual (α,w)(\alpha,w) supplies such prices ww for every optimal flow, with αi\alpha_i equal to agent ii’s MPB ratio.

Proof. For any optimal flow bb and optimal dual (α,w)(\alpha,w), complementary slackness gives

dijwj≥αi,bij>0⟹dijwj=αi.\frac{d_{ij}}{w_j} \geq\alpha_i,\qquad b_{ij}>0 \Longrightarrow\frac{d_{ij}}{w_j}=\alpha_i.

Thus agents receive money only from their MPB chores. Conversely, if a feasible flow b∈B(q)b \in\mathcal{B}(q) is MPB at some prices ww, then its MPB ratios give a feasible dual that is tight on every positive flow edge. Hence bb is a minimum-cost flow. The inner minimization therefore captures precisely the assignments that admit supporting MPB prices.

Lemma 1 shows that the inner minimization enforces MPB optimality. It remains to choose payouts that are consistent with their supporting prices. The constraint qj≤cjq_j \leq c_j only bounds a chore’s payment; an ER equilibrium additionally requires qj=min⁡{pj,cj}q_j = \min\{p_j,c_j\}. We show that local optimality of the outer maximization enforces this condition. For this, we first establish additional properties of the ER-MaxMin program. Let V(q)=C(q)−H(q)V(q)=C(q)-\mathcal{H}(q) denote its objective, where

H(q)=∑jqjlog⁡qj.\mathcal{H}(q)=\sum_j q_j\log q_j.

For fixed positive prices ww, define Φw(z)=∑jzjlog⁡wj−H(z)\Phi_w(z)=\sum_j z_j\log w_j-\mathcal{H}(z) over z∈Qz \in Q.

Lemma 2 (Convexity and a concave lower bound). The function CC is convex on QQ. For any q∈Qq \in Q, any optimal dual (α,w)(\alpha,w) at qq, and every z∈Qz \in Q,

C(z)≥C(q)+∑j(zj−qj)log⁡wj.(16)C(z) \geq C(q)+\sum_j(z_j-q_j)\log w_j. \tag*{(16)}

Thus log⁡w\log w is a subgradient of CC at qq. Moreover, the function

Fq(z)=C(q)+∑j(zj−qj)log⁡wj−H(z)F_q(z)=C(q)+\sum_j(z_j-q_j)\log w_j-\mathcal{H}(z)
=V(q)+Φw(z)−Φw(q)(z∈Q).(17)=V(q)+\Phi_w(z)-\Phi_w(q)\qquad(z\in Q). \tag*{(17)}

is concave and satisfies Fq(z)≤V(z)F_q(z)\leq V(z) for all z∈Q,∗with∗z\in Q, *with*F_q(q)=V(q)$.

Proof. An optimal dual (α,w)(\alpha,w) at qq remains feasible for every z∈Qz \in Q, so

C(z)≥∑ilog⁡αi+∑jzjlog⁡wj=C(q)+∑j(zj−qj)log⁡wj.C(z)\geq\sum_i\log\alpha_i+\sum_j z_j\log w_j =C(q)+\sum_j(z_j-q_j)\log w_j.

This proves (16) and the subgradient claim. By (15), CC is the pointwise maximum of affine functions of the payouts, so it is convex. Finally, (16) gives Fq(z)≤V(z)F_q(z)\leq V(z), with equality at qq. The function FqF_q is concave because it is an affine function minus the convex function H\mathcal{H}.

Proposition 4 (Local maxima yield ER equilibria). Every local maximizer qq of ER-MaxMin (14) is positive. For any optimal flow bb and dual (α,w)(\alpha,w) at qq, there is a scalar τ>0\tau>0 such that (τw,b)(\tau w,b) is an exact ER equilibrium and qj=min⁡{τwj,cj}q_j=\min\{\tau w_j,c_j\} for every chore jj.

Proof. Fix a local maximizer qq and optimal flow and dual solutions bb and (α,w)(\alpha,w). By Lemma 2, FqF_q is a lower bound on VV that is tight at qq. Hence qq locally maximizes FqF_q, and therefore also Φw\Phi_w, since the two functions differ by a constant.

We show that qq must be positive. If qj=0q_j = 0, transfer an amount ε>0\varepsilon> 0 to coordinate jj from a positive coordinate. Since cj>0c_j > 0, this is feasible for sufficiently small ε\varepsilon. The change in Φw\Phi_w is −εlog⁡ε+O(ε)>0-\varepsilon\log\varepsilon+ O(\varepsilon) > 0, contradicting optimality.

The first-order optimality conditions for Φw\Phi_w on the polytope QQ now give a scalar ν\nu and multipliers μj\mu_j satisfying

log⁡wj−log⁡qj−1=ν+μj,μj≥0,μj(cj−qj)=0.\log w_j - \log q_j - 1 = \nu+ \mu_j,\qquad\mu_j \ge0,\qquad\mu_j(c_j-q_j)=0.

Set τ=e−ν−1\tau= e^{-\nu-1} and pj=τwjp_j = \tau w_j. Then pj=qjeμjp_j = q_j e^{\mu_j}. If qj<cjq_j < c_j, complementary slackness gives μj=0\mu_j = 0 and pj=qjp_j = q_j; if qj=cjq_j = c_j, we have pj≥cjp_j \ge c_j. Therefore qj=min⁡{pj,cj}q_j = \min\{p_j,c_j\} in both cases. By Lemma 1, the flow bb is MPB at ww, and hence at p=τwp = \tau w. Since bb also gives every agent earning one enforced by the constraint in Eq. (13), (p,b)(p,b) is an exact ER equilibrium.

Thus, finding a local maximum of ER-MaxMin suffices to compute an exact ER equilibrium. In the next subsection, we use mirror ascent on ER-MaxMin to compute an approximate ER equilibrium in polynomial time.

Computing an Approximate ER Equilibrium

Mirror ascent is an iterative first-order method for constrained maximization. At each step, it maximizes a first-order approximation of the objective, with a penalty for moving away from the current point. The penalty is a Bregman divergence generated by a convex function called the mirror map ([4]). For ER-MaxMin, we use the entropy function H\mathcal{H} as the mirror map. As we show below, the resulting mirror-ascent step maximizes the concave lower bound FqF_q from Lemma 2.

To define the update, fix a positive payout vector q∈Qq \in Q and solve the flow program (13) to obtain an optimal flow bb and supporting prices ww from its dual. By Lemma 2, log⁡w\log w is a subgradient of CC at qq. Subtracting the gradient of H\mathcal{H} gives the direction gj=log⁡wj−log⁡qj−1g_j = \log w_j - \log q_j - 1 for the first-order approximation of VV. When CC is differentiable, g=∇V(q)g = \nabla V(q); otherwise, this construction uses the subgradient supplied by the flow dual. The divergence generated by H\mathcal{H} on QQ is the relative entropy

DKL(z∥q)=∑jzjlog⁡(zj/qj)=H(z)−H(q)−∑j(log⁡qj+1)(zj−qj)(z∈Q).(18)\begin{aligned} D_{\mathrm{KL}}(z\mathbin{\|}q) = \sum_j z_j \log(z_j/q_j) \\ &= \mathcal{H}(z) - \mathcal{H}(q) - \sum_j(\log q_j + 1)(z_j-q_j) \qquad(z \in Q). \tag*{(18)} \end{aligned}

The second equality uses ∑j(zj−qj)=0\sum_j(z_j-q_j)=0. Rearranging this identity for H(z)\mathcal{H}(z) and substituting into the lower bound from Lemma 2 gives

V(z)≥Fq(z)=C(q)+∑j(zj−qj)log⁡wj−H(z)=V(q)+∑j(log⁡wj−log⁡qj−1)(zj−qj)−DKL(z∥q)=V(q)+∑jgj(zj−qj)−DKL(z∥q).(19)\begin{aligned} V(z) \ge F_q(z) = C(q) + \sum_j(z_j-q_j)\log w_j - \mathcal{H}(z) \\ &= V(q) + \sum_j(\log w_j-\log q_j-1)(z_j-q_j) - D_{\mathrm{KL}}(z\mathbin{\|}q) \\ &= V(q) + \sum_j g_j(z_j-q_j) - D_{\mathrm{KL}}(z\mathbin{\|}q). \tag*{(19)} \end{aligned}

Thus, maximizing FqF_q over QQ is a mirror-ascent step with step size one. Let r∈Qr \in Q be the updated payouts computed by maximizing FqF_q over QQ. By Eq. (17), FqF_q differs from Φw\Phi_w by a constant, so computing rr amounts to maximizing Φw\Phi_w over QQ. The proof of Theorem 4 shows that, at a local maximum of ER-MaxMin, the current payouts qq already maximize Φw\Phi_w. The mirror-ascent update performs this maximization at each iteration. Therefore, the same optimality conditions give the updated payouts rr by scaling the supporting prices and truncating at the earning limits, as stated in the following lemma.

Lemma 3 (Mirror-ascent step). For positive numbers wjw_j, the problem

max⁡r∈QΦw(r)=∑jrjlog⁡wj−H(r)(20)\max_{r \in\mathbb{Q}} \Phi_w(r) = \sum_j r_j \log w_j - \mathcal{H}(r) \tag*{(20)}

has a unique maximizer. It is positive and has the form rj=min⁡{cj,τwj}r_j = \min\{c_j,\tau w_j\} for some τ>0\tau> 0, so that ∑jmin⁡{cj,τwj}=n\sum_j \min\{c_j,\tau w_j\} = n. For rational ww, such a τ\tau and vector rr can be computed in polynomial time.

Proof. As τ\tau increases from zero, ∑jmin⁡{cj,τwj}\sum_j \min\{c_j,\tau w_j\} increases continuously from zero to ∑jcj≥n\sum_j c_j \ge n, so a suitable τ>0\tau> 0 exists. The resulting rr is positive and satisfies the optimality conditions used in Theorem 4, with ν=−log⁡τ−1\nu= -\log\tau- 1 and μj=log⁡(τwj/rj)≥0\mu_j = \log(\tau w_j/r_j) \ge0. Strict concavity of Φw\Phi_w proves uniqueness.

We show how to compute τ\tau. If ∑jcj=n\sum_j c_j = n, taking τ=max⁡jcj/wj\tau= \max_j c_j/w_j makes every chore pay its cap, so r=cr = c. Therefore, suppose ∑jcj>n\sum_j c_j > n. Sort and relabel the chores so that c1/w1≤⋯≤cm/wmc_1/w_1 \le\cdots\le c_m/w_m, and consider the intervals [0,c1w1),[c1w1,c2w2),…,[cmwm,∞)\left[0,\frac{c_1}{w_1}\right),\left[\frac{c_1}{w_1},\frac{c_2}{w_2}\right),\ldots,\left[\frac{c_m}{w_m},\infty\right). Index these intervals by k=0,…,mk = 0,\ldots,m. If τ\tau lies in interval k<mk < m, the first kk chores are capped and the remaining chores pay τwj\tau w_j. Thus the normalization condition becomes the linear equation ∑j≤kcj+τ∑j>kwj=n\sum_{j\le k} c_j + \tau\sum_{j>k} w_j = n, whose solution is

τ=n−∑j≤kcj∑j>kwj.(21)\tau= \frac{n-\sum_{j\le k}c_j}{\sum_{j>k}w_j}. \tag*{(21)}

For each of the first mm intervals, compute this value and check whether it belongs to the interval. The final interval cannot contain a solution, since all chores are capped there and their total payout is ∑jcj>n\sum_j c_j > n. Hence one of the checks must succeed in finding τ\tau, and we return rj=min⁡{cj,τwj}r_j = \min\{c_j,\tau w_j\}. Sorting and checking these intervals take polynomial time for rational ww and cc.

The mirror-ascent step is useful since it can only improve the objective: the updated payouts rr satisfy V(r)≥Fq(r)≥Fq(q)=V(q)V(r) \ge F_q(r) \ge F_q(q) = V(q) due to Lemma 2.

Consider a mirror-ascent step at payouts qq and corresponding optimal money flows bb. Let rr be the updated payouts and p=τwp = \tau w be the prices computed using Lemma 3. If r=qr = q, then (p,b)(p,b) is an exact ER equilibrium. In general, we match the new payouts by rescaling the money flow bb as

b^ij=bijrjqj,e^i=∑jb^ij.(22)\widehat{b}_{ij}=b_{ij}\frac{r_j}{q_j},\qquad\widehat{e}_i=\sum_j\widehat{b}_{ij}. \tag*{(22)}

This preserves MPB assignments because the rescaling leaves the support of bb unchanged, and uniformly scaling prices from ww to p=τwp = \tau w preserves each agent’s MPB chores. Moreover, ∑ib^ij=(rj/qj)∑ibij=rj=min⁡{cj,pj}\sum_i\widehat{b}_{ij}=(r_j/q_j)\sum_i b_{ij}=r_j=\min\{c_j,p_j\}, as required by the earning limits. Individual earnings, however, may change from one to e^i\widehat{e}_i. Thus we return (p,b^)(p,\widehat{b}) if every e^i\widehat{e}_i lies in [1−δ,1+δ][1-\delta,1+\delta]; otherwise, we set q←rq \leftarrow r and begin the next iteration.

To initialize the iteration, we apply Lemma 3 to uniform weights wj=1w_j=1. This gives a positive payout vector, and every subsequent vector is positive by the same lemma, so the rescaling in Eq. (22) is well-defined. Algorithm 1 collects these steps.

Lemma 4. Every candidate (p,b^)(p,\widehat{b}) of Algorithm 1 satisfies exact MPB optimality, capped chore payouts, and total earning nn. If the stopping condition holds, it is a δ\delta-approximate ER equilibrium.

Algorithm 1 Approximate ER equilibrium with equal earnings

Input: Instance (N,M,D,e=1,c)(N, M, D, e = 1, c) with ∑jcj≥n\sum_j c_j \ge n; accuracy δ∈(0,1)\delta\in(0,1)

Output: A δ\delta-approximate ER equilibrium (p,b)(p,b)

  1. Initialize qj←min⁡{cj,τ0}q_j \leftarrow\min\{c_j,\tau_0\}, choosing τ0\tau_0 so ∑jqj=n\sum_j q_j=n

  2. loop

  3. Solve (13) at qq, obtaining an optimal flow bb and supporting prices ww

  4. Compute the price scale τ\tau using Lemma 3

  5. Set pj←τwjp_j \leftarrow\tau w_j and rj←min⁡{cj,pj}r_j \leftarrow\min\{c_j,p_j\} for every jj

  6. Set b^ij←bijrj/qj\widehat{b}_{ij} \leftarrow b_{ij}r_j/q_j and e^i←∑jb^ij\widehat{e}_i \leftarrow\sum_j \widehat{b}_{ij}

  7. if ∣e^i−1∣≤δ\lvert\widehat{e}_i-1\rvert\le\delta for every i∈Ni \in N then

  8. return (p,b^)(p,\widehat{b})

  9. q←rq \leftarrow r

Proof. By Lemma 1, bb is MPB at ww, and hence at p=τwp=\tau w. The rescaling in Eq. (22) preserves its support, and

∑ib^ij=rjqj∑ibij=rj=min⁡{cj,pj}.\sum_i \widehat{b}_{ij}=\frac{r_j}{q_j}\sum_i b_{ij}=r_j=\min\{c_j,p_j\}.

These payouts sum to nn. When the stopping condition on agent earning holds, all conditions defining an approximate ER equilibrium (7) are therefore satisfied.

Bounding the Number of Iterations

We now bound the number of iterations of Algorithm 1 by showing that each nonterminating iteration increases VV by a definite amount. Without loss of generality, we assume 1≤dij≤R1 \le d_{ij} \le R for all i∈Ni \in N, j∈Mj \in M.

Lemma 5 (Progress in each iteration). Every iteration of Algorithm 1 that does not terminate increases VV by at least δ2/4\delta^2/4.

Proof. Let qq and rr be the payouts before and after a mirror-ascent step, and let ww be the supporting prices at qq. By Lemma 3, rr maximizes Φw\Phi_w over QQ, so first-order optimality gives ⟨∇Φw(r),q−r⟩≤0\langle\nabla\Phi_w(r),q-r\rangle\le0. Using Lemma 2 and the entropy identity (18) at rr, we obtain

V(r)−V(q)≥Φw(r)−Φw(q)=DKL(q∥r)−⟨∇Φw(r),q−r⟩≥DKL(q∥r).(23)\begin{aligned} V(r)-V(q)&\ge\Phi_w(r)-\Phi_w(q)\\ &=D_{\mathrm{KL}}(q\mathbin\Vert r)-\langle\nabla\Phi_w(r),q-r\rangle\\ &\ge D_{\mathrm{KL}}(q\mathbin\Vert r). \tag*{(23)} \end{aligned}

We next relate this bound to the agent earnings after rescaling. A small payout qjq_j can make the ratio rj/qjr_j/q_j large, so we apply the log-sum inequality to the payments each agent receives from the chores. Let bb be the unit-earning flow and b^ij=bijrj/qj\widehat{b}_{ij}=b_{ij}r_j/q_j its rescaling, and define ω(z)=z−1−log⁡z\omega(z)=z-1-\log z for z>0z>0. Then

DKL(q∥r)=∑i,j:bij>0bijlog⁡bijb^ij≥∑i(∑jbij)log⁡∑jbij∑jb^ij=−∑ilog⁡e^i=∑iω(e^i).\begin{aligned} D_{\mathrm{KL}}(q\mathbin\Vert r) &=\sum_{i,j:b_{ij}>0}b_{ij}\log\frac{b_{ij}}{\widehat{b}_{ij}}\\ &\ge\sum_i\left(\sum_j b_{ij}\right)\log\frac{\sum_j b_{ij}}{\sum_j\widehat{b}_{ij}}\\ &=-\sum_i\log\widehat{e}_i=\sum_i\omega(\widehat{e}_i). \end{aligned}

The first equality follows from the rescaling and ∑ibij=qj\sum_i b_{ij}=q_j. The last two equalities use the original unit earnings and ∑ie^i=n\sum_i \hat{e}_i=n, respectively.

The function ω\omega is nonnegative and vanishes only at one. For δ∈(0,1)\delta\in(0,1), if ∣z−1∣>δ\lvert z-1\rvert>\delta, then

ω(z)≥δ−log⁡(1+δ)≥δ24.(24)\omega(z) \ge\delta-\log(1+\delta) \ge\frac{\delta^2}{4}. \tag*{(24)}

Indeed, ω\omega decreases below one and increases above one, and δ−log⁡(1+δ)=∫0δt/(1+t) dt≥δ2/4\delta-\log(1+\delta)=\int_0^\delta t/(1+t)\,\mathrm{d}t\ge\delta^2/4; the corresponding deviation below one has at least this value. Since the iteration does not terminate, some agent has ∣e^i−1∣>δ\lvert\hat{e}_i-1\rvert>\delta. Hence DKL(q∥r)≥∑iω(e^i)≥δ2/4D_{\mathrm{KL}}(q\mathbin\Vert r)\ge\sum_i\omega(\hat{e}_i)\ge\delta^2/4, and (23) proves the claim.

Completing the proof of Theorem 3. We first bound the total increase available to VV. Since 1≤dij≤R1\le d_{ij}\le R, we have 0≤C(q)≤nlog⁡R0\le C(q)\le n\log R. Convexity of zlog⁡zz\log z, together with ∑jqj=n\sum_j q_j=n and qj≤nq_j\le n, gives nlog⁡(n/m)≤H(q)≤nlog⁡nn\log(n/m)\le H(q)\le n\log n. Since V=C−HV=C-H, it follows that −nlog⁡n≤V(q)≤nlog⁡R−nlog⁡(n/m)-n\log n\le V(q)\le n\log R-n\log(n/m) for all q∈Qq\in Q. Thus the range of VV over QQ is at most nlog⁡(mR)n\log(mR).

By Lemma 5, each nonterminating iteration increases VV by at least δ2/4\delta^2/4. Hence there are at most 4nlog⁡(mR)/δ24n\log(mR)/\delta^2 such iterations. Including the final iteration gives the bound in Theorem 3. If ∑jcj=n\sum_j c_j=n, then Q={c}Q=\{c\} and every update has q=r=cq=r=c, so the first iteration returns an exact ER equilibrium. Together with Lemma 4, this proves correctness and the polynomial iteration bound of Algorithm 1.

However, we must address two implementation challenges before obtaining polynomial running time. First, the costs log⁡dij\log d_{ij} may be irrational, yet each iteration requires an exact optimal flow and supporting MPB prices. Second, the encoding lengths of the maintained flows, prices, and payouts must remain polynomially bounded throughout the iterations. We show how to handle these issues in Section A so that each iteration takes polynomial time. Together with the iteration bound, this completes the proof of Theorem 3.

Remark 2 (Non-identical earning requirements). We note that the same algorithm can be run with arbitrary requirements ei>0e_i>0, replacing each agent’s unit earning requirement by eie_i and total payout nn by E=∑ieiE=\sum_i e_i. The earning-error argument in Lemma 5 then guarantees progress of at least emin⁡δ2/4e_{\min}\delta^2/4, where emin⁡=min⁡ieie_{\min}=\min_i e_i. This yields O((1+(E/emin⁡)log⁡(mR)/δ2))O((1+(E/e_{\min})\log(mR)/\delta^2)) iterations. The ratio E/emin⁡E/e_{\min} may be exponential in the binary input length. Thus the iteration bound gives an FPTAS for equal earnings, but extending it to arbitrary earning requirements remains open.

Computing a (3+ε\varepsilon)-EFX Allocation

In this section, we prove Theorem 1 by converting an approximate ER equilibrium into an approximate EFX allocation. Our main result is the following.

Theorem 5. Given a δ\delta-approximate ER equilibrium with unit earning requirements and earning limits 1/21/2, where δ∈(0,1/10)\delta\in(0,1/10), we can compute a (3+10δ)(3+10\delta)-EFX allocation in time polynomial in the input length and 1/δ1/\delta.

We use the chore-swap framework of Garg and Murhekar [16], which begins with a suitable initial allocation satisfying a certain condition called λ\lambda-EFX-friendliness, for parameter λ≥1\lambda\ge1. It iteratively resolves the envy of agents by performing chore swaps: an agent who violates λ\lambda-EFX exchanges one designated chore from its bundle, called a swap chore, for a least-disutility bundle while retaining her other chores. The friendliness conditions ensure that each swap establishes λ\lambda-EFX for that agent and preserves this guarantee for agents who are already processed. Thus the framework computes a λ\lambda-EFX allocation in polynomial time. Our task is therefore to construct an EFX-friendly starting allocation. Garg et al. [20] show that an exact ER equilibrium can be rounded to an integral allocation, which is subsequently modified to yield a 4-EFX-friendly allocation. There are two challenges in extending this approach. First, our FPTAS gives only an approximate ER equilibrium. Second, the reallocation must improve upon factor four. We address the first challenge by extending the analysis of their rounding algorithm to approximate earnings. Unfortunately, the re-allocation step has a concrete bottleneck at factor 4, even with an exact ER equilibrium. We give a new algorithm that constructs a (3+ε)(3+\varepsilon)-EFX-friendly allocation by choosing the swap chores and their recipients flexibly based on the structure of the rounded allocation. This flexibility allows us to satisfy stronger EFX-friendly conditions and obtain our improved guarantee.

The Chore-Swap Framework

We overview the chore-swap framework of Garg and Murhekar [16]. It starts from a λ\lambda-EFX-friendly allocation, which has two types of agents, active and inactive. The inactive agents are already λ\lambda-envy-free. Each active agent has one swap chore, while her other chores form a residual bundle of small disutility. If she violates λ\lambda-EFX, she can exchange her swap chore for a least-disutility bundle while retaining her residual bundle. The factor λ−1\lambda-1 in the definition below leaves room for this exchange: if the residual costs at most (λ−1)di(B)(\lambda-1)d_i(B), adding bundle BB gives total disutility at most λdi(B)\lambda d_i(B). The definition imposes the comparisons that allow the swaps to be performed while preserving the fairness guarantees of other agents.

Definition 3 (λ\lambda-EFX-friendly allocation, Garg and Murhekar [16]). Let λ≥1\lambda\ge1 and let YY be an allocation with nonempty bundles. The allocation YY is λ\lambda-EFX-friendly if there are a partition N=N0⊔NHN = N_0 \sqcup N_H and a swap chore ji∈arg⁡max⁡j∈Yidijj_i \in\arg\max_{j\in Y_i} d_{ij} for each i∈NHi \in N_H such that, writing Ri=Yi∖{ji}R_i = Y_i \setminus\{j_i\} for agent ii's residual bundle,

di(Yi)≤λdi(Yk)(i,k∈N0),d_i(Y_i) \le\lambda d_i(Y_k) \qquad(i,k \in N_0),
di(Yi)≤λdi(jh)(i∈N0, h∈NH),d_i(Y_i) \le\lambda d_i(j_h) \qquad(i \in N_0,\ h \in N_H),
di(Ri)≤(λ−1)di(Yk)(i∈NH, k∈N0),d_i(R_i) \le(\lambda-1)d_i(Y_k) \qquad(i \in N_H,\ k \in N_0),
di(Ri)≤(λ−1)di(jh)(i,h∈NH).d_i(R_i) \le(\lambda-1)d_i(j_h) \qquad(i,h \in N_H).

Here NHN_H and N0N_0 are the sets of active and inactive agents, respectively. The first two inequalities imply that each inactive agent is λ\lambda-envy-free. The last two bound each active agent’s residual disutility against every inactive bundle and every swap chore. An active agent need not perform a swap if she already satisfies λ\lambda-EFX.

Theorem 6 (Garg and Murhekar [16]). Given a λ\lambda-EFX-friendly allocation, a λ\lambda-EFX allocation can be computed in polynomial time using at most nn chore swaps.

The algorithm first sets aside the swap chores and lets the active agents pick their least-disutility remaining chore in an arbitrary fixed order. It then processes these agents in the same order. An agent who violates λ\lambda-EFX exchanges her swap chore for a least-disutility bundle, keeping her residual bundle; the other agent receives the swap chore as a singleton. The picking order ensures that later swaps preserve the λ\lambda-EFX guarantees of agents already processed. For completeness, we present this algorithm and sketch its analysis in Section B.

Thus, to prove Theorem 5, it suffices to construct a (3+10δ)(3+10\delta)-EFX-friendly allocation. Our approach is to round a δ\delta-approximate ER equilibrium, and transform the rounded solution into a (3+10δ)(3+10\delta)-EFX-friendly allocation. We discuss these algorithms in the following sections.

Rounding an Approximate ER Equilibrium

When m≤2nm \le2n, an exact EFX allocation can be computed in polynomial time ([22, 20]). We therefore assume m>2nm > 2n. Let (p,b)(p,b) be a δ\delta-approximate ER equilibrium with unit earning requirements and earning limits 1/21/2, where δ∈[0,1/10]\delta\in[0,1/10]. For δ>0\delta> 0, Algorithm 1 computes such an equilibrium since m/2>nm/2 > n.

We show how to round an approximate ER equilibrium into an integral allocation in polynomial time with price bounds that will allow us to construct an EFX-friendly allocation. Garg et al. [20] give such an algorithm for rounding an exact ER equilibrium (p,b)(p,b). We first describe their algorithm and its guarantees. Let L={j:pj≤1/2}L = \{j : p_j \le1/2\} and H={j:pj>1/2}H = \{j : p_j > 1/2\} denote the sets of low-price and high-price chores, respectively.

The rounding algorithm. Define the payment graph of (p,b)(p,b) as the bipartite graph on N⊔MN \sqcup M with an edge (i,j)(i,j) of weight bijb_{ij} whenever bij>0b_{ij} > 0. Cancel alternating cycles in the payment graph by subtracting the minimum weight on one alternating set of edges and adding it on the other. Each cancellation preserves agent earnings and chore payouts and removes at least one edge. Thus polynomially many cancellations give a forest while preserving the ER conditions. Root each tree at an arbitrary agent. All references to parents and children use this rooted forest.

The algorithm starts with empty integral bundles and proceeds in four phases, as specified in Algorithm 2. Phase 1 (Line 3) assigns every original leaf chore to its only adjacent agent. Phase 2 (Lines 4–10) processes agents in breadth-first order and allocates all low-price chores, using a cutoff of one for each agent’s current bundle price. An agent whose bundle price already exceeds one passes her child high-price chores to child agents as well. Phase 3 (Line 11) retains exactly one child-agent edge for each remaining high-price chore, choosing a child who earns the most from that chore. Every remaining chore then has degree two. Phase 4 (Lines 12–14) matches these chores to all but one agent in each remaining tree; the unmatched agent is one with largest current bundle price.

To obtain the matching in Phase 4, contract each chore to an edge between its two adjacent agents, root this tree at the agent to be left unmatched, and assign each edge to its endpoint farther from the root. All assignments use edges of the original payment graph, so the resulting allocation is MPB. For the rounded allocation XX, let ki=∣Xi∩H∣k_i = |X_i \cap H| and Si=Xi∖HS_i = X_i \setminus H. When the input is an exact ER equilibrium, the analysis of Garg et al. [20] gives, for every agent ii,

p(Xi)≥12,ki≤2,p(Si)≤32−ki2.(25)p(X_i) \ge\frac{1}{2}, \qquad k_i \le2, \qquad p(S_i) \le\frac{3}{2} - \frac{k_i}{2}. \tag*{(25)}

Approximate ER equilibria. Our FPTAS, however, only gives a δ\delta-approximate ER equilibrium, in which each agent’s earning lies in [1−δ,1+δ][1-\delta,1+\delta]. Even an arbitrarily small earning error can allow an agent to receive three high-price chores, as the following example shows.

Example 5 (A third high-price chore). Consider three agents with identical disutilities equal to the chore prices. There are four high-price chores, each of price P>2P > 2. In the ER flow, two are supported only by agent 1, one only by agent 2, and the fourth pays δ\delta to agent 1 and 1/2−δ1/2-\delta to agent 2, where 0<δ<1/20 < \delta< 1/2. Agent 3 alone performs three low-price chores of price 1/31/3 each. The earnings are (1+δ,1−δ,1)(1+\delta,1-\delta,1), and all approximate ER conditions hold.

Root the shared component at agent 2. Phase 1 of Algorithm 2 assigns each leaf chore to its only adjacent agent. Agent 2 then holds a chore of price greater than one, so the procedure passes her shared high-price chore to its child agent, agent 1. Thus agent 1 receives three high-price chores even for an arbitrarily small earning error δ>0\delta> 0.

Algorithm 2 ER rounding, adapted from Garg et al. [20]

Input: An approximate ER equilibrium (p,b)(p,b) with unit earnings and earning limits 1/21/2

Output: An integral MPB allocation XX

  1. Cancel cycles in the payment graph; root every resulting tree at an agent

  2. Xi←∅X_i \leftarrow\emptyset for every ii; let L={j:pj≤1/2}L = \{j : p_j \le1/2\} and H=M∖LH = M \setminus L

  3. Assign each leaf chore to its only adjacent agent and delete it

  4. for each agent ii, in breadth-first order in the original rooted forest do

  5. &nbsp;&nbsp;&nbsp;&nbsp;if p(Xi)>1p(X_i) > 1 then

  6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for each remaining child chore j∈Hj \in H of ii do

  7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Assign jj to a child maximizing bhjb_{hj}; delete jj

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while some remaining child j∈Lj \in L satisfies p(Xi)+pj≤1p(X_i) + p_j \le1 do

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Assign jj to ii; delete jj

  10. Assign every remaining child chore j∈Lj \in L to any child agent of jj; delete jj

  11. For each remaining chore, retain its parent edge and one child edge maximizing bhjb_{hj}

  12. for each remaining tree TT do

  13. &nbsp;&nbsp;&nbsp;&nbsp;Choose h∈N(T)h \in N(T) maximizing p(Xh)p(X_h)

  14. &nbsp;&nbsp;&nbsp;&nbsp;Match its chores to N(T)∖{h}N(T) \setminus\{h\} along retained edges, and assign them

  15. return XX

We therefore need a new analysis of the rounding algorithm for approximate earnings. The useful guarantee is a joint bound on the number of high-price chores and the total price of low-price chores. In particular, an agent who receives three high-price chores must have p(Si)≤δp(S_i) \le\delta. We prove the following.

Lemma 6 (Rounding with approximate earnings). Let δ∈[0,1/2)\delta\in[0, 1/2). Given a δ\delta-approximate ER equilibrium with unit earnings and earning limits $1/2, Algorithm 2 returns an integral MPB allocation XX in polynomial time. For every agent ii, with ki=∣Xi∩H∣k_i = |X_i \cap H| and Si=Xi∖HS_i = X_i \setminus H, we have

p(Xi)≥12−δ,ki≤3,p(Si)≤32+δ−ki2.(26)p(X_i) \ge\frac{1}{2} - \delta,\qquad k_i \le3,\qquad p(S_i) \le\frac{3}{2}+\delta-\frac{k_i}{2}. \tag*{(26)}

Proof of Lemma 6. MPB optimality and polynomial running time follow from the algorithm. We prove the price bounds using the acyclic payment graph before Phase 1. Write e^i=∑jbij\hat e_i = \sum_j b_{ij} for agent ii’s original earning, so 1−δ≤e^i≤1+δ1-\delta\le\hat e_i \le1+\delta.

Upper bounds. Let FiF_i be the original leaf chores assigned to agent ii in Phase 1. Since a low-price leaf pays its full price and a high-price leaf pays 1/21/2, we have

p(Fi∩L)+12∣Fi∩H∣≤e^i≤1+δ.(27)p(F_i \cap L) + \frac{1}{2}|F_i \cap H| \le\hat e_i \le1+\delta. \tag*{(27)}

In particular, FiF_i contains at most two high-price chores. When ii is visited in Phase 2, her current bundle consists of FiF_i and possibly her original parent chore.

If this bundle has price at most one, the low-price assignments keep it at most one. Agent ii may subsequently receive at most one high-price chore in Phase 4. A bundle of price at most one contains at most one high-price chore, since such chores have price strictly greater than 1/21/2. Therefore ki≤2k_i \le2, and p(Si)≤3/2−ki/2p(S_i) \le3/2-k_i/2.

Otherwise the bundle price at ii’s visit exceeds one. All her child chores are passed down or removed. Thus her final bundle consists of FiF_i and at most her original parent chore, whether that parent was assigned earlier or in Phase 4. If the parent is low-price, (27) gives p(Si)≤1+δ−ki/2+1/2p(S_i) \le1 + \delta- k_i/2 + 1/2. If it is high-price and assigned to ii, it contributes one to kik_i and nothing to SiS_i, giving p(Si)≤1+δ−(ki−1)/2p(S_i) \le1 + \delta- (k_i - 1)/2. If the parent is not assigned to ii, the bound is stronger. In every case ki≤3k_i \le3 and the upper bound in (26) follows.

When δ=0\delta= 0, two high-price original leaves consume the entire unit earning of ii. Such an agent cannot have a positive parent edge, so cannot obtain a third high-price chore. This gives ki≤2k_i \le2 in the exact case.

Lower bound. Consider a Phase-3 tree TT, and let hh be an agent of maximum current bundle price. Every other agent receives a high-price chore in Phase 4, so obtains price greater than 1/21/2. It suffices to lower-bound p(Xh)p(X_h), which equals hh’s price before Phase 4.

Suppose some agent i∈N(T)i \in N(T) had a child chore assigned to another agent in Phase 2. If that chore was high-price, her bundle already had price greater than one. If it was low-price, it did not fit under the cutoff one, so her bundle price was greater than 1−1/2=1/21 - 1/2 = 1/2. Bundle prices only increase during rounding. By the choice of hh, we therefore have p(Xh)≥1/2p(X_h) \ge1/2 in this case.

Otherwise no agent in N(T)N(T) lost a child chore in Phase 2. All original earnings of these agents are represented either by chores already assigned to them or by the ∣N(T)∣−1|N(T)| - 1 high-price chores remaining inside TT, except possibly for the original parent chore of the root of TT. This exceptional chore accounts for at most 1/21/2 of the root’s original earning. Every internal high-price chore also pays out 1/21/2. Since every agent originally earned at least 1−δ1 - \delta, the sum of their current bundle prices is at least

∣N(T)∣(1−δ)−12−12(∣N(T)∣−1)=∣N(T)∣(12−δ).|N(T)|(1-\delta)-\frac{1}{2}-\frac{1}{2}(|N(T)|-1)=|N(T)|\left(\frac{1}{2}-\delta\right).

Therefore some agent in TT, and hence also the maximum-price agent hh, has bundle price at least 1/2−δ1/2-\delta. This proves the lower bound.

We will use these rounding bounds in § 4.4 to construct a (3+10δ)(3+10\delta)-EFX-friendly allocation for the chore-swap framework. As a warm-up, we recall in the next section the known construction of a 4-EFX-friendly allocation from an exact ER equilibrium.

Obtaining a 4-EFX-Friendly Allocation

We present the construction of a 4-EFX-friendly allocation from an ER equilibrium due to Garg et al. [20] in the language of EFX-friendliness from Garg and Murhekar [16]. Let (X,p)(X,p) be the allocation and prices obtained by rounding an exact ER equilibrium with unit earnings and earning limits 1/21/2. Thus XX satisfies (25). Normalize disutilities by the MPB ratios of XX, as in (1). Each agent’s own chores then have disutility equal to their price, and every chore has disutility at least its price to every agent.

The construction sets aside all high-price chores HH and reallocates them, leaving each agent’s low-price chores with her. Agents who receive several high-price chores are shown to be sufficiently envy-free and are inactive. Each active agent receives exactly one high-price chore as her swap chore and retains Si=Xi∖HS_i=X_i\setminus H as her residual bundle. Thus a fixed threshold of 1/21/2 determines which chores are reallocated and provides the lower bound on swap-chore prices used in the friendliness comparisons.

Lemma 7 ([16]). Given an allocation (X,p)(X,p) obtained by rounding an exact ER equilibrium with unit earning requirements and earning limits 1/21/2, a 4-EFX-friendly allocation can be constructed in polynomial time.

Proof. We use the bounds in (25). In particular, ∣H∣≤2n|H| \le2n, and every agent’s low-price chores have total price at most 3/23/2.

If ∣H∣≤n|H| \le n, assign one high-price chore to each of ∣H∣|H| agents, including every original owner of a high-price chore, while retaining all low-price chores. Denote the resulting allocation by YY. The high-price chore recipients form NHN_H; all other agents are inactive and keep Yi=Xi=SiY_i = X_i = S_i. Every inactive agent has disutility at most 3/23/2 for her bundle, while every inactive bundle and every swap chore has price at least 1/21/2. Thus the first two conditions of Definition 3 hold even with factor three.

If n<∣H∣≤2nn < |H| \le2n, apply the few-chores EFX algorithm of Garg et al. [20] to HH, ordering the original owners of high-price chores first. There are at least ∣H∣−n|H| - n such agents, since each originally owns at most two high-price chores and ∣H∣≤2n|H| \le2n. The algorithm returns an EFX allocation ZZ with nonempty bundles, where only the first ∣H∣−n|H| - n agents can receive several chores. Set Yi=Si∪ZiY_i = S_i \cup Z_i, let NH={i:∣Zi∣=1}N_H = \{i : |Z_i| = 1\}, and let N0=N∖NHN_0 = N \setminus N_H. For every inactive agent ii, we have ki≥1k_i \ge1, and hence p(Si)≤1p(S_i) \le1. Let gg be a least-disutility chore in ZiZ_i. Since ∣Zi∣≥2|Z_i| \ge2 and ZZ is EFX,

di(Zi)≤2di(Zi∖{g})≤2di(Zh)(h∈N).d_i(Z_i) \le2d_i(Z_i \setminus\{g\}) \le2d_i(Z_h) \qquad(h \in N).

Consequently,

di(Yi)=di(Si)+di(Zi)≤1+2di(Zh)≤4di(Zh),d_i(Y_i) = d_i(S_i) + d_i(Z_i) \le1 + 2d_i(Z_h) \le4d_i(Z_h),

since di(Zh)≥p(Zh)>1/2d_i(Z_h) \ge p(Z_h) > 1/2. When hh is active, ZhZ_h is its singleton swap chore; when hh is inactive, Zh⊆YhZ_h \subseteq Y_h. This proves the first two friendliness conditions.

In both cases, every active agent retains a residual bundle SiS_i of disutility at most 3/23/2. Every inactive bundle and every swap chore has price at least $1/2, so the last two friendliness conditions hold with factor λ−1=3\lambda- 1 = 3. Each swap chore is also a highest-disutility chore for its recipient: its disutility is at least its price, which exceeds 1/21/2, whereas every residual chore has disutility equal to its price and at most 1/21/2. All bundles are nonempty, and the reallocation takes polynomial time. Thus the resulting allocation is 4-EFX-friendly.

Together with Theorem 6, this recovers the 4-EFX guarantee of Garg et al. [20] in polynomial time given an exact ER equilibrium as input.

To obtain our (3+ε)(3 + \varepsilon)-EFX guarantee, we must address two obstacles. First, rounding an approximate ER equilibrium can give an agent three high-price chores, as shown in Example 5. The argument above uses the two-chore bound when choosing recipients for the reallocation. More importantly, even with an exact ER equilibrium, this fixed-threshold construction has a bottleneck at factor four. A residual bundle of an active agent has price at most 3/23/2, while a swap chore can have price arbitrarily close to 1/21/2. Comparing these quantities in the friendliness condition gives λ−1=3\lambda- 1 = 3, and hence λ=4\lambda= 4. The following example shows that this loss occurs in an actual ER rounding.

Example 6 (A bottleneck in the fixed-threshold construction). Consider four agents with identical disutilities. Fix 0<β<1/60 < \beta< 1/6 and let a=(1−β)/2a = (1 - \beta)/2 and p=1/2+βp = 1/2 + \beta. Suppose the rounded allocation is X1={a,a,1/2}X_1 = \{a, a, 1/2\}, X2={β,p}X_2 = \{\beta, p\}, X3=X4={p,p}X_3 = X_4 = \{p, p\}, where each entry denotes the price of a distinct chore, equal to every agent’s disutility for that chore.

The fixed threshold is 1/21/2: the construction in Lemma 7 sets aside all five chores of price p>1/2p > 1/2 for reallocation, while each agent retains her low-price chores. In particular, agent 1 retains S1=X1S_1 = X_1, of disutility 3/2−β3/2 - \beta. The reallocation gives two high-price chores to one agent and one to each other agent. Agents 2, 3, and 4 are ordered before agent 1 because they originally own high-price chores. Only the first agent in this order can receive two chores, so agent 1 receives one high-price

chore and becomes active. Every swap chore has disutility pp, and hence EFX-friendliness requires 32−β≤(λ−1)p\frac{3}{2}-\beta\le(\lambda-1)p, or

λ≥1+32−βp=41+2β\lambda\ge1+\frac{\frac{3}{2}-\beta}{p}=\frac{4}{1+2\beta}

This approaches factor 4 as β\beta approaches 0. Thus this construction cannot guarantee λ\lambda-EFX-friendliness for any fixed λ<4\lambda<4.

To avoid this loss, we allow the threshold to increase from 1/21/2 to t=pt=p. Starting again from XX, set aside the five high-price chores as candidate swap chores. At the new threshold pp, let one high-price chore rejoin the residual bundle of each of agents 3 and 4. Now three candidate swap chores remain, one originally owned by each of agents 2, 3, and 4. Keep these as their swap chores and leave agent 1 inactive. Thus N0={1}N_0=\{1\}, NH={2,3,4}N_H=\{2,3,4\}, and the active residual bundles are R2={β}R_2=\{\beta\} and R3=R4={p}R_3=R_4=\{p\}. We have

t≤d1(X1)=32−β≤3t,di(Ri)≤2t(i∈NH).t \le d_1(X_1)=\frac{3}{2}-\beta\le3t,\qquad d_i(R_i)\le2t\quad(i\in N_H).

Every swap chore has disutility tt and is a highest-disutility chore in its owner’s bundle. Since the agents have identical disutilities, these bounds verify all four conditions of Definition 3 for λ=3\lambda=3. Hence XX itself is 3-EFX-friendly. Raising the threshold lets agents 3 and 4 retain one high-price chore each in their residual bundles, so agent 1 can remain inactive despite her large residual bundle.

Constructing an EFX-Friendly Allocation

Example 6 illustrates how a flexible threshold can overcome the factor-4 bottleneck: allowing some high-price chores to rejoin their owners’ residual bundles lets agents with large residual bundles remain inactive. We generalize this idea to the allocation (X,p)(X,p) obtained by rounding a δ\delta-approximate ER equilibrium with unit earning requirements and earning limits 1/21/2. Our construction uses the joint bounds in Lemma 6, which allow an agent to hold three high-price chores.

We begin with a threshold t=1/2−δt=1/2-\delta and consider all high-price chores to be candidate swap chores. Our algorithm iteratively increases the price threshold tt and reduces the set of candidate swap chores, letting some candidate chores rejoin their original owners’ residual bundles. We choose the threshold and the remaining candidate chores so that each active agent can receive one swap chore, while the other agents keep their residual bundles. The sets LL and HH remain defined by the fixed cutoff 1/21/2 throughout.

The required price bounds. At any stage of the construction, let E⊆HE\subseteq H denote the current set of candidate swap chores and Ri=Xi∖ER_i=X_i\setminus E the residual bundle of agent ii. Normalize disutilities using the MPB ratios of XX. Since residual chores remain with their original owners, di(Ri)=p(Ri)d_i(R_i)=p(R_i), while any other bundle has disutility at least its price. To obtain a λ\lambda-EFX-friendly allocation, for a factor λ≥3\lambda\ge3, we seek a partition N=N0∪NHN=N_0\cup N_H, with ∣NH∣=∣E∣|N_H|=|E|, satisfying

t≤p(Ri)≤λt(i∈N0),p(Ri)≤(λ−1)t(i∈NH),pj≥t(j∈E).(28)\begin{aligned} t &\le p(R_i)\le\lambda t && (i\in N_0),\\ p(R_i)&\le(\lambda-1)t && (i\in N_H),\\ p_j&\ge t && (j\in E). \tag*{(28)} \end{aligned}

Each active agent then receives one distinct chore from EE. These bounds give the four disutility comparisons in Definition 3. We will maintain the upper bound p(Ri)≤λtp(R_i)\le\lambda t for every agent throughout the construction.

We must also ensure that each swap chore is a highest-disutility chore in its recipient’s bundle. For this reason, we return a candidate chore to its owner only when tt reaches its price. Every returned chore then has price at most that of any remaining candidate chore. The original low-price chores also have smaller prices than all candidate chores. Since residual chores remain on MPB assignments, these price comparisons ensure the required disutility ordering.

Choosing recipients for the swap chores. For a given threshold tt and candidate set EE, write

ui=p(Ri),A={i:ui≤(λ−1)t},D={i:ui<t}.u_i = p(R_i), \qquad A = \{i : u_i \le(\lambda- 1)t\}, \qquad D = \{i : u_i < t\}.

The agents in AA are eligible: their residual bundles are small enough for them to receive a swap chore. The agents in DD are deficient: they must receive a swap chore, since otherwise their bundles would have price below tt. Hence we need D⊆NH⊆AD \subseteq N_H \subseteq A and ∣NH∣=∣E∣|N_H| = |E|. Such a choice exists precisely when

∣D∣≤∣E∣≤∣A∣.|D| \le|E| \le|A|.

The two inequalities express the competing requirements: there must be enough swap chores for deficient agents, and enough eligible agents for the swap chores.

The threshold procedure. We start with E=HE = H and Ri=SiR_i = S_i. To ensure that there are initially enough candidate chores for all deficient agents, set t=1/2−δt = 1/2 - \delta, the lower bound on rounded bundle prices. Indeed, if p(Si)<1/2−δp(S_i) < 1/2 - \delta, then XiX_i must contain a high-price chore because p(Xi)≥1/2−δp(X_i) \ge1/2 - \delta. Thus each initially deficient agent owns a distinct candidate chore. This choice of tt uses the lower bound on whole bundles; the candidate set is still H={j:pj>1/2}H = \{j : p_j > 1/2\}.

Initially, the residual prices satisfy p(Si)≤3/2+δp(S_i) \le3/2 + \delta. To ensure ui≤λtu_i \le\lambda t at the start, set

λ=3/2+δ1/2−δ=3+2δ1−2δ.(29)\lambda= \frac{3/2 + \delta}{1/2 - \delta} = \frac{3 + 2\delta}{1 - 2\delta}. \tag*{(29)}

Since δ≥0\delta\ge0, we have λ≥3\lambda\ge3. For an exact ER input, λ=3\lambda= 3, giving the bounds 3t3t for inactive bundles and 2t2t for active residual bundles seen in Example 6. We will use the joint rounding bound to show that ui≤λtu_i \le\lambda t continues to hold as chores return to their owners’ residual bundles.

While ∣E∣>∣A∣|E| > |A|, there are too many candidate chores for the eligible agents. We either return a candidate chore of price tt to its original owner or, if none has this price, increase tt. A threshold increase stops at the next candidate price or the next value ui/(λ−1)u_i/(\lambda- 1) at which an ineligible agent becomes eligible, whichever is smaller. Reaching a candidate price allows a chore to be returned. Stopping at an eligibility event ensures that an agent outside AA cannot become deficient during a single threshold increase: she becomes eligible at t=ui/(λ−1)t = u_i/(\lambda- 1), before becoming deficient at t>uit > u_i.

We stop as soon as ∣E∣≤∣A∣|E| \le|A|. Chores of the same price are returned one at a time, checking this condition after every event. The key observation, proved below, is that these rules preserve ∣D∣≤∣E∣|D| \le|E|. Thus, when there are enough eligible recipients, there are still enough swap chores for all deficient agents. Algorithm 3 gives the algorithm.

The candidate set EE is nonempty whenever the while-condition holds.

Lemma 8 (Properties of the threshold procedure). Algorithm 3 terminates after O(n+∣H∣)O(n + |H|) events. At termination,

∣D∣≤∣E∣≤∣A∣,ui≤λt(i∈N),pj≥t(j∈E).(30)|D| \le|E| \le|A|, \qquad u_i \le\lambda t \quad(i \in N), \qquad p_j \ge t \quad(j \in E). \tag*{(30)}

Each RiR_i consists of SiS_i and returned high-price chores originally assigned to ii in XX, each of price at most tt.

Proof. By construction, residual chores remain with their original owners. Candidate chores have price at least tt, and returned high-price chores have price at most tt. Chores of price exactly tt may lie in either set when the procedure stops.

Algorithm 3 Constructing an EFX-friendly allocation
Input: A rounded MPB allocation $(X,p)$ satisfying (26)
Output: A $\lambda$-EFX-friendly allocation $Y$, its partition, and swap chores
1: Set $\lambda$ as in (29)
2: $t \leftarrow 1/2-\delta$; $E \leftarrow H$; $R_i \leftarrow X_i \setminus H$ for every $i$
3: $u_i \leftarrow p(R_i)$; $A \leftarrow \{i:u_i \leq (\lambda-1)t\}$; $D \leftarrow \{i:u_i<t\}$
4: while $|E|>|A|$ do
5: if some $j \in E$ has $p_j=t$ then
6: Choose one such $j$ and let $i$ be its owner in $X$
7: $E \leftarrow E \setminus \{j\}$; $R_i \leftarrow R_i \cup \{j\}$; $u_i \leftarrow u_i+p_j$
8: else
9: $t \leftarrow \min\left(\{p_j:j \in E\}\cup\{u_i/(\lambda-1):i \notin A\}\right)$
10: $A \leftarrow \{i:u_i \leq (\lambda-1)t\}$; $D \leftarrow \{i:u_i<t\}$
11: Choose $N_H$ with $D \subseteq N_H \subseteq A$ and $|N_H|=|E|$
12: $N_0 \leftarrow N \setminus N_H$; assign one distinct $j_i \in E$ to each $i \in N_H$
13: $Y_i \leftarrow R_i \cup \{j_i\}$ for $i \in N_H$; $Y_i \leftarrow R_i$ for $i \in N_0$
14: return $Y$, $N_0$, $N_H$, and the swap chores $j_i$

Residual prices. Before tt reaches 1/21/2, no high-price chore can be returned, so

ui=p(Si)≤32+δ=λ(12−δ)≤λt.u_i=p(S_i)\leq\frac{3}{2}+\delta=\lambda\left(\frac{1}{2}-\delta\right)\leq\lambda t.

For t≥1/2t\geq1/2, returned chores increase the residual price. However, the upper bound on p(Si)p(S_i) decreases by 1/21/2 for each high-price chore originally assigned to ii. By Lemma 6 and ki≤3k_i\leq3,

ui≤32+δ−ki2+kitu_i\leq\frac{3}{2}+\delta-\frac{k_i}{2}+k_i t
≤3t+δ≤λt.\leq3t+\delta\leq\lambda t.

The second inequality uses t≥1/2t\geq1/2 and ki≤3k_i\leq3; the last uses λ−3=8δ/(1−2δ)≥2δ\lambda-3=8\delta/(1-2\delta)\geq2\delta and $t\geq 1/2. Thus the joint rounding bound accommodates even a third high-price chore returning to its owner’s residual bundle.

Enough swap chores for deficient agents. Initially, every agent with p(Si)<1/2−δp(S_i)<1/2-\delta must own a high-price chore, since p(Xi)≥1/2−δp(X_i)\geq1/2-\delta. Choosing one such owned chore per deficient agent gives ∣D∣≤∣H∣=∣E∣|D|\leq|H|=|E|. Before every nonterminal event,

∣D∣≤∣A∣<∣E∣,(31)|D|\leq|A|<|E|, \tag*{(31)}

because D⊂AD\subset A. Returning one chore decreases ∣E∣|E| by one and can only shrink DD, since tt stays fixed and the owner’s residual price increases. The strict inequality in (31) therefore gives ∣D∣≤∣E∣|D|\leq|E| after the return, even if the owner leaves AA.

Suppose instead that the threshold increases to t′t'. By the choice of the next event, every agent outside the old AA has ui≥(λ−1)t′≥t′u_i\geq(\lambda-1)t'\geq t', and hence cannot belong to the new DD. Therefore

Dnew⊂Aold,∣Dnew∣≤∣Aold∣<∣E∣.D_{\mathrm{new}}\subset A_{\mathrm{old}},\qquad|D_{\mathrm{new}}|\leq|A_{\mathrm{old}}|<|E|.

This proves ∣D∣≤∣E∣|D|\leq|E| after each event, including the first one at which the stopping condition ∣E∣≤∣A∣|E|\leq|A| holds.

Number of events. At most ∣H∣|H| chores are returned. Between returns, increasing tt can only add agents to AA. Each return removes at most one agent from AA, so at most n+∣H∣n+|H| entries into AA can occur. Every threshold increase either adds an eligible agent or reaches a candidate price, in which case a chore is returned next unless the procedure stops. Thus there are O(n+∣H∣)O(n+|H|) events. If EE becomes empty, the stopping condition holds, so the procedure terminates.

We can now choose the active agents and assign the remaining swap chores. The price bounds imply the required disutility comparisons.

Lemma 9. Given the rounded allocation in Lemma 6, Algorithm 3 constructs a λ\lambda-EFX-friendly allocation in polynomial time, for λ\lambda in (29). For an exact ER input, the resulting allocation is 3-EFX-friendly.

Proof. By Lemma 8, the algorithm can choose NHN_H with D⊆NH⊆AD \subseteq N_H \subseteq A and ∣NH∣=∣E∣|N_H|=|E|. In the resulting allocation YY, every active agent receives one swap chore and every inactive agent keeps her residual bundle. The definitions of A,DA,D, together with ui≤λtu_i \le\lambda t, give

t≤p(Ri)≤λt(i∈N0),p(Ri)≤(λ−1)t(i∈NH).t \le p(R_i) \le\lambda t \quad(i \in N_0), \qquad p(R_i) \le(\lambda-1)t \quad(i \in N_H).

Thus (28) holds. Since retained chores were originally assigned on MPB edges, di(Ri)=p(Ri)d_i(R_i)=p(R_i). Every inactive bundle and every swap chore has price at least tt, so

di(Yi)≤λdi(B)(i∈N0),(32)d_i(Y_i) \le\lambda d_i(B) \qquad(i \in N_0), \tag*{(32)}
di(Ri)≤(λ−1)di(B)(i∈NH),(33)d_i(R_i) \le(\lambda-1)d_i(B) \qquad(i \in N_H), \tag*{(33)}

for every B∈{Yk:k∈N0}∪{{jh}:h∈NH}B \in\{Y_k : k \in N_0\} \cup\{\{j_h\} : h \in N_H\}. These are the four inequalities in Definition 3.

It remains to check that each swap chore jij_i is a highest-disutility chore in its recipient’s bundle. By Lemma 8, every g∈Rig \in R_i has price at most max⁡{1/2,t}\max\{1/2,t\}, whereas pji>1/2p_{j_i} > 1/2 and pji≥tp_{j_i} \ge t. Hence

di(g)=pg≤pji≤di(ji).d_i(g)=p_g \le p_{j_i} \le d_i(j_i).

Inactive bundles have price at least t>0t>0, and active agents each receive a swap chore, so all bundles are nonempty. This proves friendliness. The construction takes polynomial time by Lemma 8; when δ=0\delta=0, the factor is λ=3\lambda=3.

The Approximation Guarantee and Running Time

We are now in a position to complete the proof of Theorem 5, and that of the main result of our paper, Theorem 1.

Completing the proof of Theorem 5. Apply Algorithm 2 and then Algorithm 3. By Lemmas 6 and 9, this gives a λ\lambda-EFX-friendly allocation for λ=(3+2δ)/(1−2δ)\lambda=(3+2\delta)/(1-2\delta). By Theorem 6, at most nn chore swaps yield a λ\lambda-EFX allocation.

Since δ≤1/10\delta\le1/10, its approximation factor satisfies

λ=3+2δ1−2δ=3+8δ1−2δ≤3+10δ.\lambda= \frac{3+2\delta}{1-2\delta} = 3 + \frac{8\delta}{1-2\delta} \le3+10\delta.

Rounding takes polynomial time, and threshold selection uses O(n+∣H∣)O(n+|H|) events. The chore-swap procedure also takes polynomial time. Hence the full algorithm computes a (3+10δ)(3+10\delta)-EFX allocation from the given δ\delta-approximate ER equilibrium in polynomial time.

Proof of Theorem 1. For m≤2nm \le2n, use the known polynomial-time exact EFX algorithm Kobayashi et al. [22]; Garg et al. [20]. Otherwise, set δ=ε/10\delta= \varepsilon/10. Compute a δ\delta-approximate ER equilibrium with caps 1/21/2 using Theorem 3, and apply Theorem 5. The resulting allocation is (3+10δ)(3 + 10\delta)-EFX, and hence (3+ε)(3 + \varepsilon)-EFX.

Since 1/δ=10/ε1/\delta= 10/\varepsilon, the number of flow computations is O(1+nlog⁡(mR)/ε2)O(1 + n \log(mR)/\varepsilon^2). The remaining steps take polynomial time by Theorem 5. Thus the full running time is polynomial in the input length and 1/ε1/\varepsilon.

Conclusions

In this paper, we gave a polynomial-time algorithm for computing a (3+ε)(3 + \varepsilon)-EFX allocation of chores with additive disutilities. Our approach combines an FPTAS for equal-earnings ER equilibria with a novel threshold-based construction of EFX-friendly allocations. Two natural questions remain: can the polynomial-time EFX factor be improved to 2+ε2 + \varepsilon, matching the known existence guarantee up to an arbitrarily small loss, and can an ER FPTAS be obtained for arbitrary, non-identical earning requirements?

Statement of AI Use. The results of this paper were obtained in late September 2026; since then the author focused on polishing the exposition. The author used ChatGPT 5.6, 6, and 6.1 in developing the results and preparing this manuscript. The FPTAS for ER equilibria and was developed through interactions with ChatGPT. The author supplied the conceptual connections to Shmyrev’s formulation and spending-restricted equilibria, together with the associated intuition and market interpretation to formulate the new program for earning restricted equilibria. The convergence analysis of mirror-ascent was entirely due to ChatGPT. The idea of changing the price threshold for converting an ER rounded allocation to an EFX-friendly one originated during the author’s earlier work on Garg et al. [20] and Garg and Murhekar [16]. By choosing a different – but fixed – threshold, the author obtained a (2+3)(2 + \sqrt{3})-EFX bound. The improved construction using flexible thresholds was developed from this idea through a sequence of conversations with ChatGPT. The author takes full responsibility for the paper.

Polynomial-Time Implementation of the ER FPTAS

We show how to compute exact optimal flows with logarithmic costs and supporting prices whose encoding lengths are independent of the payouts. Let L\mathcal{L} be the binary encoding length of the rational market input, and take δ\delta to be rational. Set v=n+mv=n+m and choose B=O(L)B=O(\mathcal{L}) so that the numerator and denominator of each dijd_{ij} are at most 2B2^B.

Lemma 10 (Exact minimum-cost flows). For rational payouts q∈Qq \in\mathbb{Q}, an exact optimal basic flow for (13) can be computed in time polynomial in L\mathcal{L} and the encoding length of qq.

Proof. We approximate the costs closely enough to preserve every negative-cost simple residual cycle. A residual arc has cost log⁡dij\log d_{ij} or −log⁡dij-\log d_{ij}, so a simple cycle has cost log⁡(A/D)\log(A/D) for positive integers A,D≤2vBA,D \le2^{vB}. If A≠DA \ne D, then

∣log⁡(A/D)∣≥∣A−D∣max⁡{A,D}≥2−vB.\left|\log(A/D)\right| \ge\frac{|A-D|}{\max\{A,D\}} \ge2^{-vB}.

This bound determines how accurately we must approximate the costs. Compute rational approximations to the costs with error at most 2−vB/(4v)2^{-vB}/(4v). For this, write dij=2kud_{ij}=2^k u with 1≤u<21 \le u < 2 and use log⁡dij=klog⁡2+log⁡u\log d_{ij}=k\log2+\log u, evaluating the logarithms by a rapidly convergent series. This takes polynomial time. Each simple cycle has at most vv arcs, so its cost changes by at most 2−vB/42^{-vB}/4 and its sign is preserved whenever the original cost is nonzero. We now solve the rational minimum-cost flow problem, choosing an optimal basic flow. If this flow were not optimal for the original costs, it would have a negative simple residual cycle, which would remain negative under the approximated costs, a contradiction. Finally, the flow constraint matrix is totally unimodular. Clearing the denominators of the prescribed payouts therefore gives an integral basic flow, so the returned flow has polynomial encoding length.

Lemma 11 (Exact supporting prices). Given an optimal flow with positive chore payouts, we can compute in polynomial time positive rational numbers wj,αiw_j,\alpha_i, each with O(vB)O(vB) bits, such that αiwj≤dij\alpha_iw_j \le d_{ij} for all i,ji,j, with equality whenever bij>0b_{ij}>0.

Proof. Write Pj=log⁡wjP_j=\log w_j and Ai=−log⁡αiA_i=-\log\alpha_i. The required conditions become

Pj−Ai≤log⁡dij,Ai−Pj≤−log⁡dijif bij>0.P_j-A_i \le\log d_{ij}, \qquad A_i-P_j \le-\log d_{ij}\quad\text{if }b_{ij}>0.

By Lemma 1, these inequalities are feasible. Represent each inequality as a directed arc, and add a source with zero-length arcs to all vertices. Shortest-path distances then give feasible values for PjP_j and AiA_i.

Although the distances may be irrational, we only need their exponentials. Exponentiating replaces path-length sums by products of the rational numbers dijd_{ij}, 1/dij1/d_{ij}, and one. Thus we can run Bellman–Ford using multiplication in place of addition and exact rational comparisons. Feasibility excludes negative cycles, so each shortest path can be chosen simple and contains at most v−1v-1 arcs other than its source arc. Consequently, each exponentiated distance is a product of at most v−1v-1 such rationals and has O(vB)O(vB) bits. The values wj=ePjw_j=e^{P_j} and αi=e−Ai\alpha_i=e^{-A_i} therefore satisfy the required conditions exactly, with an encoding bound independent of qq.

By Lemma 3 and (21), τ,p,r\tau,p,r also have encoding lengths polynomial in L\mathcal{L}, independently of the iteration number. The initial payouts have polynomial encoding length, so all subsequent payouts do as well. By Lemma 10, each flow computation, rescaling, and agent earnings test therefore takes polynomial time. Since log⁡R\log R is polynomially bounded in L\mathcal{L}, the iteration bound proves that Algorithm 1 is an FPTAS.

The Chore-Swap Framework

We present the algorithm of Garg and Murhekar [16] underlying Theorem 6 and sketch why it works. Let YY be a λ\lambda-EFX-friendly allocation, with partition N=N0⊔NHN = N_0 \sqcup N_H, swap chores jij_i, and residual bundles RiR_i as in Definition 3. Write J={ji:i∈NH}J = \{j_i: i \in N_H\}. Fix an arbitrary order of the active agents and relabel them so that NH={1,…,k}N_H = \{1,\ldots,k\}. Algorithm 4 first reallocates JJ by letting these agents pick their least-disutility remaining chore in this order. It then performs chore swaps in the same order. Writing gig_i for the chore picked by agent ii, the crucial property of this ordering is di(gi)≤di(gh)d_i(g_i) \le d_i(g_h) whenever i<hi < h. This ordering preserves the λ\lambda-EFX guarantees of earlier agents.

Algorithm 4 Chore swaps from an EFX-friendly allocation (Garg and Murhekar [16])

Require: A λ\lambda-EFX-friendly allocation YY, with N0,NH,Ri,jiN_0, N_H, R_i, j_i as in Definition 3; NH={1,…,k}N_H = \{1,\ldots,k\}.

Ensure: A λ\lambda-EFX allocation XX.

  1. Xi←YiX_i \leftarrow Y_i for i∈N0i \in N_0; Xi←RiX_i \leftarrow R_i for i∈NHi \in N_H; J′←{ji:i∈NH}J' \leftarrow\{j_i: i \in N_H\}.

  2. Phase 1: Reallocate the swap chores.

  3. for i=1,…,ki = 1,\ldots,k do

  4. Choose gi∈arg⁡min⁡j∈J′dijg_i \in\arg\min_{j \in J'} d_{ij}.

  5. Xi←Ri∪{gi}X_i \leftarrow R_i \cup\{g_i\}; J′←J′∖{gi}J' \leftarrow J' \setminus\{g_i\}.

  6. Phase 2: Perform chore swaps in the picking order.

  7. for i=1,…,ki = 1,\ldots,k do

  8. if agent ii is not λ\lambda-EFX in XX then

  9. Choose ℓ∈arg⁡min⁡h∈Ndi(Xh)\ell\in\arg\min_{h \in N} d_i(X_h).

  10. (Xi,Xℓ)←(Ri∪Xℓ,{gi})(X_i, X_\ell) \leftarrow(R_i \cup X_\ell, \{g_i\}).

  11. return XX.

Proof sketch of Theorem 6. We explain why each iteration establishes λ\lambda-EFX for the agent being processed and preserves it for earlier agents. Every current bundle contains either a chore from JJ or an entire original bundle YhY_h for some h∈N0h \in N_0: a swap gives one agent a chore from JJ and adds a residual bundle to the other agent’s old bundle. Thus Definition 3 implies that, throughout Phase 2,

di(Ri)≤(λ−1)di(Xh)(i∈NH, h∈N).(34)d_i(R_i) \le(\lambda- 1)d_i(X_h) \qquad(i \in N_H,\ h \in N). \tag*{(34)}

Unprocessed agents retain their bundles. Inductively, before agent ii’s turn, every active agent h≥ih \ge i still holds Rh∪{gh}R_h \cup\{g_h\}. The picking order and friendliness give

di(Ri)+di(gi)≤(λ−1)di(gh)+di(gh)≤λdi(Xh).d_i(R_i) + d_i(g_i) \le(\lambda- 1)d_i(g_h) + d_i(g_h) \le\lambda d_i(X_h).

Hence ii is λ\lambda-envy-free towards all unprocessed agents. If she violates λ\lambda-EFX, a least-disutility bundle must therefore belong to an agent in N0∪{1,…,i−1}N_0 \cup\{1,\ldots,i-1\}. Thus no later agent participates in this swap.

A swap resolves the current agent’s envy. Let B=XℓB = X_\ell be the least-disutility bundle before an (i,ℓ)(i,\ell) swap. Agent ii receives Ri∪BR_i \cup B, while ℓ\ell is EFX with the singleton {gi}\{g_i\}. By (34) and the choice of BB, di(Ri∪B)≤λdi(Xh)d_i(R_i \cup B) \le\lambda d_i(X_h) for every unchanged bundle XhX_h. To compare with the new singleton, use the violation of λ\lambda-EFX before the swap and di(Ri)≤(λ−1)di(gi)d_i(R_i) \le(\lambda- 1)d_i(g_i):

di(Ri∪B)<di(Ri)+di(Ri)+di(gi)λ≤(1+1λ)(λ−1)di(gi)+1λdi(gi)=λdi(gi).\begin{aligned} d_i(R_i \cup B) &< d_i(R_i) + \frac{d_i(R_i) + d_i(g_i)}{\lambda} \\ &\le\left(1 + \frac{1}{\lambda}\right)(\lambda- 1)d_i(g_i) + \frac{1}{\lambda}d_i(g_i) = \lambda d_i(g_i). \end{aligned}

Later swaps preserve these guarantees. The only potentially problematic bundle created by a later swap is its singleton {gh}\{g_h\}: the other new bundle contains a whole old bundle. An earlier agent ii who now holds a singleton is EFX. Otherwise, if she initiated a swap, the bound just proved gives di(Xi)≤λdi(gi)≤λdi(gh)d_i(X_i) \le\lambda d_i(g_i) \le\lambda d_i(g_h). If she skipped her turn, the same comparison follows from Xi=Ri∪{gi}X_i = R_i \cup\{g_i\}, friendliness, and the picking order. An inactive agent either retains her original bundle, which is bounded by λdi(gh)\lambda d_i(g_h) by friendliness, or holds a singleton. These observations show inductively that all inactive and processed agents remain λ\lambda-EFX.

After the last iteration, all agents are λ\lambda-EFX. Each active agent initiates at most one swap, and each iteration takes polynomial time. Thus the algorithm uses at most ∣NH∣≤n|N_H| \le n swaps and runs in polynomial time. The full inductive proof appears in Garg and Murhekar [16].

References

  1. [1]Mahyar Afshinmehr, Matin Ansaripour, Alireza Danaei, and Kurt Mehlhorn. Approximate EFX and exact tEFX allocations for indivisible chores: Improved algorithms, 2024. URL https://arxiv.org/abs/2410.18655.
  2. [2]Siddharth Barman and Sanath Krishnamurthy. On the proximity of markets with integral equilibria. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pages 1748–1755, 2019.arxiv.org/abs/1811.08673
  3. [3]Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 557–574, 2018.arxiv.org/abs/1707.04731
  4. [4]Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167–175, 2003. doi: 10.1016/S0167-6377(02)00231-6. URL https://www.tau.ac.il/~becka/3.pdf.DOI
  5. [5]Anna Bogomolnaia, Hervé Moulin, Fedor Sandomirskiy, and Elena Yanovskaya. Competitive division of a mixed manna. Econometrica, 85(6):1847–1871, 2017. doi: 10.3982/ECTA14564. URL https://arxiv.org/abs/1702.00616.
  6. [6]Shant Boodaghian, Bhaskar Ray Chaudhury, and Ruta Mehta. Polynomial time algorithms to find an approximate competitive equilibrium for chores. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 2285–2302, 2022. URL https://arxiv.org/abs/2107.06649.
  7. [7]Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. Competitive equilibrium with chores: Combinatorial algorithm and hardness. In Proceedings of the ACM Conference on Economics and Computation, pages 1106–1107, 2022. doi: 10.1145/3490486.3538255. URL https://arxiv.org/abs/2205.11363.
  8. [8]Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, and Tianlong Nan. Competitive equilibrium for chores: From dual Eisenberg–Gale to a fast, greedy, LP-based algorithm. In Proceedings of the ACM Conference on Economics and Computation, 2024. URL https://arxiv.org/abs/2402.10439.
  9. [9]He Chen, Chonghe Jiang, and Anthony Man-Chao So. Computing competitive equilibrium for chores: Linear convergence and lightweight iteration, 2024. URL https://arxiv.org/abs/2410.04036.
  10. [10]Richard Cole and Vasilis Gkatzelis. Approximating the Nash social welfare with indivisible items. In Proceedings of the ACM Symposium on Theory of Computing, pages 371–380, 2015. doi: 10.1145/2746539.2746589.DOI
  11. [11]Richard Cole, Nikhil R. Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V. Vazirani, and Sadra Yazdanbod. Convex program duality, Fisher markets, and Nash social welfare. In Proceedings of the ACM Conference on Economics and Computation, pages 459–460, 2017. URL https://arxiv.org/abs/1609.06654.
  12. [12]Soroush Ebadian, Dominik Peters, and Nisarg Shah. How to fairly allocate easy and difficult chores. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2022. URL https://arxiv.org/abs/2110.11285.
  13. [13]Edmund Eisenberg and David Gale. Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics, 30(1):165–168, 1959. doi: 10.1214/aoms/1177706369. URL https://www.jstor.org/stable/2237130.DOI
  14. [14]Duncan K. Foley. Resource allocation and the public sector. Yale Economic Essays, 7(1):45–98, 1967.
  15. [16]Jugal Garg and Aniket Murhekar. Existence of 2-EFX allocations of chores. Proceedings of the AAAI Conference on Artificial Intelligence, 40(20):16922–16929, 2026. doi: 10.1609/aaai.v40i20.38738. URL https://arxiv.org/abs/2507.19461.
  16. [17]Jugal Garg, Aniket Murhekar, and John Qin. Fair and efficient allocations of chores under bivalued preferences. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5):5043–5050, 2022. doi: 10.1609/aaai.v36i5.20436. URL https://arxiv.org/abs/2110.09601.
  17. [18]Jugal Garg, Aniket Murhekar, and John Qin. New algorithms for the fair and efficient allocation of indivisible chores. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI), pages 2710–2718, 2023.DOI
  18. [19]Jugal Garg, Aniket Murhekar, and John Qin. Weighted EF1 and PO allocations with few types of agents or chores. Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), 2024.arxiv.org/abs/2402.17173
  19. [20]Jugal Garg, Aniket Murhekar, and John Qin. Constant-factor EFX exists for chores. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1580–1589, 2025. doi: 10.1145/3717823.3718305. URL https://arxiv.org/abs/2407.03318.
  20. [21]Wentao He and Biaoshuai Tao. EFX for additive chores: Nonexistence, Pareto incompatibility, and bi-valued existence, 2026. URL https://arxiv.org/abs/2606.08872.
  21. [22]Yusuke Kobayashi, Ryoga Mahara, and Souta Sakamoto. EFX allocations for indivisible chores: Matching-based approach. In Algorithmic Game Theory, pages 257–270, 2023.
  22. [23]Zehan Lin, Xiaowei Wu, and Shengwei Zhou. Approximately EFX and fPO allocations for bivalued chores. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 3952–3960, 2025. doi: 10.24963/ijcai.2025/440. URL https://www.ijcai.org/proceedings/2025/440.DOI
  23. [24]Ryoga Mahara. A polynomial-time algorithm for fair and efficient allocation with a fixed number of agents, 2024. URL https://arxiv.org/abs/2411.01810.
  24. [25]Ryoga Mahara. Existence of fair and efficient allocation of indivisible chores. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 6742–6766, 2026. doi: 10.1137/1.9781611978971.242. URL https://arxiv.org/abs/2507.09544.
  25. [26]A. Mas-Colell, M.D. Whinston, and J.R. Green. Microeconomic Theory. Oxford University Press, 1995.
  26. [27]Genjie Qin, Qizhi Fang, Minming Li, Wenjing Liu, and Xin Chen. Polynomial-time approximate EFX for chores via flow and matching, 2026. URL https://arxiv.org/abs/2611.07468.
  27. [28]V. I. Shmyrev. An algorithm for finding equilibrium in the linear exchange model with fixed budgets. Journal of Applied and Industrial Mathematics, 3(4):505–518, 2009. doi: 10.1134/S1990478909040097.DOI
  28. [29]Shengwei Zhou and Xiaowei Wu. Approximately EFX allocations for indivisible chores. Artificial Intelligence, 326:104037, 2024. doi: 10.1016/j.artint.2023.104037.DOI

Paper details

vlnc:W_hxdbh6ef
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents