Course Catalogue

View Specification Document | Reading List

The main goal of this course is to highlight the intriguing interplay between computational thinking and foundational principles of game theory. We investigate the mathematical concepts that model strategic interactions between different selfish entities, and we use the algorithmic theory lens in order to analyse the existence and quality of equilibrium solutions, study their computational hardness, and design mechanisms to incentivize desirable behaviour. The rigorous study of these notions gives students the fundamental tools to predict and analyse the outcomes in complex scenarios, fostering a deeper understanding of the underlying incentive structures and decision-making processes that play an important role in many modern, real-life applications, where the Internet has been established as the main platform for computing and interaction.

3 hours per week, organized as: one 2-hour lecture per week and one 1-hour tutorial per week

Algorithmics I (H) (or equivalent)

None

Algorithmics II (H) (or equivalent) is recommended but not required

Final examination 70%

Two take-home assessed exercise sets 15%

■ Provide students with a good understanding of the foundations of the field of Computational Game Theory (CGT).

■ Engage them into a critical discussion about some of the key game-theoretic concepts used in modern applications within Computer Science and Economics.

■ Expose them to the historical and technical interplay between Computer Science, Mathematics, and Economics, as this is realized through the development of CGT.

■ Give a glimpse into the motivation, toolbox, and the necessary fundamentals of some key research areas within CGT, after which students should feel comfortable to start following the related work on their own.

By the end of this course (conditioned on the list of topics chosen) students will be able to:

1. Compare and evaluate various important equilibrium notions used in game theory analysis; based on that,

2. Create games that have desirable strategic outcomes.

3. Evaluate the computational hardness of finding such equilibria.

4. Familiarize themselves with important results, key mathematical notions, and historical points in the development of (Computational) Game Theory; have a critical understanding of their significance within the field and be able to draw new connections between them.

5. Evaluate the loss in performance of a system due to selfish behaviour ("Price of Anarchy")

6. Understand the concept of learning dynamics in game-playing, such as best-responses or no-regret learning. Evaluate the performance of such dynamics and use them critically, depending on the application, as an alternative to traditional, static equilibrium concepts.