| paper | d4-conf-atal-2010-0106 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\): the decision problem is solvable in time polynomial in \(m,\tau,L\), and an optimal rational manipulation and internal allocation can be constructed. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2 (Optimal Collusion)
statement extracted from the paper’s text layer
Given a maximum demand \(K\), a finite support \(\Theta\) of rational diminishing-marginal valuation schedules, a population distribution \(\mu\), a designated coalition subdistribution \(\nu\leq\mu\), and supply \(\rho\) units per capita, choose a mass flow \(\pi_{\theta,b}\) assigning coalition agents of true type \(\theta\) to nonincreasing rational bid schedules \(b\), with noncoalition mass reporting truthfully. Allocate the top \(\rho\) mass of reported marginal units, splitting cutoff ties symmetrically, and find a flow maximizing coalition true utility \(\sum_{\theta,b,k}\alpha_{\theta b k}(v_\theta(k)-pk)\), where \(p\) is the limiting VCG cutoff price and \(\alpha_{\theta b k}\) is coalition mass receiving \(k\) units.
An atomless large-market limit of multi-unit VCG collusion: bounded-demand agents are distributed by \(\mu\), a positive-mass coalition \(\nu\) coordinates report flows, individuals receive integral bundles, and the coalition maximizes aggregate true utility at the common cutoff price.
The finite-to-continuous dictionary remains unproved: Theorem 2's merged proxy can represent coalition-scale demand, while bounded-demand atomless agents pay at a common cutoff price, and the correspondence at tied or discontinuous cutoffs is unresolved.
fatal: False
The proposed mirror covers Theorem 2's coalition-utility optimization; it leaves the convexity, core-imputation, Shapley-value, and bounded-domain Shapley results untouched.
The strongest anchor is Theorem 2 (Optimal Collusion), proved in this paper. There is no named hardness result to anchor on. Theorem 2 says that, for a multi-unit VCG auction with diminishing marginal valuations and a specified coalition that can make side payments, Algorithm 2 computes a manipulation maximizing the coalition’s *total* utility. The algorithm preserves the coalition’s truthful total number of items, sorts all the coalition members’ marginal values, has one member report the highest \(q_C\) values followed by zeros, and has the other colluders report zeros. The paper’s sorting and VCG computations run in polynomial time. The result concerns the underlying collusion problem, not merely the algorithm’s encoding.
A continuous mirror I would put to the authors is Atomless Multi-Unit VCG Collusion. Fix a maximum demand \(K\). A type \(\theta\) is a complete diminishing-marginal valuation schedule \(v_\theta(0),\ldots,v_\theta(K)\), with rational values and \(v_\theta(0)=0\). The population is a distribution \(\mu\) over a finite set \(\Theta\) of such types. A designated coalition is a subdistribution \(\nu\leq\mu\). The auction sells \(\rho\) identical units per capita, for \(0<\rho<K\). Thus a sequence of finite auctions with \(N\) bidders has about \(\mu_\theta N\) bidders of each type and \(\rho N\) items: the number of bidders grows while the number of distinct types stays small.
The coalition’s action is a report flow \(\pi_{\theta,b}\): mass of true type \(\theta\) that reports diminishing-marginal bid schedule \(b\), with \(\sum_b\pi_{\theta,b}=\nu_\theta\). Noncolluders report truthfully. The mechanism allocates the top \(\rho\) mass of reported marginal units. At a tied cutoff, it splits the tied mass symmetrically, so individuals still receive integral bundles while type-level averages may be fractional. Define payments by the high-multiplicity limit of finite-auction VCG payments: each allocated unit costs the common outside marginal value \(p\) at the clearing cutoff. The question is to find a report flow maximizing the coalition’s aggregate true utility,
\[
\sum_{\theta,b,k}\alpha_{\theta b k}\bigl(v_\theta(k)-pk\bigr),
\]
where \(\alpha_{\theta b k}\) is the mass of colluders of true type \(\theta\) who report \(b\) and receive \(k\) units under the induced allocation and tie rule. A solution is an optimizing report flow, its resulting allocation and cutoff price, and the coalition’s utility gain over truthful reporting.
This is a credible high-multiplicity regime for auctions of standardized permits or capacity units among many facilities or retailers: many bidders can share the same demand schedule because they belong to the same operational class, while the auction still concerns identical units and collusion over VCG reports. Side payments and joint utility remain central to the paper’s question. The mirror does co-modify supply to scale with population size; that is necessary to keep the multi-unit allocation meaningful as the population grows.
I expect this problem to be tractable, likely by reducing the strategic choice to a finite set of marginal-demand breakpoints and optimizing mass assignments over them. The input has only \(\tau\) true types and \(K\) marginal slots per type, even when the underlying auction has many bidders. Establishing that arbitrary reports cannot profitably exploit additional cutoff values is a key open step in that prediction. The paper’s theorem motivates the question; it does not prove this continuous result.
The weakest point is the change in the coalition’s structure. Theorem 2’s proof merges the coalition’s marginal lists into one proxy bidder. An atomless population has no bidder with positive mass, and its VCG payments are the limit of many small externalities. So the proxy argument does not carry over automatically. Allowing colluders to split their mass across reports keeps the mirror faithful to coordinated reporting, but means the optimal strategy could differ from the paper’s single-proxy strategy. The mirror covers Theorem 2’s optimal-collusion result; it does not continuize the paper’s core, Shapley-value, or other cooperative-game results. It also leaves open the finite-auction convergence rate and whether coalitions whose share vanishes with population size can still gain meaningfully.
The strongest objection is a mismatch between Theorem 2’s proxy and the proposed atomless limit. The theorem’s key move is to put the coalition’s merged marginal schedule on one bidder. In the proposed model, each bidder’s demand is capped at \(K\), while that proxy may represent demand from a coalition whose size grows with the population. As the population grows, the proxy has vanishing mass but can still affect the auction at scale. A mass distribution over ordinary bounded-demand types does not record that singular bidder.
There are two ways to address this, and each changes the model. Keep the proxy, and the auction contains a strategically important individual that the atomless society omits. Spread its report across a positive mass of colluders, and the question becomes how that coalition can manipulate the limiting cutoff through a report flow. That is coherent, but its connection to the paper’s proxy result needs a finite-to-continuous argument; the common-price payment rule alone does not establish one.
This is a real requirement for a strong mirror, but it does not defeat the better version. The programme permits a natural co-modification of the model, and a coalition of many facilities or retailers with shared valuation schedules is a plausible high-multiplicity setting. A designated coalition can be represented as a subdistribution, with coalition membership included in the relevant type description. The coalition’s aggregate utility is the objective, and the paper already permits item and money transfers, so individual bundle identity need not be retained. The resulting optimization over coordinated reports is a worthwhile computational question even if its optimal strategy differs from the single-proxy strategy.
I do not see a stronger objection in the supplied material. Theorem 2 is a named computational result; auction bidders can plausibly repeat across valuation types; and the atomless limit need not make the coalition’s price effect vanish when a positive mass coordinates. The honest negative case is therefore weak: proponents still owe a precise limit model and a dictionary connecting its payments and coalition value to finite VCG auctions, especially at tied or discontinuous cutoffs. That is a substantive proof obligation, but it does not show that no worthwhile mirror exists. Theorem 2’s anchor survives.
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.