The Essentials

Time and location: Mon and Wed at 3:00-4:20, GHC 4102

Teachers: Ariel Procaccia and Alex Psomas

TA: Anson Kahng

Office hours: Anson's office hours are on Wednesdays at 4:30-5:30, in GHC 6207. To coordinate a meeting with Ariel or Alex, please send an email.

Overview

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

The course's topics include: fair division algorithms for allocating divisible and indivisible goods, and approximate notions of fairness; computational social choice, e.g., voting rules that optimize welfare, and methods for dealing with manipulation in elections; online matching algorithms (competitive analysis, not dating) and kidney exchange; the design of truthful auctions, as well as other topics in mechanism design; noncooperative games, including Nash equilibrium and correlated equilibrium, their computation, connections to learning theory, and the price of anarchy in congestion and routing games; and cryptocurrencies, with an emphasis on game-theoretic issues.

Prerequisites: The course is mainly intended for mathematically mature CS students (graduate and undergraduate). Students in other relevant fields (e.g., mathematics, economics, operations research) are also very welcome, but note that basic knowledge in algorithms, computational complexity, and probability theory is assumed.

Requirements

For the graduate version of the course (15896, 12 units), grades are based on four homework assignments (10% × 4 = 40%), participation (15%), and research project (45%). The research project should raise novel technical questions and provide some nontrivial answers.

For the undergraduate version of the course (15483, 9 units), grades are based on four homework assignments (15% × 4 = 60%), participation (15%), and final exam (25%).

Piazza

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