TTIC 31260 - Algorithmic Game Theory (Spring 2024)

Avrim Blum

Mon/Wed 1:30-2:50pm, TTIC Room 530

(Office hours: Fri 3:00-3:50)


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.


Homeworks


Lecture Notes and Tentative Plan

  1. 03/18: Game Theory and Equilibria: basic concepts [Readings: Ch 1.1-1.3]
  2. 03/20: Equilibria & Learning: Minimax Theorem via regret minimization [Readings: Ch 4.1-4.3]
  3. 03/25: Equilibria & Learning: Bandits, internal regret and correlated equilibrium [Readings: Ch 4.4-4.6]
  4. 03/27: Equilibria & Learning: Fast algorithms for large structured games [hwk 1 due]
  5. 04/01: Equilibria: complexity of Nash and Lemke-Howson [Readings: Ch 2.1-2.4]
  6. 04/03: Price of Anarchy: definitions, potential/congestion games [Readings: Ch 17, 19.3]
    04/08: Class CANCELLED today (feel free to attend eclipse watch party downstairs)
  7. 04/10: Price of Anarchy II: leading dynamics to good behavior [Readings: Ch 18.4.2, this paper][hwk 2 due]
  8. 04/15: Social choice: voting rules, axioms, Arrow's theorem, Gibbard-Satterthwaite [Readings: Ch 9.2]
  9. 04/17: Mechanism design 1: The Vickrey auction and VCG [Readings: Ch 9.3, 9.5]
  10. 04/22: Mechanism design 2: examples, revelation principle
  11. 04/24: Mechanism design 3: digital goods [hwk 3 due]
  12. 04/29: Mechanism design 4: combinatorial auctions [Readings: Ch 11]
  13. 05/01: Fair division 1: cake cutting criteria, objectives, and algorithms
  14. 05/06: Fair division 2: indivisible goods
    05/08: No class (TTIC board meeting) [hwk 4 due]
  15. 05/13: Matching mechanisms: Top Trading Cycles
  16. 05/15: Market equilibrium [projects due]