Algorithmic Game Theory

Computer Science 6840
Spring 2010

Instructor: Éva Tardos                 TAs:  Renato Paes Leme and Hu Fu

Office:         4130 Upson                                                                               4139 Upson Hall   

phone:         255-0984                                                                                   255 9296

email:           eva at cs.cornell.edu                                                e-mails: renatoppl or hufu [at] cs [dot] cornell [dot] edu

Office hour during the final weeks (starting May 4th)

starting on Wednesday, May 12th, Renato will hold office hours on Skype by appointment. Send him email to make an appointment.

                                            You can also send us 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. 

Book

We will use the book

and supplement it with additional papers. The book is in reserve in the engineering library, and thanks to our progressive-minded publisher you can read the entire book Algorithmic Game Theory (eds. Nisan, Roughgarden, Tardos, Vazirani) online by clicking here (username=agt1user, password=camb2agt)

Another excellent textbook that covers several of the course's topics is Shoham and Leyton-Brown, Multiagent Systems, Cambridge, 2008.

Problem sets

If the problem set deadline is causing problems, please let me know at least a few days ahead of the deadline.

Topics week by week, references, etc.

            (Lecture topics, references and pointers to additional papers are posted here each week.)

Course outline (subject to change): 

We may also consider a subset of the Part IV chapters 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 4820. No prior knowledge of game theory or economics will be assumed.

Course work

There will be 4 homework sets during the semester, and a final. You may work in pairs on homeworks, and hand in a shared homework. You may discuss homework questions with other students, but closely collaborate only with your partner. The final is a non-cooperative version of the homework. Grades and solutions to the homeworks will be kept in CMS.

 

Classes on similar topics at other universities:

ˇ         Earlier version of this course

ˇ         Algorithmic Aspects of Game Theory by Christos Papadimitriou

ˇ         Topics in Algorithmic Game Theory by Tim Roughgarden and Jason Hartline

ˇ         Algorithmic Mechanism Design by Jason Hartline

ˇ         Topics in Algorithmic Game Theory by Costis Daskalakis