2023WI_COMP_SCI_332-0_SEC1 Online Markets

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 marketplaces 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.  Lectures will develop intuition for these topics through mathematical analysis.  Student work will be a mix of exercises, quizzes, short projects, and peer reviews.

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

Instructor: Jason Hartline
Office hours: W 11-12pm in Mudd 3015
Lectures: MW 3:30-4:50pm in Frances Searle 2-407.
Discussion: Piazza.

Teaching Assistants: Anant Shah
Office hours:

• M 10-11am in Tech LG62,
• F 12-1pm in Mudd 3532.

Grading: 40% projects, 20% peer review, 10% exercises, 10% quizzes, 20% final.

Project Policy: 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.  Project report guidelines.

Peer Review: Projects will be peer reviewed.  Peer review is part of the dialogue we have about course content, and serves to provide students with quick feedback about their projects.  Peer review logistics.  Peer review rubric and scoring guidelines.

Quiz Policy: Quizzes will be short and intended to assess understanding of facts and concepts in the course.  Questions will primarily be true/false, multiple choice, or numeric answers.  Quizzes are open notes, but to be done individually and without other Internet resources.  See full details on logistics and policies of quizzes.

Lecture Livestreams: Students are expected to attend the in-person classes.  However, to promote a healthy learning atmosphere, all lectures will be livestreamed to Panopto.  Students feeling like their attendance might compromise the health of other students should attend from the livestream.   

Lecture Recordings: Lectures will be recorded and available to students in the class on Panopto.  Per the university policy:  Unauthorized student recording of classroom or other academic activities (including advising sessions or office hours) is prohibited. Unauthorized recording is unethical and may also be a violation of University policy and state law. Students requesting the use of assistive technology as an accommodation should contact AccessibleNU. Unauthorized use of classroom recordings — including distributing or posting them — is also prohibited.  Under the University’s Copyright Policy, faculty own the copyright to instructional materials — including those resources created specifically for the purposes of instruction, such as syllabi, lectures and lecture notes, and presentations.  Students cannot copy, reproduce, display or distribute these materials. Students who engage in unauthorized recording, unauthorized use of a recording or unauthorized distribution of instructional materials will be referred to the appropriate University office for follow-up.

Accessibility and Accommodations: Northwestern University is committed to providing the most accessible learning environment as possible for students with disabilities. Should you anticipate or experience disability-related barriers in the academic setting, please contact AccessibleNU to move forward with the university’s established accommodation process (e: accessiblenu@northwestern.edu; p: 847-467-5530). If you already have established accommodations with AccessibleNU, please let me know as soon as possible, preferably within the first two weeks of the term, so we can work together to implement your disability accommodations. Disability information, including academic accommodations as part of a student’s educational record, is confidential under FERPA regulations.

Tentative Schedule:

• Week 1: Allocating a Resource
  • Lecture 0: ride sharing, first-price auction, ascending-price auction, second-price auction. [notes] [slides]
  • Lecture 1: empirical algorithms analysis, random variables, Monte Carlo simulation. [notes] [slides]
• Week 2: Game Theory
  • Lecture 2: Bimatrix Games, Nash Equilibrium, Dominant Strategy Equilibrium [notes] [slides]
  • Lecture 3: Dominant-strategy, Nash, Bayes-Nash equilibria; first-price, second-price auctions, revisited [notes] [slides]
  • Project 1: Bid Analysis
• Week 3: Online Learning
  • Martin Luther King Jr. Day
  • Lecture 4: online learning, exponential weights. [notes] [slides]
• Week 4: Learning and Game Theory
  • Lecture 5: Multi-armed Bandit Learning [notes] [slides]
  • Lecture 6: learning in games, coarse correlated equilibria [notes] [slides]
  • Lecture 7: Learning to bid, discretization, full feedback, partial feedback [notes]
  • Project 2: Online Learning
• Week 5: Welfare and Revenue
  
  • Lecture 8: Welfare analysis in equilibrium, competitive efficiency, individual efficiency. [notes] [slides]
  • Quiz Weeks 1-4 (take home)
  • Lecture 9: Randomized welfare analysis, second-price with reserve [notes] [slides]
• Week 6: Optimal Auctions
  • Lecture 10: pricing revenue, virtual values, optimal reserves [notes] [slides]
  • Lecture 11: revelation principle, optimal auctions, virtual welfare maximization [notes] [slides]
  • Project 3: Learning in Games
• Week 7: Learning Auctions and Econometrics
  • Lecture 12: optimal auctions (review), learning to price, learning to auction [notes] [slides]
  • Lecture 13: inferring values, inference for learning bidders. [notes] [slides]
• Week 8: Online Allocation
  • Lecture 14: online allocation, backwards induction, "the eBay problem" (prophet inequalities) [notes] [slides]
  • Quiz Weeks 5-7 (take home)
  • Lecture 15: secretary problem, ski renter. [notes] [slides]
  • Project 4: Online Revenue Maximization
• Week 9: Matching Markets
  
  • Lecture 16: Offline matching, matching algorithms, market clearing, duality [notes] [slides]
  • Lecture 17: Matching mechanisms, duality (continued), externality pricing. [notes] [slides]
• Week 10: Online Matching and Applications
  • Lecture 18: online matching, greedy online matching. [notes] [slides]
  • Lecture 19: Online markets in practice (Guest lectures by Onno Zoeter from Booking.com and Brendan Lucier from Microsoft Research)
  • Project 5: Inference for Learning Agents
• Week 11: Final Exam, Friday, 03/17/2023: 3PM-5PM. (Cumulative, Review materials [notes])