The ACO Seminar (2011-2012)

We present a general approach to quantifying a mechanism's susceptibility to strategic manipulation, based on the premise that agents report their preferences truthfully if there is little to gain from behaving strategically. Susceptibility is defined as the maximum amount of expected utility an agent can gain by manipulating. We apply this measure to anonymous voting rules, by making minimal restrictions on voters' utility functions and beliefs about each other's behavior. We give two sets of results. First, we offer bounds on the susceptiblity of specific voting rules. This includes considering several voting systems which have been previously advanced as resistant to manipulation; we find that they are actually more susceptible than simple plurality rule by our measure. Second, we give asymptotic lower bounds on susceptibility for any voting rule, under various combinations of efficiency, regularity, and informational conditions. These results illustrate the tradeoffs between susceptibility and other properties of the voting rule.