Introductory description
The focus of the module is on algorithmic and computational complexity aspects of gametheoretic 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, cooperative 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, LemkeHowson algorithm, finding all equilibria;
Complexity results: Efficient algorithms, NPcompleteness of decision problems relating to set of equilibria, PPADcompleteness;
Some parts of the module will be researchled, 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 noncooperative and cooperative game theory, in particular standard game models and solution concepts.
 Understand a variety of advanced algorithmic techniques and complexity results for computing gametheoretic 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 
coursework 1

5%


question sheet 1  peer assessed

coursework 2

15%


question sheet

Oncampus Examination

80%


CS409 examination
~Platforms  AEP
 Answerbook Gold (24 page)
 students may use a calculator

Assessment group R1

Weighting 
Study time 
Online Examination

100%


CS409 resit paper
~Platforms  AEP
 Online examination: No Answerbook required
 students may use a calculator

Feedback on assessment
Written comments and marks.
Past exam papers for CS409
Prerequisites
Students must have studied the material in CS260 or equivalent relevant content.
Courses
This module is Optional for:

Year 5 of
UCSAG504 MEng Computer Science (with intercalated year)

Year 4 of
UCSAG402 MEng Computing Systems

Year 5 of
UCSAG403 MEng Computing Systems (Intercalated Year)

Year 1 of
TCSAG5PD Postgraduate Taught Computer Science

Year 1 of
TCSAG5P8 Postgraduate Taught Computer Science and Applications

Year 4 of
UCSAG503 Undergraduate Computer Science MEng
This module is Option list A for:

TCOSF3P6 Complex Systems Science (Erasmus Mundus)

Year 1 of
F3P6 Complex Systems Science

Year 1 of
F3PJ Complex Systems Science (Ecole Polytechnique/Chalmers University)

Year 1 of
F3PK Complex Systems Science (Ecole Polytechnique/Gothenburg)

TCOSF3P7 Complex Systems Science (Erasmus Mundus) (University of Warwick)

Year 1 of
F3PH Complex Systems Science (Double Degree with Chalmers University)

Year 1 of
F3PG Complex Systems Science (Double Degree with Ecole Polytechnique)

Year 1 of
F3PJ Complex Systems Science (Ecole Polytechnique/Chalmers University)

Year 1 of
F3PK Complex Systems Science (Ecole Polytechnique/Gothenburg)

Year 1 of
F3P7 Complex Systems Science (University of Warwick)

Year 5 of
UCSAG504 MEng Computer Science (with intercalated year)

Year 1 of
RMAAG1PG Postgraduate Research Mathematics of Systems

Year 1 of
TMAAG1PF Postgraduate Taught Mathematics of Systems

Year 4 of
UCSAG503 Undergraduate Computer Science MEng

Year 4 of
USTAG304 Undergraduate Data Science (MSci)

Year 4 of
UCSAG4G3 Undergraduate Discrete Mathematics

Year 3 of
UMAAG100 Undergraduate Mathematics (BSc)

Year 4 of
UMAAG101 Undergraduate Mathematics with Intercalated Year
This module is Option list B for:

Year 4 of
UCSAG402 MEng Computing Systems

Year 5 of
UCSAG403 MEng Computing Systems (Intercalated Year)

UMAAG105 Undergraduate Master of Mathematics (with Intercalated Year)

Year 3 of
G105 Mathematics (MMath) with Intercalated Year

Year 5 of
G105 Mathematics (MMath) with Intercalated Year

UMAAG103 Undergraduate Mathematics (MMath)

Year 3 of
G103 Mathematics (MMath)

Year 4 of
G103 Mathematics (MMath)

UMAAG106 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