| paper | d4-conf-sigecom-2007-0021 |
| 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: \(\kappa^*=1\). The unique optimal rule is \(r^*(\mu)=\alpha p_\alpha(\mu)\) for every rational distribution. Construction and support-based evaluation are polynomial-time; every guarantee \(\kappa\in[0,1]\) is achievable. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given rational \(\alpha\in(0,1)\), a finite value set \(V\), and a rational distribution \(\mu\) over \(V\), allocate mass \(\alpha\) to the highest values, splitting ties as needed, and charge winners the cutoff value \(p_\alpha(\mu)\) per unit. Among deterministic anonymous strategyproof VCG-rebate rules that return the same per-capita rebate \(r(\mu)\) to all agents and satisfy \(0\le r(\mu)\le\alpha p_\alpha(\mu)\), maximize \(\kappa\) subject to \(r(\mu)\ge\kappa\alpha p_\alpha(\mu)\) for every \(\mu\); what is the optimal rule and how efficiently can it be computed from the support?
A unit-demand auction with a continuum of agents whose values follow a finite-support distribution \(\mu\), and capacity equal to the fraction \(\alpha\) of the population. The decision is an anonymous per-capita VCG rebate rule; the objective is its worst-case fraction of per-capita VCG revenue, \(\alpha p_\alpha(\mu)\).
The mirror covers the worst-case optimal redistribution objective and mechanism in Theorems 1 and 2. It leaves aside the finite coefficient constraints, Bailey–Cavallo comparisons, and finite-population impossibility of strong budget balance.
The strongest honest case is a large cooperative auction for a scarce shared resource: many residents want one unit of access each, such as a charging slot or a use-right for a community-owned asset. Residents with the same value and other mechanism-relevant features form a type. There are many residents but relatively few types, and the number of available units grows with the population: \(m/n\to\alpha\), with \(0<\alpha<1/2\) as the clearest scarce-capacity regime. The society is a distribution \(\mu\) over value types, and mass is the fraction of residents of each type.
The paper has no named NP-hardness or standard complexity-class result. Its useful anchors are exact optimization results, both proved here. Theorem 2 is my lead. It says that, for \(n\ge m+2\), the worst-case-optimal mechanism from the paper’s linear VCG-redistribution family is also worst-case optimal among all deterministic, anonymous, strategy-proof, efficient VCG-redistribution mechanisms satisfying no deficit. The result still holds if individual rationality is dropped. Theorem 1 gives the mechanism within the linear family: for \(n\ge m+2\), it is unique, its worst-case redistributed fraction is
\[
k^*=1-\frac{\binom{n-1}{m}}{\sum_{j=m}^{n-1}\binom{n-1}{j}},
\]
and, for \(i=m+1,\ldots,n-1\), its coefficients are
\[
c_i^*=
\frac{(-1)^{i+m-1}(n-m)\binom{n-1}{m-1}}
{i\left(\sum_{j=m}^{n-1}\binom{n-1}{j}\right)\binom{n-1}{i}}
\sum_{j=i}^{n-1}\binom{n-1}{j}.
\]
The paper’s Claim 1 also establishes \(c_i=0\) for \(i\le m\).
I would pose the continuous counterpart of Theorem 1 as Linear-Quantile VCG Redistribution\(_\infty\). Its design instance is a capacity share \(\alpha\) and a finite set of possible values; an evaluation society is a rational distribution \(\mu\) over those values. Let \(p_\alpha(\mu)\) be the value at the cutoff immediately below the top \(\alpha\) mass—the continuum counterpart of the \((m+1)\)st-highest bid. A linear rank rule is specified by a finite signed measure \(\lambda\) on rank fractions \(u\in(0,1)\); it rebates each unit of population mass
\[
r_\lambda(\mu)=\int Q_\mu(u)\,d\lambda(u),
\]
where \(Q_\mu\) is the descending value quantile. The question is to choose \(\lambda\) maximizing \(\kappa\), subject to \(0\le r_\lambda(\mu)\le\alpha p_\alpha(\mu)\) and \(r_\lambda(\mu)\ge\kappa\alpha p_\alpha(\mu)\) for every society. This is the rank-coefficient vector becoming a quantile-weight rule. The solution \(\lambda=\alpha\delta_\alpha\) gives \(r_\lambda(\mu)=\alpha p_\alpha(\mu)\), hence \(\kappa=1\). It can be evaluated by sorting the \(\tau\) supported values, in time polynomial in \(\tau\) and their encoding length.
The counterpart of Theorem 2 is Anonymous VCG-Rebate\(_\infty\). Given the same capacity share and value domain, choose any deterministic anonymous VCG rebate rule \(r:\mu\mapsto r(\mu)\) that preserves the efficient allocation, is strategy-proof, and never runs a deficit. Maximize the worst-case fraction \(\kappa\) of VCG revenue returned, meaning \(r(\mu)\ge\kappa\alpha p_\alpha(\mu)\) for every \(\mu\), while \(r(\mu)\le\alpha p_\alpha(\mu)\). The solution is again \(r(\mu)=\alpha p_\alpha(\mu)\), with \(\kappa=1\). Since population mass is normalized to one, the VCG revenue per unit of population is \(\alpha p_\alpha(\mu)\). Rebating that amount to every resident returns it all. In an atomless society a single resident’s report does not change \(\mu\), the cutoff, or the rebate; the remaining allocation and payment are the VCG ones. The rule is anonymous, non-deficit, and individually rational because the added rebate is nonnegative.
Both mirrors fall on the tractable side: the full-population problem has a closed-form rule, and evaluating it is polynomial in the support size. The match to the paper is concrete: the object being redistributed is still multi-unit VCG revenue, the objective is still worst-case redistribution, and the linear-family version replaces ranks of other bids with population quantiles. This does not claim the paper has a hardness result that dissolves; it asks whether its mechanism-design optimization becomes simpler when agents have zero individual mass.
The weak point is exactly that zero-mass assumption. In the finite paper, one bidder can be pivotal at rank \(m+1\); in the atomless model, no individual can move the cutoff. Thus the continuous rule may be a natural large-market version of their mechanism-design question, but it can erase the strategic constraint that makes the finite problem interesting. In the scarce regime \(m/n\to\alpha<1/2\), Theorem 1’s formula is consistent with the optimal guarantee tending to \(1\). For \(\alpha>1/2\), its proportional-supply limit is instead \((1-\alpha)/\alpha\), so a full-rebate continuum answer would not represent the finite worst case uniformly across regimes. That boundary is a further question, not a reason to reject the scarce-capacity mirror: the authors should recognize it as their VCG redistribution objective in a specific high-multiplicity market, with the change in individual pivotality made explicit.
The paper’s numbered results do not establish a complexity bound or classify a computational problem. Theorem 1 characterizes an optimal redistribution rule; Theorem 2 proves its economic optimality beyond the linear family. The LP is a way to derive the rule, not a complexity result. That leaves little for ChoCo’s computational-complexity programme to mirror.
The proposed continuous versions of both theorems expose the deeper problem. With capacity share \(\alpha\) and cutoff value \(p_\alpha(\mu)\), the per-capita VCG revenue is \(\alpha p_\alpha(\mu)\). In an atomless society, rebate that amount to every resident. A single resident’s report does not change \(\mu\), the cutoff, or the rebate, so the rebate creates no incentive to misreport; the VCG allocation and payment retain their usual incentive property. The total rebate exactly matches revenue, and the added rebate is nonnegative. Thus the guarantee is \(1\) for every society.
That result is a degeneration of the paper’s central design constraint. In the finite auction, a bidder can move the cutoff, and the leave-one-out rebates must respect that strategic effect while satisfying no deficit. In the atomless model, an individual has no effect on the aggregate. Theorem 2’s comparison among mechanisms and Theorem 1’s rank coefficients—including Claim 1’s finite constraints on those coefficients—therefore lose their work. The proposed \(\lambda=\alpha\delta_\alpha\) is a valid description of the full rebate, but it captures precisely why the finite optimization disappears.
The strongest rescue would retain finite pivotality while studying a large market, perhaps through a finite-size correction or a sequence with \(1/n\)-mass agents. That keeps the leave-one-out incentive constraints and returns to the finite problem; the continuous distribution summarizes its reports. Theorem 1 already supplies the exact finite optimum whose asymptotics one could study. Treating positive-mass cohorts as strategic agents instead changes the model to strategic blocs, rather than the paper’s anonymous unit-demand bidders.
I cannot rule out an author finding the atomless full-rebate limit economically illuminating. The negative case is strongest on programme fit: it gives a simple large-market observation, while the strategic and computational problem that makes this paper distinctive vanishes in the limit.
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.