Answer: polynomial-time solvable
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateAn optimal mechanism has the following allocation: the interval [0; 1] can be divided into regions where C00() > 0 (a contest) or when C00() = 0 (a lottery). Goods 16There is a unique ex-ante optimal allocation if the set f 2 [0; 1]j d v() g() 0 R 1 g(^)d^ =d = 0g has measure 0. 17Virtual surplus is the surplus generated by giving the object to someone of type taking into account the full cost this has on incentives. Namely, the cost to designer of keeping the other (higher) types truthtelling rather than pretending to be a lower type. 18We may have lim%1 z() > or < z (1).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many complete applicant types \(T\), rational masses \(\mu_t\) summing to \(1\), values \(v_t\), signal-cost coefficients \(g_t\), and per-capita supply \(\alpha\), choose report-contingent allocation probabilities \(q_r\in[0,1]\) and wasteful signal efforts \(e_r\geq 0\). Maximize \(\sum_{t\in T}\mu_t(v_tq_t-g_te_t)\), subject to incentive compatibility \(v_tq_t-g_te_t\geq v_tq_r-g_te_r\) for all \(t,r\), individual rationality \(v_tq_t-g_te_t\geq0\), and capacity \(\sum_{t\in T}\mu_tq_t\leq\alpha\); determine an optimal menu and its value.
A society is given by its support: an ordered list \(T=\{1,\ldots,\tau\}\) of privately known applicant types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. There is one homogeneous good category, \(m=1\), and each applicant values at most one unit.
Inputs also include positive binary-rational values \(v_t\), signal-cost coefficients \(g_t\), and supply \(0<\alpha<1\), ordered so that \(v_t/g_t\) is weakly increasing; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
A symmetric direct menu assigns each report \(r\in T\) an allocation probability \(q_r\in[0,1]\) and deterministic effort \(e_r\geq0\); both sequences are weakly increasing in the supplied type order. Effort costs a true type \(t\) exactly \(g_te_r\), is entirely wasted, and yields no payment to the designer. Nonparticipation gives utility zero.
Maximize \(\sum_{t\in T}\mu_t(v_tq_t-g_te_t)\), subject to \(v_tq_t-g_te_t\geq v_tq_r-g_te_r\) for every \(t,r\in T\), \(v_tq_t-g_te_t\geq0\) for every \(t\), and \(\sum_t\mu_tq_t\leq\alpha\). Unused supply may be discarded; truthful reporting need only be weakly optimal.
Can an optimal menu and its exact value be computed in time polynomial in \(m,\tau,L\), or is deciding whether the optimum is at least an input binary-rational threshold \(K\) NP-hard?
For finitely many agents with independently drawn continuous private types, an optimal symmetric mechanism combines contests and uniform lotteries over type regions determined by a convex envelope; this is a structural characterization, without a bit-complexity bound. [Chakravarty–Kaplan](https://mpra.ub.uni-muenchen.de/18481/1/MPRA_paper_18481.pdf).
No result settling the exact finite-support mass problem above was located in the literature search.
The stated finite-support problem is polynomial-time solvable. For \(m=1\), an optimal menu and its exact value can be computed in \(O(\tau^2L^2)\) bit operations using elementary integer arithmetic. Consequently, the threshold decision problem belongs to \(\mathrm P\).
The proof below is self-contained; it does not require the continuous-type characterization in [Chakravarty–Kaplan](https://mpra.ub.uni-muenchen.de/18481/1/MPRA_paper_18481.pdf).
Define \(x_t=v_t/g_t\). By hypothesis, \(0<x_1\leq\cdots\leq x_\tau\). Since \(g_t>0\), dividing type \(t\)'s utility by \(g_t\) preserves its report preferences. Thus incentive compatibility is equivalent to
\(x_tq_t-e_t\geq x_tq_r-e_r\qquad(t,r\in T).\)
Fix any allocation sequence \(0\leq q_1\leq\cdots\leq q_\tau\leq1\). Define its increments by
\(z_1=q_1,\qquad z_i=q_i-q_{i-1}\quad(2\leq i\leq\tau).\)
All increments are nonnegative. Define efforts
\(e_t^*=\sum_{i=2}^{t}x_{i-1}z_i,\)
where an empty sum is zero.
Lemma. The menu \((q,e^*)\) is incentive compatible and individually rational, and its efforts are weakly increasing. Moreover, every feasible menu with allocation \(q\) satisfies \(e_t\geq e_t^*\) for every \(t\).
Proof. For any feasible menu, incentive compatibility of type \(i-1\) against report \(i\) gives
\(e_i-e_{i-1}\geq x_{i-1}(q_i-q_{i-1})=x_{i-1}z_i.\)
Summing these inequalities and using \(e_1\geq0\) proves \(e_t\geq e_t^*\).
To check incentive compatibility of the proposed efforts, first take \(r>t\). Monotonicity of the ratios gives
\(e_r^*-e_t^*=\sum_{i=t+1}^{r}x_{i-1}z_i\geq x_t\sum_{i=t+1}^{r}z_i=x_t(q_r-q_t).\)
Rearranging proves that type \(t\) weakly prefers report \(t\) to report \(r\).
If \(r<t\), the same ordering gives
\(e_t^*-e_r^*=\sum_{i=r+1}^{t}x_{i-1}z_i\leq x_t\sum_{i=r+1}^{t}z_i=x_t(q_t-q_r),\)
which again proves the required incentive inequality.
Individual rationality follows from
\(e_t^*\leq x_t\sum_{i=2}^{t}z_i=x_t(q_t-q_1)\leq x_tq_t.\)
Finally, \(e_i^*-e_{i-1}^*=x_{i-1}z_i\geq0\), so efforts are nonnegative and weakly increasing. This proves the lemma.
Because every coefficient \(\mu_tg_t\) is positive, replacing feasible efforts by \(e^*\) weakly increases the objective. Therefore optimization may be restricted to these least efforts.
Set \(x_0=0\), and define
\(a_i=\sum_{t=i}^{\tau}\mu_t,\qquad c_i=\sum_{t=i}^{\tau}\mu_t(v_t-g_tx_{i-1})\quad(1\leq i\leq\tau).\)
Positive masses imply
\(1=a_1>a_2>\cdots>a_\tau>0.\)
Also \(c_i\geq0\): for \(t\geq i\), monotonicity gives \(v_t-g_tx_{i-1}=g_t(x_t-x_{i-1})\geq0\).
Since \(q_t=\sum_{i=1}^{t}z_i\), exchanging the order of finite summation yields
\(\sum_{t=1}^{\tau}\mu_tq_t=\sum_{i=1}^{\tau}a_iz_i.\)
Using the least-effort formula similarly yields
\(\sum_{t=1}^{\tau}\mu_t(v_tq_t-g_te_t^*)=\sum_{i=1}^{\tau}c_iz_i.\)
Consequently, the original optimum equals the optimum of
\(\displaystyle \max_{z\in P}\sum_{i=1}^{\tau}c_iz_i,\)
where
\(\displaystyle P=\left\{z\in\mathbb R^\tau:\ z_i\geq0,\ \sum_{i=1}^{\tau}z_i\leq1,\ \sum_{i=1}^{\tau}a_iz_i\leq\alpha\right\}.\)
Both directions of this equivalence hold:
The set \(P\) is nonempty and compact, so its linear objective attains a maximum.
We first justify that some maximizer is an extreme point of \(P\). Among all maximizers, choose \(z^*\) maximizing \(\sum_i z_i^2\); such a choice exists by compactness. If \(z^*\) were a nontrivial convex combination of distinct feasible points \(u,v\), linearity and optimality would force both \(u,v\) to be maximizers. Strict convexity of the squared norm would then give
\(\sum_i(z_i^*)^2<\max\left\{\sum_i u_i^2,\sum_i v_i^2\right\},\)
a contradiction.
We now classify every extreme point.
Suppose a feasible point has at least three positive coordinates. On those coordinates there is a nonzero vector \(d\) satisfying
\(\sum_i d_i=0,\qquad \sum_i a_id_i=0,\)
because these are two homogeneous linear equations in at least three unknowns. Set all other coordinates of \(d\) to zero. For sufficiently small positive \(\varepsilon\), both \(z+\varepsilon d\) and \(z-\varepsilon d\) remain nonnegative and preserve both resource sums. They are distinct feasible points with midpoint \(z\). Thus \(z\) is not extreme.
If only coordinate \(i\) is positive, its feasible range is
\(0\leq z_i\leq b_i,\qquad b_i=\min\{1,\alpha/a_i\}.\)
A point strictly inside this interval is not extreme. Hence the only possible extreme point with this support has \(z_i=b_i\), with objective
\(W_i=c_i\min\{1,\alpha/a_i\}.\)
Suppose the positive coordinates are \(i<j\). Both resource constraints must be tight.
Indeed, if at most one were tight, a nonzero perturbation supported on \(i,j\) could preserve every tight resource constraint. Sufficiently small perturbations in both directions would preserve positivity and all slack inequalities, contradicting extremality.
Thus
\(z_i+z_j=1,\qquad a_iz_i+a_jz_j=\alpha.\)
Since \(a_i>a_j\), these equations uniquely give
\(z_i=\frac{\alpha-a_j}{a_i-a_j},\qquad z_j=\frac{a_i-\alpha}{a_i-a_j}.\)
These weights are nonnegative precisely when \(a_i\geq\alpha\geq a_j\). Their objective is
\(W_{ij}=\frac{c_i(\alpha-a_j)+c_j(a_i-\alpha)}{a_i-a_j}.\)
Equality at either endpoint gives a feasible candidate already covered by the one-coordinate case; allowing these duplicates simplifies enumeration.
Every extreme point is covered by the zero vector, a one-coordinate candidate, or a two-coordinate candidate. Conversely, every listed candidate is feasible. Therefore
\(\displaystyle \mathrm{OPT}=\max\left(\{0\}\cup\{W_i:1\leq i\leq\tau\}\cup\{W_{ij}:1\leq i<j\leq\tau,\ a_i\geq\alpha\geq a_j\}\right).\)
There are \(O(\tau^2)\) candidates. Retaining a maximizing candidate gives an optimal \(z\), and the formulas in Section 1 recover an optimal menu. In particular, an optimum exists with at most two positive allocation increments.
It remains to verify that the enumeration is polynomial in bit complexity, rather than merely in arithmetic operations.
Write the rational inputs as binary-encoded integer numerator-denominator pairs. Let \(D\) be the product of all input denominators. Its binary length is \(O(L)\), because the sum of their binary lengths is bounded by the total input length.
Define the tail sums
\(V_i=\sum_{t=i}^{\tau}\mu_tv_t,\qquad G_i=\sum_{t=i}^{\tau}\mu_tg_t.\)
Each denominator occurring in a term \(\mu_tv_t\) or \(\mu_tg_t\) divides \(D\): \(D\) contains the denominators of both relevant input entries. Thus all \(a_i,V_i,G_i\), and \(\alpha\) can be represented over the common denominator \(D\).
Their numerators have \(O(L)\) bits. For example,
\(0<V_i\leq\max_t v_t,\qquad 0<G_i\leq\max_t g_t,\qquad 0<a_i\leq1,\)
and both \(D\) and each input value have \(O(L)\)-bit representations.
The ratios \(x_i=v_i/g_i\) also have \(O(L)\)-bit numerators and denominators. Computing
\(c_i=V_i-x_{i-1}G_i\)
therefore uses only a constant number of operations on \(O(L)\)-bit integers per index.
For the candidate weights, write \(a_i=A_i/D\) and \(\alpha=A_\alpha/D\). Then
\(\alpha/a_i=A_\alpha/A_i,\)
and the pair weights become
\(\frac{A_\alpha-A_j}{A_i-A_j},\qquad \frac{A_i-A_\alpha}{A_i-A_j}.\)
All these integers have \(O(L)\) bits, and the pair denominator is positive because \(a_i>a_j\). Each candidate objective combines at most two coefficients \(c_i\), so it too has an \(O(L)\)-bit rational representation. Exact comparisons use cross-multiplication of \(O(L)\)-bit integers.
Computing \(D\) and all tail sums takes \(O(\tau)\) arithmetic operations. Enumeration takes \(O(\tau^2)\) such operations. Schoolbook multiplication and long division on \(O(L)\)-bit integers take \(O(L^2)\) bit operations, giving total time
\(O(\tau^2L^2)\qquad\text{for }m=1.\)
Reconstructing the menu takes \(O(\tau)\) further arithmetic operations. Because the selected \(z\) has at most two nonzero coordinates, each output \(q_t\) and \(e_t^*\) combines at most two rational terms and has \(O(L)\)-bit representation.
Finally, comparing the exact optimum with the input threshold \(K\) is an exact rational comparison, polynomial in the total input length including \(K\). Thus the decision problem is in \(\mathrm P\), and NP-hardness under polynomial-time reductions would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated finite-support problem. Its optimization reduction, candidate enumeration, and exact-arithmetic bound are correct. I found no major or minor issues.
Dividing each type’s utility by its positive coefficient \(g_t\) preserves both incentive compatibility and individual rationality.
For any feasible menu, the incentive constraint of type \(i-1\) against report \(i\) gives
\[
e_i-e_{i-1}\geq x_{i-1}z_i.
\]
Summing and using \(e_1\geq0\) correctly establishes the coordinatewise lower bound \(e_t\geq e_t^*\).
The proposed efforts satisfy all incentive constraints:
The individual-rationality bound and effort monotonicity also follow as written. These arguments remain valid when adjacent ratios are equal and when allocation increments vanish.
Because every objective coefficient multiplying effort is negative, replacing feasible efforts by their coordinatewise minimum weakly increases welfare. Restricting optimization to \(e^*\) is therefore justified.
The allocation increments are nonnegative, and allocation monotonicity and bounds are exactly represented by
\[
z_i\geq0,\qquad \sum_i z_i\leq1.
\]
The supply constraint becomes \(\sum_i a_i z_i\leq\alpha\) by the stated finite-sum rearrangement.
The objective coefficients are correct: increment \(z_i\) contributes allocation value to every type \(t\geq i\), and, for \(i\geq2\), contributes effort \(x_{i-1}z_i\) to those same types. Setting \(x_0=0\) correctly handles \(i=1\).
Positive masses imply strictly decreasing positive tail masses. The claimed nonnegativity of the coefficients \(c_i\) follows from the ordered ratios, including the separately defined value \(x_0=0\).
Both directions of the optimization equivalence are established. An arbitrary feasible menu can have a smaller objective than its least-effort replacement; the proof correctly accounts for this rather than asserting objective preservation.
The existence argument is valid: the maximizer set is compact, and maximizing the strictly convex squared norm over that set yields an extreme point of the feasible polytope.
The support classification is correct:
When both resource constraints are tight, the displayed weights solve the two equations correctly. Their nonnegativity condition and objective formula are also correct. The strict inequality \(a_i>a_j\) guarantees a positive denominator.
The enumeration covers every extreme point, and every enumerated candidate is feasible. This suffices for the optimum formula; the proof does not need to establish separately that every listed candidate is extreme.
The common-denominator construction is valid. The product \(D\) includes denominators with their input-entry multiplicities, so each product denominator arising in \(\mu_t v_t\) or \(\mu_t g_t\) divides \(D\). Its bit length is \(O(L)\).
The bounds on tail sums correctly imply \(O(L)\)-bit numerators over \(D\). The ratios \(x_i\), coefficients \(c_i\), candidate weights, and candidate objectives likewise have \(O(L)\)-bit representations: each uses only a bounded number of products of integers of that size.
There are \(O(\tau)\) preprocessing operations and \(O(\tau^2)\) candidate-evaluation and comparison operations. Schoolbook integer arithmetic therefore supports the claimed \(O(\tau^2L^2)\) bit-operation bound for the stipulated \(m=1\).
Reconstruction also satisfies the stated bound because the selected candidate has at most two nonzero increments. Comparing against \(K\) is polynomial in the total input length including that threshold.
The argument covers \(\tau=1\), equal ratios, zero objective coefficients, endpoint pair weights, and discarded supply. Nonparticipation and weak truthfulness are handled explicitly.
The result concerns the finite-support problem in the task. It neither relies on nor establishes a bit-complexity result for continuously distributed private types. No additional clarification is needed to verify the submitted claim.
⟨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.