Algorithmic Game Theory

Computer Science 684
Fall 2005

Instructor: Éva Tardos

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

Time: MWF 1:25-2:15

Place: Olin 245

Office Hours:  Tuesday 1-2 and Fridays 2-3. You may also send me email to make an appointment.

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): 

We may also consider a subset of the following topics depending on time available and the interest of participants.

Pre-requisites

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

Problem Sets

  

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

Course work

There will be 3 homework sets during the semester, and a final project reading and evaluating papers. In addition, students will take turns writing class notes.

Class notes are due within a week after the class at which you took notes. Here is a sample file for scribes, if you want to use Latex for you notes, but any other format that can be converted to pdf and posted on the Web is fine.

For the class project students are expected to read and evaluate 1-3 papers that were not covered in class, in an area related to the course. The first step in the project will be a short (1 page) "proposal", suggesting the papers you want to read, and an outline of your plans. The final project should contain a summary of the problem and model considered in the papers, your critical evaluation of the problem, summary of the result, and intuitive explanation and proof of why some of the results are true. You need to understand the proof well enough to be able to explain it well. The expected length of a full project is about 8-10 pages.

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. 

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.)

For the topics of selfish routing too also:

Similar Courses

There are many similar course offered at other schools too: Game Theory . net offers a wide range of game theory courses. The previous version of this course was offered in the spring of 2004.