THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2022/2023

Timetable information in the Course Catalogue may be subject to change.

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

Postgraduate Course: Algorithmic Game Theory and its Applications (INFR11020)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Credit level (Normal year taken)SCQF Level 11 (Year 4 Undergraduate) AvailabilityAvailable to all students
SCQF Credits10 ECTS Credits5
SummaryGame theory is the formal study of interaction between "self-interested" (or "goal-oriented") "systems" (or "agents" or "decision makers" or "players"), & strategic scenarios that arise in such settings. It began life in Economics in the 1940's with the work of von Neumann & Morgenstern, but has since been applied to an extraordinary range of subjects, including political science, evolutionary biology & even to inspection regimes for arms control.

Game theory has for years also played an important, if less recognized, role in several branches of computer science. Applications within computer science include the use of games in automated verification & model checking to model computing systems in an unknown and possibly adverse environment. In AI games are applied to the analysis of multi-agent systems. Recently, with the advent of the internet and e-commerce, many game theoretic questions in the interplay between economics & computing have received extensive attention. These include electronic auctions, & more generally mechanism design questions (inverse game theory) related to finding incentive structures for cooperation between independent entities on the internet.

Wherever game theory plays a quantitative role, algorithmic and computational questions related to "solving" games are also of central importance.

This course aims to bring together as a coherent body of knowledge the game theoretic algorithms & models that underpin several flourishing subjects at the intersection of computer science, economics and e-commerce, & AI.
Course description Examples of diverse games
Zero-sum two-person games: LP, simplex, LP-duality, mixed strategies and the minimax theorem

General games in strategic form:
- Equilibria and Nash's theorem
- 2-player equilibria: Lemke-Howson algorithm and its variants.

Games in Extensive form (mainly zero-sum, perfect information):
- Game trees. Relation to Strategic games
- and / or game graphs and reachability games
- bisimulation, simulation, parity games, and other omega-games on automata (finitely presented, infinite duration games)
- mean value games, MDPs, and stochastic games

Mechanism design and inverse game theory: designing games where selfish players will behave as desired:
- Vickery auctions and other mechanisms
- Combinatorial auctions
- Incentive structures for the internet.

Relevant QAA Computing Curriculum Sections: Artificial Intelligence, Data Structures and Algorithms, e-commerce, Simulation and Modelling, Theoretical Computing
Entry Requirements (not applicable to Visiting Students)
Pre-requisites It is RECOMMENDED that students have passed Algorithms and Data Structures (INFR10052)
Co-requisites
Prohibited Combinations Students MUST NOT also be taking Algorithmic Game Theory and its Applications (UG) (INFR11218)
Other requirements MSc students must register for this course, while Undergraduate students must register for INFR11218 instead.

This course is open to all Informatics students including those on joint degrees. For external students where this course is not listed in your DPT, please seek special permission from the course organiser.

Some mathematical maturity, and concretely some basic background in linear algebra; discrete mathematics; probability; at the level of the year 1 and 2 required undergraduate courses in these topics.

Background in algorithms, and exposure to computational complexity theory (NP - completeness, etc.) is desirable but not required.
Information for Visiting Students
Pre-requisitesAs above.
High Demand Course? Yes
Course Delivery Information
Academic year 2022/23, Available to all students (SV1) Quota:  None
Course Start Semester 2
Timetable Timetable
Learning and Teaching activities (Further Info) Total Hours: 100 ( Lecture Hours 20, Seminar/Tutorial Hours 8, Summative Assessment Hours 2, Programme Level Learning and Teaching Hours 2, Directed Learning and Independent Learning Hours 68 )
Assessment (Further Info) Written Exam 80 %, Coursework 20 %, Practical Exam 0 %
Additional Information (Assessment) Exam 80%
Coursework 20%

Students will be given written practical assignments reinforcing the material taught in class. The assignments are mainly theoretical, but some of the assigned questions may ask students to implement parts of algorithms for "solving" a game.

You should expect to spend approximately 32 hours on the coursework and tutorial sheet exercises, combined, for this course.
Feedback Marked coursework, plus weekly tutorial sheets which are not marked, but whose solutions are discussed at weekly tutorials.
Exam Information
Exam Diet Paper Name Hours & Minutes
Main Exam Diet S2 (April/May)Algorithmic Game Theory and its Applications (INFR11020)2:00
Learning Outcomes
On completion of this course, the student will be able to:
  1. Understand various models of games, how they are related, and how they arise in various applications in computer science and elsewhere
  2. Understand linear programming and some of its broad applicability
  3. Understand how algorithms are used to "solve" such games and their efficiency
  4. Model various scenarios as strategic games, and devise algorithms to solve them
  5. Understand the aims of the current research frontier
Reading List
M. Maschler, E. Solan, & S. Zamir, "Game Theory", 2013.
V. Chvátal, "Linear Programming", 1980.
N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (editors), "Algorithmic Game Theory", 2007.
Y. Shoham & K. Leyton-Brown, "Multiagent systems: algorithmic, game-theoretic, and logical foundations", 2009.
A. Mas-Colell, M. Whinston, and J. Green, "Microeconomic Theory", 1995.
T. Roughgarden, "Twenty Lectures on Algorithmic Game Theory", 2016.
Additional Information
Graduate Attributes and Skills Not entered
Keywordsgame theory,algorithms,data structures
Contacts
Course organiserDr Kousha Etessami
Tel: (0131 6)50 5197
Email: Kousha@inf.ed.ac.uk
Course secretaryMrs Helen Tweedale
Tel: (0131 6)50 2692
Email: Helen.Tweedale@ed.ac.uk
Navigation
Help & Information
Home
Introduction
Glossary
Search DPTs and Courses
Regulations
Regulations
Degree Programmes
Introduction
Browse DPTs
Courses
Introduction
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Prospectuses
Important Information