Computational Issues in Game Theory

Instructor: Michal Feldman (mfeldman@huji.ac.il)

TA: Ilan Nehama (ilan_n@cs.huji.ac.il)

Course textbook: Algorithmic Game Theory, (username=agt1user, password=camb2agt). Cambridge University Press.
Editors: Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay Vazirani.

Course Requirements

1. Students are expected to read any required material (will be published before class, and include book chapters and research papers) and come prepared to every class.
2. Answer all problem sets that will be assigned during the semester (30% of final grade). It is highly recommended that you do the exercizes on your own. If you happen to discuss some problems with a friend, please write which problem you discussed and with whom.
3. Submit a final project (70% of final grade).

Final project's instructions

1. Student group size: TBD. The expectation from the project will be proportional to the number of students participating.

2. Proposal and approval: a proposal should be submitted and include:

1. List of students in the group.

2. General area and specific set of papers.

3. Type of project.

3. intermediate project progress report: explain what results you have obtained already, what (if any) difficulties you encountered, and what you plan to do to complete your project

4. Possible project types:

1. Summary of a few papers (average 2-3 papers) on a specific subject, including: research area, main research questions, main contribution and results, main proof ideas and methodology, interesting extensions or modifications to the model and possible challenges.

2. Concentrating on a specific paper, considering extensions or modification the model, and study how they impact the results.

3. Looking at a specific research (usually inspired by some paper) and trying to prove something new. (There is no need to guarantee something new, in case you fail it is sufficient to describe what where the "proof attempts" and why did they "fail".)

4. A more empirical work, trying to do an empirical evaluation of a certain game theoretic environment. You will need to specify what are the goals of the investigation, and whatever results you obtained.

Problem sets:

Problem set 1. Submit individually. Deadline: April 2.

Problem set 2. Submit individually. Deadline: May 3. (note that some of the questions are not mandatory).

Classes

Date	Topics	Slides	Reading
March 8, 2009	Introduction to game theory and to algorithmic game theory
March 15, 2009	Intro to GT (cont'd), zero-sum games, mixed strategies, Nash's theorem,	slides	AGT, chapter 1
March 22, 2009
March 29, 2009
April 19, 2009	Price of anarchy, potential games	slides	AGT, chapters 17,18,19