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

• Homework 1. Due [add date]. Hand in using the following dropbox link.

Lecture Notes and Tentative Plan

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