Computational Game Theory: 2020-2021
Organiser | |
Lecturers | |
Degrees | Schedule C1 (CS&P) — Computer Science and Philosophy Schedule C1 — Computer Science Schedule C1 — Mathematics and Computer Science |
Term | Hilary Term 2021 (20 lectures) |
Overview
The lectures for this course will be live via MS Teams, via the live lecture channel
The recordings of the lectures will be made available to view afterwards.
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. The aims of the course are threefold: 1. to introduce the key models and solution concepts of non-cooperative and cooperative game theory; 2. to introduce the issues that arise when computing with game theoretic solution concepts, and the main approaches to overcoming these issues, and to illustrate the role that computation plays in game theory; 3. to introduce a research-level topic in computational game theory.
Learning outcomes
Upon 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 and be able to apply the key models and solution concepts of cooperative game theory, including TU and NTU games; 4. understand a contemporary research-level topic at the intersection between game theory and computer science.Syllabus
1. Preferences, Utility, and Goals:
• Preference relations and their interpretation; utility as a numeric model of preference.
• Decision-making under uncertainty: preferences over lotteries; von Neumann and Morgenstern utility functions; expected utility and expected utility maximisation.
• Paradoxes of expected utility maximisation; framing effects and prospect theory.
• Compact representations for preference relations (e.g., CP-NETS).
• Dichotomous preferences and goals. Representations for specifying goals (e.g., weighted formula representations for combinatorial domains); expressiveness and computational issues.
2. Strategic Form Non-Cooperative Games:
• The basic model; solution concepts: pure strategy Nash equilibrium; dominant strategies; notable games (e.g., Prisoner’s Dilemma; Game of Chicken; Stag Hunt); coordination games and focal points; complexity of pure strategy Nash equilibrium.
• Measuring social welfare; utilitarian social welfare; egalitarian social welfare.
• Mixed strategies; Nash’s theorem; -Nash equilibrium.
• Computing mixed strategy Nash equilibria: the Lemke-Howson algorithm.
• Zero sum games; the Minimax Theorem.
• Compact representations for strategic form games; Boolean games; congestion games.
3. Iterated Games:
• Finitely repeated games and backward induction.
• Infinitely repeated games; measuing utility over infinite plays; modelling strategies as finite state machines with output (Moore machines); the folk theorems; implications of using bounded automata to model strategies.
• Iterated Boolean games.
• Axelrod’s tournament; the Hawk-Dove game; evolutionary game theory; evolutionarily stable strategies.
4. Extensive Form Non-Cooperative Games:
• Extensive form games of perfect information; Zermelo’s algorithm and backward induction; P-completeness of Zermelo’s algorithm; subgame perfect equilibrium.
• Win-lose games; Zermelo’s theorem.
• Compact representations for extensive form games; the PEEK games and EXPTIME-completeness results; the Game Description Language (GDL).
• Imperfect information games; information sets; solution concepts for imperfect information games.
• Compact representations for imperfect information games; PEEK games with incomplete information; undecidability results.
5. Cooperative Games:
• Transferable utility (TU) characteristic function games; the basic model; stability & fairness solution concepts: the core; the kernel; the Nucleolus; the cost of stability; the Shapley value; the Banzhaf index.
• Compact representations for TU games; induced subgraph representation; marginal contribution nets.
• Simple TU games; swap and trade robustness; weighted voting games; vector weighted voting games; network flow games.
• NTU games and representations for them; hedonic games.
• Coalition structure formation; exact and approximation algorithms.
6. Social Choice:
• social choice and social welfare functions;
• Condorcet’s paradox;
• desirable properties of social choice procedures (Pareto condition, independence of irrelevant alternatives);
• popular voting procedures (Borda, etc);
• Arrow’s theorem;
• strategic manipulation of voting procedures and associated impossibility results (Gibbard-Satterthwaite theorem);
• complexity of manipulation for voting protocols.
7. Research Topics:
In the final part of the course we will focus on a research topic from the contemporary literature; possible examples include:
• algorithmic mechanism design & auctions;
• selfish routing, the price of anarchy;
• security games.
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)
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.