Optimal False-Name-Proof Voting Rules with Costly Voting

Abstract

One way for agents to reach a joint decision is to vote over the alternatives. In open, anonymous settings such as the Inter-net, an agent can vote more than once without being detected. A voting rule is false-name-proof if no agent ever benefits from casting additional votes. Previous work has shown that all false-name-proof voting rules are unresponsive to agents’ preferences. However, that work implicitly assumes that cast-ing additional votes is costless. In this paper, we consider what happens if there is a cost to casting additional votes. We characterize the optimal (most responsive) false-name-proof-with-costs voting rule for 2 alternatives. In sharp contrast to the costless setting, we prove that as the voting population grows larger, the probability that this rule selects the major-ity winner converges to 1. We also characterize the optimal group false-name-proof rule for 2 alternatives, which is ro-bust to coalitions of agents sharing the costs of additional votes. Unfortunately, the probability that this rule chooses the majority winner as the voting population grows larger is relatively low. We derive an analogous rule in a setting with 3 alternatives, and provide bounding results and computational approaches for settings with 4 or more alternatives.