Show The Graduate Center Menu
 
 

Algorithmic Game Theory

Course Rationale

In strategic environments, multiple agents compete and collaborate to advance their goals.
Such environments are common: advertisers bidding for space in search engines,
students submitting applications for public schools, drivers choosing which road to take,
and even hospitals participating in kidney exchange programs are just a few examples of agents engaged in strategic behavior.  In this class, we will learn how to analyze strategic environments and design algorithms for them. The focus is on results with real-world applications.

Course Description

This course covers Algorithmic Game Theory (with focus on Mechanism and Market Design). Most of the course is divided into three parts. Parts I and II deal with the design of mechanisms (algorithms) for strategic environments: part I covers mechanisms that can use money to influence agent behavior, and part II covers mechanisms that cannot. Part III deals with the analysis of strategic behavior through the lens of approximation---the "Price of Anarchy". In addition to theoretical results, a large amount of time is dedicated to real-world applications (sponsored search auctions, spectrum auctions, dorm allocation, school choice, kidney exchange, resident matching, and more).

The course is especically designed to minimize pre-requisites. No knowledge of Game Theory or Economics is required. The only pre-requisite is an introductory course in algorithms (at the level of "Analysis of Algorithms" offered at the Graduate Center). It might be possible to take an algorithms course as a co-requisite instead; if interested, contact the instructor. In addition, the prerequisite might be waived for students with general "mathematical maturity"; if interested, contact the instructor.

Topic List

  • Basics of Game Theory
  • Mechanism Design with money/auctions, including applications such as online advertising, spectrum auctions and more.
  • Matching markets, including applications such as resident matching, school choice, kidney exchange, house allocation, and more.
  • Voting mechanisms and social choice.
  • Selfish routing and the price of anarchy.
  • Additional topics/applications (time permitting): crowdsourcing, P2P networks, fair division, strategic aspects of Bitcoin, and more.

Learning Objectives

Students who successfully complete this course will be able to:

1. Model and reason about strategic environments.

2. Understand the trade-offs between optimization, assumptions on agent

behavior, and running time.

3. Develop familiarity with the tools and applications of Algorithmic Game

Theory, with emphasis on Mechanism and Market Design.

4. Understand the interplay between theory and application.

Assessment

  • Homework assignments (evaluating learning objectives 1,2,3,4) 65%
  • Final project (evaluating learning objectives 1,2,3,4) 35%