CS 269I: Incentives in Computer Science
- Sept 26: Welcome to CS269I!
Roughgarden (Office hours (note new time): Mondays 12:15-1:15 PM, Gates 474. Email: firstname.lastname@example.org.)
(Office hours: Wednesdays 4-6PM, Gates 460.
Email: email@example.com.) (Starting 10/5.)
(Office hours: Tuesdays 10:30AM-12:30PM, Gates 482.
Email: firstname.lastname@example.org.) (Starting 10/4.)
(Office hours (note new time): Fridays 2-4PM, Gates 466.
Email: email@example.com.) (Starting 9/30.)
Time/location (new room!): 10:30-11: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.
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 auction and contest design, equilibrium
analysis, cryptocurrencies, design of networks and network protocols,
matching markets, reputation systems, and social choice. Possible case studies
include BGP routing, Bitcoin, eBay's reputation system, Facebook's
advertising mechanism, Mechanical Turk, and dynamic pricing in
General references: Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
See also the Amazon page.
The following collection
is older and targeted more to researchers than to students,
but is still useful for several topics.
- 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.
We will also draw on the following books for some of the lectures.
Game Theory, Cambridge University Press, 2007.
Read the entire book online by clicking
(look under the "Resources" tab).
- Exercise Sets (50%):
Exercise sets will be handed out on Wednesdays and will be due one
You can work in pairs, if you wish.
- Final Project (50%):
For details and some example topics, see here.
- Week 1: Introduction to incentives through killer examples.
- Week 2: Social choice (voting, Arrow's impossibility theorem,
- Week 3: Incentives in peer-to-peer and social networks (e.g.,
incentives in BitTorrent).
- Week 4: Incentives in communication networks (routing, flow
- Week 5: Incentives in cryptocurrencies (like Bitcoin).
- Week 6: Reputation systems. Incentives in crowdsourcing.
- Week 7: Basic auction theory (eBay, sponsored search auctions).
- Week 8: Advanced auction theory and mechanism design (Facebook
advertising auctions, contest design).
- Week 9: Scoring rules and prediction markets.
- Week 10: Lessons from behavioral economics (i.e., how do people
make decisions, anyway?).
- Lecture 1 (Mon Sept 26): 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
- Lecture 2 (Wed Sept 28):
Stable matchings. Properties of the deferred acceptance
(Gale-Shapley) mechanism. Could college admissions go through a
- Lecture 3 (Mon Oct 3): Participatory democracy.
Spoilers and the 2000 US election.
Majority, plurality, ranked-choice voting, Borda counts.
Gibbard-Satterthwaite and the impossibility of reasonable
strategyproof voting rules. Arrow's Impossibility Theorem.
Compromises, single-peaked preferences, and the median voting rule.
Supplementary reading and resources:
- Participatory budgeting
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).
- Lecture 4 (Wed Oct 5):
Subjective vs. objective interpretations of voting rules. Metaphor:
linear regression as the maximum likelihood solution with normally
distributed errors. Marquis de Condorcet and majority rule as a
maximum likelihood estimator. The Kemeny-Young rule.
Knapsack voting and its properties.
Supplementary reading and resources:
- 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 5 (Mon Oct 10): 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).
- Lecture 6 (Wed Oct 12):
Coordination games. Technology adoption and network cascades.
Individual vs. collective preferences in public good problems.
Case study: badge design in Stack Overflow, Coursera, etc.
- Lecture 7 (Mon Oct 17):
Selfish routing and network over-provisioning.
Braess's paradox and Pigou's example.
The price of anarchy.
Modest over-provisioning guarantees near-optimal routing.
- Lecture 8 (Wed Oct 19): The Border Gateway Protocol for
Internet routing. Stable routings: non-uniqueness and
non-existence. Dispute wheels and the convergence of BGP to a
unique solution. Incentive issues. Incentive-compatability with
- Lecture 9 (Mon Oct 24):
Incentives in Bitcoin mining. Transactions and the Bitcoin blockchain
Incentive issues: the 51% attack, the double-spend
attack, and selfish mining.
- Lecture 10 (Wed Oct 26):
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
- Lecture 11 (Mon Oct 31):
Incentives in societal networks
by Balaji Prabhakar).
"Nudges" for changing behavior.
Case studies in Bangalore, Singapore, and at Stanford.
- Lecture 12 (Wed Nov 2):
Adverse selection, moral hazard, and reputation systems.
The market for lemons.
Analogs in health insurance, the labor market, and online platforms.
Moral hazard. Reputational effects in the n-person Prisoner's
Dilemma. Whitewashing and the pay-your-dues strategy.
Sybil attacks. Case study: the evolution of eBay's reputation system.
- Lecture 13 (Mon Nov 7):
Auction design basics.
How would you bid in a first-price auction?
The Vickrey auction and truthfulness.
Introduction to sponsored search auctions.
- Lecture 14 (Wed Nov 9):
The theory of first-price auctions. Externalities. VCG: a truthful sponsored search auction. GSP vs. VCG. Supplementary reading:
- Lecture 15 (Mon Nov 14):
Revenue equivalence of the GSP and VCG sponsored search auctions.
VCG in AdSense and Facebook. The general VCG mechanism and its
truthfulness. Practical issues with VCG.
- Lecture 16 (Wed Nov 16):
Revenue maximization. Bayesian optimal auctions.
Monopoly prices. Optimality of Vickrey with a monopoly price reserve.
Case study: reserve prices in Yahoo! keyword auctions.
Prior-independent auctions and the Bulow-Klemperer theorem.
- Lecture 17 (Mon Nov 28):
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 18 (Wed Nov 30):
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.
- Lecture 19 (Mon Dec 5):
Behavioral economics. Time-inconsistent planning: procrastination,
choice reduction, and undue obedience. Upper and lower bounds on cost
ratios. Naive vs. sophisticated agents. Further reading:
- Lecture 20 (Wed Dec 7):
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: