Finding Equilibria: Simpler for Pessimists, Simplest for Optimists

We illustrate this claim with the help of a simple game, depicted in Figure 1(a). Each vertex other than the start vertex is owned by one player among the players $\{\circ ,\mathrm{\square },\mathrm{◇}\}$ and a play in this game refers to a sequence of moves of a token along the edges of the graph. The initial vertex $s$ denotes a stochastic vertex, which moves the token to the next vertex with probability $\frac{1}{2}$ at each step. When the token is on a vertex owned by a player $i$, that player decides where the token goes next, and when a terminal vertex (vertex $t_1,t_2,t_3$, or $t_4$) is reached, the numbers at the terminal vertex indicate the payoff obtained by each player.

If the token moves out of vertex $s$, player $\circ$ then chooses between a green $(\downarrow )$ or an orange action $(\to )$. If the action $\to$ was selected, the player $\mathrm{\square }$ must make a similar choice (between actions $\downarrow$ and $\to$). If both players selected the action $\to$, then the player $\mathrm{◇}$ is given the opportunity to reach a terminal that offers negative reward to either player $\circ$ or $\mathrm{\square }$, while the other player gets an additional profit (payoff $1$ instead of $0$).

A strategy profile is a Nash equilibrium (NE) if no player can increase their expected payoff by changing their strategy as long as the other players stick to theirs. If player $\mathrm{◇}$ does not use randomisation, there is no NE in this game where she gets an expected payoff $1$, since along any play that reaches deterministically either the vertex $t_3$ or $t_4$, one of the two players $\circ$ or $\mathrm{\square }$ gets the expected payoff $0$ and has an incentive to deviate to the action $\downarrow$ at their vertex. However, using randomisation, there is such an NE if both player $\circ$ and $\mathrm{\square }$ choose action $\to$, and player $\mathrm{◇}$ chooses at random to go either to vertex $t_3$ or $t_4$, each with probability $\frac{1}{2}$. Then, both player $\circ$ and player $\mathrm{\square }$ have expected payoff $1$, the same as if they reach the terminals vertices $t_1$ or $t_2$.

However, if both the players $\circ$ and $\mathrm{\square }$ were modelling, say, safety-critical systems, such a Nash equilibrium is dubious because neither player can afford, even a low probability of, the reward $-1$ as they do not have this tolerance to risk. Such a strategy profile would not be stable even if only one of the two players $\circ$ or $\mathrm{\square }$, let alone both, were risk-averse. However, the strategy where player $\circ$ choses the action $\to$, player $\mathrm{\square }$ the action $\downarrow$, and player $\mathrm{◇}$ randomises between her choices with equal probability, is a potential equilibrium in the case where player $\mathrm{\square }$ is risk averse. On the other hand, if all players $\circ$, $\mathrm{\square }$, and $\mathrm{◇}$ were risk loving, say they model entities like hackers of a system that are happy with some chance at a small positive reward, the same strategy would not be an equilibrium, as player $\mathrm{\square }$ would rather gamble for chance at the reward $+1$, despite the risk of a negative reward, thus deviating from the action $\downarrow$ instead to the “risky” alternative $\to$.

This example thus generalises a line of reasoning that is often made in finance or decision theory: consider a participant of a certain lottery where they lose $100 with probability $\frac{99}{100}$, and wins $10000 with probability $\frac{1}{100}$. While the expected payoff is positive ($1), expectation alone is insufficient as a decision criterion to participate in the lottery.

A risk measure captures the perception that a player has of what their payoff will be. Thus, it generalises the notion of expected payoff. Various risk measures exist in the literature, and have been used extensively in the field of economics and finance. They include expected shortfall (ES), value at risk (VaR) [2], variance [4], entropic risk measure (ER) [10]. In terms of graph modelling, these risk measures have been studied mainly over Markov decision processes (MDPs) using variance (along with mean) as a risk measure [9, 27, 21], ES [28, 19, 22] (also referred to as conditional value at risk (CVaR), average value at risk (AVaR), expected tail loss (ETL), and superquantile in literature) and ER [15, 7, 3]. Studying the entropic risk measure in MDPs appears more practical compared to ES or using variance-penalised risk measures, due to the intractable exponential memory [14] and time required to compute optimal strategies [27] for the other measures, even in MDPs. On the other hand, when the risk measure used is ER, players have optimal positional strategies in MDPs [16].

