Computational Issues in Game Theory

FINAL PROJECT IS DUE ON NOVEMBER 1, 2008

The project should be submitted by email to mfeldman@huji.ac.il (myself) and to ilan.nehama@mail.huji.ac.il (Ilan Nehama).

Course description: Recent years have seen a flurry of research activity on problems lying at the border of computer science, game theory and microeconomics. This trend is, in part, due to the emergence of the Internet, which is composed of distributed computer networks managed by multiple administrative authorities and shared by users with competing interests. This course reflects the state of the art research in the boundaries of these disciplines, and will cover a broad range of topics, including auction design and mechanism design, combinatorial auctions, computational complexity of equilibria, network games, potential and congestion games, price of anarchy, price of stability, digital goods, and more.

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

TA of the course: Ilan Nehama, email: ilan.nehama@mail.huji.ac.il

Course Requirements

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.
Answer all problem sets that will be assigned during the semester (30% of final grade). Problem sets should be made and submitted INDIVIDUALLY. It is highly recommended that you do them on your own. If you happen to discuss some problems with a friend, please note which problem you discussed and with whom.
Submit a final project (70% of final grade).

Final project's instructions

1. Student group size: 1-3 students. 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. Assigned: June 3, 2008. Due: June 21, 2008. Solution.

Problem set 2. Assigned: July 28, 2008. Due: August 11, 2008. (note: submission of problem set 2 is not mandatory, but I highly recommend solving it).

Classes

Date	Topics	Slides	Reading
May 11, 2008	Intro to game theory (dominant strategies, Nash equilibrium, …)
May 18, 2008	Zero-sum games, mixed strategies, Nash's theorem,	slides / for print	AGT, chapter 1
May 25, 2008	Potential games	slides / for print	AGT, chapter 17
June 1, 2008	Potential games (cont'd)		AGT, chapter 19
June 8, 2008	Shavuot evening (no class)
June 15, 2008	Load balancing, strong equilibrium, total search problems	slides / for print total search / for print	AGT, chapter 20 AGT, chapter 2

June 22, 2008	Load balancing on related machines, routing atomic flow	Slides / for print	AGT, chapter 18 AGT, chapter 20
June 29, 2008	Intro to social choice theory	No slides	AGT, chapter 9
July 6, 2008	Arrow impossibility theorem	No slides	AGT, chapter 9
July 13, 2008	Gibbard-Satterthwaite theorem, mechanism design, Intro to VCG mechanisms	No slides	AGT, chapter 9
July 20, 2008	VCG mechanisms, Combinatorial Auctions, Single-minded bidders	No slides	AGT, chapter 11
July 27, 2008	LOS mechanism for Single-minded bidders, LPR formulation	No slides	AGT, chapter 11
August 3, 2008	Combinatorial auctions approximation		"Approximation algorithms for combinatorial auctions with complement free bidders", Dobzinski, Nisan and Schapira, STOC'05.