Office: 4130
Upson
657
phone: 255-0984 255-4195
email: eva at cs.cornell.edu thanh at cs.cornell.edu
Office Hours: Tuesdays 3-4. Wednesdays 5-6
You can also send us email to make an appointment..
Office hours for the final weeks
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.
Book
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), 2007For 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.
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.
There are many similar course offered at other schools too: Game Theory . net offers a wide range of game theory courses.