| paper | d4-conf-aaai-2011-0263 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: \(1\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Fix a finite set \(J\) of item categories and a finite set \(\Theta\) of gross-substitutes valuations over integral bundles \(B\subseteq J\), with per-capita supplies \(q_j\). For populations of size \(N\), give category \(j\) an integer supply approximating \(Nq_j\), and let the empirical type distribution converge to \(\mu\in\Delta(\Theta)\). Among sequences of anonymous finite-population VCG redistribution mechanisms that are strategy-proof, individually rational, and non-deficit at every \(N\), find a limiting per-type rebate rule \(\beta_\theta(\mu)\) maximizing \(\inf_{\mu:\,p(\mu)>0}\frac{\sum_{\theta\in\Theta}\mu_\theta\beta_\theta(\mu)}{p(\mu)}\), where \(p(\mu)\) is limiting VCG revenue per capita and allocations assign integral bundles to each unit of mass subject to the category supplies.
A large market with a fixed finite set \(\Theta\) of complete gross-substitutes valuation types, population distribution \(\mu\), and category supplies growing with population size. Allocation variables \(x_{\theta,B}\) assign mass of type \(\theta\) to integral bundles \(B\); anonymous finite-population VCG redistribution rules induce limiting rebates \(\beta_\theta(\mu)\), whose worst-case fraction of per-capita VCG revenue is maximized.
The theorem assumes tie-free profiles, while repeated type masses can create ties, so its Cavallo guarantee is not established in the proposed limit without a compatible tie-breaking rule.
fatal: False
The mirror covers Theorem 1’s Cavallo guarantee and the paper’s worst-case redistribution objective; it leaves the later recursive gadgets, automated mechanism design construction, and numerical cases without separate mirrors.
The best anchor is Theorem 1, proved in this paper, though it is a performance theorem rather than a complexity-class result. It states that, for combinatorial auctions with gross-substitutes valuations and \(n>m+1\), the Cavallo scheme’s worst-case fraction of VCG revenue redistributed is exactly \((n-m-1)/n\). The paper proves the lower bound for gross substitutes; the upper bound follows from Guo and Conitzer (2009)’s result for a restricted auction setting. The paper has no named result saying a problem is in P, NP-hard, or belongs to another complexity class. If “anchor” strictly requires such a result, then it has no qualifying anchor.
The most plausible regime is a large market with many small firms or buyers drawn from a relatively small set of valuation types—for example, firms competing for standardized permits, with per-type valuations satisfying gross substitutes. Let \(\Theta\) be the finite set of complete valuation types, \(\mu_\theta\) the fraction of agents of type \(\theta\), and let the supply of each item category grow with the population. If \(N\) is population size and \(m_N/N\to\rho<1\), then the paper’s Cavallo guarantee tends to \(1-\rho\). This makes the population limit meaningful while keeping the number of types \(\tau=|\Theta|\) potentially much smaller than \(N\).
A concrete continuous question is Gross-Substitutes Mass Redistribution. Its input is a finite type set \(\Theta\) of gross-substitutes valuations and per-capita supplies \(q_j\), with \(\sum_j q_j=\rho\). A population is a distribution \(\mu\in\Delta(\Theta)\). An allocation is described by masses \(x_{\theta,B}\): the mass of type \(\theta\) assigned the *integral* bundle \(B\), subject to \(\sum_B x_{\theta,B}=\mu_\theta\) and the per-capita supply constraints. The allocation maximizes total value.
The task is to find a limiting VCG redistribution rule, together with its worst-case guarantee. More precisely, require the rule to be the limit of anonymous finite-population VCG redistribution schemes that are strategyproof, individually rational, and non-deficit at every population size. If \(\beta_\theta(\mu)\) is the limiting rebate per unit mass and \(p(\mu)\) the limiting VCG revenue per capita, maximize
\[ \inf_{\mu:\,p(\mu)>0} \frac{\sum_{\theta\in\Theta}\mu_\theta\beta_\theta(\mu)}{p(\mu)}. \]
The solution is the limiting rule and its guarantee. The finite-population requirement matters: strategyproofness would otherwise become vacuous for an agent of zero mass. Theorem 1 supplies a baseline: the Cavallo sequence achieves the guarantee inherited from \((n-m_N-1)/n\), tending to \(1-\rho\). It does not establish that this is optimal in the continuous model, especially when \(\tau\) is fixed.
I would tentatively expect a tractable formulation for fixed, explicitly represented \(\Theta\), perhaps through a finite or separable optimization program using gross-substitutes welfare oracles. That is a research conjecture, not a result of this paper. The main follow-up questions are whether the best guarantee improves on \(1-\rho\) at bounded support, whether the relevant optimization admits an efficient separation oracle, and whether any discrete hardness survives when \(\tau\ll N\).
The weak point is substantial: the paper assumes tie-free type profiles, while repeated agents of the same type naturally create ties. Symmetric tie-breaking would be a plausible co-modification, but it changes the mechanism details. Also, Theorem 1 concerns Cavallo’s guarantee, not the complexity of finding optimal redistribution schemes; it is the paper’s closest named anchor for this continuous design question, not a direct complexity result.
Theorem 1 is the only named anchor, and it is a worst-case guarantee for one fixed redistribution rule, not a complexity result. Turning it into a computational question means adding a larger task: optimize over limiting redistribution mechanisms. That task may be interesting, but it is not what the theorem establishes.
In the paper’s original regime, fix \(m\) and a finite set of bounded valuation types, then let the population grow. Because only \(m\) items can be allocated, total welfare and VCG revenue stay bounded; per-capita revenue therefore tends to zero. The proposed objective, which ranges only over populations with positive limiting per-capita revenue, has an empty domain. If instead we retain the paper’s total-revenue fraction, its Cavallo guarantee is
\[
\frac{n-m-1}{n}\longrightarrow 1.
\]
Since no feasible mechanism can redistribute more than all the revenue, the limiting optimum is already \(1\). The distinction between mechanisms lies in the finite-population correction, which the continuum limit discards.
The proposed repair is to scale the number of items with the population. That can produce a meaningful limit, and per-capita supply is an admissible co-modification. But in the paper, \(m\) counts distinct indivisible items and valuation types are functions over their bundles. Keeping a fixed finite type set as \(m\) grows requires replacing those items with replicated categories or another growing-supply model. The resulting optimization over limiting redistribution schemes could be a worthwhile new problem; it does not inherit a computational bottleneck from Theorem 1, whose guarantee is an explicit formula.
So the strongest negative case is that this anchor gives no nontrivial continuous computational question in its fixed-item regime, and its nondegenerate version needs a substantial new model and objective. I cannot honestly make that case universal: the replicated-goods version is plausible, and optimizing redistribution there might be valuable. The objection weakens exactly at that repaired model.
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.