Nicolas Markey

Abstract

We study the existence of mixed-strategy equilibria in concurrent games played on graphs. While existence is guaranteed with safety objectives for each player, Nash equilibria need not exist when players are given arbitrary terminal-reward objectives, and their existence is undecidable with qualitative reachability objectives (and only three players). However, these results rely on the fact that the players can enforce infinite plays while trying to improve their payoffs. In this paper, we introduce a relaxed notion of equilibria, where deviations are imprecise. We prove that contrary to Nash equilibria, such (stationary) equilibria always exist, and we develop a PSPACE algorithm to compute one.

@inproceedings{gandalf2016-BMS,
  author =              {Bouyer, Patricia and Markey, Nicolas and Stan,
                         Daniel},
  title =               {Stochastic Equilibria under Imprecise Deviations in
                         Terminal-Reward Concurrent Games},
  editor =              {Cantone, Domenico and Delzanno, Giorgio},
  booktitle =           {{P}roceedings of the 7th {I}nternational {S}ymposium
                         on {G}ames, {A}utomata, {L}ogics and {F}ormal
                         {V}erification ({GandALF}'16)},
  acronym =             {{GandALF}'16},
  series =              {Electronic Proceedings in Theoretical Computer
                         Science},
  volume =              {226},
  pages =               {61-75},
  year =                {2016},
  month =               sep,
  doi =                 {10.4204/EPTCS.226.5},
  abstract =            {We study the existence of mixed-strategy equilibria
                         in concurrent games played on graphs. While
                         existence is guaranteed with safety objectives for
                         each player, Nash equilibria need not exist when
                         players are given arbitrary terminal-reward
                         objectives, and their existence is undecidable with
                         qualitative reachability objectives (and~only three
                         players). However, these results rely on the fact
                         that the players can enforce infinite plays while
                         trying to improve their payoffs. In this paper, we
                         introduce a relaxed notion of equilibria, where
                         deviations are imprecise. We prove that contrary to
                         Nash equilibria, such (stationary) equilibria always
                         exist, and we develop a PSPACE algorithm to compute
                         one.},
}