$𝜺$-Stationary Nash Equilibria in Multi-Player Stochastic Graph Games

Motivated by this discussion, we consider the relaxed variant of the equilibrium concept that is also well-studied [18, 9]. Specifically, we study the problem of computing $\epsilon$-approximate Nash equilibria – in which the expected utility of each player is required to be within $\epsilon$ of the optimum response to the other players’ strategies – while still satisfying given constraints on the players’ payoffs. Formally, we focus on multi-player turn-based games with terminal rewards and for a (stationary) strategy profile that is an $\epsilon$-NE that also approximately satisfies the constraints (the constraints are also satisfied up to an $\epsilon$-additive factor), assuming there is an exact stationary NE.

The decision version of this problem is defined as follows: given such a game, determine whether either (i) there exists an exact NE that satisfies the constraints, or (ii) no $\epsilon$-approximate NE satisfies the constraints $\epsilon$-approximately. Instances that fall outside these two cases – that is, where an $\epsilon$-approximate equilibrium exists but no exact one does – are considered indeterminate, and the output may be arbitrary in those cases. Note that whenever there is an exact NE, by definition, there exists an $\epsilon$-NE.

We show that this approximate variant is computationally more tractable than the general problem of deciding the existence of a stationary constrained equilibrium. In particular, we present an algorithm that solves the problem within the class $\mathrm{𝖥𝖭𝖯}$ with access to an $\mathrm{𝖭𝖯}$ oracle. We also show that the probabilities required for the exact version of the problem can be double-exponentially small, proving some evidence of hardness of the problem. Finally, we show that the decision version of the problem is $\mathrm{𝖭𝖯}$-hard.

Given a (finite or infinite) set of outcomes $\mathrm{\Omega }$ and a probability measure $\mathbb{P}$ over $\mathrm{\Omega }$, let $X$ be a random variable over $\mathrm{\Omega }$, i.e., a mapping $X:\mathrm{\Omega }\to ℝ$. We write ${𝔼}^{\mathbb{P}}[X]$, or simply $𝔼[X]$, for the expected value of $X$, when defined. Given a finite set $S$, a probability distribution over $S$ is a mapping $d:S\to [0,1]$ that satisfies the equality ${\sum }_{x\in S}d(x)=1$.

Integers are always implicitly assumed to be represented with their binary encoding. For a given integer $n\in \mathbb{N}$, we therefore write $\mathrm{𝖻𝗂𝗍}(n)=\lceil {\log }_2(n+1)\rceil$ for the number of bits required to write $n$. Similarly, unless stated otherwise, a rational number $\frac{p}{q}$, where $p$ and $q$ are co-prime, is represented by the pair of the encodings of $p$ and $q$, and we write $\mathrm{𝖻𝗂𝗍}\left(\frac{p}{q}\right)=\mathrm{𝖻𝗂𝗍}(p)+\mathrm{𝖻𝗂𝗍}(q)+1$.

A directed graph $(V,E)$ consists of a set $V$ of vertices and a set $E$ of ordered pairs of vertices, called edges. For simplicity, we often write $uv$ for an edge $(u,v)\in E$. A path in the directed graph $(V,E)$ is a (finite or infinite) ordered sequence of vertices from $V$ such that every pair of two consecutive elements is an edge. A cycle is a path with distinct vertices such that the last element of the sequence and the first one also forms an edge.

Throughout this paper, we use the word game for multiplayer simple quantitative turn-based games played on graphs.

When referring to a game $𝒢$, we will often use the notations $V$ for vertices, $E$ for edges, $\mathrm{\Pi }$ for players, and so on without necessarily recalling them.

We call play a path in the underlying graph that is infinite, or whose last vertex is a terminal vertex. The payoff functions $\mu$ and ${\mu }_i$, defined only for terminal vertices, are extended naturally to plays as follows: for a play of the form $ht$, with $t\in T$, we define $\mu (ht)=\mu (t)$, and for an infinite play $\pi$, we define $\mu (\pi )={(0)}_{i\in \mathrm{\Pi }}$ (all players receive the payoff $0$ in an infinite path where no terminal vertex is reached).

In this paper, by strategy, we mean a stationary strategy, that is, a strategy that only depends on the current vertex.

