Skip to main content

Optimal false-name-proof voting rules with costly voting

Publication ,  Journal Article
Wagman, L; Conitzer, V
Published in: Proceedings of the National Conference on Artificial Intelligence
December 29, 2008

One way for agents to reach a joint decision is to vote over the alternatives. In open, anonymous settings such as the Internet, 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 casting 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 majority winner converges to 1. We also characterize the optimal group false-name-proof rule for 2 alternatives, which is robust 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. Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Duke Scholars

Published In

Proceedings of the National Conference on Artificial Intelligence

Publication Date

December 29, 2008

Volume

1

Start / End Page

190 / 195
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Wagman, L., & Conitzer, V. (2008). Optimal false-name-proof voting rules with costly voting. Proceedings of the National Conference on Artificial Intelligence, 1, 190–195.
Wagman, L., and V. Conitzer. “Optimal false-name-proof voting rules with costly voting.” Proceedings of the National Conference on Artificial Intelligence 1 (December 29, 2008): 190–95.
Wagman L, Conitzer V. Optimal false-name-proof voting rules with costly voting. Proceedings of the National Conference on Artificial Intelligence. 2008 Dec 29;1:190–5.
Wagman, L., and V. Conitzer. “Optimal false-name-proof voting rules with costly voting.” Proceedings of the National Conference on Artificial Intelligence, vol. 1, Dec. 2008, pp. 190–95.
Wagman L, Conitzer V. Optimal false-name-proof voting rules with costly voting. Proceedings of the National Conference on Artificial Intelligence. 2008 Dec 29;1:190–195.

Published In

Proceedings of the National Conference on Artificial Intelligence

Publication Date

December 29, 2008

Volume

1

Start / End Page

190 / 195