Computational Social Choice

Abstract

3 Voting 17 3.1 Voting Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1 Scoring Rules . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.2 Condorcet Extensions . . . . . . . . . . . . . . . . . . . 19 3.1.3 Other Rules . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.1 The Gibbard-Satterthwaite Impossibility . . . . . . . . . . 24 3.2.2 Restricted Domains of Preferences . . . . . . . . . . . . . 24 3.2.3 Computational Hardness of Manipulation . . . . . . . . . 26 3.2.4 Probabilistic Voting Rules . . . . . . . . . . . . . . . . . 29 3.2.5 Irresolute Voting Rules . . . . . . . . . . . . . . . . . . . 30 3.3 Possible and Necessary Winners . . . . . . . . . . . . . . . . . . 31