Pure Nash Equilibria in Concurrent Deterministic Games
Pure Nash Equilibria in Concurrent Deterministic Games
复制标题
并发确定性博弈中的纯纳什均衡
DOI：
10.2168/lmcs-11(2:9)2015
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Ummels
中科院分区：
文献类型：
--
作者：
P. Bouyer;Romain Brenguier;N. Markey;M. Ummels
研究了多人并发的纯策略纳什均衡问题
We study pure-strategy Nash equilibria in multi-player concurrent
deterministic games, for a variety of preference relations. We provide a novel
construction, called the suspect game, which transforms a multi-player
concurrent game into a two-player turn-based game which turns Nash equilibria
into winning strategies (for some objective that depends on the preference
relations of the players in the original game). We use that transformation to
design algorithms for computing Nash equilibria in finite games, which in most
cases have optimal worst-case complexity, for large classes of preference
relations. This includes the purely qualitative framework, where each player
has a single omega-regular objective that she wants to satisfy, but also the
larger class of semi-quantitative objectives, where each player has several
omega-regular objectives equipped with a preorder (for instance, a player may
want to satisfy all her objectives, or to maximise the number of objectives
that she achieves.)