# Chess-Like Games May Have No Uniform Nash Equilibria Even in Mixed Strategies

Authors: Endre Boros; Vladimir Gurvich; Emre Yamangil
Journal: Game Theory
 (2013)

---

## Abstract

Recently, it was shown that Chess-like games may have no uniform (subgame perfect) Nash equilibria in pure positional strategies. Moreover, Nash equilibria may fail to exist already in two-person games in which all infinite plays are equivalent and ranked as the worst outcome by both players. In this paper, we extend this negative result further, providing examples that are uniform Nash equilibria free, even in mixed or independently mixed strategies. Additionally, in case of independently mixed strategies we consider two different definitions for effective payoff: the Markovian and the a priori realization.


---

## Body

## 1. Introduction

### 1.1. Nash-Solvability in Pure and Mixed Strategies: Main Results

There are two very important classes of the so-called uniformly Nash-solvable positional games with perfect information, for which a Nash equilibrium (NE) in pure stationary strategies, which are also independent of the initial position, exists for arbitrary payoffs. These two classes are the two-person zero-sum games and then-person acyclic games.However, when (directed) cycles are allowed and the game is not zero sum, then a positional game with perfect information may have no uniform NE in pure stationary strategies. This may occur already in the special case of two players with all cycles equivalent and ranked as the worst outcome by both players. Such an example was recently constructed in [1].Here we strengthen this result and show that for the same example no uniform NE exists even in mixed stationary strategies, not only in pure ones. Moreover, the same negative result holds for the so-called independently mixed strategies. In the latter case we consider two different definitions for the effective payoffs, based on Markovian and a priori realizations.In the rest of the introduction we give precise definitions and explain the above result in more details.Remark 1.
In contrast, for the case of a fixed initial position, Nash-solvability in pure positional strategies holds for the two-person case and remains an open problem forn>2; see [1] for more details; see also [2–20] for different cases of Nash-solvability in pure strategies.Furthermore, for a fixed initial position, the solvability in mixed strategies becomes trivial, due to the general result of Nash [21, 22]. Thus, our main example shows that Nash’s theorem cannot be extended for positional games to the case of uniform equilibria. It is shown for the following four types of positional strategies: pure, mixed, and independently mixed, where in the last case we consider two types of effective payoffs, defined by Markovian and a priori realizations.


### 1.2. Positional Game Structures

Given a finite directed graph (digraph)G=(V,E) in which loops and multiple arcs are allowed, a vertex v∈V is interpreted as a position and a directed edge (arc) e=(v,v′)∈E as a move from v to v′. A position of outdegree 0 (one with no moves) is called terminal. Let VT={a1,…,am} be the set of all terminal positions. Let us also introduce a set of n players I={1,…,n} and a partition D:V=V1∪⋯∪Vn∪VT, assuming that each player i∈I is in control of all positions in Vi.Aninitial position v0∈V may be fixed. The triplet (G,D,v0) or pair 𝒢=(G,D) is called a Chess-like positional game structure (or just a game structure, for short), initialized or noninitialized, respectively. By default, we assume that it is not initialized.Two examples of (noninitialized) game structures𝒢1 and 𝒢2 are given in Figure 1.Figure 1
Two Chess-like game structures𝒢1 and 𝒢2. In 𝒢1, there are 3 players controlling one position each (i.e., 𝒢1 is play-once), while in 𝒢2 there are only two players who alternate turns; hence, each of them controls 3 positions: v1,v3,v5 are controlled by player 1 and v2,v4,v6 by player 2. In each position vℓ, the corresponding player has only two options: (p) to proceed to vℓ+1 and (t) to terminate at aℓ, where ℓ∈{1,2,3} (v4=v1) in 𝒢1 and ℓ∈{1,…,6} (v7=v1) in 𝒢2. To save space, we show only symbols aℓ, while the corresponding vertex names are omitted.


### 1.3. Plays, Outcomes, Preferences, and Payoffs

Given an initialized positional game structure(G,D,v0), a play is defined as a directed path that begins in v0 and either ends in a terminal position a∈VT or is infinite. In this paper we assume that all infinite plays form one outcome a∞ (or c), in addition to the standard Terminal outcomes of VT. (In [5], this condition was referred to as AIPFOOT.)Autility (or payoff) function is a mapping u:I×A→ℝ, whose value u(i,a) is interpreted as a profit of the player i∈I={1,…,n} in case of the outcome a∈A={a1,…,am,a∞}.A payoff is calledzero-sum if ∑i∈I‍u(i,a)=0 for every a∈A. Two-person zero sum games are important. For example, the standard Chess and Backgammon are two-person zero-sum games in which every infinite play is a draw, u(1,a∞)=u(2,a∞)=0. It is easy to realize that u(i,a∞)=0 can be assumed for all players i∈I without any loss of generality.Another important class of payoffs is defined by the conditionu(i,a∞)<u(i,a) for all i∈I and a∈VT; in other words, the infinite outcome a∞ is ranked as the worst one by all players. Several possible motivations for this assumption are discussed in [4, 5].A quadruple(G,D,v0,u) and triplet (G,D,u) will be called a Chess-like game, initialized and noninitialized, respectively.Remark 2.
From the other side, the Chess-like games can be viewed as the transition-free deterministic stochastic games with perfect information; see, for example, [8–11].
In these games, every nonterminal position is controlled by a playeri∈I and the local reward r(i,e) is 0 for each player i∈I and move e, unless e=(v′,v) is a terminal move, that is, v∈VT. Obviously, in the considered case all infinite plays are equivalent since the effective payoff is 0 for every such play. Furthermore, obviously, a∞ is the worst outcome for a player i∈I if and only if r(i,e)>0 for every terminal move e.
If|I|=n=m=|A|=2, then the zero-sum Chess-like games turn into a subclass of the so-called simple stochastic games, which were introduced by Condon in [23].


### 1.4. Pure Positional Strategies

Given game structure𝒢=(G,D), a (pure positional) strategyxi of a player i∈I is a mapping xi:Vi→Ei that assigns to each position v∈Vi a move (v,v′) from this position.The concept of mixed strategies will be considered in Section1.10; till then only pure strategies are considered. Moreover, in this paper, we restrict the players to their positional (pure) strategies. In other words, the move (v,v′) of a player i∈I in a position v∈Vi depends only on the position v itself, not on the preceding positions or moves.LetXi be the set of all strategies of a player i∈I and X=∏i∈I‍Xi be the direct product of these sets. An element x={x1,…,xn}∈X is called a strategy profile or situation.


### 1.5. Normal Forms

A positional game structure can be represented in thenormal (or strategic) form.Let us begin with the initialized case. Given a game structure𝒢=(G,D,v0) and a strategy profile x∈X, a play p(x) is uniquely defined by the following rules: it begins in v0 and in each position v∈Vi proceeds with the arc (v,v′) determined by the strategy xi. Obviously, p(x) either ends in a terminal position a∈VT or p(x) is infinite. In the latter case p(x) is a lasso; that is, it consists of an initial part and a directed cycle (dicycle) repeated infinitely. This holds, because all players are restricted to their positional strategies. In either case, an outcome a=g(x)∈A={a1,…,am,a∞} is assigned to each strategy profile x∈X. Thus, a game form gv0:X→A is defined. It is called the normal form of the initialized positional game structure 𝒢.If the game structure𝒢=(G,D) is not initialized, then we repeat the above construction for every initial position v0∈V∖VT to obtain a play p=p(x,v0), outcome a=g(x,v0), and mapping g:X×(V∖VT)→A, which is the normal form of 𝒢 in this case. In general we have g(x,v0)=gv0(x). For the (noninitialized) game structures in Figure 1 their normal forms are given in Figures 2 and 3.Figure 2
The normal formg1 of the positional game structures 𝒢1 from Figure 1. Each player has only two strategies: to terminate (t) or proceed (p). Hence, g1 is represented by a 2×2×2 table, each entry of which contains 3 terminals corresponding to the 3 potential initial positions v1,v2,v3 of 𝒢1. The rows and columns are the strategies of the players 1 and 2, while two strategies of the player 3 are the left and right 2×2 subtables. The corresponding game (g1,u) has no uniform NE whenever a utility function u:I×A→ℝ satisfies the constraints U1 specified in the figure.Figure 3
The normal formg2 of the positional game structures 𝒢2 from Figure 1. There are two players controlling 3 positions each. Again, in every position there are only two options: to terminate (t) or proceed (p). Hence, in 𝒢2, each player has 8 strategies, which are naturally coded by the 3-letter words in the alphabet {t,p}. Respectively, g2 is represented by the 8×8 table, each entry of which contains 6 terminals corresponding to the 6 (nonterminal) potential initial positions v1,…,v6 of 𝒢2. Again, players 1 and 2 control the rows and columns, respectively. The corresponding game (g1,u) has no uniform NE whenever a utility function u:I×A→ℝ satisfies the constraints U2 specified under the table. Indeed, a (unique) uniformly best response of the player 1 (resp. 2) to each strategy of 2 (resp. 1) is shown by the white discs (resp. black squares). Since the obtained two sets are disjoint, no uniform NE exists in (g1,u).Given also a payoffu:I×A→ℝ, the pairs (gv0,u) and (g,u) define the games in the normal form, for the above two cases.Of course, these games can be also represented by the corresponding real-valued mappings:(1)fv0:I×X⟶ℝ,f:I×X×(VVT)⟶ℝ,
where fv0(i,x)=f(i,x,v0)=u(i,gv0(x))=u(i,g(x,v0)) for all i∈I, x∈X, v0∈V∖VT.Remark 3.
Yet, it seems convenient to separate the game fromg and utility function u.
By this approach,g “takes responsibility for structural properties” of the game (g,u), that is, the properties that hold for any u.