The entropic risk measure is computed by assigning a risk parameter to an agent, i.e., a value $\rho \in ℝ$. The entropic risk measure of a random variable $X$ is then defined as ${𝕄}_{\rho }[X]=-\frac{1}{\rho }{\log }_e\left(𝔼\left[e^{-\rho X}\right]\right)$ [12] for $\rho \ne 0$. Assume $X$ is a player’s payoff. If the risk parameter $\rho$ is positive, the corresponding players are risk-averse and therefore more weight is given to worse payoffs. Conversely, players with a negative $\rho$ are risk-loving. When $\rho$ tends to $0$, the entropic risk measure converges to the classical expectation $𝔼[X]$.

Consider again the game in Figure 1(a), and the strategy profile in which player $\circ$ and player $\mathrm{\square }$ choose action $\to$, and player $\mathrm{◇}$ goes to the vertex $t_3$ with probability $p\in [0,1]$, and to vertex $t_4$ with probability $1-p$. Then, player $\circ$’s perception of such a strategy profile, depending on her risk parameter $\rho$, is defined by the entropic risk measure $𝕄[{\mu }_{\circ }]=-\frac{1}{\rho }{\log }_e\left(p{e}^{-\rho }+(1-p)e^{\rho }\right)$. Figure 1(b) illustrates this formula, where each curve captures the perceived payoff for a fixed probability $p$, the thick blue line corresponds to the case $p=0$, the thick red line to $p=1$, and mixtures of blue and red curves to intermediary cases – the thick purple curve corresponds to $p=\frac{1}{2}$. Note that this purple curve reaches exactly the value $0$ when $\rho =0$. This is because $0$ is the expected payoff of player $\circ$ when $p=\frac{1}{2}$, and the entropic risk measure when $\rho =0$ – defined as the limit when $\rho$ approaches zero – corresponds exactly to the expected payoff. For higher values of $\rho$, the entropic risk measure is lower, since it corresponds to cases where player $\circ$ is more risk-averse and focuses on the event of reaching the vertex $t_4$; for symmetric reasons, for lower values of $\rho$, the values of entropic risk measure are higher.

Consider the perception of risk our agents may have in the previous example. If indeed such entities were modelling safety-critical agents where rewards below a certain threshold are unacceptable, such agents usually do not accept any strategy profile where they have any positive probability of such rewards, disregarding what the probabilities actually are, behaving as extremely pessimistic players – they assume that the worst of the cases that may happen. On the other hand, we may model certain external environment factors, or hackers of a system as an extremely optimistic player: they are happy with a small probability of success – they can repeat such attempts with a large number of trials – and seek to maximise the best payoff they may receive with positive probability.

We define the pessimistic risk measure of a random variable $X$ as the supremum of values $x$ such that $X$ almost surely takes values above $x$, or its essential infimum ($\mathrm{ess}\inf$); the optimistic risk measure is defined symmetrically (using $\mathrm{ess}\sup$). In Figure 1(b), the reader may have observed that all curves (except the thick blue and the thick red ones) converge to the value $-1$ when $\rho$ tends to $+\mathrm{\infty }$, and to the value $1$ when $\rho$ tends to $-\mathrm{\infty }$. These extreme cases correspond to the pessimistic and the optimistic risk measure, respectively, and we group them under the umbrella term extreme risk measure (XR).

Risk-sensitive equilibria are equilibria in multi-player games defined using a specified risk measure for each player, where no player can improve the risk measure of their payoff by deviating unilaterally from their strategy. Risk-sensitive equilibria takes into account the risk-sensitivities of a player to ensure that a player does not have an incentive to deviate. When the risk measure used is the entropic risk measure, we call such equilibria entropic risk-sensitive equilibria (ERSEs). When using our novel risk measure – the extreme risk measure – we refer to them as extreme risk-sensitive equilibria (XRSEs).

