Robust equilibria in mean-payoff games

Conference item

We study the problem of finding robust equilibria in multiplayer concurrent games with mean payoff objectives. A (k, t)-robust equilibrium is a strategy profile such that no coalition of size k can improve the payoff of one its member by deviating, and no coalition of size t can decrease the payoff of other players. While deciding whether there exists such equilibria is undecidable in general, we suggest algorithms for two meaningful restrictions on the complexity of strategies. The first restriction concerns memory. We show that we can reduce the problem of the existence of a memoryless robust equilibrium to a formula in the (existential) theory of reals. The second restriction concerns randomisation. We suggest a general transformation from multiplayer games to two-player games such that pure equilibria in the first game correspond to winning strategies in the second one. Thanks to this transformation, we show that the existence of robust equilibria can be decided in polynomial space, and that the decision problem is PSPACE-complete.

Authors: Brenguier, R

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer, Berlin, Heidelberg
• Host title: International Conference on Foundations of Software Science and Computation Structures: FoSSaCS 2016
• Volume: 9634
• Pages: 217-233
• Series: Lecture Notes in Computer Science
• Publication date: 2016-01-01
• Acceptance date: 2015-12-18
• DOI: 10.1007/978-3-662-49630-5_13
• ISSN: 0302-9743
• ISBN: 9783662496299