Lecturer	Elias Koutsoupias
Degrees	Schedule C1 (CS&P) — Computer Science and Philosophy Schedule C1 — Computer Science Schedule C1 — Mathematics and Computer Science Hilary Term — MSc in Advanced Computer Science
Term	Hilary Term 2027  (20 lectures)

Overview

This course provides an introduction to Algorithmic Game Theory (AGT), a field at the intersection of computer science, economics, and mathematics. It focuses on the computational aspects of strategic interactions among rational agents, exploring how algorithmic considerations influence the design and analysis of mechanisms and systems in decentralised environments. Key topics include quantifying the inefficiency of equilibria (Price of Anarchy), designing robust incentive mechanisms (Mechanism Design), understanding the computational complexity of game-theoretic concepts, exploring fundamental solution concepts like stable matching, designing optimal auctions, analysing profit inequalities in various settings, and understanding learning dynamics and no-regret algorithms in games.

Learning outcomes

By the end of this course, students should be able to:

1. Formulate real-world problems as game-theoretic models and analyze their strategic properties.
2. Calculate and interpret the Price of Anarchy and Price of Stability for various classes of games.
3. Design and prove properties of incentive-compatible mechanisms, including Vickrey-Clarke-Groves (VCG) mechanisms and their variants, and stable matching algorithms.
4. Design and analyze optimal auctions for various selling environments.
5. Apply approximation algorithms and other computational techniques to address hard algorithmic game theory problems, including those involving profit inequalities.
6. Understand and analyze learning dynamics in games, particularly no-regret algorithms, and their relation to equilibrium concepts.

Prerequisites

Strong mathematical maturity is essential, including:
- Basic knowledge of game theory concepts (e.g., from an undergraduate computational game theory course or equivalent)
- Solid background in algorithms
- Familiarity with probability theory, linear algebra, and discrete mathematics

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.