VoteID 2009 Program

We address the problem of constructing mechanisms for popular voting that are computationally hard to manipulate. A recent paper by Conitzer and Sandholm shows that one can make many well-known mechanisms resistant to manipulation by prepending them with a pre-round of a certain form. Variants of these technique result in mechanisms that are NP-hard, #P-hard, or PSPACE-hard. We extend this result in several directions.

First, we show that using this approach, one can make manipulation as hard as inverting one-way functions. This hardness criterion is standard in cryptography, and is an important step in achieving average-case hardness.

Second, we introduce a general technique for obtaining a new mechanism by combining two or more base mechanisms, and study the resulting class of hybrid voting mechanisms. We show that the mechanisms of Conitzer and Sandholm can be viewed as a special case of our construction. Moreover, many other mechanisms in this class are also hard to manipulate, and some of them have a combination of desirable properties not shared by previously known manipulation-resistant mechanisms.

Finally, we discuss the limitations of pre-round based mechanisms and show that they cannot be used to achieve some natural average-case hardness goals.