| paper | d4-conf-aaai-2012-0194 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given two finite-support rational identity-count distributions \(\pi_1,\pi_2\), each with positive mean and variance, and a sequence of two-type societies with masses \(\mu_N=(p_N,1-p_N)\), where \(Np_N,N(1-p_N)\in\mathbb{N}\), \(p_N>1/2\), and \(d_N=N(2p_N-1)=\omega(1)\) and \(d_N=O(\sqrt{N})\), determine which policy eventually gives the higher probability that \(A\) wins. When the ratios \(\mu_i/\sigma_i\) differ, Theorem 1 ranks the policies by that ratio.
Use voter types \(t_A=(A\succ B)\) and \(t_B=(B\succ A)\), with normalized masses \(p_N\) and \(1-p_N\) and total scale \(N\). Under policy \(\pi_i\), each supporter independently draws an identity count and casts that many votes for their preferred alternative; compare policies by \(\Pr[V_{A,i}>V_{B,i}]\). The population composition is the continuous object, while the identity-count randomness remains as in the paper.
The mirror covers Theorem 1's asymptotic comparison of individual vote distributions; it leaves Theorems 2–5 on adjusted-margin hypothesis testing, the simulations, and broader mechanism-design questions untouched.
There is a limit to the positive case: the paper has no named complexity result asserting that a problem is in P, NP-hard, FPT, or similar. Its named Theorems 1–5 are statistical results, not complexity classifications. So none is an eligible anchor under your strict anchor rule.
The strongest honest candidate is Theorem 1, proved in this paper. It says that for two individual vote distributions with positive means and variances and finite absolute third moments, and a sequence of elections where \(n_A-n_B\) grows as \(\omega(1)\) but is \(O(\sqrt n)\), if \(\mu_1/\sigma_1>\mu_2/\sigma_2\), then eventually the first distribution gives a higher probability that the majority of votes goes to the alternative with more true supporters. This is a real result about choosing among false-name-limiting methods, though not a complexity theorem.
A plausible mirror is the local-continuum false-name policy comparison. An instance gives two finite-support rational distributions \(\pi_1,\pi_2\) over the number of identities a supporter creates. The society has two types: supporters ranking \(A\) above \(B\), and supporters ranking \(B\) above \(A\). For a sequence of total population scales \(N\), their masses are \(p_N\) and \(1-p_N\), with \(Np_N\) and \(N(1-p_N)\) integral and
\[
Np_N-N(1-p_N)=\omega(1),\qquad Np_N-N(1-p_N)=O(\sqrt N).
\]
Each supporter independently draws an identity count from the selected policy and casts that many votes for their preferred alternative. The designer chooses between \(\pi_1\) and \(\pi_2\) to maximize the probability that the vote winner is the alternative with greater supporter mass. The solution is the eventually better policy; when the ratios differ, Theorem 1 orders them by \(\mu_i/\sigma_i\). If they tie, this theorem does not settle the comparison.
The regime is a large online referendum with many supporters but only two preference types. The type is the supporter’s complete preference ranking; mass is the fraction of supporters of each type. The policy is common to the population, as in the paper. The continuous object is the population composition; the false-identity draws remain stochastic as they are in the authors’ model. This is a credible scenario for them to recognize: it asks their same policy-comparison question in terms of population shares. Its expected answer is tractable for the finite-support input above, since the ratios can be compared by exact rational arithmetic. That tractability is a consequence of Theorem 1 plus direct calculation, not a complexity result claimed by the paper.
The mirror covers only the paper’s comparison of individual vote distributions, not its adjusted-margin hypothesis test or its broader design questions. It suggests follow-ups about tied ratios, exact finite-population comparisons, and choosing from a larger catalogue of policies.
The weak point is that this is a local, large-population reformulation of an asymptotic statistical theorem. A fixed continuous society with unequal type masses loses the near-tie scaling that makes Theorem 1 informative. And while the paper’s finite-agent model is not itself a continuous-population model, the proposed mirror may still feel more like a continuous restatement of its analysis than a new computational question.
The decisive problem is that this paper supplies no computational result to mirror. Theorem 1 is a statistical asymptotic comparison of false-name policies; Theorems 2–5 develop a hypothesis test. None classifies the complexity of a computational social choice problem or gives an algorithm for one. For Theorem 1, once the policies are specified, its comparison is about their moments and the probability of an election outcome. That can be a useful result, but it does not create the complexity question this programme is meant to chart.
The strongest proposed mirror is still intelligible: represent supporters of \(A\) and \(B\) as two voter types with masses \(p\) and \(1-p\), and keep the paper’s per-supporter random identity counts. But the relevant uncertainty depends on the finite population scale. For fixed \(p\ne 1/2\), the expected vote margin grows with population size while its standard deviation grows only as the square root, so the local policy comparison disappears in the limit. At \(p=1/2\), the limiting society does not retain the near-tie information Theorem 1 uses. Recovering it requires a sequence of societies with a scaled margin—roughly, \(n_A-n_B\) on the order of \(\sqrt n\)—and therefore an explicit population-size and fluctuation parameter. That is a legitimate local asymptotic statistical model, but it does not turn the theorem into a computational question about a society given by type masses.
A better proposal might let the designer choose among false-name policies subject to cost or implementation constraints. That could be worthwhile research, but any computational difficulty would come from the newly specified policy set and constraints. The paper’s theorem does not define that optimization problem, and the continuous object doing the work would be the distribution over identity counts, not the population. The two-type, high-multiplicity referendum scenario is plausible; the objection is not that such a society makes no sense. It is that this paper’s results concern statistical reliability under individual randomness, rather than the computational landscape of interventions on a continuous society.
So the negative case is strong against treating Theorem 1 as a ChoCo anchor, but it cannot establish the universal claim that no author would find any continuous-population reformulation worthwhile. A local asymptotic version could be a useful extension. Its value would be as statistical modeling, though, not as a continuous computational-social-choice mirror of a named result in this paper.
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.