### 1.6. Nash Equilibria in Pure Strategies

The concept of Nash equilibria is defined standardly [21, 22] for the normal form games.First, let us consider the initialized case. Givengv0:X→A and u:I×A→ℝ, a situation x∈X is called a Nash equilibrium (NE) in the normal form game (gv0,u) if fv0(i,x)≥fv0(i,x′) for each player i∈I and every strategy profile x′∈X that can differ from x only in the ith component. In other words, no player i∈I can profit by choosing a new strategy if all opponents keep their old strategies.In the noninitialized case, the similar property is required for eachv0∈V∖VT. Given a payoff f:I×X×(V∖VT)→ℝ, a strategy profile x∈X is called a uniform NE if f(i,x,v0)≥f(i,x′,v0) for each i∈I, every x′ defined as above, and for all v0∈V∖VT, too.Remark 4.
In the literature, the last concept is frequently called a subgame perfect NE rather than a uniform NE. This name is justified when the digraphG=(V,E) is acyclic and each vertex v∈V can be reached from v0. Indeed, in this case (G,D,v,u) is a subgame of (G,D,v0,u) for each v∈V. However, if G has a dicycle then any two its vertices v′ and v′′ can be reached one from the other; that is, (G,D,v′,u) is a subgame of (G,D,v′′,u) and vice versa. Thus, the name uniform (or ergodic) NE seems more accurate.


### 1.7. Uniformly Best Responses

Again, let us start with the initialized case. Given the normal formfv0:I×X→ℝ of an initialized Chess-like game, a player i∈I, and a pair of strategy profiles x,x′ such that x′ may differ from x only in the ith component, we say that x′improvesx (for the player i) if fv0(i,x)<fv0(i,x′). Let us underline that the inequality is strict. Furthermore, by this definition, a situation x∈X is a NE if and only if it can be improved by no player i∈I; in other words, any sequence of improvements either can be extended, or terminates in an NE.Given a playeri∈I and situation x=(xi∣i∈I), a strategy xi*∈Xi is called a best response (BR) of i in x if fv0(i,x*)≥fv0(i,x′) for any x′, where x* and x′ are both obtained from x by replacement of its ith component xi by xi* and xi′, respectively. A BR xi* is not necessarily unique but the corresponding best achievable value fv0(i,x*) is, of course, unique. Moreover, somewhat surprisingly, such best values can be achieved by a BR xi* simultaneously for all initial positions v0∈V∖VT. (See, e.g., [1, 4–6], of course, this result is well known in much more general probabilistic setting; see, e.g., textbooks [24–26].)Theorem 5.
Letf:I×X×(V∖VT)→ℝ be the normal form of a (noninitialized) Chess-like game (G,D,u). Given a player i∈I and a situation x∈X, there is a (pure positional) strategy xi*∈Xi which is a BR of i in x for all initial positions v0∈V∖VT simultaneously.We will call such a strategyxi* a uniformly BR of the player i in the situation x. Obviously, the nonstrict inequality fv(i,x)≤fv(i,x*) holds for each position v∈V. We will say that xi* improves x if this inequality is strict, fv0(i,x)<fv0(i,x*), for at least one v0∈V. This statement will serve as the definition of a uniform improvement for the noninitialized case. Let us remark that, by this definition, a situation x∈X is a uniform NE if and only if x can be uniformly improved by no player i∈I; in other words, any sequence of uniform improvements either can be extended or terminates in a uniform NE.For completeness, let us repeat here the simple proof of Theorem5 suggested in [1].Given a noninitialized Chess-like game𝒢=(G,D,u), a player i∈I, and a strategy profile x∈X, in every position v∈V∖(Vi∪VT) let us fix a move (v,v′) in accordance with x and delete all other moves. Then, let us order A according to the preference ui=u(i,*). Let a1∈A be a best outcome. (Note that there might be several such outcomes and also that a1=c might hold.) Let V1 denote the set of positions from which player i can reach a1 (in particular, a1∈V1). Let us fix corresponding moves in V1∩Vi. Obviously, there is no move to a1 from V∖V1. Moreover, if a1=c, then player i cannot reach a dicycle beginning from V∖V1; in particular, the induced digraph G1=G[V∖V1] contains no dicycle.Then, let us consider an outcomea2 that is the best for i in A, except maybe a1, and repeat the same arguments as above for G1 and a2, and so forth. This procedure will result in a uniformly BR xi* of i in x since the chosen moves of i are optimal independently of v0.


### 1.8. Two Open Problems Related to Nash-Solvability of Initialized Chess-Like Game Structures

Given an initialized game structure𝒢=(G,D,v0), it is an open question whether an NE (in pure positional strategies) exists for every utility function u. In [4], the problem was raised and solved in the affirmative for two special cases: |I|≤2 or |A|≤3. The last result was strengthened to |A|≤4 in [7]. More details can be found in [1] and in the last section of [6].In general the above problem is still open even if we assume thatc is the worst outcome for all players.Yet, if we additionally assume that𝒢 is play-once (i.e., |Vi|=1 for each i∈I), then the answer is positive [4]. However, in the next subsection we will show that it becomes negative if we ask for the existence of a uniform NE rather than an initialized one.


### 1.9. Chess-Like Games with a Unique Dicycle and without Uniform Nash Equilibria in Pure Positional Strategies

Let us consider two noninitialized Chess-like positional game structures𝒢1 and 𝒢2 given in Figure 1. For j=1,2, the corresponding digraph Gj=(Vj,Ej) consists of a unique dicycle Cj of length 3j and a matching connecting each vertex vℓj of Cj to a terminal aℓj, where ℓ=1,…,3j and j=1,2. The digraph G2 is bipartite; respectively, 𝒢2 is a two-person game structures in which two players take turns; in other words, players 1 and 2 control positions v1,v3,v5 and v2,v4,v6, respectively. In contrast, 𝒢1 is a play-once three-person game structure, that is, each player controls a unique position. In every nonterminal position vℓj there are only two moves: one of them (t) immediately terminates in aℓj, while the other one (p) proceeds to vℓ+1j; by convention, we assume 3j+1=1.Remark 6.
In Figure1, the symbols aℓj for the terminal positions are shown but vℓj for the corresponding positions of the dicycle are skipped; moreover, in Figures 1–3, we omit the superscript j in aℓj, for simplicity and to save space.Thus, in𝒢1 each player has two strategies coded by the letters t and p, while in 𝒢2 each player has 8 strategies coded by the 3-letter words in the alphabet {t,p}. For example, the strategy (tpt) of player 2 in 𝒢2 requires to proceed to v52 from v42 and to terminate in a22 from v22 and in a62 from v62.The corresponding normal game formsg1 and g2 of size 2×2×2 and 8×8 are shown in Figures 2 and 3, respectively. Since both game structures are noninitialized, each situation is a set of 2 and 6 terminals, respectively. These terminals correspond to the nonterminal positions of 𝒢1 and 𝒢2, each of which can serve as an initial position.A uniform NE free example for𝒢1 was suggested in [4]; see also [1, 8]. Let us consider a family U1 of the utility functions defined by the following constraints:
(2)u(1,a2)>u(1,a1)>u(1,a3)>u(1,c),u(2,a3)>u(2,a2)>u(2,a1)>u(2,c),u(3,a1)>u(3,a3)>u(3,a2)>u(3,c).In other words, for each playeri∈I={1,2,3} to terminate is an average outcome; it is better (worse) when the next (previous) player terminates; finally, if nobody does, then the dicycle c appears, which is the worst outcome for all. The considered game has an improvement cycle of length 6, which is shown in Figure 2. Indeed, let player 1 terminates at a1, while 2 and 3 proceed. The corresponding situation (a1,a1,a1) can be improved by 2 to (a1,a2,a1), which in its turn can be improved by 1 to (a2,a2,a2). Repeating the similar procedure two times more we obtain the improvement cycle shown in Figure 2.There are two more situations, which result in(a1,a2,a3) and (c,c,c). They appear when all three players terminate or proceed simultaneously. Yet, none of these two situations is an NE either. Moreover, each of them can be improved by every player i∈I={1,2,3}.Thus, the following negative result holds, which we recall without proof from [4]; see also [1].Theorem 7.
Game(𝒢1,u) has no uniform NE in pure strategies whenever u∈U1.We note that each player has positive payoffs. This is without loss of generality as we can shift the payoffs by a positive constant without changing the game.A similar two-person uniform NE-free example was suggested in [1], for 𝒢2. Let us consider a family U2 of the utility functions defined by the following constraints:
(3)u(1,a6)>u(1,a5)>u(1,a2)>u(1,a1)>u(1,a3)>u(1,a4)>u(1,c),u(2,a3)>u(2,a2)>u(2,a6)>u(2,a4)>u(2,a5)>u(2,c),u(2,a6)>u(2,a1)>u(2,c).We claim that the Chess-like game(𝒢2,u) has no uniform NE whenever u∈U2.Let us remark that|U2|=3 and that c is the worst outcome for both players for all u∈U2. To verify this, let us consider the normal form g2 in Figure 3. By Theorem 5, there is a uniformly BR of player 2 to each strategy of player 1 and vice versa. It is not difficult to check that the obtained two sets of the BRs (which are denoted by the white discs and black squares in Figure 3) are disjoint. Hence, there is no uniform NE. Furthermore, it is not difficult to verify that the obtained 16 situations induce an improvement cycle of length 10 and two improvement paths of lengths 2 and 4 that end in this cycle.Theorem 8 (see [1]).
Game(𝒢2,u) has no uniform NE in pure strategies whenever u∈U2.The goal of the present paper is to demonstrate that the above two game structures may have no uniform NE not only in pure but also in mixed strategies. Let us note that by Nash’s theorem [21, 22] NE in mixed strategies exist in any initialized game structure. Yet, this result cannot be extended to the noninitialized game structure and uniform NE. In this research we are motivated by the results of [8, 11].


