To familiarise students with formal methods of strategic interaction, as studied in game theory. The focus of the module is on algorithmic and computational complexity aspects of game-theoretic models. One of the aims will be to give a flavour of current research and most recent advances in the field of algorithmic game theory.
On successful completion of the module students should be able to:
- Understand the fundamental concepts of non-co-operative and co-operative game theory, in particular standard game models and solution concepts.
- Understand a variety of advanced algorithmic techniques and complexity results for computing game-theoretic solution concepts (equilibria).
- Apply solution concepts, algorithms, and complexity results to unseen games that are variants of known examples.
- Understand the state of the art in some areas of algorithmic research, including new developments and open problems.
- Game models: Strategic form, extensive form, games of incomplete information (eg auctions), succinct representations, market equilibria, network games, co-operative games.
- Solution concepts: Nash equilibria, subgame perfection, correlated equilibria, Bayesian equilibria, core and Shapley value.
- Quality of equilibria: Price of anarchy, price of stability, fairness.
- Finding equilibria: Linear programming algorithms, Lemke-Howson algorithm, finding all equilibria.
- Complexity of results: Efficient algorithms, NP-completeness of decision problems relating to set of equilibria, PPAD-completeness.
Some parts of the module will be research-led, so some topics will vary from year to year.