CS 332: Online Markets (formerly CS 396)

Picasso's Bulls

Current Term: Winter 2023.
Previous Terms: Spring 2022, Spring 2020.

Synopsis:
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: any one of:

  • CS 212 (Discrete Math) and CS 214 (Data Structures) or
  • CS 336 (Algorithms) or
  • ECON 380-1 (Game Theory) or
  • IEMS 303 (Statistics) or
  • MMSS 211-2 (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: Online Markets and Empirical Analysis
    • Topics: first-price auction, second-price auction, random variables, Monte Carlo sampling, confidence bounds.
  • Week 2: Game Theory
    • Topics: bimatrix games, Nash equilibrium, dominant strategy equilibrium, Bayes-Nash equilibria; first-price, second-price auctions.
  • Week 3: Online Learning
    • Topics: online learning, exponential weights, multi-armed bandit Learning, regret.
  • Week 4: Learning and Game Theory
    • Topics: learning in games, coarse correlated equilibria, learning to bid, discretization, full feedback, partial feedback.
  • Week 5: Welfare in Equilibrium
    • Topics: welfare analysis in equilibrium, competitive efficiency, individual efficiency, second-price with reserve.
  • Week 6: Revenue
    • Topics: pricing revenue, virtual values, optimal reserves, revelation principle, optimal auctions, virtual welfare maximization.
  • Week 7: Learning Auctions and Econometrics
    • Topics: learning to price, learning to auction, inferring values, inference for learning bidders.
  • Week 8: Online Allocation
    • Topics: online allocation, backwards induction, “the eBay problem” (prophet inequalities), secretary problem, ski renter.
  • Week 9: Matching Markets
    • Topics: offline matching, matching algorithms, externality pricing mechanism, duality, online matching, greedy online matching.