Thus, in a game $𝒢$, a strategy for player $i$ is a mapping ${\sigma }_i$ that maps each vertex $v\in V_i$ to a probability distribution over the neighbours of $v$. A strategy profile for a subset $P\subseteq \mathrm{\Pi }$ is a tuple ${({\sigma }_i)}_{i\in P}$, that we usually write $\overline{\sigma }$ if $P=\mathrm{\Pi }$, and ${\overline{\sigma }}_{-i}$ if $P=\mathrm{\Pi }\setminus \{i\}$ for some player $i$. We then write $({\sigma }_{-i},{\sigma }_i^{\prime })$ to denote the strategy profile $\overline{\tau }$ defined by ${\tau }_i={\sigma }_i^{\prime }$ and ${\tau }_j={\sigma }_j$ for $j\ne i$.

A strategy profile $\overline{\sigma }$ for all players in the game $𝒢$ defines a probability measure ${\mathbb{P}}_{\overline{\sigma }}$ over plays – which turns the payoff functions ${\mu }_i$ into random variables. We then write $𝔼(\overline{\sigma })$ for the expectation operator ${𝔼}^{{\mathbb{P}}_{\overline{\sigma }}}$. If the game is a Markov chain, then we just write $𝔼$ to represent this value. We say the maximum payoff of an MDP is the maximum of all expectations over all stationary strategies and write $\mathrm{𝗏𝖺𝗅}={\max }_{\sigma }𝔼(\overline{\sigma })$ to denote it.

In such games, we study equilibria, that is, strategy profiles that offer some stability guarantees. The most famous notion of equilibrium is the Nash equilibrium [19].

A classical quantitative relaxation of Nash equilibria is that of $\epsilon$-approximate Nash equilibria, or just $\epsilon$-Nash equilibria.

A classical decision problem about Nash equilibria is the following one.

Problem 1 is known to be undecidable if the players are allowed to use memory [24], which is excluded by our formalism here. Where players are restricted to stationary strategy – as in our definition – this problem is known to be $\exists ℝ$-complete [16], where $\exists ℝ$ is the complexity class of problems that can be reduced to the satisfiability of a formula in the existential theory of the reals. In order to obtain a more tractable problem, we consider here an approximated version defined using the notion of $\epsilon$-NEs: we wish to obtain, for sure, the answer yes when an NE satisfying the constraint exists, and to obtain, for sure, the answer no when we are far from having such an NE because there is not even an $\epsilon$-NE that satisfies the constraint up to $\epsilon$ – but on the limit case, we can accept any answer. Formally, we want an algorithm that solves the following problem.

We call functional approximate constrained NE problem the functional version of this problem, in which the answer yes is replaced by a succinct representation of an $\epsilon$-NE that satisfies the constraint up to $\epsilon$. In the sequel, we show a ${\mathrm{𝖥𝖭𝖯}}^{\mathrm{𝖭𝖯}}$ upper bound on this functional problem, which implies an ${\mathrm{𝖭𝖯}}^{\mathrm{𝖭𝖯}}$ upper bound on the non-functional one; and an $\mathrm{𝖭𝖯}$ lower bound on the non-functional approximated problem, which implies an $\mathrm{𝖥𝖭𝖯}$ lower bound on the functional one.

A sentence in the existential theory of the reals is of the form

where $F(x_1,\mathrm{\dots },x_k)$ is a quantifier-free formula in the language of ordered fields over the reals $ℝ$. More concretely, atomic sub-formulas are

where $p\in ℝ[x_1,\mathrm{\dots },x_k]$ is a polynomial over $ℝ$, and arbitrary formulas are built by Boolean connectives.

This statement is similar to a result in the work of Hansen, Koucký, and Miltersen [15, Thm. 4]. We write the ETR sentence for solving constrained stationary Nash equilibrium in the following proposition.

The following part is similar to the ETR sentence for constrained stationary Nash equilibria found in the work of Ummels and Wojtczak [24, Theorem 4.5]. However, we require the explicit bounds on the number of variables, the degree polynomials, and the length of the sentence. Thus, we rewrite the explicit ETR sentence. First, by the assumption, there exists a strategy profile that is a stationary Nash equilibrium $\overline{\sigma }$. Let $S$ be the set of all non-zero edges in the strategy profile $\overline{\sigma }$. Furthermore, we define the set of vertices $V_S$ from which terminals can be reached with non-zero probability. Second, we have a formula that states that the variables $p_{vw}$ indeed describe a strategy. We enforce that the non-zero variables belong to the set $S$. We further ensure that for stochastic vertices, the variable $p_{vw}$ encodes exactly the value dictated by the probability function $𝗉$ by the stochastic vertex. This involves satisfying the following constraints:

1. 1.

   $p_{vw}>0$; for each $vw\in S$

2. 2.

   $p_{vw}\le 1$; for each $vw\in S$

3. 3.

   $p_{vw}=0$; for each $vw\notin S$

4. 4.

   ${\sum }_{w\in E(v)}{p}_{vw}=1$; for each non-stochastic vertex $v$

