Course on Algorithmic Game Theory

Throughout the world of modern computer networks, there are environments in which participants act strategically. Agents use shared infrastructure such as servers with the goal of minimizing their own cost rather than the overall cost of all agents. In online advertising and cloud computing, huge markets have developed, with many agents trying to maximize their own utility. In all these settings, algorithms either act as selfish agents or have to cope with such behavior. This brings about novel questions that fall outside the scope of traditional algorithmic theory. Algorithmic game theory, a research direction at the intersection of game theory and algorithm design, has emerged to provide answers.

In this course, we introduce the foundations of algorithmic game theory, centered on the fundamental questions: How can such strategic behavior be modeled mathematically? What are its consequences? And how can we design systems that function well despite it?

The first part focuses on descriptive algorithmic game theory. We introduce basic game theory and also study questions such as computational complexity of equilibria or the loss of performance due to selfish behavior. The second part is on mechanism design with money, in which we discuss questions around designing systems so that they can cope with strategic behavior, focusing on auctions and incentives. Finally, in the third part, we consider mechanism design without money, exploring fair allocations, stable matchings, and voting.

I frequently teach this course at the University of Bonn. Lecture notes and video recordings are available below.

There is a Welcome Video on YouTube and also a playlist of all videos on YouTube.

Current Set of Lectures

  1. Introduction to Congestion Games
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  2. Computing Equilibria in Congestion Games
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  3. Normal-Form Games and Mixed Nash Equlibria
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  4. Existence of Mixed Nash Equilibria
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  5. Complexity of Pure Nash Equilibria in Congestion Games
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  6. Correlated Equilibria
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  7. Minimizing External Regret
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  8. Price of Anarchy
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  9. Inefficiencies in Cost and Market Sharing Games
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  10. Introduction to Mechanism Design
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  11. Single-Parameter Mechanisms
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  12. Greedy Mechanisms for Combinatorial Auctions
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  13. VCG Mechanisms
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  14. General Combinatorial Auctions
    [Most Recent Lecture Notes]
  15. Smooth Mechanisms
    [Most Recent Lecture Notes]
  16. Bayes-Nash Equilibria
    [Most Recent Lecture Notes]
  17. Walrasian Equilibria
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  18. Posted Prices with Incomplete Information
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  19. Revenue Maximization
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  20. Revenue Maximization with Identical Distributions
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  21. Allocations without Money
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  22. Stable Matching
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  23. Cake Cutting
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  24. Voting
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]
  25. Cost Sharing
    [Most Recent Lecture Notes] [Lecture Notes for Video] [Video on YouTube]

Other Lectures