| paper | d4-conf-aaai-2000-0231 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: The revenue-threshold problem is in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), by exact rational linear feasibility. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given \(m\) goods and \(\tau\) bidder types, each with an integer bundle \(q_t\in\mathbb{Z}_{\ge 0}^m\), a rational price \(p_t\ge 0\), and population mass \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), together with rational per-capita supplies \(s_g\ge 0\), choose accepted mass \(x_t\in[0,\mu_t]\) to maximize \(\sum_t p_t x_t\), subject to \(\sum_t q_{tg}x_t\le s_g\) for every good \(g\). Each accepted bidder receives their whole integer bundle; only the accepted mass of a type is fractional.
A compact linear program with one accepted-mass variable per repeated bidder type, revenue as the objective, and per-capita supply constraints. Its input size is measured by \(m\), \(\tau\), and the rational input bit length \(L\).
The mirror covers the one-bid-per-bidder subcase of winner determination. It leaves aside the paper’s general additive multi-bid model, mutual-exclusion constraints, CAMUS’s search procedures, and its experimental results.
The strongest honest anchor is Theorem 2, proved in this paper: CAMUS is complete for multi-unit combinatorial auction winner determination, meaning that given goods with finite supplies and bids specifying a price and a requested quantity of each good, it is guaranteed to find a revenue-maximizing feasible subset of bids. Feasibility means that the selected bids’ total demand for each good does not exceed its supply. This is an exact-algorithm correctness result; it does not establish a polynomial-time bound for CAMUS.
There is no numbered theorem in the supplied text classifying winner determination as NP-hard or in P. The paper says that the general problem is intractable even in the single-unit case, citing Rothkopf, Pekec, and Harstad (1998), but that is background rather than a numbered result proved here. So Theorem 2 is an algorithmic anchor, not a hardness anchor.
My lead mirror is Continuous Multi-Unit Winner Determination. Consider a wholesale auction with \(m\) goods and a population of bidders. A type \(t\) is a complete, repeated bid: a bundle vector \(q_t\in\mathbb{Z}_{\ge 0}^m\) and a price \(p_t\in\mathbb{Q}_{\ge 0}\). The input gives \(\tau\) such types, their rational population shares \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), and the per-capita supply \(s_g\in\mathbb{Q}_{\ge 0}\) of each good. Each bidder submits one bid. The decision variable \(x_t\in[0,\mu_t]\) is the mass of type \(t\) whose bid is accepted. Find a feasible \(x\) maximizing
\[ \sum_{t=1}^{\tau} p_t x_t \quad\text{subject to}\quad \sum_{t=1}^{\tau} q_{tg}x_t\le s_g \quad\text{for each good }g. \]
The individual outcome remains discrete: every accepted bidder receives the entire integer bundle \(q_t\), and every rejected bidder receives nothing. Only the accepted mass is fractional. Thus a value such as \(x_t=0.23\) means that 23% of the type’s population wins, not that each winner receives 23% of a television. This is a population-continuous model with the necessary co-modification that supply is measured per capita.
A plausible regime is a wholesale platform with many retailers or automated purchasing agents using a relatively small set of repeated bundle-and-price templates. The agents share a type because their demands and offers match on every feature relevant to winner determination. Here \(N\), the number of bidders, can be very large while \(\tau\ll N\). The paper’s own example of standardized multi-good orders makes repeated bundle types natural; repeated purchasing policies make repeated prices plausible too. The case is strongest in such a templated market, rather than in an auction where nearly every bidder submits a unique offer.
This mirror is an LP with \(\tau\) variables, \(m\) supply constraints, and rational bounds. It can be solved exactly in time polynomial in \(m,\tau\), and the input bit length \(L\). I expect Class A for this continuous problem. The discrete-to-continuous bridge is direct: for \(N\) bidders, \(n_t\) of type \(t\), and integer stock \(B_g\), set \(\mu_t=n_t/N\) and \(s_g=B_g/N\). A discrete allocation with \(y_t\) winning bids gives \(x_t=y_t/N\). Conversely, rounding an optimal continuous solution down to \(y_t=\lfloor Nx_t\rfloor\) preserves feasibility and loses less than \(\sum_t p_t\) in total revenue. The loss per capita therefore falls below \(\sum_t p_t/N\). The continuous optimum also gives an upper bound on the normalized discrete optimum.
The authors should recognize this as their winner-determination question: it keeps the same seller objective, package bids, prices, and capacity constraints, and changes the number of identical bidders from an integer count to population mass. It covers the one-bid-per-bidder subcase of their model, not every feature of the general additive-bid model. A natural next question is whether the result extends cleanly to bidder types with multiple bids and mutual-exclusion constraints, and whether the resulting allocation-pattern LP has a compact formulation. Other follow-ups are to characterize when the LP is integral and to bound its discrete integrality gap more sharply.
The weakest point is that repeated *exact* price-and-bundle offers may be uncommon in markets where bids are individually tailored. Also, the continuous LP’s tractability is a new result about the mirror; it does not transfer a complexity classification from Theorem 2, since that theorem proves correctness rather than an efficient worst-case running time. Those limits narrow the claim, but leave a concrete mirror of the paper’s central optimization problem.
The strongest case against starts with an anchor mismatch: Theorem 2 proves that CAMUS finds an optimal allocation, but it gives no worst-case running-time bound. The paper’s experimental results do not fill that gap. So Theorem 2 is a thin foundation for a programme about complexity landscapes: its exactness claim does not tell us whether the continuous version changes tractability.
The proposed one-bid-per-bidder mirror also has little distance from the standard fractional winner-determination LP. With repeated bid types, its variables are accepted bidder mass; with divisible goods, they can be read as fractions of bids accepted. The paper itself notes that infinitely divisible goods can be handled by linear programming. That makes the proposed subcase look more like a familiar relaxation than a new algorithmic frontier.
But those points do not defeat the better mirror. Give each type a complete bid menu and any relevant mutual-exclusion constraints. Let \(a\) range over the feasible allocation patterns for one bidder of type \(t\), and let \(z_{t,a}\) be the mass receiving pattern \(a\). Then \(\sum_a z_{t,a}=\mu_t\); supply constraints and revenue are linear in the \(z_{t,a}\). There may be exponentially many patterns, so the computational question becomes whether the pricing problem over patterns is tractable. That is a recognizable version of the paper’s winner-determination problem, with per-capita supplies as the permitted co-modification. In a wholesale or procurement market where many automated buyers reuse a small set of bid menus, high multiplicity is plausible. Full-menu types also preserve the bidder information needed for mutual exclusion.
The overlap with fractional winner determination limits the novelty of the single-bid version, but it is not a decisive objection under the programme’s standard: a familiar or already-solved continuous answer does not make a well-posed population mirror unworthy, and divisible outcomes alone do not establish that the population model has already been studied. Nor does the lack of a complexity theorem erase the paper’s central computational problem.
So the negative case is weak. Theorem 2 is not a complexity classification, and the simplest mirror may be too close to a known LP to be an exciting result. But the full-menu, high-multiplicity version still presents a credible pricing question, and I cannot honestly argue that no worthwhile continuous mirror exists.
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.