Algorithmic Game Theory, April 2024 - July 2024

by Uri Feige


Useful books:
Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani (Editors). Algorithmic Game Theory. Cambridge University Press, 2007.
Tim Roughgarden. Twenty Lectures on Algorithmic Game Theory. Cambridge University Press, 2016.

Homework assignments need to be handed in two weeks after they are given. They make half the final grade. The teaching assistant is Yotam Gafni. yotam.gafni@gmail.com


April 9. Introduction to solution concepts in game theory.
Lecture
Homework

April 16. Computing equilibria in pure strategies.
Lecture

April 30. Computing equilibria in mixed strategies.
Lecture
Homework

May 7. Nash equilibrium and Sperner's lemma.
Lecture

May 21. Computational aspects of Nash equilibria.
Lecture
Homework

May 28. Selfish Routing and Price of Anarchy.
Lecture
Homework (posted on June 5)

June 4. Fair division.
Lecture

June 18. Fair division (indivisible goods).
Lecture
Homework

June 25. Share based fairness for arbitrary entitlements.
Lecture

July 2. Mechanism design - VCG.
Lecture
Homework

July 9. Combinatorial auctions and the configuration LP.
Lecture

July 17. Final exam/project.
Download, when you are ready to do this assignment on your own.


If you find errors in lecture notes or homework, please let me know.