| paper | d4-conf-wine-2013-0010 |
| 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 that some sequential auctions have poor equilibrium welfare; it does not assert or classify the computation of an auction outcome. The cohort-market limit is a concrete and plausible equilibrium-analysis sequel, but it does not supply the missing computational character for the sole anchor.
fails bit a — no named computational result to mirror
The proposed limit extends Theorem 1's welfare analysis to replicated type cohorts. The paper's prose extensions and its item-ordering conjecture are not computational results either.
The strongest positive case is a narrow population-limit sequel to Theorem 1. The theorem, proved in Section 4, says that the price of anarchy of sequential first-price item auctions with additive and unit-demand bidders is \(\Omega(\min\{n,m\})\), and that this lower bound persists when attention is restricted to subgame-perfect equilibria surviving iterated elimination of weakly dominated strategies. It is proved here, not cited from elsewhere.
A plausible mirror is the Type-Mass Sequential-Auction Price of Anarchy. An instance has item categories \(J\), a finite set \(T\) of complete bidder valuation types \(v_t\) (restricted to the paper’s additive and unit-demand valuations), rational type masses \(\mu_t>0\) summing to \(1\), rational per-capita supplies \(q_j\) for \(j\in J\), and a fixed order for selling the item copies. For each sufficiently divisible \(N\), form a replica auction with \(N\mu_t\) bidders of type \(t\) and \(Nq_j\) copies of each category \(j\), sold sequentially by first-price auction. Let \(\mathcal E_N\) be its subgame-perfect equilibria surviving IEWDS, and let \(W_N^*\) be its optimal welfare. The question is to determine
\[
\rho(\mu,q)=\liminf_{N\to\infty}\ \inf_{E\in\mathcal E_N}\frac{W(E)}{W_N^*}.
\]
A solution would give the value of \(\rho\), with matching asymptotic bounds and, where applicable, a sequence of equilibria witnessing the bound. This keeps the paper’s auction, strategic solution concept, and welfare objective; the society is now described by type shares, and item supply scales with population.
One credible regime is a large marketplace selling standardized lots to many buyers whose complete valuation schedules fall into a relatively small number of recurring cohorts. Then \(N\) can greatly exceed \(|T|\), while the number of item copies grows with the market. The paper’s authors could plausibly recognize this as a population-scale version of their question. It generates useful follow-ups: does the bad welfare ratio persist under replication, can it be bounded in terms of item categories and type count, and does taking the population limit preserve the IEWDS equilibrium structure?
The serious weakness is that Theorem 1 is not a computational-complexity result: it bounds equilibrium welfare loss; it does not establish that a problem is in P, NP-hard, FPT, or similar. The paper gives no numbered result of that kind. Its valuation-class extensions are described in prose, and Conjecture 1 is an open conjecture about item ordering, not a complexity classification. So the proposed mass problem is a plausible research sequel, but it cannot serve as a qualifying computational-complexity anchor for this task.
There is a second limitation: the lower-bound construction uses \(k\) specialized unit-demand bidders, so its number of distinct bidder types grows with \(k\). The paper does not show that the construction’s inefficiency survives when many bidders share each type. That is the central question the population-limit problem would test. I would leave its complexity class open; the theorem supplies no basis for claiming tractability or hardness transfer.
Theorem 1 is the sole anchor, and it establishes an equilibrium-efficiency bound, not the complexity of a computational problem. Its claim is that some sequential auctions have price of anarchy \(\Omega(\min\{n,m\})\), even among equilibria surviving IEWDS. The paper constructs a bad equilibrium; it does not ask for an algorithm to find one, classify the complexity of computing one, or optimize an allocation under a specified computational objective. The authors explicitly avoid solving the equilibrium game and instead analyze welfare indirectly. Calling the equilibrium structure “complex” does not supply the missing complexity result.
The strongest proposed rescue is a market with recurring bidder cohorts and item supplies that grow with the population. That is a plausible sequel to this paper. But the proposed \(\rho(\mu,q)\) is a limit of equilibrium welfare ratios: studying it would ask how equilibria behave under replication, not continue a computational question established by Theorem 1. A direct atomless model also needs a new equilibrium account. An individual bidder has zero mass and cannot affect aggregate supply or future play, while the paper’s strategic mechanism relies on bidders’ choices changing later incentives. Keeping finite replicas preserves that mechanism, but then the object is a sequence of finite games whose equilibrium limits need to be analyzed.
The paper’s lower-bound construction also does not itself establish that the bad outcome persists for fixed support size: its chain uses increasingly specialized unit-demand bidders. Replicating a fixed set of types is a sensible experiment, but whether that experiment retains the inefficiency is an open question, not something supplied by the theorem. That is a limitation on the proposed mirror’s connection to the result, not a claim that a different answer would make the question uninteresting.
One could attach a computational question—for example, deciding whether a replicated market has an IEWDS-surviving equilibrium below a welfare threshold. But that requires choosing a new input-output problem and carrying the extensive-form incentives, histories, and equilibrium refinement into the limit. The type masses do not naturally turn the game into the mass-transfer LPs or pricing problems that motivate ChoCo’s complexity programme. So I would reject Theorem 1 as a qualifying ChoCo anchor. I would not claim that no continuous study of these auctions could be worthwhile: the cohort-market limit could be valuable auction theory. The negative case is strongest, and honest, when it says that this is a different research question from the continuous computational mirror sought here.
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.