| paper | d4-conf-aaai-2008-0045 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
For rational \(c>0\), let a society have preference types \(A,B\) with masses \(\mu_A+\mu_B=1\). Find a neutral lottery rule \(P_A(a,b)\) that is pointwise maximal for every state \(a\ge b\), subject to the mass-scaled group false-name-proof constraints: for every \(A\)-preferring coalition of mass \(\kappa>0\), background ballot masses \(z_A,z_B\ge0\), and added false-ballot masses \(\delta_A,\delta_B\ge0\), require \(P_A(z_A+\kappa,z_B)\ge P_A(z_A+\kappa+\delta_A,z_B+\delta_B)-c(\delta_A+\delta_B)/\kappa\); impose the symmetric constraint for \(B\), along with neutrality and the corresponding participation and strategy-proofness conditions. Is the pointwise-optimal rule \(P_A(a,b)=\min\{1,\tfrac12+c\ln(a/b)\}\) for \(a\ge b>0\), with \(P_A(a,0)=1\) for \(a>0\) and \(P_A(0,0)=1/2\)?
A society has two preference types \(A,B\) carrying masses \(\mu_A,\mu_B\); the rule maps aggregate ballot masses to a lottery, and a coalition of mass \(\kappa\) pays \(c(\delta_A+\delta_B)/\kappa\) per member to add false-ballot mass \((\delta_A,\delta_B)\). The candidate pointwise-optimal rule uses \(c\ln(a/b)\) in place of the discrete harmonic sum.
The synthesis ranges over a rule on a continuum with infinitely many incentive constraints, and the case does not specify an admissible finite representation or an algorithm for certifying all of them.
fatal: False
The mirror covers Theorem 3 only; it leaves Theorems 1, 2, 4, and 5 and Procedure 2 unmirrored.
The strongest positive case is Theorem 3, proved in this paper. It states that, with two alternatives, GFNP2 is a strongly optimal neutral group false-name-proof rule satisfying voluntary participation. The rule it names gives A probability \(1\) when \(x_A>x_B=0\), probability \(1/2\) when both vote counts are zero, and, when \(x_A\ge x_B>0\), probability \(\min\{1,\frac12+\sum_{k=x_B}^{x_A-1}c/k\}\); the other cases follow by neutrality. In other words, among rules meeting those constraints, GFNP2 gives A at least as high a winning probability at every state where A has at least as many votes. This is a constructive optimal-rule result, not a stated complexity-class result. The paper has no named hardness result.
My lead mirror is Continuous GFNP2 Rule Synthesis. Imagine a large two-choice online referendum: each voter prefers A or B, all voters face the same cost \(c\) for an extra account, and coordinated groups can share that cost. The types are the voters’ complete descriptions for this problem—preference and cost—so there are two types, with masses \(\mu_A,\mu_B\), while the electorate size \(N\) is much larger than the support size \(\tau=2\). This is a plausible high-multiplicity regime, and Theorem 3’s explicit study of coalitions supports treating group manipulation as part of the problem.
A rule \(P\) maps the aggregate ballot masses \((a,b)\) to a lottery over A and B. To state the group constraint in mass units, take a coalition of A-preferring voters of mass \(\kappa>0\), with background ballots \(z=(z_A,z_B)\). If the coalition casts its truthful ballots, the state is \((z_A+\kappa,z_B)\). If it adds false-name ballot mass \((\delta_A,\delta_B)\), its cost per member is \(c(\delta_A+\delta_B)/\kappa\). Require that this deviation never improves the coalition’s expected utility after cost:
\[ P_A(z_A+\kappa,z_B) \ge P_A(z_A+\kappa+\delta_A,z_B+\delta_B) - \frac{c(\delta_A+\delta_B)}{\kappa}. \]
Impose the symmetric condition for B, along with neutrality, strategy-proofness, and voluntary participation. The problem is: find a rule satisfying these conditions that maximizes \(P_A(a,b)\) at every state with \(a\ge b\). Its solution is the continuous analogue of the paper’s strongly optimal rule.
The natural candidate is
\[ P_A(a,b)= \begin{cases} 1, & a>0,\ b=0,\\ \min\{1,\frac12+c\ln(a/b)\}, & a\ge b>0,\\ \frac12, & a=b=0, \end{cases} \]
with the other states determined by neutrality. This is not a result proved in the paper; it is the proposed continuous solution. Its connection to Theorem 3 is direct: set \(x_A=Na\) and \(x_B=Nb\) in GFNP2’s sum. For fixed positive \(a\ge b\), as \(N\) grows, \(\sum_{k=Nb}^{Na-1}c/k\) approaches \(c\ln(a/b)\). The mass-scaled group cost also preserves the original incentive: a coalition of mass \(\kappa\) adding ballot mass \(\delta\) pays \(c\delta/\kappa\) per member. The expected direction is tractable: the candidate is a closed-form rule, though an exact computational classification would depend on how its logarithmic values are represented. Further questions include proving optimality under the continuous constraints, bounding the finite-\(N\) approximation error, and extending the model to heterogeneous costs or more alternatives.
The mirror covers Theorem 3 only. I would not use the paper’s asymptotic performance results or its LP procedure as anchors for a computational-complexity claim. The main weakness is that individual false-name-proofness becomes vacuous for atomless voters: one voter changes aggregate mass by zero. The group version avoids that degeneracy by giving coalitions positive mass and sharing costs, and the paper itself treats group false-name-proofness. Still, that choice narrows the mirror to coordinated groups, and the resulting two-alternative synthesis problem may be too simple to reveal a broader complexity landscape.
If “anchor” is meant strictly to require a named theorem asserting a complexity class such as P or NP-hardness, then this paper has no qualifying anchor. Theorem 3 is the closest constructive result, and it supports the continuous group-rule question above, but it does not classify a problem’s computational complexity.
Theorem 3 is the right anchor, and the referendum scenario is convincing. The types can be the two preferences, or preference and cost if costs vary. Group manipulation gives a sensible way to avoid the vanishing influence of a single atomless voter. The proposed limit is also well motivated: for \(x_A=Na\) and \(x_B=Nb\), the harmonic sum in GFNP2 approaches \(c\ln(a/b)\). I would not reject this mirror on grounds of multiplicity, atomlessness, or an unchanged answer.
The difficulty is the kind of result Theorem 3 proves. It characterizes one rule that is pointwise optimal across every state, subject to universal incentive constraints. The paper’s other named results concern asymptotic behavior and probability bounds. None asks for the worst-case complexity or an algorithm for an instance-level computational task. The finite-state LP in Procedure 2 supplies a computational technique for designing a rule under a cap and a prior; the paper gives no complexity classification for it.
There are two ways to make the proposed mirror computational. One is to ask for the whole optimal rule. That requires specifying how an algorithm represents and outputs a function on a continuum of states, and how its infinitely many incentive constraints are encoded. Without those choices, there is no finite input/output problem whose complexity ChoCo could chart. The other is to take rational masses \(a,b\) as input and evaluate the rule to some precision. That is a well-posed task, but it asks for a probability at one state; it does not capture Theorem 3’s global optimality claim. A finite grid or a bounded state space would make synthesis finite, as in Procedure 2, while moving the question to a chosen discretization of rule design.
One could extend the model to more alternatives, heterogeneous costs, or continuous priors and study a functional optimization problem. That might be worthwhile mechanism-design research. The paper’s own results do not establish that it yields the kind of instance-based complexity landscape ChoCo is pursuing. My negative case therefore rests on scope, not on a defect in the mass model: the best anchor has a credible analytic continuous mirror, but no corresponding computational problem is specified. If ChoCo counts continuous rule characterization as sufficient, this case is weak; under its stated focus on computational questions, Theorem 3 does not yet give it a solid anchor.
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.