### 1.10. Mixed and Independently Mixed Strategies

Standardly, amixed strategyyi of a player i∈I is defined as a probabilistic distribution over the set Xi of his pure strategies. Furthermore, yi is called an independently mixed strategy if i randomizes in his positions v∈Vi independently. We will denote by Yi and by Zi⊆Yi the sets of mixed and independently mixed strategies of player i∈I, respectively.Remark 9.
Let us recall that the players are restricted to their positional strategies and let us also note that the latter concept is closely related to the so-called behavioral strategies introduced by Kuhn [19, 20]. Although Kuhn restricted himself to trees, yet his construction can be extended to directed graphs, too.Let us recall that a game structure is called play-once if each player is in control of a unique position. For example,𝒢1 is play-once. Obviously, the classes of mixed and independently mixed strategies coincide for a play-once game structure. However, for 𝒢2 these two notion differ. Each player i∈I={1,2} controls 3 positions and has 8 pure strategies. Hence, the set of mixed strategies Yi is of dimension 7, while the set Zi⊆Yi of the independently mixed strategies is only 3-dimensional.


## 1.1. Nash-Solvability in Pure and Mixed Strategies: Main Results

There are two very important classes of the so-called uniformly Nash-solvable positional games with perfect information, for which a Nash equilibrium (NE) in pure stationary strategies, which are also independent of the initial position, exists for arbitrary payoffs. These two classes are the two-person zero-sum games and then-person acyclic games.However, when (directed) cycles are allowed and the game is not zero sum, then a positional game with perfect information may have no uniform NE in pure stationary strategies. This may occur already in the special case of two players with all cycles equivalent and ranked as the worst outcome by both players. Such an example was recently constructed in [1].Here we strengthen this result and show that for the same example no uniform NE exists even in mixed stationary strategies, not only in pure ones. Moreover, the same negative result holds for the so-called independently mixed strategies. In the latter case we consider two different definitions for the effective payoffs, based on Markovian and a priori realizations.In the rest of the introduction we give precise definitions and explain the above result in more details.Remark 1.
In contrast, for the case of a fixed initial position, Nash-solvability in pure positional strategies holds for the two-person case and remains an open problem forn>2; see [1] for more details; see also [2–20] for different cases of Nash-solvability in pure strategies.Furthermore, for a fixed initial position, the solvability in mixed strategies becomes trivial, due to the general result of Nash [21, 22]. Thus, our main example shows that Nash’s theorem cannot be extended for positional games to the case of uniform equilibria. It is shown for the following four types of positional strategies: pure, mixed, and independently mixed, where in the last case we consider two types of effective payoffs, defined by Markovian and a priori realizations.


## 1.2. Positional Game Structures

Given a finite directed graph (digraph)G=(V,E) in which loops and multiple arcs are allowed, a vertex v∈V is interpreted as a position and a directed edge (arc) e=(v,v′)∈E as a move from v to v′. A position of outdegree 0 (one with no moves) is called terminal. Let VT={a1,…,am} be the set of all terminal positions. Let us also introduce a set of n players I={1,…,n} and a partition D:V=V1∪⋯∪Vn∪VT, assuming that each player i∈I is in control of all positions in Vi.Aninitial position v0∈V may be fixed. The triplet (G,D,v0) or pair 𝒢=(G,D) is called a Chess-like positional game structure (or just a game structure, for short), initialized or noninitialized, respectively. By default, we assume that it is not initialized.Two examples of (noninitialized) game structures𝒢1 and 𝒢2 are given in Figure 1.Figure 1
Two Chess-like game structures𝒢1 and 𝒢2. In 𝒢1, there are 3 players controlling one position each (i.e., 𝒢1 is play-once), while in 𝒢2 there are only two players who alternate turns; hence, each of them controls 3 positions: v1,v3,v5 are controlled by player 1 and v2,v4,v6 by player 2. In each position vℓ, the corresponding player has only two options: (p) to proceed to vℓ+1 and (t) to terminate at aℓ, where ℓ∈{1,2,3} (v4=v1) in 𝒢1 and ℓ∈{1,…,6} (v7=v1) in 𝒢2. To save space, we show only symbols aℓ, while the corresponding vertex names are omitted.


## 1.3. Plays, Outcomes, Preferences, and Payoffs

Given an initialized positional game structure(G,D,v0), a play is defined as a directed path that begins in v0 and either ends in a terminal position a∈VT or is infinite. In this paper we assume that all infinite plays form one outcome a∞ (or c), in addition to the standard Terminal outcomes of VT. (In [5], this condition was referred to as AIPFOOT.)Autility (or payoff) function is a mapping u:I×A→ℝ, whose value u(i,a) is interpreted as a profit of the player i∈I={1,…,n} in case of the outcome a∈A={a1,…,am,a∞}.A payoff is calledzero-sum if ∑i∈I‍u(i,a)=0 for every a∈A. Two-person zero sum games are important. For example, the standard Chess and Backgammon are two-person zero-sum games in which every infinite play is a draw, u(1,a∞)=u(2,a∞)=0. It is easy to realize that u(i,a∞)=0 can be assumed for all players i∈I without any loss of generality.Another important class of payoffs is defined by the conditionu(i,a∞)<u(i,a) for all i∈I and a∈VT; in other words, the infinite outcome a∞ is ranked as the worst one by all players. Several possible motivations for this assumption are discussed in [4, 5].A quadruple(G,D,v0,u) and triplet (G,D,u) will be called a Chess-like game, initialized and noninitialized, respectively.Remark 2.
From the other side, the Chess-like games can be viewed as the transition-free deterministic stochastic games with perfect information; see, for example, [8–11].
In these games, every nonterminal position is controlled by a playeri∈I and the local reward r(i,e) is 0 for each player i∈I and move e, unless e=(v′,v) is a terminal move, that is, v∈VT. Obviously, in the considered case all infinite plays are equivalent since the effective payoff is 0 for every such play. Furthermore, obviously, a∞ is the worst outcome for a player i∈I if and only if r(i,e)>0 for every terminal move e.
If|I|=n=m=|A|=2, then the zero-sum Chess-like games turn into a subclass of the so-called simple stochastic games, which were introduced by Condon in [23].


## 1.4. Pure Positional Strategies

Given game structure𝒢=(G,D), a (pure positional) strategyxi of a player i∈I is a mapping xi:Vi→Ei that assigns to each position v∈Vi a move (v,v′) from this position.The concept of mixed strategies will be considered in Section1.10; till then only pure strategies are considered. Moreover, in this paper, we restrict the players to their positional (pure) strategies. In other words, the move (v,v′) of a player i∈I in a position v∈Vi depends only on the position v itself, not on the preceding positions or moves.LetXi be the set of all strategies of a player i∈I and X=∏i∈I‍Xi be the direct product of these sets. An element x={x1,…,xn}∈X is called a strategy profile or situation.