5. 5.

   $p_{vw}=𝗉(vw)$; for all stochastic vertices $v$.

The variables $r_v^i$ correspond to the payoff player $i$ receives by starting from the vertex $v$. The payoffs $r_v^i$ are equal to $0$ for all vertices in $V_S$ because no terminal is reachable from such vertices. The payoffs for other vertices satisfy the following constraints.

1. 6.

   $r_t^i={\mu }_i(t)$, for $t\in T$;

2. 7.

   $r_v^i=0$, for $v\notin V_S$;

3. 8.

   $r_v^i={\sum }_{w\in E(v)}{p}_{vw}{r}_v^i$, for $v\in V_S\setminus T$;

We now check that there is no unilateral deviation for the players by adding the following constraints. This following check is enough because, when fixing the strategies of all players except player $i$, the resulting structure is an MDP. For MDPs, Bellman equations characterise the value of each state and the equation below enforces that the value at a state $v$ is at least as large as the maximum value of any successor, thereby ensuring consistency with the Bellman equations of the induced MDP [4, Theorem 10.109].

1. 9.

   $r_v^i\ge r_w^i$, for $v\in V_i,w\in E(v)$;

Finally, we add the auxiliary variables $g_{vw}$ to keep track of the size of $p_{vw}$, which satisfy the following constraint:

1. 10.

   $g_{vw}{p}_{vw}=1$, for each $vw\in S$;

Thus, our ETR statement is: $\exists p\exists r\exists g$ that satisfies constraints $1$-$10$, completing the proof. $\mathrm{⊲}$

The following result from the work of Basu, Pollack, and Roy [5] guarantees that if a system of polynomial inequalities is satisfiable, then there is a valuation satisfiable within a ball with radius double-exponentially large with respect to the input size. Before we state the result, we recall that a partition of semi-algebraic subsets of ${ℝ}^k$ generated by a set of polynomials $𝒫$ is the collection of all nonempty sets of the form $\{x\in {ℝ}^k\mid \text{sign}(p(x))=\sigma (p)\text{ for all }p\in 𝒫\}$, where $\sigma :𝒫\to \{-1,0,1\}$ ranges over all possible sign assignments. Intuitively, the partition is obtained by slicing ${ℝ}^k$ according to which side of each polynomial in $𝒫$ a point lies on (positive, zero, or negative).

Note that each of the constraints in the ETR sentence is a polynomial of degree at most 2. The total number of variables is $O(m|\mathrm{\Pi }|)$. Note that we had introduced auxiliary variables $g_{vw}$ and required that $g_{vw}{p}_{vw}=1$, for each $vw\in S$. Since this is also a polynomial in $𝒫$, using Lemma 8, for all $vw\in S$, we have $g_{vw}\le 2^{\tau 2^{O(m|\mathrm{\Pi }|)}}$. Consequently, we have $p_{vw}\ge 2^{-\tau 2^{O(m|\mathrm{\Pi }|)}}$, which completes the proof. $◀$

We recall some results used in the work of Frederiksen and Milterson [14] where they adapted arguments that are standard in the context of numerical analysis to provide better algorithms for approximating the values of concurrent reachability games.

We define the set of floating-point numbers with precision $\mathrm{\ell }$ as

The floating-point representation of an element $x=m\cdot 2^e\in ℱ(\mathrm{\ell })$ uses $\mathrm{𝖻𝗂𝗍}(m)+\mathrm{𝖻𝗂𝗍}(|e|)$ bits. We define the relative distance of two positive real numbers $x,\tilde{x}$ as

Intuitively, $\mathrm{𝗋𝖾𝗅}(x,\tilde{x})$ describes the multiplicative distance. Observe that if the values are closer to $0$, but $\epsilon$ apart for some small $\epsilon$, their relative distance is larger than if these values are much larger and only $\epsilon$ apart. We say $x$ is $(\mathrm{\ell },i)$-close to $\tilde{x}$ if $\mathrm{𝗋𝖾𝗅}(x,\tilde{x})\le {(1-2^{1-\mathrm{\ell }})}^{-i}-1$, where $\mathrm{\ell }$ is a positive integer and $i$ is a non-negative integer. $(\mathrm{\ell },i)$-closeness measures how far two numbers can differ after $i$ steps of rounding in an $\mathrm{\ell }$-bit floating-point system. Here, $\mathrm{\ell }$ controls precision (smaller gaps between representable numbers), and $i$ allows for cumulative rounding error. So $x$ is $(\mathrm{\ell },i)$-close to $\tilde{x}$ if their relative difference is within about $i\cdot 2^{1-\mathrm{\ell }}$, that is, within $i$ units of machine precision.

