| paper | d4-conf-aaai-2007-0136 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper's numbered content consists of definitions, while its winner-determination complexity statements appear only in the Discussion and are attributed to earlier work. The proposed mass-allocation LP is a coherent continuous extension of that background problem, but it cannot supply the required computational result of this paper. Bit (a) therefore fails even though the candidate mirror is plausible.
fails bit a — no named computational result to mirror
The proposed LP addresses the Discussion's winner-determination aside; it does not cover the paper's GM-SMA claims about false-name-proofness, Pareto-efficiency behavior, or loser-collusion and core guarantees.
The paper has no numbered computational result of the required kind: no Theorem, Lemma, Corollary, or Proposition asserting a complexity classification. Its central GM-SMA claims concern mechanism properties such as false-name-proofness and resistance to loser collusion, not computational complexity.
The strongest possible foothold is an unnumbered, cited claim in the Discussion: winner determination in combinatorial auctions is NP-complete, with references to Sandholm (1999) and Fujishima, Leyton-Brown, and Shoham (1999); the paper also says it is polynomial-time solvable for submodular valuations, citing Lehmann, O’Callaghan, and Shoham (2002). These are computational claims, but they do not meet the required anchor format, and they are cited results rather than results proved here.
If that unnumbered claim is admitted provisionally, the most credible mirror is continuous winner determination. Consider a market with goods \(M\), valuation types \(T\), and society distribution \(\mu\), where each type \(t\) has a normalized, monotone valuation \(v_t(B)\) for every bundle \(B\subseteq M\). Let \(q_j\) be the per-capita supply of good \(j\). Choose masses \(x_{t,B}\ge 0\), where \(x_{t,B}\) is the share of society of type \(t\) assigned the integral bundle \(B\), to maximize
\[
\sum_{t\in T}\sum_{B\subseteq M} x_{t,B}v_t(B)
\]
subject to
\[
\sum_{B\subseteq M}x_{t,B}=\mu_t \quad(t\in T),\qquad
\sum_{t\in T}\sum_{B\ni j}x_{t,B}\le q_j \quad(j\in M).
\]
The goods supply scales with population, as in a bulk market with repeated buyer types and inventory growing with the market. Infinitesimal agents still receive whole bundles; mass records how many agents of each type receive each bundle.
With valuation tables given explicitly, this is an LP with \(\tau 2^m\) allocation variables, so it is tractable in the size of those tables. The expected direction is therefore Class A for this representation. Whether there is an algorithm polynomial in \(m,\tau,L\) for succinct valuations depends on the bundle-optimization or pricing problem; this paper does not settle that. Natural follow-up questions are the complexity under standard succinct valuation models, the approximation gap when a finite electorate is rounded to these masses, and whether GM-SMA’s payment and false-name properties have a sensible counterpart for an atomless population.
This is a modest positive case. The article’s main contribution is about strategic properties of GM-SMA, and a continuum can change the significance of an individual false-name deviation. The winner-determination mirror also changes the setting by scaling supply with population and allowing a type cohort’s mass to be divided among bundles. Those changes are plausible for a large repeated market, but the paper neither develops that regime nor gives the numbered computational anchor the requested case requires.
The strongest negative is about the anchor, not about whether a continuous auction model can be written. This paper’s GM-SMA claims concern false-name-proofness, Pareto efficiency, and core stability; its explicit impossibility is also about mechanism properties. The computational claim is an aside in the Discussion: discrete winner determination is NP-complete, citing earlier work, and is polynomial for submodular valuations. The paper proves neither claim or presents them as its contribution. Its own computational direction is only a suggestion that an efficient false-name-proof protocol might be developed. Sandholm’s paper is a source for the cited winner-determination result, but that makes it prior work, not a computational result of this paper. [Sandholm, “An Algorithm for Optimal Winner Determination in Combinatorial Auctions”](https://www.ijcai.org/Proceedings/99-1/Papers/078.pdf)
The proposed mass-allocation LP is a plausible mirror of that background problem: repeated buyer types and inventory scaled with population make sense in a bulk market. But it leaves out what is distinctive about this paper. It optimizes welfare; it does not compute GM-SMA payments or address its false-name and collusion guarantees. Those strategic questions depend on a named bidder’s deviation. In an atomless population, one bidder has zero mass, so the deviation disappears; making a whole type cohort the strategic actor changes the question.
There is also limited computational novelty in the LP formulation itself. With valuation tables listed explicitly, it is solvable in time polynomial in the table size, which can already be exponential in \(m\). With compact valuations, the exponential bundle variables bring back a pricing or demand problem. Configuration-LP work already studies fractional bundle assignments and the associated demand-query machinery; that is relevant background, though its usual interpretation as a relaxation over named bidders does not by itself make it a continuous-population collision. [FOCS work discussing configuration-LP methods for combinatorial auctions](https://conferences.computer.org/focs/2019/pdfs/FOCS2019-7pBwCpNH4Mz2L4MJWVl6Xp/17gbYZTuou76Kc76NCWYoU/NUzNRWj3JKDgJhz78g9Ex.pdf)
I cannot honestly claim that no repeated-type, per-capita-supply version of winner determination could be worth studying. It is a sensible high-multiplicity model, and that is the weak point in the negative case. My case is strongest under the requested standard of mirroring this paper’s computational results: the proposed LP is a worthwhile question about a cited background problem, but not a mirror of a computational result this paper contributes. If a cited discussion claim is allowed to serve as the anchor, the universal negative does not hold up.
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.