| paper | d4-conf-sigecom-2008-0016 |
| 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: Polynomial-time solvable by an exact rational linear program. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite rational value set \(V=\{v_1>\cdots>v_\tau\ge 0\}\), a unit-mass society with distribution \(\mu\in\Delta(V)\), per-capita supply \(\rho\in(0,1)\), a finite menu of symmetric strategyproof and individually rational unit-demand rules with rational per-capita rank functionals \(U_j(q)\) and \(P_j(q)\), and a finite rational basis of report-independent rebate functionals \(B_k(q)\), choose a lottery \(\lambda\in\Delta_t\), a nonnegative rebate \(R(q)=\sum_k\theta_k B_k(q)\), and the largest \(\alpha\). Require, for every \(\mu\in\Delta(V)\), that \(R(q_\mu)\ge 0\), \(\sum_j\lambda_jP_j(q_\mu)\ge R(q_\mu)\), and \(\sum_j\lambda_j(U_j(q_\mu)-P_j(q_\mu))+R(q_\mu)\ge\alpha W_\rho(\mu)\), where \(q_\mu\) is the nonincreasing value quantile and \(W_\rho(\mu)=\int_0^\rho q_\mu(s)\,ds\). Return the optimal lottery, rebate, and guaranteed ratio.
A mass-one population of unit-demand agents has finitely many value types and a distribution \(\mu\); supply is \(\rho\) units per unit mass. Each agent receives at most one indivisible unit, while type-level allocation averages may be fractional. Choose among a finite menu of rank-based mechanisms and rebate functionals to maximize worst-case welfare relative to the efficient allocation benchmark. An atomless agent’s report leaves \(q_\mu\) unchanged, so the aggregate rebate is report-independent; direct truthfulness still governs each agent’s own allocation and payment.
When efficient VCG is absent, a common aggregate rebate still makes rebate choice nonbinding, reducing the problem to menu-dependent maximin allocation quality; the proponent addresses the VCG-in-menu case but not this broader collapse.
fatal: False
The mirror covers Theorem 1’s finite-menu mechanism and rebate optimization for unit-demand auctions with finitely many value types. It leaves the WCO characterization, the burning, partition, and generalized partition results, and their conjectures untouched. The paper’s own continuous model means fractional mixtures over mechanisms, not a continuous population.
The strongest positive case is narrow: the paper’s Theorem 1, proved here, gives an algorithmic anchor for optimizing over a finite menu of allocation mechanisms and redistribution rules. It does not give a hardness result. Its “continuous model” means that mixture probabilities over mechanisms may be fractional; it does not mean that the bidder population is continuous.
Theorem 1 says that, for fixed \(n>m\) and a finite menu of linear allocation mechanisms \(M_1,\dots,M_t\), the best competitive ratio can be found by a finite LP when mixtures are allowed and by a finite MIP when the mechanism must be a single menu member. The programs use variables for the mixture probabilities, \(\alpha\), and \(n\) redistribution values \(R_0,\dots,R_{n-1}\). Instead of checking every bid vector, they check the \(n+1\) profiles with \(z\) top bids equal to \(1\) and all others \(0\). The theorem proves that an optimal solution to these reduced programs extends to a feasible mechanism for every bid profile, using an explicit interpolation formula for the redistribution rule. The paper then uses the method to compute mechanisms. This is a formulation-and-computation result, rather than a stated polynomial-time classification in the high-multiplicity input size.
My lead mirror is *Atomless Linear-Menu Redistribution Design*. A society has mass \(1\), a finite set of rational value types \(V=\{v_1>\cdots>v_\tau\ge 0\}\), and a distribution \(\mu\) over those types. Its supply is \(\rho\in(0,1)\) units per unit of population mass. Write \(q_\mu(s)\) for the nonincreasing value quantile, ordered from highest to lowest. The perfect-allocation benchmark is
\[
W_\rho(\mu)=\int_0^\rho q_\mu(s)\,ds.
\]
The instance also specifies a finite menu \(M_1,\ldots,M_t\) of symmetric, strategyproof, individually rational unit-demand allocation rules, together with rational formulas for their per-capita efficiency \(U_j(q)\) and revenue \(P_j(q)\). These are linear rank-based functionals, such as the continuum versions of allocating to the highest-valued mass up to a quota. A finite rational basis specifies the permitted rank-based rebate functionals \(\mathcal R(q)\).
The task is to choose a lottery \(\lambda\in\Delta_t\), a permitted rebate \(\mathcal R\), and the largest \(\alpha\) such that, for every distribution \(\mu\) over \(V\),
\[
\mathcal R(q_\mu)\ge 0,\qquad
\sum_j\lambda_jP_j(q_\mu)\ge\mathcal R(q_\mu),
\]
and
\[
\sum_j\lambda_j\bigl(U_j(q_\mu)-P_j(q_\mu)\bigr)+\mathcal R(q_\mu)
\ge \alpha W_\rho(\mu).
\]
The solution is the mechanism lottery, rebate rule, and guaranteed competitive ratio. In the atomless model, removing one tagged agent leaves \(q_\mu\) unchanged, so the common rebate is independent of that agent’s report. The strategyproofness requirement still applies to each agent’s allocation and payment rule.
A plausible regime is a large permit or voucher market with a fixed supply rate, many households, and a small set of standardized reservation-value classes. The type is the household’s value class; \(\mu_v\) is the fraction of households in class \(v\); the mechanism chooses how much mass in each rank range receives a unit and how much revenue to return. The paper’s menu restriction is preserved, while \(n\) and \(m\) scale together and the benchmark becomes welfare per capita.
I expect this mirror to be Class A when the mechanism and rebate kernels have a fixed number of rational breakpoints: the theorem’s threshold-profile argument suggests a finite separation problem over value quantiles. Establishing a polynomial-size reduction in \(\tau\), the menu size, and the encoding length would be new work. The question also generates a finite-to-continuous dictionary: how do the optimized ratios behave when a society with masses \(\mu\) is represented by \(N\) agents and \(N\mu_v\) agents have each value type?
The scope is Theorem 1’s menu-restricted competitive mechanism-design problem. It does not cover every mechanism in the paper or supply a continuous analogue of a hardness result.
The weakest point is substantial: in the atomless limit, a rebate based on everyone else’s reports can become the same for every agent. If the menu contains efficient VCG and its revenue is nonnegative, returning that revenue uniformly gives welfare equal to allocation efficiency. The finite-population tension between efficiency and redistribution can therefore disappear, making the mirror much easier than the paper’s problem. The positive case survives as a precise continuum boundary question about the paper’s mechanism-design method; it is weaker as a claim that the paper’s central tradeoff persists unchanged.
Theorem 1 is a real computational anchor: it gives an exact LP/MIP reduction for a finite menu of linear allocation mechanisms. So the negative case cannot rest on saying the paper has no algorithmic result.
The problem is that the theorem’s mechanism-design tension is sensitive to having a finite population. In an atomless society, one agent’s report does not change the aggregate distribution. That makes an equal rebate based on the society’s aggregate revenue independent of that agent’s report. With supply \(\rho\) per unit mass and cutoff price \(p\), efficient VCG allocation serves the highest-valued mass and collects per-capita revenue \(\rho p\). Rebate \(\rho p\) to every agent: the aggregate rebate equals the revenue, the rebate is report-independent, and truthful reporting at the fixed cutoff remains optimal. Individual rationality holds, and welfare equals the efficient allocation benchmark \(W_\rho(\mu)\). Thus \(\alpha=1\) whenever the menu includes the natural efficient VCG rule. The optimization over rebates, central to the proposed mirror, has disappeared.
The finite-menu escape does not fully restore the theorem’s subject. If the menu excludes VCG, full rebate still turns welfare into allocation efficiency for mechanisms with nonnegative revenue. The remaining task is to choose a lottery over that particular menu to maximize worst-case allocation quality. That can be a well-posed continuous-population problem, but its difficulty comes from the chosen menu and its growing description, rather than from the paper’s rebate-design result. Theorem 1’s \(n+1\) threshold profiles and \(n\) rebate variables arise from finite order statistics and leave-one-agent-out constraints; in the atomless model those constraints collapse. To preserve their bite, one could make positive-mass cohorts strategic players, but then a cohort acts as a bloc rather than representing many independently strategic agents. Keeping individual pivotality instead requires retaining finite granularity.
There is a genuine limit to this negative case: a carefully chosen family of inefficient mechanisms, such as scaled partition rules, might yield an interesting continuous maximin allocation problem. I cannot honestly show that every such question is worthless. But that would need its own computational motivation and analysis; it does not rescue the proponent’s mirror as stated. Its natural version either has the efficient mechanism and a uniform rebate, making the optimum \(1\), or excludes that mechanism and turns the result into a different, menu-specific allocation problem.
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.