Algorithmic Game Theory

Computer Science 684
Spring 2004

Instructor: Éva Tardos

5153 Upson
255-0984
eva at cs.cornell.edu

Time: MWF 11:15-12:05

Place: Phillips 219.

Office Hours: 

Mondays 10-11 and Thursdays 2:30-3:30, or by appointment.

Office hour Monday 17: 2-3pm.

TA:  Mark Sandler

492 Rhodes Hall
254-8833
sandler at cs.cornell.edu

Office Hours: 

Fridays 2-3, or by appointment.

Mark will have additional office hours during the regular class times.

Final Project due Wednesday, May 19th

 Submit a brief proposal for your final project before spring break. The project proposal is a few paragraph long explanation on what you are hoping to accomplish. The goal of asking for the proposals is to get each group started on thinking about the projects, and also to allow early feedback on the plans. You can work on this project in groups of at most 3.

There are many different types of projects possible. You can consider a game, and propose to work on understanding the algorithmic issues associated with this game, such as how to find an equilibria, are there many equilibria, do natural plays find such equilibria, what are the quality of the worst or best equilibria, etc. I think the most interesting projects would model some phenomena in computer science as a game, and analyze a simplified version. Projects may be theoretical or experimental in nature. Alternatively, your project may be an extended survey of the literature in a sub-area. If you choose to do a survey, you should make sure that you understand the papers well, and can compare the results, and techniques of different papers, explain their advantages and disadvantages. 

 

Handouts

Overview

Algorithmic Game Theory combines algorithmic thinking with game-theoretic, or, more generally, economic concepts. The course will focus on problems arising from, and motivated by, the Internet and other decentralized computer networks. The most defining characteristic of the Internet is that it was not designed by a single central entity, but emerged from the complex interaction of many economic agents, such as network operators, service providers, designers, users, etc., in varying degrees of collaboration and competition. The course will focus on some of the many questions at the interface between algorithms and game theory that arise from this point of view. 

Topics

Topics include some of the following (subject to change): 

Topics week by week, lecture notes, references, etc.

Notes for January 26- February 6 on Introduction to games, Nash equilibria, load balancing game, potential games, a routing game, non-atomic games, and convex optimization.

Week of January 26-30:

Week of February 2-6: 

Week of February 9-13: 

Week of February 16-20: 

Week of February 23-27 (Price of anarchy on randomized load balancing games):

Week of March 1-5 (Markets, and market equilibria)

Week of March 8-12: guest lectures by

Week of March 15-19 Bandwidth sharing:  mechanisms and the price of anarchy.

Week of March 29-April 2: Fair bandwidth sharing  

Week of April 5-9: We continue discussing the fair bandwidth sharing game, and start talking about cross monotone cost-sharing.

Week of April 12-16: We define truthfulness, and discuss the VCG mechanism

Week of April 19-23: More on truthful mechanisms and impossibility results

Week of April 26-31: More on impossibility and Bayesian games

Week of May 3-7: Three recent results


Pre-requisites

The course pre-requisites include background in algorithms and graphs at the level of CS 482. No prior knowledge of game theory or economics will be assumed.

Course work

There will be 3-4 homework sets during the semester, and a final project. 

You may discuss the homework problems with other members of the class, but you must write up the assignment separately and list the names of the people with whom you discussed the assignment. 

There are many different types of projects possible both experimental, theoretical, or an extended survey of literature in a sub-area. You can work on the final project in groups of up to three people. The first step in the project will be a short `proposal'.

Book

There is no textbook for the course, as it covers recent research. The following book is a very nice introduction to game theory. (But it is not required for the course.)

Similar Courses

By Christos Papadimitiou, Noam Nisan, Mike Kearns, Eli Upfal, Eric Friedman, and Joan Feigenbaum. In addition,  Game Theory . net offers a wide range of game theory courses.