MS&E 336/CS 366: Computational Social Choice

Autumn 2021-22

Mon, Wed 1:30-2:50pm
McCullough 122

INSTRUCTOR
Ashish Goel
ashishg@stanford.edu, 650 814 1478
Office Hours: M 4-5:30 pm, Huang 304 and on zoom (link available here). Priority to in-person students till 5 and to zoom participants thereafter.
Class forum: We will use ed stem as a discussion forum. Sign up link available here.

Auditors: please sign on to the mailman list msande336-aut2122-guests and let the instructor know.

You can also browse last year's class for a rough preview of this year.

DESCRIPTION
"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


REQUIREMENTS
The course requirements will be:
  1. Each student will be asked to scribe one lecture in a group of 2 (10% of the grade). Sign up link available here.
  2. Two HWs, which can be done in groups of 2-3 (40% of the grade). Given Oct 11, Nov 3. Due Oct 22, Nov 14 before midnight.
  3. A take-home midterm (20%). Given Nov 1 before midnight. Due Nov 3 before 2pm.
  4. Reading 4-6 research papers in preparation for the class.
  5. All project submissions and grading etc will be on gradescope. We will use a class forum, but we are still setting it up.
  6. A project report with optional presentation (30%).

    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 (Oct 15th), 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: Nov 17th along with your preference regarding giving a presentation.
    Final report due: Dec 3, midnight
    Brief 10 minute presentations of selected projects: Dec 1.


HANDOUTS

DETAILED LIST OF TOPICS
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, Metric Distortion of Social Choice Rules, Improved Metric Distortion for Deterministic Social Choice Rules, Resolving the Optimal Metric Distortion Conjecture
    3. Open problems: What about a deliberative model?
  2. Participatory Budgeting
            https://pbstanford.org
            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. Gerrymandering : invited talk and open problems.
  5. Blockchain governance and decentralized exchanges.

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