CS409 15 CATS (7.5 ECTS) Term 1

Availability

Option - MEng CS and DM, MSc Computer Science, MSc Data Analytics

Prerequisites

CS260 Algorithms

Academic Aims

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.

Learning Outcomes

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.

Content

• 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 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.

Books

• Osborne and Rubinstein, A Course in Game Theory
• Roughgarden, Selfish Routing and the Price of Anarchy
• Nisan, Roughgarden, Tardos and Vazirani (eds), Algorithmic Game Theory
• Selected research papers.

Assessment

Three-hour examination (80%), coursework (20%)

Teaching

30 lectures