| paper | d4-conf-ijcai-1999-0006 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proposed continuous winner-determination problem is a coherent high-multiplicity extension: with explicit bid menus, its mass-allocation formulation is a rational linear program. But the paper's NP-completeness statement is unnumbered and credited to prior work, while its own CASS and VSA evidence is empirical and carries no formal algorithmic guarantee. The required named computational result from this paper is missing, so bit (a) fails.
fails bit a — no named computational result to mirror
The proposed formulation covers the paper's central revenue-maximizing choice of non-conflicting bids; it does not mirror CASS's search, caching, and pruning methods or VSA's behavior and experimental results.
The paper has no numbered theorem, lemma, corollary, or proposition that establishes a complexity class. The closest anchor is its unnumbered Section 2 claim: given bids for bundles of goods, finding a feasible set of pairwise non-conflicting bids with maximum total revenue is NP-complete. The paper cites Rothkopf et al. (1995) for this claim; it does not prove it here. The two unnumbered VSA theorems concern when a current allocation is optimal and whether bidding can continue indefinitely, not a complexity classification. So this cannot be a fully compliant named-result anchor. If the Section 2 claim is admitted as the nearest available anchor, the strongest positive mirror I see is:
Continuous High-Multiplicity Winner Determination is the lead. An instance has goods \(G\); a finite support \(T\) of bidder types with rational masses \(\mu_t\ge 0\), where \(\sum_t\mu_t=1\); and a finite, explicit XOR menu \(B_t=\{(p_{tj},S_{tj})\}\) for each type. A type is a complete bid menu: all members have the same bundles, prices, and eligibility, and each member can win at most one bid. The instance also gives rational per-capita supplies \(q_g\) for each good. Find masses \(x_{tj}\ge 0\) maximizing \(\sum_{t,j}p_{tj}x_{tj}\), subject to
\[
\sum_j x_{tj}\le \mu_t \quad\text{for every }t,
\qquad
\sum_{t,j:g\in S_{tj}}x_{tj}\le q_g \quad\text{for every }g.
\]
The solution is the winning mass for each bid; each unit of mass receives either its whole bundle or none. The aggregate mass can be divided across bids because the population is continuous.
A plausible regime is a large, recurring allocation market for standardized projects or firms competing for bundles of transport, spectrum, or service capacity. There might be millions of bidders but only tens or hundreds of complete bid-menu types. Supply scales with the cohort: a finite instance with \(N\) bidders has \(N\mu_t\) of each type and \(Nq_g\) units of each good. That scaling is part of the mirror. If bidders have individualized menus so that the number of types approaches \(N\), the high-multiplicity motivation weakens.
This is recognizable as the paper’s winner-determination problem: choose which offered bundles are accepted to maximize revenue. The paper itself explains XOR bidding through dummy goods, so the menu restriction has a direct counterpart in its model. The question does not continuize the bundles: each recipient gets a whole bundle. It continuizes how much of each bidder type wins.
I expect this mirror to be tractable. With explicit bid menus, the displayed formulation is a rational linear program, solvable in time polynomial in \(|G|\), \(\tau\), the total number of listed bids, and the input bit length. For a finite replicated auction, requiring each \(x_{tj}\) to be a multiple of \(1/N\) yields the integer allocation problem; the continuous question removes that grid requirement. Follow-up questions include how well a continuous solution can be rounded to a finite auction, when the integrality gap vanishes, and whether column generation remains tractable if menus are represented implicitly.
The main weakness is substantial: the paper’s hard problem has arbitrary bundle conflicts, while this mirror relaxes bidder counts and uses an XOR regime. Its hardness may arise from the structure of bundles and goods, not from population multiplicity, so tractability here would not establish that the paper’s NP-hardness dissolves simply by scaling up the population. Still, it is a coherent high-multiplicity winner-determination question: the aggregate solution assigns whole bids to fractions of a genuinely large, repeated population. It covers the paper’s underlying allocation problem, not the complexity of CASS or the behavior of VSA; the paper gives no numbered complexity result for either algorithm.
The paper does not give a named computational result for a continuous mirror to target. Its only complexity classification is the unnumbered NP-completeness statement in Section 2, which it attributes to Rothkopf et al. The paper’s own contributions are CASS and VSA, their empirical performance, and unnumbered observations about VSA’s behavior. None establishes a complexity class or an algorithmic guarantee for those methods. On the strict anchor requirement, the proponent’s “lead” therefore does not qualify as a mirror of a named result from this paper.
That does not dispose of the underlying winner-determination problem. The strongest version of the proponent’s proposal is coherent: define bidder types by complete bid menus, let a large cohort repeat those types, and scale per-capita supplies with the population. Its mass-allocation LP is a sensible high-multiplicity question. But it supplies the paper with a population model, menu types, and scaled inventory that its formal problem never states. It is a worthwhile extension of the auction problem, not a continuous version of a named result proved by these authors.
The negative case is weak if the reader accepts the paper’s cited NP-completeness claim as an anchor despite the naming requirement. In that reading, the proposed mirror survives: a continuous population of repeated bidder types is plausible, and the co-scaled supplies fit the programme’s scope. I cannot honestly argue that no scenario yields a worthwhile mirror; the defensible case against is that this paper itself offers no qualifying named computational result to mirror.
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.