On asymptotic strategy-proofness of classical social choice rules (Q1863937)

The Gibbard-Satterthwaite theorem states that every nondictatorial social choice function is manipulable, but does not quantify that manipulability. Every manipulable social choice function is unstable and here the author shows that unstable rules based on either the majority relation or a faithful scoring rule have simple combinatorics. In both cases, the author proves by combinatorial arguments that there is an upper bound on the proportion of unstable profiles of the form \(O(1/\sqrt{n})\), where \(n\) is the number of voters. Together with other results in the area, this shows that all classical social choice rules are asymptotically non-manipulable.