CS409 Algorithmic Game Theory
CS409-15 Algorithmic Game Theory
Introductory description
The focus of the module is on algorithmic and computational complexity aspects of game-theoretic models.
Module aims
To familiarise students with formal methods of strategic interaction, as studied in game theory. One of the aims will be to give a flavour of current research and most recent advances in the field of algorithmic game theory.
Outline syllabus
This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.
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.
Learning outcomes
By the end of the module, students should be able to:
- Understand the fundamental concepts of non-cooperative 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.
Indicative reading list
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.
Subject specific skills
Advanced algorithmic techniques;
Transferable skills
Problem Solving;
Communication skills
Study time
| Type | Required |
|---|---|
| Lectures | 30 sessions of 1 hour (20%) |
| Seminars | 9 sessions of 1 hour (6%) |
| Private study | 111 hours (74%) |
| Total | 150 hours |
Private study description
private reading and revision
Costs
No further costs have been identified for this module.
You do not need to pass all assessment components to pass the module.
Students can register for this module without taking any assessment.
Assessment group D4
| Weighting | Study time | Eligible for self-certification | |
|---|---|---|---|
| Coursework 1 | 5% | Yes (waive) | |
|
question sheet 1 - peer assessed |
|||
| coursework 2 | 15% | Yes (extension) | |
|
question sheet |
|||
| In-person Examination | 80% | No | |
|
CS409 examination
|
|||
Assessment group R1
| Weighting | Study time | Eligible for self-certification | |
|---|---|---|---|
| In-person Examination - Resit | 100% | No | |
|
CS409 resit paper
|
|||
Feedback on assessment
Written comments and marks.
Pre-requisites
Students must have studied the material in CS260 or equivalent relevant content.
Courses
This module is Optional for:
- Year 5 of UCSA-G504 MEng Computer Science (with intercalated year)
- Year 1 of TCSA-G5PD Postgraduate Taught Computer Science
- Year 4 of UCSA-G503 Undergraduate Computer Science MEng
- Year 4 of UMAA-G105 Undergraduate Master of Mathematics (with Intercalated Year)
This module is Option list A for:
- Year 5 of UCSA-G504 MEng Computer Science (with intercalated year)
- Year 1 of RMAA-G1PG Postgraduate Research Mathematics of Systems
- Year 1 of TMAA-G1PF Postgraduate Taught Mathematics of Systems
- Year 4 of UCSA-G503 Undergraduate Computer Science MEng
- Year 4 of USTA-G304 Undergraduate Data Science (MSci)
- Year 4 of UCSA-G4G3 Undergraduate Discrete Mathematics
- Year 5 of UCSA-G4G4 Undergraduate Discrete Mathematics (with Intercalated Year)
- Year 3 of UMAA-G100 Undergraduate Mathematics (BSc)
- Year 3 of UMAA-G103 Undergraduate Mathematics (MMath)
- Year 4 of UMAA-G101 Undergraduate Mathematics with Intercalated Year
This module is Option list B for:
-
UMAA-G105 Undergraduate Master of Mathematics (with Intercalated Year)
- Year 4 of G105 Mathematics (MMath) with Intercalated Year
- Year 5 of G105 Mathematics (MMath) with Intercalated Year
-
UMAA-G103 Undergraduate Mathematics (MMath)
- Year 3 of G103 Mathematics (MMath)
- Year 4 of G103 Mathematics (MMath)
- Year 4 of UMAA-G107 Undergraduate Mathematics (MMath) with Study Abroad
-
UMAA-G106 Undergraduate Mathematics (MMath) with Study in Europe
- Year 3 of G106 Mathematics (MMath) with Study in Europe
- Year 4 of G106 Mathematics (MMath) with Study in Europe
Further Information
Term 1
15 CATS (7.5 ECTS)
Module Organisers:
Matthias Englert
Charilaos Efthymiou