From its origins, following the publication of "Theory of Games and Economic Behavior" by John von Neumann and Oskar Morgenstern in 1944, game theory has
developed primarlily as an analytic framework for economic and social interaction. However, beginning with the early 80ies, games of various kinds have been used increasingly as models of interaction in computational systems. The objective of this course is to present a sample of game models together with prominent applications in different areas of computer science.
A central part of this course will be devoted to the study of infinite games played over finite or infinite graphs. The theory of infinite games is intertwined with the theory of automata over infinite objects (words, trees) and it has important applications to the automatic verification of programs.
Aside with automata theory and program verification, the study of the internet emerged as a fertile application area for game-theoretic techniques. Thus, essential problems about network traffic control, optimal routing policy, and combinatorial auctions can be phrased and solved as problems about games. This course proposes an introduction into these novel areas of research via the so-called classical theory of games.
Course overview
Perfect-information games on graphs
Strictly competitive games of infinite duration arise as a
natural model for the interaction between a reactive program and its
environment.
As a fundamental case, we study games with perfect information
and qualitatitive payoffs (either win or lose). Main topics
are:
omega-regular games and finite-state strategies,
memoryless determinacy for parity games, and
algorithmic synthesis of optimal strategies.
In extension, we discuss mean-payoff games. These are games with
quantitative payoffs where each move is associated with a
local payoff and the players aim to maximise the long-run cummulative
payoff.
Games and tree automata:
We introduce a basic model of automata over infinite trees, and illustrate its connections with games over finite graphs (emptiness, complementation). Tree automata will also be employed for mu-calculus model-checking.
Games with imperfect information, concurrent moves
Games with imperfect information model situations where
decisionmakers are uncertain about the events that occurred in a
global system. An important particular case are concurrent games,
where the players act simultaneously.
We survey various criteria of optimal behaviour in such games and
the associated algorithmic problems.
Introduction to classical game theory
Games in strategic form.
Nash equilibrium.
Two-player zero-sum games with finitely many strategies.
The Min-Max Theorem of John von Neuman.
Games in extensive form.
Introduction to repeated games.
Refinements of Nash equilibrium.
Algorithmic mechanism design
In the traditional approach to mutli-agent or distributed systems, agents are assumed to either follow a prescribed algorithm towards achieving their abjective or to act purely hostile to impede others from acheiveing theirs.
Systems with several agents are also studied in economic game theory. In this context, however, agents rarely obey a prescribed procedure nor are they purely hostile to other agents. One main difference between computatational and economic agents is that the latter ones are sensitive to incentives. At this point, the central question of mechanism design arises: given a global objective (such as maximising social welfare, for instance), how to conceive a system of incentives with that encourage individual actions in such a way that their composition supports the global objective. Hence, mechanism design is concerned with building games rather than solving them.
It is noteworthy that the classical approach to economic mechanism design largely ignores issues of computational complexity. With the development of the Internet we are facing a complex global system of agents that pursue their individual objectives according to their computational abilities on the one hand and the offered incentives on the other hand. Introduced in a seminal article by Nisan and Ronen, Algorithmic Mechanism Design emerged as a theory where incentive structures are studied in the light of computational complexity.
In this part of the lecture, we will discuss the following topics:
introduction to mechanism design, the Vickrey-Clarke-Groves mechanism;
classical imposibility results (Gibbard-Sattertwaite Theorem), and
examples of algorithmic mechanism design.
Course Schedule
The lectures take place on Tuesdays 12h45 -- 14h15 in the Rentiers building (30, Rue du Chateau des Rentiers, room 131).
The final exam will be on Tuesday 9 February at 13h00 the usual place of the lecture (Rentiers).
Séance 1: 14/09 [Olivier Serre] Introduction.
Séance 2: [Olivier Serre] Games on finite graphs 1/3.
Séance 3: [Olivier Serre] Games on finite graphs 2/3.
Séance 4 [Olivier Serre] Games on finite graphs 3/3.
Séance 5 [Olivier Serre] Games, tree automata, and logics 1/2.
Séance 6 [Olivier Serre] Games, tree automata, and logics 2/2.
Séance 7 [Dietmar Berwanger] Quantitative and stochastic games 1/3.
Séance 8 [Dietmar Berwanger] Quantitative and stochastic games 2/3.
Séance 9 [Dietmar Berwanger] Quantitative and stochastic games 3/3.
Séance 10 [Dietmar Berwanger] Imperfect information 1/3
Séance 11 [Dietmar Berwanger] Imperfect information 2/3
Séance 12 [Dietmar Berwanger] Imperfect information 3/3
Séance 13 [Olivier Serre] Games on infinite graphs 1/2.
Séance 14 [Olivier Serre] Games on infinite graphs 2/2.
Séance 15 [Dietmar Berwanger] Strategic games and Mechanism Design 1/2
Séance 16 [Dietmar Berwanger] Strategic games and Mechanism Design 2/2
Language of the course
Dietmar Berwanger gives the lectures in English.
Wieslaw Zielonka gives the lectures in French but, if there is a demand
and if all other students agree, he can give the lectures in English.
Examinations will be both in French and English.
Material
Course material will be available at the following webpages:
Familiarity with classical automata theory over finite words will be helpful for following the section about games on graphs. We recommend those students who are not acquainted with this area to join the catch-up course on Automata given by Olivier Carton at the beginning of the semester.
Literature
Roger B. Myerson, Game theory. Analysis of Conflict, Harvard University Press.
Martin J. Osborne and Ariel Rubinstein, A Course in Game Theory, The MIT Press.
Drew Fudenberg and Jean Tirole, Game theory, The MIT Press.
Tim Roughgarden, Selfish Routing and the Price of Anarchy. The MIT Press (avec google on peut trouver la thèse de Roughgarden qui couvre une grande partie de ce livre).
Roger B. Myerson, Game theory. Analysis of Conflict, Harvard University Press.
Erich Grädel, Wolfgang Thomas, Thomas Wilke (eds.), Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], Lecture Notes in Computer Science 2500, Springer 2002.
Erich Grädel et al., Finite Model Theory and Its Applications, EATCS Texts in Theoretical Computer Science, Springer 2007.
Elwyn R. Berlekamp, Richard K. Guy, John Horton Conway, Winning Ways for Your Mathematical Plays, AK Peters, 4 volumes.
![[arobase]](./commercial_at.png){kind=small}
mpri![[point]](./full_stop.png){kind=small}
master![[Version Française]](./french_flag.png)