## 1.5. Normal Forms

A positional game structure can be represented in thenormal (or strategic) form.Let us begin with the initialized case. Given a game structure𝒢=(G,D,v0) and a strategy profile x∈X, a play p(x) is uniquely defined by the following rules: it begins in v0 and in each position v∈Vi proceeds with the arc (v,v′) determined by the strategy xi. Obviously, p(x) either ends in a terminal position a∈VT or p(x) is infinite. In the latter case p(x) is a lasso; that is, it consists of an initial part and a directed cycle (dicycle) repeated infinitely. This holds, because all players are restricted to their positional strategies. In either case, an outcome a=g(x)∈A={a1,…,am,a∞} is assigned to each strategy profile x∈X. Thus, a game form gv0:X→A is defined. It is called the normal form of the initialized positional game structure 𝒢.If the game structure𝒢=(G,D) is not initialized, then we repeat the above construction for every initial position v0∈V∖VT to obtain a play p=p(x,v0), outcome a=g(x,v0), and mapping g:X×(V∖VT)→A, which is the normal form of 𝒢 in this case. In general we have g(x,v0)=gv0(x). For the (noninitialized) game structures in Figure 1 their normal forms are given in Figures 2 and 3.Figure 2
The normal formg1 of the positional game structures 𝒢1 from Figure 1. Each player has only two strategies: to terminate (t) or proceed (p). Hence, g1 is represented by a 2×2×2 table, each entry of which contains 3 terminals corresponding to the 3 potential initial positions v1,v2,v3 of 𝒢1. The rows and columns are the strategies of the players 1 and 2, while two strategies of the player 3 are the left and right 2×2 subtables. The corresponding game (g1,u) has no uniform NE whenever a utility function u:I×A→ℝ satisfies the constraints U1 specified in the figure.Figure 3
The normal formg2 of the positional game structures 𝒢2 from Figure 1. There are two players controlling 3 positions each. Again, in every position there are only two options: to terminate (t) or proceed (p). Hence, in 𝒢2, each player has 8 strategies, which are naturally coded by the 3-letter words in the alphabet {t,p}. Respectively, g2 is represented by the 8×8 table, each entry of which contains 6 terminals corresponding to the 6 (nonterminal) potential initial positions v1,…,v6 of 𝒢2. Again, players 1 and 2 control the rows and columns, respectively. The corresponding game (g1,u) has no uniform NE whenever a utility function u:I×A→ℝ satisfies the constraints U2 specified under the table. Indeed, a (unique) uniformly best response of the player 1 (resp. 2) to each strategy of 2 (resp. 1) is shown by the white discs (resp. black squares). Since the obtained two sets are disjoint, no uniform NE exists in (g1,u).Given also a payoffu:I×A→ℝ, the pairs (gv0,u) and (g,u) define the games in the normal form, for the above two cases.Of course, these games can be also represented by the corresponding real-valued mappings:(1)fv0:I×X⟶ℝ,f:I×X×(VVT)⟶ℝ,
where fv0(i,x)=f(i,x,v0)=u(i,gv0(x))=u(i,g(x,v0)) for all i∈I, x∈X, v0∈V∖VT.Remark 3.
Yet, it seems convenient to separate the game fromg and utility function u.
By this approach,g “takes responsibility for structural properties” of the game (g,u), that is, the properties that hold for any u.


## 1.6. Nash Equilibria in Pure Strategies

The concept of Nash equilibria is defined standardly [21, 22] for the normal form games.First, let us consider the initialized case. Givengv0:X→A and u:I×A→ℝ, a situation x∈X is called a Nash equilibrium (NE) in the normal form game (gv0,u) if fv0(i,x)≥fv0(i,x′) for each player i∈I and every strategy profile x′∈X that can differ from x only in the ith component. In other words, no player i∈I can profit by choosing a new strategy if all opponents keep their old strategies.In the noninitialized case, the similar property is required for eachv0∈V∖VT. Given a payoff f:I×X×(V∖VT)→ℝ, a strategy profile x∈X is called a uniform NE if f(i,x,v0)≥f(i,x′,v0) for each i∈I, every x′ defined as above, and for all v0∈V∖VT, too.Remark 4.
In the literature, the last concept is frequently called a subgame perfect NE rather than a uniform NE. This name is justified when the digraphG=(V,E) is acyclic and each vertex v∈V can be reached from v0. Indeed, in this case (G,D,v,u) is a subgame of (G,D,v0,u) for each v∈V. However, if G has a dicycle then any two its vertices v′ and v′′ can be reached one from the other; that is, (G,D,v′,u) is a subgame of (G,D,v′′,u) and vice versa. Thus, the name uniform (or ergodic) NE seems more accurate.


## 1.7. Uniformly Best Responses

Again, let us start with the initialized case. Given the normal formfv0:I×X→ℝ of an initialized Chess-like game, a player i∈I, and a pair of strategy profiles x,x′ such that x′ may differ from x only in the ith component, we say that x′improvesx (for the player i) if fv0(i,x)<fv0(i,x′). Let us underline that the inequality is strict. Furthermore, by this definition, a situation x∈X is a NE if and only if it can be improved by no player i∈I; in other words, any sequence of improvements either can be extended, or terminates in an NE.Given a playeri∈I and situation x=(xi∣i∈I), a strategy xi*∈Xi is called a best response (BR) of i in x if fv0(i,x*)≥fv0(i,x′) for any x′, where x* and x′ are both obtained from x by replacement of its ith component xi by xi* and xi′, respectively. A BR xi* is not necessarily unique but the corresponding best achievable value fv0(i,x*) is, of course, unique. Moreover, somewhat surprisingly, such best values can be achieved by a BR xi* simultaneously for all initial positions v0∈V∖VT. (See, e.g., [1, 4–6], of course, this result is well known in much more general probabilistic setting; see, e.g., textbooks [24–26].)Theorem 5.
Letf:I×X×(V∖VT)→ℝ be the normal form of a (noninitialized) Chess-like game (G,D,u). Given a player i∈I and a situation x∈X, there is a (pure positional) strategy xi*∈Xi which is a BR of i in x for all initial positions v0∈V∖VT simultaneously.We will call such a strategyxi* a uniformly BR of the player i in the situation x. Obviously, the nonstrict inequality fv(i,x)≤fv(i,x*) holds for each position v∈V. We will say that xi* improves x if this inequality is strict, fv0(i,x)<fv0(i,x*), for at least one v0∈V. This statement will serve as the definition of a uniform improvement for the noninitialized case. Let us remark that, by this definition, a situation x∈X is a uniform NE if and only if x can be uniformly improved by no player i∈I; in other words, any sequence of uniform improvements either can be extended or terminates in a uniform NE.For completeness, let us repeat here the simple proof of Theorem5 suggested in [1].Given a noninitialized Chess-like game𝒢=(G,D,u), a player i∈I, and a strategy profile x∈X, in every position v∈V∖(Vi∪VT) let us fix a move (v,v′) in accordance with x and delete all other moves. Then, let us order A according to the preference ui=u(i,*). Let a1∈A be a best outcome. (Note that there might be several such outcomes and also that a1=c might hold.) Let V1 denote the set of positions from which player i can reach a1 (in particular, a1∈V1). Let us fix corresponding moves in V1∩Vi. Obviously, there is no move to a1 from V∖V1. Moreover, if a1=c, then player i cannot reach a dicycle beginning from V∖V1; in particular, the induced digraph G1=G[V∖V1] contains no dicycle.Then, let us consider an outcomea2 that is the best for i in A, except maybe a1, and repeat the same arguments as above for G1 and a2, and so forth. This procedure will result in a uniformly BR xi* of i in x since the chosen moves of i are optimal independently of v0.


## 1.8. Two Open Problems Related to Nash-Solvability of Initialized Chess-Like Game Structures

Given an initialized game structure𝒢=(G,D,v0), it is an open question whether an NE (in pure positional strategies) exists for every utility function u. In [4], the problem was raised and solved in the affirmative for two special cases: |I|≤2 or |A|≤3. The last result was strengthened to |A|≤4 in [7]. More details can be found in [1] and in the last section of [6].In general the above problem is still open even if we assume thatc is the worst outcome for all players.Yet, if we additionally assume that𝒢 is play-once (i.e., |Vi|=1 for each i∈I), then the answer is positive [4]. However, in the next subsection we will show that it becomes negative if we ask for the existence of a uniform NE rather than an initialized one.


## 1.9. Chess-Like Games with a Unique Dicycle and without Uniform Nash Equilibria in Pure Positional Strategies

