CS 269I: Incentives in Computer Science
- Office hours: Mondays 11am-Noon, Gates 474.
- Email: firstname.lastname@example.org.
- Office hours: Mondays and Tuesdays, 1:30-3pm (for both), in
- Email: email@example.com.
- Office hours: Wednesdays 2-3:30pm and Fridays 1:30-3pm, in Gates B26.
- Email: firstname.lastname@example.org.
- Office hours: Tuesdays 10-11:30am and Thursdays noon-1:30pm, in Gates B30.
- Email: email@example.com.
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.
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.
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).
- Lecture 1 (The Draw/College Admissions)
[notes from 2016]
- Lecture 2 (Stable Matching) [notes from 2016]
- Lecture 3 (Markets, Everywhere)
- Lecture 4 (Asymmetric Information)
[notes from 2016]
- Lecture 5 (Market-Clearing Prices)
- 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]
- 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%):
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
- 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
- Lecture 2 (Wed Sept 26):
Stable matchings. Properties of the deferred acceptance
(Gale-Shapley) mechanism. Could college admissions go through a
- 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.
- 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.
Sybil attacks. Case study: the evolution of eBay's reputation system.
- 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
- 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.
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.
Case study: reserve prices in Yahoo! keyword auctions.
- 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.
Previous offering: Fall 2016. (Overlap will be about 75%.)