| paper | d4-conf-atal-2010-0351 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: \(+\infty\): no deterministic strategyproof mechanism has a finite multiplicative approximation guarantee, even allowing dependence on input parameters and masses. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5.3
statement extracted from the paper’s text layer
Given a rational distribution \(\mu\) over types \(t=(X_t,Y_t)\), where \(X_t\) is a public bundle and \(Y_t\) its true labels, consider deterministic mechanisms \(F\) mapping reported type distributions to separators in \(\mathrm{LINEAR}_d\). Require that for every type \(t\), every \(0<q\leq\mu_t\), and every alternative label vector \(\hat Y\), \(R_t(F(\mu))\leq R_t(F(\mu-q\delta_t+q\delta_{(X_t,\hat Y)}))\). What is the best worst-case approximation factor for \(F\) against \(\operatorname{OPT}(\mu)=\min_{c\in\mathrm{LINEAR}_d}R_\mu(c)\), and can it be achieved in time polynomial in the dimension, support size, bundle descriptions, and input bit length?
A population is a distribution over complete respondent types, each carrying a public bundle and private labels. A separator determines each type’s average classification risk, and the objective is total misclassification weighted by type mass. Incentive constraints allow any positive mass of one type to switch its reported labels while keeping its bundle fixed.
The mirror covers Theorem 5.3’s deterministic approximation lower bound for linear separators; it leaves the randomized mechanism results, the conjunction results, and the generalization discussion aside.
My lead is a continuous-population mirror of Theorem 5.3, for linear separators.
Take a product-testing panel with many respondents. Each respondent is assigned a public bundle \(X_t\) of products, represented by points in \(\mathbb{Q}^d\), and has a private label for each product. A complete type is \(t=(X_t,Y_t)\): the bundle and the respondent’s true labeling. Respondents of the same type have the same preferences over classifiers because they assess them on the same examples with the same labels. A society is a distribution \(\mu\) over these types, with \(\mu_t\) the fraction of respondents of type \(t\). The panel can be large while the number \(\tau\) of types stays small. In the paper’s reduction, the two bundle patterns and six label patterns per bundle give a constant-size type support.
A deterministic mechanism \(F\) takes the distribution of reported types \(\nu\) and returns a linear separator. For a true society \(\mu\), its global risk is
\[ R_\mu(c)= \frac{\sum_t \mu_t \sum_{x\in X_t}\mathbf{1}[c(x)\ne Y_t(x)]} {\sum_t \mu_t |X_t|}, \qquad \operatorname{OPT}(\mu)=\min_{c\in\mathrm{LINEAR}_d}R_\mu(c). \]
The individual’s risk \(R_t(c)\) is the fraction of their own bundle misclassified. To state an incentive condition on mass distributions, require that no positive mass \(q\) of one true type can improve its members’ risk by changing their reported labels. For every \(t\), \(0<q\le\mu_t\), and alternative report \(\hat t=(X_t,\hat Y)\), require
\[ R_t(F(\mu)) \le R_t\!\left(F(\mu-q\delta_t+q\delta_{\hat t})\right). \]
Call this type-mass strategyproofness. The continuous question is: given \(d\), the public bundles, and a rational report distribution of support \(\tau\), find a separator by evaluating a deterministic mechanism that satisfies this condition across societies. What is the best worst-case approximation factor \(\alpha\), and can a mechanism attaining it be evaluated in time polynomial in \(d,\tau\), and the input bit length?
Theorem 5.3, proved in this paper, is the anchor: “For any \(d\ge1\), there is no deterministic SP \(o(\sqrt m)\)-approximation mechanism for \(\mathrm{LINEAR}_d\),” where \(m\) is the total number of examples. Its proof is sketched here and reduces through the paper’s toy classification problem. It is an approximation impossibility for all mechanisms, not a runtime lower bound.
I expect this lower bound to transfer to the mass-strategyproof question on its finite empirical societies. If \(N\) respondents realize \(\mu\), then one respondent’s misreport moves mass \(q=1/N\). A mechanism satisfying the displayed condition for every \(q\) must satisfy the paper’s individual strategyproofness condition on that finite realization, and the risk and benchmark agree. Thus the continuous mass model cannot promise an \(o(\sqrt m)\) approximation uniformly over those instances. This is a Class-B-style transfer of an approximation barrier; it does not establish NP-hardness.
The mirror’s scope is Theorem 5.3’s deterministic lower bound for linear separators. The paper’s randomized mechanism results and its questions about generalization are outside this mirror. The authors should recognize the underlying problem—choosing a linear classifier from strategic, privately labeled data without payments—as theirs. The panel scenario also fits the paper’s own market-research motivation, while making the high-multiplicity regime explicit.
The weakest point is the incentive condition. The paper studies deviations by one agent; type-mass strategyproofness also tests coordinated deviations by any positive mass of identical agents. That extension keeps incentives meaningful in a population model and includes a single finite agent’s \(1/N\) deviation, but it is stronger than the paper’s original axiom. At an exactly atomless limit, a single person changes no mass, so ordinary individual strategyproofness can become vacuous and Theorem 5.3 need not survive. The follow-up question is whether a useful approximation theory remains when incentive constraints are tied to a vanishing agent mass, and how its guarantees depend on that mass, \(\tau\), and the bundle sizes.
Theorem 5.3 is a real approximation-mechanism result, so I would not dismiss it for lack of a named computational result. Nor is lack of multiplicity a strong objection: repeated respondents with the same public bundle and label vector give a plausible finite type space.
The strongest objection is the change in the strategic unit. In an atomless population, one respondent has measure zero. If a mechanism sees only the distribution \(\mu\), a unilateral report leaves \(\mu\) unchanged, so every mechanism is strategyproof under the paper’s individual-deviation meaning—including one that always returns a poor classifier. The tension between strategyproofness and approximation that drives Theorem 5.3 has disappeared.
The proposed type-mass condition restores that tension by allowing any \(q>0\) of a type to change reports. But that makes a coordinated mass a strategic actor; the paper studies unilateral deviations. The finite embedding is valid: when \(N\) respondents each have mass \(1/N\), the condition includes an individual’s deviation, and the risk ratio agrees. That establishes a lower bound on those embedded finite societies. It does not make arbitrary positive-mass deviations individual deviations. Conversely, restricting deviations to \(1/N\) requires \(N\) as part of the model: the same \(\mu\) can describe populations of different sizes. As the individual mass tends to zero, the unilateral constraint vanishes.
So I can argue against a *faithful atomless mirror* of Theorem 5.3: preserving individual strategyproofness makes it vacuous, while the proposed repair changes the axiom to mass-coalition strategyproofness. But that is not enough to sustain the universal claim that no worthwhile mirror exists. If the authors accept coordinated type cohorts as a natural population model, the proponent’s mirror remains plausible, and its finite-society lower-bound transfer is sound. The honest negative case is narrow and vulnerable at precisely that modeling choice.
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.