Let us consider two noninitialized Chess-like positional game structures𝒢1 and 𝒢2 given in Figure 1. For j=1,2, the corresponding digraph Gj=(Vj,Ej) consists of a unique dicycle Cj of length 3j and a matching connecting each vertex vℓj of Cj to a terminal aℓj, where ℓ=1,…,3j and j=1,2. The digraph G2 is bipartite; respectively, 𝒢2 is a two-person game structures in which two players take turns; in other words, players 1 and 2 control positions v1,v3,v5 and v2,v4,v6, respectively. In contrast, 𝒢1 is a play-once three-person game structure, that is, each player controls a unique position. In every nonterminal position vℓj there are only two moves: one of them (t) immediately terminates in aℓj, while the other one (p) proceeds to vℓ+1j; by convention, we assume 3j+1=1.Remark 6.
In Figure1, the symbols aℓj for the terminal positions are shown but vℓj for the corresponding positions of the dicycle are skipped; moreover, in Figures 1–3, we omit the superscript j in aℓj, for simplicity and to save space.Thus, in𝒢1 each player has two strategies coded by the letters t and p, while in 𝒢2 each player has 8 strategies coded by the 3-letter words in the alphabet {t,p}. For example, the strategy (tpt) of player 2 in 𝒢2 requires to proceed to v52 from v42 and to terminate in a22 from v22 and in a62 from v62.The corresponding normal game formsg1 and g2 of size 2×2×2 and 8×8 are shown in Figures 2 and 3, respectively. Since both game structures are noninitialized, each situation is a set of 2 and 6 terminals, respectively. These terminals correspond to the nonterminal positions of 𝒢1 and 𝒢2, each of which can serve as an initial position.A uniform NE free example for𝒢1 was suggested in [4]; see also [1, 8]. Let us consider a family U1 of the utility functions defined by the following constraints:
(2)u(1,a2)>u(1,a1)>u(1,a3)>u(1,c),u(2,a3)>u(2,a2)>u(2,a1)>u(2,c),u(3,a1)>u(3,a3)>u(3,a2)>u(3,c).In other words, for each playeri∈I={1,2,3} to terminate is an average outcome; it is better (worse) when the next (previous) player terminates; finally, if nobody does, then the dicycle c appears, which is the worst outcome for all. The considered game has an improvement cycle of length 6, which is shown in Figure 2. Indeed, let player 1 terminates at a1, while 2 and 3 proceed. The corresponding situation (a1,a1,a1) can be improved by 2 to (a1,a2,a1), which in its turn can be improved by 1 to (a2,a2,a2). Repeating the similar procedure two times more we obtain the improvement cycle shown in Figure 2.There are two more situations, which result in(a1,a2,a3) and (c,c,c). They appear when all three players terminate or proceed simultaneously. Yet, none of these two situations is an NE either. Moreover, each of them can be improved by every player i∈I={1,2,3}.Thus, the following negative result holds, which we recall without proof from [4]; see also [1].Theorem 7.
Game(𝒢1,u) has no uniform NE in pure strategies whenever u∈U1.We note that each player has positive payoffs. This is without loss of generality as we can shift the payoffs by a positive constant without changing the game.A similar two-person uniform NE-free example was suggested in [1], for 𝒢2. Let us consider a family U2 of the utility functions defined by the following constraints:
(3)u(1,a6)>u(1,a5)>u(1,a2)>u(1,a1)>u(1,a3)>u(1,a4)>u(1,c),u(2,a3)>u(2,a2)>u(2,a6)>u(2,a4)>u(2,a5)>u(2,c),u(2,a6)>u(2,a1)>u(2,c).We claim that the Chess-like game(𝒢2,u) has no uniform NE whenever u∈U2.Let us remark that|U2|=3 and that c is the worst outcome for both players for all u∈U2. To verify this, let us consider the normal form g2 in Figure 3. By Theorem 5, there is a uniformly BR of player 2 to each strategy of player 1 and vice versa. It is not difficult to check that the obtained two sets of the BRs (which are denoted by the white discs and black squares in Figure 3) are disjoint. Hence, there is no uniform NE. Furthermore, it is not difficult to verify that the obtained 16 situations induce an improvement cycle of length 10 and two improvement paths of lengths 2 and 4 that end in this cycle.Theorem 8 (see [1]).
Game(𝒢2,u) has no uniform NE in pure strategies whenever u∈U2.The goal of the present paper is to demonstrate that the above two game structures may have no uniform NE not only in pure but also in mixed strategies. Let us note that by Nash’s theorem [21, 22] NE in mixed strategies exist in any initialized game structure. Yet, this result cannot be extended to the noninitialized game structure and uniform NE. In this research we are motivated by the results of [8, 11].


## 1.10. Mixed and Independently Mixed Strategies

Standardly, amixed strategyyi of a player i∈I is defined as a probabilistic distribution over the set Xi of his pure strategies. Furthermore, yi is called an independently mixed strategy if i randomizes in his positions v∈Vi independently. We will denote by Yi and by Zi⊆Yi the sets of mixed and independently mixed strategies of player i∈I, respectively.Remark 9.
Let us recall that the players are restricted to their positional strategies and let us also note that the latter concept is closely related to the so-called behavioral strategies introduced by Kuhn [19, 20]. Although Kuhn restricted himself to trees, yet his construction can be extended to directed graphs, too.Let us recall that a game structure is called play-once if each player is in control of a unique position. For example,𝒢1 is play-once. Obviously, the classes of mixed and independently mixed strategies coincide for a play-once game structure. However, for 𝒢2 these two notion differ. Each player i∈I={1,2} controls 3 positions and has 8 pure strategies. Hence, the set of mixed strategies Yi is of dimension 7, while the set Zi⊆Yi of the independently mixed strategies is only 3-dimensional.


## 2. Markovian and A Priori Realizations

For the independently mixed strategies we will consider two different options.For every playeri∈I let us consider a probability distribution Pvi for all positions v∈Vi, which assigns a probability p(v,v′) to each move (v,v′) from v∈Vi, standardly assuming
(4)0≤p(v,v′)≤1,∑v′∈V‍p(v,v′)=1,0ppp(v,v′)=0whenever(v,v′)∉E.Now, the limit distributions of the terminalsA={a1,…,am,a∞} can be defined in two ways, which we will be referred to as the Markovian and a priori realizations.The first approach is classical; the limit distribution can be found by solving am×m system of linear equations; see, for example, [27] and also [26].For example, let us consider𝒢1 and let pj be the probability to proceed in vj for j=1,2,3. If p1=p2=p3=1, then, obviously, the play will cycle with probability 1 resulting in the limit distribution (0,0,0,1) for (a1,a2,a3,c). Otherwise, assuming that v1 is the initial position, we obtain the limit distribution:
(5)(1-p11-p1p2p3,p1(1-p2)1-p1p2p3,p1p2(1-p3)1-p1p2p3,0).Indeed, positionsv1,v2,v3 are transient and the probability of cycling forever is 0 whenever p1p2p3<1. Obviously, the sum of the above four probabilities is 1.The Markovian approach assumes that fort=0,1,… the move e(t)=(v(t),v(t+1)) is chosen randomly, in accordance with the distribution Pv(t), and independently for all t (furthermore, v(0)=v0 is a fixed initial position). In particular, if the play comes to the same position again, that is, v=v(t)=v(t′) for some t<t′, then the moves e(t) and e(t′) may be distinct  although they are chosen (independently) with the same distribution Pv.The concept ofa priori realization is based on the following alternative assumptions. A move (v,v′) is chosen according to Pv, independently for all v∈V∖VT, but only once, before the game starts. Being chosen the move (v,v′) is applied whenever the play comes at v. By these assumptions, each infinite play ℓ is a lasso; that is, it consists of an initial part (that might be empty) and an infinitely repeated dicycle cℓ. Alternatively, ℓ may be finite; that is, it terminates in a VT. In both cases, ℓ begins in v0 and the probability of ℓ is the product of the probabilities of all its moves, Pℓ=∏e∈ℓ‍p(e). In this way, we obtain a probability distribution on the set of lassos of the digraph. In particular, the effective payoff is defined as the expected payoffs for the corresponding lassos. Let us also note that (in contrast to the Markovian case) the computation of limit distribution is not computationally efficient, since the set of plays may grow exponentially in size of the digraph. No polynomial algorithm computing the limit distribution is known for a priori realizations. Returning to our example 𝒢1, we obtain the following limit distribution:
(6)(1-p1,p1(1-p2),p1p2(1-p3),p1p2p3)1-p1,pp1fortheoutcomes(a1,a2,a3,c),
with initial position v1. The probability of outcome c is p1p2p3; it is strictly positive whenever pi>0 for all i∈I. Indeed, in contrast to the Markovian realization, the cycle will be repeated infinitely whenever it appears once under a priori realization.Remark 10.
Thus, solving the Chess-like games in the independently mixed strategies looks more natural under a priori (rather than Markovian) realizations. Unfortunately, it seems not that easy to suggest more applications of a priori realizations and we have to acknowledge that the concept of the Markovian realization is much more fruitful. Let us also note that playing in pure strategies can be viewed as a special case of both Markovian and a priori realizations with degenerate probability distributions.As we already mentioned, the mixed and independently mixed strategies coincide for𝒢1 since it is play-once. Yet, these two classes of strategies differ in 𝒢2.


