Permissive Equilibria in Multiplayer Reachability Games

We study multiplayer reachability games played on a finite graph. However, instead of studying the classical notion of strategy, we consider the concept of multi-strategy. A multi-strategy for Player i prescribes a set of possible actions when it is Player i's turn to play, instead of a single action. Thus, once a multi-strategy is fixed for each player, there are several paths in the game graph that are consistent with these multi-strategies from a given initial vertex. In this setting, we aim at synthesizing the most permissive multi-strategies. The permissiveness of multi-strategies may be compared in different ways. We here extend the concept of penalty of a multi-strategy, already defined in a two-player zero-sum setting in Bouyer at al. [1], to the multiplayer setting. This penalty depends on weights associated with edges not chosen by the multi-strategy, and we prefer a multi-strategy with a penalty as small as possible. Once the notions of permissive Nash equilibrium and subgame perfect equilibrium are properly defined, our aim is to decide the existence of a permissive equilibrium that satisfies some constraints on the penalties (one upper-bound penalty is fixed per player). Since the existence of such permissive equilibrium does not provide any certainty about the satisfaction of the reachability objective of the players, we also study permissive equilibria with bounded penalties and which satisfy some properties on the set of players who satisfy their objective. This is a joint work with Benjamin Monmege. [1] Patricia Bouyer, Marie Duflot, Nicolas Markey, Gabriel Renault: Measuring Permissivity in Finite Games. CONCUR 2009

Authors

• Aline Goeminne

Keywords

No keywords are indexed for this paper.