Computational Game Theory: 20172018
Lecturer 

Degrees 
Schedule C1 (CS&P) — Computer Science and Philosophy Schedule C1 — Computer Science Schedule C1 — Mathematics and Computer Science 
Term 
Michaelmas Term 2017 (20 lectures) 
Overview
Game theory is the mathematical theory of strategic interactions between selfinterested 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 selfinterested, 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 noncooperative 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 researchlevel topic in computational game theory.
NB. There is no past paper for the 201617 Computational Game Theory course. Whilst you may refer to the 201516 MFoCS (MSc in Mathematics and Foundations of Computer Science) Computational Game Theory exam in preparation (please see: https://www.cs.ox.ac.uk/teaching/internal/papers/MSCinCS/2016/), please note that the content and scope of the 201617 version will be different. In particular, the exam will not be fully essaybased.
Learning outcomes
Upon completing this course, a student will: 1. understand the key concepts of preferences, utility, and decisionmaking 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 noncooperative 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 researchlevel 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.
•
Decisionmaking 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., CPNETS).
• Dichotomous preferences and goals. Representations
for specifying goals (e.g., weighted formula representations for combinatorial domains); expressiveness and computational
issues.
2. Strategic Form NonCooperative 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 LemkeHowson 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 HawkDove game;
evolutionary game theory; evolutionarily stable strategies.
4. Extensive Form NonCooperative Games:
• Extensive form games of perfect information; Zermelo’s algorithm and
backward induction; Pcompleteness of Zermelo’s algorithm; subgame perfect equilibrium.
• Winlose games; Zermelo’s theorem.
•
Compact representations for extensive form games; the PEEK games and EXPTIMEcompleteness 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 (GibbardSatterthwaite
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:
• 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: 4http://books.osborne.economics.utoronto.ca
• Y. Shoham and
K. LeytonBrown. 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.