Optimal False-Name-Proof Voting Rules with Costly Voting

Liad Wagman, Vincent Conitzer

Introduction

In open online environments, digital democracy faces a significant threat: the "Sybil attack," where a single user casts multiple votes under different identities. Traditional social choice theory assumes a "one person, one vote" principle, but in decentralized or anonymous systems, ensuring this is difficult. Previous research suggested a bleak outlook: to make a voting rule "false-name-proof" (FNP) when extra votes are free, the rule must be almost entirely unresponsive to voter preferences, often defaulting to a coin flip unless there is absolute unanimity. This paper challenges that negative result by introducing a small cost for casting additional votes.

The Costly Voting Model

The authors propose a mechanism design approach where the first vote is free, but every subsequent vote by the same agent incurs a cost $c > 0$. This cost could represent solving a CAPTCHA, a small transaction fee, or the time required to manage multiple accounts. By assuming $c > 0$, the researchers aim to find "strongly optimal" voting rules—those that maximize responsiveness to the majority while remaining resistant to manipulation by agents who might otherwise buy extra influence.

The FNP2 Rule for Two Alternatives

For elections with two alternatives (A and B), the authors characterize a unique strongly optimal rule called $FNP2$. If $x_A$ and $x_B$ are the vote counts for each alternative, and $x_A \geq x_B > 0$, the probability of A winning is defined as:

$$P(A \text{ wins}) = \min\{1, 0.5 + c(x_A - x_B)\}$$

This rule is neutral, strategy-proof, and ensures voluntary participation. Crucially, it shows that the win probability increases linearly with the margin of victory until it reaches certainty.

Convergence and Performance

A key theoretical contribution is the proof that as the population size $n$ grows, the $FNP2$ rule converges to the majority winner. Unlike the costless setting where the error rate remains constant, the introduction of cost $c$ allows the rule to become increasingly accurate in large populations.

Error rate of the FNP2 rule as a function of the number of voters $n$.

Simulations confirm this convergence. As shown in the figure above, the probability of the rule failing to select the majority winner (the "error") drops significantly as $n$ increases. Similarly, increasing the cost $c$ per additional vote also reduces the error rate, as it allows the voting rule to be more sensitive to the margin of victory without risking manipulation.

Error rate of the FNP2 rule as a function of the cost $c$ per additional vote.

Group Manipulation and Multi-Alternative Rules

The paper also explores more complex scenarios. While $FNP2$ handles individual manipulation, the authors find that "group false-name-proofness" (GFNP)—where a coalition shares the cost of extra votes—is much harder to achieve. The resulting $GFNP2$ rule is significantly less responsive, with error rates often remaining near 40-50% even in large populations.

For three alternatives, the authors derive $FNP3$, which uses the margins between all candidates to determine probabilities. For four or more alternatives, they provide a recursive linear programming procedure to find optimal rules, though a simple closed-form solution remains elusive.

Conclusion

This work demonstrates that even a minimal cost for Sybil identities can bridge the gap between theoretical safety and practical utility in online voting. While group collusion remains a significant challenge, the $FNP2$ rule provides a robust foundation for responsive, manipulation-resistant digital democracy in large-scale systems.

Summary updated

BibTeX
@inproceedings{wagman2008optimal,
  author = {Liad Wagman and Vincent Conitzer},
  title = {{Optimal False-Name-Proof Voting Rules with Costly Voting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure