In this presentation, I will discuss the paper Communication Complexity of Common Voting Rules [1], which examines how many bits must be exchanged to elicit voters’ preferences and determine the outcome of an election, depending on the voting rule used. I begin by presenting the concept of deterministic and non-deterministic communication complexity, followed by an introduction of the main voting rules analyzed in the paper. I then explain the paper’s main results, which primarily establish lower and upper bounds on the communication complexity of several well-known voting rules, such as plurality, Borda count, and the Condorcet rule. This talk aims to provide a deeper understanding of the communication requirements of different voting systems.
References
[1] Vincent Conitzer and Tuomas Sandholm. Communication complexity of common voting rules. In Proceedings of the 6th ACM conference on Electronic commerce, pages 78–87, 2005.