COMS 6998-3: Introduction to Algorithmic Game Theory

Instructors: Sergei Vassilvitskii, Sébastien Lahaie (both at Yahoo! Research)
E-mail: { sergei, lahaies } at

Teaching Assistants

Time/Location: 4:10-6:00PM on Mondays in 233 Mudd. 253 Engineering Terrace

Course description: Algorithmic game theory is an emerging area at the intersection of computer science and microeconomics. Motivated by the rise of the internet and electronic commerce, computer scientists have turned to models where problem inputs are held by distributed, selfish agents (as opposed to the classical model where the inputs are chosen adversarially). This new perspective leads to a host of fascinating questions on the interplay between computation and incentives.

This course provides a broad survey of topics in algorithmic game theory, such as: algorithmic mechanism design; combinatorial and competitive auctions; congestion and potential games; computation of equilibria; network games and selfish routing; and sponsored search. No prior knowledge of game theory is necessary; the most important prerequisite is mathematical maturity.

Prerequisites: Algorithms ( COMS 4231 ), Discrete Math ( COMS 3203 ).

Optional Text: Algorithmic Game Theory. Nisan, Roughgarden, Tardos, Vazirani. Cambridge University Press, 2007.
*** The book is available online for free! Thanks to the progressive-minded publisher, you can read the entire book by clicking here (username=agt1user, password=camb2agt).

Course requirements: Two problem sets (25% each); a 10-15 page report summarizing 1-3 research papers (40%); participation (10%). Pass/Fail students, select either the problem sets or the project.

Late Policy: You can hand in one of the problem sets 3 days late (Thursday at 5pm). No other late homeworks will be accepted. You cannot hand in the project late.

Homework policy: You are encouraged to discuss the course material and the homework problems with each other in small groups (2-3 people), but you must list all discussion partners on your problem set. Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem.  In addition, each person must write up their solutions independently;  you may not look at another student's written solutions. You may consult outside materials, but all materials used must be appropriately acknowledged, and you must always write up your solutions in your own words. Violation of this policy will result in a penalty to be assessed at the instructor's discretion. This may include receiving a zero grade for the assignment in question AND a failing grade for the whole course, even for the first infraction.

Schedule and references: