You are previewing Handbook of Computational Social Choice.
O'Reilly logo
Handbook of Computational Social Choice

Book Description

The rapidly growing field of computational social choice, at the intersection of computer science and economics, deals with the computational aspects of collective decision making. This handbook, written by thirty-six prominent members of the computational social choice community, covers the field comprehensively. Chapters devoted to each of the field's major themes offer detailed introductions. Topics include voting theory (such as the computational complexity of winner determination and manipulation in elections), fair allocation (such as algorithms for dividing divisible and indivisible goods), coalition formation (such as matching and hedonic games), and many more. Graduate students, researchers, and professionals in computer science, economics, mathematics, political science, and philosophy will benefit from this accessible and self-contained book.

Table of Contents

  1. Cover
  2. Half title
  3. Title
  4. Copyright
  5. Table of Contents
  6. Foreword
  7. Contributors
  8. 1 Introduction to Computational Social Choice
    1. 1.1 Computational Social Choice at a Glance
    2. 1.2 History of Social Choice Theory
    3. 1.3 Book Outline
    4. 1.4 Further Topics
    5. 1.5 Basic Concepts in Theoretical Computer Science
  9. Part I Voting
    1. 2 Introduction to the Theory of Voting
      1. 2.1 Introduction to an Introduction
      2. 2.2 Social Choice Functions: Plurality, Copeland, and Borda
      3. 2.3 Axioms I: Anonymity, Neutrality, and the Pareto Property
      4. 2.4 Voting Rules I: Condorcet Extensions, Scoring Rules, and Run-Offs
      5. 2.5 An Informational Basis for Voting Rules: Fishburn’s Classification
      6. 2.6 Axioms II: Reinforcement and Monotonicity Properties
      7. 2.7 Voting Rules II: Kemeny and Dodgson
      8. 2.8 Strategyproofness: Impossibilities
      9. 2.9 Strategyproofness: Possibilities
      10. 2.10 Approval Voting
      11. 2.11 The Future
    2. 3 Tournament Solutions
      1. 3.1 Introduction
      2. 3.2 Preliminaries
      3. 3.3 Common Tournament Solutions
      4. 3.4 Strategyproofness and Agenda Implementation
      5. 3.5 Generalizations to Weak Tournaments
      6. 3.6 Further Reading
    3. 4 Weighted Tournament Solutions
      1. 4.1 Kemeny’s Rule
      2. 4.2 Computing Kemeny Winners and Kemeny Rankings
      3. 4.3 Further Median Orders
      4. 4.4 Applications in Rank Aggregation
      5. 4.5 Other C2 Functions
    4. 5 Dodgson’s Rule and Young’s Rule
      1. 5.1 Overview
      2. 5.2 Introduction, Election-System Definitions, and Results Overview
      3. 5.3 Winner-Problem Complexity
      4. 5.4 Heuristic Algorithms
      5. 5.5 The Parameterized Lens
      6. 5.6 Approximation Algorithms
      7. 5.7 Bibliography and Further Reading
    5. 6 Barriers to Manipulation in Voting
      1. 6.1 Introduction
      2. 6.2 Gibbard-Satterthwaite and Its Implications
      3. 6.3 Noncomputational Avenues around Gibbard-Satterthwaite
      4. 6.4 Computational Hardness as a Barrier to Manipulation
      5. 6.5 Can Manipulation Be Hard Most of the Time?
      6. 6.6 Fully Game-Theoretic Models
      7. 6.7 Conclusions
    6. 7 Control and Bribery in Voting
      1. 7.1 Introduction
      2. 7.2 Preliminaries
      3. 7.3 Control
      4. 7.4 Bribery
      5. 7.5 A Positive Look
      6. 7.6 Summary
    7. 8 Rationalizations of Voting Rules
      1. 8.1 Introduction
      2. 8.2 Consensus-Based Rules
      3. 8.3 Rules as Maximum Likelihood Estimators
      4. 8.4 Conclusions and Further Reading
    8. 9 Voting in Combinatorial Domains
      1. 9.1 Motivations and Classes of Problems
      2. 9.2 Simultaneous Voting and the Separability Issue
      3. 9.3 Approaches Based on Completion Principles
      4. 9.4 Sequential Voting
      5. 9.5 Concluding Discussion
    9. 10 Incomplete Information and Communication in Voting
      1. 10.1 Introduction
      2. 10.2 Models of Partial Preferences
      3. 10.3 Solution Concepts with Partial Preferences
      4. 10.4 Communication and Query Complexity
      5. 10.5 Preference Elicitation
      6. 10.6 Voting with an Uncertain Set of Alternatives
      7. 10.7 Compilation Complexity
      8. 10.8 Social Choice from a Utilitarian Perspective
      9. 10.9 Conclusions and Future Directions
  10. Part II Fair Allocation
    1. 11 Introduction to the Theory of Fair Allocation
      1. 11.1 Introduction
      2. 11.2 What Is a Resource Allocation Problem?
      3. 11.3 Solutions and Rules
      4. 11.4 A Sample of Results
      5. 11.5 Conclusion
    2. 12 Fair Allocation of Indivisible Goods
      1. 12.1 Preferences for Resource Allocation Problems
      2. 12.2 The Fairness versus Efficiency Trade-Off
      3. 12.3 Computing Fair Allocations
      4. 12.4 Protocols for Fair Allocation
      5. 12.5 Conclusion
    3. 13 Cake Cutting Algorithms
      1. 13.1 Introduction
      2. 13.2 The Model
      3. 13.3 Classic Cake Cutting Algorithms
      4. 13.4 Complexity of Cake Cutting
      5. 13.5 Optimal Cake Cutting
      6. 13.6 Bibliography and Further Reading
  11. Part III Coalition Formation
    1. 14 Matching under Preferences
      1. 14.1 Introduction and Discussion of Applications
      2. 14.2 Two-Sided Preferences
      3. 14.3 One-Sided Preferences
      4. 14.4 Concluding Remarks and Further Reading
    2. 15 Hedonic Games
      1. 15.1 Introduction
      2. 15.2 Solution Concepts
      3. 15.3 Preference Restrictions and Game Representations
      4. 15.4 Algorithms and Computational Complexity
      5. 15.5 Further Reading
    3. 16 Weighted Voting Games
      1. 16.1 Introduction
      2. 16.2 Basic Definitions
      3. 16.3 Basic Computational Properties
      4. 16.4 Voter Weight versus Voter Power
      5. 16.5 Simple Games and Yes/No Voting Systems
      6. 16.6 Conclusions
      7. 16.7 Further Reading
  12. Part IV Additional Topics
    1. 17 Judgment Aggregation
      1. 17.1 Introduction
      2. 17.2 Basics
      3. 17.3 Aggregation Rules
      4. 17.4 Agenda Characterization Results
      5. 17.5 Related Frameworks
      6. 17.6 Applications in Computer Science
      7. 17.7 Bibliographic Notes and Further Reading
    2. 18 The Axiomatic Approach and the Internet
      1. 18.1 Introduction
      2. 18.2 An Axiomatic Characterization of PageRank
      3. 18.3 Trust-Based Recommendations
      4. 18.4 Mechanisms for Multilevel Marketing
      5. 18.5 Discussion: Additional Applications
    3. 19 Knockout Tournaments
      1. 19.1 Introduction
      2. 19.2 Formal Definition and Some Properties
      3. 19.3 Agenda Control for General Knockout Tournaments
      4. 19.4 Agenda Control for Balanced Trees Is Easy for Special Instances
      5. 19.5 Extensions and Further Reading
  13. References
  14. Index