## 3. Chess-Like Games with No Uniform NE

In the present paper, we will strengthen Theorems7 and 8, showing that games (𝒢1,u) and (𝒢2,u) may fail to have an NE (not only in pure, but even) in mixed strategies, as well as in the independently mixed strategies, under both Markovian and a priori realizations.For convenience, letJ={1,…,m} denote the set of indices of nonterminal positions. We will refer to positions giving only these indices.Let us recall the definition of payoff functionfv0(i,x) of player i for the initial position v0 and the strategy profile x; see Theorem 5. Let us extend this definition introducing the payoff function for the mixed and independently mixed strategies. In both cases, we define it as the expected payoff, under one of the above realizations, and denote by Fv0(i,p), where p is an m-vector whose jth coordinate pj is the probability of proceeding (not terminating) at position j∈J.Remark 11.
Let us observe that, in both𝒢1 and 𝒢2, the payoff functions Fv0(i,p), i∈I are continuously differentiable functions of pj when 0<pj<1 for all j∈J, for all players i∈I. Hence, if p is a uniform NE such that 0<pj<1 for all j∈J (under either a priori or Markovian realization), then
(7)∂Fv0(i,p)∂pj=0,∀i∈I,j∈J,v0∈V.
In the next two sections, we will construct games that have no uniform NE under both, a priori and Markovian, realizations. Assuming that a uniform mixed NE exists, we will obtain a contradiction with (7) whenever 0<pj<1 for all j∈J.


### 3.1.(𝒢1,u) Examples

The next lemma will be instrumental in the proofs of the following two theorems.Lemma 12.
The probabilities to proceed satisfy0<pj<1 for all j∈J={1,2,3} in any independently mixed uniform NE in game (𝒢1,u), where u∈U1, and under both a priori and Markovian realizations.Proof.
Let us assume indirectly that there is an (independently) mixed uniform NE under a priori realization withpj=0 for some j∈J. This would imply the existence of an acyclic game with uniform NE, in contradiction with Theorem 7. Now let us consider the case pj=1. Due to the circular symmetry of (𝒢1,u), we can choose any player, say, j=1. The preference list of player 3 is u(3,a1)>u(3,a3)>u(3,a2)>u(3,c). His most favorable outcome, a1, is not achievable since p1=1. Hence, p3=0 because his second best outcome is a3. Thus, the game is reduced to an acyclic one, in contradiction with Theorem 7, again.Theorem 13.
Game(𝒢1,u) has no uniform NE in independently mixed strategies under a priori realization whenever u∈U1.Proof.
To simplify our notation we denote byj+ and j- the following and preceding positions along the 3-cycle of 𝒢1, respectively. Assume indirectly that (p1,p2,p3) forms a uniform NE and considers the effective payoff of player 1:
(8)Fj(1,p)=(1-pj)u(1,aj)+pj(1-pj+)u(1,aj+)+pjpj+(1-pj-)u(1,aj-)+pjpj+pj-u(1,c),
where j is the initial position.
By Lemma12, we must have 0<pj<1 for j∈J={1,2,3}. Therefore (7) must hold. Hence, (∂Fj(1,p)/∂pj-)=pjpj+(u(1,c)-u(1,aj-))=0 and pjpj+=0 follows since u(1,aj-)>u(1,c). Thus, p1p2p3=0, in contradiction to our assumption.Let us recall that for𝒢1, independently mixed strategies and mixed strategies are the same.Now, let us consider the Markovian realization. Game(𝒢1,u) may have no NE in mixed strategies under Markovian realization either, yet, only for some special payoffs u∈U1.Theorem 14.
Game(𝒢1,u), with u∈U1, has no uniform NE in independently mixed strategies under Markovian realization if and only if μ1μ2μ3≥1, where
(9)μ1=u(1,a2)-u(1,a1)u(1,a1)-u(1,a3),μ2=u(2,a3)-u(2,a2)u(2,a2)-u(2,a1),μ3=u(3,a1)-u(3,a3)u(3,a3)-u(3,a2).It is easy to verify thatμi>0 for i=1,2,3 whenever u∈U1. Let us also note that in the symmetric case μ1=μ2=μ3=μ the above condition μ1μ2μ3≥1 turns into μ≥1.Proof.
Letp=(p1,p2,p3) be a uniform NE in the game (𝒢1,u) under Markovian realization. Then, by Lemma 12, 0<pi<1 for i∈I={1,2,3}. The payoff function of a player, with respect to the initial position that this player controls, is given by one of the next three formulas:
(10)F1(1,p)=(1-p1)u(1,a1)+p1(1-p2)u(1,a2)+p1p2(1-p3)u(1,a3)1-p1p2p3,F2(2,p)=(1-p2)u(2,a2)+p2(1-p3)u(2,a3)+p2p3(1-p1)u(2,a1)1-p1p2p3,F3(3,p)=(1-p3)u(3,a3)+p3(1-p1)u(3,a1)+p3p1(1-p2)u(3,a2)1-p1p2p3.
By Lemma12, (7) holds for any uniform NE. Therefore we have
(11)(1-p1p2p3)2∂F1(1,p)∂p1=p2(1-p3)u(1,a3)+(p2p3-1)u(1,a1)+(1-p2)u(1,a2)=0,(1-p1p2p3)2∂F2(2,p)∂p2=p3(1-p1)u(2,a1)+(p1p3-1)u(2,a2)+(1-p3)u(2,a3)=0,(1-p1p2p3)2∂F3(3,p)∂p3=p1(1-p2)u(3,a2)+(p1p2-1)u(3,a3)+(1-p1)u(3,a1)=0.
Settingλi=μi+1 for i=1,2,3, we can transform the above equations to the following form:
(12)λ1(1-p2)=1-p2p3,λ2(1-p3)=1-p1p3,λ3(1-p1)=1-p1p2.
Assuming 0<pj<1, j∈J and using successive elimination, we uniquely express p via λ as follows:
(13)0<p1=λ2+λ3-λ1λ2-λ2λ3+λ1λ2λ3-1λ1λ3-λ1+1<1,0<p2=λ1+λ3-λ1λ3-λ2λ3+λ1λ2λ3-1λ1λ2-λ2+1<1,0<p3=λ1+λ2-λ1λ2-λ1λ3+λ1λ2λ3-1λ2λ3-λ3+1<1.
Interestingly, all threepj<1 inequalities are equivalent with the condition (λ1-1)(λ2-1)(λ3-1)<1, that is, μ1μ2μ3<1, which completes the proof.


### 3.2.(𝒢2,u) Examples

