Spring 2012
Unique Number 53265
CS 395T
Algorithmic Game Theory


Instructor Greg Plaxton (office hours TTh 5-5:30 and W 2-3, ACES 3.420; email: plaxton at cs)
Grader Muhibur Rasheed (email: muhibur at cs)
Class Time TTh 3:30-5
Class Location PAR 101

There is no required textbook for the course. The course material is drawn from a variety of different sources. One useful reference that can be downloaded for free is Algorithmic Game Theory (Cambridge University Press, 2007, edited by Nisan, Roughgarden, Tardos, and Vazirani). Other sources include: Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis by Roth and Sotomayor (Cambridge University Press, 1990); Multagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations by Shoham and Leyton-Brown (Cambridge University Press, 2009); Game Theory: Analysis of Conflict by Myerson (Harvard University Press, 1997); Auction Theory by Krishna (Academic Press, 2010); Snipers, Shills & Sharks: eBay and Human Behavior by Steiglitz (Princeton University Press, 2007).

Course Outline

Numerous internet-based applications involve agents who interact with one another to share or trade resources. Such agents are not controlled by a single entity, and may not be willing to cooperate with one another to maximize the global benefit of the system. Instead, such agents are likely to act strategically, in order to maximize their own self-interest. Game theory studies the behavior of strategic agents. Internet applications have led to a resurgence of interest in game theory, and the large scale of these applications has prompted investigation into many interesting new questions related to computational aspects of game theory. This course presents a collection of foundational results that motivate and inform much of the ongoing research in this area.

Students who have taken a graduate or upper-division undergraduate theory course should be well-prepared to take this course. See the schedule for a more detailed specification of the lecture plan.

Quizzes There will be regular quizzes in the course, approximately one per week. The quizzes are open book/notes. If you miss a quiz for any reason (legitimate or otherwise), you will receive a zero for that quiz. However, as discussed in the "Overall Raw Score" section below, the lowest third of your quiz scores will be dropped in the computation of your quiz average.
Problem Sets There will be five problem sets. You are allowed to discuss high-level approaches to the assignment problems with other members of the class, but you are not allowed to discuss or exchange detailed solutions. If you are having difficulty with the problem sets, I'll be glad to give you some hints during my office hours. See the schedule to determine when each problem set will be handed out/due.
Overall Raw Score Fifty percent of each student's overall raw score will be based on performance on the quizzes. The lowest third of a student's quiz scores will be dropped in computing the quiz average. The remaining fifty percent of the overall raw score will be based on the five problem sets, each of which is worth ten percent.
Letter Grades The overall raw score thresholds for receiving an A, A–, et cetera will be determined at the end of the course. For students taking the course on a CR-NC basis, an overall raw score of 50 or more will be sufficient to earn a CR.
Feedback Throughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course.