CS 269I: Incentives in Computer Science
Instructor:
-
Tim
Roughgarden
- Office hours: Mondays 11am-Noon, Gates 474.
- Email: tim@cs.stanford.edu.
Course Assistants:
-
Austin Jones
- Office hours: Mondays and Tuesdays, 1:30-3pm (for both), in
Gates B28.
- Email: austinhj@stanford.edu.
-
Pratyaksh Sharma
- Office hours: Wednesdays 2-3:30pm and Fridays 1:30-3pm, in Gates B26.
- Email: praty@stanford.edu.
-
Ashwin Sreenivas
- Office hours: Tuesdays 10-11:30am and Thursdays noon-1:30pm, in Gates B30.
- Email: ashwinsr@stanford.edu.
Time/location: 9:30-10:50 AM Mon/Wed in
room 128 of the Education building.
Piazza site: Here
Prerequisites: Mathematical maturity at the level of undergraduate algorithms (CS161). Programming maturity at the level of 106B/X.
Course Description:
Many 21st-century computer science applications require the design of software or systems that interact with multiple self-interested participants. This course will provide students with the vocabulary and modeling tools to reason about such design problems. Emphasis will be on understanding basic economic and game theoretic concepts that are relevant across many application domains, and on case studies that demonstrate how to apply these concepts to real-world design problems. Topics include auctions (for spectrum and online advertising), equilibrium analysis, cryptocurrencies, network protocols, two-sided markets (online labor markets, dating markets, etc.), crowdsourcing, reputation systems, and social choice. Case studies include Bitcoin and Ethereum, eBay's reputation system, Facebook's advertising mechanism, Mechanical Turk, and Augur's prediction markets.
General references: Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
See also the Amazon page.
- This textbook is based on the course CS364A. The overlap with 269I will be
roughly 20-25%. Though if you enjoy this course, you're likely to
also enjoy many of the topics in this book.
The following collection
is older and targeted more to researchers than to students,
but is still useful for several topics.
-
Algorithmic
Game Theory, Cambridge University Press, 2007.
Read the entire book online by clicking
here
(look under the "Resources" tab).
We will also draw on the following books for some of the lectures.
Lecture notes
- Lecture 1 (The Draw/College Admissions)
[notes from 2016]
- Lecture 2 (Stable Matching) [notes from 2016]
- Lecture 3 (Markets, Everywhere)
[beta version]
- Lecture 4 (Asymmetric Information)
[notes from 2016]
- Lecture 5 (Market-Clearing Prices)
[beta version]
- Lecture 6 (Spectrum Auctions)
- First half of lecture: see slides
and pages 62-64 of these notes;
second half: Sections 2 and 3 of these notes.
- Lecture 7 (Auction Basics)
- Lecture 8 (VCG Auctions)
- Lecture 9 (Scoring Rules)
[notes from 2016]
- Lecture 10 (Prediction Markets)
[notes from 2016]
- Lecture 11 (Incentives in P2P)
[notes from 2016]
- Lecture 12 (Incentives in Bitcoin)
[notes from 2016]
- Lecture 13 (Proof-of-Stake Cryptocurrencies) [no notes]
- Lecture 14 (Incentives in Crowdsourcing) [notes from 2016]
- Lecture 15 (Kidney Exchange) [no notes]
- Lecture 16 (Participatory Budgeting) [no notes]
- Lecture 17 [Strategic Voting]
- Lecture 18 (Fair Division)
[notes from 2016]
- Lecture 19 [Time-Inconsistent Planning]
[notes from 2016]
- Exercise Sets (50%):
Exercise sets will be handed out on Wednesdays and will be due one
week later.
You can work in pairs, if you wish.
- Final Project (50%):
This will be a team project. A
project proposal will be due around midterms and the final project
at the end of the course.
For details and some example topics, see
here.
Announcement: Due to logistical difficulties, the
poster session has been cancelled. The written report is still
due Friday, December 7th.
Exemplary reports from 2016:
- Week 1: Introduction to incentives through killer examples.
- Week 2: Decentralized two-sided markets, reputation.
- Week 3: Auction basics. Spectrum auctions.
- Week 4: The VCG mechanism and Facebook. Crowdsourcing.
- Week 5: Scoring rules, peer grading, prediction markets.
- Week 6: Incentives in cryptocurrencies.
- Week 7: Incentives in networks (communication, peer-to-peer, social, etc.).
- Week 8: Guest lectures on kidney exchange and participatory budgeting.
- Week 9: Social choice: voting and fair division.
- Week 10: Incentives in machine learning. Lessons from behavioral economics (i.e., how do people
make decisions, anyway?).
- Lecture 1 (Mon Sept 24): The incentives of the Draw, past
and present. Pareto optimality and strategyproofness.
College admissions. One-sided
vs. two-sided markets. The National Resident Matching Program
(NRMP).
Supplementary reading:
- Lecture 2 (Wed Sept 26):
Stable matchings. Properties of the deferred acceptance
(Gale-Shapley) mechanism. Could college admissions go through a
centralized clearinghouse?
Supplementary reading:
- Lecture 3 (Mon Oct 1):
Markets from (almost) the 21st century. Centralized vs. decentralized markets. Market failures: timing issues, safety issues, thinness, congestion. Signaling to combat congestion.
Supplementary reading:
- Lecture 4 (Wed Oct 3):
Adverse selection, moral hazard, and reputation systems.
The market for lemons.
Analogs in health insurance, the labor market, and online platforms.
Moral hazard.
Whitewashing and
Sybil attacks. Case study: the evolution of eBay's reputation system.
Supplementary reading:
- Lecture 5 (Mon Oct 8): Markets for goods, with prices.
Demand and supply curves. Market-clearing prices for fungible goods.
Idiosyncratic goods and competitive equilibrium. First Welfare
Theorem. Existence of competitive equilibria in matching markets with
money.
- Lecture 6 (Wed Oct 10):
Case study: wireless spectrum auctions. Readings:
- Cramton/Shoham/Steinberg (eds.), Combinatorial Auctions,
MIT Press, 2006.
- Chapter 4 (Cramton) covers simultaneous ascending auctions.
- Chapter 5 (Ausubel/Cramton/Milgrom) discusses how to add a final
"proxy" round with package bidding.
- Milgrom, Chapter 1 of Putting Auction Theory to Work, Cambridge, 2004.
- Goeree/Holt, Hierarchical Package Bidding, about bidding only on predefined packages.
- Milgrom/Segal, Deferred-Acceptance Heuristic Auctions, 2014.
Describes the format for the reverse auction in the FCC Incentive Auction.
- Lecture 7 (Mon Oct 15):
Auction design basics.
The Vickrey auction and truthfulness.
Welfare maximization.
Sponsored search auctions: the Generalized Second Price (GSP) and Vickrey-Clarke Groves (VCG) auctions.
- Lecture 8 (Wed Oct 17):
The general VCG mechanism and its
truthfulness. Practical issues with VCG. Case study: advertising at Facebook.
Monopoly prices.
Case study: reserve prices in Yahoo! keyword auctions.
Supplementary materials:
- Lecture 9 (Mon Oct 22):
Strictly proper scoring rules. Incentivizing honest opinions.
Output agreement. Peer prediction. Further reading:
- Section 27.4 of the AGT book (see general references).
- Chapter 17 of the Parkes/Suen book (see general references).
- Lecture 10 (Wed Oct 24):
Prediction markets. The Iowa Electronic Markets and continuous double
auctions. The Policy Analysis Market and the Wisdom of Crowds.
Market scoring rules and automated market-makers.
Further reading:
- Lecture 11 (Mon Oct 29): Incentives in peer-to-peer (P2P)
networks. History lesson: Napster, Gnutella, etc. Free riding on
Gnutella. Prisoner's Dilemma. Repeated Prisoner's Dilemma: the
grim trigger and Tit-for-Tat stategies.
Tit-for-tat in the BitTorrent
reference client. Strategic clients (BitThief and BitTyrant).
Supplementary reading:
- Lecture 12 (Wed Oct 31):
Incentives in Bitcoin mining. Transactions and the Bitcoin blockchain
protocol. Forks.
Incentive issues: the 51% attack, the double-spend
attack, and selfish mining.
Supplementary reading:
- Lecture 13 (Mon Nov 5):
Incentives in proof-of-stake cryptocurrencies.
Digression on Ethereum. Stake-weighted sampling and its implementation in Ouroboros and Algorand. Issues: nothing-at-stake, local and global predictability. Related papers:
- Lecture 14 (Wed Nov 7):
Incentives in crowdsourcing.
Bitcoin in a regime with high transaction fees.
The DARPA Network Challenge and incentivizing recruitment.
Sybil attacks and possible solutions.
The "Wisdom of the Crowd": fact or fiction? Herding behavior and
information cascades.
Supplementary reading:
- Lecture 15 (Wed Nov 12):
Guest lecture by Mohammad Akbarpour.
- Lecture 16 (Wed Nov 14):
Guest lecture by Ashish Goel.
- Lecture 17 (Mon Nov 26):
Strategic voting.
Spoilers and the 2000 US election.
Majority, plurality, ranked-choice voting, Borda counts.
Gibbard-Satterthwaite and the impossibility of reasonable
strategyproof voting rules.
Compromises, single-peaked preferences, and the median voting rule.
Subjective vs. objective interpretations of voting rules.
Marquis de Condorcet and majority rule as a
maximum likelihood estimator. The Kemeny-Young rule.
Supplementary reading and resources:
- Participatory budgeting
in general
and at Stanford.
- The rank aggregation problem.
-
Reasonably short proofs of the Gibbard-Satterthwaite and Arrow impossibility theorems are here (see Sections 1.2.3 and 1.2.4).
- Chapter 23 of the Easley/Kleinberg book (see general references).
- The dramatic life of Marquis de Condorcet.
- See Pnyx for an implementation of the Kemeny rule.
- Knapsack voting, by Goel/Krishnaswamy/Sakshuwong (2014).
- Section 15.2 of the Parkes/Suen book (see general references).
- Lecture 18 (Wed Nov 28):
Fair division. The cut and choose protocol and envy-freeness. The
Selfridge-Conway envy-free protocol for 3 players. Recent advances
for 4 or more players. The rent division problem, and the maxmin
envy-free solution. Further reading:
- Lecture 19 (Mon Dec 3):
Behavioral economics. Time-inconsistent planning: procrastination,
choice reduction, and undue obedience. Upper and lower bounds on cost
ratios. Naive vs. sophisticated agents. Further reading:
Previous offering: Fall 2016. (Overlap will be about 75%.)