Welcome to Algorithmic Game Theory and Applications
This is an MSc (and 4th year) course that runs in Semester 2 (Spring 2024). The lecturer is Kousha Etessami. (Some of the information below is still from the prior year, 2023. It will be updated during the course.) The lecture times for the course are Mondays and Thursdays, 11:10-12:00 (Edinburgh time). The lectures will be recorded and posted online. There will also be weekly tutorials, starting in Week 3. These will cover and discuss the contents of the weekly tutorial sheet. There is also a Piazza Discussion Forum for the course, accessible from the LEARN page, where you can post questions and discuss the course content with fellow students (but DO NOT share answers to coursework). The times are indicated under "Timetable" on the AGTA course DPT on the DRPS web pages (the tutorial time slots may be subject change at the beginning of the course).
On successful completion of this course, you should be able to:
- understand various models of games, how they are related, and how they arise in various applications in computer science and elsewhere
- understand linear programming and some of its broad applicability
- understand how algorithms are used to "solve" such games and their efficiency
- model various scenarios as strategic games, and devise algorithms to solve them
- understand the aims of the current research frontier
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
All rights reserved The University of Edinburgh