Answer: Deciding \(S^*(q,c)\le K\) is \(\mathrm{NP}\)-complete, already for \(\tau=1\) and \(K=0\). Polynomial-time exact optimal-assignment computation would imply \(\mathrm P=\mathrm{NP}\). The sharp worst-case value is \(1/4\), and it is attained.
Theorem 3.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven any instance with n agents having identical cost functions, there exists a PROPS allocation with total subsidy at most n/4 when n is even, and at most (n2 −1)/(4n) when n is odd.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational per-capita chore supplies \(q_e\ge0\) and costs \(c_e\in[0,1]\), let \(b=\sum_e q_ec_e\). Choose a finite-support distribution \(y_z\ge0\) over integral bundles \(z\in\mathbb Z_{\ge0}^m\), with \(\sum_z y_z=1\) and \(\sum_z y_zz_e=q_e\) for every chore type \(e\), minimizing \(\sum_z y_z[c\cdot z-b]_+\). Determine the worst-case optimum and whether an optimal mass assignment can be computed in time polynomial in \(m\) and the binary input length \(L\).
A society is given by its support: the list of the \(\tau\) agent types with positive mass, each mass a binary rational; \(\tau\) means support size, not the number of possible types. Here the society has total mass \(1\) and one identical additive-cost type, so \(\tau=1\).
There are \(m\ge1\) chore types, with binary-rational per-capita supplies \(q_e\ge0\) and unit costs \(c_e\in[0,1]\); supplies need not sum to \(1\). Write \(b=\sum_{e=1}^m q_ec_e\).
An assignment is a finite-support distribution of masses \(y_z\ge0\) over integral bundles \(z\in\mathbb Z_{\ge0}^m\), satisfying \(\sum_z y_z=1\) and \(\sum_z y_zz_e=q_e\) for every \(e\). Empty bundles and multiple copies of a chore type are allowed.
The subsidy for bundle \(z\) is \([c\cdot z-b]_+\), where \([a]_+=\max\{a,0\}\). Define \(S^*(q,c)=\min_y\sum_z y_z[c\cdot z-b]_+\). An optimal assignment is represented by listing its supported bundles and binary-rational masses; \(L\) is the total binary input length, including any threshold.
Is deciding \(S^*(q,c)\le K\), for binary-rational \(K\ge0\), in \(\mathrm P\) or \(\mathrm{NP}\)-hard, and can an exact optimal assignment be computed in time polynomial in \(m,\tau,L\)?
What is the sharp worst-case value \(\sup_{m\ge1,\;q\in\mathbb Q_{\ge0}^m,\;c\in(\mathbb Q\cap[0,1])^m}S^*(q,c)\)?
For \(n\ge2\) identical discrete agents, a polynomial-time algorithm achieves total proportionality subsidy at most \(n/4\) for even \(n\), and \((n^2-1)/(4n)\) for odd \(n\); both worst-case bounds are tight. [Source](https://arxiv.org/pdf/2307.04411)
No result settling exactly this finite-support mass-assignment problem was located in the literature search.
1. Result
The decision problem is \(\mathrm{NP}\)-complete, already with \(\tau=1\), threshold \(K=0\), and every supply equal to \(1/2\). Consequently, computing an exact optimal assignment in time polynomial in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
Nevertheless, every instance has an exact optimal assignment with at most \(m+1\) supported bundles and polynomial total binary encoding length.
The sharp worst-case value is
\(\displaystyle \sup_{m,q,c} S^*(q,c)=\frac14.\)
This value is attained.
2. A useful identity
Write an assignment as a finitely supported random integral bundle \(Z\), with \(\mathbb E Z=q\), and let \(X=c\cdot Z\). Then \(\mathbb E X=b\). Therefore
\(\displaystyle \mathbb E[X-b]_+=\frac12\mathbb E|X-b|.\)
Indeed, the positive and negative parts of \(X-b\) have equal expectations because \(\mathbb E(X-b)=0\).
It follows that an assignment has zero subsidy exactly when every bundle receiving positive mass has cost \(b\). We will use this characterization in the reduction.
3. Attainment and polynomial-size optimal assignments
We first justify that the minimum is attained and that optimal assignments provide polynomial-size certificates.
Define the capped-cost function
\(\displaystyle h(z)=\min\{c\cdot z,b\}.\)
For any feasible assignment,
\(\displaystyle \mathbb E[c\cdot Z-b]_+=b-\mathbb E h(Z).\)
Consider the relaxed maximization problem over finite-support distributions satisfying
\(\displaystyle \mathbb E Z_e\le q_e\quad\text{for every }e,\)
with objective \(\mathbb E h(Z)\).
Reduction to finitely many bundles. For each positive-cost coordinate, set
\(\displaystyle B_e=\left\lfloor\frac{b+1}{c_e}\right\rfloor,\)
and set \(B_e=0\) when \(c_e=0\). Let
\(\displaystyle \mathcal T=\{z\in\mathbb Z_{\ge0}^m: z_e\le B_e\text{ for every }e\}.\)
Every integral bundle can be replaced by a coordinatewise smaller bundle in \(\mathcal T\), preserving its capped cost:
Thus every relaxed feasible distribution can be replaced by one supported on \(\mathcal T\), without increasing any coordinate mean or changing its objective.
Consequently, the relaxed optimum is the optimum \(H\) of the finite rational linear program
\(\displaystyle \max \sum_{z\in\mathcal T}p_z h(z), \quad \sum_{z\in\mathcal T}p_z=1, \quad \sum_{z\in\mathcal T}p_z z_e\le q_e, \quad p_z\ge0. \)
The feasible region is nonempty, since it contains the distribution concentrated on the empty bundle, and compact, since it lies in a finite-dimensional probability simplex. Hence an optimum exists. A basic optimal solution has at most \(m+1\) positive bundle masses.
Although \(\mathcal T\) may be very large, each coordinate \(B_e\) has polynomial binary length in the input. The masses of a basic solution also have polynomial binary length: they solve a rational linear system of order at most \(m+1\), with integer bundle coefficients of polynomial binary length and rational right-hand sides from the input. Clearing denominators and applying Cramer’s rule gives the required determinant bounds.
Restoring the missing supplies. Let \(Z\) have such a basic optimal relaxed distribution, and define
\(\displaystyle d=q-\mathbb E Z\ge0.\)
There is a rational distribution on at most \(m+1\) integral vectors \(W\) with \(\mathbb E W=d\). Explicitly, write
\(\displaystyle d_e=\lfloor d_e\rfloor+r_e,\qquad 0\le r_e<1,\)
and take a common uniform random variable \(U\) on \([0,1]\), setting
\(\displaystyle W_e=\lfloor d_e\rfloor+\mathbf 1_{\{U<r_e\}}.\)
The vector changes only at the at most \(m\) distinct breakpoints \(r_e\). Its induced finite distribution therefore has at most \(m+1\) outcomes, with rational masses.
Take \(Z\) and \(W\) independently. Then \(Z+W\) is a finite-support assignment with mean \(q\). Since \(h\) is coordinatewise nondecreasing,
\(\displaystyle \mathbb E h(Z+W)\ge \mathbb E h(Z)=H.\)
Conversely, \(Z+W\) is feasible for the relaxed problem, whose optimum is \(H\). Thus equality holds, and
\(\displaystyle S^*(q,c)=b-H.\)
This proves attainment by a rational finite-support assignment. The construction uses at most \((m+1)^2\) bundles, all with polynomial encoding length. Optimizing the original subsidy objective over this already finite collection of bundles yields a basic optimal solution with at most \(m+1\) supported bundles, again with polynomial-length rational masses.
A proposed such assignment can be checked in polynomial time: verify nonnegative masses, total mass, all supply equalities, and the subsidy threshold using exact rational arithmetic. Therefore the decision problem belongs to \(\mathrm{NP}\).
4. Hardness despite allowing repeated copies
We reduce from PARTITION: given positive integers \(a_1,\ldots,a_n\), decide whether some subset sums to half their total. This problem is \(\mathrm{NP}\)-complete; see [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). We may assume the total \(A=\sum_i a_i\) is even, because doubling every input integer preserves the answer and ensures this restriction.
The encoding below forces a cost-\(b\) integral bundle to contain exactly one chore from each pair. This is necessary because repeated copies are allowed.
Set
\(\displaystyle a_{\max}=\max_i a_i,\qquad B=n+1,\qquad M=na_{\max}+1, \)
\(\displaystyle D=MB^{n-1}+a_{\max},\qquad H=nD+1,\qquad P=\sum_{i=1}^n B^{i-1}. \)
For each \(i\), introduce two integer weights
\(\displaystyle w_{i,0}=H+MB^{i-1}, \qquad w_{i,1}=H+MB^{i-1}+a_i. \)
Define
\(\displaystyle T=nH+MP+\frac A2.\)
Choose a power of two \(C\ge H+D\). The society has \(2n\) chore types, with
\(\displaystyle q_{i,t}=\frac12,\qquad c_{i,t}=\frac{w_{i,t}}C,\qquad K=0.\)
All costs lie in \((0,1]\); indeed, the reduction uses dyadic costs and supplies. Moreover,
\(\displaystyle b=\frac1{2C}\sum_{i,t}w_{i,t}=\frac TC. \)
Every constructed number has polynomial binary length: the largest radix power has binary length bounded by a constant multiple of \(n\log(n+1)\). Thus this is a polynomial-time reduction.
Characterizing cost-\(b\) bundles. Suppose an integral bundle \(z\) satisfies
\(\displaystyle \sum_{i,t}w_{i,t}z_{i,t}=T.\)
Let \(k=\sum_{i,t}z_{i,t}\) be its total number of chores.
The target remainder \(R=MP+A/2\) satisfies
\(\displaystyle 0\le R\le nMB^{n-1}+\frac{na_{\max}}2\le nD<H. \)
Since each weight is at least \(H\), and \(T=nH+R<(n+1)H\), we have \(k\le n\). Each weight’s remainder after subtracting \(H\) is at most \(D\). Hence the bundle’s total remainder is at most \(kD\le nD<H\).
Uniqueness of quotient and remainder upon division by \(H\) now gives
\(\displaystyle k=n\)
and
\(\displaystyle M\sum_{i=1}^n B^{i-1}(z_{i,0}+z_{i,1}) +\sum_{i=1}^n a_i z_{i,1} =MP+\frac A2. \)
Because
\(\displaystyle 0\le\sum_i a_i z_{i,1}\le na_{\max}<M \quad\text{and}\quad 0\le A/2<M, \)
reduction modulo \(M\) gives
\(\displaystyle \sum_i a_i z_{i,1}=\frac A2.\)
Subtracting this equality leaves
\(\displaystyle \sum_{i=1}^n B^{i-1}(z_{i,0}+z_{i,1}) =\sum_{i=1}^n B^{i-1}. \)
Every coefficient \(z_{i,0}+z_{i,1}\) is at most \(n<B\). Uniqueness of base-\(B\) representation therefore forces
\(\displaystyle z_{i,0}+z_{i,1}=1\quad\text{for every }i.\)
Thus any cost-\(b\) bundle selects exactly one chore from each pair, and its selected indices with \(z_{i,1}=1\) solve PARTITION.
Equivalence of the instances. If PARTITION has a solution, take the corresponding selecting bundle and its complementary selecting bundle. Both have cost \(b\). Giving each mass \(1/2\) supplies every chore type in quantity \(1/2\) and yields zero subsidy.
Conversely, a zero-subsidy assignment must consist entirely of cost-\(b\) bundles, by Section 2. Any one of these bundles yields a partition by the characterization above.
There is also an explicit separation in a no instance. Every bundle cost is an integer multiple of \(1/C\), and none equals \(b=T/C\). Therefore every bundle satisfies
\(\displaystyle |c\cdot z-b|\ge\frac1C.\)
For every feasible assignment, Section 2 then implies
\(\displaystyle \mathbb E[c\cdot Z-b]_+\ge\frac1{2C}>0.\)
Hence deciding \(S^*(q,c)\le0\) is \(\mathrm{NP}\)-hard. Together with Section 3, this proves \(\mathrm{NP}\)-completeness.
5. The universal upper bound
Choose a positive integer \(N\) such that all \(Nq_e\) are integers. Make \(Nq_e\) individual chores of each type \(e\), and allocate this finite collection among \(N\) identical agents.
Starting from empty bundles, assign each chore to an agent of currently minimum load. All loads remain within an interval of length at most \(1\). To verify the invariant, suppose the current minimum is \(s\), and all loads lie in \([s,s+1]\). Assigning a chore of cost at most \(1\) to a minimum-load agent leaves every load in that same interval. The initial loads satisfy the invariant.
Give each resulting bundle mass \(1/N\), merging identical bundles if necessary. This is a feasible finite-support assignment with average load \(b\).
Let its minimum and maximum loads be \(\ell\) and \(u\). If \(u=\ell\), the subsidy is zero. Otherwise, \(\ell\le b\le u\) and \(u-\ell\le1\). Convexity of \(x\mapsto[x-b]_+\) gives, for \(x\in[\ell,u]\),
\(\displaystyle [x-b]_+\le\frac{x-\ell}{u-\ell}(u-b). \)
Taking expectations yields
\(\displaystyle \mathbb E[X-b]_+ \le\frac{(b-\ell)(u-b)}{u-\ell} \le\frac{u-\ell}{4} \le\frac14. \)
The middle inequality follows from
\(\displaystyle (b-\ell)(u-b)\le\frac{((b-\ell)+(u-b))^2}{4}.\)
Thus \(S^*(q,c)\le1/4\) for every instance. This construction proves existence; its expansion into individual chores can be exponentially large in the binary input length.
6. Sharpness and the computational conclusion
Take one chore type with \(q_1=1/2\) and \(c_1=1\). Then \(b=1/2\). Every integral bundle has cost a nonnegative integer, so
\(\displaystyle |c\cdot z-b|\ge\frac12.\)
Section 2 implies that every feasible assignment has subsidy at least \(1/4\). The assignment giving mass \(1/2\) to the empty bundle and mass \(1/2\) to the one-chore bundle attains this value.
Finally, an exact optimal-assignment algorithm running in time polynomial in \(m,\tau,L\) would decide the reduced PARTITION instances by checking whether its output subsidy is zero. Since these instances have \(\tau=1\), such an algorithm would imply \(\mathrm P=\mathrm{NP}\). Polynomial-size exact outputs exist, but finding them is \(\mathrm{NP}\)-hard.
⟨structured verdict parsed — rendered above⟩
The output resolves both questions correctly. The decision problem is \(\mathrm{NP}\)-complete under the stated binary encoding, exact optimal-assignment computation is \(\mathrm{NP}\)-hard, and the sharp worst-case subsidy is \(1/4\), attained by the given example. I found no major or minor mathematical issues.
Feasibility gives \(\mathbb E X=b\). Because the distribution has finite support, all expectations are finite, and the positive and negative parts of \(X-b\) have equal expectations. Thus
\(\mathbb E[X-b]_+=\tfrac12\mathbb E|X-b|\)
is correct.
The zero-subsidy characterization also follows: a finite sum of nonnegative terms vanishes exactly when every positive-mass bundle has cost \(b\). There is no unsupported inference from an infimum here; attainment is subsequently proved.
The identity \(\mathbb E[c\cdot Z-b]_+=b-\mathbb E h(Z)\) is used for assignments satisfying the supply equalities, where it is valid. The relaxed problem separately maximizes the capped-cost objective.
The truncation argument is correct in every case:
Each replacement decreases coordinates and preserves capped cost. Therefore the finite LP represents the relaxed optimum exactly.
The LP is nonempty and compact, as stated. The standard basic-solution property applies: with normalization and at most \(m\) supply constraints, an optimal basic solution has at most \(m+1\) positive bundle variables. The binary-length argument is sufficient. The bundle coordinates have polynomial binary length, and the relevant basis systems have order at most \(m+1\); clearing denominators and bounding determinants gives polynomial-length rational masses. The potentially enormous number of LP columns does not invalidate this certificate-size argument.
The missing-supply construction is valid. Its common-uniform-variable representation induces at most \(m+1\) integral outcomes with rational probabilities and expectation \(d\). Independence then gives \(\mathbb E(Z+W)=q\).
Both objective comparisons are justified. Coordinatewise monotonicity gives \(\mathbb E h(Z+W)\ge H\), while feasibility for the relaxed problem gives \(\mathbb E h(Z+W)\le H\). Consequently, equality holds and the resulting assignment is globally optimal.
The product distribution has at most \((m+1)^2\) bundles with polynomial total encoding length. Optimizing over that finite collection preserves global optimality and permits the claimed reduction to at most \(m+1\) supported bundles.
Exact rational verification of such a certificate takes polynomial time, establishing membership in \(\mathrm{NP}\) for arbitrary permitted thresholds.
The source problem is correctly stated as binary-encoded PARTITION, whose \(\mathrm{NP}\)-completeness is supported by the cited [Karp paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). Doubling all inputs preserves the answer and ensures an even total.
The constructed costs and supplies satisfy the target restrictions. Every weight is positive and at most \(H+D\), so division by the chosen power of two gives a cost in \((0,1]\). All supplies equal \(1/2\), the agent-type support size remains \(\tau=1\), and the threshold is zero. The construction admits polynomial-length numbers and polynomial-time arithmetic.
The calculation \(b=T/C\) is correct: summing both weights in each pair and dividing by two produces exactly the stated target \(T\).
The characterization of cost-\(b\) bundles checks out step by step:
These bounds specifically address the permission to use repeated copies; no binary-bundle assumption is hidden in the argument.
The reduction works in both directions. A partition and its complement yield two cost-\(b\) bundles whose equal masses meet every supply. Conversely, every positive-mass bundle in a zero-subsidy assignment yields a partition.
The additional separation bound is also correct. In a no instance, all bundle costs lie on the \(1/C\) lattice and none equals \(T/C\), giving absolute deviation at least \(1/C\) and subsidy at least \(1/(2C)\). Thus even arbitrarily small positive subsidies cannot undermine the zero-threshold reduction.
Rational supplies permit the stated finite integer expansion. The greedy load invariant is valid: assigning a chore of cost at most \(1\) to a current minimum-load agent keeps all loads within the previous interval of length \(1\). Consequently, the final load range has length at most \(1\).
Assigning mass \(1/N\) to each resulting bundle satisfies normalization and every supply equality, with average load \(b\). This remains valid when \(N=1\), some supplies vanish, or all costs vanish.
When the range is nondegenerate, the displayed convexity bound is exactly the chord bound between the minimum and maximum loads. Taking expectations gives the stated expression. The product inequality then bounds it by one quarter of the range length, hence by \(1/4\). The equal-load case is handled separately.
The output correctly treats this expansion as an existence argument, without claiming polynomial running time.
For \(q_1=1/2\) and \(c_1=1\), every integral bundle cost differs from \(b=1/2\) by at least \(1/2\). The established identity therefore gives subsidy at least \(1/4\). The two-bundle assignment attains that value and meets the supply exactly.
An exact polynomial-time optimal-assignment algorithm would allow exact subsidy evaluation on the reduced instances and thus decide PARTITION in polynomial time. The conclusion is correctly conditional on \(\mathrm P\ne\mathrm{NP}\); the output does not claim an unconditional separation.
No additional clarification or repair is needed.
⟨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.