COMS 4995: Incentives in Computer Science
Instructor:
-
Tim
Roughgarden
- Office hours: Wednesdays 3:45-4:45pm, Mudd 410.
- Email: tr@cs.columbia.edu.
Course Assistants:
- Yaonan Jin
- Office hours: Tuesdays 1:30-3:30pm in the TA room, Mudd first floor.
- Email: yj2552@columbia.edu.
-
Eric Neyman
- Office hours: Mondays 3-5pm and Tuesdays 11:30am-1:30pn in the TA
room, Mudd first floor.
- Email: eric.neyman@columbia.edu.
Time/location: 1:10-3:40 PM Wednesdays, in
room 411 of the International Affairs building.
Piazza site: here
Prerequisites: Mathematical maturity at the level of
a 4000-level course such as algorithms (CSOR 4231) or complexity (COMS 4236).
Programming maturity at the level of COMS W3134.
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.
Textbook:
There is no official textbook for the course. There will be lecture notes for most of the lectures. One general reference is
Twenty Lectures on Algorithmic Game Theory, which is
based on a more advanced graduate course. (The overlap with this course will be
roughly 20-25%. Though if you enjoy this course, you're likely to
also enjoy many of the topics in this book.)
Lecture notes
- Lecture 1 (Room assignment/stable matching): Part 1; Part 2
- Lecture 2 (Markets, Everywhere):
See here
and Sections 1 and 2 here.
- Lecture 3 (Competitive equilibra; information asymmetry):
See Section 3 here
for the first half of lecture, and here for the second.
- Lecture 4 (Sponsored search auctions):
See here,
Sections 2 and 3 here, and Sections 1 and 2 here.
- Lecture 5 (VCG and revenue maximization):
See Sections 3 and 4 here and Section 1 here
and Section 3 here.
- Lecture 6 (Scoring rules and prediction markets): Part 1; Part 2
- Lecture 7 (Incentives in cryptocurrencies): see
here
and Section 1 here.
- Lecture 8 (Incentives in networks): Part 1; Part 2
- Lecture 9 (Time-Inconsistent Planning): here
- Lecture 10 (Voting and Fair Division):
Part 1 and
Part 2 (Section 5 only) and
Part 3.
- Lecture 11 (Spectrum auctions): pages 62-64 of these notes and
Sections 2 and 3 of these notes.
- Exercise Sets (50%):
Exercise sets will be handed out on Wednesdays and will be due one
week later, by noon.
- Week 1 Exercises (out Wed Jan 22, due Wed Jan 29)
- Week 2 Exercises (out Wed Jan 29, due Wed Feb 5)
- Week 3 Exercises (out Wed Feb 5, due Wed Feb 12)
- Week 4 Exercises (out Wed Feb 12, due Wed Feb 19)
- Week 5 Exercises (out Wed Feb 19, due Wed Feb 26)
- Week 6 Exercises (out Wed Feb 26, due Wed Mar 4)
- Week 7 Exercises (out Wed Mar 4, due Wed Mar 11)
- Week 8 Exercises (out Wed Mar 11, due Wed Apr 1)
- Week 9 Exercises (out Wed Apr 1, due Wed Apr 8)
- Week 10 Exercises (out Wed Apr 8, due Wed Apr 15)
- Exercise Set Policies:
- To be submitted in groups of 1 or 2
(all students of the group receive the same score).
- You can form different pairs for different exercise sets.
- You can discuss exercises with students from other groups
verbally and at a high level only.
-
Except where otherwise noted, you may refer to your course notes, the
textbooks and research papers listed on the course Web
page only. You cannot refer to textbooks, handouts, or
research papers that are not listed on the course home page. If you
do use any approved sources, make you sure you cite them
appropriately, and make sure that all your words are your own.
- You are strongly encouraged to use LaTex to typeset your write-up.
Here's a LaTeX template that you can use to
type up solutions. Here
and here are good
introductions to LaTeX.
- Honor code: We expect you to abide by the computer science department's
policies and procedures regarding academic honesty.
- Submission instructions:
We are using Gradescope for the homework submissions. Go to
www.gradescope.com to either login or create a new
account. Use the
course code MKRKK6 to register for this class. Only one group member
needs to submit the assignment. When submitting, please remember to
add all group member names onto Gradescope.
- Late Days:
- One late day equals a 24-hour extension.
- Each student has three free late days.
- At most two late days can be applied to a single assignment;
after Friday (following the original due date) no solutions
will be accepted.
- Each late day used after the first two will result in a 25%
penalty.
- Example: a student had one free late day remaining but his/her
group uses two late days on a Problem Set. If the group's write-up
earns p points, the student receives a final score of .75*p points
for the assignment.
- Final Project (50%):
This will be a team project, with up to 4 people per team.
For details, deadlines, and some example topics, see here.
Exemplary reports from past offerings:
- Week 1: Introduction to incentives (room assignment and stable matching).
- Week 2: Markets: examples, properties, and design decisions.
- Week 3: Asymmetric information, adverse selection, moral hazard.
- Week 4: Auctions, Part 1 (Vickrey and sponsored search auctions).
- Week 5: Auctions, Part 2 (VCG and spectrum auctions).
- Week 6: Scoring rules, peer grading, prediction markets.
- Week 7: Incentives in cryptocurrencies.
- Week 8: Incentives in networks (communication, peer-to-peer, social, etc.).
- Week 9: The price of anarchy. Time-inconsistent planning.
- Week 10: Social choice: voting and fair division.
- Week 11: Incentives and algorithms in kidney exchange.
- Week 12: Student presentations.
- Week 13: Student presentations.
- Week 14: Student presentations.
- Lecture 1 (Wed Jan 22):
The incentives of room assignment.
Pareto optimality and strategyproofness.
College admissions. One-sided
vs. two-sided markets. The National Resident Matching Program
(NRMP).
Stable matchings. Properties of the deferred acceptance
(Gale-Shapley) mechanism. Could college admissions go through a
centralized clearinghouse?
Supplementary reading:
- Lecture 2 (Wed Jan 29):
Markets from (almost) the 21st century. Centralized vs. decentralized markets. Market failures: timing issues, safety issues, thinness, congestion. Signaling to combat congestion. Markets for goods, with prices.
Demand and supply curves. Market-clearing prices for fungible goods.
Supplementary reading:
- Lecture 3 (Wed Feb 5):
Idiosyncratic goods and competitive equilibrium. First Welfare
Theorem. Existence of competitive equilibria in matching markets with
money.
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 4 (Wed Feb 12):
Auction design basics.
The Vickrey auction and truthfulness.
Welfare maximization.
Sponsored search auctions: the Generalized Second Price (GSP) and Vickrey-Clarke Groves (VCG) auctions. Case studies: Google and Facebook.
- Lecture 5 (Wed Feb 19):
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 6 (Wed Feb 26):
Strictly proper scoring rules. Incentivizing honest opinions.
Peer prediction.
Prediction markets.
Market scoring rules and automated market-makers.
- Lecture 7 (Wed Mar 4):
Incentives in Bitcoin mining. Transactions and the Bitcoin blockchain
protocol. Forks.
Incentive issues: the 51% attack, the double-spend
attack, and selfish mining. Bitcoin in a regime with high transaction fees. Incentives in proof-of-stake cryptocurrencies.
Supplementary reading:
- Lecture 8 (Wed Mar 11):
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).
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
path verification.
Supplementary reading:
- [Spring break]
- [no class March 25]
- Lecture 9 (Wed Apr 1):
Behavioral economics. Time-inconsistent planning: procrastination,
choice reduction, and undue obedience. Upper and lower bounds on cost
ratios. Naive vs. sophisticated agents.
- Lecture 10 (Wed Apr 8):
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.
Knapsack voting and participatory budgeting.
Supplementary reading and resources:
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.
- Lecture 11 (Wed Apr 15):
Case study: wireless spectrum auctions. Readings:
- Lecture 12 (Wed Apr 22):
Student presentations (format TBD).
- Lecture 13 (Wed Apr 29):
Student presentations (format TBD).