Communication complexity of common voting rules
Publication
, Journal Article
Conitzer, V; Sandholm, T
Published in: Proceedings of the ACM Conference on Electronic Commerce
June 5, 2005
We determine the communication complexity of the common voting rules. The rules (sorted by their communication complexity from low to high) are plurality, plurality with runoff, single transferable vote (STV), Condorcet, approval, Bucklin, cup, maximin, Borda, Copeland, and ranked pairs. For each rule, we first give a deterministic communication protocol and an upper bound on the number of bits communicated in it; then, we give a lower bound on (even the nondeterministic) communication requirements of the voting rule. The bounds match for all voting rules except STV and maximin. Copyright 2005 ACM.
Duke Scholars
Published In
Proceedings of the ACM Conference on Electronic Commerce
DOI
Publication Date
June 5, 2005
Start / End Page
78 / 87
Citation
APA
Chicago
ICMJE
MLA
NLM
Conitzer, V., & Sandholm, T. (2005). Communication complexity of common voting rules. Proceedings of the ACM Conference on Electronic Commerce, 78–87. https://doi.org/10.1145/1064009.1064018
Conitzer, V., and T. Sandholm. “Communication complexity of common voting rules.” Proceedings of the ACM Conference on Electronic Commerce, June 5, 2005, 78–87. https://doi.org/10.1145/1064009.1064018.
Conitzer V, Sandholm T. Communication complexity of common voting rules. Proceedings of the ACM Conference on Electronic Commerce. 2005 Jun 5;78–87.
Conitzer, V., and T. Sandholm. “Communication complexity of common voting rules.” Proceedings of the ACM Conference on Electronic Commerce, June 2005, pp. 78–87. Scopus, doi:10.1145/1064009.1064018.
Conitzer V, Sandholm T. Communication complexity of common voting rules. Proceedings of the ACM Conference on Electronic Commerce. 2005 Jun 5;78–87.
Published In
Proceedings of the ACM Conference on Electronic Commerce
DOI
Publication Date
June 5, 2005
Start / End Page
78 / 87