Group for Research in Decision Analysis

Nash equilibria in congestion games: Efficiency and unicity properties

Corinne Touati INRIA, France

In the field of game theory —that aim to study interactions between strategic agents — the central solution concept is the equilibrium introduced by John Nash (1928-2015). Roughly put, a vector of strategy is at Nash equilibrium if no agent (generally called player) can improve its payoff by unilaterally deviating from this strategy. This definition, however, is deceptively simple for two main reasons. First, computing Nash equilibria is known to be hard, with complexity belonging to the so-called PPAD class. Second, games with unique Nash equilibria are scarce, and the efficiency of equilibria may be difficult to assess or to bound.

In this talk, we focus in efficiency and unicity aspects of equilibria in a restricted class of games of particular interest in networks: the congestion games, in which agents compete for accessing a set of ressources. We consider different scenarios and present some surprising results.

Free entrance.
Welcome to everyone!