| paper | d4-conf-wine-2013-0032 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
Theorem 1 is a computational result, and the proponent gives a concrete continuous-population version of its equilibrium-existence question. But in that version a bidder cannot affect cutoff prices, changing the strategic problem and removing the reduction's exact packing constraint. Whether the authors would recognize this price-taking extension as their problem is the specific unresolved issue.
fails bit b-changes — the continuum limit changes the question
The opponent's strongest point is that measure-zero deviations leave cutoff prices fixed, changing the equilibrium concept and removing the strategic packing structure; the proponent acknowledges that change but does not establish that the authors would treat the resulting problem as theirs.
fatal: False
It is undecided whether the authors would recognize atomless, price-taking VCG equilibrium existence as a continuation of their pure Nash equilibrium existence problem. A clear indication from the authors that nonatomic markets are within their mechanism agenda would settle this recognition question.
The proposed mirror concerns Theorem 1's equilibrium-existence decision and leaves the relaxed-smoothness welfare bounds and other Price of Anarchy results unmodeled.
The strongest case is Theorem 1, proved in this paper. It says that when valuations are subadditive (\(V=\mathrm{CF}\)), bids are additive (\(B=\mathrm{OS}\)), the mechanism is VCG, and bids are conservative, deciding whether a pure Nash equilibrium exists is NP-hard. The authors prove it here by reduction from 3-Partition in Appendix B. This is the right anchor: the paper’s hardness concerns equilibrium existence in the underlying auction, not an encoding of it.
A plausible high-multiplicity regime is a large exchange for standardized advertising or computing slots. There may be millions of small bidders but only \(\tau\) recurring valuation types: each type specifies the bidder’s value for every bundle of the \(m\) slot categories. Inventory grows with the market, so a category has \(q_j\) copies per capita. Each person still receives an integral bundle; only the fraction of the population receiving each bundle is continuous.
My lead mirror is Continuum Additive-Bid VCG Equilibrium Existence. Its instance is a finite set of item categories \(M\), a support \(T\) of \(\tau\) valuation types with rational masses \(\mu_t>0\) summing to \(1\), rational per-capita supplies \(q_j\in(0,1)\), and succinctly represented valuations \(v_t:2^M\to\mathbb{Q}_{\ge 0}\). Each \(v_t\) is normalized, monotone, and subadditive. A type-\(t\) bidder may submit an additive bid vector \(b\in\mathbb{Q}_{\ge0}^m\), conservatively: \(\sum_{j\in S}b_j\le v_t(S)\) for every \(S\subseteq M\).
Define the allocation as the many-copy limit of VCG with \(N\) bidders and \(q_jN\) copies of category \(j\). For each category, the highest bids receive its supply, ties at the cutoff are split anonymously, and winners pay the cutoff bid—the limiting per-copy VCG price. Each person’s bundle remains integral. A pure equilibrium is a measurable assignment of bids to individuals in which no individual can gain by changing their bid, with the cutoff prices fixed under that measure-zero deviation. The decision question is whether such an equilibrium exists. A yes solution can be given as cutoff prices, tie allocations, and a finite list of conservative bid vectors and rational population masses; whether every equilibrium has such a finite rational certificate is itself a useful first question for a prover. Complexity should be stated in \(m,\tau,L\), including the valuation representation.
I expect the mirror to be hard, probably Class C, because checking which bundles a type can profitably reach with conservative additive bids still involves combinatorial constraints over subsets. The continuous mass may remove the integral assignment choices behind 3-Partition, so Theorem 1 does not establish hardness here. Further questions include whether the problem becomes tractable for fixed \(\tau\), what bundle-pricing subproblem governs it, and whether its equilibria characterize approximate equilibria in large finite replicas.
The weak point is substantial: Theorem 1’s reduction has \(\tau\) growing with the instance, and uses a finite supply of indivisible items. In the proposed limit, inventory scales with population and an individual no longer changes the cutoff price. The mirror is credible as the equilibrium-existence question for a many-copy VCG market; it is an extension of the theorem’s setting, not a transfer of its hardness result.
Theorem 1 is the right result to test, but its reduction is built around atomicity. Appendix B uses \(3m\) indivisible items \(I_j\), and a pure equilibrium exists only when the \(B_i\) agents can divide those items into exact bundles of total weight \(B\). That is the 3-Partition constraint. In a replicated high-multiplicity market, each type has positive mass and each item category has per-capita supply. A type’s population can then split across bundles, even though each person still receives an integral bundle. The exact packing constraint that drives the reduction becomes fractional. The theorem gives no hardness evidence for that limit.
There is a deeper change in the equilibrium question. In the proposed atomless model, one person’s deviation has measure zero, so it leaves the item cutoffs unchanged. The resulting equilibrium is price-taking: each person chooses bids against fixed per-item prices. Finite-player VCG equilibrium existence asks about bidders who can affect allocations and payments through their deviations. Keeping those effects requires agents with positive mass; letting a whole type coordinate its deviation changes the equilibrium concept. The continuous question may be interesting, but the paper’s NP-hardness theorem does not establish it as the same question.
The paper’s other main results are welfare bounds from relaxed smoothness. Under a well-defined continuum equilibrium, their per-agent inequalities appear to extend by integration and yield analogous aggregate bounds. That could make a useful welfare analysis, but it does not supply the computational classification ChoCo seeks. An algorithmic question about atomless equilibrium existence would need its own representation of bid distributions and its own pricing or demand problem; the paper does not establish that this is where its computational contribution lies.
That is the strongest case against this anchor: the known hardness is attached to indivisible assignments and strategic price effects that disappear in the natural continuum limit. The case is weak as a universal verdict. Subadditive valuations over many item categories could still make the resulting type-level demand or pricing problem difficult, and a column-generation formulation might be worthwhile. I cannot rule out that the authors would regard that as their problem; the paper alone does not make that case.
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.