| paper | d4-conf-wine-2016-0015 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1 establishes a price-of-anarchy bound, and Theorem 3 bounds that ratio in a lower-bound construction; neither is a result about computing an object or the hardness of computing it. A continuous type-mass version of the welfare analysis is conceivable, but it cannot supply the missing computational anchor required for a mirror.
fails bit a — no named computational result to mirror
The proposed type-mass extension concerns Theorem 1's independent-admission welfare guarantee. It leaves Theorem 2's everybody-or-nobody admission case, Theorem 3's XOS lower-bound construction, and the other applications untreated.
The strongest honest positive case is for a continuum version of the paper’s independent-admission welfare analysis. The paper has named game-theoretic results, but no named result that classifies a problem as \(P\), NP-hard, FPT, or similar. Its best anchor for this mirror is therefore a welfare guarantee, not a computational-complexity theorem.
The anchor is Theorem 1, proved in this paper. It says: if bidders have monotone valuations from a class \(\mathcal V\) with correlation gap \(\gamma(\mathcal V)\), then under fully independent availabilities the price of anarchy for oblivious learning in a simultaneous composition of weakly \((\lambda,\mu_1,\mu_2)\)-smooth mechanisms is at most
\[
\gamma(\mathcal V)\frac{\mu_2+\max(1,\mu_1)}{\lambda}.
\]
The proof is here; it uses the smooth-composition result of Syrgkanis and Tardos [25] and correlation-gap machinery from [1].
A plausible regime is a large online marketplace with many advertisers and a few recurring advertiser types. A type specifies the advertiser’s complete valuation for bundles and its per-mechanism admission probabilities. Its mass \(\mu_t\) is the fraction of advertisers of that type. Advertisers bid before learning which mechanisms will be available to them, as in the paper. The number of advertisers can be very large while the support size \(\tau\) remains modest. To keep welfare nonzero per person in the limit, let each mechanism’s supply scale with the population; assignments to individual agents remain integral, while type-level average allocations may be fractional.
The continuous question I would hand to a prover is Continuum Price of Anarchy under Independent Admission. An instance gives rational masses \((\mu_t)_{t\in T}\) summing to one, a finite type set \(T\), each type’s monotone valuation \(v_t\) and independent admission probabilities \(q_{tj}\), and a finite-action family of simultaneous mechanisms with per-capita supplies and uniform smoothness guarantees. A solution is the worst price of anarchy among availability-oblivious coarse-correlated learning outcomes: equivalently, the infimum of expected equilibrium welfare divided by the expected welfare of an allocation planner who observes availability. An outcome can be represented by masses \(\pi_{t,b}\) of type \(t\) using joint bid vector \(b\), with \(\sum_b\pi_{t,b}=\mu_t\); a permitted randomized outcome is a distribution over such profiles satisfying the no-regret inequalities for every type and fixed deviating bid. The question is to compute this worst ratio, or decide whether it is at most a supplied threshold.
I expect the theorem’s uniform welfare-bound question to be tractable in the continuous model: the smoothness and correlation-gap argument should pass from sums over bidders to integrals over type mass, retaining the bound in Theorem 1. That is a Class A style result for certifying a guarantee. It does not, by itself, show that the exact worst ratio or a worst equilibrium can be computed efficiently. Useful follow-ups are whether the finite-population games converge to this model, how the bound depends on \(\tau\), and whether correlated admission admits a comparable type-mass result. I would limit this mirror to Theorem 1’s independent-admission setting.
The paper’s Theorem 3 is a named lower bound: for \(m\) simultaneous discrete first-price auctions with XOS valuations, pure Nash equilibria with oblivious bidding can have price of anarchy \(\Omega((\log m)/(\log\log m))\), even though each auction is weakly \((1/2,1,0)\)-smooth. It is proved here. I would not use it as a population-continuization anchor: its construction has a single bidder, and its growth is in the number of items \(m\), not population multiplicity.
The soft spot in my case is the market model. Scaling supply and making agents infinitesimal changes the standard single-item auction setting, and the continuum’s price-taking behavior may change its equilibria. The mirror is convincing insofar as the authors recognize the core question—how oblivious learning performs under admission and mechanism composition—but less secure as a mirror of their exact finite-bidder auction game.
The strongest objection is that this paper has no named computational result of the kind ChoCo is set up to mirror. Theorem 1 and Theorem 2 prove price-of-anarchy bounds for learning outcomes; Theorem 3 proves a lower bound on that welfare ratio. None classifies the complexity of a computational problem or gives an exact, approximation, or parameterized algorithm for one. Those are substantive results, but their object is welfare analysis.
The marketplace scenario in the proposed mirror is coherent: many advertisers could share complete types that include valuations and admission probabilities. The problem is the proposed computational target. If it is to establish Theorem 1’s uniform welfare bound for type masses, the task is a measure-based extension of a smoothness inequality, with no computational problem or algorithm specified. If it is to compute the exact worst price of anarchy, that is a new problem. Theorem 1 supplies an upper bound, not an exact computation task. To make the new task’s complexity meaningful, one would need to specify how mechanisms and valuations are encoded, what equilibrium distributions over continuum bid profiles are represented, and how aggregate outcomes and welfare are computed. Masses \(\pi_{t,b}\) alone may not capture the cross-agent correlations relevant to a composed auction. Supplying those details could define a worthwhile project, but it would not be a computational mirror of the theorem the proponent named.
The per-capita-supply proposal also requires care. Scaling supply can keep welfare nonzero as the population grows, but it changes a single-item auction into a capacity-scaled market. The smoothness conditions and resulting continuum equilibrium model would need to be established for that market. This is a plausible co-modification; it is not a reason to reject the idea by itself. It does, however, make the proposed transfer less automatic than replacing bidder sums with type masses suggests.
Theorem 3 offers no second population anchor: its lower-bound construction has one bidder and many items. Adding bidder cohorts changes the strategic competition in the construction, so it would create a different result to mirror.
The negative case is strongest as a judgment about ChoCo’s priorities, not as proof that no useful continuum model exists. A nonatomic market with repeated advertiser types could be a sensible research object in mechanism design. The case against is that this paper’s named results do not pose the population-dependent computational questions ChoCo is meant to chart.
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.