CS 598: AI Methods for Market Design (Spring 2024)

Lectures
Fridays, 10:20 AM - 1:20 PM at Science & Engineering Resource Center (SEC), Room 205
Instructor
Xintong Wang (Email: xintong.wang[at]rutgers.edu)
Office Hours
Fridays, 2 PM – 3PM at CoRE 319

Announcements

  • Jan 15: Welcome to CS598! You can find the course syllabus here.
  • Jan 18 [update @ 8pm]: We will have our first lecture (1/19 10:20am) on Zoom (link in Canvas) due to the winter weather advisory.
  • Jan 28: Please follow the guidelines on Canvas to indicate your paper presentation preferences by Wednesday 1/31, 23:59pm.
  • Feb 1: Please check out the paper presentation assignment and guidelines on how to read and present research papers.
  • Feb 20: Please check out HW1 and start early (due midnight, March 4, 2024). Here's a LaTeX template that you can use to type up your solutions. And here are some good introductions to LaTeX.
  • Feb 26: Please find the guidelines for class project, together with some example ideas / projects here. Feel free to drop by office hours to discuss your project ideas / proposals with me. The project proposal is due 23:59pm, March 19, 2024, but you are encouraged to submit before spring break.
  • March 23: Please sign up for a time slot here to discuss your course project with me on March 29 and for future office hours.
  • April 8: Please check out HW2 and start early (due midnight, April 22, 2024).

Course Overview

Marketplaces use algorithms and sets of rules to allocate resources among self-interested participants, who hold necessary information and act to pursue their own goals. Market failure – the designed algorithms or rules fail to achieve certain objectives – can occur when the designer fails to elicit agent preferences or accurately model how agents respond to rules and influence each other to produce outcomes. The course introduces how to integrate modern AI and machine learning techniques and economic thinking (e.g., game theory) to (i) model strategic agent behavior, (ii) identify relation between rules in the marketplace and market failures, and (iii) redesign them to achieve broader, system-wide objectives. Cases of today’s marketplaces will be discussed, such as online platforms, ride-sharing systems, financial exchanges (centralized & decentralized).

Prerequisites: This course will assume fundamental knowledge in AI and machine learning (e.g., 01:198:440/461/462, 16:198:520/530/536, or equivalent) and mathematical maturity (comfortable with linear algebra, probability, and algorithm analysis). Students are expected to read and discuss research papers. Familiarity with economic/game theory will be helpful but not required. Please contact the instructor if you have questions regarding whether your background is suitable for the course.


Course Schedule (tentative)

Date Lecture Readings Pre-class CQs /
Peer Evaluation
01/19 Introduction [slides] Economic reasoning and artificial intelligence (via Shibboleth)
Chap 1 of Algorithmic Economics by Parkes and Seuken		 Class survey
01/26 Intro to game theory [slides] Chap 2 and Chap 4 of Algorithmic Economics
(Optional) Computing the optimal strategy to commit to 		CQs for Game Theory
02/02 Eq. computation [slides] Chap 3 of Algorithmic Economics CQs for Eq. Computation
02/09 Auction design [slides] Chap 6 of Algorithmic Economics (6.7 is optional)
Putting the agent in agent-based modeling
A unified game-theoretic approach to multiagent reinforcement learning 		CQs for Auction & Eq. papers
Peer eval paper #1
Peer eval paper #2
02/16 Mechanism design [slides] Chap 7 (Sec 7.1-7.2) of Algorithmic Economics
What game are we playing? End-to-end learning in normal and extensive form games
Artificial intelligence and auction design 		CQs for MD & papers
Peer eval paper #3
Peer eval paper #4
02/23 Mechanism design II [slides] Chap 7 (Sec 7.4) of Algorithmic Economics
Learning to mitigate AI collusion on economic platforms 		CQs for MD II & papers
Peer eval paper #6
03/01 Online ad markets [slides] Chap 10 (Optional) of Algorithmic Economics
Optimal auctions through deep learning [full version][short version]
Reinforcement mechanism design: With applications to dynamic pricing in sponsored search auctions
Auction design for ROI-constrained buyers 		CQs for Ad Market & papers
Peer eval paper #5
Peer eval paper #7
Peer eval paper #8
03/08 Matching [slides] Chap 12 of Algorithmic Economics
Project discussion (if time) 		Midterm survey
03/15 Spring break
03/22 Information elicitation [slides] Chap 15 of Algorithmic Economics
Eliminating waste in cadaveric organ allocation
Optimizing long-term social welfare in recommender systems: a constrained matching approach 		CQs for Info elicitation & papers
Peer eval paper #9
Peer eval paper #10
03/29 Class project working session Eliciting thinking hierarchy without a prior CQs for paper on info elicitation
Peer eval paper #11
Sign up sheet (project advising)
04/05 Prediction markets [slides]
Crypto economics [slides] 		Chap 16 of Algorithmic Economics
Chap 21 of Algorithmic Economics
Log-time prediction markets for interval securities (Optional) 		CQs for PM and Crypto (Optional)
04/12 GT aspects in learning I [slides] Flash Boys 2.0: Frontrunning, transaction reordering, and consensus instability in decentralized exchanges
Performative prediction
Preference dynamics under personalized recommendations 		Pre-class CQs
Peer eval paper #12
Peer eval paper #13
Peer eval paper #14
04/19 GT aspects in learning II [slides] One for one, or all for all: Equilibria and optimality of collaboration in federated learning
Mechanisms that incentivize data sharing in federated learning
Project discussion (if time) 		Pre-class CQs
Peer eval paper #15
Peer eval paper #16
04/26 Project presentations

Materials and Resources

Links to papers and reading materials will be posted before each lecture, and slides will be posted after lectures. We will draw on the following books for some of the lectures:

  • A draft of Algorithmic Economics: A Design Approach, by David Parkes (Harvard) and Sven Seuken (U. Zurich). Relevant chapters of the book will be distributed on Canvas during the course.
  • Twenty Lectures on Algorithmic Game Theory by Tim Roughgarden (Columbia). The book is not available online, but it is based on lecture notes for the course on Incentives in Computer Science.

Course Requirements and Grading

The course will involve one paper presentation, 2-3 problem sets, and a class project. We will follow the grading scheme below:

  • Class participation (20%): Students are expected to read assigned chapters/papers before lecture and participate in class discussions. Based on initial understanding, students should complete simple comprehension questions / commentaries on papers before each class. Drop policy: two CQs / commentaries can be skipped.
  • Problem sets (20%): There will be 2-3 problem sets, covering concepts discussed in lectures. You can work in pairs, if you wish.
  • Paper presentation (15%): To complement lecture content, we will read and discuss a selected list of papers on recent advances. Each student (typically in a pair) should present and lead discussion on one paper. More information on paper bidding and presentation guidelines to follow.
  • Final project (45%): The goal of the project is to allow you to explore independent interests, learn more about a particular area, and practice teamwork. Projects can be done in a group of 3, and may be analyzing an existing model or proposing new ideas, and primarily theoretical or empirical. More instructions to follow, and below is the tentative project deadlines:
    • Project proposal (10%): March 8
    • Presentation (15%): April 26
    • Final report (20%): May 6

Acknowledgments

The course draws inspiration from: