Computational Game Theory:  2023-2024

Overview

Game theory is the mathematical theory of strategic interactions between self-interested agents. Game theory provides a range of models for representing strategic interactions, and associated with these, a family of solution concepts, which attempt to characterise the rational outcomes of games. Game theory is important to computer science for several reasons: First, interaction is a fundamental topic in computer science, and if it is assumed that system components are self-interested, then the models and solution concepts of game theory seems to provide an appropriate framework with which to model such systems. Second, the problem of computing with the solution concepts proposed by game theory raises important challenges for computer science, which test the boundaries of current algorithmic techniques. This course aims to introduce the key concepts of game theory for a computer science audience, emphasising both the applicability of game theoretic concepts in a computational setting, and the role of computation in game theoretic problems. The course assumes no prior knowledge of game theory. 

Learning outcomes

1. understand the key concepts of preferences, utility, and decision-making under certainty and uncertainty, and the key computational issues in 1representing and manipulating representations of preferences and utility; 2. understand and be able to apply the key models and solution concepts of non-cooperative game theory, including both strategic form and extensive form games, and the key computational issues that arise when applying these models; 3. understand the principles of congestion games and their relevance 4. understand the concept of the price of anarchy for analysing distributed systems 5. understand a contemporary research-level topic at the intersection between game theory and computer science.

Syllabus

1. Introduction
2. Preferences, Utility, and Goals
3. Normal Form Games
4. Mixed Strategies and Nash's Theorem
5. Extensive Form Games
6. Iterated Games
7. Evolutionary Games
8. Zero Sum Games
9. Compactly specified extensive form games and their complexity
10. Congestion games
11. The Price of Anarchy
12. Contemporary research topic

Reading list

Recommended Reading: Game Theory

• R. D. Luce and H. Raiffa, Games and Decisions, Wiley, 1958   (Even when somewhat dated, excellent discussions of the main concepts of game theory)
• M. Machler, E. Solan, S. Zamir, Game Theory, Cambridge U.P., 2013  (Excellent contemporary text on game theory that combines rigour with readibility)
• M. J. Osborne and A. Rubinstein, A Course in Game Theory, 1994  (Mathematically rigorous text. Available online: https://books.osborne.economics.utoronto.ca/)
• M. J. Osborne, An Introduction to Game Theory, Oxford U.P., 2004  (A somewhat lighter companion to Osborne and Rubinstein’s ‘A Course in Game Theory’)
• R. Y. Aumann, ‘Game Theory’, in The New Palgrave Dictionary of Economics, 2nd edition, Macmillan, 2008  (Short historical overview, with some valuable philosophical reflections on game theory and a light bias towards cooperative game theory) available online:https://link.springer.com/content/pdf/10.1057/978-1-349-95121-5_942-2.pdf)

Recommended Reading: GT and Computer Science

• Y. Shoham and K. Leyton-Brown, Multiagent Systems, Cambridge UP, 200 (A rigorous introduction to multi-agent systems as seen from a game-theoretic perspective.) available online http://www.masfoundations.org/mas.pdf)
• G. Chalkiadakis, E. Elkind, and M Wooldridge, Computational Aspects of Cooperative Game Theory Morgan-Claypool, 2011. (Studies cooperative game theory from the point of view of computer science.)
• Anna R. Karlin and Yuval Peres (eds), Game Theory, Alive, AMS, 2017 (State-of-the-art and rigorous textbook in the field)

Feedback

Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.

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.