Risk-sensitive equilibria is particularly relevant in security contexts, where, for example, defenders may act conservatively while attackers behave opportunistically. Similarly, in autonomous systems, different components – such as safety controllers, efficiency optimizers, or compliance monitors – may operate under independent objectives and distinct risk profiles. We study ERSEs and XRSEs in a general enough framework where it might also be suitable to model a variety of situations including epidemic processes and probabilistic planning, where equilibria on graph games are considered. Incorporating risk measures while considering equilibria enables more realistic and nuanced models of such multi-agent interactions.

We consider simple quantitative multiplayer stochastic games played on graphs, that is, games in which the payoffs that the players receive depend on the terminal vertex that is reached – and in which an infinite play is associated to the the payoff zero for all players. In such games, we consider two questions in particular: the existence and the complexity of the constrained existence problem of both ERSEs and XRSEs.

In Section 3, we show that the constrained existence problem of ERSEs is undecidable, extending from the same problem for Nash equilibria in the work of Ummels and Wojtczak [31]. However, building on results on the two-player zero-sum case by Baier et al. [3], we find restrictions on strategies to recover decidability. Using known results about NEs, we also show that, when the rewards are all nonnegative, such an equilibrium always exists.

We define extreme risk measure (XR) as a novel risk measure to consider in multi-agent stochastic systems. In Section 4, we show that our new definition is robust, since it exactly captures the well-studied entropic risk measure when the risk parameters tend to $\pm \mathrm{\infty }$. Our main technical contributions are about the extreme risk measure, and extreme risk-sensitive equilibria (XRSEs). We show that the constrained existence problem of XRSEs is decidable and $\mathrm{𝖭𝖯}$-complete. The technical crux of proving $\mathrm{𝖭𝖯}$ membership lies in proving that if an XRSE satisfying the constraints exists, then there exists one that has finite memory, and a polynomial representation. Such a succinct representation then can therefore can be guessed and verified in polynomial time. We show that the problem remains $\mathrm{𝖭𝖯}$-complete when strategies are required to be stationary, pure, or positional. Finally, we show that if all players are extreme optimists, the problem is $\mathrm{𝖯𝖳𝖨𝖬𝖤}$-complete.

As we do for ERSEs, we also prove the existence of XRSEs in games with nonnegative rewards – and we show that there exists such a stationary equilibrium (where players use no memory and only randomness) that can be algorithmically constructed in polynomial time.

Hurwicz criterion is used in decision theory in situations where probabilities are unknown, and it assigns for a given random variable $X$ and a parameter $\alpha \in [0,1]$, the objective of maximising the quantity $\alpha \max (X)+(1-\alpha )\min (X)$ [17, 5], which generalises Wald’s maximin criterion [32] that constitutes to one extreme ($\alpha =0$) of Hurwicz criterion. Our definition of pessimistic risk measure corresponds to Wald’s maximin criterion when only outcomes of positive probability are considered, while our pessimistic risk measure corresponds to the other extreme of Hurwicz’s criterion ($\alpha =1$). Even classical notions such as considering the worst-case scenario obtained by abstracting any stochastic environment and treating it instead as an adversary can be seen as Wald’s maximin criterion applied on all outcomes, including probability $0$ events.

To the best of our knowledge, equilibria defined using any risk measure, and in particular, the entropic risk measure, have not been studied in multiplayer graph games. Two works have considered risk in the specific case of two-player zero-sum games on stochastic arenas. The first of these works is by Bruyère, Filiot, Randour, and Raskin [6] who have studied “beyond worst-case synthesis problem” which considers some measures that address risk averseness in a player in the context of synthesis. They consider “strongly risk-averse” strategies, those which avoid outcomes below a certain threshold and maximise the expected payoff, resulting in an entirely different risk measure. Baier, Chatterjee, Meggendorfer, and Piribauer have considered two-player zero-sum stochastic games with total-reward objectives (payoff is the sum of the rewards seen along the way), when one player is risk-sensitive and wants to optimise their entropic risk measure [3]. They show that computing optimal strategies can be done in $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ (when the base $e$ is replaced by an algebraic number). If the base of the exponent is $e$, computing optimal strategies is in $3\mathrm{𝖤𝖷𝖯𝖳𝖨𝖬𝖤}$ due to a recent result of Gallego-Hernández and Mansutti [13].

