Title: Introduction to Game Theory
Speaker: Michael Wooldridge (University of Oxford)
When: Monday to Friday, February 27 to March 3, 2023, 14:30h
Where: FCUL, rooms C1.3.23, C1.3.20, C1.3.23, C1.3.23, C1.3.33A
(Coffee break included)
Introduction
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 characterize 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 the game theory seem 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, emphasizing both the applicability of game theoretic concepts in a computational setting and the role of computation in game theoretic problems.
Objectives
The aims of this module 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.
Contents
Upon completing this module, a student will:
1. understand the key concepts of preferences, utility, and decision-making under certainty and uncertainty, and the key computational issues in representing 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;
Prerequisites
The course assumes no prior knowledge of game theory. Mathematical and computer science ability is assumed at the level of a second-year undergraduate.
Outline 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 maximization.
· Paradoxes of expected utility maximization; 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; c-Nash equilibrium.
· Computing mixed strategy Nash equilibria.
3. 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.
4. Iterated & Evolutionary Games:
· Finitely repeated games and backward induction.
· Infinitely repeated games; measuring utility over infinite plays; modeling 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.
Recommended Reading
· Michael Maschler, Eilon Solan, Shmuel Zamir. Game Theory, Cambridge UP, 2013. The best contemporary overview of game theory.
· Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. MIT Press, 1994. An excellent introduction to game theory, freely available from: http://books.osborne.economics.utoronto.ca
· Y. Shoham and K. Leyton-Brown. Multiagent Systems. Cambridge UP, 2009. Freely available from: http://www.masfoundations.org/
· G. Chalkiadakis, E. Elkind, and M. Wooldridge. Computational Aspects of Cooperative Game Theory. Morgan & Claypool, 2011. The book for cooperative games.