General Information:

  • Instructor: Xi Chen CSB 503, Office hours: Wednesday 3-5 pm or by appointment
  • TA: Dimitris Paparas, Office hours: Tuesday 3-5 pm, Mudd 122A
  • Room: Engineering 253 (From Mudd, take the elevator to the second floor.)
  • Time: Thursday 4:10 pm -- 6:00 pm
  • Textbook: Algorithmic Game Theory, by Nisan, Roughgarden, Tardos and Vazirani.
    Online non-printable copy can be found here, with errata The book has also been reserved in the engineering library.
  • More references and links can be found on the Lectures and Links page.
  • Important information (e.g., due dates of assignments) can be found on the Announcement page.

Course Description:

  • In the past decade, concepts and approaches from game theory and economics have been widely used in computer science. Many of the applications are motivated by the rise of the Internet and e-commerce, due to the absence of central authority. It is not surprising that being able to understand or even predict the behavior of selfish agents is critical to the success of many Internet-based applications. In this course, we will survey topics at the interface of theoretical computer science and game theory / economics, and see
    • Why algorithmic thinking is important when game-theoretic tools are applied to computer systems
    • How algorithmic thinking interacts with some of the most classical models in game theory / economics, and
    • How theoretical computer science also provides new perspectives in some areas of game theory / economics

  • Some of the topics that will be covered in the course are:
    • Pure equilibria, price of anarchy and the potential function method
    • Zero-sum games and the Minmax theorem
    • Brouwer's fixed point theorem and Sperner's lemma
    • Existence of equilibria (theorems of Nash; and of Arrow and Debreu) and their computation
    • Algorithmic mechanism design

Prerequisites:

  • The course assumes no prior knowledge of game theory / economics.
  • Algorithm and basic computational complexity
  • Discrete math, basic probability and calculus
  • This is a theory course so you should feel comfortable reading and working with math.

Course Requirements:

  • Participate in lectures and scribe notes. Depending on the enrollment, we will have one or two students scribing notes on each lecture. The notes, which should be a clear exposition of the material covered, will be posted here before the next lecture. The template file can be found here (Template.tex and Template.pdf). Check this if you are not familiar with LaTeX. It should only take you 157 minutes at most.

  • Homework. There will be at most three sets of assignments (due dates TBA). Most of the problems are proofs of theorems to help you understand the material covered. No late assignments accepted. You are encouraged to discuss the homework problems in small groups (2-3 people), as long as the participants are listed in the homework. Even if the group solves the problem together, you must write up every step entirely by yourself and you are expected to fully understand every step of the proof. Students are expected to adhere to the Academic Honesty policy of the Computer Science Department.

  • Final project. During the course, students are expected to work on a specific research topic in groups of at most two. Each group should submit a short (less than one page) proposal by the middle of the semester (date TBA). The students are encouraged to discuss the project with the instructor as early as possible before submitting the proposal. More information will be available later. The project could be:
    • A survey of recent research papers on the topic. It is expected to explain the topic and to give a clear and thorough exposition of the recent results. It is also expected to include something original, e.g., comments on the model studied, barrier to current techniques, future research directions, etc.
    • An original research result. It could be a new theoretical result in algorithmic game theory; or an application of game-theoretic tools in your own research area.

  • Presentation. Each group needs to give a short presentation in class later in the semester (dates TBA), which should give other students a clear overview of the project.

  • Grading: Class participation (10%), homework assignments (50%), final project and presentation (40%).