Here we will show that(𝒢2,u) may have no uniform NE for both Markovian and a priori realizations, in independently mixed strategies, whenever u∈U2. As for the mixed (unlike the independently mixed) strategies, we obtain NE-free examples only for some (not for all) u∈U2.We begin with extending Lemma12 to game (𝒢2,u) and u∈U2 as follows.Lemma 15.
The probabilities to proceed satisfy0<pj<1 for all j∈J={1,2,3,4,5,6} in any independently mixed uniform NE in game (𝒢2,u), where u∈U2, and under both a priori and Markovian realizations.Proof.
To prove thatpj<1 for all j∈J let us consider the following six cases: (i)
Ifp1=1, then player 2 will proceed at position 6, as a2>a6 in U2, implying p6=1.(ii)
Ifp2=1, then either p1=0 or p3=1, as player 1, prefers a1 to a3.(iii)
Ifp3=1, then p2=0, as player 2 cannot achieve his best outcome of a3, while a2 is his second best one.(iv)
Ifp4=1, then p3=1, as player 1’s worst outcome is a3 in the current situation.(v)
Ifp5=1, then p4=1, as player 2, prefers a6 to a4.(vi)
Ifp6=1, then p5=0, as player 1’s best outcome, is a5 now.It is easy to verify that, by the above implications, in all six cases at least one of the proceeding probabilities should be 0, in contradiction to Theorem 8.Let us show that the game(𝒢2,u) might have no NE in independently mixed strategies under both Markovian and a priori realizations. Let us consider the Markovian one first.Theorem 16.
Game(𝒢2,u) has no uniform NE in the independently mixed strategies under Markovian realization for all u∈U2.Proof.
Let us consider the uniform NE conditions for player 2. Lemma15 implies that (7) must be satisfied. Applying it to the partial derivatives with respect to p4 and p6 we obtain
(14)(1-p1p2p3p4p5p6)2p1p2p3p4p5∂F1(2,p)∂p6=((1-p1)u(2,a1)+p1(1-p2)u(2,a2)+p1p2(1-p3)u(2,a3)+p1p2p3(1-p4)u(2,a4)+p1p2p3p4(1-p5)u(2,a5)-(1-p1p2p3p4p5)u(2,a6))=0,(1-p1p2p3p4p5p6)2p1p2p3p5p6∂F5(2,p)∂p4=(1-p5)u(2,a5)+p5(1-p6)u(2,a6)+p5p6(1-p1)u(2,a1)+p5p6p1(1-p2)u(2,a2)+p5p6p1p2(1-p3)u(2,a3)-(1-p1p2p3p5p6)u(2,a4)=0.
Let us multiply the first equation byp5p6 and subtract it from the second one, yielding
(15)(1-p1p2p3p4p5p6)[-u(2,a4)+(1-p5)u(2,a5)+p5u(2,a6)]=0,
or equivalently, u(2,a4)-(1-p5)u(2,a5)-p5u(2,a6)=0. From this equation, we find
(16)p5=u(2,a4)-u(2,a5)u(2,a6)-u(2,a5).
Furthermore, the condition 0<p5<1 implies that either u(2,a5)<u(2,a4)<u(2,a6) or u(2,a5)>u(2,a4)>u(2,a6). Both orders contradict the preference list U2, thus, completing the proof.Now let us consider the case of a priori realization.Theorem 17.
Game(𝒢2,u) has no uniform NE in independently mixed strategies under a priori realization for all u∈U2.Proof.
Let us assume indirectly thatp=(p1,p2,p3,p4,p5,p6) form a uniform NE. Let us consider the effective payoff of the player 1 with respect to the initial position 2:
(17)F2(1,p)=(1-p2)u(1,a2)+p2(1-p3)u(1,a3)+p2p3(1-p4)u(1,a4)+p2p3p4(1-p5)u(1,a5)+p2p3p4p5(1-p6)u(1,a6)+p2p3p4p5p6(1-p1)u(1,a1).
By Lemma 15, we have 0<pj<1 for j∈J={1,2,3,4,5,6}. Hence, (7) must hold; in particular, (∂F2(1,p)/∂p1)=0 and, since u∈U2 is positive, we obtain p2p3p4p5p6=0,  that is a contradiction.The last result can be extended from the independently mixed to mixed strategies. However, the corresponding example is constructed not for all but only for someu∈U2.Theorem 18.
The game(𝒢2,u) has no uniform, NE in mixed strategies, at least for some u∈U2.Proof.
Let us recall that there are two players in𝒢2 controling three positions each and there are two possible moves in every position. Thus, each player has eight pure strategies. Standardly, the mixed strategies are defined as probability distributions on the set of the pure strategies, that is, x,y∈𝒮8, where z=(z1,…,z8)∈𝒮8 if and only if ∑i=18‍zi=1 and z≥0.
Furthermore, let us denote byakl(v0) the outcome of the game beginning in the initial position v0∈V in case when player 1 chooses his pure strategy k and player 2 chooses her pure strategy l, where k,l∈{1,…,8}.
Given a utility functionu:I×A→ℝ, if a pair of mixed strategies x,y∈𝒮8 form a uniform NE then
(18)∑k=18‍xku(2,akl(v0)){=zv0,ifyl>0≤zv0,otherwise
must hold for some zv0 value for all initial positions v0∈V. Indeed, otherwise player 2 would change the probability distribution y to get a better value. Let S={i∣yi>0} denote the set of indices of all positive components of y∈𝒮8. By (19), there exists a subset S⊆{1,…,n} such that the next system is feasible:
(19)∑k=18‍xku(2,akl(v0))=zv0,∀l∈S,∑k=18‍xku(2,akl(v0))≤zv0,∀l∉S,∑k=18‍xk=1,xk≥0,∀k=1,…,8,zv0unrestricted,∀v0∈V.
Then, let us consider, for example, a utility functionu∈U2 with the following payoffs of player 2:
(20)u(2,a1)=43,u(2,a2)=81,u(2,a3)=93,u(2,a4)=50,u(2,a5)=15,u(2,a1)=80,u(2,c)=0.
We verified that (19) is infeasible for all subsets S⊆{1,…,8} such that |S|≥2. Since for any u∈U2 there is no pure strategy NE either, we obtain a contradiction.


### 3.3. Concluding Remarks

Remark 19.
In the last two theorems, in contrast with Theorem14, uniform NE exist for no u∈U2.Remark 20.
Let us note that Nash’s results [21, 22], guaranteeing the existence of an NE in mixed strategies for any normal form games, are applicable in case of a fixed initial position. Yet, our results show that Nash’s theorem, in general, does not extend to the case of uniform NE, except for the n-person acyclic case [12, 19, 20] and the two-person zero sum cases.Remark 21.
It seems that the same holds for allu∈U2. We tested (19) for many randomly chosen u∈U2 and encountered infeasibility for all S⊆{1,…,8} such that |S|≥2. Yet, we have no proof and it still remains open whether for any u∈U2 there is no NE in mixed strategies.Remark 22.
Finally, let us note that for an arbitrary Chess-like game structure (not only for𝒢1 and 𝒢2) in independently mixed strategies under both the Markovian and a priori realizations for any i∈I and k,l∈J, the ratio (∂Fl(i,p)/∂pi)/(∂Fk(i,p)/∂pi)=P(i,k,l) is a positive constant.


## 3.1.(𝒢1,u) Examples

The next lemma will be instrumental in the proofs of the following two theorems.Lemma 12.
The probabilities to proceed satisfy0<pj<1 for all j∈J={1,2,3} in any independently mixed uniform NE in game (𝒢1,u), where u∈U1, and under both a priori and Markovian realizations.Proof.
Let us assume indirectly that there is an (independently) mixed uniform NE under a priori realization withpj=0 for some j∈J. This would imply the existence of an acyclic game with uniform NE, in contradiction with Theorem 7. Now let us consider the case pj=1. Due to the circular symmetry of (𝒢1,u), we can choose any player, say, j=1. The preference list of player 3 is u(3,a1)>u(3,a3)>u(3,a2)>u(3,c). His most favorable outcome, a1, is not achievable since p1=1. Hence, p3=0 because his second best outcome is a3. Thus, the game is reduced to an acyclic one, in contradiction with Theorem 7, again.Theorem 13.
Game(𝒢1,u) has no uniform NE in independently mixed strategies under a priori realization whenever u∈U1.Proof.
To simplify our notation we denote byj+ and j- the following and preceding positions along the 3-cycle of 𝒢1, respectively. Assume indirectly that (p1,p2,p3) forms a uniform NE and considers the effective payoff of player 1:
(8)Fj(1,p)=(1-pj)u(1,aj)+pj(1-pj+)u(1,aj+)+pjpj+(1-pj-)u(1,aj-)+pjpj+pj-u(1,c),
where j is the initial position.
By Lemma12, we must have 0<pj<1 for j∈J={1,2,3}. Therefore (7) must hold. Hence, (∂Fj(1,p)/∂pj-)=pjpj+(u(1,c)-u(1,aj-))=0 and pjpj+=0 follows since u(1,aj-)>u(1,c). Thus, p1p2p3=0, in contradiction to our assumption.Let us recall that for𝒢1, independently mixed strategies and mixed strategies are the same.Now, let us consider the Markovian realization. Game(𝒢1,u) may have no NE in mixed strategies under Markovian realization either, yet, only for some special payoffs u∈U1.Theorem 14.
Game(𝒢1,u), with u∈U1, has no uniform NE in independently mixed strategies under Markovian realization if and only if μ1μ2μ3≥1, where
(9)μ1=u(1,a2)-u(1,a1)u(1,a1)-u(1,a3),μ2=u(2,a3)-u(2,a2)u(2,a2)-u(2,a1),μ3=u(3,a1)-u(3,a3)u(3,a3)-u(3,a2).It is easy to verify thatμi>0 for i=1,2,3 whenever u∈U1. Let us also note that in the symmetric case μ1=μ2=μ3=μ the above condition μ1μ2μ3≥1 turns into μ≥1.Proof.
Letp=(p1,p2,p3) be a uniform NE in the game (𝒢1,u) under Markovian realization. Then, by Lemma 12, 0<pi<1 for i∈I={1,2,3}. The payoff function of a player, with respect to the initial position that this player controls, is given by one of the next three formulas:
(10)F1(1,p)=(1-p1)u(1,a1)+p1(1-p2)u(1,a2)+p1p2(1-p3)u(1,a3)1-p1p2p3,F2(2,p)=(1-p2)u(2,a2)+p2(1-p3)u(2,a3)+p2p3(1-p1)u(2,a1)1-p1p2p3,F3(3,p)=(1-p3)u(3,a3)+p3(1-p1)u(3,a1)+p3p1(1-p2)u(3,a2)1-p1p2p3.
By Lemma12, (7) holds for any uniform NE. Therefore we have
(11)(1-p1p2p3)2∂F1(1,p)∂p1=p2(1-p3)u(1,a3)+(p2p3-1)u(1,a1)+(1-p2)u(1,a2)=0,(1-p1p2p3)2∂F2(2,p)∂p2=p3(1-p1)u(2,a1)+(p1p3-1)u(2,a2)+(1-p3)u(2,a3)=0,(1-p1p2p3)2∂F3(3,p)∂p3=p1(1-p2)u(3,a2)+(p1p2-1)u(3,a3)+(1-p1)u(3,a1)=0.
Settingλi=μi+1 for i=1,2,3, we can transform the above equations to the following form:
(12)λ1(1-p2)=1-p2p3,λ2(1-p3)=1-p1p3,λ3(1-p1)=1-p1p2.
Assuming 0<pj<1, j∈J and using successive elimination, we uniquely express p via λ as follows:
(13)0<p1=λ2+λ3-λ1λ2-λ2λ3+λ1λ2λ3-1λ1λ3-λ1+1<1,0<p2=λ1+λ3-λ1λ3-λ2λ3+λ1λ2λ3-1λ1λ2-λ2+1<1,0<p3=λ1+λ2-λ1λ2-λ1λ3+λ1λ2λ3-1λ2λ3-λ3+1<1.
Interestingly, all threepj<1 inequalities are equivalent with the condition (λ1-1)(λ2-1)(λ3-1)<1, that is, μ1μ2μ3<1, which completes the proof.


## 3.2.(𝒢2,u) Examples

Here we will show that(𝒢2,u) may have no uniform NE for both Markovian and a priori realizations, in independently mixed strategies, whenever u∈U2. As for the mixed (unlike the independently mixed) strategies, we obtain NE-free examples only for some (not for all) u∈U2.We begin with extending Lemma12 to game (𝒢2,u) and u∈U2 as follows.Lemma 15.
The probabilities to proceed satisfy0<pj<1 for all j∈J={1,2,3,4,5,6} in any independently mixed uniform NE in game (𝒢2,u), where u∈U2, and under both a priori and Markovian realizations.Proof.
To prove thatpj<1 for all j∈J let us consider the following six cases: (i)
Ifp1=1, then player 2 will proceed at position 6, as a2>a6 in U2, implying p6=1.(ii)
Ifp2=1, then either p1=0 or p3=1, as player 1, prefers a1 to a3.(iii)
Ifp3=1, then p2=0, as player 2 cannot achieve his best outcome of a3, while a2 is his second best one.(iv)
Ifp4=1, then p3=1, as player 1’s worst outcome is a3 in the current situation.(v)
Ifp5=1, then p4=1, as player 2, prefers a6 to a4.(vi)
Ifp6=1, then p5=0, as player 1’s best outcome, is a5 now.It is easy to verify that, by the above implications, in all six cases at least one of the proceeding probabilities should be 0, in contradiction to Theorem 8.Let us show that the game(𝒢2,u) might have no NE in independently mixed strategies under both Markovian and a priori realizations. Let us consider the Markovian one first.Theorem 16.
Game(𝒢2,u) has no uniform NE in the independently mixed strategies under Markovian realization for all u∈U2.Proof.
Let us consider the uniform NE conditions for player 2. Lemma15 implies that (7) must be satisfied. Applying it to the partial derivatives with respect to p4 and p6 we obtain
(14)(1-p1p2p3p4p5p6)2p1p2p3p4p5∂F1(2,p)∂p6=((1-p1)u(2,a1)+p1(1-p2)u(2,a2)+p1p2(1-p3)u(2,a3)+p1p2p3(1-p4)u(2,a4)+p1p2p3p4(1-p5)u(2,a5)-(1-p1p2p3p4p5)u(2,a6))=0,(1-p1p2p3p4p5p6)2p1p2p3p5p6∂F5(2,p)∂p4=(1-p5)u(2,a5)+p5(1-p6)u(2,a6)+p5p6(1-p1)u(2,a1)+p5p6p1(1-p2)u(2,a2)+p5p6p1p2(1-p3)u(2,a3)-(1-p1p2p3p5p6)u(2,a4)=0.
Let us multiply the first equation byp5p6 and subtract it from the second one, yielding
(15)(1-p1p2p3p4p5p6)[-u(2,a4)+(1-p5)u(2,a5)+p5u(2,a6)]=0,
or equivalently, u(2,a4)-(1-p5)u(2,a5)-p5u(2,a6)=0. From this equation, we find
(16)p5=u(2,a4)-u(2,a5)u(2,a6)-u(2,a5).
Furthermore, the condition 0<p5<1 implies that either u(2,a5)<u(2,a4)<u(2,a6) or u(2,a5)>u(2,a4)>u(2,a6). Both orders contradict the preference list U2, thus, completing the proof.Now let us consider the case of a priori realization.Theorem 17.
Game(𝒢2,u) has no uniform NE in independently mixed strategies under a priori realization for all u∈U2.Proof.
Let us assume indirectly thatp=(p1,p2,p3,p4,p5,p6) form a uniform NE. Let us consider the effective payoff of the player 1 with respect to the initial position 2:
(17)F2(1,p)=(1-p2)u(1,a2)+p2(1-p3)u(1,a3)+p2p3(1-p4)u(1,a4)+p2p3p4(1-p5)u(1,a5)+p2p3p4p5(1-p6)u(1,a6)+p2p3p4p5p6(1-p1)u(1,a1).
By Lemma 15, we have 0<pj<1 for j∈J={1,2,3,4,5,6}. Hence, (7) must hold; in particular, (∂F2(1,p)/∂p1)=0 and, since u∈U2 is positive, we obtain p2p3p4p5p6=0,  that is a contradiction.The last result can be extended from the independently mixed to mixed strategies. However, the corresponding example is constructed not for all but only for someu∈U2.Theorem 18.
The game(𝒢2,u) has no uniform, NE in mixed strategies, at least for some u∈U2.Proof.
Let us recall that there are two players in𝒢2 controling three positions each and there are two possible moves in every position. Thus, each player has eight pure strategies. Standardly, the mixed strategies are defined as probability distributions on the set of the pure strategies, that is, x,y∈𝒮8, where z=(z1,…,z8)∈𝒮8 if and only if ∑i=18‍zi=1 and z≥0.
Furthermore, let us denote byakl(v0) the outcome of the game beginning in the initial position v0∈V in case when player 1 chooses his pure strategy k and player 2 chooses her pure strategy l, where k,l∈{1,…,8}.
Given a utility functionu:I×A→ℝ, if a pair of mixed strategies x,y∈𝒮8 form a uniform NE then
(18)∑k=18‍xku(2,akl(v0)){=zv0,ifyl>0≤zv0,otherwise
must hold for some zv0 value for all initial positions v0∈V. Indeed, otherwise player 2 would change the probability distribution y to get a better value. Let S={i∣yi>0} denote the set of indices of all positive components of y∈𝒮8. By (19), there exists a subset S⊆{1,…,n} such that the next system is feasible:
(19)∑k=18‍xku(2,akl(v0))=zv0,∀l∈S,∑k=18‍xku(2,akl(v0))≤zv0,∀l∉S,∑k=18‍xk=1,xk≥0,∀k=1,…,8,zv0unrestricted,∀v0∈V.
Then, let us consider, for example, a utility functionu∈U2 with the following payoffs of player 2:
(20)u(2,a1)=43,u(2,a2)=81,u(2,a3)=93,u(2,a4)=50,u(2,a5)=15,u(2,a1)=80,u(2,c)=0.
We verified that (19) is infeasible for all subsets S⊆{1,…,8} such that |S|≥2. Since for any u∈U2 there is no pure strategy NE either, we obtain a contradiction.


## 3.3. Concluding Remarks

Remark 19.
In the last two theorems, in contrast with Theorem14, uniform NE exist for no u∈U2.Remark 20.
Let us note that Nash’s results [21, 22], guaranteeing the existence of an NE in mixed strategies for any normal form games, are applicable in case of a fixed initial position. Yet, our results show that Nash’s theorem, in general, does not extend to the case of uniform NE, except for the n-person acyclic case [12, 19, 20] and the two-person zero sum cases.Remark 21.
It seems that the same holds for allu∈U2. We tested (19) for many randomly chosen u∈U2 and encountered infeasibility for all S⊆{1,…,8} such that |S|≥2. Yet, we have no proof and it still remains open whether for any u∈U2 there is no NE in mixed strategies.Remark 22.
Finally, let us note that for an arbitrary Chess-like game structure (not only for𝒢1 and 𝒢2) in independently mixed strategies under both the Markovian and a priori realizations for any i∈I and k,l∈J, the ratio (∂Fl(i,p)/∂pi)/(∂Fk(i,p)/∂pi)=P(i,k,l) is a positive constant.



---

*Source: 534875-2013-05-22.xml*