| paper | d4-conf-aaai-2004-0162 |
| 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: Polynomial-time solvable. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
Given τ valuation types \(t\) with rational masses \(\mu_t\) summing to \(1\), \(m\) goods with rational per-capita capacities \(q_j\), explicit XOR bids with free disposal, and report-independent nested ranges \(\mathcal{B}_1\subseteq\cdots\subseteq\mathcal{B}_K=2^G\) represented by GROWRANGE item-partition refinements, compute at each stage \(\ell\) an exact rational welfare-maximizing assignment of type mass to integral bundles in \(\mathcal{B}_\ell\), respecting type masses and capacities; also compute the optimum after deleting each type’s mass.
A finite set of complete valuation types carries masses \(\mu_t\). At each stage, variables \(x_{t,S}\) assign type-\(t\) mass to integral bundles \(S\) in that stage’s partition-defined range, maximizing \(\sum_{t,S}x_{t,S}v_t(S)\), subject to \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:j\in S}x_{t,S}\le q_j\). The model also asks for the corresponding optima with each type removed.
Covers the stage-by-stage welfare allocations and type-deletion counterfactuals underlying the mechanism. It does not preserve the individual strategyproofness claim in an atomless population, or cover the time-based interruption analysis, consensus estimator, or empirical performance results.
The strongest positive mirror is the allocation computation underneath Theorem 2. That theorem, proved in this paper, says that the anytime VCG mechanism is strategyproof under a stage-based interruption and implements an efficient allocation if it runs long enough. The paper does not give a named NP-hardness or polynomial-time classification for that computation, so the complexity question below is a new one motivated by the theorem, not a result the paper already establishes.
Consider a large repeated combinatorial-auction market: many buyers have one of a small number \(\tau\) of valuation functions, while the number of buyers \(n\) is large. For example, buyers in a procurement platform might fall into a few recurring demand profiles. A type \(t\) is the buyer’s complete valuation \(v_t\) over bundles of \(m\) goods; \(\mu_t\) is the fraction of the population with that valuation. Let the supply of good \(j\) be \(q_j\) units per unit of population. Scaling supply with population is part of making this a meaningful large-market version of the paper’s auction.
The precise mirror is Mass-GROWRANGE Allocation. Its input is rational masses \(\mu_t\) summing to \(1\), rational supplies \(q_j\), valuations given as explicit XOR bids with free disposal, and a report-independent nested sequence of bundle families \(\mathcal B_1\subseteq\cdots\subseteq\mathcal B_K=2^G\), such as the families induced by GROWRANGE’s refining item partitions. At each stage \(\ell\), find a mass assignment \(x_{t,S}\) maximizing
\[ \sum_t\sum_{S\in\mathcal B_\ell}x_{t,S}v_t(S) \]
subject to
\[ x_{t,S}\ge 0,\qquad \sum_{S\in\mathcal B_\ell}x_{t,S}=\mu_t,\qquad \sum_t\sum_{S\ni j}x_{t,S}\le q_j\quad\text{for every good }j. \]
Here \(x_{t,S}\) is the mass of type-\(t\) buyers receiving the integral bundle \(S\); the aggregate may split a type across bundles. The requested solution is an exact rational optimum at every stage, together with the optimum after removing each type’s mass, which supplies the VCG counterfactuals.
This is recognizably the allocation problem that Theorem 2’s mechanism repeatedly solves, now stated for a continuous population. Under the stated XOR and partition representation, I expect Class A: these are configuration LPs with exponentially many bundle variables, but their pricing queries can be answered by scanning the listed XOR bids and finding the cheapest allowed bundle covering each bid. That suggests exact polynomial-time optimization in \(m,\tau\), the input bit length, the bid-list size, and the number of stages. A VCG wrapper preserves truthfulness for a type cohort treated as one reporting unit, by the same maximal-in-range logic as in Theorem 2.
The mirror covers the stage-based allocation and its counterfactual computations, not the paper’s time-based interruption result or every claim about individual bidders. That is its weakest point: in an atomless population, one individual’s report has zero effect, so individual strategyproofness can become vacuous. Cohort-level truthfulness is meaningful only where a type group really does act through a common reporting unit. The allocation-complexity question still stands without that assumption, but the strategic claim would need that qualification. Further questions include the finite-population integrality gap, the pricing boundary for richer valuation languages, and whether any useful individual-incentive guarantee survives the limit.
The strongest objection to the proponent’s anchor is that Theorem 2 is about incentives, not the complexity of allocation. It proves dominant-strategy truthfulness for finite agents when the interruption is stage-based. In an atomless society, changing one individual’s report leaves the population distribution unchanged, so the individual’s effect on the allocation vanishes. Treating an entire type cohort as the reporting agent restores a strategic problem, but changes the strategic unit from individual bidders to a bloc. That is a poor mirror of Theorem 2’s incentive claim.
The same issue undermines a better mirror of the paper’s incentive results. Theorem 1 gives a named impossibility for tractable, reasonable, strategyproof VCG-based combinatorial auctions; Theorems 4 and 5 address strategyproofness under time-based interruption. In a continuum model, one must either make a single agent’s mass positive, abandoning the atomless population, or model cohorts as agents, changing the game. Neither preserves the paper’s original individual-incentive question.
But that does not defeat the proposed allocation problem. With per-capita supplies, finitely many complete valuation types, and integral bundles assigned to each unit of mass, Mass-GROWRANGE is a coherent continuous-population optimization problem. Its configuration LP and XOR pricing structure look like a plausible tractability question. Scaled supply is a legitimate part of the mirror under ChoCo’s scope, and high multiplicity is evidence for the setting, not a collision. Calling the result a routine LP, or observing that its answer may be easy, would not show the question is unworthy.
So the negative case is weak against the allocation-complexity anchor. It can defeat the claim that this is a faithful continuous mirror of the paper’s *strategyproofness theorems*: the individual incentive guarantee loses meaning, and cohort truthfulness changes the model. It cannot honestly rule out the continuous allocation problem as worthwhile in its own right.
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.