TY - GEN
T1 - Correlated equilibria and fairness in concurrent stochastic games
AU - Kwiatkowska, Marta
AU - Norman, Gethin
AU - Parker, David
AU - Santos, Gabriel
PY - 2022/3/30
Y1 - 2022/3/30
N2 - Game-theoretic techniques and equilibria analysis facilitate the design and verification of competitive systems. While algorithmic complexity of equilibria computation has been extensively studied, practical implementation and application of game-theoretic methods is more recent. Tools such as PRISM-games support automated verification and synthesis of zero-sum and (ε-optimal subgame-perfect) social welfare Nash equilibria properties for concurrent stochastic games. However, these methods become inefficient as the number of agents grows and may also generate equilibria that yield significant variations in the outcomes for individual agents. We extend the functionality of PRISM-games to support correlated equilibria, in which players can coordinate through public signals, and introduce a novel optimality criterion of social fairness, which can be applied to both Nash and correlated equilibria. We show that correlated equilibria are easier to compute, are more equitable, and can also improve joint outcomes. We implement algorithms for both normal form games and the more complex case of multi-player concurrent stochastic games with temporal logic specifications. On a range of case studies, we demonstrate the benefits of our methods.
AB - Game-theoretic techniques and equilibria analysis facilitate the design and verification of competitive systems. While algorithmic complexity of equilibria computation has been extensively studied, practical implementation and application of game-theoretic methods is more recent. Tools such as PRISM-games support automated verification and synthesis of zero-sum and (ε-optimal subgame-perfect) social welfare Nash equilibria properties for concurrent stochastic games. However, these methods become inefficient as the number of agents grows and may also generate equilibria that yield significant variations in the outcomes for individual agents. We extend the functionality of PRISM-games to support correlated equilibria, in which players can coordinate through public signals, and introduce a novel optimality criterion of social fairness, which can be applied to both Nash and correlated equilibria. We show that correlated equilibria are easier to compute, are more equitable, and can also improve joint outcomes. We implement algorithms for both normal form games and the more complex case of multi-player concurrent stochastic games with temporal logic specifications. On a range of case studies, we demonstrate the benefits of our methods.
UR - http://www.scopus.com/inward/record.url?scp=85126844931&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-99527-0_4
DO - 10.1007/978-3-030-99527-0_4
M3 - Conference contribution
SN - 9783030995263
T3 - Lecture Notes in Computer Science
SP - 60
EP - 78
BT - TACAS 2022
A2 - Fisman, D.
A2 - Rosu, G.
PB - Springer
T2 - 28th International Conference on Tools and Algorithms for the Construction and Analysis of Systems
Y2 - 2 April 2022 through 7 April 2022
ER -