| paper | d4-conf-wine-2012-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
The named price-of-anarchy results count as mechanism-performance guarantees under the stated test. But a continuum of applicants makes each applicant infinitesimal and changes the paper's atomic Nash and Bayesian equilibria into nonatomic equilibria, so these bounds do not carry over as the same question. The proposed support-sensitive equilibrium-computation problem is a plausible follow-up, but the paper's \(O(n^2\log^2 m)\) algorithm is unnumbered and cannot anchor it.
fails bit b-changes — the continuum limit changes the question
A nonatomic version could revisit Theorem 1's single-round guarantee and Theorem 2 and Corollary 1's multiround guarantees, but would change the equilibrium concept; it does not mirror the unnumbered equilibrium-computation algorithm in Section 3.1.
A plausible high-multiplicity setting is a large funding programme with many applicants drawn from a small number of recurring valuation types. A type is an applicant’s complete concave valuation function and its feasible verified reports; mass is the fraction of applicants of each type. Scale the resource supply with the number of applicants, and HRG ranks type-level requests by reported value per requested resource. Computing equilibria in that population game would be a sensible continuous question.
But the paper has no named computational-complexity result that can anchor it under your rule. Theorem 1, proved here, establishes that HRG’s pure and Bayesian Price of Anarchy are both 2. Theorem 2, also proved here, bounds the \(k\)-round game’s PoA by a formula in the bundle sizes; Corollary 1 gives PoA \(1+1/k\) for bundle ratios \(m_t/m_1=t\). These are named mechanism-performance results, not results placing a problem in P, proving hardness, or giving a named running-time bound. The \(O(n^2\log^2 m)\) algorithm for computing a complete-information Nash equilibrium appears in Section 3.1, but is unnumbered.
So there is a credible population-continuum direction here, but no eligible anchor from which to state the requested per-anchor problem or assign it to the programme’s tractability trichotomy. Calling Theorem 1 or 2 such an anchor would overstate what the paper proves.
The strongest case against is an anchor problem. The funding-programme scenario is sensible: applicants can be grouped by their complete valuation and reporting type, with resources scaled to population. I can’t honestly reject it on high-multiplicity grounds.
But Theorems 1 and 2 and Corollary 1 establish price-of-anarchy bounds, not the complexity of a computational problem. Their continuous analogues would ask about equilibrium efficiency in a continuum game; that may be interesting, but it is not the complexity question ChoCo is meant to chart. The paper’s actual equilibrium-computation result is the \(O(n^2\log^2 m)\) algorithm in Section 3.1. A stronger mirror would ask for a support-sensitive algorithm for a population represented by \(\tau\) types and rational masses. That is a plausible new problem, but the paper gives no numbered theorem, lemma, or corollary about its computational complexity to anchor it. Translating the algorithm is not automatic: it works agent by agent, and the continuum model must replace individual tie-breaking and deviations with mass-level behavior.
So the proponent has a credible research direction, but has not supplied an eligible named result and corresponding continuous computational question. That is the best negative case the paper supports. It does not establish the universal claim that no worthwhile mirror exists: if a well-posed computational follow-up counts as a mirror even without a named complexity result to transfer, the applicant-population setting remains a live candidate.
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.