Algorithmic game theory

Summary

We will study mathematical models of the interplay between algorithms and strategic behavior. We cover fundamental concepts from game theory and mechanism design, including Nash equilibria, the price of anarchy, auctions and market design, incentive compatibility, and online learning and dynamics.

Content

Keywords

game theory, algorithms, mechanism design, auctions, nash equilibrium

Learning Prerequisites

Recommended courses

Algorithms, Probability, Linear Algebra, Optimization

Learning Outcomes

By the end of the course, the student must be able to:

• Formulate a game-theoretic model of the interaction of strategic agents.
• Compare different equilibrium notions.
• Analyze incentives in a game-theoretic model.
• Quantify the efficiency of decentralized behavior using the concept of Price of Anarchy.
• Reason about the concept of Nash equilibrium and understand how it can be used to model strategic behavior.
• Design and analyze algorithms and mechanisms tailored for the interaction with strategic users.
• Recognize the basic limitations of standard game theoretic models.

Transversal skills

• Communicate effectively, being understood, including across different languages and cultures.
• Assess one's own level of skill acquisition, and plan their on-going learning goals.
• Demonstrate the capacity for critical thinking

Teaching methods

Classical formal teaching interlaced with practical exercices.

Expected student activities

Active participation in exercise sessions is essential.

Assessment methods

• 30% midterm exam
• 70% final exam

Supervision

Resources

Bibliography

Algorithmic Game Theory. Nisan, Roughgarden, Tardos & Vazirani (2007).

Twenty Lectures on Algorithmic Game Theory. Roughgarden (2016).

Ressources en bibliothèque

• Find the references at the Library

Moodle Link

• https://go.epfl.ch/MGT-435