Algorithmic Game Theory

Computer Science 684
Fall 2008

Instructor: Éva Tardos                 TA: Thành Nguyen

Office:         4130 Upson                                                           657 Rhodes Hall      

phone:         255-0984                                                               255-4195

email:           eva at                                                thanh at

Office Hours:  Tuesdays 3-4.                                                 Wednesdays 5-6

                            You can also send us email to make an appointment..

Office hours for the final weeks

Friday May 2:                3:30-4:30pm                          Eva in 4130 Upson
Monday, May 5.               4-5pm                                Thanh in 657 Rhodes
Tuesday, May 6                 3-4pm                                  Eva 4130 Upson
Wednesday, May 7.           4-5pm                                Thanh in 657 Rhodes
Thursday, May 8                 3-4pm                                  Eva 4130 Upson
Friday, May 9.                      4-5pm                                Thanh in 657 Rhodes
Monday, May 12                 3-4pm                                  Eva 4130 Upson
Tuesday, May 13.                 4-5pm                                Thanh in 657 Rhodes
Wednesday, May 14              4-5pm                                  Eva 4130 Upson
Thursday, May 15                 1-2pm                                  Eva 4130 Upson



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. 


We will use the book

and supplement it with additional papers. The book is in reserve in the engineering library, and many chapters. See table of contents, as well as many chapters are available online.


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

We may also consider a subset of the Part IV chapters depending on time available and the interest of participants.


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 

Problem set 1 was due on Thursday February 21st. It is now graded, and solutions are available on  CMS.

Problem Set 2 was due on Thursday March 13th. It is now graded, and solutions are available on  CMS.

Project Proposal was due Thursday March 27th. 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. Project group may contain 2-3 students.

There are many different types of projects possible. You can consider a game motivated by some computer science and/or network problem, 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. Projects may be theoretical or experimental in nature.
Alternatively, your project may choose to understand, explain and possibly extend 2-3 papers from the literature. There are many references in the book for interesting related papers to read. For such a proposal, you should make sure that you understand the papers well, and can explain compare the results, and techniques of different papers, explain their advantages and disadvantages.

Problem Set 3 was due on Tuesday April 15th. Problems 2 and 4 updated on April 2

The final project will be due Thursday May 1st

The class final can be taken any time after May 1st. Final can be picked up from Eva or Than (stop by or send us email to ask) .You will have 3 days to finish the final, starting when you picked it up.

Topics week by week, references, etc.

Igal Milchtaich: Congestion Games with Player-Specific Payoff Functions,  Games and Economic Behavior 13 (1996), 111–124.

Nir Andelman, Michal Feldman and Yishay Mansour
Strong Price of Anarchy
Seventeenth ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007

For proof of Lemma 4.1 see Appendix B of

S. Albers, S. Eilts, E. Even-Dar, Y. Mansour and L. Roditty.
On Nash Equilibria for a Network Creation Game.
Seventeenth ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006

Amir Epstein, Michal Feldman and Yishay Mansour
Strong Equilibrium in Cost-Sharing Connection Game
In Proceedings of the 8th ACM Conference on Electronic Commerce (EC'07)

Vincent Conitzer and Tuomas Sandholm. New Complexity Results about Nash Equilibria. To appear in Games and Economic Behavior.

Course work

There will be 3 homework sets during the semester, a final, and a final project. You may work in pairs on homeworks and on the project, and hand in a shared homework. The final is a non-cooperative version of the homework. Grades and solutions to the homeworks will be kept in CMS.

For the class project students can propose independent projects, or read, critically evaluate and try to extend or modify some 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 project topic, or 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, your attempts to extend/modify the solution, and intuitive explanation and proof of why some of the results are true, and why it does or does not extend.

Similar Courses

There are many similar course offered at other schools too: Game Theory . net offers a wide range of game theory courses.