| paper | d4-journals-geb-2013-0080 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
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 nonatomic population of applicants with finitely many complete value-and-signal-cost types, represented by masses \(\mu_t\). The designer chooses report-contingent allocation probabilities \(q_r\) and wasteful effort \(e_r\), maximizes mass-weighted surplus, and respects incentive, participation, and per-capita capacity constraints.
The LP does not establish that its expected per-capita feasibility constraints reproduce the finite-agent contest feasibility in Proposition 1, or provide a discrete-to-continuous correspondence.
fatal: False
The mirror covers the central optimal allocation problem and its incentive constraints; it does not establish that the contest-versus-lottery regions, the paper’s scarcity result, or its other comparative statics carry over unchanged.
The positive case is narrow. On a strict reading of the requested anchor rule, this paper has no named complexity result: none of its numbered results says that a problem is in P, NP-hard, or has another standard complexity status. The closest anchor is Proposition 1, proved in the paper. It is a structural characterization of an optimum, rather than a complexity theorem.
Proposition 1 says that the type interval \([0,1]\) is divided into regions according to the second derivative of the convex envelope \(C=\operatorname{Conv}(z)\): regions with \(C''(\theta)>0\) use a contest, and regions with \(C''(\theta)=0\) use a lottery. Here \(z(0)=0\), \(z(1)=S_\ell\), and, for \(\theta<1\),
\[
z(\theta)=\int_0^\theta
\left(\frac{v(s)}{g(s)}\right)'
\left(\int_s^1 g(u)\,du\right)ds
+\frac{v(0)}{g(0)}\int_0^1 g(u)\,du.
\]
Goods are allocated sequentially: in a contest region, the highest type gets the good; otherwise it is assigned by lottery among agents whose types lie in that region. The winner is removed and the process repeats. The paper also specifies that when \(\ell_1<0\), \(\theta=1\) is treated as a contest region.
A concrete mirror of that result is High-Multiplicity Wasteful-Signal Allocation. An instance has a finite set \(T=\{1,\ldots,\tau\}\) of privately known types, rational masses \(\mu_t>0\) summing to one, and rational values \(v_t>0\) and signal-cost coefficients \(g_t>0\). Order types so that \(v_t/g_t\) is weakly increasing, echoing the paper’s single-crossing assumption. The designer has per-capita supply \(\alpha\in(0,1)\). Each type reports a type; the anonymous direct mechanism specifies allocation probability \(q_r\in[0,1]\) and expected wasteful signal effort \(e_r\geq0\) for report \(r\). A type-\(t\) agent reporting \(r\) gets utility \(v_tq_r-g_te_r\). The problem is to find a feasible menu maximizing aggregate social surplus:
\[
\max_{q,e}\ \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\quad\forall t,r,\qquad
v_tq_t-g_te_t\geq0\quad\forall t,\qquad
\sum_t\mu_tq_t\leq\alpha.
\]
A solution is an optimal menu and its value. For indivisible goods, \(q_t\) is a winning probability; within a type class, fractional mass can receive the good so each individual still receives an integral bundle.
The regime is a large rationed programme—say, a charitable allocation with many applicants but a small number of standardized value and application-cost classes. The classes are complete types: people in one class have the same value and cost parameters for this problem. Thus \(N\) can be much larger than \(\tau\), while supply scales as \(M=\alpha N\). The mirror keeps the paper’s allocation objective, private information, costly wasteful signals, and incentive constraints; it continuizes the population and scales supply per capita.
For this finite-support mirror, the expected answer is tractable: the stated optimization is a rational LP with \(O(\tau)\) variables and \(O(\tau^2)\) incentive constraints, so it can be solved in time polynomial in \(\tau\) and input bit length \(L\). That complexity claim belongs to the proposed mirror, not to the paper. The mirror’s further questions are whether this LP is the limit or an additive approximation of the corresponding finite-\(N\) mechanism problem, and how its solutions relate to the paper’s convex-envelope characterization as the type grid is refined.
Proposition 1 is my strongest anchor because it characterizes the paper’s central welfare optimization, rather than a side observation about scarcity or weighting. The case is plausible as a population-continuum version of the authors’ problem: their finite agents already face symmetric allocation and costly signaling, and the change to mass preserves those decisions while making supply per-capita. Its weakest point is substantial: the paper studies finite \(N\) agents whose types are independently drawn from a continuous distribution, and Proposition 1 is not a computational-complexity result. The mirror fixes type masses and uses nonatomic feasibility, so a referee could regard the LP as a nearby mean-field mechanism-design problem rather than a complexity result extracted from this paper. It is a credible, narrow mirror; it offers no hardness anchor or claim that discrete hardness dissolves.
The strongest anchor is Proposition 1, but it characterizes an optimum rather than the complexity of a computational problem. Its object is a Bayesian mechanism for \(N\) finite agents: an agent’s chance of winning depends on their report in a contest with the other agents, whose types are independently drawn. The convex envelope of \(z\) describes how that mechanism switches between contests and lotteries. The paper gives no finite input encoding, algorithm, or complexity claim for finding that mechanism. Numerical computation of the envelope would not supply the missing complexity result.
The proposed finite-support menu is coherent, and a large charitable programme with standardized applicant classes is a plausible high-multiplicity setting. But the menu replaces the paper’s finite-agent competition with an atomless screening model. With fixed masses, capacity is \(\sum_t \mu_t q_t\leq\alpha\); a single agent’s deviation does not change those masses. Each type chooses a menu point \((q_r,e_r)\), subject to ordinary incentive constraints. That is a valid finite-type mechanism-design LP, but it does not preserve Proposition 1’s contest against \(N-1\) random rivals or establish a discrete-to-continuous dictionary for the paper’s problem. The LP’s existence alone does not make it a computational result of this paper.
The best attempt to preserve the original model would take \(N\) large with \(M/N\to\alpha\), retaining private types, costly signals, and the random competition. That is a sensible asymptotic question. Yet, with the paper’s analytic \(v\) and \(g\), it remains an asymptotic mechanism-design question, not a complexity problem on binary-encoded societies. Turning it into one requires choosing a representation—such as a rational type grid—and proving how that finite instance relates to the \(N\)-agent model. Those are new modelling and algorithmic contributions, not a computational question already anchored by Proposition 1.
So the negative case is limited. The paper does not rule out a worthwhile continuous allocation model, and the charitable-applicant scenario is credible. The stronger objection is that its central result offers no computational anchor for ChoCo: the proposed mirror either changes the mechanism environment to a standard finite-type LP or becomes an asymptotic analysis without a specified computational input.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.