Answer: polynomial-time solvable
Theorem 6.2. — class: algorithmic
Algorithm 2 is a strongly polynomial-time algo- rithm that gives an outcome that is ex-ante WEF, and ex-post WPROP1, ex-ante Pareto optimal, and ex-post Pareto optimal.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent types \(T\), item categories \(G\), masses \(\mu_t\), per-person entitlements \(a_t\), additive values \(v_t(g)\), and supplies \(q_g\) per unit population, compute a weighted-MNW ex-ante allocation \(F\) and a succinct lottery over continuum allocation patterns implementing \(F\), such that every recipient receives an integral bundle satisfying WPROP1 and every supported pattern is Pareto optimal.
Let \(T\) be finite, with masses \(\mu_t>0\), \(\sum_t\mu_t=1\), entitlements \(a_t>0\), \(\sum_t\mu_ta_t=1\), additive values \(v_t(g)\), and per-capita supplies \(q_g\) of item categories \(g\in G\). A feasible integral pattern is a measurable assignment of finite integral bundles to recipients such that category \(g\) is assigned to mass \(q_g\); \(F_{tg}\) is type \(t\)'s expected number of \(g\)'s.
Write \(U_t(F_s)=\sum_gv_t(g)F_{sg}\). Ex-ante WEF means \(U_t(F_t)/a_t\ge U_t(F_s)/a_s\) for all \(t,s\). An individual type-\(t\) bundle \(B\) is WPROP1 if \(v_t(B)\ge a_t\sum_gq_gv_t(g)\), or this holds after adding one unreceived item. A pattern is PO if no feasible measurable integral pattern weakly improves every recipient and strictly improves a positive-mass set.
Target.
For rational input data, is computing an expected allocation \(F\) and a finite implementing lottery that maximizes \(\sum_t\mu_ta_t\log U_t(F_t)\), is ex-ante WEF, and whose supported patterns are WPROP1 and PO in P, or is it NP-hard?
Nearest known results.
For a finite list of agents with weighted entitlements and additive valuations, this weighted maximum-Nash-welfare lottery problem has a strongly polynomial-time algorithm: its expectation is WEF and PO, and every supported integral allocation is WPROP1 and PO.
Assume the standard goods interpretation:
Then the target problem is polynomial-time solvable. In fact, the implementing lottery may be chosen to have a single pattern.
The nonatomic assumption is essential to the formulation. If type populations may contain atoms, the masses $\mu_t$ alone do not determine which bundle frequencies are implementable.
Put
$$ b_t:=\mu_ta_t,\qquad y_{tg}:=\mu_tF_{tg}. $$
Then $\sum_t b_t=1$, and feasibility becomes
$$ \sum_t y_{tg}=q_g. $$
Moreover,
$$ U_t(F_t)=\frac{1}{\mu_t}\sum_gv_t(g)y_{tg}. $$
Consequently, up to the constant $-\sum_tb_t\log\mu_t$, the objective is
$$ \max_{y\ge0} \sum_tb_t\log\left(\sum_gv_t(g)y_{tg}\right) \quad\text{subject to}\quad \sum_ty_{tg}\le q_g. \tag{1} $$
This is the Eisenberg–Gale program for a linear Fisher market with buyers $t$, budgets $b_t$, and supplies $q_g$. Exact rational equilibria of linear Fisher markets are computable in polynomial time; indeed, a strongly polynomial algorithm is known for the linear case ([Orlin, 2010](https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.2)).
If some constraint in (1) is slack, then the corresponding category is valued at zero by every type: otherwise assigning a positive additional amount to a type valuing it would strictly increase the objective. Such universally valueless leftovers can therefore be assigned arbitrarily. Hence we obtain a rational optimum satisfying
$$ \sum_ty_{tg}=q_g $$
for every $g$. Set $F_{tg}=y_{tg}/\mu_t$.
No denominator-clearing expansion into individual agents or individual items is used.
Let $p_g\ge0$ be optimal dual multipliers for the supply constraints in (1). The KKT conditions give, for every $t,g$,
$$ \frac{b_tv_t(g)} {\sum_hv_t(h)y_{th}} \le p_g, \tag{2} $$
with equality whenever $y_{tg}>0$. Since $b_t=\mu_ta_t$ and $\sum_hv_t(h)y_{th}=\mu_tU_t(F_t)$, (2) becomes
$$ \frac{a_tv_t(g)}{U_t(F_t)}\le p_g. \tag{3} $$
Summing the equalities in (3) over the categories with $F_{tg}>0$ gives
$$ p\mathbin{\cdot}F_t = \frac{a_t}{U_t(F_t)} \sum_gv_t(g)F_{tg} =a_t. \tag{4} $$
For arbitrary $s,t$, inequality (3) and (4) imply
$$ U_t(F_s) =\sum_gv_t(g)F_{sg} \le \frac{U_t(F_t)}{a_t} \sum_gp_gF_{sg} = \frac{U_t(F_t)}{a_t}a_s. $$
Thus
$$ \frac{U_t(F_t)}{a_t} \ge \frac{U_t(F_s)}{a_s}, $$
which is precisely ex-ante WEF.
Fix $t$. Multiply its WEF inequality against type $s$ by $\mu_sa_s$ and sum over $s$. Using $\sum_s\mu_sa_s=1$ gives
$$ \frac{U_t(F_t)}{a_t} \ge \sum_s\mu_sU_t(F_s). $$
Feasibility gives
$$ \sum_s\mu_sU_t(F_s) = \sum_gv_t(g)\sum_s\mu_sF_{sg} = \sum_gq_gv_t(g) =V_t. $$
Therefore
$$ U_t(F_t)\ge a_tV_t. \tag{5} $$
This is the fractional weighted-proportionality bound needed for the WPROP1 implementation.
Given rational $x\in\mathbb Q_{\ge0}^G$ and nonnegative additive values $v_g$, one can compute in polynomial time a rational distribution over at most $|G|+1$ integral bundles $b$ such that
$$ \mathbb E[b]=x, $$
and every supported $b$ satisfies either
$$ v(b)\ge v(x), $$
or there is an unselected residual item $g$ such that
$$ v(b)+v_g>v(x). \tag{6} $$
Write
$$ x_g=n_g+r_g,\qquad n_g=\lfloor x_g\rfloor,\quad 0\le r_g<1. $$
Discard coordinates with $r_g=0$, and order the remaining coordinates as $g_1,\ldots,g_k$ so that
$$ v_{g_1}\ge v_{g_2}\ge\cdots\ge v_{g_k}. $$
Put
$$ R_j:=\sum_{i=1}^jr_{g_i},\qquad R_0:=0. $$
For $\theta\in[0,1)$, select $g_i$ precisely when the interval $(R_{i-1},R_i]$ contains a point of the shifted lattice $\theta+\mathbb Z$. Because $r_{g_i}<1$, at most one such point lies in this interval.
For uniform $\theta$, the selection probability of $g_i$ is exactly the length $r_{g_i}$ of the interval modulo one. Thus the bundle
$$ b_g=n_g+\mathbf 1[g\text{ is selected}] $$
has expectation $x$.
The selected set changes only when $\theta$ crosses one of the fractional parts of $R_0,\ldots,R_k$. Partitioning $[0,1)$ at these rational breakpoints therefore converts this construction into a rational distribution over at most $k+1$ bundles.
For a supported selected set, define
$$ C_j:=\sum_{i=1}^j\mathbf 1[g_i\text{ is selected}], \qquad D_j:=C_j-R_j. $$
The interval $(0,R_j]$ contains either $\lfloor R_j\rfloor$ or $\lceil R_j\rceil$ shifted lattice points. Hence
$$ -1<D_j<1. \tag{7} $$
Let
$$ \Delta:=v(b)-v(x) =\sum_{i=1}^kv_{g_i} \left(\mathbf 1[g_i\text{ is selected}]-r_{g_i}\right). $$
Summation by parts yields
$$ \Delta = v_{g_k}D_k+ \sum_{j=1}^{k-1} \left(v_{g_j}-v_{g_{j+1}}\right)D_j. \tag{8} $$
Suppose $\Delta<0$. Then not every residual item is selected. Let $h$ be the first unselected index. For $j<h$, every $g_1,\ldots,g_j$ is selected, so
$$ D_j=j-R_j>0. $$
For $j\ge h$, (7) gives $D_j>-1$. Since the value sequence is nonincreasing, all coefficients in (8) are nonnegative. Therefore
$$ \begin{aligned} \Delta &> -\left( v_{g_k} + \sum_{j=h}^{k-1}(v_{g_j}-v_{g_{j+1}}) \right)\\ &=-v_{g_h}. \end{aligned} $$
Thus $v(b)+v_{g_h}>v(x)$. Since $g_h$ was not selected, this is an unreceived residual copy. This proves the lemma.
Apply the lemma to $x=F_t$ and $v_g=v_t(g)$ separately for each type $t$. Let its resulting distribution be
$$ \{(\lambda_{t\ell},b^{t\ell})\}_{\ell=1}^{K_t}, \qquad K_t\le |G|+1. $$
Thus
$$ \sum_\ell\lambda_{t\ell}b^{t\ell}_g=F_{tg}. \tag{9} $$
Because the type-$t$ population is nonatomic, partition it measurably into sets of masses
$$ \mu_t\lambda_{t1},\ldots,\mu_t\lambda_{tK_t}, $$
and give bundle $b^{t\ell}$ to every recipient in the $\ell$-th set.
By (9), the total assigned mass of category $g$ is
$$ \sum_t\mu_t\sum_\ell\lambda_{t\ell}b^{t\ell}_g = \sum_t\mu_tF_{tg} =q_g. $$
Hence this is a feasible integral pattern.
For every supported bundle $b^{t\ell}$, the rounding lemma gives either
$$ v_t(b^{t\ell})\ge U_t(F_t), $$
or an unreceived item $g$ such that
$$ v_t(b^{t\ell})+v_t(g)>U_t(F_t). $$
Combining this with (5) shows that every recipient is WPROP1.
Let $A$ denote the constructed pattern. Suppose another feasible measurable integral pattern $A'$ weakly improves every recipient and strictly improves a positive-mass set.
Define its type averages by
$$ F'_{tg}:= \frac1{\mu_t} \int_{\text{type }t}A'_g(x)\,dx. $$
Then $F'$ is feasible. Moreover,
$$ U_t(F'_t)-U_t(F_t) = \frac1{\mu_t} \int_{\text{type }t} \left(v_t(A'(x))-v_t(A(x))\right)\,dx \ge0. $$
Because $T$ is finite and strict improvement occurs on a positive-mass set, it occurs on a positive-mass subset of at least one type. The corresponding nonnegative integrand is strictly positive on a positive-measure set, so its integral is strictly positive. Therefore, for some $t$,
$$ U_t(F'_t)>U_t(F_t). $$
All $U_t(F_t)$ are positive. Consequently,
$$ \sum_t\mu_ta_t\log U_t(F'_t) > \sum_t\mu_ta_t\log U_t(F_t), $$
contradicting the optimality of $F$. Hence $A$ is PO.
Return the degenerate lottery placing probability $1$ on $A$.
The output contains at most
$$ \sum_tK_t\le |T|(|G|+1) $$
type-bundle classes. Exact Fisher-market algorithms return rational allocations of polynomial encoding length. Floors, cumulative sums, rational breakpoint sorting, and interval lengths all require polynomially many rational arithmetic operations, and all bundle counts are written in binary.
Thus the entire expected allocation and implementing lottery have polynomial encoding length and are computable in polynomial time.
Finally, $F$ maximizes the objective over all feasible expectations. Since the constructed $F$ also satisfies WEF and admits a WPROP1-and-PO implementation, it also maximizes the objective over the target’s more restricted feasible set.
⟨structured verdict parsed — rendered above⟩
The argument is mathematically coherent under the prover’s added assumptions: finite goods, nonnegative valuations, positive attainable utility for every type, nonatomic populations, and the proposed finite representation of a pattern. Under those assumptions, the Fisher-market reduction, WEF derivation, rounding construction, WPROP1 conclusion, and Pareto-optimality argument all stand.
It does not fully resolve USER_TASK as written, however. Several assumptions essential to the proof are not present in the task. In particular, the proof gives only a conditional polynomial-time result, whereas the target asks for a classification for the stated rational inputs.
The substitutions
$$ b_t=\mu_ta_t,\qquad y_{tg}=\mu_tF_{tg} $$
are correct. Feasibility becomes
$$ \sum_ty_{tg}=q_g, $$
and
$$ U_t(F_t)=\frac{1}{\mu_t}\sum_gv_t(g)y_{tg}. $$
Consequently, the logarithmic objective differs from the Eisenberg–Gale objective by an allocation-independent constant. This reduction is valid when all relevant utilities are positive.
Replacing equality by
$$ \sum_ty_{tg}\le q_g $$
is valid under nonnegative valuations: any slack good valued positively by some type could improve that type’s positive utility, while a universally valueless good can be used to fill the equality without changing utilities.
This reasoning fails without nonnegative valuations. The original task merely says “additive values”; it does not explicitly impose $v_t(g)\ge0$. For example, with one type and both a positive-valued and a negative-valued mandatory-supply category, the relaxed program may discard the negative item even though the original feasibility condition requires assigning it.
The cited source does verify a strongly polynomial algorithm for linear Fisher markets, but it explicitly describes divisible goods with integral money and integral utility inputs. The write-up does not state the reductions needed for rational budgets, rational supplies, or recovery of a polynomial-bit allocation from the computed market equilibrium. These are plausibly routine, but they are required for the precise complexity claim. See [Orlin, “Improved Algorithms for Computing Fisher’s Market Clearing Prices”](https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.2).
The KKT inequality
$$ \frac{b_tv_t(g)}{\sum_hv_t(h)y_{th}}\le p_g $$
with equality for $y_{tg}>0$ is correct for the nonnegative linear Fisher program.
Substitution yields
$$ \frac{a_tv_t(g)}{U_t(F_t)}\le p_g. $$
Summing the equalities over the support of $F_t$ correctly gives
$$ p\cdot F_t=a_t. $$
Applying the coordinatewise inequality to $F_s$ then gives
$$ U_t(F_s)\le\frac{U_t(F_t)}{a_t}p\cdot F_s =\frac{U_t(F_t)}{a_t}a_s. $$
Thus ex-ante WEF follows. No gap was found in this part under the stated positivity assumptions.
Multiplying WEF by $\mu_sa_s$ and summing over $s$ is correct because
$$ \sum_s\mu_sa_s=1. $$
Feasibility gives
$$ \sum_s\mu_sU_t(F_s)=\sum_gq_gv_t(g)=V_t. $$
Therefore
$$ U_t(F_t)\ge a_tV_t. $$
This step is correct.
The shifted-lattice construction gives each residual coordinate marginal probability $r_g$, so its expectation is $x$.
The number of positive-probability regions is at most $k+1$, since selection changes only at the fractional parts of $R_0,\ldots,R_k$. The treatment of exact breakpoint values is not specified, but those values have probability zero; an explicit convention would make the finite distribution completely formal.
For every prefix,
$$ -1<D_j<1 $$
is correct. The summation-by-parts identity
$$ \Delta = v_{g_k}D_k+ \sum_{j=1}^{k-1}(v_{g_j}-v_{g_{j+1}})D_j $$
is also correct.
If $h$ is the first unselected coordinate, then $D_j>0$ for $j<h$, while $D_j>-1$ thereafter. Because the coefficients are nonnegative, the conclusion
$$ \Delta>-v_{g_h} $$
follows. Thus the lemma itself is sound.
Assuming each type population is nonatomic, partitions with prescribed masses $\mu_t\lambda_{t\ell}$ exist. The resulting category totals are exactly
$$ \sum_t\mu_tF_{tg}=q_g. $$
Each bundle either has value at least $U_t(F_t)$ or reaches a value strictly above $U_t(F_t)$ after adding the identified residual item. Combined with
$$ U_t(F_t)\ge a_tV_t, $$
this establishes WPROP1.
The phrase “unreceived residual item” needs a precise interpretation in the continuum/category model. The construction proves that one extra unit of category $g$ was not selected for that bundle and that the residual marginal $r_g$ is positive. Whether this is exactly the task’s notion of an “unreceived item” depends on how physical copies are represented. The task does not define this point.
For a recipientwise Pareto improvement $A'$, averaging within types gives a feasible expectation $F'$.
Since every recipient’s utility change is nonnegative, each type’s mean utility is weakly higher. Because there are finitely many types, strict improvement on a positive-mass set occurs on a positive-mass subset of at least one type. The associated nonnegative measurable utility difference then has a strictly positive integral. Hence some type’s average utility is strictly higher.
As every original type utility is positive, strict monotonicity of the logarithm gives a strictly larger objective, contradicting optimality. This establishes Pareto optimality of the constructed pattern under the added assumptions.
A degenerate lottery on the constructed pattern is indeed a finite implementing lottery. The rounding stage has at most $|T|(|G|+1)$ type-bundle classes, and its rational arithmetic has polynomial bit complexity.
However, the claim that the entire algorithm has polynomial bit complexity still relies on an unstated rational-input reduction to the cited Fisher-market algorithm and on polynomial-time recovery of a rational equilibrium allocation, not merely prices. This is a minor verification gap conditional on the model assumptions.
USER_TASKThe following are not merely expositional:
USER_TASK does not state this. The relaxed Fisher program and its monotonicity arguments depend essentially on it.USER_TASK. On such inputs the logarithmic objective may be identically $-\infty$ or otherwise require an explicit convention, and the proof does not classify them.To make the claimed classification verifiable, the task or theorem must explicitly restrict to finite $G$, nonnegative rational valuations, positive $V_t$, nonatomic type spaces, and the stated finite class-mass encoding of patterns. The write-up must also state how rational Fisher instances meet the cited algorithm’s input hypotheses and how a polynomial-bit equilibrium allocation is recovered.
⟨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.