Prof. Avrim Blum
Prof. Ariel Procaccia
Time and location: Tue and Thu at 10:30-11:50, GHC 4211
Office hours: Anytime; please send an email first.
Algorithms, Games, and Networks is a new interdisciplinary course that covers selected theoretical topics at the interface of computer science and economics.
The course's topics include: solution concepts in game theory, such as Nash equilibrium and correlated equilibrium, their computation, and connections to learning theory; the price of anarchy in routing and congestion games; computational social choice: voting rules as maximum likelihood estimators, the axiomatic approach to ranking systems and crowdsourcing, manipulation of elections and ways to circumvent it; algorithmic mechanism design, focusing on truthful approximation algorithms; market design, with an emphasis on optimization and incentives in kidney exchange; diffusion of technologies and influence maximization in social networks; and procedures for fair division, such as cake cutting algorithms.
Book: The course book is Algorithmic Game Theory, which is freely available online.
Prerequisites: The course is mainly intended for graduate students in computer science. We also welcome undergraduates and students in other relevant fields (e.g., mathematics, economics, business), but note that mathematical maturity is required, and basic knowledge in computational complexity and probability theory is assumed.
Grades are based on exercises (50%), final project (25%), lecture notes (15%), and participation (10%).
We are using the Piazza course management system; please sign up here.
A template for lecture notes is available here.