The Essentials

Teachers:
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.

Overview

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.

Requirements

Grades are based on exercises (50%), final project (25%), lecture notes (15%), and participation (10%).

Useful Links

We are using the Piazza course management system; please sign up here.

A template for lecture notes is available here.

Sign up for a scribe slot here, and for a project presentation slot here.