| paper | d4-journals-geb-2021-0031 |
| 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 ($\mathrm{P}$) under the stated requirement of finite interim expectations: answer yes exactly when $q\le S_{\mathrm{eff}}$. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given unit-mass buyer and seller populations with types \((v,k)\) and \((c,\ell)\), respectively, where values and costs lie in \([0,1]\), levels are independent of values, and each side has positive mass at every level from \(L1\) through \(L_K\), randomly match buyers and sellers for independent encounters. For rational polynomial value densities \(f\) and \(g\) satisfying Theorem 4’s generic conditions and rational level proportions, find a common budget-balanced direct mechanism \((p,x)\) maximizing aggregate surplus per encounter, subject to level-\(k\) incentive compatibility and interim individual rationality for every populated level; in particular, compute an optimal posted price \(\pi\), or an \(\varepsilon\)-optimal one.
A mass distribution over buyer types \((v,k)\) and seller types \((c,\ell)\), with independent matching. The decision variables are the trade probability \(p(v,c)\) and buyer-to-seller payment \(x(v,c)\). Maximize \(\int_0^1\int_0^1 (v-c)p(v,c)f(v)g(c)\,dc\,dv\) subject to the paper’s level-\(k\) incentive and participation constraints. Generically, the mechanism is a deterministic posted price \(\pi\).
Independent encounters merely multiply the per-encounter objective, so population mass adds no computational structure; the proponent acknowledges this limitation, which bounds the mirror’s novelty but does not defeat the analogue.
fatal: False
The mirror covers Theorem 4’s generic optimal-mechanism result for unobservable levels. It leaves the paper’s double-auction analyses, observable-level results, and non-incentive-compatible mechanism cases aside.
The strongest honest case rests on Theorem 4, proved in this paper. Crawford proves no named polynomial-time, NP-hardness, or parameterized-complexity result. Theorem 4 is instead a structural optimization result: it identifies the form of an optimal mechanism for a continuous optimization problem. So the mirror below is an algorithmic question suggested by that structure, not a complexity classification the paper already establishes.
Theorem 4 assumes that traders’ levels are unobservable and that each side’s population includes every level from \(L1\) through some \(K>1\). It assumes well-behaved value densities \(f,g\), with neither density equal to \(1\) almost everywhere and no \(x\) for which both \(F(x)=x\) and \(G(x)=x\). Subject to level-\(k\) incentive compatibility and interim individual rationality, and apart from certain further nongeneric density cases, the mechanism maximizing traders’ total expected surplus is equivalent to a deterministic posted-price mechanism. Its price \(\pi\) is optimal and satisfies
\[
\frac{f(\pi)}{g(\pi)}
=
\frac{\int_{\pi}^{1}(v-\pi)f(v)\,dv}
{\int_{0}^{\pi}(\pi-c)g(c)\,dc}.
\]
The theorem is proved here; posted-price mechanisms themselves have prior literature. This is my lead anchor because it reduces a search over direct mechanisms to a one-parameter choice in the generic case.
A plausible population regime is a large platform handling \(N\) independent buyer–seller encounters in a period. Each encounter trades at most one indivisible object. Buyers have values \(v\in[0,1]\), sellers costs \(c\in[0,1]\), and each trader has a level \(k\) of strategic thinking. Types are role, value or cost, and level; levels are not observed by the platform, and levels are independent of values as in the paper. The buyer and seller populations have unit-mass measures \(\mu_B(dv,k)=\alpha_k f(v)\,dv\) and \(\mu_S(dc,\ell)=\beta_\ell g(c)\,dc\), with positive mass at each level from \(L1\) through \(L_K\). A matched pair is drawn independently from the two populations. Here mass means the fraction of the platform’s buyers or sellers with those characteristics, rather than uncertainty about which two named traders happen to be present.
The mirror problem is Continuum Level-\(k\) Bilateral Trade Optimization. Given those population measures and a common direct mechanism, choose a trade rule \(p(v,c)\in[0,1]\) and expected payment \(x(v,c)\) from buyer to seller. Require budget balance and level-\(k\) incentive compatibility and interim individual rationality for every populated level: truthful reporting must maximize each trader’s expected utility under that level’s beliefs, and truthful participation must give nonnegative interim utility. Maximize aggregate surplus per encounter,
\[
\int_0^1\int_0^1 (v-c)p(v,c)f(v)g(c)\,dc\,dv.
\]
A solution is a feasible mechanism attaining the maximum; an approximation version can ask for a feasible mechanism within \(\varepsilon\) of it. For the posted-price solution, \(p(v,c)=1\) exactly when \(c\leq \pi\leq v\), and \(x(v,c)=\pi p(v,c)\). With rational polynomial densities as input, the generic posted-price case becomes a one-dimensional optimization problem.
I would expect that generic subproblem to be Class A: Theorem 4 supplies the structural reduction, after which the price can be found by optimizing a scalar objective. The paper does not prove a polynomial bit-complexity bound, and its unspecified further nongeneric exceptions mean the theorem alone does not classify every input. A prover could also ask whether a finite-support approximation preserves the optimum, how the price’s bit complexity depends on the density representation, and what changes when levels are observable.
The authors could plausibly recognize this as their bilateral-trade problem in a large platform: every encounter uses the same environment and mechanism, while the objective is the mass-weighted sum of its surplus. The mirror covers Theorem 4’s unobservable-level optimization result, not the paper’s analyses of the double auction or its other mechanism-design cases.
The weak point is that this population has a continuous value coordinate, so its type space is uncountable; it does not fit the programme’s usual finite-support \(\tau\) input. Also, repeating independent encounters largely scales the paper’s expected-surplus objective, and the paper already models values with continuous densities. That makes this a credible large-population interpretation of Theorem 4, but a weaker claim that population continuization unlocks a genuinely new computational problem.
Theorem 4 is the right anchor, but its structure makes the proposed population mirror look computationally thin. It characterizes a mechanism for one buyer and one seller whose private values are drawn from densities \(f\) and \(g\). Those densities describe uncertainty about the two traders’ values; they are not masses of interchangeable traders. The distinction matters here because the theorem’s posted price already depends on those densities, and the paper already performs the corresponding integration. Turning each encounter into a large population does not create that optimization problem.
Suppose a platform runs \(N\) independent buyer–seller encounters under the same mechanism. Its expected aggregate surplus is just \(N\) times the paper’s per-encounter objective. The incentive constraints remain the same for each buyer and seller, and Theorem 4’s price condition still depends on \(f\) and \(g\). In the proposed version, the level frequencies add no further structure: with level-\(k\) incentive compatibility required for every populated level, the theorem’s price condition does not depend on those frequencies. Grouping repeated agents by value and level therefore changes the accounting, but not the optimization the theorem solves.
That remains true if values are discretized into finitely many rational types to fit the programme’s usual input model. The multiplicities of those types determine their proportions, but the encounter objective and constraints depend on the resulting distributions. The computational input that could matter is the support size or representation of \(f\) and \(g\), not the number of agents represented by each type. Searching for an exact or approximate optimal price might be a sensible algorithmic question once the density representation and complexity measure are specified; it would be a question about computing the paper’s existing continuous-type solution, not a computational gain from continuizing the population.
A stronger population variant could couple encounters through scarce shared inventory, a platform budget, or a matching decision. Then mass proportions might affect which trades are feasible, and the problem could acquire real computational structure. But that is a many-trader market design problem, not a population version of Theorem 4’s bilateral mechanism: the shared constraint or matching rule becomes a new primitive, and the paper’s price characterization no longer supplies the optimization problem. Such an extension might be worth studying on its own. The paper gives little reason to count it as a continuous mirror of this result.
There is a limit to this negative case: the paper has no numbered complexity theorem, but Theorem 4 does identify a computationally meaningful optimization problem, so the absence of a complexity classification alone does not rule out a mirror. The sharper objection is that the proposed large-platform scenario either repeats the same two-agent problem \(N\) times, leaving the solution unchanged, or introduces market-wide coupling and becomes a different problem. The case against this anchor is strongest on that boundary; it cannot establish that no broader market-design project could be worthwhile.
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.