We define ${\oplus }^{\mathrm{\ell }},{\ominus }^{\mathrm{\ell }},{\otimes }^{\mathrm{\ell }},{\oslash }^{\mathrm{\ell }}$ as finite precision arithmetic operations $+,-,\ast ,/$ respectively by truncating the result of the exact arithmetic operation to $\mathrm{\ell }$ bits. We drop the superscript $\mathrm{\ell }$ if context is clear.

We denote by $𝒟(\mathrm{\ell })$ the set of all floating-point probability distributions with precision $\mathrm{\ell }$. A probability distribution $\mu \in \mathrm{\Delta }([t])$ belongs to $𝒟(\mathrm{\ell })$ if there exists $w_1,w_2,\mathrm{\cdots },w_t\in ℱ(\mathrm{\ell })$ such that

• $\mathrm{■}$

  For all $i\in [t]$, we have $\mu (i)=\frac{w_i}{{\sum }_{j\in [t]}{w}_j}$; and

• $\mathrm{■}$

  ${\sum }_{j\in [t]}{w}_j$ and 1 are $(\mathrm{\ell },t)$-close.

We define the relative distance $\mathrm{𝗋𝖾𝗅}$ for probability distributions as $\mathrm{𝗋𝖾𝗅}(\mu ,\tilde{\mu })≔\max \{\mathrm{𝗋𝖾𝗅}(\mu (i),\tilde{\mu }(i)):i\in [t]\}$. We say $\mu$ is $(\mathrm{\ell },i)$-close to $\tilde{\mu }$ if $\mathrm{𝗋𝖾𝗅}(\mu ,\tilde{\mu })\le {(1-2^{1-\mathrm{\ell }})}^{-i}-1$, where $\mathrm{\ell }$ is a positive integer and $i$ is a non-negative integer.

We first recall the result in the work of Frederiksen and Milterson [14] related to approximation of probability distributions by floating-point distributions.

A stationary strategy comprises of probability distributions over actions for each state. We can truncate a strategy by truncating each of these probability distributions. Let the strategy profile ${\overline{\sigma }}^{\prime }$ be the truncation of the strategy profile $\overline{\sigma }$ defined in the above result. Therefore, for all players $i$ and vertices $v\in V_i$, we have that $\overline{\sigma }(v)$ and ${\overline{\sigma }}^{\prime }(v)$ are $(\mathrm{\ell },2n)$-close. Consequently, for all vertices $v,w\in V$,

We then recall the result in the work of Solan [21]. This result provides an upper bound on the difference between the reachability values of two Markov chains based on the relative distance of their transition functions.

By Equation 1 and Lemma 11, we bound the the difference of payoffs for $\overline{\sigma }$ and ${\overline{\sigma }}^{\prime }$. For all players $i$, we have $|𝔼(\overline{\sigma })[{\mu }_i]-𝔼({\overline{\sigma }}^{\prime })[{\mu }_i]|\le 16n^2{2}^{-\mathrm{\ell }}$. Since the strategy profile $\overline{\sigma }$ is a constrained Nash equilibrium, ${\overline{\sigma }}^{\prime }$ is a $(32n^2{2}^{-\mathrm{\ell }})$-constrained Nash equilibrium, which completes the proof. $◀$

In the above result, we show that it is sufficient to consider floating-point representable strategies to solve the problem. We now present the ${\mathrm{𝖭𝖯}}^{\mathrm{𝖭𝖯}}$ procedure. We first recall the result in the work of Frederiksen and Milterson [14] related to computing the approximate value of MCs with floating-point distributions.

We first present the $\mathrm{𝖼𝗈𝖭𝖯}$ procedure and then prove its soundness and completeness.

The procedure guesses a pure stationary strategy $\sigma$ for the player. Note that the size of the representation of a pure stationary strategy is polynomial with respect to the size of the representation of $𝒫$. By fixing $\sigma$, we obtain an MC $ℳ$. We denote by ${\mathrm{𝗏𝖺𝗅}}_{\sigma }$ the value $𝔼(\sigma )[\mu ]$. By Lemma 12, there exists a polynomial time algorithm that computes an $\epsilon$-approximation ${\widehat{\mathrm{𝗏𝖺𝗅}}}_{\sigma }$ of ${\mathrm{𝗏𝖺𝗅}}_{\sigma }$. Our procedure outputs no if $\alpha \le {\widehat{\mathrm{𝗏𝖺𝗅}}}_{\sigma }$. If there exists no such pure stationary strategy, the procedure outputs yes.

