d4-conf-aaai-2014-0523

Theorem 1 gives VCG a positive equilibrium welfare guarantee. But the proposed mass game makes each type cohort a strategic principal, whose deviations control a coalition; in a truly atomless population, an individual has no pivotal externality. That changes the strategic question, so the continuous version does not preserve the anchored result.

The objection that survived

The cohort player has coalition-sized deviations instead of the individual deviations in Theorem 1, and the case gives no construction that preserves those incentives in an atomless limit.

What the mirror covers

The proposed question targets Theorem 1's equilibrium welfare ratio; it does not independently anchor Theorem 2's single false-name bidder or its almost-tight example.

Open questions for a prover

The case FOR (proponent)

The strongest positive case is a high multiplicity version of the paper’s VCG welfare analysis. Theorem 1, proved here, says that if bidders’ true valuations and bidding functions are \(\alpha\)-near-submodular and bidders are individually rational, then every Nash equilibrium of VCG has welfare at least \(\frac{1}{1+\alpha}\mathrm{OPT}\). This includes equilibria where bidders use pseudonyms. It is a useful anchor because the bound concerns the welfare of an outcome under strategic bidding, not fractional outcomes or a noise model.

A plausible regime is a large procurement or spectrum market where many buyers share one of a small number of valuation profiles. A type \(t\) is a buyer’s complete valuation function \(v_t:2^G\to\mathbb{Q}_{\ge 0}\), with \(D(v_t)\ge 1/\alpha\). The society is a rational distribution \(\mu\) over a finite set \(\mathcal T\) of such types, with \(\sum_t\mu_t=1\) and \(|\mathcal T|\ll N\), the number of buyers. Standardized goods could be supplied in proportion to market size; that supply change is part of this proposed mirror.

I would call the candidate Mass-VCG-IR-Welfare. An instance consists of \(G,\mathcal T,\mu\), an \(\alpha\), and per-capita supply \(q_j\) for each good \(j\). Let \(x_{t,S}\) be the mass of type \(t\) receiving the integral bundle \(S\subseteq G\). Feasible allocations satisfy
\[ \sum_{S\subseteq G}x_{t,S}=\mu_t,\qquad \sum_{t\in\mathcal T}\sum_{S\ni j}x_{t,S}\le q_j. \]
True welfare is \(W(x)=\sum_{t,S}x_{t,S}v_t(S)\), and \(\mathrm{OPT}\) is its maximum over feasible allocations. Each type’s mass can submit bids through one or more pseudonyms; VCG selects a declared-welfare-maximizing allocation and charges each pseudonym its externality. The question is: over the individually rational Nash equilibria in which the bids satisfy the paper’s \(\alpha\)-near-submodularity condition, what is the infimum of \(W(x)/\mathrm{OPT}\)? A proof of the bound, or a counterexample, is a solution. I expect the paper’s lower bound \(\frac{1}{1+\alpha}\) to survive: its proof’s inequalities over bidders have a natural mass-weighted form. The sharper question is whether that bound is tight in this model.

Theorem 2, also proved here, is related but I would not use it as a second anchor. It says that when the nonmanipulating bidders have \(\alpha\)-near-submodular valuations, a VCG Nash equilibrium with one false-name bidder has welfare at least \(\frac{1}{1+\alpha}\mathrm{OPT}\), even if that bidder’s false-name bids are neither individually rational nor \(\alpha\)-near-submodular; the paper gives instances with welfare as low as \(\frac{1}{\alpha}\mathrm{OPT}\). A continuous version would need a distinguished positive-mass manipulator. But one bidder’s mass vanishes in the population limit; giving the manipulator positive mass instead turns it into a coalition. That changes the strategic question.

This is a credible population-limit question, but its weakness is substantial. To define the mass game above, a type cohort acts as a strategic principal controlling its mass. In the paper, individual bidders choose bids and VCG prices reflect the effect of removing an individual. Treating a whole cohort as one player changes Nash deviations; treating agents as truly atomless risks making their individual externalities vanish. The per-capita supply scaling also extends the auction environment.

There is a further scope problem: these named theorems give welfare guarantees, not computational-complexity classifications or algorithms. The paper explicitly sets aside VCG’s computational practicality. So the proposed mirror may be acceptable as a continuation of its economic-efficiency analysis, but I cannot honestly present it as a strong ChoCo complexity anchor: the paper contains no named result establishing that a problem is in P, hard, FPT, or similar.

The case AGAINST (opponent, writing after the proponent)

There is a plausible high-multiplicity auction setting here: many buyers may share one complete valuation function, and supplies can scale with market size. I would not reject the mirror on the ground that bidders lack a meaningful type distribution.

The problem is that Theorem 1 is a welfare guarantee for Nash equilibria, not a computational result. It proves a bound of \(1/(1+\alpha)\) on the equilibrium welfare ratio; it gives no algorithm or complexity classification for a computational problem. The paper explicitly sets computational practicality aside and treats VCG’s welfare-maximizing allocation as available. Replacing bidder counts with type masses may give a continuous version of the welfare statement, but it does not make that statement a ChoCo complexity result.

The strongest alternative would be to ask for the worst equilibrium welfare ratio in a mass market, or to make deciding whether a low-welfare equilibrium exists the computational problem. Those could be research questions, but the latter adds a new complexity target that the paper neither studies nor establishes. The proposed infimum over equilibria is not, by itself, a computational question with an input, output, and resource bound.

There is also a real modelling tension in carrying Theorem 1’s strategic content into the limit. Its deviations and VCG externality prices are attached to individual bidders and identities. If each type’s mass becomes one strategic player, a deviation controls a whole cohort and changes the game. If the population is atomless, a single bidder’s false-name reports have zero mass and cannot change the aggregate allocation; preserving pivotal effects requires retaining positive-sized agents or giving a manipulator positive mass, which turns the deviation into a coalition. These alternatives may motivate new models, but none is simply Theorem 1 over a continuous society.

Theorem 2 does not provide a better anchor: its exceptional false-name bidder creates the same difficulty, more starkly. A positive-mass manipulator is a coalition, while an individual atom disappears in the limit.

So the strongest defensible negative conclusion is narrow: this paper has no named computational result for ChoCo to continuize. A continuous welfare analysis might still be worthwhile in its own right, and the universal claim that no scenario could support one would be too strong. But that would be a new equilibrium-economics project, not a continuous mirror of a computational result in this paper.

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.