Verifying Equilibria in Finite-Horizon Probabilistic Concurrent Game Systems

Senthil Rajasekaran ORCID:0000-0002-6675-8063, Moshe Y. Vardi ORCID:0000-0002-0661-5773 · 2025

Read Verifying Equilibria in Finite-Horizon Probabilistic Concurrent Game Systems by Senthil Rajasekaran ORCID:0000-0002-6675-8063, Moshe Y. Vardi ORCID:0000-0002-0661-5773 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-14690.txt.

Introduction

Senthil Rajasekaran and Moshe Vardi study the cost of verifying equilibria in probabilistic game systems, in a 2025 paper. The catalog creator field adds identifier numbers, so the head byline governs. Many agents act at once over a set number of rounds, with chance in the outcomes, and a strategy profile is an equilibrium if no agent gains by straying.

Checking a given profile is easier than computing one from scratch, so it draws research focus. The authors show verification for the stricter subgame perfect form sits in a lower complexity class than for the Nash form, which is complete for a higher class. That flips intuition, since the stricter form looks harder.

Catalog record

CREATORSenthil Rajasekaran ORCID:0000-0002-6675-8063, Moshe Y. Vardi ORCID:0000-0002-0661-5773
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE108 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-14690

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Verifying Equilibria in Finite-Horizon Probabilistic Concurrent Game Systems Senthil Rajasekaran ORCID:0000-0002-6675-8063, Moshe Y. Vardi ORCID:0000-0002-0661-5773 Abstract . Finite-horizon probabilistic multi-agent concurrent game systems, also known as finite multiplayer stochastic games, are a well-studied model in computer science due to their ability to represent a wide range of real-world scenarios involving strategic interactions among agents over a finite number of iterations (given by the finite horizon). The analysis of these games typically focuses on evaluating (verifying) and computing (synthesizing/realizing) which strategy profiles (functions that represent the behavior of each agent) qualify as equilibria. The two most prominent equilibrium concepts are the Nash equilibrium and the subgame-perfect equilibrium , with the latter considered a conceptual refinement of the former. Computing these equilibria from scratch is, however, often computationally infeasible. Therefore, recent attention has shifted to the verification problem, where a given strategy profile must be evaluated to determine whether it satisfies equilibrium conditions. In this paper, we demonstrate that the verification problem for subgame-perfect equilibria lies in PSPACE, while for Nash equilibria, it is EXPTIME-complete. This is a highly counterintuitive result since subgame-perfect equilibria are often seen as a strict strengthening of Nash equilibria and are intuitively seen as more complicated. Apr. 10, 2025May 20, 2026 † † lmcs-doi: Volume 22, Issue 2, Paper 19 1. Introduction The ubiquity of distributed systems in modern computing architectures has motivated much recent work into the study of multi-agent systems [ GTW02 , Gup16 , MMPV14 , SL09 , VdHW08 , Woo09 , AKM+19 , RBV23 , RV22 , RV21 , BBM10 , BBMU11 , BMS14 , BBMU15 , BRRvdB24 , BRvdB23 ] , which are abstract mathematical models in which two or more rational agents interact with each other in order to achieve their goals. The broad motivation behind these works is to provide a mathematical framework for analyzing the overall trends of the complex mechanics that arise when multiple agents interact with one another in a strategic manner. Much of the relevant work in this area comes from the field of formal methods , which has recently begun to analyze equilibria in multi-agent systems as a way to analyze “stable” behaviors in multi-agent systems, and, therefore, analyze the system’s properties as a whole. The two major problems in the field of formal methods are the realizability [ PR89 ] and the verification problems [ Ros92 , RV22 ] . Therefore, much of the work in formal analysis of multi-agent systems is concerned with determining the existence of (the realizability problem) and verifying (the verification problem) different types of equilibria [ GTW02 , BBMU11 , BBM10 , BBMU15 , RBV23 , RV22 , RV21 , Gup16 , GNPW18 , GPW17 , BBMU15 , BRRvdB24 , BRvdB23 ] . As evidenced by the previously cited works, however, work in formal verification often comes with a strong preference for deterministic systems and deterministic agent behaviors. This creates something of an ideological divide between equilibrium analysis in the formal methods literature and the study of equilibria in the game theory literature. Our broad goal in this paper is to begin to bridge this divide by applying this formal methods style of equilibrium analysis to probabilistic systems. This is a new line of inquiry, as even papers in the formal methods literature that consider probabilistic systems such as [ GHL+21 ] (which itself notes the focus on deterministic systems in previous literature) consider notions of almost-sure satisfaction on infinite-length executions of a system. These notions allow for these probabilistic systems to be analyzed through the same techniques used for deterministic ones. In order to differentiate our work from this type of analysis, we consider finite-horizon systems, meaning that the system has an explicitly given finite bound on the number of steps in the execution of the system. This terminology follows the notation from the literature on Markov Decision Processes [ Put94 , Ete21 ] and breaks from the terminology of the formal verification literature, where finite-horizon is usually shorthand for “finite but unbounded” [ Woo09 , GV13 ] . Finite-horizon systems are also arguably more popular than their infinite-horizon counterparts in the literature on Markov Decision Process [ Put94 , Ete21 , Sol22 , BKN+19 ] , which can be seen as the “single-agent” analog of the systems we consider in this paper. We wish to consider the computational complexity of the realizability and verification problems in finite-horizon probabilistic multi-agent systems. The two most popular equilibrium concepts in the field of game theory are the Nash equilibrium [ Nas50 ] and the subgame-perfect equilibrium [ OR94 ] , with the latter a strengthening of the former. However, this immediately presents a problem for the realizability problem. Since the realizability problem is concerned with determining whether an equilibrium exists, and we are considering probabilistic systems with a finite horizon, the realizability problem becomes trivial. This is because subgame-perfect equilibria can be shown to always exist in these systems through the use of algorithms like backwards induction [ Far24 ] . Furthermore, if we note that every subgame-perfect equilibrium is, by definition, a Nash equilibrium, then we note that Nash equilibria always exist in these systems as well. If we remove the finite-horizon specification, then the status of the realizability problem for infinite-horizon systems now becomes a long-standing open problem in the field of game theory. In [ CMJ04 ] , it was claimed that there existed a 2-agent infinite-horizon game in which each of the agents had a reachability goal that did not have a Nash equilibrium. This claim, however, was shown to be flawed in [ BMS14 ] , so the question of whether the realizability problem is trivial in this setting is still open. Since even this is not known, the complexity of the realizability problem for Nash equilibria remains open in the infinite-horizon setting. Similarly, it is not known if a subgame-perfect equilibrium strategy profile always exists in the same unbounded setting. This leads us to focus on the verification problem for both the Nash and subgame-perfect equilibrium concepts. The verification problem takes an input of both a system and a candidate tuple of strategies and determines whether the input tuple of strategies satisfies the equilibrium condition. In this way, it can naturally be seen as dual to the often considered problem of computing an equilibrium from scratch that is foundational to fields like algorithmic game theory [ Rou10 ] . However, despite the fact that recent works [ RV22 , Umm11 , Par23 , KNPS21 ] and tools [ KNPS20 , GNPW18 , CGSP15 ] have begun to consider practical aspects of the verification problem, there has been virtually no theoretical development of the verification problem in probabilistic settings. In order to accurately isolate the complexity of verification, we introduce a new succinctly represented model in this paper, the b-bounded concurrent game system. In a b-bounded system, only b agents select an action concurrently at all given game-states, where b is a fixed constant. This model serves two purposes. First, it allows us to generalize from the popular but restrictive turn-based game model that is ubiquitous in the literature [ Umm11 , Gup16 , Woo09 , Rou10 ] . Second, it sharpens our complexity-theoretic results

Read the complete text