If $\alpha \le \mathrm{𝗏𝖺𝗅}-\epsilon$, then, by [12], there exists a pure stationary strategy $\sigma$ such that $\mathrm{𝗏𝖺𝗅}={\mathrm{𝗏𝖺𝗅}}_{\sigma }$. The procedure non-deterministically guesses $\sigma$. By Lemma 12, we have ${\widehat{\mathrm{𝗏𝖺𝗅}}}_{\sigma }+\epsilon \ge {\mathrm{𝗏𝖺𝗅}}_{\sigma }$. Therefore, we have $\alpha \le {\widehat{\mathrm{𝗏𝖺𝗅}}}_{\sigma }$, and the procedure outputs no.

If $\alpha \ge \mathrm{𝗏𝖺𝗅}+\epsilon$, then for all pure stationary strategies $\sigma$, we have $\alpha \ge {\mathrm{𝗏𝖺𝗅}}_{\sigma }+\epsilon$. By Lemma 12, we have ${\widehat{\mathrm{𝗏𝖺𝗅}}}_{\sigma }-\epsilon \le {\mathrm{𝗏𝖺𝗅}}_{\sigma }$. Therefore, $\alpha \ge {\widehat{\mathrm{𝗏𝖺𝗅}}}_{\sigma }$ which implies that the procedure outputs yes and yields the result. $◀$

We first present the procedure and then prove its soundness and completeness.

Let $\mathrm{\ell }$ be sufficiently large. The procedure guesses a strategy profile and verifies that it is an $\epsilon /8$-constrained stationary Nash equilibrium $\overline{\sigma }$. By Lemma 6 and Lemma 9, the size of the representation of $\overline{\sigma }$ is polynomial with respect to the size of game and $\mathrm{𝖻𝗂𝗍}(\epsilon )$. By fixing the strategy profile $\overline{\sigma }$, we obtain an MC $ℳ$. We denote by ${\mathrm{𝗏𝖺𝗅}}_i$ the payoff of $ℳ$ where the reward function is ${\mu }_i$. By Lemma 11, the procedure computes the $\epsilon /8$-approximate payoff ${\widehat{\mathrm{𝗏𝖺𝗅}}}_i$ in polynomial time. For each player $i$, by fixing the strategy profile ${\overline{\sigma }}_{-i}$, we obtain an MDP ${𝒫}_i$. We denote by ${\widetilde{val}}_i$ the value of ${𝒫}_i$ where the reward function is ${\mu }_i$. Then, the procedure checks if there exists an $\epsilon$-unilateral deviation for player $i$ by deciding if ${\widetilde{\mathrm{𝗏𝖺𝗅}}}_i$ for is at most ${\widehat{\mathrm{𝗏𝖺𝗅}}}_i(v)+3/4\epsilon$ up to additive error $\epsilon /8$. The procedure finally checks if the payoff constraints are satisfied.

We assume that $\overline{\sigma }$ is not an $\epsilon$-constrained Nash equilibrium, i.e., there exists a player $i$ such that $\epsilon$-unilateral deviation is possible. Equivalently, we have ${\mathrm{𝗏𝖺𝗅}}_i\le {\widetilde{\mathrm{𝗏𝖺𝗅}}}_i-\epsilon$. Therefore, we have

However, for this case, the $\mathrm{𝖼𝗈𝖭𝖯}$ procedure defined in Lemma 13, successfully outputs no. Therefore, our procedure does not output $\overline{\sigma }$ as $\epsilon$-constrained stationary Nash equilibrium, which yields the soundness of our procedure.

By Lemma 6 and Lemma 9, there exists an $\epsilon /8$-constrained stationary Nash equilibrium $\overline{\sigma }$ which is polynomial-size representable. The procedure non-deterministically guesses $\overline{\sigma }$. Since the strategy profile is $\epsilon /8$-Nash equilibrium, for all players $i$, we have ${\widetilde{\mathrm{𝗏𝖺𝗅}}}_i\le {\mathrm{𝗏𝖺𝗅}}_i+\epsilon /8$. Therefore, we get

Thus, the $\mathrm{𝖼𝗈𝖭𝖯}$ procedure outputs yes. Therefore, our procedure successfully decides that $\overline{\sigma }$ is a $\epsilon$-constrained stationary Nash equilibrium. This yields the completeness of the procedure and completes the proof. $◀$

We proceed by reduction from the $3\mathrm{𝖲𝖠𝖳}$ problem. Let $\phi ={\bigvee }_{i=1}^m\left(L_{i1}\wedge L_{i2}\wedge L_{i3}\right)$ be a CNF formula, over the variable set $X$.