MS&E 336/CS 366: Computational Social Choice

Winter 2019-20

Mon, Wed 1:30-2:50pm
Room 460-334

Ashish Goel, 650 814 1478
Office Hours: M 4-5 pm, or by appointment, Huang 359

"Social Choice" is the study of collective decision making, elections being the simplest example. With the advent of the Internet, polarized democratic processes, and new modes of social interaction, this field has gained renewed interest and importance. This class will be suited for graduate (and advanced undergraduate) students who want to do research in computational and algorithmic aspects of social choice, or who would like to learn more about an important application and techniques at the intersection of algorithms, game-theory, and the social sciences.

From the Course Bulletin

An in-depth treatment of algorithmic and game-theoretic issues in social choice. Topics include common voting rules and impossibility results; ordinal vs cardinal voting; market approaches to large scale decision making; voting in complex elections, including multi-winner elections and participatory budgeting; protocols for large scale negotiation and deliberation; fairness in societal decision making; algorithmic approaches to governance of modern distributed systems such as blockchains and community-mediated social networks; opinion dynamics and polarization.

Pre-reqs: Either (a) Instructor’s consent or (b) Algorithms at the level of CS 161/MS&E 212; Probability at the level of MS&E 221; basic Game Theory

The course requirements will be:
  1. Each student will be asked to scribe one lecture (10% of the grade).
  2. Two HWs, which can be done in groups of 2-3 (20% of the grade). Given Jan 30, Feb 18. Due Feb 9, Feb 28 before midnight.
  3. A take-home midterm (30%). Given Feb 12th before midnight. Due Feb 14th 2pm.
  4. Reading 4-6 research papers in preparation for the class.
  5. A project report with optional presentation (40%).

    Each report should be done in groups of 2-3, and should involve a survey of an open problem, along with possible directions, and some progress for small special cases (or even the full problem). The project selection will be due at the end of the 4th week of classes (Feb 6th), but you are welcome to get an early start if you like. A preview of suggested open problems to study will be presented in the second week of classes. All material needed for the open problems will be covered by the 6th week of classes.

    Preliminary report due: Mar 2nd.
    Final report due: Mar 16th


HCSC refers to the Handbook of computational social choice, available as a downloadable pdf or print text. AGT refers to Algorithmic Game Theory, available as an online book from the Stanford Library. We will interleave introductory material and in-depth topics.

Introductory Material:
  1. A summary of voting rules. The Condorcet criterion, Copeland, Borda, Ranked Pairs, Run-offs, Transferable Single Vote.  HCSC Chapter 1 and 2.1-2.7, class notes.
  2. A brief introduction to Game-theoretic implementation concepts. AGT Chapter 1, 9.1-9.4, 5.1-5.2
    1. Nash Equilibrium, Incentive Compatibility, sub-game Perfect Equilibria, and repeated games.
    2. Fisher markets.
    3. Bargaining in two person groups: Nash bargaining and Kalai–Smorodinsky bargaining.
  3. Impossibility results in strategic voting: The Gibbard-Satterthwaite theorem: a simple proof (in brief). HCSC Chapter 2.6.
  4. Getting around the Gibbard-Satterthwaite theorem: special classes of voter utilities. The Median voting rule, and “Vox Populi”. Approval Voting. HCSC Chapter 2.7.
  5. Opinion Dynamics: deGroot, Attitude polarization, Schelling Segregation. Open problem: On the Convergence of the Hegselmann-Krause System.

    Note: At this point, we will be in the 7th week of classes, and all material required for the projects will be complete.
  6. Maskin’s Monotonicity Theorem: Proof and implications. The original paper by Maskin which is quite easy to read. Also see HCSC Chapter 2.6.
  7. Three Brief Proofs of ARROW'S IMPOSSIBILITY THEOREM (read this paper in brief; the current wikipedia page on Arrow's impossibility theorem has a short proof which you should read in detail. The proof on wikipedia may of course change later, but you can use this permalink for the proof that I verified.) Getting around Arrow’s Impossibility theorem: Randomized voting rules.
  8. A statistical view of voting rules. HCSC 8.3.
  9. Notions of fairness — envy freeness, proportionality, and core (HCSC Chapter 11); Approximate majorization; The core of the participatory budgeting problem

Applications and In-depth Treatment:
  1. From ordinal to cardinal decision making.
    1. Utility-centric approach: Optimal social choice functions: A utilitarian view
    2. Cost-centric approach: Approximating Optimal Social Choice under Metric Preferences
    3. Open problems: Metric Distortion of Social Choice Rules, Improved Metric Distortion for Deterministic Social Choice Rules
  2. Participatory Budgeting
            Knapsack voting for participatory budgeting
            Truthful Aggregation of Budget Proposals
  3. Sequential deliberation for social choice rules. Open problem: sequential deliberation for budgeting problems.
  4. Blockchain governance and forking (invited talk and open problems).

    Note: At this point, we will be in the 7th week of classes, and all material required for the projects will be complete.
  5. Cake-cutting in practice. HCSC Chapter 13, .
  6. Mechanism Design without Money. AGT Chapter 10, Markets for public decision making.
  7. Committee selection and multi-winner elections. HCSC chapter 9.
  8. Additional case studies (time permitting): Bayesian persuasion, the MIT moral machine, crowdsourcing societal tradeoffs, judgement aggregation.