Coronavirus (Covid-19): Latest updates and information
Skip to main content Skip to navigation

CS409 Algorithmic Game Theory

Throughout the 2020-21 academic year, we will be adapting the way we teach and assess modules in line with government guidance on social distancing and other protective measures in response to Coronavirus. Teaching will vary between online and on-campus delivery through the year, and you should read the additional information linked on the right hand side of this page for details of how we anticipate this will work. The contact hours shown in the module information below are superseded by the additional information. You can find out more about the University’s overall response to Coronavirus at: https://warwick.ac.uk/coronavirus.

CS409-15 Algorithmic Game Theory

Academic year
20/21
Department
Computer Science
Level
Undergraduate Level 4
Module leader
Marcin Jurdzinski
Credit value
15
Module duration
10 weeks
Assessment
Multiple
Study location
University of Warwick main campus, Coventry
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 D3
Weighting Study time
coursework 1 5%

question sheet 1 - peer assessed

coursework 2 15%

question sheet

CS409 examination 80%

CS409 examination

~Platforms - AEP

Assessment group R
Weighting Study time
CS409 resit paper 100%

CS409 resit paper

~Platforms - AEP

Feedback on assessment

Written comments and marks.

Past exam papers for CS409

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 4 of UCSA-G402 MEng Computing Systems
  • Year 5 of UCSA-G403 MEng Computing Systems (Intercalated Year)
  • Year 1 of TCSA-G5PD Postgraduate Taught Computer Science
  • Year 1 of TCSA-G5P8 Postgraduate Taught Computer Science and Applications
  • Year 4 of UCSA-G503 Undergraduate Computer Science MEng

This module is Option list A for:

  • TCOS-F3P6 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)
  • TCOS-F3P7 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 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 3 of UMAA-G100 Undergraduate Mathematics (BSc)
  • Year 4 of UMAA-G101 Undergraduate Mathematics with Intercalated Year

This module is Option list B for:

  • Year 4 of UCSA-G402 MEng Computing Systems
  • Year 5 of UCSA-G403 MEng Computing Systems (Intercalated Year)
  • UMAA-G105 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
  • UMAA-G103 Undergraduate Mathematics (MMath)
    • Year 3 of G103 Mathematics (MMath)
    • Year 4 of G103 Mathematics (MMath)
  • 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)

Online Material

Additional Information