Bureaucrats, editor, Administrators
373
edits
Changes
no edit summary
== Title ==
A Manipulability Dichotomy Theorem for Generalized Scoring Rules
== Speaker ==
Lirong Xia, Postdoc at Center for Research on Computation and Society (CRCS), Harvard University
== Abstract ==
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.
A Manipulability Dichotomy Theorem for Generalized Scoring Rules
== Speaker ==
Lirong Xia, Postdoc at Center for Research on Computation and Society (CRCS), Harvard University
== Abstract ==
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.