| paper | Towards a universal test suite for combinatorial auction algorithms |
| authors | Kevin Leyton-Brown, Mark Pearson, Y. Shoham |
| venue | SIGECOM 2000 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains no numbered theorem, lemma, proposition, or corollary asserting an algorithm, approximation, computational formulation used to compute, or hardness result; its intractability statement is background prose. The proposed continuous high-multiplicity path-allocation problem is recognizable and well posed, but without a qualifying result from this paper it cannot satisfy bit (a).
fails bit a — no named computational result to mirror
The proposed mirror covers path-based winner determination, especially “CATS 1.0 problem 1” and its bandwidth or commodity-flow extension, but leaves the other distributions, benchmark methodology, and empirical test-suite claims untouched.
The strongest positive case is modest but genuine. This paper does not itself contain a qualifying computational anchor: it has no numbered Theorem, Lemma, Proposition, or Corollary asserting an \( \mathrm{NP} \)-hardness, polynomial-time, FPT, or similar result. “The computational combinatorial auction problem” is introduced in §1.2, and the paper says that the unrestricted problem is intractable, but this is background prose, not a named result proved here. “CATS 1.0 problem 1” is a named distribution, not a complexity theorem. Therefore there are no honest anchors to quote under the programme’s rules.
Nevertheless, the paper supplies a strong candidate mirror of its underlying winner-determination problem. I would call it Continuous CATS Winner Determination for Paths in Space.
Take a graph \(G=(V,E)\), where each edge is a good, and let \(q_e\in\mathbb{Q}_{\ge 0}\) be the supply of edge \(e\) per bidder. Let \(T\) be a finite set of bidder types, with population distribution \(\mu\). A type \(t\) completely specifies the bidder’s origin and destination, feasible path family \(\mathcal P_t\), budget and all path valuations \(v_t(P)\). Thus two bidders of type \(t\) have the same preferences and submit the same XOR family of path bids. The mass \(\mu_t\) is the fraction of bidders of that type.
The decision variable is
\[ x_{t,P}\ge 0, \]
the mass of type-\(t\) bidders awarded path \(P\). The continuous winner-determination problem is
\[ \max_x \sum_{t\in T}\sum_{P\in\mathcal P_t} v_t(P)x_{t,P} \]
subject to
\[ \sum_{P\in\mathcal P_t}x_{t,P}\le \mu_t \quad\text{for every }t, \]
and
\[ \sum_{t\in T}\sum_{P\ni e}x_{t,P}\le q_e \quad\text{for every }e\in E. \]
The output is an optimal aggregate allocation \(x\) and its maximum revenue. Each unit of mass still receives one integral path; only the aggregate allocation is fractional. The corresponding decision version asks whether the optimum is at least \(R\).
This is recognisably the paper’s problem, not merely a tractable cousin. It retains indivisible bundles, complementarities, XOR-substitutability, scarce goods, path structure, and revenue-maximising winner determination. It is also exactly the sort of multi-unit extension the paper discusses in §4.1.3 for bandwidth allocation and commodity flow.
The natural regime is a large repeated market: for example, many shipping firms seeking near-identical bandwidth routes, or many firms bidding for repeated daily capacity on the same network. There may be \(n\) firms but only \(\tau\) economically distinct bidder types, with \(n\gg\tau\). Each type shares its origin, destination, valuation parameters, budget, and substitutable path bids. Edge capacities scale with the population: an instance with \(n\mu_t\) bidders has approximately \(nq_e\) copies of edge \(e\). Normalising by \(n\) gives the LP above. This is a proper high-multiplicity interpretation, rather than treating individually idiosyncratic bidders as interchangeable.
The computational question is especially well aligned with the continuization programme. The LP has exponentially many possible paths, and column generation requires solving, for each type \(t\), a pricing problem of the form
\[ \max_{P\in\mathcal P_t} \left(v_t(P)-\sum_{e\in P}\lambda_e\right), \]
where \(\lambda_e\) are dual prices. For the path-valuations explicitly motivated by CATS, this may reduce to a shortest- or longest-path computation, suggesting a Class A result for that specialization. For more general CATS distributions, the pricing problem could remain hard; that would be a meaningful boundary question rather than evidence that the mirror is artificial.
The authors would plausibly recognise this as their problem because their central object is allocation of bundles to maximise seller revenue, while their CATS distributions are explicitly built from bidder types, complementarities, substitutable XOR bids, and multi-unit auction domains. The paper itself does not make the population continuous: it generates finite bid sets. Thus this is not a novelty collision. It is a high-multiplicity computational reformulation of the winner-determination problem underlying the test suite.
The mirror covers only the winner-determination component of the paper, especially “CATS 1.0 problem 1” and its bandwidth/commodity-flow extension. It does not mirror the paper’s broader claims about benchmark realism, random graph generation, experimental evaluation, or the proposed universal test-suite methodology.
Its weakest point is that the original paper is primarily a benchmark-design paper, not a complexity paper. There is no named hardness or algorithmic theorem for the proposed continuous version to mirror. A second weakness is that scaling supplies with population changes the single-unit auction into a multi-unit or repeated-market model. That co-modification is forced if a continuum of bidders is to receive nonzero allocations, and the paper explicitly discusses such extensions, but an opposing analyst could still argue that it is not the exact one-shot model studied experimentally.
The further questions are nevertheless substantive: whether path pricing is polynomial for each CATS family; whether discrete high-multiplicity winner determination converges exactly to the LP; whether arbitrary-relationship or temporal-scheduling distributions yield continuum-specific hardness; and how an efficient continuous solver approximates large finite CATS auctions. So the positive case is not that this paper proves a continuous complexity result. It is that its economically typed, multi-unit combinatorial-auction models admit a precise and recognisable population-continuous winner-determination problem, with the programme’s characteristic LP-and-pricing structure.
The decisive objection is that this paper has no qualifying computational result to continuize. It is a benchmark-design paper, not a complexity paper. Its only computational claim—that unrestricted combinatorial-auction winner determination is intractable—is background prose, not a theorem proved here. “CATS 1.0 problem 1” names a generated distribution, not an algorithmic result. Thus there is no paper result whose continuous analogue could be classified as tractable, hard, or continuum-specifically hard.
The proposed path mirror is instead a new research problem built from the paper’s motivating application. CATS does not define a finite type space, a population distribution, or a parameterized family of repeated bidder types. It generates explicit finite bids, with num_bids controlling the sample size. In the path distribution, origins, destinations, private values, and resulting bid sets are sampled; exact bidders are generally distinct. Grouping them into types is therefore an additional modelling choice, not a continuization of the model actually specified.
The strongest rescue is the repeated-market scenario: many firms with identical route demands, identical valuations, and capacities scaling with the number of firms. That is economically plausible, and the resulting formulation
\[ \max \sum_{t,P} v_t(P)x_{t,P} \]
subject to type-mass and edge-capacity constraints is mathematically legitimate. But it is a high-multiplicity multi-unit path-allocation problem, not the single-unit finite-bid auction that constitutes the paper’s principal object. Without scaling capacities, the limit is degenerate: a finite set of single-unit goods supplies vanishing per-capita capacity. With scaling, one has changed the auction into a repeated or capacitated market. Section §4.1.3 mentions such multi-unit extensions, but does not study their computational complexity or establish them as part of CATS’s contribution.
Nor does the column-generation observation repair the anchoring problem. For the simplest path valuations, pricing reduces to a shortest-path calculation; for richer CATS valuations, pricing may be difficult. Either outcome could motivate a new paper, but neither mirrors a named result here. The proposed questions about convergence, approximation, or pricing complexity belong to a new continuous combinatorial-auction programme, not to the claims made by Leyton-Brown, Pearson, and Shoham.
The same dilemma affects any stronger version based on real estate, arbitrary complementarities, airport slots, or scheduling. Holding the original finite supplies gives a vanishing-capacity limit; scaling supplies creates a repeated multi-unit scheduling or allocation model. A distribution over randomly generated valuations would not solve this: it would be an average-case or stochastic generator, not a continuous society of finitely many complete types. And since the paper’s purpose is to generate realistic finite test instances, replacing those heterogeneous instances by repeated masses may erase precisely the variation the test suite was designed to expose.
This is nevertheless not an airtight universal negative. The repeated-route market is a sensible high-multiplicity scenario, and the resulting LP has exactly the kind of aggregate-allocation and pricing structure the continuization programme values. The strongest honest conclusion is therefore narrower: this paper supplies no named computational anchor, and the proposed mirror is a plausible new extension rather than a continuization of a result in the paper. If the gate requires an emphatic, worthwhile mirror of the paper itself, the negative case is strong; if any recognisable high-multiplicity reformulation suffices, the path mirror survives.
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.