CSEp 590b: Incentives in Computer Science (Winter 2020)

[course information | lectures | homework | resources | discussion board

announcements

• Upload your final project report (must be a pdf) both to piazza (tag "project_reports") and to canvas. Due March 15 at 11:59pm.

• If you wrote code as part of your project, upload a single zip file containing everything to canvas, also by March 15, 11:59pm..

lectures

• January 7: Administrivia; Matching and allocation problems.
  • References:
    • Chapter 10 of Game Theory, Alive.
    • The Draw, Stable Matching and TTCA (Section 3 only) by Tim Roughgarden.
      Note that in Tim's TTCA notes, "DSIC" means "truthful" and "in the core" means "stable".

• January 21: Basics of game theory (dominant strategies, Nash equilibrium, zero-sum games, extensive form games, repeated games)
  • References:
    • For a very gentle introduction, see this chapter from Kleinberg and Easley
    • Roughgarden Lecture 5 Sections 2-3
    • 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
    • A Safer World, Using Stackelberg games for security

• January 28: 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.

• February 4: Fair division; auctions
  • References:
    • How to cut cake fairly and finally eat it too by Erica Klarreich.
    • Introduction to auctions by Tim Roughgarden
    • More on auctions by Tim Roughgarden
    • Chapter 11 and 14.1-14.4 of Game Theory, Alive.

• February 11: Sponsored search auctions, VCG
  • References:
    • Introduction to auctions by Tim Roughgarden
    • More on auctions by Tim Roughgarden
    • VCG by Tim Roughgarden
    • Wired article about Facebook and VCG
    • Chapter 15.1-15.5 of Game Theory, Alive.

• February 18: FCC Incentive Auction, Intro to Bitcoin
  • References:
    • Combinatorial and Wireless Spectrum Auctions by Tim Roughgarden
    • Videos about FCC Incentive Auction: #1, # 2, #3
    • Bitcoin, under the hood by Aviv Zohar
    • Bitcoin (Investopedia)

• February 25: Strategic behavior in Bitcoin
  • References:
    • Majority is Not Enough: Bitcoin mining is vulnerable by Eyal and Sirer
    • The Miner's Dilemma by Eyal

• March 3: Strategic behavior in Bitcoin cont., more on equilibria and online learning
  • References:
    • On the instability of Bitcoin without the block reward by Carsten, Kalodner, Weinberg and Narayanan.
    • Hierarchy of equilibrium concepts and potential games , Roughgarden.
    • Best response dynamics, sections 1 and 2, Roughgarden.
    • No regret dynamics, Roughgarden.
    • The Multiplicative Weights Update Method: A Meta-Algorithm and Applications by Arora, Hazan Kale

homework

• Exercise Set 1; due January 16.
• Programming Project 1; due February 2.
• Exercise Set 2; due February 5.
• Programming Project 2; due February 16.
• Programming Project 3; due February 23.
• Programming Project 4; due March 8.

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

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: Tuesdays, 6:30 -- 9:20pm in G04
Office hours:  By appointment -- send email.

Teaching assistant: