The Essentials

Teacher: Ariel Procaccia

Time and location: Tue and Thu at 1:30-2:50, GHC 5222

Office hours: Anytime; please send an email first.

Overview

Algorithms, Games, and Networks is an interdisciplinary course that covers selected theoretical topics at the interface of computer science and economics.

The course's topics include: computational social choice, e.g., voting rules as maximum likelihood estimators, the axiomatic approach to ranking systems and crowdsourcing, manipulation of elections and ways to circumvent it; cooperative games, focusing on solution concepts such as the core and the Shapley value, and their computation; fair division algorithms for allocating divisible and indivisible goods, and approximate notions of fairness; online matching algorithms (competitive analysis, not dating) and kidney exchange; noncooperative games, including Nash equilibrium and correlated equilibrium, their computation, connections to learning theory, Stackelberg security games, and the price of anarchy in congestion and routing games; and topics in social networks such as the diffusion of technologies and influence maximization.

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. Undergraduates and students in other relevant fields (e.g., mathematics, economics, business) are also welcome, but note that mathematical maturity is required, and basic knowledge in computational complexity and probability theory is assumed.

Requirements

Grades are based on three homeworks (15% × 3 = 45%), final project (45%), and participation (10%).

Piazza

We are using the Piazza course management system, especially for in-class polls; please sign up here.