Computational Game Theory: 2023-2024
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 outcomesUpon completing this course, a student will:
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.
- Preferences, Utility, and Goals
- Normal Form Games
- Mixed Strategies and Nash's Theorem
- Extensive Form Games
- Iterated Games
- Evolutionary Games
- Zero Sum Games
- Compactly specified extensive form games and their complexity
- Congestion games
- The Price of Anarchy
- Contemporary research topic
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)
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
Matriculated University of Oxford students who are interested in taking this course, or others 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. Priority will be given to students studying for degrees in the Department of Computer Science.