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 , computes a -EFX allocation in time polynomial in the input length and . 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 -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 is EFX if for all agents and ; here denotes agent ’s additive disutility function and 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 -EFX allocation, where , the above inequality is relaxed to . Smaller values of give stronger fairness guarantees, with 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 -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 is constant.
For general , 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 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 , a -EFX allocation can be computed in time polynomial in the input length and .
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 -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 aims to earn 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 has an earning limit on the total amount it can pay to the agents. At prices , it pays out ; when its price exceeds this limit, it is only partially allocated. When earning caps 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 , 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 and arbitrary positive earning limits satisfying .
Theorem 2. For every , 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 . Each agent earns an amount in , 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 . With earning limits, a chore can be partially allocated and its payout is , so prices need no longer sum to . We therefore work with the chore payouts , which still sum to and satisfy the simple bounds .
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 , denoting the amount agent spends on good , and total spending . It maximizes over nonnegative money flows and total spending , subject to each agent spending one and the caps ; here is agent ’s value for good . 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, denotes the money agent earns from chore , and 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 , minimizing , subject to each agent earning one and each chore paying out , 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 over feasible payouts. The resulting program, -, 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 . 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 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 -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 -EFX allocation in polynomial time from a suitable starting allocation, called -EFX-friendly. In such an allocation, the inactive agents are already -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 -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 and exact earnings, each agent receives at most two chores of price above . 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 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 for a -approximate ER equilibrium. Choosing sufficiently small relative to and applying the chore-swap framework yields a -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 , 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 for some , Lin et al. [23] compute a -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 -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 for a positive integer .
Problem instance. A chore division instance consists of a set of agents, a set of indivisible chores, and a list of additive disutility functions.
We let denote the disutility of chore for agent , and define the disutility ratio
For , we have .
An allocation is a partition of the chores, where denotes the bundle assigned to agent . A fractional allocation assigns a fraction of chore to agent , with for each chore . Agent ’s disutility under fractional allocation is . Allocations are integral unless stated otherwise.
Fairness notions. For , agent is -envy-free (-EF) in allocation if for every . Agent is -EFX in allocation if
An allocation is -EF or -EFX if the above condition holds for every agent. By definition, an agent assigned a singleton bundle is EFX. For a positive integer , an allocation is -EF, if, for every , there exists with such that . When , this becomes the well-studied EF1 fairness notion.
Prices and MPB allocations. Let be chore prices, where is the payment per unit of chore . Let and denote the prices of bundles and , respectively. The minimum pain-per-buck (MPB) ratio of agent and her set of MPB chores are
An allocation-price pair is MPB if implies for all , i.e., an agent only performs chores that minimize her disutility to payment ratio. For an integral allocation, this means for every .
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 ’s disutilities by and obtain
We use this normalization when analyzing the rounding and chore-swap algorithms.
For an integral allocation and a positive integer , let
This is the price remaining after removing up to highest-price chores from . The pair is -price-EF (-pEF) if for all . An MPB allocation that is -pEF is also -EF, by (1). For , 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 is Pareto-optimal (PO) if no integral allocation satisfies for every agent , with strict inequality for at least one agent. It is fractionally Pareto-optimal (fPO) if no complete fractional allocation satisfies for every agent , with strict inequality for at least one agent. Here, completeness means that for every chore . 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 , there exists a positive price vector such that is MPB. Thus an allocation is fPO if and only if it admits supporting MPB prices.
Earning-Restricted Equilibria
An earning-restricted (ER) market consists of a chore division instance , agent earning requirements , and chore earning limits or caps . Each agent aims to earn by performing chores of least possible disutility, while the agents are restricted to collectively receive at most from chore . An equilibrium specifies a fractional allocation and prices that meet these requirements.
Definition 1 (ER equilibrium, Garg et al., [20]). A pair is an earning-restricted equilibrium if
(i) is MPB and for every agent ;
(ii) for every chore .
Condition (i) requires each agent to earn her requirement using only MPB chores. It enforces agent optimality: the bundle minimizes ’s disutility among all bundles that meet its earning requirement through .
Condition (ii) imposes the earning restriction: if , chore is fully allocated and pays out ; otherwise, only a fraction is allocated and the payout is . Garg et al. [20] show that an ER equilibrium exists if and only if . Our algorithmic result concerns equal earning requirements. Hence, we normalize them to for all , and assume .
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 , a pair is a -approximate ER equilibrium with unit earning requirements if
Remark 1 (The total earning constraint). Summing Eq. (2) over all agents gives . The usual relaxation of ER equilibrium allows the total earning to vary within this range, whereas Eq. (5) requires it to equal . 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 denote the earning of agent from chore , and let denote the total payout of chore . For an allocation , these quantities are given by
In these variables, the agent earning requirement becomes , and the earning restriction becomes . Since prices are positive, if and only if , so the MPB condition is preserved as well. Consequently, the approximate ER conditions can equivalently be written as
We will describe our equilibrium algorithm using these money flows. When and are specified, each chore’s payout is , and we abbreviate the solution as . Conversely, given money flows and prices satisfying the above conditions, define . The total fraction of chore allocated is , and the earnings and MPB assignments are unchanged. Thus 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 for every agent, that all disutilities and earning limits are positive, and that . Our algorithm returns money flows and prices satisfying (7), which are equivalent to the conditions in Definition 2. Let denote the largest ratio between an agent’s maximum and minimum disutility.
Theorem 3. Let be an ER market with unit earning requirements and . For any , Algorithm 1 computes a -approximate ER equilibrium using at most
minimum-cost flow computations. Each iteration takes polynomial time, so the algorithm is an FPTAS. If , 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 for good .1 Write . 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.
The primal variables describe the allocation, while the dual variables are the prices of goods and is the reciprocal of agent ’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.
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 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 as an agent’s disutility approaches zero, and the dual-like objective tends to as some 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 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 fraction of chore is allocated, so the total earning condition becomes . Adding would bound prices rather than payouts and could exclude valid ER equilibria with . Moreover, the price-sum constraint may exclude every ER equilibrium, as the following example shows.
Example 1 (Price normalization). Consider two chores and one agent with disutilities , earning requirement one, and earning limits . The ordinary chore equilibrium has prices . If we impose the earning limits at these prices, the total payout is , and the agent cannot earn one. In an ER equilibrium, both chores must pay out , and the MPB condition requires their prices to be in ratio . Thus prices support an ER equilibrium with allocation . Moreover, every ER price vector has price sum at least . 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 , unit earning requirements, and earning limits . Prices and earnings for all 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 of a chore , keeping it distinct from its price . In these variables, we can impose the earning limits directly through and maintain the total payout . We must then find supporting MPB prices that satisfy .
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 is restricted to . If its price exceeds , only a 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 to EG-Dual and then taking its dual gives Shmyrev’s formulation for ordinary goods markets. Its variables are and , denoting the total spending on good and the money agent spends on good , respectively. Since this program has money-flow variables, it can be adapted to incorporate spending limits. Adding the constraints to Shmyrev’s program gives the SR program of Cole et al. [11]:
We use the convention for the entropy term . The first two constraints already imply . With these bounds, prices are recovered from the dual variables and satisfy . 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)
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 and earning limits . Its objective is , which is minimized at payouts or . However, the ER equilibrium has payouts and prices .
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 . 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 and earning limits . Since , maximizing the objective amounts to
The maximizer is . Taking these payouts as prices makes both chores MPB, since . Both chores are fully allocated and the agent earns one.
Now reduce the second chore’s earning limit to . Maximizing the same objective subject to this cap gives payouts . These payouts cannot themselves serve as prices, since at equal prices the agent would prefer the first chore. Instead, prices 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 .
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 receives of the total payout from chore , and earns one in total. For fixed payouts , we must choose the money flows to ensure agent optimality, i.e., the MPB condition. We show that minimizing 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 be the set of feasible chore payouts:
For fixed , we distribute the payouts by solving the following program:
This is a minimum-cost flow problem: the constraints require each agent to earn one and each chore to pay out , and sending one unit from chore to agent has cost . The problem is feasible for every , since satisfies these constraints. Let denote its set of feasible money flows.
Our program for ER equilibria, termed ER-MaxMin, is presented below.
(ER-MaxMin)
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 and corresponding to the agent and chore constraints in Eq. (13), we obtain
This is a linear program in and . The logarithmic costs are what give the desired MPB guarantee: the additive dual inequalities become after exponentiation.
Lemma 1 (Minimum-cost flows and MPB prices). For every , a flow is optimal if and only if it admits supporting MPB prices. Every optimal dual supplies such prices for every optimal flow, with equal to agent ’s MPB ratio.
Proof. For any optimal flow and optimal dual , complementary slackness gives
Thus agents receive money only from their MPB chores. Conversely, if a feasible flow is MPB at some prices , then its MPB ratios give a feasible dual that is tight on every positive flow edge. Hence 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 only bounds a chore’s payment; an ER equilibrium additionally requires . 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 denote its objective, where
For fixed positive prices , define over .
Lemma 2 (Convexity and a concave lower bound). The function is convex on . For any , any optimal dual at , and every ,
Thus is a subgradient of at . Moreover, the function
is concave and satisfies for all F_q(q)=V(q)$.
Proof. An optimal dual at remains feasible for every , so
This proves (16) and the subgradient claim. By (15), is the pointwise maximum of affine functions of the payouts, so it is convex. Finally, (16) gives , with equality at . The function is concave because it is an affine function minus the convex function .
Proposition 4 (Local maxima yield ER equilibria). Every local maximizer of ER-MaxMin (14) is positive. For any optimal flow and dual at , there is a scalar such that is an exact ER equilibrium and for every chore .
Proof. Fix a local maximizer and optimal flow and dual solutions and . By Lemma 2, is a lower bound on that is tight at . Hence locally maximizes , and therefore also , since the two functions differ by a constant.
We show that must be positive. If , transfer an amount to coordinate from a positive coordinate. Since , this is feasible for sufficiently small . The change in is , contradicting optimality.
The first-order optimality conditions for on the polytope now give a scalar and multipliers satisfying
Set and . Then . If , complementary slackness gives and ; if , we have . Therefore in both cases. By Lemma 1, the flow is MPB at , and hence at . Since also gives every agent earning one enforced by the constraint in Eq. (13), 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 as the mirror map. As we show below, the resulting mirror-ascent step maximizes the concave lower bound from Lemma 2.
To define the update, fix a positive payout vector and solve the flow program (13) to obtain an optimal flow and supporting prices from its dual. By Lemma 2, is a subgradient of at . Subtracting the gradient of gives the direction for the first-order approximation of . When is differentiable, ; otherwise, this construction uses the subgradient supplied by the flow dual. The divergence generated by on is the relative entropy
The second equality uses . Rearranging this identity for and substituting into the lower bound from Lemma 2 gives
Thus, maximizing over is a mirror-ascent step with step size one. Let be the updated payouts computed by maximizing over . By Eq. (17), differs from by a constant, so computing amounts to maximizing over . The proof of Theorem 4 shows that, at a local maximum of ER-MaxMin, the current payouts already maximize . The mirror-ascent update performs this maximization at each iteration. Therefore, the same optimality conditions give the updated payouts 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 , the problem
has a unique maximizer. It is positive and has the form for some , so that . For rational , such a and vector can be computed in polynomial time.
Proof. As increases from zero, increases continuously from zero to , so a suitable exists. The resulting is positive and satisfies the optimality conditions used in Theorem 4, with and . Strict concavity of proves uniqueness.
We show how to compute . If , taking makes every chore pay its cap, so . Therefore, suppose . Sort and relabel the chores so that , and consider the intervals . Index these intervals by . If lies in interval , the first chores are capped and the remaining chores pay . Thus the normalization condition becomes the linear equation , whose solution is
For each of the first 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 . Hence one of the checks must succeed in finding , and we return . Sorting and checking these intervals take polynomial time for rational and .
The mirror-ascent step is useful since it can only improve the objective: the updated payouts satisfy due to Lemma 2.
Consider a mirror-ascent step at payouts and corresponding optimal money flows . Let be the updated payouts and be the prices computed using Lemma 3. If , then is an exact ER equilibrium. In general, we match the new payouts by rescaling the money flow as
This preserves MPB assignments because the rescaling leaves the support of unchanged, and uniformly scaling prices from to preserves each agent’s MPB chores. Moreover, , as required by the earning limits. Individual earnings, however, may change from one to . Thus we return if every lies in ; otherwise, we set and begin the next iteration.
To initialize the iteration, we apply Lemma 3 to uniform weights . 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 of Algorithm 1 satisfies exact MPB optimality, capped chore payouts, and total earning . If the stopping condition holds, it is a -approximate ER equilibrium.
Algorithm 1 Approximate ER equilibrium with equal earnings
Input: Instance with ; accuracy
Output: A -approximate ER equilibrium
Initialize , choosing so
loop
Solve (13) at , obtaining an optimal flow and supporting prices
Compute the price scale using Lemma 3
Set and for every
Set and
if for every then
return
Proof. By Lemma 1, is MPB at , and hence at . The rescaling in Eq. (22) preserves its support, and
These payouts sum to . 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 by a definite amount. Without loss of generality, we assume for all , .
Lemma 5 (Progress in each iteration). Every iteration of Algorithm 1 that does not terminate increases by at least .
Proof. Let and be the payouts before and after a mirror-ascent step, and let be the supporting prices at . By Lemma 3, maximizes over , so first-order optimality gives . Using Lemma 2 and the entropy identity (18) at , we obtain
We next relate this bound to the agent earnings after rescaling. A small payout can make the ratio large, so we apply the log-sum inequality to the payments each agent receives from the chores. Let be the unit-earning flow and its rescaling, and define for . Then
The first equality follows from the rescaling and . The last two equalities use the original unit earnings and , respectively.
The function is nonnegative and vanishes only at one. For , if , then
Indeed, decreases below one and increases above one, and ; the corresponding deviation below one has at least this value. Since the iteration does not terminate, some agent has . Hence , and (23) proves the claim.
Completing the proof of Theorem 3. We first bound the total increase available to . Since , we have . Convexity of , together with and , gives . Since , it follows that for all . Thus the range of over is at most .
By Lemma 5, each nonterminating iteration increases by at least . Hence there are at most such iterations. Including the final iteration gives the bound in Theorem 3. If , then and every update has , 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 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 , replacing each agent’s unit earning requirement by and total payout by . The earning-error argument in Lemma 5 then guarantees progress of at least , where . This yields iterations. The ratio 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+)-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 -approximate ER equilibrium with unit earning requirements and earning limits , where , we can compute a -EFX allocation in time polynomial in the input length and .
We use the chore-swap framework of Garg and Murhekar [16], which begins with a suitable initial allocation satisfying a certain condition called -EFX-friendliness, for parameter . It iteratively resolves the envy of agents by performing chore swaps: an agent who violates -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 -EFX for that agent and preserves this guarantee for agents who are already processed. Thus the framework computes a -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 -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 -EFX-friendly allocation, which has two types of agents, active and inactive. The inactive agents are already -envy-free. Each active agent has one swap chore, while her other chores form a residual bundle of small disutility. If she violates -EFX, she can exchange her swap chore for a least-disutility bundle while retaining her residual bundle. The factor in the definition below leaves room for this exchange: if the residual costs at most , adding bundle gives total disutility at most . The definition imposes the comparisons that allow the swaps to be performed while preserving the fairness guarantees of other agents.
Definition 3 (-EFX-friendly allocation, Garg and Murhekar [16]). Let and let be an allocation with nonempty bundles. The allocation is -EFX-friendly if there are a partition and a swap chore for each such that, writing for agent 's residual bundle,
Here and are the sets of active and inactive agents, respectively. The first two inequalities imply that each inactive agent is -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 -EFX.
Theorem 6 (Garg and Murhekar [16]). Given a -EFX-friendly allocation, a -EFX allocation can be computed in polynomial time using at most 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 -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 -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 -EFX-friendly allocation. Our approach is to round a -approximate ER equilibrium, and transform the rounded solution into a -EFX-friendly allocation. We discuss these algorithms in the following sections.
Rounding an Approximate ER Equilibrium
When , an exact EFX allocation can be computed in polynomial time ([22, 20]). We therefore assume . Let be a -approximate ER equilibrium with unit earning requirements and earning limits , where . For , Algorithm 1 computes such an equilibrium since .
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 . We first describe their algorithm and its guarantees. Let and denote the sets of low-price and high-price chores, respectively.
The rounding algorithm. Define the payment graph of as the bipartite graph on with an edge of weight whenever . 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 , let and . When the input is an exact ER equilibrium, the analysis of Garg et al. [20] gives, for every agent ,
Approximate ER equilibria. Our FPTAS, however, only gives a -approximate ER equilibrium, in which each agent’s earning lies in . 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 . In the ER flow, two are supported only by agent 1, one only by agent 2, and the fourth pays to agent 1 and to agent 2, where . Agent 3 alone performs three low-price chores of price each. The earnings are , 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 .
Algorithm 2 ER rounding, adapted from Garg et al. [20]
Input: An approximate ER equilibrium with unit earnings and earning limits
Output: An integral MPB allocation
Cancel cycles in the payment graph; root every resulting tree at an agent
for every ; let and
Assign each leaf chore to its only adjacent agent and delete it
for each agent , in breadth-first order in the original rooted forest do
if then
for each remaining child chore of do
Assign to a child maximizing ; delete
while some remaining child satisfies do
Assign to ; delete
Assign every remaining child chore to any child agent of ; delete
For each remaining chore, retain its parent edge and one child edge maximizing
for each remaining tree do
Choose maximizing
Match its chores to along retained edges, and assign them
return
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 . We prove the following.
Lemma 6 (Rounding with approximate earnings). Let . Given a -approximate ER equilibrium with unit earnings and earning limits $1/2, Algorithm 2 returns an integral MPB allocation in polynomial time. For every agent , with and , we have
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 for agent ’s original earning, so .
Upper bounds. Let be the original leaf chores assigned to agent in Phase 1. Since a low-price leaf pays its full price and a high-price leaf pays , we have
In particular, contains at most two high-price chores. When is visited in Phase 2, her current bundle consists of and possibly her original parent chore.
If this bundle has price at most one, the low-price assignments keep it at most one. Agent 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 . Therefore , and .
Otherwise the bundle price at ’s visit exceeds one. All her child chores are passed down or removed. Thus her final bundle consists of 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 . If it is high-price and assigned to , it contributes one to and nothing to , giving . If the parent is not assigned to , the bound is stronger. In every case and the upper bound in (26) follows.
When , two high-price original leaves consume the entire unit earning of . Such an agent cannot have a positive parent edge, so cannot obtain a third high-price chore. This gives in the exact case.
Lower bound. Consider a Phase-3 tree , and let be an agent of maximum current bundle price. Every other agent receives a high-price chore in Phase 4, so obtains price greater than . It suffices to lower-bound , which equals ’s price before Phase 4.
Suppose some agent 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 . Bundle prices only increase during rounding. By the choice of , we therefore have in this case.
Otherwise no agent in 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 high-price chores remaining inside , except possibly for the original parent chore of the root of . This exceptional chore accounts for at most of the root’s original earning. Every internal high-price chore also pays out . Since every agent originally earned at least , the sum of their current bundle prices is at least
Therefore some agent in , and hence also the maximum-price agent , has bundle price at least . This proves the lower bound.
We will use these rounding bounds in § 4.4 to construct a -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 be the allocation and prices obtained by rounding an exact ER equilibrium with unit earnings and earning limits . Thus satisfies (25). Normalize disutilities by the MPB ratios of , 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 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 as her residual bundle. Thus a fixed threshold of 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 obtained by rounding an exact ER equilibrium with unit earning requirements and earning limits , a 4-EFX-friendly allocation can be constructed in polynomial time.
Proof. We use the bounds in (25). In particular, , and every agent’s low-price chores have total price at most .
If , assign one high-price chore to each of agents, including every original owner of a high-price chore, while retaining all low-price chores. Denote the resulting allocation by . The high-price chore recipients form ; all other agents are inactive and keep . Every inactive agent has disutility at most for her bundle, while every inactive bundle and every swap chore has price at least . Thus the first two conditions of Definition 3 hold even with factor three.
If , apply the few-chores EFX algorithm of Garg et al. [20] to , ordering the original owners of high-price chores first. There are at least such agents, since each originally owns at most two high-price chores and . The algorithm returns an EFX allocation with nonempty bundles, where only the first agents can receive several chores. Set , let , and let . For every inactive agent , we have , and hence . Let be a least-disutility chore in . Since and is EFX,
Consequently,
since . When is active, is its singleton swap chore; when is inactive, . This proves the first two friendliness conditions.
In both cases, every active agent retains a residual bundle of disutility at most . Every inactive bundle and every swap chore has price at least $1/2, so the last two friendliness conditions hold with factor . Each swap chore is also a highest-disutility chore for its recipient: its disutility is at least its price, which exceeds , whereas every residual chore has disutility equal to its price and at most . 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 -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 , while a swap chore can have price arbitrarily close to . Comparing these quantities in the friendliness condition gives , and hence . 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 and let and . Suppose the rounded allocation is , , , where each entry denotes the price of a distinct chore, equal to every agent’s disutility for that chore.
The fixed threshold is : the construction in Lemma 7 sets aside all five chores of price for reallocation, while each agent retains her low-price chores. In particular, agent 1 retains , of disutility . 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 , and hence EFX-friendliness requires , or
This approaches factor 4 as approaches 0. Thus this construction cannot guarantee -EFX-friendliness for any fixed .
To avoid this loss, we allow the threshold to increase from to . Starting again from , set aside the five high-price chores as candidate swap chores. At the new threshold , 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 , , and the active residual bundles are and . We have
Every swap chore has disutility 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 . Hence 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 obtained by rounding a -approximate ER equilibrium with unit earning requirements and earning limits . Our construction uses the joint bounds in Lemma 6, which allow an agent to hold three high-price chores.
We begin with a threshold and consider all high-price chores to be candidate swap chores. Our algorithm iteratively increases the price threshold 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 and remain defined by the fixed cutoff throughout.
The required price bounds. At any stage of the construction, let denote the current set of candidate swap chores and the residual bundle of agent . Normalize disutilities using the MPB ratios of . Since residual chores remain with their original owners, , while any other bundle has disutility at least its price. To obtain a -EFX-friendly allocation, for a factor , we seek a partition , with , satisfying
Each active agent then receives one distinct chore from . These bounds give the four disutility comparisons in Definition 3. We will maintain the upper bound 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 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 and candidate set , write
The agents in are eligible: their residual bundles are small enough for them to receive a swap chore. The agents in are deficient: they must receive a swap chore, since otherwise their bundles would have price below . Hence we need and . Such a choice exists precisely when
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 and . To ensure that there are initially enough candidate chores for all deficient agents, set , the lower bound on rounded bundle prices. Indeed, if , then must contain a high-price chore because . Thus each initially deficient agent owns a distinct candidate chore. This choice of uses the lower bound on whole bundles; the candidate set is still .
Initially, the residual prices satisfy . To ensure at the start, set
Since , we have . For an exact ER input, , giving the bounds for inactive bundles and for active residual bundles seen in Example 6. We will use the joint rounding bound to show that continues to hold as chores return to their owners’ residual bundles.
While , there are too many candidate chores for the eligible agents. We either return a candidate chore of price to its original owner or, if none has this price, increase . A threshold increase stops at the next candidate price or the next value 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 cannot become deficient during a single threshold increase: she becomes eligible at , before becoming deficient at .
We stop as soon as . 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 . 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 is nonempty whenever the while-condition holds.
Lemma 8 (Properties of the threshold procedure). Algorithm 3 terminates after events. At termination,
Each consists of and returned high-price chores originally assigned to in , each of price at most .
Proof. By construction, residual chores remain with their original owners. Candidate chores have price at least , and returned high-price chores have price at most . Chores of price exactly 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 reaches , no high-price chore can be returned, so
For , returned chores increase the residual price. However, the upper bound on decreases by for each high-price chore originally assigned to . By Lemma 6 and ,
The second inequality uses and ; the last uses 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 must own a high-price chore, since . Choosing one such owned chore per deficient agent gives . Before every nonterminal event,
because . Returning one chore decreases by one and can only shrink , since stays fixed and the owner’s residual price increases. The strict inequality in (31) therefore gives after the return, even if the owner leaves .
Suppose instead that the threshold increases to . By the choice of the next event, every agent outside the old has , and hence cannot belong to the new . Therefore
This proves after each event, including the first one at which the stopping condition holds.
Number of events. At most chores are returned. Between returns, increasing can only add agents to . Each return removes at most one agent from , so at most entries into 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 events. If 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 -EFX-friendly allocation in polynomial time, for in (29). For an exact ER input, the resulting allocation is 3-EFX-friendly.
Proof. By Lemma 8, the algorithm can choose with and . In the resulting allocation , every active agent receives one swap chore and every inactive agent keeps her residual bundle. The definitions of , together with , give
Thus (28) holds. Since retained chores were originally assigned on MPB edges, . Every inactive bundle and every swap chore has price at least , so
for every . These are the four inequalities in Definition 3.
It remains to check that each swap chore is a highest-disutility chore in its recipient’s bundle. By Lemma 8, every has price at most , whereas and . Hence
Inactive bundles have price at least , 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 , the factor is .
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 -EFX-friendly allocation for . By Theorem 6, at most chore swaps yield a -EFX allocation.
Since , its approximation factor satisfies
Rounding takes polynomial time, and threshold selection uses events. The chore-swap procedure also takes polynomial time. Hence the full algorithm computes a -EFX allocation from the given -approximate ER equilibrium in polynomial time.
Proof of Theorem 1. For , use the known polynomial-time exact EFX algorithm Kobayashi et al. [22]; Garg et al. [20]. Otherwise, set . Compute a -approximate ER equilibrium with caps using Theorem 3, and apply Theorem 5. The resulting allocation is -EFX, and hence -EFX.
Since , the number of flow computations is . The remaining steps take polynomial time by Theorem 5. Thus the full running time is polynomial in the input length and .
Conclusions
In this paper, we gave a polynomial-time algorithm for computing a -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 , 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 -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 be the binary encoding length of the rational market input, and take to be rational. Set and choose so that the numerator and denominator of each are at most .
Lemma 10 (Exact minimum-cost flows). For rational payouts , an exact optimal basic flow for (13) can be computed in time polynomial in and the encoding length of .
Proof. We approximate the costs closely enough to preserve every negative-cost simple residual cycle. A residual arc has cost or , so a simple cycle has cost for positive integers . If , then
This bound determines how accurately we must approximate the costs. Compute rational approximations to the costs with error at most . For this, write with and use , evaluating the logarithms by a rapidly convergent series. This takes polynomial time. Each simple cycle has at most arcs, so its cost changes by at most 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 , each with bits, such that for all , with equality whenever .
Proof. Write and . The required conditions become
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 and .
Although the distances may be irrational, we only need their exponentials. Exponentiating replaces path-length sums by products of the rational numbers , , 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 arcs other than its source arc. Consequently, each exponentiated distance is a product of at most such rationals and has bits. The values and therefore satisfy the required conditions exactly, with an encoding bound independent of .
By Lemma 3 and (21), also have encoding lengths polynomial in , 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 is polynomially bounded in , 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 be a -EFX-friendly allocation, with partition , swap chores , and residual bundles as in Definition 3. Write . Fix an arbitrary order of the active agents and relabel them so that . Algorithm 4 first reallocates by letting these agents pick their least-disutility remaining chore in this order. It then performs chore swaps in the same order. Writing for the chore picked by agent , the crucial property of this ordering is whenever . This ordering preserves the -EFX guarantees of earlier agents.
Algorithm 4 Chore swaps from an EFX-friendly allocation (Garg and Murhekar [16])
Require: A -EFX-friendly allocation , with as in Definition 3; .
Ensure: A -EFX allocation .
for ; for ; .
Phase 1: Reallocate the swap chores.
for do
Choose .
; .
Phase 2: Perform chore swaps in the picking order.
for do
if agent is not -EFX in then
Choose .
.
return .
Proof sketch of Theorem 6. We explain why each iteration establishes -EFX for the agent being processed and preserves it for earlier agents. Every current bundle contains either a chore from or an entire original bundle for some : a swap gives one agent a chore from and adds a residual bundle to the other agent’s old bundle. Thus Definition 3 implies that, throughout Phase 2,
Unprocessed agents retain their bundles. Inductively, before agent ’s turn, every active agent still holds . The picking order and friendliness give
Hence is -envy-free towards all unprocessed agents. If she violates -EFX, a least-disutility bundle must therefore belong to an agent in . Thus no later agent participates in this swap.
A swap resolves the current agent’s envy. Let be the least-disutility bundle before an swap. Agent receives , while is EFX with the singleton . By (34) and the choice of , for every unchanged bundle . To compare with the new singleton, use the violation of -EFX before the swap and :
Later swaps preserve these guarantees. The only potentially problematic bundle created by a later swap is its singleton : the other new bundle contains a whole old bundle. An earlier agent who now holds a singleton is EFX. Otherwise, if she initiated a swap, the bound just proved gives . If she skipped her turn, the same comparison follows from , friendliness, and the picking order. An inactive agent either retains her original bundle, which is bounded by by friendliness, or holds a singleton. These observations show inductively that all inactive and processed agents remain -EFX.
After the last iteration, all agents are -EFX. Each active agent initiates at most one swap, and each iteration takes polynomial time. Thus the algorithm uses at most swaps and runs in polynomial time. The full inductive proof appears in Garg and Murhekar [16].
References
- [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]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]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]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]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]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]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]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]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]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]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]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]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]Duncan K. Foley. Resource allocation and the public sector. Yale Economic Essays, 7(1):45–98, 1967.
- [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.
- [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.
- [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
- [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
- [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.
- [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.
- [22]Yusuke Kobayashi, Ryoga Mahara, and Souta Sakamoto. EFX allocations for indivisible chores: Matching-based approach. In Algorithmic Game Theory, pages 257–270, 2023.
- [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
- [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.
- [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.
- [26]A. Mas-Colell, M.D. Whinston, and J.R. Green. Microeconomic Theory. Oxford University Press, 1995.
- [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.
- [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
- [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