Algorithmic Game Theory

Computer Science 6840
Spring 2012

245 Olin, MWF 1:25-2:15 

Instructor: Éva Tardos                 TAs:  Renato Paes Leme and Vasilis Syrgkanis

Office:         4141 Upson                                                                    4139 Upson Hall and 340 Upson hall  

phone:         255-0984                                                              

email:           eva at cs.cornell.edu                                                e-mails: renatoppl and vasilis [at] cs [dot] cornell [dot] edu

 

See Piazza for office hours during the final weeks.

We also have a Piazza page. Piazza is a web-based discussion forum for communication with classmates and the course staff. Except for confidential matters, Piazza is preferred over email, as anyone can answer and everyone can benefit from the answer. The coure staff weill monitor questions and answers and endorse good answers in a timely manner. If you know the answer to a question, feel free to post a reply yourself, but please avoid giving away any hints on the homework or posting any part of a solution.

 

Overview and Prerequisites

Algorithmic Game Theory combines algorithmic thinking with game-theoretic, or, more generally, economic concepts. The course will study a range of topics at this interface. The only prerequisite to the course is mathematical thinking at the level of doing well at CS 4820.

Book

We will mainly use the books

and supplement these with additional papers. Another excellent textbook that covers several of the course's topics is Shoham and Leyton-Brown, Multiagent Systems, Cambridge, 2008. For a nice introduction to Game Theory look at Ken Binmore: Game Theory: a Very Short Introduction, Oxford University Press.

Problem Sets

Course notes

The tex version of the notes for lecture 1 for suggested format.

 

Video of all previous classes are available at www.cs.cornell.edu/videonote/Cornell

A LaTex tutorial last year can be found at http://www.cs.cornell.edu/courses/cs4820/2011sp/handouts/tutorial2.html

 


Course outline (subject to change): 

Course work

Course work consists of 4 homework sets, a final, a project, and scribe notes. You may work in pairs on homeworks and the project, 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. Extra credit will be available for solving more homework problemsthan required or by improving wikipedia pages about topics discussed in class. Grades and solutions to the homeworks will be kept in CMS.

The project should be a research-like experience (understand what is known about about a research problem, and try to advance knowledge). You can base projects on recent research papers: understanding what they are doing, and attempting to improve the model or result. Or you can base projects on your own research interests. You need to write your project result in format of a paper, expected to be 6-10 pages long (definitely no longer than 10).

Grading

Course grade is determined roughly as

Extra credit can be earned by solving all problem on the problem set, or by improving pages on wikipedia related to the course. Extra credit is very useful for getting an A+, and can also be used can to partially make up missing credit on homeworks, and the final.

 

Classes on similar topics at other universities:

ˇ         Earlier version of this course

ˇ         Algorithmic Game Theory by Christos Papadimitriou

ˇ         Algorithmic Game Theory by Tim Roughgarden

ˇ         Algorithmic Mechanism Design by Jason Hartline

ˇ         Topics in Algorithmic Game Theory by Costis Daskalakis