Incentives in Computer Science

CSE 490z: Incentives in Computer Science (Spring 2020)

[course information | lectures | resources | discussion board

announcements

Welcome to "Incentives in Computer Science"!
You can find the zoom links for all lectures and office hours here (as well as lecture recordings).
You can find all assignments here.
- Homework 6 is posted (due May 30, 11:59pm).
- Homework 7, which is an extra credit assignment, is posted (due June 8, 11:59pm).

lectures

March 30: Administrivia

April 3: Intro to matching and allocation problems.
- References:
  - Chapter 10 of Game Theory, Alive.
  - The Draw and TTCA (Section 3 only) by Tim Roughgarden.
    Note that in Tim's TTCA notes, "DSIC" means "truthful" and "in the core" means "stable".
  - Popular articles about kidney exchange and beyond: here and here.
April 6: Stable Matching
- References:
  - Chapter 10 of Game Theory, Alive.
  - Stable Matching, by Tim Roughgarden
April 10: Wrap up stable matching; Start game theory
- References:
  - Stable marriage and coupon collecting
  - Unbalanced random matching markets: the stark effect of competition
April 13: Basics of game theory (dominant strategies, Nash equilibrium)
- References:
  - For a very gentle introduction, see this chapter from Kleinberg and Easley
  - Roughgarden Lecture 6 Section 1
  - Game Theory, Alive. Sections, 2.1-2.4.3, 2.5, 4.1-4.2, 6.1, 6.4.1
  - Some slides from Stanford about network effects and cascading behavior
April 17: More basics of game theory (zero-sum games, extensive form games)
- References:
  - A Safer World, Using Stackelberg games for security
April 20: Repeated games; intro fair division.
- References:
  - A Safer World, Using Stackelberg games for security
  - Roughgarden Lecture 5 Sections 2-3
  - Incentives build robustness in BitTorrent
  - Do incentives build robustness in BitTorrent?
April 24: Fair division; intro to auctions
- References:
  - How to cut cake fairly and finally eat it too by Erica Klarreich.
  - Introduction to auctions by Tim Roughgarden
  - Chapter 11 and 14.1-14.4 of Game Theory, Alive.
April 27: Single-item auctions, revenue equivalence
- References:
  - More on auctions by Tim Roughgarden
  - Chapter 11 and 14.1-14.4 of Game Theory, Alive.
May 1: Sponsored search auctions
- References:
  - VCG by Tim Roughgarden
  - Wired article about Facebook and VCG
  - The VCG Auction in Theory and Practice by Hal Varian.
  - Chapter 15.1-15.5 of Game Theory, Alive.
May 4: VCG, intro revenue maximization
- References:
  - Revenue maximizing auctions, by Tim Roughgarden
  - The first price auction in online display advertising, by Despotakis, Ravi and Sayedi.
  - Credible mechanisms, by Akbarpour and Li
  - Chapter 14.8-14.9, 14.11, 15.6 of Game Theory, Alive.
May 8: More revenue maximization
May 11: Digital goods auctions, Scoring Rules
- References:
  - Scoring rules and incentivizing honest feedback, by Tim Roughgarden
  - Chapter 16.3 of Game Theory, Alive.
May 15: Discussion of strategy design 1
May 18: Prediction markets
- References:
  - Prediction markets, by Tim Roughgarden
May 22: Intro to Bitcoin
- References:
  - Bitcoin, under the hood by Aviv Zohar
  - Bitcoin (Investopedia)
May 29 (and part of June 1): Strategic behavior in Bitcoin
- References:
  - Majority is Not Enough: Bitcoin mining is vulnerable by Eyal and Sirer
  - The Miner's Dilemma by Eyal
  - On the instability of Bitcoin without the block reward by Carsten, Kalodner, Weinberg and Narayanan.
June 1: Price of anarchy
- References:
  - Selfish routing and network overprovisioning by Tim Roughgarden.
  - Modeling network traffic using game theory, chapter from Kleinberg and Easley.
  - Selfish routing and the price of anarchy by Tim Roughgarden.
  - More on selfish routing by Tim Roughgarden.
  - Chapters 8 of Game Theory, Alive.

resources

Programming: For the programming portions of the homeworks, you will need to use Java. Here is some relevant information.
Latex: Here is a LaTeX template that you can use to type up solutions. Here and here are introductions to LaTeX.

course information

About this course:
Many modern applications require the design of software or systems that interact with multiple self-interested participants. This course will teach students how to think about and analyze such systems using economic and game theoretic principles. Topics include auctions (e.g., Facebook's advertising system), equilibrium analysis, cryptocurrencies (e.g. the incentive structure of Bitcoin), two-sided markets (online labor markets, dating markets, etc.),and reputation systems.

References:

Game Theory, Alive. by A. Karlin and Y. Peres.
Incentives in computer science, CS 269I at Stanford, Tim Roughgarden
Algorithmic game theory, CS 364A at Stanford, Tim Roughgarden
Networks, Crowds and Markets, by Easley and Kleinberg.

Tentative syllabus (may change):

Matching and allocation problems, stability and incentives.
Introduction to Game Theory, Nash equilibrium, dominant strategies, normal form and extensive form games.
Price of anarchy for traffic and network over-provisioning.
Auctions: First price, second price, ad auctions, VCG mechanism, combinatorial and spectrum auctions.
Markets and the issues faced such as asymmetric information; reputation systems, market clearing prices, first welfare theorem and auction algorithm.
Incentives in cryptocurrencies.
Online learning in markets.
Scoring rules and prediction markets.
Time inconsistent planning, behavioral economics; differential privacy.
Voting

Instructor: Anna Karlin, CSE 594, tel. 543 9344
Time: Mondays and Fridays; 1:30 - 2:50pm over zoom.
Office hours: Mondays 3:30 - 4:30 pm over zoom and by appointment -- send email.

Teaching assistant:

Aditya Saraf send email.

Office hours: Wednesdays 2-3pm over zoom and by appointment.

Course evaluation: 6-8 homeworks, mix of programming and theoretical exercises.