CS 396: Online Markets

Picasso's Bulls

Current Term: Spring 2020.

Online markets are causing significant changes to society. Examples include eBay, airBnB, tinder, Uber, stackexchange, and Amazon. This class gives an introduction to the science of online markets combining topics from game theory and economics with topics from machine learning and algorithms. The two main topics of interest are how individuals in these market places optimize their strategies and how the market designer optimizes the rules of the market place so that, when individuals optimize their strategies, desired market outcomes are achieved. Student work will be a mix of problem sets and short projects.

Prerequisites: CS 212 (Discrete Math) and CS 214 (Data Structures) or CS 336 (Algorithms) or ECON 380-1 (Game Theory).

Grading: 40% problem sets, 30% projects, 15% midterm, 15% final.

Homework Policy: Homeworks and projects are to be done in pairs. Both students must contribute to the solution of all problems. One copy of the assignment should be turned in. Both students will receive the same grade.

Tentative Schedule:

  • Week 1: Auctions and Algorithms
    • Topics: first-price auction, second-price auction, secretary problem, prophet inequality.
  • Week 2: Matching
    • Topics: offline matching, online matching, matching mechanisms.
  • Week 3: Equilibria
    • Topics: Nash equilibria, dominant strategy equilibria, Bayes-Nash equilibria.
  • Weeks 4-5: Online Learning
    • Topics: expert learning, multi-armed bandit learning, external regret, internal regret.
  • Week 6: Optimal Auctions
    • Topics: Welfare maximization, revenue maximization, reserve pricing.
  • Week 7: Equilibrium Analysis (the price of anarchy)
    • Topics: first-price auctions, simultaneous first-price auctions.
  • Weeks 8-9: Econometrics
    • Topics: learning agents, price of anarchy from data, counterfactual estimation.
  • Week 10: Elicitation.
    • Topics: Scoring rules, Bayesian truth serum, peer prediction.