| paper | d4-journals-geb-2019-0162 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Theorem 9 states an inefficiency lower bound, not an algorithm, hardness result, or solver formulation; the LP is used in the proof and experiments but is not the named result’s computational claim. Theorem 2 is also a welfare bound, and its pivotal-agent effect does not carry over to literal atomless incentives.
fails bit a — no named computational result to mirror
Theorem 9 is a finite two-agent welfare bound, and its LP use does not make the theorem computational; meanwhile, the \(\eta\)-mass deviation preserves finite-agent incentives rather than their atomless limit.
fatal: True
No cited theorem supplies a computational mirror. The proposed extension concerns Theorem 2’s welfare-loss bound; Theorem 9 remains a two-agent bound over discretized valuation levels, and the other mechanism characterization and performance results are not covered.
Strictly, this paper has no named theorem asserting a complexity classification such as \(\mathrm{P}\), NP-hardness, or FPT. The closest computational anchor is Theorem 9, proved here: for \(n=m=2\), with \(k=3\) discrete valuation levels, the absolute inefficiency of every strategyproof, budget-balanced randomized mechanism is at least \(1/7\). The proof gives a feasible dual solution to the discretized mechanism-design LP. That makes it an optimization anchor under the paper’s LP exception, but not a complexity result.
The strongest support for a population mirror is Theorem 2, also proved here: for every deterministic, strategyproof, budget-balanced, neutral mechanism over the paper’s valuation domain, \(r_n^M(f)\ge 1/n\), and the bound is tight. It is a worst-case welfare result, not a computational one. Its \(1/n\) scaling nevertheless makes a high-multiplicity regime natural to ask about.
My lead mirror would be Continuous Population Budget-Balanced Mechanism Design. The regime is a large public-goods electorate or user community choosing among a small number of projects. A type is a complete bounded valuation vector over the alternatives; \(\mu_t\) is the population share with type \(t\). The plausible high-multiplicity case has many people and a modest number of recurring valuation types.
For a precise version, take two alternatives and a finite list \(T\) of rational valuation vectors. A mechanism assigns each mass distribution \(\mu\in\Delta(T)\) a lottery \(F(\mu)\) and a per-capita payment \(p_t(\mu)\) for each type. Let \(\eta\) be the mass of one individual. Require budget balance, \(\sum_t\mu_t p_t(\mu)=0\), and unilateral strategyproofness: for every \(\mu,t,s\) with \(\mu_t\ge\eta\), reporting \(s\) instead of \(t\) must not improve that individual’s utility when the reported distribution becomes \(\mu-\eta e_t+\eta e_s\). The objective is to minimize
\[ \sup_{\mu\in\Delta(T)} \frac{ \max_{a}\sum_t\mu_t v_t(a) - \sum_t\mu_t\, v_t\!\cdot F(\mu) }{M}. \]
The problem is to compute this optimum and give an optimal mechanism, or decide whether a mechanism with loss at most a supplied rational threshold exists. The mass distribution is the society being continued; lotteries are already part of the paper’s model. The \(\eta\)-mass deviation preserves the individual incentive question while allowing society to be represented by type masses.
I would tentatively expect the fixed-two-alternative, fixed-three-level version to be Class A: its feasibility constraints are linear in allocation and payment variables, and Theorem 9 shows the authors already use LPs to study this objective. The key unanswered algorithmic step is whether the continuum of mass profiles and deviations admits a finite polyhedral description or an efficient separation procedure. Theorem 2 gives a useful benchmark for the deterministic, all-\(n\) side of the same problem: worst-case per-capita inefficiency can fall at rate \(1/n\).
The weak point is that Theorem 9 is for two agents, so it does not itself establish a many-agent regime. Also, the \(\eta\)-mass incentive constraint is a high-multiplicity extension of individual strategyproofness; if the authors insist on a strictly atomless population with literal zero-mass individual deviations, the incentive problem changes substantially and may collapse. And even granting the LP connection, this paper does not itself provide a named computational-complexity result.
The paper has no named computational complexity result to continuize. Theorem 1 characterizes mechanisms; Theorems 2–8 give worst-case inefficiency bounds; and Theorem 9 proves an objective lower bound by exhibiting a dual certificate for a finite LP. That LP has 81 valuation profiles. It is a computational technique in the proof, but the result says nothing about an algorithm’s running time, a scalable separation problem, or a complexity landscape. Here the LP exception does not supply the missing computational anchor.
Theorem 2 is the strongest candidate for a population mirror, and the repeated-valuation public-goods electorate is a credible high-multiplicity regime. The obstacle is more specific: its \(1/n\) loss comes from one pivotal individual. In a literal atomless population, an individual report does not change the aggregate distribution. Choosing the welfare-maximizing alternative from that distribution with zero payments is then efficient, budget balanced, and strategyproof: every individual is indifferent between reports. The paper’s per-capita loss has disappeared. To retain the pivotal effect, the proposed mirror keeps an atom of size \(\eta\). If society is restricted to feasible empirical distributions, that gives a finite-\(n\) grid problem; if arbitrary distributions are allowed, it combines a continuum with finite-sized agents and needs a separate interpretation. Either way, the nontrivial result is about preserving finite-agent incentives, not what the atomless limit reveals. A derivative incentive condition or a rescaled objective might preserve more information, but each changes the question.
Theorem 9 is weaker as an anchor. Its \(k=3\) discretization is of valuation levels, not population mass; the theorem has just two agents. Turning it into a many-agent type-distribution problem would be a new extension, and the atomless incentive issue returns. Its original finite LP does not point to a continuous-population pricing or separation problem.
I would vote against this as a ChoCo mirror: the paper’s main results are economic bounds, and the strongest population limit either makes the objective vanish or retains finite atoms. The negative case is not airtight: optimizing the finite-\(\eta\) mechanism-design LP could be worthwhile in its own right. But that would be a new computational mechanism-design project, not a continuous mirror motivated by a computational result in this paper.
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.