The two-player zero-sum case is a specific case of the constrained existence problem in two-agent systems, where the payoff functions of the two agents as well as their risk parameters are exactly the negation of each other. On the other hand, another subcase of the constrained existence problem of equilibria defined using the entropic risk measure is of course the constrained existence problem of NEs, when the risk parameters of all agents are set to $0$, which is known to be undecidable from the work of Ummels and Wojtczak [31].

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 }$, that is, a mapping $X:\mathrm{\Omega }\to ℝ$. We then write ${𝔼}^{\mathbb{P}}[𝕏]$, or simply $𝔼[X]$, for the expectation of $X$, when it is 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$. We write $\mathrm{𝖲𝗎𝗉𝗉}(d)$ for the support of the distribution $d$, that is, the set of elements $x\in S$ such that $d(x)>0$.

Given a set $\mathrm{\Omega }$ of outcomes, a risk measure over $\mathrm{\Omega }$ is a mapping $M$ which maps a probability measure $\mathbb{P}$ over $\mathrm{\Omega }$ and a random variable $X$ to a real value $M^{\mathbb{P}}[X]$. Sometimes, in the literature, risk measures are expected to have the following three properties: (1) they are normalised, i.e., we have $M^{\mathbb{P}}[0]=0$; (2) they are monotone, i.e., the pointwise inequality $X\le Y$ implies $M^{\mathbb{P}}[X]\le M^{\mathbb{P}}[Y]$; and (3) they are translative, i.e., $M^{\mathbb{P}}[X+c]=M^{\mathbb{P}}[X]+c$ for every constant $c$. In particular, the expectation of a random variable $𝔼$ satisfies those properties. We will not need those properties, and only state them here to remark that the risk measures we consider satisfy them. Note that translativity sometimes refers to the opposite of the definition given here, i.e., the property $M^{\mathbb{P}}[X+c]=M^{\mathbb{P}}[X]-c$ for every $c$. This is a matter of whether we use a risk measure or its negation.

A directed graph $(V,E)$ consists of a set of vertices $V$ and a set of ordered pair of vertices, called edges, $E$. In a directed graph $(V,E)$, for each vertex $u$, we write $E(u)$ to denote the set $E\cap (\{u\}\times V)$. 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) word $\pi ={\pi }_0{\pi }_1\mathrm{\dots }$ over the alphabet $V$ such that ${\pi }_n{\pi }_{n+1}\in E$ for every $n$ such that ${\pi }_n$ and ${\pi }_{n+1}$ exist. We write $\mathrm{𝖮𝖼𝖼}(\pi )$ for the set of vertices occurring along $\pi$, and $\mathrm{𝖨𝗇𝖿}(\pi )$ for those that occur infinitely often, if there are any. The prefix ${\pi }_0\mathrm{\dots }{\pi }_n$ is written as ${\pi }_{\le n}$ or , and the suffix ${\pi }_n{\pi }_{n+1}\mathrm{\dots }$ is written as ${\pi }_{\ge n}$ or ${\pi }_{>n-1}$. A finite path $\pi ={\pi }_0\mathrm{\dots }{\pi }_n$ is simple if every vertex occurs at most once along $\pi$. It is a cycle if its last vertex ${\pi }_n$ is such that ${\pi }_n{\pi }_0\in E$.

In a more general framework, payoffs can be assigned to all infinite paths. Here, we only focus on what is usually called simple quantitative games, i.e. games in which the underlying graph contains terminal vertices and the payoffs depend only on which terminal vertex is eventually reached. We thus extend the mapping $\mu$ to the set ${(V\setminus T)}^{\omega }\cup {(V\setminus T)}^{\ast }T$ by defining $\mu (v_1\mathrm{\dots }{v}_{k}t)=\mu (t)$, and $\mu (v_1{v}_2\mathrm{\dots })={(0)}_{i\in \mathrm{\Pi }}$ (if no terminal vertex is reached, everyone gets the payoff $0$). A game is Boolean if all payoffs belong to the set $\{0,1\}$.

An initialised game is a tuple $(𝒢,v_0)$, usually written ${𝒢}_{\upharpoonright v_0}$, where $v_0\in V$ is an initial vertex. In what follows, when the context is clear, we use the word game also for an initialised game. We often assume that we are given a game ${𝒢}_{\upharpoonright v_0}$ and implicitly use the same notations as in the definition above.

