DATES: 27/06/22 - 01/07/22 (both included)
HOUR: 11:00 - 13:15
FORMAT: Face-to-face or ONLINE
PLACE: IIIA-CSIC, Campus UAB
REGISTRATION IS CLOSED
Why doing this course?
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.
AIMS
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.
Professor Mike Wooldridge
Mike Wooldridge is a Senior Research and a Professor of Computer Science in the Oxford University. He gained a BSc Computer Science in 1989, and a PhD in Computation in 1992. He joined the University of Oxford as a Professor of Computer Science on 1 June 2012, after 12 years as a Professor of Computer Science at the University of Liverpool; during his time at Liverpool, he was Head of Department of Computer Science (2001-05), and Head of School of Electrical Engineering, Electronics, and Computer Science (2008-11). In 2011, Michael was awarded a five-year European Research Council (ERC) Advanced Grant, which fully funds him and his group from 2012 to 2017.
Michael is a AAAI Fellow, an ECCAI Fellow, an AISB Fellow, and a BCS Fellow. In 2006, he was the recipient of the ACM Autonomous Agents Research Award. In 1997, he founded AgentLink, the EC-funded European Network of Excellence in the area of agent-based computing.
SYLLABUS
LECTURE 1: PREFERENCES, UTILITIES, 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.
- Dichotomous preferences and goals. Representations for specifying goals (e.g., weighted formula representations for combinatorial domains); expressiveness and computational issues.
LECTURE 2: NORMAL FORM GAMES
- The basic model; solution concepts: pure strategy Nash equilibrium; dominant strategies; notable games (e.g., Prisoner' 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; computing mixed strategy Nash equilibria.
- Compact representations for strategic form games; Boolean games.
LECTURE 3: EXTENSIVE FORM GAMES
- Extensive form games of perfect information; Zermelo's algorithm and backward induction; P-completeness of Zermelo's algorithm; subgame perfect equilibrium.
- Imperfect information games; information sets; solution concepts for imperfect information games; behavioural strategies; Kuhn's theorem.
LECTURE 4: ITERATED GAMES
- Finitely repeated games and backward induction.
- Infinitely repeated games; measuring utility over infinite plays; modelling strategies as finite state machines with output (Moore machines); the folk theorems.
- Iterated Boolean games.
- Axelrod's tournament; the Hawk-Dove game; evolutionary game theory; evolutionarily stable strategies.
LECTURE 5: ZERO SUM GAMES
- Maximin and minimax; the minimax theorem.
- Extensive form zero sum games and complexity classes.
REGISTRATION FEES
90,00€ Student - In person
60.00€ Student - Online
200€ - No students - In person
150€ - Non students - Online
REGISTRATION IS CLOSED
