| paper | d4-conf-atal-2011-0261 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 19 passes the computational-result test because it gives a specified mechanism an approximation guarantee. But when the society is nonatomic, one expert's report changes no mass, so individual strategyproofness is vacuous and the aggregate-optimal classifier has ratio \(1\). Requiring strategyproofness at each finite population size preserves the original atomic problem along a sequence, rather than giving an intrinsic continuous analogue of the anchored result.
fails bit b-changes — the continuum limit changes the question
The finite-refinement requirement restores individual incentives only by retaining finite-agent constraints; in a rule on \(\mu\) itself, an individual cannot change the outcome-relevant mass and strategyproofness imposes no restriction.
fatal: True
The proposed anchors were Theorem 4's uniform-weight lower bound and Theorem 19's CRD guarantee; neither yields a surviving continuous strategic question. The paper's other results are not covered by this proposed mirror.
The best mirror is an asymptotic strategyproof-classification problem. The society is the continuous object: for shared finite inputs \(X\), a type is a complete binary labeling \(Y:X\to\{-,+\}\), and \(\mu_Y\) is the fraction of experts with that labeling. Its support size \(\tau\) counts the distinct labelings, not the number of experts. A type’s risk for classifier \(c\) is
\[
r_Y(c)=\frac{1}{|X|}\sum_{x\in X}\mathbf 1[c(x)\ne Y(x)],
\]
so society risk is \(R_\mu(c)=\sum_Y\mu_Yr_Y(c)\), and \(\operatorname{OPT}(\mu)=\min_{c\in C}R_\mu(c)\).
For a precise incentive notion, I would define the continuous rule as a refinement-stable family of anonymous mechanisms \(M_N\). At population size \(N\), the input is an empirical distribution \(\nu\) with masses in multiples of \(1/N\); \(M_N\) returns a lottery over \(C\) and is strategyproof against each expert changing their own report. As \(N\) grows, these distributions converge to \(\mu\), and the lotteries converge to a rule \(M_\infty(\mu)\). The problem is to determine the best worst-case limiting ratio
\[
\rho_\infty^*=
\inf_{(M_N)}
\limsup_{N\to\infty}
\sup_{\nu:\operatorname{OPT}(\nu)>0}
\frac{\mathbb E_{c\sim M_N(\nu)}[R_\nu(c)]}{\operatorname{OPT}(\nu)},
\]
where the infimum is over such strategyproof families. This preserves individual incentives at every finite refinement while making the limiting input a distribution over types.
Lead anchor — Theorem 4, proved in this paper. On \(X=\{x,y,z\}\) and the three classifiers that predict positive at exactly one of those points, for every strategyproof mechanism and every \(n\ge2\), the authors prove that for every \(\tilde\epsilon>0\) there is a uniform-weight instance \(S\) with
\[
R_I(M(S),S)>
\left(3-\frac2n-\tilde\epsilon\right)R_I(c^*(S),S).
\]
If the mechanism is consistent or \(\mu\)-granular, the theorem also gives such a finite instance with \(k=O(1/\tilde\epsilon,1/\mu)\) data points. The continuous question anchored here is: what is \(\rho_\infty^*\) on this fixed three-classifier domain? Theorem 4 forces its answer to be at least \(3\): restrict any proposed family to each \(N\), apply the theorem, then let \(N\) grow.
A second anchor supplies the matching construction. Theorem 19, proved in this paper (with its proof omitted for space). For weights \(w_i\), CRD chooses dictator \(i\) with probability \(p_i=\alpha_w p_i'\), where \(p_i'=w_i/[2(1-w_i)]\) and \(\alpha_w=1/\sum_i p_i'\); its approximation ratio is \(\alpha_w+1\le 3-2/n\). For equal weights, this is uniform random dictatorship, and the bound tends to \(3\). Thus the lead problem has the exact answer \(\rho_\infty^*=3\). Theorem 19 also anchors a constructive question: given a type distribution \(\mu\) arising from agents whose individual weights vanish, produce a strategyproof lottery with risk at most \(3\operatorname{OPT}(\mu)\). The limit mechanism samples a type according to its mass and returns that type’s fixed empirical-risk-minimizing classifier. Its probability on each classifier is the total mass of types assigned that classifier. This rule is tractable when the per-type ERM computation is tractable; the paper does not establish a runtime bound for arbitrary concept classes.
The regime is large-scale classification with shared cases: for example, a large panel of experts or annotators evaluating the same benchmark cases, with common protocols producing relatively few complete labeling patterns. Then \(N\) can be large while \(\tau\ll N\), and a small but positive minority type can have mass about \(1/N\). That is close to the paper’s setting, and the lower-bound theorem already uses a particularly simple classifier class. The mirror keeps the population distribution, private label types, classifier choices, social risk, and finite-level truthfulness. It does not rely on fractional outcomes: the lottery over classifiers is already in the paper, while the continuum is in the population.
I expect the upper-bound problem to be tractable in this sense: the mechanism is a direct distributional limit of the paper’s dictator mechanism, and the three-point minimax value follows from the two named bounds. This is not an NP-hardness or running-time result. The paper contains named mechanism-performance theorems, but no conventional complexity-class theorem to mirror.
The weakest point is the limiting incentive model. In a genuinely nonatomic population, one individual’s report has zero effect, so ordinary individual strategyproofness becomes vacuous. The refinement-family definition avoids that by retaining individual strategyproofness at every finite population size, but it makes the question an asymptotic mirror rather than a standalone theorem about a nonatomic game. I think the authors would recognize it as their problem’s high-multiplicity limit because the finite models preserve their exact incentives and shared-input assumptions. Whether they would accept a direct, intrinsic strategyproofness notion on \(\mu\) alone remains an open follow-up.
The proponent has chosen the most credible setting: many annotators judging the same benchmark cases. I don’t see a strong objection to high multiplicity here. A complete labeling is a sensible type, and a large panel can plausibly have many people per type. The better case against is about what the proposed mirror asks.
Take Theorem 4’s strongest mirror: the limiting best approximation ratio over individually strategyproof mechanisms on a distribution of labeling types. In a genuinely nonatomic society, an individual report changes no mass. Any mechanism that depends only on \(\mu\) is therefore strategyproof automatically. The mechanism can simply choose a classifier minimizing \(\sum_Y\mu_Y r_Y(c)\), giving ratio \(1\) whenever that empirical-risk minimization is computable. The strategic tradeoff behind Theorem 4 has disappeared. Requiring strategyproofness at every finite refinement restores that tradeoff, but then the question is about the original finite-agent mechanisms along a sequence of population sizes. It is not an intrinsic computational problem on the continuous society.
The same problem affects Theorem 19. In the finite model, CRD is a lottery over named agents; when their weights vanish, it approaches sampling a type according to its mass and returning that type’s preferred classifier. That is a natural limit of the paper’s mechanism. But in the nonatomic model, it is an unnecessarily costly way to be strategyproof: choosing the aggregate-optimal classifier is already strategyproof. In the finite-refinement model, CRD remains the paper’s mechanism applied at larger \(n\). Neither version exposes a new computational task about continuous populations.
There is also a mismatch with ChoCo’s target. Theorems 4 and 19 establish welfare approximation guarantees for strategyproof mechanisms. They do not classify the complexity of computing a mechanism, give an algorithm for a hard optimization problem, or analyze the cost of that computation. The obvious computation in the proposed distributional model is weighted empirical-risk minimization over \(C\); any difficulty there belongs to the concept-class optimization problem, not to the population continuization. That leaves no clear separation or pricing problem, nor an algorithmic landscape for the continuous mirror to chart.
One could seek a nonvacuous continuum incentive notion by allowing a positive-mass group to misreport. But that changes individual strategyproofness into a coalition or mass-deviation requirement, so Theorems 4 and 19 no longer anchor the question. Such a problem might be worthwhile on its own; it does not rescue these anchors as mirrors of this paper.
This is a limited negative case, not evidence that no plausible mirror exists. The population regime is credible, and the proposed limit is mathematically well-defined as an asymptotic study. My objection is that its intrinsic strategic version collapses, while its nontrivial version retains the finite-agent problem—and neither supplies the computational question ChoCo is looking for.
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.