Answer: An exact rational assignment can be computed in \(\operatorname{poly}(m,\tau,L)\) time.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a bivalued fair division instance (N, M, C) of divisible chores with all cij ∈{a, b} for some a, b ∈R+, an EF+PO allocation can be computed in strongly polynomial-time. Due to space constraints, details and proofs of this section appear only in the full version of the paper (Garg, Murhekar, and Qin 2021).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given divisible chores \(M\), one unit of each chore, a finite support \(T\) of complete cost types \(c_t\in\{1,k\}^{M}\), and rational masses \(\mu_t>0\) summing to \(1\), choose mass assignments \(z_{tj}\ge0\) with \(\sum_{t\in T}z_{tj}=1\) for every \(j\). Define type \(t\)'s cost for type \(t'\)'s average bundle by \(D_t(z_{t'})=\sum_{j\in M}c_t(j)z_{t'j}/\mu_{t'}\). Find a feasible \(z\) satisfying \(D_t(z_t)\le D_t(z_{t'})\) for all \(t,t'\), such that no feasible \(y\) has \(D_t(y_t)\le D_t(z_t)\) for every \(t\) with strict inequality for some \(t\).
Let \(M\) contain \(m\ge1\) divisible chores, one unit of each, with additive costs. A society is given by its support: the list of \(\tau\ge1\) distinct complete types \(c_t\in\{1,k\}^{M}\) with positive binary rational masses \(\mu_t\) summing to \(1\). Here \(k\ge1\) is a common binary rational input, \(\tau\) is the support size rather than the number of possible types, and \(L\) is the total input bit length.
A feasible assignment is \(z\in\mathbb{R}_{\ge0}^{T\times M}\) satisfying \(\sum_{t\in T}z_{tj}=1\) for every \(j\in M\); each member of type \(t\) receives the average bundle \(z_t/\mu_t\). Define \(D_t(z_s)=\sum_{j\in M}c_t(j)z_{sj}/\mu_s\).
Require envy-freeness, \(D_t(z_t)\le D_t(z_s)\) for all \(t,s\in T\), and Pareto optimality: no feasible \(y\) satisfies \(D_t(y_t)\le D_t(z_t)\) for every \(t\), with strict inequality for at least one type. Competing assignments need not be envy-free.
Is computing an exact rational assignment satisfying these requirements possible in time \(\operatorname{poly}(m,\tau,L)\), or is this computational problem NP-hard?
For finitely many equal-share agents and divisible chores with two common positive costs, an envy-free and Pareto-optimal allocation is computable in strongly polynomial time ([Garg–Murhekar–Qin](https://arxiv.org/html/2110.09601)).
For divisible chores with unequal shares and arbitrary strictly positive additive costs, competitive allocations are Pareto-optimal and weighted envy-free, and are computable in strongly polynomial time when either the number of agents or chores is fixed ([Brânzei–Sandomirskiy](https://arxiv.org/html/1907.01766)). These results do not establish the requested bound with both \(m\) and \(\tau\) variable.
An exact rational envy-free and Pareto-optimal assignment can be computed in time \(\operatorname{poly}(m,\tau,L)\).
The proof below gives an algorithm using polynomially many rational linear programs. It extends the price-raising idea of [Garg–Murhekar–Qin, Section 4](https://arxiv.org/html/2110.09601) by balancing earnings per unit of mass and proving an explicit criterion for choosing which prices to raise. No expansion of rational masses into individual agents is needed.
If \(k=1\), set \(z_{tj}=\mu_t\). Every type receives the same average bundle, so envy-freeness holds. Moreover, every feasible assignment \(y\) satisfies
\(\sum_t\mu_tD_t(y_t)=m\), which rules out a Pareto improvement.
Assume henceforth that \(k>1\).
If a type has cost \(k\) for every chore, divide its entire cost vector by \(k\). Leave all other cost vectors unchanged. Denote the resulting costs by \(\bar c_t(j)\).
Multiplying a type’s entire cost vector by a positive constant preserves its envy comparisons and its comparisons between competing assignments. Thus this normalization preserves both required properties. The normalized costs still belong to \(\{1,k\}\), and every type now has at least one chore of cost \(1\).
Write
\(\bar D_t(z_s)=\sum_j\bar c_t(j)z_{sj}/\mu_s\).
Define initial prices and eligible edges by
\[ \text{(using inline delimiters below)} \]
\(p_j^0=\min_t\bar c_t(j),\qquad E^0=\{(t,j):\bar c_t(j)=p_j^0\}.\)
Every chore has an eligible recipient. Every type has an eligible chore: a chore it values at \(1\) necessarily has initial price \(1\).
For an assignment \(x\), define its initial earnings by
\(e_t(x)=\sum_jp_j^0x_{tj}\).
We construct an assignment \(x^0\) supported on \(E^0\). Its crucial property will be
\[x^0_{tj}>0,\ (s,j)\in E^0 \quad\Longrightarrow\quad e_s(x^0)/\mu_s\ge e_t(x^0)/\mu_t.\tag{1}\]
Thus a chore held by a type with higher earnings per unit mass cannot be eligible for a type with lower earnings per unit mass.
Initially no type is fixed. At each stage, let \(U\) be the unfixed types. Solve the linear program
\(\displaystyle \min a\)
subject to:
Let \(a_*\) be the optimum, and let \(\mathcal F\) be the set of assignments satisfying these constraints with \(a=a_*\).
A type \(t\in U\) is forced if
\(e_t(x)=\mu_ta_*\) for every \(x\in\mathcal F\).
This can be checked by minimizing \(e_t(x)\) over \(\mathcal F\).
Freeze every forced type at earnings \(\mu_ta_*\), and repeat.
There is a forced type at every stage. Otherwise, for each \(t\in U\), choose an assignment \(x^{(t)}\in\mathcal F\) with \(e_t(x^{(t)})<\mu_ta_*\). Their average belongs to \(\mathcal F\) and satisfies this strict inequality for every unfixed type. Its maximum earnings per unit mass is therefore strictly below \(a_*\), contradicting optimality.
Successive levels strictly decrease. If some types remain unfixed, choose one such witness for each remaining type and average them. Forced types retain their fixed earnings, while every remaining type has earnings per unit mass strictly below \(a_*\). Hence the next optimum is strictly smaller.
Consequently, the procedure terminates after at most \(\tau\) stages. It produces groups \(G_1,\ldots,G_R\) and levels
\[a_1>a_2>\cdots>a_R\ge0,\qquad e_t(x^0)=\mu_ta_r\quad(t\in G_r).\tag{2}\]
The successive optimal faces are nested: previously fixed equalities remain imposed, and each new upper bound is smaller than the preceding one. Choose \(x^0\) from the final face.
Suppose \(x^0_{tj}>0\), \((s,j)\in E^0\), and
\(e_t(x^0)/\mu_t>e_s(x^0)/\mu_s\).
Let \(t\in G_r\), so \(s\) was still unfixed when \(G_r\) was frozen.
Transfer a sufficiently small positive quantity \(\varepsilon\) of chore \(j\) from \(t\) to \(s\). Both edges are eligible. This transfer decreases \(e_t\) by \(p_j^0\varepsilon\) and increases \(e_s\) by the same amount.
Because \(s\)’s final earnings per unit mass are strictly below \(a_r\), choose \(\varepsilon\) small enough that its new earnings remain at most \(\mu_sa_r\). All earlier fixed equalities remain unchanged, and every other stage-\(r\) upper bound remains satisfied. Thus the modified assignment lies in the stage-\(r\) optimal face but gives \(t\) earnings strictly below \(\mu_ta_r\). This contradicts \(t\)’s being forced.
This proves (1).
Set \(w_r=\sum_{t\in G_r}\mu_t\).
Each chore is assigned entirely within one group. Indeed, if two positive recipients of a chore had different levels, both would be eligible for it, contradicting (1).
Let \(J_r\) be the chores assigned within \(G_r\). The sets \(J_r\) partition \(M\), and therefore
\[w_ra_r=\sum_{j\in J_r}p_j^0.\tag{3}\]
Every level is positive. If some type \(s\) had zero earnings, choose a chore eligible for \(s\). That chore has a positive recipient \(t\), whose earnings are positive because prices are positive. Property (1) would give \(0=e_s/\mu_s\ge e_t/\mu_t>0\), a contradiction.
Earlier groups’ chores are expensive for every later type. Specifically, if \(j\in J_r\) and \(s\in G_\ell\) with \(\ell>r\), then (1) implies \((s,j)\notin E^0\). Since costs belong to \(\{1,k\}\), this forces
\[p_j^0=1,\qquad \bar c_s(j)=k.\tag{4}\]
In particular, every chore outside the last group has initial price \(1\).
If \(R=1\), retain \(x^0\) and prices \(p^0\). By (2), its earnings are proportional to masses. Section 5 proves the required properties.
Assume henceforth that \(R\ge2\).
For \(h\in\{1,\ldots,R-1\}\), consider multiplying the prices of chores in \(J_1\cup\cdots\cup J_h\) by \(k\).
Under the original assignment \(x^0\), earnings per unit mass become \(ka_r\) for \(r\le h\) and remain \(a_r\) for \(r>h\). Define their weighted average
\[q_h=k\sum_{r\le h}w_ra_r+\sum_{r>h}w_ra_r.\tag{5}\]
Because the masses sum to \(1\), this is also the total price of all chores after the increase.
We need a prefix satisfying
\[ka_h\ge q_h\ge a_{h+1}.\tag{6}\]
Such a prefix always exists. Choose the smallest \(h\) for which \(q_h\ge a_{h+1}\). This choice exists because every adjusted level for \(h=R-1\) is at least \(a_R\), so their weighted average is at least \(a_R\).
If \(h=1\), every adjusted level is at most \(ka_1\), hence \(q_1\le ka_1\).
If \(h>1\), minimality gives \(q_{h-1}<a_h\), and therefore
\(q_h=q_{h-1}+(k-1)w_ha_h <a_h+(k-1)w_ha_h \le ka_h,\)
where the last inequality uses \(w_h\le1\). This proves (6).
Fix this prefix, write \(q=q_h\), and define
\(p_j= \begin{cases} kp_j^0,&j\in J_1\cup\cdots\cup J_h,\\ p_j^0,&\text{otherwise}. \end{cases}\)
Call types in \(G_1\cup\cdots\cup G_h\) raised types. Set
\(\alpha_t= \begin{cases} 1/k,&t\text{ is raised},\\ 1,&t\text{ is unraised}. \end{cases}\)
We now verify that
\[\bar c_t(j)\ge\alpha_tp_j\qquad\text{for every }t,j.\tag{7}\]
For a raised type, a raised chore has price \(k\), by (4), and cost at least \(1=\alpha_tp_j\). An unraised chore satisfies \(\bar c_t(j)\ge p_j^0\ge p_j^0/k=\alpha_tp_j\).
For an unraised type, every raised chore has cost \(k\), by (4), equal to its new price. Every unraised chore satisfies \(\bar c_t(j)\ge p_j^0=p_j\).
Moreover:
Under \(x^0\) at prices \(p\), a raised type in \(G_r\) earns \(\mu_tka_r\ge\mu_tq\), while an unraised type earns \(\mu_ta_r\le\mu_tq\), by (6).
Total earnings are \(q=\sum_jp_j\). Thus the raised types’ total surplus equals the unraised types’ total deficit relative to the targets \(\mu_tq\).
Transfer portions of raised types’ chores to unraised types until these surpluses and deficits are exhausted. Each donor has enough earnings to supply its surplus. Every such donor–recipient transfer preserves equality in (7), as established above.
Hence there exists a feasible assignment \(z\) satisfying
\[\sum_jp_jz_{tj}=\mu_tq,\qquad z_{tj}>0\Longrightarrow\bar c_t(j)=\alpha_tp_j.\tag{8}\]
To compute an exact rational assignment, solve the feasibility linear program consisting of feasibility, the earnings equalities in (8), and the restrictions
\(z_{tj}=0\) whenever \(\bar c_t(j)\ne\alpha_tp_j\).
The transfer argument proves this program feasible.
When \(R=1\), (7)–(8) instead hold directly with \(p=p^0\), \(\alpha_t=1\), \(q=\sum_jp_j^0\), and \(z=x^0\).
For any types \(t,s\), (7)–(8) give
\(\displaystyle \bar D_t(z_t) =\frac{\alpha_t}{\mu_t}\sum_jp_jz_{tj} =\alpha_tq,\)
and
\(\displaystyle \bar D_t(z_s) \ge\frac{\alpha_t}{\mu_s}\sum_jp_jz_{sj} =\alpha_tq.\)
Thus \(z\) is envy-free.
For Pareto optimality, let \(y\) be any feasible competing assignment, without an envy-freeness restriction. By (7),
\[\displaystyle \sum_t\frac{\mu_t}{\alpha_t}\bar D_t(y_t) =\sum_{t,j}\frac{\bar c_t(j)}{\alpha_t}y_{tj} \ge\sum_{t,j}p_jy_{tj} =\sum_jp_j=q.\tag{9}\]
For \(z\), equality holds by (8). Every weight \(\mu_t/\alpha_t\) is strictly positive. Consequently, a weak decrease in every type’s disutility with a strict decrease for one type would make the weighted sum strictly smaller than \(q\), contradicting (9).
Therefore \(z\) is Pareto-optimal against all feasible assignments. The normalization preserves both properties, so they hold for the original costs.
The balancing procedure uses at most \(\tau\) minimax linear programs and at most \(\tau^2\) additional linear programs to identify forced types. Each has polynomially many variables and constraints.
We must also bound the bit lengths of the fixed levels inserted into later programs. Equation (3) gives
\[\displaystyle a_r=\frac{\sum_{j\in J_r}p_j^0}{\sum_{t\in G_r}\mu_t}.\tag{10}\]
The numerator is \(u+vk\) for integers \(u,v\) between \(0\) and \(m\). The denominator is a sum of a subset of the input masses. Both have bit length polynomial in \(L+\log m+\log\tau\): a common denominator for such a sum can be formed by multiplying input denominators, whose total binary length is bounded by the input length.
Thus every level \(a_r\), every fixed earnings value \(\mu_ta_r\), and every coefficient in the balancing programs has polynomial bit length. This bound concerns all levels produced by the procedure, independently of which rational optimum is selected.
The prices \(p_j\), multipliers \(\alpha_t\), and value \(q=\sum_jp_j\) likewise have polynomial bit length. The final feasibility program therefore has polynomial encoding length.
Standard polynomial-time algorithms for rational linear programming compute exact rational optima or feasible solutions of polynomial bit length. Applying them to the polynomially many programs above proves the claimed bound \(\operatorname{poly}(m,\tau,L)\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The algorithm establishes the requested polynomial-time bound for variable \(m\) and \(\tau\), with binary rational masses and \(k\). I found no major or minor mathematical issues. The cited allocation results are contextual; the argument does not depend on extending their theorems without proof.
For \(k=1\), the assignment \(z_{tj}=\mu_t\) is feasible and gives every type the same average bundle. The identity
\[
\sum_t\mu_tD_t(y_t)=m
\]
holds for every feasible \(y\). Since all masses are positive, a Pareto improvement would strictly decrease this sum, which is impossible.
Dividing an all-\(k\) type’s cost vector by \(k>0\) scales all its relevant comparisons by the same positive factor. This preserves both envy-freeness and the Pareto-improvement relation, including comparisons against unrestricted competing assignments. The normalized costs remain in \(\{1,k\}\), and every type has a cost-\(1\) chore.
Normalization can make originally distinct types have identical normalized costs. This causes no problem: the algorithm retains their separate indices and masses and does not require normalized types to remain distinct.
Every chore has an eligible recipient because its initial price is a minimum over a nonempty finite set. Every type has an eligible chore because any chore it values at \(1\) has initial price \(1\).
The first minimax program is feasible: chores can be allocated to eligible recipients, and \(a\) can be chosen sufficiently large. At later stages, the preceding optimal face supplies a feasible assignment.
For every nonempty unfixed set, the objective is bounded below by \(0\), since earnings are nonnegative and masses are positive. The assignment variables lie in a compact product of simplices. Thus the finite optimum and the witness minima used to identify forced types are attained.
The averaging argument establishing the existence of a forced type is valid. If every unfixed type had a witness with its own inequality strict, averaging those witnesses would make every unfixed inequality strict simultaneously, while preserving feasibility and all fixed equalities. The resulting assignment would permit a strictly smaller objective value.
The same reasoning applies to the types remaining after a stage and proves that the next level is strictly smaller. At least one type is frozen per stage, so there are at most \(\tau\) stages.
The nesting assertion is correct: subsequent upper bounds on remaining types are smaller, and frozen types retain their earlier equalities. Consequently, an assignment from the final face belongs to every earlier optimal face.
The transfer contradiction is sound. If a positive recipient \(t\) has a larger final earnings-to-mass ratio than an eligible type \(s\), strict decrease of the group levels implies that \(s\) was still unfixed when \(t\)’s group was frozen.
The final assignment lies in that stage’s optimal face. A sufficiently small transfer preserves nonnegativity, chore feasibility, earlier fixed equalities, and the upper bound for \(s\), which has strict slack at that stage. It decreases \(t\)’s earnings below its supposedly forced value. This is precisely the required contradiction.
A chore cannot have positive recipients in two different groups: applying (1) with the higher-level recipient as \(t\) and the lower-level recipient as \(s\) contradicts their level ordering. Thus the sets \(J_r\) partition the chores.
Equation (3) correctly sums each group’s earnings. The positivity argument is also valid: a zero-earnings type has an eligible chore, that chore has a positive recipient with positive earnings, and (1) would force the zero ratio to be at least a positive ratio.
For a chore assigned to an earlier group, a later type cannot be eligible. With costs restricted to \(\{1,k\}\), ineligibility forces initial price \(1\) and that later type’s cost \(k\). This establishes (4), including its use for every raised chore.
The weights \(w_r\) are positive and sum to \(1\), so \(q_h\) is indeed the weighted average of the adjusted levels and the total adjusted price.
For \(h=R-1\), every adjusted level is at least \(a_R\), ensuring that the specified smallest prefix exists. For \(h=1\), every adjusted level is at most \(ka_1\). For \(h>1\), the calculation
\[
q_h=q_{h-1}+(k-1)w_ha_h
<a_h+(k-1)w_ha_h
\le ka_h
\]
is correct, using minimality and \(w_h\le1\). Both inequalities in (6) follow.
The verification of (7) covers all combinations of raised and unraised types and chores. In particular, all raised chores have initial price \(1\), and every unraised type values every raised chore at \(k\).
Every original positive edge satisfies equality in (7). For raised types, their positive edges lie among raised chores and have normalized cost \(1\). For unraised types, their original eligible edges retain their prices. Every transfer edge from a raised chore to an unraised type also satisfies equality.
By (6) and the ordering of levels, all raised types have earnings at least their targets, while all unraised types have earnings at most their targets. Total surplus equals total deficit. Each donor’s surplus is no greater than its current earnings, all its assigned chores are raised, and every unraised recipient can receive any raised chore on an equality edge. The stated transfer argument therefore establishes feasibility of (8).
The separate \(R=1\) treatment is correct and avoids any need to choose a prefix.
Equality on positive own-allocation edges gives own normalized disutility \(\alpha_tq\). Inequality (7), combined with each other type’s proportional earnings, gives cross-disutility at least \(\alpha_tq\). The denominators are correctly those of the bundle’s recipient, so this proves exactly the envy-freeness requested.
Equation (9) is correct for every feasible competing assignment. Equality holds for \(z\), and all weights \(\mu_t/\alpha_t\) are strictly positive. A Pareto improvement would therefore contradict the lower bound \(q\). No envy-freeness assumption on the competing assignment is used.
The procedure uses at most \(\tau\) minimax programs and at most \(\tau^2\) forced-type checks. Their dimensions are polynomial in \(m\) and \(\tau\).
Equation (10) provides a valid bound on all levels generated during the procedure. Its numerator is \(u+vk\), with \(u,v\le m\); its denominator is a positive subset sum of input masses. Products of input denominators have binary length bounded by the sum of their input lengths, so these quantities, their quotients, and the fixed earnings have polynomial bit length.
This argument is not circular: the structural identities establish an a priori size bound on the optimal values, independently of the bit complexity of finding them.
The final prices, multipliers, total price, and feasibility program likewise have polynomial encoding length. The standard exact rational linear-programming result applies: the optimization programs are feasible with attained finite optima, and the final feasibility program is feasible. It yields rational solutions of polynomial bit length in polynomial time.
Actionable feedback: No repair is required. The proof resolves the assigned continuous problem without expanding rational masses into equal-share agents.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.