Course description: This course covers selected theoretical topics at the interface of computer science and economics. 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: the axiomatic approach to ranking systems and crowdsourcing, manipulation; algorithmic mechanism design, focusing on truthful approximation algorithms; market design, with an emphasis on optimization and incentives; diffusion of technologies and influence maximization in social networks; and procedures for fair division, such as cake cutting algorithms. By the end of this course, students should have a basic understanding of the field and be able to critically read research papers in the area.
Prerequisites: The course is mainly intended for graduate students in computer science. This is a proof-oriented course, and basic knowledge in algorithms, computational complexity, and probability theory is assumed.
Evaluation: Grades are based on 4 homework assignments (60%), a course project (20%), and class participation (20%). Each student will be asked to help with grading one of the assignments as part of the class participation component.
Textbook: The course textbook is Algorithmic Game Theory (Nisan, Roughgarden, Tardos, Vazirani, eds.) which is freely available online. Readings listed below refer to chapters in this book unless specified otherwise.