Level: M1 - M2
Contact: Dietmar Berwanger (dwb@lsv.fr) and Patricia Bouyer (bouyer@lsv.fr)
Location: Laboratoire Méthodes Formelles, ENS Paris-Saclay
Keywords: Games of perfect information, Nash equilibria
Description
Games (and especially games played on graphs) have been intensively used in computer science as a powerful way of modelling interactions between several computerised systems [6]. Until recently, more focus had been put on the study of purely antagonistic games (a.k.a. zero-sum games), which conveniently represent systems evolving in a (hostile) environment. In this zero-sum games setting, the objectives of both players are opposite: the aim of one player is to prevent the other player from achieving her own objective.
Over the last fifteen years, games with non-zero-sum objectives have come into the picture: they allow for conveniently modelling complex infrastructures where each individual system tries to fulfil its own objectives, while still being subject to uncontrollable actions of the surrounding systems. As an example, consider a wireless network in which several devices try to send data: each device can modulate its transmit power, in order to maximise its bandwidth and reduce energy consumption as much as possible. In that setting, focusing only on optimal strategies for one single agent may be too narrow. Game-theoreticians have defined and studied many other solution concepts for such settings, of which Nash equilibrium [7] is the most prominent. A Nash equilibrium is a strategy profile where no player can improve the outcome of the game by unilaterally changing her strategy. In other terms, in a Nash equilibrium, each individual player has a satisfactory strategy. Notice that Nash equilibria need not exist or be unique, and are not necessarily optimal: Nash equilibria where all players lose may coexist with more interesting Nash equilibria. Finding constrained Nash equilibria (e.g., equilibria in which some players are required to win) is thus an interesting problem for our setting.
While Nash equilibria are a prominent solution concept for rationality of players, they suffer of some defaults like non-credibility of some threats (strategy that a player would play to « punish » a player’s deviation, forgetting her own interest). The concept of subgame-perfect equilibria has been proposed as an alternative solution to solve the problem of non-credible threats [8]. Very recently, the notion of faithful Nash equilibria has been proposed [1], which would get rid of some defaults of subgame-perfect equilibria.
Game theory is cross-disciplinary, and solution concepts are of interest to various research communities. In the computer science community we are mostly (but not solely) interested in computability issues. Since more than fifteen years, there has been a growing interest in studying these concepts on games over graphs, and much progress has been made in this direction. We would like to cite for instance [5,4,3,2] for algorithmic aspects concerning Nash and subgame-perfect equilibria.
Internship goal
In this internship the goal is to understand the notion of faithful Nash equilibria (FNE), and to study computability and complexity issues for the synthesis of strategy profiles that are FNE. We will start with simple games given as finite trees (that is, games in extensive form). Then, if time allows, we will study this concept in the more general context of games over graphs.
This M2 internship proposal can be extended to a PhD proposal.
References
[1] Françoise Forges and József Sákovics. Tenable Threats when Nash equilibrium is the norm. Int. J. Game Theory 2022 (DOI: 10.1007/s00182-022-00806-3)
[2] Léonard Brice, Jean-François Raskin, Marie van den Bogaard. On the Complexity of SPEs in Parity Games. CSL 2022: 10:1-10:17 (DOI: 10.4230/LIPIcs.CSL.2022.10)
[3] Patricia Bouyer, Romain Brenguier, Nicolas Markey, Michael Ummels. Pure Nash Equilibria in Concurrent Deterministic Games. Log. Methods Comput. Sci. 11(2) (2015) (DOI: 10.2168/LMCS-11(2:9)2015)
[4] Michael Ummels. Stochastic multiplayer games: theory and algorithms. PhD thesis, RWTH Aachen University, 2011
[5] Michael Ummels. The Complexity of Nash Equilibria in Infinite Multiplayer Games. FoSSaCS 2008: 20-34 (DOI: 10.1007/978-3-540-78499-9_3)
[6] Wolfgang Thomas. Infinite Games and Verification (Extended Abstract of a Tutorial). CAV 2002: 58-64 (DOI: 10.1007/3-540-45657-0_5)
[7] John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(1):48–49, 1950.
[8] Roger B. Myerson. Game theory - Analysis of Conflict. Harvard University Press 1997