CATS-Nov-05-2012
Title[edit]
A Manipulability Dichotomy Theorem for Generalized Scoring Rules
Speaker[edit]
Lirong Xia, Postdoc at Center for Research on Computation and Society (CRCS), Harvard University
Abstract[edit]
Social choice studies ordinal preference aggregation with applications ranging from high-stakes political elections to low-stakes movie rating websites. One recurring concern is that of the robustness of a social choice (voting) rule to manipulation, bribery and other kinds of strategic behavior. A number of results have identified ways in which computational complexity can provide a new barrier to strategic behavior, but most of previous work focused on case-by-case analyses for specific social choice rules and specific types of strategic behavior. In this talk, I present a dichotomy theorem for the manipulability of a broad class of generalized scoring rules and a broad class of strategic behavior called vote operations. When the votes are i.i.d., then with high probability the number of vote operations that are needed to achieve the strategic individual's goal is 0, \Theta(\sqrt n), \Theta(n), or infinity. This theorem significantly strengthens previous results and implies that most social choice situations are more vulnerable to many types of strategic behavior than previously believed.
