Answer: —
Theorem 19 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor every instance with $n$ agents with additive valuations over at most $n$ items, there is a randomized allocation with the following properties.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent types \(T\) with masses \(\mu_t>0\), item types \(J\) with per-capita supplies \(\sigma_j\ge0\) satisfying \(\sum_j\sigma_j=1\), and additive values \(v_t(j)\ge0\), compute an exchangeable-within-type finite-support lottery over measurable matchings assigning one indivisible item to every infinitesimal agent. Every realization must be Pareto optimal and give every type-\(t\) agent value at least \(\operatorname{TPS}_t=\max\{z\ge0:\sum_j\sigma_j\min(v_t(j),z)=z\}\); if \(U_t\) is the common expected utility of type \(t\), require \(U_t\ge\operatorname{PS}_t=\sum_j\sigma_jv_t(j)\) and \(\exp(\sum_t\mu_t\log U_t)\ge\operatorname{OPT}_\infty/e^{(e+1)/e}\), where \(\operatorname{OPT}_\infty\) is the maximum of \(\exp(\sum_t\mu_t\log(\mu_t^{-1}\sum_jv_t(j)a_{tj}))\) over \(a_{tj}\ge0\) with \(\sum_ja_{tj}=\mu_t\) and \(\sum_ta_{tj}\le\sigma_j\).
Let finite type sets \(T,J\) have rational masses \(\mu_t>0\), supplies \(\sigma_j\ge0\), and values \(v_t(j)\ge0\), with \(\sum_t\mu_t=\sum_j\sigma_j=1\). Each agent receives one indivisible item. A measurable matching respects the supplies; it is Pareto optimal if no measurable reassignment weakly improves every agent and strictly improves a positive mass of agents.
A finite-support lottery is exchangeable within type when every type-\(t\) agent has the same marginal distribution over items. Its output lists the support probabilities and finitely described measurable matchings. Write \(U_t\) for that agent’s expected value, \(\operatorname{PS}_t=\sum_j\sigma_jv_t(j)\), and \(\operatorname{TPS}_t=\max\{z\ge0:\sum_j\sigma_j\min(v_t(j),z)=z\}\).
Let \(\operatorname{OPT}_\infty=\max_a\exp\!\left(\sum_t\mu_t\log\!\left(\mu_t^{-1}\sum_jv_t(j)a_{tj}\right)\right)\), where \(a_{tj}\ge0\), \(\sum_ja_{tj}=\mu_t\), and \(\sum_ta_{tj}\le\sigma_j\); interpret a zero utility factor as making the objective zero.
Target. Is computing such a lottery in polynomial time, or is it NP-hard, when every realization is Pareto optimal and gives each type-\(t\) agent at least \(\operatorname{TPS}_t\), while \(U_t\ge\operatorname{PS}_t\) and \(\exp(\sum_t\mu_t\log U_t)\ge\operatorname{OPT}_\infty/e^{(e+1)/e}\)?
Nearest known result. For finitely many agents and at most as many items, a fractional allocation underlying a lottery with these corresponding guarantees can be computed in polynomial time; Pareto-optimal realizations are established existentially.
Proved result: the required explicit output can be exponentially large. Consequently, under binary encoding of rational data, no algorithm can always compute the requested lottery in polynomial total time. This obstruction already occurs with one type and two items, when every matching is Pareto optimal and the welfare guarantee holds with equality to the optimum. It does not establish NP-hardness.
1. A support-size lower bound.
Represent a single type of mass \(1\) by the interval \([0,1)\), equipped with Lebesgue measure \(\lambda\). Consider an item \(r\) with supply \(p>0\).
Let an exchangeable lottery have realizations \(M_1,\ldots,M_K\), with positive probabilities \(w_1,\ldots,w_K\). Define the measurable set
\(R_i=\{x:M_i(x)=r\}\).
Every realization exhausts every supply: each agent receives one item, and total supply equals total agent mass. Hence \(\lambda(R_i)=p\).
By exchangeability, there is a common marginal probability \(\rho\) such that, for every agent \(x\),
\(\sum_{i=1}^K w_i\mathbf{1}_{R_i}(x)=\rho\).
Integrating this finite sum gives
\(\rho=\sum_{i=1}^K w_i\lambda(R_i)=p\sum_{i=1}^K w_i=p\).
Since \(p>0\), every agent belongs to at least one \(R_i\). Subadditivity of measure therefore yields
\(1=\lambda(\bigcup_{i=1}^K R_i)\leq\sum_{i=1}^K\lambda(R_i)=Kp\).
Thus
\(K\geq\lceil 1/p\rceil\).
The same proof works if exchangeability is required only almost everywhere. The probabilities need not be equal, and no restriction on the descriptions of the measurable sets was used.
2. An instance family satisfying all the other requirements.
Fix an integer \(q\geq2\). Take one type \(t\), two items \(r,c\), and data
\(\mu_t=1\),
\(\sigma_r=1/q\),
\(\sigma_c=1-1/q\),
\(v_t(r)=1\), and
\(v_t(c)=0\).
We verify each requirement.
*Truncated proportional share.* For \(z>0\),
\(\sum_j\sigma_j\min(v_t(j),z)=q^{-1}\min(1,z)<z\).
Indeed, for \(0<z\leq1\) this expression equals \(z/q<z\), and for \(z>1\) it equals \(1/q<z\). At \(z=0\), equality holds. Consequently,
\(\operatorname{TPS}_t=0\).
Every matching satisfies the required individual floor because all values are nonnegative.
*Proportional share and expected utility.* We have
\(\operatorname{PS}_t=1/q\).
The preceding marginal calculation shows that every agent in any exchangeable lottery receives \(r\) with probability \(1/q\). Therefore
\(U_t=1/q=\operatorname{PS}_t\).
*Fractional optimum.* With one type, feasibility forces \(a_{tr}=\sigma_r\) and \(a_{tc}=\sigma_c\): the row sum is \(1\), the column upper bounds sum to \(1\), and therefore both column bounds must be tight. It follows that
\(\operatorname{OPT}_\infty=1/q\).
Thus every exchangeable lottery has
\(\exp(\sum_t\mu_t\log U_t)=1/q=\operatorname{OPT}_\infty\),
which is stronger than the requested approximation guarantee.
*Pareto optimality of every realization.* Consider any matching, and let \(R\) be its set of agents receiving \(r\). Then \(\lambda(R)=1/q\).
In any weak Pareto improvement, every agent in \(R\) must retain \(r\), since receiving \(c\) would reduce that agent’s value from \(1\) to \(0\). A positive mass of strict improvements would therefore require giving \(r\) to a positive mass of agents outside \(R\), in addition to everyone in \(R\). This exceeds the supply \(1/q\). Hence no such improvement exists, and every matching is Pareto optimal.
3. The lower bound is attainable.
Partition the agent interval into the \(q\) half-open intervals
\(I_i=[(i-1)/q,i/q)\), for \(i=1,\ldots,q\).
In realization \(i\), give \(r\) to agents in \(I_i\) and \(c\) to everyone else. Give each realization probability \(1/q\).
Every realization respects supplies and has a finite rational interval description. Every agent receives \(r\) in exactly one realization, so the lottery is exchangeable. All the guarantees follow from Section 2.
Thus the minimum possible support size for this instance is exactly \(q\).
4. Computational consequence and remaining question.
Set \(q=2^n\). The entire instance has binary encoding length \(O(n)\): in particular, the supplies \(1/2^n\) and \((2^n-1)/2^n\) each have descriptions of length \(O(n)\).
Nevertheless, every valid lottery has at least \(2^n\) support elements. Because the requested output explicitly lists the support probabilities and corresponding matchings, merely writing it requires at least \(\Omega(2^n)\) output entries. Polynomial total running time is therefore impossible.
An indexed formula describing all these realizations, or a succinct sampling procedure, could avoid listing them individually, but that would change the specified output representation.
The remaining classification issue is NP-hardness. An unconditional output-size lower bound does not itself constitute an NP-hardness reduction. The result proved here rules out the polynomial-time alternative for the stated explicit output, while leaving NP-hardness unsettled.
⟨structured verdict parsed — rendered above⟩
The support-size lower bound and its instance family are correct. They rigorously rule out polynomial total running time under binary input encoding and the required explicit output format. They do not establish NP-hardness, as the prover explicitly acknowledges. The result is therefore partial relative to USER_TASK, with no mathematical error found in the argument presented.
This is justified. Every agent receives exactly one item, so the total allocated mass is \(1\). The supplies also sum to \(1\). Since each allocated item mass is bounded above by its supply, all those bounds must be tight. In particular, \(\lambda(R_i)=p\) in every realization.
The equation
\[
\sum_{i=1}^{K}w_i\mathbf{1}_{R_i}(x)=\rho
\]
correctly expresses the common marginal probability of receiving \(r\). The sets are measurable, the sum is finite, and the probabilities sum to \(1\). Integration therefore gives \(\rho=p\).
There is no unjustified interchange of limits or integrals. The same calculation is valid if exchangeability holds only almost everywhere.
Because \(p>0\), the marginal equation implies that every agent belongs to at least one \(R_i\). Under almost-everywhere exchangeability, the union instead has full measure, which is sufficient.
Finite subadditivity gives
\[
1\leq Kp,
\]
and integrality of \(K\) gives \(K\geq\lceil 1/p\rceil\). This argument does not require equal probabilities or any special geometry of the measurable sets.
Finding: The lower bound is fully established.
For every integer \(q\geq2\), the masses, supplies, and values satisfy all stated input restrictions.
Finding: All calculations and domain conditions are correct.
In a weak improvement, every original recipient of \(r\) must continue receiving \(r\), since it is the only item giving that agent value \(1\). Strict improvement is possible only for an original recipient of \(c\) who receives \(r\).
Consequently, a positive mass of strict improvements would require allocating \(r\) to its original mass \(1/q\) plus a positive additional mass. That violates the supply constraint.
Finding: Every feasible realization in this instance family is Pareto optimal under the stated definition. Possible changes on null sets do not invalidate the argument, because strict improvement must occur on positive mass.
The \(q\) half-open intervals form a measurable partition of \([0,1)\), each with measure \(1/q\). Each proposed realization therefore respects supplies. Their rational endpoints give finite descriptions.
Every agent lies in exactly one interval, including agents at partition boundaries. With probability \(1/q\) on each realization, every agent has the required marginal probability. Section 2 of the prover’s output supplies all remaining guarantees.
Combining this construction with the lower bound establishes that the minimum support size is exactly \(q\).
For \(q=2^n\), the numerator and denominator encodings of the supplies have length \(O(n)\); all other input data have constant size. Every valid output nevertheless lists at least \(2^n\) support elements.
Under the specified explicit-list representation, writing those entries takes at least \(\Omega(2^n)\) time in the usual sequential computation model. This correctly rules out polynomial total running time, independently of any complexity-class separation.
The prover also correctly distinguishes an explicit list from a formula or sampling procedure that describes many realizations succinctly.
Major scope issue — the target complexity classification remains incomplete. The output establishes an unconditional output-length obstruction, but supplies no NP-hardness reduction. Failure of polynomial total running time because of mandatory output length does not imply NP-hardness.
This is an acknowledged limitation, not a false inference in the proof. No clarification or routine calculation would close it. To claim a complete NP-hardness resolution of USER_TASK, the prover would need to specify an appropriate reduction notion for the explicit-output search problem and prove hardness under that notion. The current lower-bound write-up itself needs no mathematical repair.
⟨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.