Answer: \(\text{Polynomial-time solvable}\)
Theorem 19 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 achieves asymptotic truthfulness and computes an asymptotic core solution with high probability in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For \(m\) divisible public items with feasible allocation set \(Z\), utility reports in the paper’s admissible class, and a population supported on at most \(\tau\) utility types with rational masses \(\mu_t\) satisfying \(N\mu_t\in\mathbb{Z}\), can one compute a randomized mechanism \(M_N\) in time polynomial in \(N,\tau,m,L\) that is asymptotically truthful under every one-resident report change of mass \(1/N\) and returns an asymptotic core allocation with high probability? Here, for true type \(t\), alternative report \(t'\), and other-resident mass vector \(\nu\), truthfulness compares \(\mathbb{E}[U_t(M_N(\nu+e_t/N))]\) with \((1-\epsilon_N)\mathbb{E}[U_t(M_N(\nu+e_{t'}/N))]-\delta_N\), where \(\epsilon_N,\delta_N\to0\). The core condition treats a coalition as masses \(a_t\in[0,\mu_t]\), with \(\alpha=\sum_t a_t>0\), and rules out allocations \(z'\in Z\) satisfying \(\alpha U_t(z')\ge(1+\eta_N)U_t(z)+\kappa_N\) for every participating type, with strict improvement on positive mass, where \(\eta_N,\kappa_N\to0\).
Let \(m,d\ge1\), let \(c,s_1,\ldots,s_m\) be positive binary rationals, and define \(Z=\{z\in[0,1]^m:\sum_jz_j\le1,\;cz_j\le s_j\ \forall j\}\); allocations specify fractions of the full capacity.
An admissible type has a binary-rational parameter vector \(u_t\in[0,1]^d\) specifying a differentiable, coordinatewise strictly increasing, concave utility \(U_t:Z\to[0,1]\), with \(U_t(0)=0\), positive somewhere, and \(\beta\)-Lipschitz gradient for a fixed common \(\beta\). The utility family is publicly specified; values and gradients at rational points can be approximated to absolute error \(2^{-b}\) in time polynomial in \(m,d,L,b\).
A society is given by its support: the list of its \(\tau\) types with positive binary-rational masses \(\mu_t\). Here \(\tau\) is the support size, not the number of possible types; \(\sum_t\mu_t=1\). An integer \(N\ge2\) satisfies \(N\mu_t\in\mathbb Z\); \(L\) is the total binary input length, and running time is measured in \(N,\tau,m,d,L\), allowing polynomial dependence on the numerical value of \(N\).
A randomized mechanism \(M_N\) samples a feasible rational allocation from the reported society. Reports may introduce admissible types absent from the original support. For every admissible \(t,t'\) and nonnegative rational vector \(\nu\) with \(\sum_r\nu_r=1-1/N\) and \(N\nu_r\in\mathbb Z\), require \(\mathbb E[U_t(M_N(\nu+e_t/N))]\ge(1-\epsilon_N)\mathbb E[U_t(M_N(\nu+e_{t'}/N))]-\delta_N\), where \(e_t\) denotes unit mass at type \(t\).
An allocation \(z\) satisfies the \((\eta_N,\kappa_N)\)-mass core if there are no real coalition masses \(a_t\in[0,\mu_t]\), with \(\alpha=\sum_ta_t>0\), and \(z'\in Z\) such that \(\alpha U_t(z')\ge(1+\eta_N)U_t(z)+\kappa_N\) for every \(t\) with \(a_t>0\), strictly for at least one such type. Coalition masses need not be multiples of \(1/N\).
Require this core condition with probability at least \(1-1/N-1/N^m\), with nonnegative, instance-uniform errors \(\epsilon_N,\delta_N,\eta_N,\kappa_N\to0\) as \(N\to\infty\) along \(m=o(\sqrt N)\).
Is sampling a mechanism satisfying these truthfulness and mass-core guarantees possible in time polynomial in \(N,\tau,m,d,L\), or is this computational task NP-hard?
For finite societies, PPGA is stated to achieve asymptotic truthfulness and asymptotic core membership with the stated probability in polynomial time under \(m=o(\sqrt N)\). [Kananian, Sujanani, and Zahedi](https://www.jair.org/index.php/jair/article/download/19414/27258/52390).
No result settling exactly the support-input problem with arbitrary real coalition masses was identified in the search.
The task is polynomial-time solvable. A deterministic mechanism suffices: approximately maximize a smoothed Nash-welfare objective with a small quadratic regularizer. Smoothing bounds the effect of changing one report; regularization makes the optimizer stable.
The proof below includes rational output, polynomial bit complexity, reports introducing previously absent types, and arbitrary real coalition masses. It does not depend on implementing PPGA.
First, arbitrary real coalition masses do not create an additional obstruction in this model.
Suppose an allocation is blocked by masses \((a_t)_t\), with total mass \(\alpha>0\), and alternative \(z'\). Let \(S=\{t:a_t>0\}\). Replace the coalition masses by
\( \widehat a_t=\mu_t \) for \(t\in S\), and \( \widehat a_t=0 \) otherwise.
Their total mass \(\widehat\alpha\) satisfies \(\widehat\alpha\ge\alpha\). Since utilities are nonnegative,
\( \widehat\alpha U_t(z')\ge\alpha U_t(z') \)
for every participating type. Thus every blocking inequality remains valid, including the strict inequality. Consequently, whenever a real-mass blocking coalition exists, one exists that includes the entire mass of every participating type.
Because \(N\mu_t\) is integral, this also proves equivalence between the stated mass-core condition and the corresponding finite-agent core condition for the population containing \(N\mu_t\) copies of each type. This explains why the coalition distinction alone does not prevent applying a finite-society result such as [the cited PPGA theorem](https://www.jair.org/index.php/jair/article/download/19414/27258/52390). We nevertheless give a direct construction to establish the required computational guarantees.
Fix an integer constant \(B\ge 1+2\beta\). It depends only on the fixed common smoothness bound.
Define
\( w_j=\min\{1,s_j/c\},\qquad D=\operatorname{diag}(w_1,\ldots,w_m), \)
and introduce the rational polytope
\( K=\{x\in[0,1]^m:\sum_j w_jx_j\le1\}. \)
The map \(x\mapsto Dx\) is a bijection from \(K\) to \(Z\). For every admissible type, put
\( V_t(x)=U_t(Dx). \)
We claim that, uniformly over all admissible types,
\( \|\nabla V_t(x)\|_2\le B\sqrt m,\qquad \|\nabla V_t(x)-\nabla V_t(y)\|_2\le\beta\|x-y\|_2. \)
For the first bound, the segment from \(0\) to \(w_je_j\) lies in \(Z\). Integrating the Lipschitz-gradient bound along that segment gives
\( U_t(w_je_j)\ge w_j\partial_jU_t(0)-\frac{\beta w_j^2}{2}. \)
Since \(U_t(w_je_j)\le1\), it follows that
\( w_j\partial_jU_t(0)\le1+\frac{\beta}{2}. \)
Also, \(\partial_jU_t(0)\ge0\), by coordinatewise monotonicity along this segment. For any \(z\in Z\), we have \(\|z\|_2\le1\), and therefore
\( |w_j\partial_jU_t(z)| \le w_j\partial_jU_t(0)+w_j\beta\|z\|_2 \le1+\frac{3\beta}{2}\le B. \)
The chain rule now gives the asserted gradient bound. For the second bound, use \(\|D\|_2\le1\):
\( \|\nabla V_t(x)-\nabla V_t(y)\|_2 =\|D(\nabla U_t(Dx)-\nabla U_t(Dy))\|_2 \le\beta\|x-y\|_2. \)
In particular, every \(V_t\) is \(G\)-Lipschitz on \(K\), where
\( G=B\sqrt m. \)
This normalization is essential: the original gradients need not have instance-uniform bounds when some capacities are very small.
Choose a dyadic rational \(r\in(0,1]\) as follows. If \(m^2>N\), set \(r=1\). Otherwise, let \(k\) be the largest nonnegative integer satisfying
\( 2^{4k}m^2\le N, \)
and set \(r=2^{-k}\). Thus, when \(m^2\le N\),
\( (m^2/N)^{1/4}\le r<2(m^2/N)^{1/4}, \)
and always \(r^{-1}\le N^{1/4}\).
Set
\( \lambda=\frac rm,\qquad h=\frac{r^3}{8B^2m^2}. \)
For a reported society \(\mu\), define
\( F_\mu(x)=\sum_t\mu_t\log(V_t(x)+r)-\frac{\lambda}{2}\|x\|_2^2, \qquad x\in K. \)
Each logarithmic term is concave because \(V_t+r\) is positive and concave, and the logarithm is increasing and concave. Hence \(F_\mu\) is differentiable and \(\lambda\)-strongly concave. It has a unique maximizer \(x_\mu^*\), since \(K\) is compact.
The mechanism computes a rational point \(x_\mu\in K\) satisfying the directional-gradient certificate
\( g_\mu(x_\mu):= \max_{y\in K}\nabla F_\mu(x_\mu)\cdot(y-x_\mu)\le h, \)
and outputs \(z_\mu=Dx_\mu\). Section 6 proves that this computation takes polynomial time.
Use the following errors:
\( \epsilon_N=0,\qquad \delta_N=\min\left\{1,\frac{2B^2m^2}{Nr^2}+r\right\}, \)
\( \eta_N=2r,\qquad \kappa_N=(1+2r)r. \)
These bounds depend only on \(N,m\) and the fixed common \(\beta\).
Fix a reported society and write \(x=x_\mu\). For any \(y\in K\), concavity of \(V_t\) implies
\( V_t(y)\le V_t(x)+\nabla V_t(x)\cdot(y-x). \)
Divide by \(V_t(x)+r>0\), multiply by \(\mu_t\), and sum. Using the formula for \(\nabla F_\mu\), we obtain
\( \sum_t\mu_t\frac{V_t(y)}{V_t(x)+r} \le \sum_t\mu_t\frac{V_t(x)}{V_t(x)+r} +\nabla F_\mu(x)\cdot(y-x) +\lambda x\cdot(y-x). \)
The three terms on the right are bounded respectively by \(1\), \(h\), and \(\lambda m=r\). The last bound follows from \(x,y\in[0,1]^m\). Since \(h\le r\), this proves
\[ \sum_t\mu_t\frac{V_t(y)}{V_t(x)+r}\le1+2r. \tag{1} \]
Suppose, towards a contradiction, that real coalition masses \(a_t\in[0,\mu_t]\), of total mass \(\alpha>0\), and an alternative \(Dy\in Z\) block the output for the stated errors. Then every participating type satisfies
\( \alpha V_t(y)\ge(1+2r)V_t(x)+(1+2r)r =(1+2r)(V_t(x)+r), \)
with a strict inequality for at least one participating type. Dividing and summing with weights \(a_t\) gives
\( \sum_t a_t\frac{V_t(y)}{V_t(x)+r}>1+2r. \)
Every ratio is nonnegative and \(a_t\le\mu_t\), so this contradicts (1).
Thus the output always belongs to the \((\eta_N,\kappa_N)\)-mass core. No discretization of coalition masses was used.
Concavity and the gradient certificate imply
\( F_\mu(x_\mu^*)-F_\mu(x_\mu) \le\nabla F_\mu(x_\mu)\cdot(x_\mu^*-x_\mu)\le h. \)
At a constrained maximizer, the first-order optimality condition is
\( \nabla F_\mu(x_\mu^*)\cdot(x-x_\mu^*)\le0 \quad\text{for all }x\in K. \)
Combining this condition with strong concavity gives
\( F_\mu(x_\mu^*)-F_\mu(x) \ge\frac{\lambda}{2}\|x-x_\mu^*\|_2^2. \)
Consequently,
\[ \|x_\mu-x_\mu^*\|_2\le\sqrt{2h/\lambda}. \tag{2} \]
Consider any neighboring societies
\( p=\nu+e_t/N,\qquad q=\nu+e_{t'}/N. \)
Their supports may differ. Nevertheless, their objectives satisfy the exact identity
\( F_p(x)-F_q(x) =\frac1N\bigl(\log(V_t(x)+r)-\log(V_{t'}(x)+r)\bigr). \)
Since \(\|\nabla V_t\|_2\le G\), each logarithmic term is \(G/r\)-Lipschitz. Therefore \(F_p-F_q\) is \(2G/(Nr)\)-Lipschitz.
Apply the strong-concavity inequality at both exact maximizers and add:
\( \lambda\|x_p^*-x_q^*\|_2^2 \le (F_p-F_q)(x_p^*)-(F_p-F_q)(x_q^*) \le\frac{2G}{Nr}\|x_p^*-x_q^*\|_2. \)
If the distance is nonzero, divide by it; otherwise the following bound is immediate:
\[ \|x_p^*-x_q^*\|_2\le\frac{2G}{Nr\lambda}. \tag{3} \]
Using (2), (3), and the \(G\)-Lipschitz property of the true type’s utility yields
\( |V_t(x_p)-V_t(x_q)| \le\frac{2G^2}{Nr\lambda} +2G\sqrt{2h/\lambda} =\frac{2B^2m^2}{Nr^2}+r. \)
Utilities also lie in \([0,1]\), so the difference is at most \(1\). Hence
\( U_t(z_p)\ge U_t(z_q)-\delta_N. \)
This is exactly the required truthfulness inequality with \(\epsilon_N=0\). Viewing the deterministic output as a point-mass distribution gives the same inequality in expectation. The proof applies to every admissible \(t,t'\), including types absent from the original support.
We now construct the directional-gradient certificate using only the promised approximation oracles and rational arithmetic.
The gradient of \(F_\mu\) is Lipschitz with constant at most
\( H=\frac Br+\frac{B^2m}{r^2}+\lambda. \)
Indeed, for a logarithmic term, the gradient difference is bounded by the sum of \(\beta/r\) times the distance and \(G^2/r^2\) times the distance. Weighted summation and the quadratic term give the displayed bound, since \(B\ge\beta\).
The squared diameter of \(K\) is at most \(m\). Put
\( C=mH,\qquad \theta=\frac{h}{4C}. \)
These are positive rationals, and \(0<\theta\le1\).
A rational linear objective can be maximized over \(K\) by continuous knapsack: discard nonpositive coefficients, sort the remaining coordinates by coefficient divided by \(w_j\), and fill them in that order subject to \(x_j\le1\) and the remaining budget. The exchange argument proves optimality: budget assigned to a smaller ratio can be moved to an unsaturated larger ratio without violating feasibility and while increasing the objective. This algorithm uses polynomially many exact rational operations.
At a rational point \(x\in K\), approximate each utility value and gradient coordinate to error at most
\( \xi=\frac{hr^2}{4m(1+B)}. \)
Clip approximate utility values to \([0,1]\). Multiply approximate original gradient coordinates by \(w_j\), and clip the results to \([-B,B]\). Clipping preserves their error bounds because the true quantities lie in those intervals.
For a coordinate of a logarithmic gradient, the resulting error is at most
\( \frac{\xi}{r}+\frac{B\xi}{r^2} \le\frac{(1+B)\xi}{r^2} =\frac{h}{4m}. \)
Thus we can compute a rational vector \(\widehat g\) satisfying
\[ \|\widehat g-\nabla F_\mu(x)\|_\infty\le\frac{h}{4m}. \tag{4} \]
Start at \(x=0\). At each iteration, compute \(\widehat g\), and use linear optimization to choose
\( y\in\operatorname*{arg\,max}_{v\in K}\widehat g\cdot v. \)
Compute the rational number \(\widehat s=\widehat g\cdot(y-x)\).
If \(\widehat s\le h/2\), return \(x\). Otherwise update
\( x\leftarrow x+\theta(y-x). \)
Every iterate is rational and feasible.
By (4), for every \(v\in K\),
\( |(\widehat g-\nabla F_\mu(x))\cdot(v-x)|\le h/4. \)
Consequently, upon termination the true directional-gradient maximum is at most \(3h/4\), and hence at most \(h\), as required.
At a nonterminating iteration,
\( \nabla F_\mu(x)\cdot(y-x)>h/4. \)
Smoothness then gives
\( F_\mu(x+\theta(y-x))-F_\mu(x) \ge\theta h/4-C\theta^2/2 =\frac{h^2}{32C}. \)
Throughout \(K\), the range of \(F_\mu\) is at most
\( \log((1+r)/r)+r/2\le2/r. \)
Therefore the algorithm terminates after at most
\( \left\lceil\frac{64C}{rh^2}\right\rceil+1 \)
iterations.
This bound is polynomial in \(N,m\): \(B\) is fixed, \(r^{-1}\le N^{1/4}\), and \(h^{-1}=8B^2m^2r^{-3}\).
The required oracle precision has
\( \log(1/\xi)=O(\log m+\log N+1) \)
bits, with constants depending only on \(B\). Each iteration evaluates only the listed support types, so its oracle work is polynomial in \(\tau,m,d\), the query encoding length, and this precision.
The knapsack solutions have polynomial rational encoding length: their coordinates are \(0\), \(1\), or a remaining rational budget divided by some \(w_j\). The fixed rational update factor \(\theta\) causes iterate encoding lengths to grow at most polynomially with the number of iterations and the input length. Thus all query points, intermediate arithmetic, and the final allocation \(Dx\) have polynomial encoding length.
Together with the assumed utility-oracle bounds, this proves total running time polynomial in \(N,\tau,m,d,L\).
Along any sequence with \(m=o(\sqrt N)\), put \(q=m^2/N\). Then \(q\to0\), and eventually
\( q^{1/4}\le r<2q^{1/4}. \)
Hence
\( \delta_N\le2B^2q^{1/2}+2q^{1/4}\to0,\qquad \eta_N=2r\to0,\qquad \kappa_N=(1+2r)r\to0, \)
while \(\epsilon_N=0\).
The mechanism always outputs a feasible rational allocation satisfying the stated mass-core condition. Its success probability is therefore \(1\), which exceeds \(1-1/N-1/N^m\). All four errors are instance-uniform in the required asymptotic regime.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The construction establishes polynomial-time solvability under the stated utility-oracle assumptions. The core, truthfulness, rational-output, and asymptotic guarantees all follow from the written argument. I found no major or minor issues requiring repair.
1. Arbitrary real coalition masses
The enlargement argument is valid. For a blocking coalition, its participating set \(S=\{t:a_t>0\}\) is unchanged when each positive mass is replaced by \(\mu_t\). Its total mass increases, and nonnegative utilities ensure that every blocking inequality remains valid. An inequality already strict remains strict.
The claimed equivalence with the corresponding finite-agent condition is also valid when that condition uses the same scaled utility inequalities: full-type coalitions have integral membership because \(N\mu_t\) is integral, and any finite-agent coalition supplies admissible mass fractions.
This observation does not establish the applicability of every other hypothesis of PPGA, but the prover does not rely on PPGA for its conclusion.
2. Normalization and uniform derivative bounds
All feasibility and domain claims check out:
The displayed lower bound for \(U_t(w_je_j)\) follows from the assumed Lipschitz gradient along that segment. Coordinatewise monotonicity gives \(\partial_jU_t(0)\ge0\), and the utility upper bound then yields \(w_j\partial_jU_t(0)\le1+\beta/2\).
The subsequent estimate gives \(|w_j\partial_jU_t(z)|\le1+3\beta/2\le B\). Thus the chain-rule conclusion \(\|\nabla V_t(x)\|_2\le B\sqrt m\) is correct.
The normalized gradient smoothness bound also follows correctly from \(\|D\|_2\le1\). Since \(K\) is convex, the resulting gradient bound establishes the claimed \(G\)-Lipschitz utility bound on all of \(K\).
These estimates are uniform over admissible types and independent of small capacities, as required.
3. Parameters and objective
The dyadic choice of \(r\) has the stated bounds. Maximality of \(k\) gives both \(r\ge(m^2/N)^{1/4}\) and \(r<2(m^2/N)^{1/4}\) in the applicable branch. The global bound \(r^{-1}\le N^{1/4}\) holds in both branches.
The logarithmic terms are well-defined because \(V_t+r\ge r>0\). Their concavity follows from the stated composition rule. Subtracting the quadratic term makes \(F_\mu\) \(\lambda\)-strongly concave. Continuity, compactness, and strong concavity justify existence and uniqueness of its maximizer.
The chosen constants satisfy \(h\le r\). All four reported errors are nonnegative and depend only on \(N,m\), and the fixed common smoothness bound.
4. Mass-core guarantee
The concavity inequality for each \(V_t\), its division by the positive denominator, and its weighted summation are valid. The gradient identity introduces exactly the regularizer correction \(\lambda x\cdot(y-x)\).
The three upper bounds are correct:
Therefore inequality (1) follows.
For a purported blocking coalition, the chosen errors give precisely \(\alpha V_t(y)\ge(1+2r)(V_t(x)+r)\). Division and summation with weights \(a_t\) yield a sum strictly greater than \(1+2r\): every participating mass is positive, including the mass attached to the strict inequality.
Nonnegativity of the ratios and \(a_t\le\mu_t\) then contradict (1). This proves the stated core condition for arbitrary real coalition masses, without any discretization assumption.
5. Truthfulness guarantee
The directional-gradient certificate correctly implies objective suboptimality at most \(h\). Strong concavity, together with the constrained first-order optimality condition, gives the stated distance bound (2).
For neighboring societies, the objective difference identity is exact even when their supports differ. Each logarithmic utility is \(G/r\)-Lipschitz, so their difference, scaled by \(1/N\), has the claimed Lipschitz constant.
Adding the two strong-concavity inequalities at the respective maximizers gives the displayed stability inequality. The prover explicitly handles the zero-distance case before division, so (3) has no missing exceptional case.
The final constants check exactly: \(2G^2/(Nr\lambda)=2B^2m^2/(Nr^2)\), and \(2G\sqrt{2h/\lambda}=r\). The utility range additionally bounds the difference by \(1\), justifying the minimum in \(\delta_N\).
Consequently, the required incentive inequality holds with \(\epsilon_N=0\). Deterministic output is an admissible point-mass randomized mechanism. The argument covers every admissible pair of reports, including previously absent types.
6. Computation and bit complexity
The algorithm supplies the promised certificate using only the available utility-value and gradient approximations.
The smoothness bound \(H\) is valid: the two contributions from a logarithmic gradient are bounded by \(\beta/r\) and \(G^2/r^2\), and the regularizer contributes \(\lambda\). Replacing \(\beta\) by \(B\) preserves the bound.
The linear optimization procedure is correct for this polytope. All weights \(w_j\) are strictly positive, so the coefficient-to-weight ratios are defined. Discarding nonpositive coefficients is permissible because unused capacity is allowed. The stated exchange argument justifies the greedy ordering.
For approximate gradients:
The stopping test is sound. The uniform coordinate error implies an inner-product error at most \(h/4\) for every feasible direction. Maximization of the approximate linear objective therefore bounds the true directional maximum by \(3h/4\) on termination.
At a nonterminating iteration, the selected true directional derivative exceeds \(h/4\). The smoothness inequality and the chosen step size yield the claimed improvement \(h^2/(32C)\); the arithmetic is correct. The objective-range bound is also valid, giving the stated finite iteration bound.
That bound is polynomial in the permitted numerical parameters because \(B\) is fixed, \(r^{-1}\le N^{1/4}\), and \(h^{-1}=8B^2m^2r^{-3}\).
The bit-complexity discussion is sufficient. Knapsack vertices have polynomial rational encoding length, and each fixed rational update increases encoding length by at most a polynomial amount. Polynomially many iterations therefore retain polynomial query and output lengths. The requested oracle precision likewise has polynomial bit length. No exact logarithm evaluations or irrational optimizer outputs are required.
7. Asymptotics and probability
Under \(m=o(\sqrt N)\), the quantity \(q=m^2/N\) tends to zero. The bounds on \(r\) correctly imply \(\delta_N\le2B^2q^{1/2}+2q^{1/4}\to0\), while \(\eta_N\to0\), \(\kappa_N\to0\), and \(\epsilon_N=0\).
The errors are instance-uniform in the stated regime. The core guarantee holds for every output, so its probability is \(1\), satisfying the required lower bound.
No additional lemma or clarification is needed to verify the claimed result.
⟨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.