Cooperative Concurrent Games

In rational verification, one is interested in understanding which temporal logic properties will hold in a concurrent game, under the assumption that players choose strategies that form an equilibrium. Players are assumed to behave rationally in pursuit of individual goals, typically specified as temporal logic formulae. To date, rational verification has only been studied in noncooperative settings. In this paper, we extend the rational verification framework to cooperative games, in which players may form coalitions to collectively achieve their goals. We base our study on the computational model given by concurrent game structures and focus on the core as our basic solution concept. We show the core of a concurrent game can be logically characterised using ATL*, and study the computational complexity of key decision problems associated with the core, which range from problems in PSPACE to problems in 3EXPTIME. We also discuss a number of variants of the main definition of the core, leading to the issue of credible coalition formations, and a possible implementation of the main reasoning framework.

Authors

• Julian Gutierrez
• Sarit Kraus Bar-Ilan University
• Michael Wooldridge University of Oxford

Keywords

• Concurrent Games
• Cooperative Games
• Logic
• Formal Verification