Answer: Polynomial-time solvable by an exact rational linear program.
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe optimal objective value for CM (DM) equals α∗ C (α∗ D). For DM, an optimal allocation mechanism is Mj, where j is the (only) index that satisfies p∗ D,j = 1. For CM, an optimal allocation mechanism is the mixture over M1, M2, . . . , Mt where Mj is chosen with probability p∗ C,j. An optimal redistribution function RC can be obtained from the R∗ C,x as follows: for any V and any i, RC(V∼i) = R∗ C,0V∼i(1) + n−1 X x=1 (R∗ C,x −R∗ C,x−1)V∼i(x) Here, V∼i(x) is the xth-highest bid among bids other than i’s own bid.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite rational value set \(V=\{v_1>\cdots>v_\tau\ge 0\}\), a unit-mass society with distribution \(\mu\in\Delta(V)\), per-capita supply \(\rho\in(0,1)\), a finite menu of symmetric strategyproof and individually rational unit-demand rules with rational per-capita rank functionals \(U_j(q)\) and \(P_j(q)\), and a finite rational basis of report-independent rebate functionals \(B_k(q)\), choose a lottery \(\lambda\in\Delta_t\), a nonnegative rebate \(R(q)=\sum_k\theta_k B_k(q)\), and the largest \(\alpha\). Require, for every \(\mu\in\Delta(V)\), that \(R(q_\mu)\ge 0\), \(\sum_j\lambda_jP_j(q_\mu)\ge R(q_\mu)\), and \(\sum_j\lambda_j(U_j(q_\mu)-P_j(q_\mu))+R(q_\mu)\ge\alpha W_\rho(\mu)\), where \(q_\mu\) is the nonincreasing value quantile and \(W_\rho(\mu)=\int_0^\rho q_\mu(s)\,ds\). Return the optimal lottery, rebate, and guaranteed ratio.
Fix a rational value alphabet \(V=\{v_1>\cdots>v_m\ge0\}\) with \(v_1>0\), and rational supply \(0<\rho<1\). Agents are nonatomic, have unit demand and quasilinear utilities, and total mass is one.
A society is given by its support: the list of its \(\tau\) positive-mass types and their binary rational masses, summing to one; \(\tau\) is the support size, not the number of possible types. All rational societies supported in \(V\), including proper subsets, are admissible.
Let \(q_\mu\) be the right-continuous nonincreasing value quantile on \([0,1)\), with \(q_\mu(1)\) equal to the smallest positive-mass type, and let \(W_\rho(\mu)=\int_0^\rho q_\mu(s)\,ds\).
The input contains \(t\ge1\) promised symmetric, strategyproof, individually rational allocation rules, feasible for supply \(\rho\), with zero payment for a zero report; ties are treated symmetrically. Their expected per-capita allocated value and revenue are \(U_j(q)\) and \(P_j(q)\).
Each input functional \(F\), including the \(b\) rebate basis functionals \(B_k\), is explicitly encoded as \(F(q)=\int_0^1 f(s)q(s)\,ds+\sum_\ell c_\ell q(r_\ell)\), where \(f\) is a step function with rational breakpoints and signed rational heights, and \(c_\ell,r_\ell\) are rational with \(r_\ell\in[0,1]\).
Choose \(\lambda\in\Delta_t\), unrestricted coefficients \(\theta\in\mathbb R^b\), and \(R(q)=\sum_{k=1}^b\theta_kB_k(q)\). Every agent receives the same rebate \(R(q_\mu)\); changing one agent’s report leaves the population distribution unchanged, so this rebate is report-independent.
Maximize \(\alpha\in\mathbb R\), subject, for every admissible \(\mu\), to \(R(q_\mu)\ge0\), \(\sum_j\lambda_jP_j(q_\mu)\ge R(q_\mu)\), and \(\sum_j\lambda_j(U_j(q_\mu)-P_j(q_\mu))+R(q_\mu)\ge\alpha W_\rho(\mu)\). Constraints use expectations over mechanism randomness. Return an optimal lottery, rebate coefficients, and ratio.
Is this optimization problem solvable in polynomial time, or is its decision version asking whether a feasible ratio \(\alpha\ge a\) exists, for a binary rational threshold \(a\), NP-hard? State running times in \(m,\tau,t,b\) and total input bit length \(L\), uniformly over admissible supports \(\tau\le m\).
For finite societies, optimal redistribution and a lottery over a specified finite menu of linear allocation mechanisms admit an exact finite LP characterization; choosing a single menu mechanism admits a mixed integer formulation. [Guo–Conitzer](https://users.cs.duke.edu/~conitzer/inefficientEC08.pdf)
The expanded treatment also gives an exact LP characterization when optimizing over all linear unit-demand allocation mechanisms. [Guo–Conitzer, expanded treatment](https://users.cs.duke.edu/~conitzer/betterAIJ14.pdf) No result settling the precise nonatomic problem above was located in the literature search.
The optimization problem is solvable in polynomial time by an exact rational linear program. Its decision version belongs to \(\mathrm P\).
The key fact is that every admissible quantile is a convex combination of quantiles supported on the two extreme values, \(\{v_1,v_m\}\). For these two-value societies, the encoded functionals are piecewise affine in a single mass parameter. Point evaluations require one-sided limiting constraints, but only polynomially many.
The argument below treats the stated nonatomic model directly. For the related finite-agent LP characterizations, see [Guo–Conitzer, expanded treatment](https://users.cs.duke.edu/~conitzer/betterAIJ14.pdf).
First assume \(m\ge2\), and write \(h=v_1\), \(\ell=v_m\), and \(\delta=h-\ell>0\).
For rational \(x\in[0,1]\), let \(q_x\) be the quantile of the society with mass \(x\) at \(h\) and mass \(1-x\) at \(\ell\), omitting zero-mass types. Thus, for \(s<1\),
\(q_x(s)=\ell+\delta\,\mathbf 1_{\{s<x\}},\)
and the stipulated endpoint convention gives
\(q_x(1)=\ell+\delta\,\mathbf 1_{\{x=1\}}.\)
In particular, \(q_0\) and \(q_1\) are the constant-low and constant-high quantiles.
Lemma. Every admissible \(q_\mu\) is a convex combination of admissible quantiles of this form, with equality at every point of \([0,1]\).
Proof. Write \(p_i=\mu(\{v_i\})\), allowing \(p_i=0\), and put
\(S_i=\sum_{k=1}^{i}p_k,\qquad \Delta_i=v_i-v_{i+1}\quad(1\le i<m).\)
For \(s<1\), right continuity gives the identity
\(q_\mu(s)=v_m+\sum_{i=1}^{m-1}\Delta_i\mathbf 1_{\{s<S_i\}}.\)
Indeed, if \(q_\mu(s)=v_j\), then the indicators are zero for \(i<j\) and one for \(i\ge j\); the sum telescopes to \(v_j-v_m\).
This identity also respects the separately defined value at \(s=1\). If \(v_j\) is the smallest positive-mass type, then \(S_i=1\) exactly for \(i\ge j\). Consequently,
\(q_\mu(1)=v_m+\sum_{i=1}^{m-1}\Delta_i\mathbf 1_{\{S_i=1\}}.\)
Since \(\sum_{i=1}^{m-1}\Delta_i=h-\ell=\delta\), it follows pointwise, including at \(1\), that
\(q_\mu=\sum_{i=1}^{m-1}\frac{\Delta_i}{\delta}\,q_{S_i}.\)
The coefficients are positive and sum to one. Each \(S_i\) is rational, so every \(q_{S_i}\) is admissible. This proves the lemma.
For fixed \((\lambda,\theta,\alpha)\), each required inequality is of the form \(H(q)\ge0\), where \(H\) is a linear functional:
The lemma implies
\(H(q_\mu)=\sum_{i=1}^{m-1}\frac{\Delta_i}{\delta}H(q_{S_i}).\)
Therefore, an inequality holds for every admissible society if and only if it holds for every rational two-value society \(q_x\).
This also proves that any violation has an admissible witness with support size at most two. The reduction uses the premise that proper subsets of the alphabet are admissible.
If \(m=1\), there is only the constant quantile \(q(s)=v_1\), and the universal constraints already reduce to three inequalities.
Consider an encoded functional
\(F(q)=\int_0^1 f(s)q(s)\,ds+\sum_\nu c_\nu q(r_\nu).\)
Define
\(A_F=\int_0^1 f(s)\,ds+\sum_\nu c_\nu,\qquad I_F(x)=\int_0^x f(s)\,ds.\)
Also define
\(C_F^{<}(x)=\sum_{\nu:r_\nu<x}c_\nu,\qquad C_F^{\le}(x)=\sum_{\nu:r_\nu\le x}c_\nu.\)
For \(0\le x<1\), direct substitution gives
\(F(q_x)=\ell A_F+\delta\bigl(I_F(x)+C_F^{<}(x)\bigr).\)
At \(x=1\), the endpoint convention instead gives
\(F(q_1)=hA_F.\)
These formulas allow signed heights and signed point coefficients.
Let
\(0=z_0<z_1<\cdots<z_{K-1}=1\)
be the common grid containing:
Including \(\rho\) accounts for \(W_\rho\), whose kernel is \(\mathbf 1_{[0,\rho)}\).
For every functional \(F\), construct the following coefficient rows:
| Row label | Coefficient \(F_e\) |
|---|---|
| Actual value at \(z<1\) | \(\ell A_F+\delta\bigl(I_F(z)+C_F^{<}(z)\bigr)\) |
| Actual value at \(1\) | \(hA_F\) |
| Right limit at \(z<1\) | \(\ell A_F+\delta\bigl(I_F(z)+C_F^{\le}(z)\bigr)\) |
| Left limit at \(1\) | \(\ell A_F+\delta\bigl(I_F(1)+C_F^{<}(1)\bigr)\) |
There are \(K\) actual rows, \(K-1\) right-limit rows, and one left-limit row: \(2K\) rows in total.
For welfare,
\(W_\rho(q_x)=\ell\rho+\delta\min\{x,\rho\}.\)
Its one-sided limits agree with this continuous expression.
Lemma. For any fixed linear combination \(H\) of the encoded functionals and \(W_\rho\), the condition \(H(q_x)\ge0\) for every rational \(x\in[0,1]\) is equivalent to nonnegativity of all \(2K\) constructed rows.
Proof.
Suppose first that \(H(q_x)\ge0\) for every rational \(x\). Every grid point is rational, so all actual rows are nonnegative. Each one-sided row is the limit along a rational sequence of nonnegative values, and is therefore nonnegative as well.
Conversely, suppose all constructed rows are nonnegative. On each open interval \((z_i,z_{i+1})\), every integral \(I_F(x)\) is affine in \(x\), and every point-evaluation contribution is constant. Thus \(H(q_x)\) is affine there.
Its lower-end limit is the right-limit row at \(z_i\). Its upper-end limit is the actual row at \(z_{i+1}\) when \(z_{i+1}<1\), because the strict inequality \(r_\nu<x\) excludes terms at that endpoint both in the actual value and in the left limit. When \(z_{i+1}=1\), its upper-end limit is the separately included left-limit row at \(1\).
An affine function between two nonnegative endpoint limits is nonnegative throughout the interval. The actual rows cover the grid points themselves. Hence \(H(q_x)\ge0\) for every rational \(x\).
The limiting rows need not represent admissible societies themselves. Their necessity follows from rational admissible societies approaching them; their sufficiency follows from the affine interpolation just proved.
Let \(E\) be the set of these \(2K\) row labels. For each \(e\in E\), write the constructed coefficients as \(U_{j,e},P_{j,e},B_{k,e},W_e\).
Use variables \(\lambda_1,\ldots,\lambda_t,\theta_1,\ldots,\theta_b,\alpha\), and solve:
Maximize \(\alpha\), subject to
\(\lambda_j\ge0\quad(1\le j\le t),\qquad \sum_{j=1}^t\lambda_j=1,\)
and, for every \(e\in E\),
\(\sum_{k=1}^b\theta_kB_{k,e}\ge0,\)
\(\sum_{j=1}^t\lambda_jP_{j,e}-\sum_{k=1}^b\theta_kB_{k,e}\ge0,\)
\(\sum_{j=1}^t\lambda_j(U_{j,e}-P_{j,e})+\sum_{k=1}^b\theta_kB_{k,e}-\alpha W_e\ge0.\)
The variables \(\theta_k\) are unrestricted, as required.
The first lemma reduces the universal constraints to rational two-value societies. The second lemma reduces those constraints to these finite rows. Thus this LP has exactly the feasible set of the original optimization problem.
For the decision problem, add \(\alpha\ge a\) and test feasibility.
Under the standard strategyproofness promise on the nonnegative report domain, the zero-payment normalization implies nonnegative expected payments. To see this, fix a population distribution and consider a zero-valued agent. Reporting zero gives utility zero; reporting any value with expected payment \(p\) gives utility \(-p\). Strategyproofness therefore implies \(p\ge0\).
Individual rationality also gives \(U_j(q)-P_j(q)\ge0\). Consequently, choosing any one menu rule, setting \(\theta=0\), and taking \(\alpha=0\) is feasible.
Every feasible ratio is bounded above by one. Indeed, consider the admissible constant-high society \(q_1\). Supply feasibility gives
\(U_j(q_1)\le\rho v_1=W_\rho(q_1).\)
The budget constraint gives \(R(q_1)\le\sum_j\lambda_jP_j(q_1)\). Combining this with the ratio constraint yields
\(\alpha\rho v_1\le\sum_j\lambda_j(U_j(q_1)-P_j(q_1))+R(q_1)\le\sum_j\lambda_jU_j(q_1)\le\rho v_1.\)
Because \(\rho v_1>0\), this proves \(\alpha\le1\).
All LP coefficients are rational. The standard exact rational linear-programming theorem states that a feasible rational LP with objective bounded above attains a rational optimum, and that an optimal solution can be found in time polynomial in its binary encoding length. Its hypotheses hold here. Unrestricted, possibly unbounded rebate coefficients do not prevent attainment of the bounded objective.
The resulting \((\lambda^*,\theta^*,\alpha^*)\) therefore supplies the requested optimal lottery, rebate coefficients, and ratio.
Let \(N\) be the total number of encoded step-function records and point-evaluation terms, and put \(D=2t+b+1\), counting \(U_j,P_j,B_k,W_\rho\). Then \(K\le N+3\).
For \(m\ge2\), the LP has:
Sorting the grid and constructing all coefficients by prefix integration and summation takes
\(O\bigl(m+N\log N+DK\bigr)\)
rational arithmetic operations.
Let \(L\) include the binary encodings of the alphabet, supply, functionals, and decision threshold when applicable. Each constructed coefficient has polynomial bit length; a conservative bound is \(O(L^2)\). Hence the LP encoding length is \(O\bigl(K(t+b+1)L^2\bigr)\), up to standard indexing overhead.
The complete algorithm therefore runs in
\(\operatorname{poly}(m,t,b,L)\)
bit operations. Its running time is independent of any particular society’s support size \(\tau\), and is uniform over all admissible \(\tau\le m\). It enumerates neither supports nor mass vectors. For \(m=1\), a single coefficient row suffices.
⟨structured verdict parsed — rendered above⟩
The polynomial-time reduction is sound. The convex-combination identity respects the quantile’s endpoint convention, and the finite LP correctly handles discontinuities caused by point evaluations. There is one minor clarification concerning the domain of the strategyproofness promise used to establish feasibility.
For \(m\ge2\), the definitions \(h=v_1\), \(\ell=v_m\), and \(\delta=h-\ell>0\) are valid.
The formulas for \(q_x\) correctly handle all cases:
The decomposition
\[
q_\mu=\sum_{i=1}^{m-1}\frac{\Delta_i}{\delta}q_{S_i}
\]
is correct pointwise. Allowing zero masses causes repeated cumulative masses but does not invalidate the telescoping identity. At \(1\), the indices satisfying \(S_i=1\) give exactly the difference between the smallest positive-mass value and \(v_m\).
The coefficients are positive and sum to one. Every \(S_i\) is rational, and the associated society is admissible because proper subsets, including singleton supports, are allowed.
For fixed optimization variables, all three constraint expressions are linear in \(q\). Consequently, the decomposition establishes the claimed equivalence between checking all admissible societies and checking all rational extreme-value societies. The assertion that a violation has a witness of support size at most two also follows.
The separate treatment of \(m=1\) is correct.
No issue found in this reduction.
For \(x<1\), the formula
\[
F(q_x)=\ell A_F+\delta\bigl(I_F(x)+C_F^{<}(x)\bigr)
\]
correctly uses the strict inequality \(r_\nu<x\). In particular, a point evaluation at \(1\) contributes only its baseline value in this range.
At \(x=1\), the quantile is constant, so \(F(q_1)=hA_F\) is correct.
The four row formulas correctly distinguish:
Signed coefficients do not affect these identities.
The welfare formula
\[
W_\rho(q_x)=\ell\rho+\delta\min\{x,\rho\}
\]
is correct, including \(x=0\) and \(x=1\). Including \(\rho\) in the grid makes welfare affine on each open grid interval.
No issue found in the coefficient construction.
Necessity of the limiting rows follows from rational sequences approaching each endpoint from the appropriate side. Such sequences exist because the grid points are rational and consecutive distinct grid points have positive separation.
For sufficiency, every constraint expression is affine on each open grid interval. Its lower endpoint limit is the right-limit row. Its upper endpoint limit is the actual row when the upper endpoint is below \(1\), and the separately included left-limit row when it is \(1\).
Thus nonnegative endpoint limits imply nonnegativity throughout each interval. Actual rows cover the remaining grid points.
The row count \(K+(K-1)+1=2K\) is correct.
No issue found in this equivalence.
All displayed constraints are linear in \(\lambda,\theta,\alpha\). The simplex constraints and unrestricted rebate coefficients match the task.
The two reductions establish exact equality of the original feasible set and the LP feasible set. Adding \(\alpha\ge a\) correctly expresses the decision problem.
For \(m=1\), evaluating the three universal constraints at the unique constant quantile suffices.
No issue found in the LP formulation.
The individual-rationality argument establishing \(U_j(q)-P_j(q)\ge0\) is correct after aggregating expected truthful utilities.
The payment argument is correct provided strategyproofness applies to a true zero-valued agent at the fixed population distribution. Such an agent obtains utility zero by reporting zero, and utility equal to minus the expected payment by making another report.
Minor issue — strategyproofness domain. The task explicitly mentions a zero report but does not separately define the true-value domain when \(0\notin V\). The prover invokes “the standard strategyproofness promise on the nonnegative report domain,” which supplies the natural intended assumption. However, availability of a zero report alone does not establish the incentive inequality for a true zero-valued agent.
Minimum clarification: Explicitly state that the strategyproofness promise includes true value zero, even when zero is absent from the society alphabet, at each fixed population distribution. Under this interpretation, nonnegative payments and feasibility of \(\theta=0,\alpha=0\) follow as written.
The upper bound \(\alpha\le1\) is otherwise correct. The constant-high society is admissible, its welfare is \(\rho v_1>0\), and supply feasibility and the budget constraint give precisely the displayed inequality.
The rational-LP theorem is stated adequately for this application. Once nonemptiness is established, the rational finite LP has a bounded objective and therefore attains a rational optimum computable in polynomial time. Unboundedness of some rebate coordinates does not invalidate this conclusion.
The variable and constraint counts are correct. Sorting the common grid and constructing coefficient arrays by prefix integration and summation require polynomially many rational arithmetic operations.
The stated conservative polynomial bound on coefficient bit lengths is sufficient. Hence the resulting LP has polynomial binary encoding length, and exact rational LP optimization gives polynomial bit complexity.
The claimed independence from any particular \(\tau\) is justified: the algorithm constructs no support enumeration, and the reduction covers every admissible support uniformly. The output parameters therefore have the asserted polynomial-time computability, subject to the minor domain clarification above.
⟨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.