We call play a path in the underlying graph that is infinite, or whose last vertex is a terminal vertex. Other paths are called histories. We will then use the notations $\mathrm{𝖧𝗂𝗌𝗍}(𝒢)$ to denote finite paths in the graph of the game, and $\mathrm{𝖯𝗅𝖺𝗒𝗌}(𝒢)$ to denote both finite and infinite paths. For a history $h=h_0\mathrm{\dots }{h}_n$, we write $\mathrm{𝗅𝖺𝗌𝗍}(h)=h_n$. We will also write ${\mathrm{𝖧𝗂𝗌𝗍}}_i(𝒢)$ for the set of histories whose last vertex is controlled by player $i$. A history or play in an initialised game ${𝒢}_{\upharpoonright v_0}$ is a history or play in $𝒢$ whose first vertex is $v_0$.

In a game ${𝒢}_{\upharpoonright v_0}$, a strategy for player $i$ is a mapping ${\sigma }_i$ that maps each history $hu\in {\mathrm{𝖧𝗂𝗌𝗍}}_i({𝒢}_{\upharpoonright v_0})$ to a probability distribution over $E(u)$. The set of possible strategies for player $i$ in ${𝒢}_{\upharpoonright v_0}$ is written as ${\mathrm{𝖲𝗍𝗋𝖺𝗍}}_i({𝒢}_{\upharpoonright v_0})$. A path ${\pi }_0{\pi }_1\mathrm{\dots }$ (be it a history or a play) is compatible with the strategy ${\sigma }_i$ if for each $k$ such that ${\pi }_k\in V_i$, the probability that the strategy ${\sigma }_i$ proposes $h_{k+1}$ after history $h_{\le k}$ is positive, that is, we have ${\sigma }_i(h_{\le k})(h_{k+1})>0$. A strategy profile for a subset $P\subseteq \mathrm{\Pi }$ is a tuple ${({\sigma }_i)}_{i\in P}$. A strategy profile for the set $P$ of players is written ${\overline{\sigma }}_P$, or simply $\overline{\sigma }$ when $P=\mathrm{\Pi }$. We also write ${\overline{\sigma }}_{-i}$ for ${\overline{\sigma }}_P$ where $P=\mathrm{\Pi }\setminus \{i\}$. Similarly, we use $({\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$. We sometimes write $\overline{\sigma }(hv)$ to mean ${\sigma }_i(hv)$ where $i$ is the player controlling $v$, or $𝗉(v)$ when $v\in V_{\mathrm{?}}$.

For some history $h$, and a strategy ${\sigma }_i$, we define the strategy truncated to a history $h$, written ${\sigma }_{i\upharpoonright hv}$, as the strategy ${\sigma }_i^{\prime }:h^{\prime }\mapsto {\sigma }_i(h{h}^{\prime })$ in the game ${𝒢}_{\upharpoonright v}$.

A strategy profile ${\overline{\sigma }}_{-i}$ in the game ${𝒢}_{\upharpoonright v_0}$ defines an initialised Markov decision process ${𝒢}_{\upharpoonright v_0}({\overline{\sigma }}_{-i})$, where the vertices of the (infinite) underlying graph are the histories of ${𝒢}_{\upharpoonright v_0}$ and the edges are added from $hu$ to each history $huv$ iff $uv\in E$. Similarly, a strategy profile $\overline{\sigma }$ for $\mathrm{\Pi }$ defines an initialised Markov chain ${𝒢}_{\upharpoonright v_0}(\overline{\sigma })$. Thus, it also defines a probability measure ${\mathbb{P}}_{\overline{\sigma }}$ over plays – which turns the payoff functions ${\mu }_i$ into random variables.

We say that a strategy ${\sigma }_i$ is pure when for each history $hu$, there is a vertex $v$ such that ${\sigma }_i(hu)(v)=1$; then we often just write ${\sigma }_i(hu)=v$. We say that ${\sigma }_i$ is stationary when for every two histories $hu,h^{\prime }u\in {\mathrm{𝖧𝗂𝗌𝗍}}_i({𝒢}_{\upharpoonright v_0})$, we have ${\sigma }_i(hu)={\sigma }_i(h^{\prime }u)$. In that case, we sometimes assume that strategy ${\sigma }_i$ is defined in every game ${𝒢}_{\upharpoonright u}$ and simply write ${\sigma }_i(u)$ for ${\sigma }_i(hu)$. Finally, the strategy ${\sigma }_i$ is positional when it is pure and stationary. Those concepts are naturally generalised to strategy profiles.

A memory structure for player $i$ is a tuple $(S_i,s_0,{\delta }_i,{\nu }_i)$, where $S_i$ is a finite set of memory states, where $s_0\in S_i$ is an initial state, where ${\delta }_i$ is a memory-update mapping that maps each pair $(s,v)\in S_i\times V$ to a memory state $s^{\prime }$, and where ${\nu }_i$ is an output mapping that maps each pair $(s,v)\in S_i\times V_i$ to a distribution $d$ over $E(v)$. The memory-update mapping can be extended to a mapping ${\delta }_i^{\ast }:\mathrm{𝖧𝗂𝗌𝗍}({𝒢}_{\upharpoonright v_0})\to S_i$ with ${\delta }_i^{\ast }(\epsilon )=s_0$ and ${\delta }_i^{\ast }(hu)={\delta }_i({\delta }_i^{\ast }(h),u)$ for each history $hu$. The memory structure then induces a strategy ${\sigma }_i$ defined by ${\sigma }_i(hu)={\nu }_i({\delta }_i^{\ast }(h),u)$ for each history $hu\in {\mathrm{𝖧𝗂𝗌𝗍}}_i{𝒢}_{\upharpoonright v_0}$. A strategy induced by a memory structure is called finite-memory strategy. Note that stationary strategies are exactly the strategies that are induced by a memory structure with $|S_i|=1$.

We analogously define memory structures for a subset of players $P\subseteq \mathrm{\Pi }$, which also defines finite-memory strategy profiles. Note that if ${\overline{\sigma }}_P$ is a finite-memory strategy profile, then each ${\sigma }_i$ with $i\in P$ is finite-memory – the memory structure inducing that strategy is obtained by replacing $\nu$ by its restriction to $S\times V_i$. Conversely, if each ${\sigma }_i$ with $i\in P$ is finite-memory, then the strategy profile ${\overline{\sigma }}_P$ is finite-memory – a collective memory structure can be obtained by constructing the product of individual memory structures.

In multiplayer stochastic games, we wish to study generalisations of the classical Nash equilibria where the expectation is replaced by other risk measures. Such generalisations are called risk-sensitive equilibria [24]. When $M$ is a risk measure and $\overline{\sigma }$ is a strategy profile, we write $M(\overline{\sigma })$ for $M^{{\mathbb{P}}_{\overline{\sigma }}}$.

Nash equilibria in a game ${𝒢}_{\upharpoonright v_0}$ can then be defined as $\overline{M}$-risk-sensitive equilibria, where $M_i=𝔼$ for each player $i$. The following problem is the main focus throughout our paper.

We mainly consider the entropic risk measure and the extreme risk measure.

The constrained existence problem of Nash equilibria is undecidable [31, Theorem 4.9]. Since Nash equilibria are ERSEs with ${\rho }_i=0$ for each player $i$, our result follows. $◀$

We therefore briefly study cases where the class of strategies considered is restricted.

We end this section with this result: ERSEs are guaranteed to exist, if all rewards are nonnegative.

We conjecture that this result remains true when negative rewards are involved.

Our algorithm constructs a decreasing sequence $E=E_0,E_1,\mathrm{\dots }$ of sets of edges, and considers, for each $k$, the stationary strategy profile that randomises between all the outgoing edges in $E_k$ from all vertices. If this strategy profile is not an XRSE, there is a player $i$ who has a profitable deviation. We carefully identify edges used by player $i$, and remove them. This process always terminates, and the set obtained defines an XRSE. $◀$

Like in the case of ERSEs, we conjecture that existence, and even existence of a stationary XRSE, remain true in the general case. We remark that even for Nash equilibria, existence of an NE in such simple stochastic game is known only if all the rewards are nonnegative.