Spring 2012Unique Number 53265CS 395TAlgorithmic Game Theory

InstructorGreg Plaxton (office hours TTh 5-5:30 and W 2-3, ACES 3.420; email: plaxton at cs) GraderMuhibur Rasheed (email: muhibur at cs) Class TimeTTh 3:30-5 Class LocationPAR 101 TextbookThere 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 Analysisby Roth and Sotomayor (Cambridge University Press, 1990);Multagent Systems: Algorithmic, Game-Theoretic, and Logical Foundationsby Shoham and Leyton-Brown (Cambridge University Press, 2009);Game Theory: Analysis of Conflictby Myerson (Harvard University Press, 1997);Auction Theoryby Krishna (Academic Press, 2010);Snipers, Shills & Sharks: eBay and Human Behaviorby Steiglitz (Princeton University Press, 2007).Course OutlineNumerous 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.

QuizzesThere 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 SetsThere 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 ScoreFifty 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 GradesThe 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. FeedbackThroughout the semester, please feel free to provide feedback to the instructor regarding any aspect of the course.