Bouyer, Patricia and Brenguier, Romain and Markey, Nicolas and Ummels, Michael - Pure Nash Equilibria in Concurrent Deterministic Games

lmcs:1569 - Logical Methods in Computer Science, June 19, 2015, Volume 11, Issue 2
Pure Nash Equilibria in Concurrent Deterministic Games

Authors: Bouyer, Patricia and Brenguier, Romain and Markey, Nicolas and Ummels, Michael

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.)


Source : oai:arXiv.org:1503.06826
DOI : 10.2168/LMCS-11(2:9)2015
Volume: Volume 11, Issue 2
Published on: June 19, 2015
Submitted on: August 11, 2016
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computer Science and Game Theory


Share

Browsing statistics

This page has been seen 46 times.
This article's PDF has been downloaded 21 times.