CS 683                   Advanced Design and Analysis of Algorithms

Spring 2007 Topic:   Learning, Games, and Electronic Markets


In many contemporary applications of algorithms, it is necessary to design algorithms which make better and better decisions as information is revealed to them over time. The central theme of this course will be a family of algorithms for online learning and prediction, and the applications of these algorithms to game theory and the design of electronic markets. The emphasis will be on mathematical techniques for designing, analyzing, and applying these algorithms. Topics will include algorithms for predicting from expert advice, adaptive game playing, Nash equilibrium and correlated equilibrium, evolutionary game theory, multi-armed bandit problems, Markov decision processes, optimal stopping, pricing and auction theory, universal portfolios, collaborative learning and reputation mechanisms.


Robert Kleinberg
4138 Upson
Phone: 255-9200

Time and Place

MWF 2:30-3:20
165 Olin Hall

Office Hours

Weds. 3:30-4:30
Thurs. 3:00-4:00
...or by appointment.


Familiarity with basic notions from algorithms and elementary probability theory, and competence with reading and writing mathematical proofs. If you have not taken at least one class in algorithms (at the level of CS 482) and at least one class in probability (at the level of Math 471) you should seek permission from the instructor.


  • Useful readings for week 8: Course Outline

    Suggested Reading
    There is no required textbook for the class, but there are two recommended texts:

    Both of these are on reserve in the Engineering Library. The content of the course has a greater amount of overlap with the first book, but we will also cover a few selected topics from the second.