CS 886: Game-theoretic methods for computer science
Time and Location:
Mondays and Wednesdays 10:00-11:30
DC 3313
Office hours on Mondays 1:30-2:30 in DC 2518
 
Description:
In settings ranging from computer networks to electronic markets, computer scientists are observing and designing systems consisting of multiple self-interested parties (or agents).  Game theory and mechanism design provide us with a set of tools and techniques for analyzing agent behavior in these systems, as well as informing us how to design systems so that agents behave in the way we would like them to.
 
This course will provide an introduction to key game theory and mechanism design concepts.  We will study how these ideas are being used in computer science, as well as computational issues in game theory and mechanism design.  Examples and applications from AI, Theory, and Systems will be presented.
 
Course Topics (tentative list):
Specific topics include normal-form games, extensive-form games, Bayesian games, repeated games, equilibrium concepts, computation of game-theoretic solution concepts, social-choice and voting, positive and negative results for mechanism design, single-item auctions, combinatorial auctions, computational issues in mechanism design.
 
Prerequisites:
This course draws on a wide set of ideas from both CS and economics. While there are no formal prerequisites, students should be comfortable constructing and following formal mathematical proofs. It is assumed that students will NOT be familiar with game theory and mechanism design.
 
Organization:
The first part of the course will consist of lectures on game theory and mechanism design.  The second part of the course will be run as a seminar with students reading and presenting research papers in class.
 
Grading (subject to change):
Paper presentations    20%
Assignments                10%
Class Participation      20%
Term-long Project       50%
 
Class Participation:
Class participation is an important component of this course.  Before each class all students must read the paper being presented and submit comments and questions.  Things to think about include
 
  1. • What is the main contribution of the paper?
  2. • Is it important? Why?
  3. • What is the main insight in the paper?
  4. • What assumptions were made?
  5. • What applications might arise from the paper?
  6. • How can the results be extended?
  7. • What was unclear to you?
 
Project:
The final project allows students to explore material not covered in class, and share that material with other students.  The topic of the project can be a literature survey, a compare and contrast study of two or three influential papers, or a development of your own research ideas.  The project will involve several steps; project proposal due early in the semester, a project presentation, and the final project report.
 
 
3,3
Cooperate
5,0
0,5
1,1
Cooperate
Defect
Defect