0937e642_Game_Theory_Discussion_Group__Title_and_abstract
[Date/Time] November 30, 2004 5:30 -- 7:00 PM [Location] Wean 7220 [Speaker] Vincent Conitzer [Title and abstract] 
The Communication Complexity of Common Voting Protocols We determine the communication complexity of a number of well-known voting protocols. For each protocol, we first give an upper bound on the communication complexity by providing a communication protocol for it and analyzing how many bits need to be transmitted in this protocol. For many of the voting protocols, it will turn out that we cannot do better than simply letting each voter immediately communicate all her (potentially relevant) information. However, for some protocols (such as the Plurality with Runoff, STV and Cup protocols) there is a natural multistage communication protocol that, with some analysis, can be shown to significantly outperform the immediate communication of all (potentially relevant) information. Finally, for some protocols (such as the Bucklin protocol), we need to introduce a nontrivial communication protocol to achieve the best possible upper bound. Then, we show that our upper bounds are tight by giving a matching lower bound on each voting protocol's communication complexity (with the exception of STV, for which our upper and lower bounds are apart by a factor $\log m$).
Game Theory Discussion Group
Title and abstract