| paper | d4-conf-wine-2012-0015 |
| 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: \(\inf_M\rho(M)=e/(e-1)<2\), attained by a truthful, individually rational, budget-feasible mechanism computable in polynomial time. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a rational distribution \(\mu\) over complete types \(t=(a_t,d_t,v_t)\), with public predictor coefficient \(a_t\), verified data value \(d_t\), and private unit cost \(v_t\), consider direct mechanisms that observe cost reports and assign each user an inclusion probability and expected scaled transfer. Require dominant-strategy truthfulness and individual rationality for each user, and integrated transfers within budget \(B\). For \(\theta_t\in[0,1]\), define residual weight \(R=\sum_t\mu_t|a_t|(1-\theta_t)\); selected users incur privacy cost \(v_t|a_t|/R\). What is the best worst-case approximation ratio for maximizing \(\sum_t\mu_t|a_t|\theta_t\), relative to the cost-aware benchmark \(\mathrm{OPT}=\max_{\theta\in[0,1]^\tau}\{\sum_t\mu_t|a_t|\theta_t:\sum_t\mu_t|a_t|(v_t+B)\theta_t\le B\sum_t\mu_t|a_t|\}\), and can a truthful mechanism achieve a ratio below \(2\)?
A large recommender-system population represented by mass \(\mu_t\) over types with shared data, predictor coefficients, and privacy costs. The estimator selects each user with probability \(\theta_t\), has Laplace scale \(\sigma=\Delta R\), and makes per-user transfers subject to aggregate budget and pointwise truthfulness.
Each user has zero mass, so the paper’s pivotality and payment-threshold argument does not transfer; the proponent acknowledges the binary four-user step but leaves the per-user allocation and payment rule for fractional \(\theta_t\) unspecified.
fatal: False
The mirror covers Theorem 4’s approximation barrier. It leaves Theorems 1 and 2’s privacy-distortion results and Theorem 3’s mechanism guarantee outside the proposed question.
The strongest mirror is the paper’s truthful privacy-auction problem in the large-user regime it already motivates: a recommender system with millions of records, where many users share a public similarity-weight class, a rating from a finite scale, and a privacy-cost tier. A complete type is \(t=(a_t,d_t,v_t)\): predictor coefficient, verified data value, and true unit privacy cost. If there are \(N\) users and only \(\tau\) such types, with \(N\gg\tau\), mass \(\mu_t\) is the fraction of users of type \(t\). Repeated ratings and standardized privacy tiers make this a plausible instance regime, even though it need not describe every platform.
My lead is Continuum Truthful DCLEF Approximation. Give the prover a finite support of rational masses \(\mu_t\), data values \(d_t\in I\), coefficients \(a_t\ne0\), hidden costs \(v_t>0\), and budget \(B\). Think of each user’s original predictor weight as \(a_t/N\), so the target is the per-capita predictor \(s=\sum_t\mu_t a_t d_t\). The mechanism elicits users’ costs and chooses a measurable subset of users to include in the estimator; within a type, it may select any fraction \(\theta_t\in[0,1]\) of the mass. For selected mass, the DCLEF noise scale is
\[ \sigma(\theta)=\Delta\sum_t\mu_t|a_t|(1-\theta_t), \]
and the estimator is the selected users’ weighted data, the midpoint contribution of the unselected users, and Laplace noise with scale \(\sigma(\theta)\). This keeps the paper’s estimator and privacy-cost model while making the population continuous.
For a precise budget convention, scale each individual payment by \(N\), writing it as \(q\). A selected type-\(t\) user then has scaled privacy cost \(v_t\Delta|a_t|/\sigma(\theta)\); total scaled payments are integrated over the selected mass and must be at most \(B\). The mechanism must be dominant-strategy truthful for each user’s cost report, individually rational, and budget feasible. Its objective is to maximize selected predictor weight \(\sum_t\mu_t|a_t|\theta_t\), equivalently to minimize worst-case DCLEF distortion. The benchmark \(\mathrm{OPT}\) is the maximum of that objective with costs known, subject to budget feasibility. Explicitly,
\[ \mathrm{OPT}=\max_{\theta\in[0,1]^\tau}\sum_t\mu_t|a_t|\theta_t \quad\text{subject to}\quad \sum_t\mu_t|a_t|(v_t+B)\theta_t \le B\sum_t\mu_t|a_t|. \]
The question is to determine the best worst-case approximation ratio of truthful mechanisms for this continuous instance, in particular whether a ratio strictly below \(2\) is achievable. The benchmark is a fractional optimization problem; the solution being sought is a truthful mechanism, not merely an allocation or an encoding.
The anchor is Theorem 4 (Hardness of Approximation), proved in this paper’s Appendix E. It states that for every \(\varepsilon>0\), no truthful, individually rational, budget-feasible DCLEF mechanism achieves a \((2-\varepsilon)\)-approximation relative to \(\mathrm{OPT}\), where \(\mathrm{OPT}\) is the best individually rational, budget-feasible DCLEF mechanism without a truthfulness requirement. The proof uses four equal-weight individuals: one has cost \(a<2\), three have cost \(2\), and the budget is \(1+a/2\). The nontruthful optimum selects the cheap individual and one other, for value \(2d\). A mechanism approaching a factor below \(2\) must select the cheap individual and at least one expensive one. Truthfulness forces the cheap user’s payment to cover the cost as their reported value approaches \(2\), requiring payment at least \(1\); then the budget cannot cover an expensive user, whose cost is at least \(1\). That contradiction proves the bound.
I expect the continuous question to be Class A for a useful approximation guarantee, although I would not claim the ratio is \(1\). The benchmark constraint above is linear, and divisible mass removes the particular “one more individual” step in the four-agent proof. This suggests room for fractional allocation and threshold payments to beat the discrete lower bound. The result would still be recognizably the authors’ problem: it buys the same data for the same prediction using the same privacy costs and estimator, while asking whether truthfulness and budget feasibility permit a better guarantee when the users form large repeated cohorts. The mirror covers Theorem 4’s approximation barrier.
The weak point is that Theorem 4 is a mechanism-design impossibility, not a standard complexity lower bound, and its proof turns on a small population with binary per-user inclusion. Its obstruction may have an integral analogue: threshold payments and the privacy externality could still enforce a factor-\(2\) barrier for fractional cohorts. I’m arguing that the continuum question is well-posed and plausibly tractable, not that the lower bound has already been overcome.
Theorem 4 is the only strong anchor here, and its obstacle is the strategic unit. The paper’s guarantee concerns named individuals: one person can change their report, affect the mechanism’s allocation, and trigger a payment threshold. The four-person construction depends on that pivotality. In the proposed mass model, each person’s weight is \(a_t/N\). A unilateral report then has vanishing effect on the aggregate allocation, noise scale, and budget. Truthfulness becomes a pointwise pricing condition in an atomless market; the paper’s lower-bound argument no longer transfers as stated.
The better versions expose a fork. If types are atomless users and truthfulness applies to each user, the mechanism is a continuous procurement auction whose incentives operate against aggregate quantities. That is a coherent question, but it changes the strategic environment behind Theorem 4. If a type instead acts as one strategic bloc, its report controls positive mass and restores pivotality, but the bidders are now cohorts, with a coalition-level truthfulness requirement. That changes who the agents are. Taking finite replications and studying their limit preserves individual truthfulness at each finite size; the result is then an asymptotic theory of a sequence of auctions, rather than a complexity question about a continuous society.
There is also a scope concern. The paper chooses data contributors and compensates them to release a prediction; it does not aggregate agents’ preferences over collective alternatives. Its main results are privacy–accuracy bounds and incentive-compatible procurement guarantees. Theorem 4 is a named approximation impossibility, so I would not dismiss it as lacking a result to mirror. Still, it does not supply the kind of computational social choice problem ChoCo is organized around: an algorithmic complexity landscape over a population of social-choice types.
This is the strongest negative case I see, and it is limited. A continuous privacy auction could be worthwhile in mechanism design, and a finite-replication limit might interest the paper’s authors. I cannot honestly rule out every scenario. The case against is that such work would change the incentive model or leave ChoCo’s stated computational social choice scope; the proponent has identified a plausible adjacent research question, rather than a clear ChoCo mirror.
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.