Helger Lipmaa's publications

Hybrid Voting Protocols and Hardness of Manipulation

Edith Elkind and Helger Lipmaa. Hybrid Voting Protocols and Hardness of Manipulation. In Xiaotie Deng and Dingzhu Du, editors, The 16th Annual International Symposium on Algorithms and Computation, ISAAC 2005, volume 3827 of Lecture Notes in Computer Science, pages 206--215, Sanya, Hainan, China, December 19--21, 2005. Springer, Heidelberg.

File: [.pdf (122 KB)] pdf recommended.


This paper addresses the problem of constructing voting protocols that are hard to manipulate. We describe a general technique for obtaining a new protocol by combining two or more base protocols, and study the resulting class of (vote-once) hybrid voting protocols, which also includes most previously known manipulation-resistant protocols. We show that for many choices of underlying base protocols, including some that are easily manipulable, their hybrids are NP-hard to manipulate, and demonstrate that this method can be used to produce manipulation-resistant protocols with unique combinations of useful features..

Keywords: NA.



Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.