Algorithms and the Internet, G22.3033-005

Instructor. Richard Cole, 430 Warren Weaver Hall, tel: 998-3119, cole at cs dot nyu dot edu.

Class time.  Wednesday, 5:00-6:50pm, room 102 Warren Weaver Hall.
Office hours.  Wednesday, 4:00-5:00pm

Course Background  The advent of the internet has led to many settings in which the standard algorithmic goal of seeking an optimal solution is no longer clearcut.  For example, in an (online) auction, rational sellers and potential buyers have conflicting goals (of maximizing revenue on the one hand, and of minimizing payment on the other, at least presumably).  Likewise, the current Internet backbone is run by a handful of companies, whose individual motivations are to minimize their handling of others traffic, which does not necessarily lead to the same routings as in a network managed by a single organization.  This type of scenario is the concern of game theory, and consequently there has been a burgeoning of interest in algorithmic game theory.
This course will study recent results in algorithmic game theory and other algorithmic topics motivated by the advent of the world wide web.

Course format  The course will consist of one or two lectures on game theory.  Subsequent classes will focus on discussing papers from the literature.  Students will be expected to present many of these papers.

Course Schedule

Background reading  Guillermo Owen, Game Theory, Academic Press.

Prerequisites  Honors Algorithms, or an A in Fundamental Algorithms, or permission of the instructor. (Richard Cole)
Last modified: Nov 12, 2003