Strategic Voting
In: Synthesis Lectures on Artificial Intelligence and Machine Learning Ser.
Cover -- Copyright Page -- Title Page -- Dedication -- Contents -- Preface -- Acknowledgments -- Introduction -- Basic Notation -- Social Choice -- Game Theory -- Game Forms are Voting Rules -- The Quest for Truthful Voting -- Strategyproofness and the Gibbard-Satterthwaite Theorem -- Voting Manipulations -- The Gibbard-Satterthwaite Theorem -- Frequency of Manipulation -- Group Manipulations -- Safe Manipulations -- Irresolute Social Choice Correspondences -- Exercises -- Regaining Truthfulness in Voting -- Domain Restriction -- Single-Peaked Preferences on a Line -- Other Single-Peak Domains -- Dichotomous Preferences -- Complexity Barriers -- Few Candidates and Coalitional Manipulations -- Randomized Voting Rules -- Gibbard's Characterization -- Stronger Impossibility Results -- Output Approximation -- Almost-Strategyproof Rules -- Approximation with Almost-Strategyproof Rules -- Differential Privacy -- Exercises -- Voting and Mechanism Design -- Payments -- The VCG Mechanism -- Range Voting -- Approximation by Randomized Voting Rules -- Facility Location -- Location in a General Metric Space -- Location on a Line -- Location on a Circle -- Other Variations -- Judgment Aggregation -- Formal Framework -- Incentives and Manipulation -- Exercises -- Voting Equilibrium Models -- Simultaneous Voting Games -- Desiderata for Voting Models -- Implementation -- Nash Implementation -- Strong Implementation -- Implementation in Undominated Strategies -- Other Notions of Implementation -- Fallback Strategies -- Truth Bias/Partial Honesty -- Laziness and the Paradox of Voting -- The ``Calculus of Voting'' -- The Expected Value of Voting -- Equilibrium Stability -- Social Networks -- Quantal Response Equilibrium -- Other Equilibrium Models -- Minimax Regret -- Robust Equilibrium -- Iterated Removal of Dominated Strategies -- Exercises.