| paper | d4-conf-wine-2008-0064 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: \(\mathrm P\) · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite value set \(V\), a society distribution \(\mu\) over \(V\), slot-quality classes with per-capita capacities \(\kappa_j\), and qualities \(\alpha_1\ge\cdots\ge\alpha_q>0\), choose a rank-weight measure \(\lambda\) to maximize \(e\) subject, for every \(\mu\), to \(0\le R_\lambda(\mu)\le T_a(\mu)\) and \(R_\lambda(\mu)\ge eT_a(\mu)\), where \(R_\lambda(\mu)=\int_0^1 Q_\mu(u)\,d\lambda(u)\) and \(T_a\) is the per-capita limit of finite-auction Clarke surplus. Define tagged-agent allocation and payment by the corresponding finite-agent limit and require unilateral DSIC.
A nonatomic assignment market with types \(v\in V\), mass \(\mu_v\), and slot-class capacities \(\kappa_j\) per unit population; the decision is the rank-weight measure \(\lambda\), the objective is worst-case redistribution fraction \(e\), and individual VCG utility is defined by a tagged-agent finite-market limit.
The per-capita surplus \(T_a(\mu)\) does not by itself specify a tagged agent’s allocation and VCG transfer: literal zero-mass removal has zero effect, so those utilities need a finite-agent or first-variation limit.
fatal: False
The mirror covers Theorem 4’s worst-case-optimal linear redistribution result under scaling-based correlation. It leaves the independent-vector impossibility in Theorem 2 and the nonlinear BAILEY result in Proposition 1 aside.
The strongest mirror is nonatomic optimal linear redistribution for scaling-correlated slot assignment. It is a tractability anchor, not a hardness one: the paper has no named NP-hardness result. Its best computational anchor is Theorem 4, whose LP is actually used to compute an optimal mechanism.
Theorem 4, proved in this paper, says that when each agent’s value for object \(j\) is \(\alpha_jv_i\), with \(\alpha_1\ge\cdots\ge\alpha_p>0\), and \(n>p+1\), solving LP (9) gives a linear redistribution mechanism that is worst-case optimal among all feasible, individually rational, deterministic, anonymous Groves redistribution mechanisms. Its objective is to maximize the worst-case fraction of Clarke surplus rebated. The theorem’s significance for computation is the LP formulation of this underlying mechanism-design problem; I am not treating the LP itself as the mirror question.
A natural high-multiplicity setting is online advertising. There are \(N\) advertisers but only \(\tau\) distinct values per click, with \(\tau\ll N\). An advertiser’s complete type is their value \(v\); their value for a slot of quality \(\alpha_j\) is \(\alpha_jv\). Let there be \(q\) quality classes, with \(\alpha_1\ge\cdots\ge\alpha_q>0\), and \(\kappa_jN\) slots in class \(j\). Thus the slot supply scales with the population, a necessary per-capita co-modification. In the limit, society is a distribution \(\mu\) over a finite set \(V\) of values, and class \(j\) has capacity \(\kappa_j\) per unit mass. The population, not the outcomes, is the continuous object.
Here is the lead problem, stated as something a prover could take as given. For each \(v\in V\) and slot class \(j\), choose assigned mass \(x_{vj}\ge0\), with \(\sum_jx_{vj}\le\mu_v\) and \(\sum_vx_{vj}\le\kappa_j\); the allocation maximizes \(\sum_{v,j}\alpha_jv x_{vj}\). Let \(\rho=\sum_j\kappa_j<1\), \(s_j=\sum_{h\le j}\kappa_h\), and \(Q_\mu(u)\) be the descending quantile of advertiser values. The per-capita Clarke surplus is
\(T_a(\mu)=\sum_{j<q}s_j(\alpha_j-\alpha_{j+1})Q_\mu(s_j)+\rho\alpha_qQ_\mu(\rho),\)
where the quantiles at the cutoffs denote the marginal advertiser there, using the common value when there is a tie.
Now choose a fixed rank-weight measure \(\lambda\) and give every infinitesimal agent the rebate \(R_\lambda(\mu)=\int_0^1Q_\mu(u)\,d\lambda(u)\). This is linear in the rank-ordered type profile, the continuum counterpart of the paper’s linear rebate rule. The question is to maximize \(e\) subject to \(R_\lambda(\mu)\ge0\), \(R_\lambda(\mu)\le T_a(\mu)\), and \(R_\lambda(\mu)\ge eT_a(\mu)\) for every \(\mu\). The solution is \(\lambda=\omega_a\), where \(\omega_a=\sum_{j<q}s_j(\alpha_j-\alpha_{j+1})\delta_{s_j}+\rho\alpha_q\delta_\rho\). It gives \(R_\lambda(\mu)=T_a(\mu)\) for every society, so the optimum is \(e=1\), which feasibility makes an upper bound. The rebate is nonnegative, returns exactly the VCG surplus, and is independent of any one zero-mass agent’s report; the VCG allocation and payments therefore retain unilateral DSIC in this nonatomic model. This is a tractable answer to the same underlying design question as Theorem 4: how to rebate VCG payments while preserving efficiency, incentives, feasibility and individual rationality.
The result covers the paper’s scaling-based-correlation mechanism-design result, not its general independent \( \mathbb{R}_+^p \) impossibility claim. It also raises concrete follow-up questions: does the optimum of the paper’s finite LPs converge to this value as \(N\) grows, at what rate, and what happens when incentive constraints include deviations by a positive mass of agents?
The weak point is the incentive model. In a nonatomic society, an individual report does not change \(\mu\), so individual DSIC puts little pressure on an aggregate rebate rule. The full-redistribution result depends on that limit and may fail under coalition or positive-mass deviation requirements. I still think this is a credible mirror: the scenario is natural for high-volume advertising, the rebate-design objective is unchanged, and the population limit exposes a precise question about how the finite optimal LP behaves.
Theorem 4 is the strongest anchor, and the advertising scenario is credible: many advertisers can share one of a small number of values per click, while slot supply scales with the population. The weakness is what happens to the incentive constraint in that limit.
In the finite mechanism, agent \(i\)’s rebate must depend only on the other agents’ bids. That restriction matters because changing \(i\)’s bid can change the total Clarke surplus. In the proposed atomless model, changing one agent’s report leaves \(\mu\) unchanged. So any rebate defined from \(\mu\)—including \(R_\lambda(\mu)\)—is automatically independent of that report. The constraint that makes finite rebate design difficult has disappeared. Setting the common rebate to the society’s per-capita Clarke surplus then exhausts the budget by construction; the result reflects the vanished unilateral influence, rather than a continuous optimization analogue of the paper’s finite mechanism-design problem.
There is a related modeling seam. Under a literal continuum VCG rule, removing one zero-mass agent changes neither the allocation nor the welfare of the rest, so that agent’s pivotal payment is zero. The proposed positive \(T_a(\mu)\) instead comes from taking the limit of the *aggregate* payments in finite auctions and dividing by population size. That is a reasonable limit convention, but it needs a tagged-agent interpretation to define each person’s allocation and payment. With that convention, unilateral DSIC can still be checked, but the rebate constraint remains vacuous because the tagged agent does not change \(\mu\). Requiring deviations by positive mass could restore a binding constraint, but it changes the incentive notion from the paper’s individual DSIC.
The best salvage is therefore a finite-to-limit question: whether the paper’s optimal LPs converge to this atomless benchmark, and how quickly. That could be mathematically worthwhile, but it is a convergence result about a solved finite LP, not a new continuous rebate-design problem with the paper’s operative incentive tension. My negative case is narrow: the population regime is natural and the mirror is formally writable; the objection is that the atomless limit removes the constraint that made Theorem 4’s problem nontrivial.
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.