The focus of the module is on algorithmic and computational complexity aspects of game-theoretic models.
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.
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.
By the end of the module, students should be able to:
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.
Advanced algorithmic techniques;
Problem Solving;
Communication skills
| 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 reading and revision
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.
| 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
|
|||
| Weighting | Study time | Eligible for self-certification | |
|---|---|---|---|
| In-person Examination - Resit | 100% | No | |
|
CS409 resit paper
|
|||
Written comments and marks.
Students must have studied the material in CS260 or equivalent relevant content.
This module is Optional for:
This module is Option list A for:
This module is Option list B for: