| paper | d4-journals-jair-2011-0023 |
| 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: Polynomial-time solvable. The optimal value, an optimal limiting redistribution law, and universally feasible exact finite strategyproof lifts are computable in polynomial time. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a rational supply ratio \(0<\rho<1\), a rational nonincreasing piecewise-constant slot-quality schedule \(\gamma:[0,\rho]\to\mathbb{R}_{\ge0}\) with its terminal drop to zero, and at most \(\tau\) scalar value types, characterize and compute the optimal limiting redistribution law. At each resolution \(N\), there are \(N\) unit-demand agents and \(p_N/N\to\rho\) slots whose qualities approximate \(\gamma\); choose anonymous Groves rebates \(r_i^N=f_N(\mathbf v_{-i})\) that are individually rational and feasible for every profile. Maximize \(\liminf_{N\to\infty}\inf_{\mathbf v:S_N>0}\sum_i r_i^N/S_N\), over profiles using at most \(\tau\) value types, and give exact finite strategyproof lifts of the limiting law.
A society has mass \(\mu_v\) of advertisers of each scalar type \(v\), supported on at most \(\tau\) types. Slot rank \(s\in[0,\rho]\) has quality \(\gamma(s)\); a mass assignment couples advertiser types to slot capacity and maximizes \(\int v\gamma(s)\,dx\). The designer chooses a limiting rebate law, represented by a coefficient measure \(A\), whose finite-resolution Groves rebates depend only on other agents’ reports and satisfy DSIC, feasibility, and individual rationality. The objective is the worst-case limiting share of Clarke surplus returned to agents.
The finite problem is already an explicit LP, so the mirror’s computational contribution depends on whether its limit admits a useful representation or efficient separation method; the case identifies this as open but does not show that the limit creates a substantial new obstacle.
fatal: False
The mirror extends Theorem 4’s scaling-based, scalar-value setting to supply proportional to population and studies its limiting optimal rebate law. It leaves Theorem 3’s unrestricted multidimensional impossibility, Theorem 5’s general heterogeneous-value guarantee, and HETERO’s conjectures and simulations aside.
The best case is that this paper gives a real opening for a population mirror in mechanism design. Its central object is already an aggregate guarantee: how much of the VCG surplus can be returned across all reported profiles while preserving efficiency, truthfulness, feasibility, and individual rationality. Those properties translate naturally into constraints on a population distribution and its mass assigned to resource types.
The paper has no named NP-hardness or other complexity-class result, so I would not claim a hardness anchor. Its strongest computational anchor is Theorem 4, proved here. For values with a scaling relationship, \(\theta_{ij}=\gamma_j v_i\), where \(\gamma_1\ge\cdots\ge\gamma_p>0\), it says that, when \(n>p+1\), the mechanism obtained by solving LP (11) is worst-case optimal among feasible, individually rational, deterministic, anonymous Groves redistribution mechanisms. The LP chooses the rebate coefficients to maximize the guaranteed fraction of Clarke surplus over all ordered signal profiles. The paper calls the resulting index nonzero; its discussion supports positivity by solving the LP for particular parameter settings, rather than by a general proof covering every \(n,p\). The theorem is an optimization result, not a polynomial-time complexity classification.
Here is a continuous question that keeps the strategic problem intact. Think of a large ad exchange with many small advertisers. Each advertiser wants at most one placement; its value for a placement is a common slot-quality factor times a scalar willingness to pay. Advertisers with the same scalar value are one type, and \(\mu_v\) is their share of the population. As the population grows, placement supply grows with it: a fraction \(\rho<1\) of the population can be served, with placement qualities approaching a nonincreasing schedule \(\gamma(s)\), \(0\le s\le\rho\). This is the permitted co-modification of supply: each placement remains a unit-demand assignment, while the number of placements scales with population.
At resolution \(1/N\), there are \(N\) agents, each of mass \(1/N\), and \(p_N/N\to\rho\) placements. A type \(v\) has value \(\gamma_{j,N}v\) for placement \(j\). The allocation decision is the mass \(x_{v,j}\) assigned from each type to each placement; it must maximize total value while assigning at most one placement to each agent. The mechanism designer chooses an anonymous rebate rule \(r_i^N=f_N(\mathbf v_{-i})\), independent of agent \(i\)’s own report, and seeks to maximize the worst-case ratio \(\sum_i r_i^N/S_N\), where \(S_N\) is total Clarke surplus. Every finite-resolution rule must satisfy \(r_i^N\ge0\) and \(\sum_i r_i^N\le S_N\).
The named mirror is Scaling-Based Continuous Optimal Redistribution. Its input is a rational, piecewise-constant quality schedule \(\gamma\), supply ratio \(\rho\), and a bound \(\tau\) on the number of distinct signal types. Its output is a family of leave-one-out rebate rules, exact at every \(N\), and their limiting rebate law, maximizing \(\liminf_{N\to\infty}\inf_{\mathbf v}\sum_i r_i^N/S_N\) over societies with at most \(\tau\) types. In a regular limit, the finite rebate coefficients \(c_{j,N}\) induce a coefficient measure \(A\); for a value quantile \(Q\), the limiting rebate per capita has the form \(\int_{[0,1]}Q(1-u)\,dA(u)\). The normalized Clarke surplus has the corresponding limit \(\int_{(0,\rho]}sQ(1-s)\,(-d\gamma(s))\), with the terminal drop of \(\gamma\) to zero included. A solution is the optimal limiting law and a proof that it has exact feasible, individually rational, strategyproof finite lifts. The underlying question is optimal redistribution for a population with scaling-related values; the measure and LP are ways to represent and compute its answer.
I would expect this to be a Class A candidate: the paper’s ordering argument reduces its finite problem to an LP, and a bounded number of value types suggests a compact set of quantile constraints. What remains to prove is that the finite LPs have a useful limit, that the limiting constraints can be separated efficiently, and that the algorithm runs in \(K,\tau,L\) and the schedule’s encoding size. Theorem 4 does not establish those facts.
A second, more general anchor is Theorem 5, proved here. Its Bailey–Cavallo mechanism rebates \(r_i=t_{-i}/n\), where \(t_{-i}\) is the Clarke surplus without agent \(i\). When \(n>2p\), it guarantees redistribution index at least \((n-2p)/n>0\): at most \(2p\) agents affect the Clarke surplus, so every other agent’s exclusion leaves that surplus unchanged. This is a proved lower bound, not an optimality theorem.
That result suggests Critical-Mass Redistribution for Heterogeneous Assignment. Let there be \(N\) agents and \(K\) object classes, with \(q_jN\) objects in class \(j\), total supply ratio \(\rho=\sum_j q_j<1/2\), and a society \(\mu\) over at most \(\tau\) complete valuation-vector types. The allocation variable \(x_{t,j}\) assigns mass of type \(t\) to class \(j\), subject to type-mass and supply limits, and maximizes welfare. At each finite resolution, use the exact Bailey–Cavallo rebate \(r_i=S_{N,-i}/N\). The problem is to compute its sharp worst-case limiting redistribution index over these societies and identify an attaining family of societies. Theorem 5 gives the baseline guarantee \(1-2\rho\); whether that bound is sharp in the stated type regime is the continuous question. With \(K\) and \(\tau\) bounded, I would expect a Class A route through mass-assignment and pricing formulations. It also prompts the further question of whether any mechanism approaches full redistribution in this regime.
The paper’s Theorem 3 marks the boundary rather than serving as a hardness anchor: on the unrestricted multidimensional domain, a feasible, individually rational, deterministic, anonymous DSIC linear rebate cannot have positive redistribution index. The scaling mirror avoids that domain by using complete types of the form \(\gamma v\); the Bailey–Cavallo mirror uses a nonlinear rebate. That restriction is exactly why these are plausible mirrors of the authors’ questions, rather than attempts to claim their impossibility result disappears.
My weakest point is the distinction between a population limit and a purely atomless mechanism. If an individual has zero mass, unilateral reports cannot change the aggregate, and DSIC can become vacuous. The mirrors above therefore require exact leave-one-out mechanisms at each finite resolution and study their high-multiplicity limit. That keeps the strategic content, but a referee could reasonably ask whether this is a continuous problem in its own right or an asymptotic family of finite ones. I think the authors would recognize it as a serious extension of their mechanism-design problem—especially since supply scaling and high multiplicity preserve the assignment and rebate questions—but the limit needs to earn that recognition with a nontrivial result.
The negative case is mainly about the programme’s fit, not whether a continuous model can be written down. The paper’s theorems are mechanism-design results, not complexity classifications. Theorem 4 gives an explicit LP with \(O(n)\) variables and constraints; Theorem 5 gives a rebate formula whose payments can be computed using assignment optimization. So their finite computational tasks already have standard polynomial-time formulations. A limit theory could be interesting, but the proponent’s proposed algorithmic questions do not expose a clear new complexity landscape.
Theorem 4 is still the strongest anchor. Its best mirror is coherent: scale supply with population, use complete scalar-value types, and study the limiting worst-case-optimal rebate law. But each finite member of that family is already solved by LP (11). The proposed continuous result would establish convergence and characterize the limit of those LP solutions. That is a legitimate asymptotic optimization problem, but the paper does not suggest a new computational obstacle for it. And the limiting rebate law cannot retain the original strategic content by itself: if one person has zero mass, changing their report does not change the society distribution. Requiring exact strategyproof finite lifts preserves that content, but makes the core object a sequence of finite mechanisms with a limit theorem attached.
Theorem 5 admits a sensible stronger mirror too: arbitrary complete valuation-vector types, object-class supplies scaled with population, and the sharp limiting worst-case redistribution index of Bailey–Cavallo. Its bound \(1-2\rho\) when \(p/N\to\rho<1/2\) gives the question real substance. Still, the result to compute is a performance guarantee for an already specified mechanism, not a new computational task identified by the paper. The mass assignment is a capacitated welfare optimization, and the finite rebates reduce to assignment calculations. The paper gives no reason to expect that taking the limit reveals a complexity boundary rather than a sharper analysis of a tractable mechanism. High multiplicity supports this mirror’s plausibility; I am not treating existing high-multiplicity work as a collision.
Theorem 3 is an especially poor computational anchor. It is an impossibility result for linear rebate functions, not a hardness result. In an atomless model, an individual’s report cannot affect the aggregate, so dominant-strategy truthfulness can become vacuous. One can define a nontrivial marginal or first-order incentive condition, but that changes the mechanism question. Or one can require exact finite lifts, in which case the impossibility is inherited from the finite models and the novel work is again about their asymptotics.
I would not claim these arguments rule out every worthwhile mirror. Theorem 4’s limit problem is plausible, and the population-scaled supply model is a reasonable co-modification. The strongest case against is narrower: these anchors support asymptotic mechanism analysis, but none clearly opens the computational complexity programme this paper might otherwise seem to invite. That is a weak negative verdict; a reader who counts a new limit theorem for the optimal LP as enough could reasonably reject it.
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.