Shapley Polygons in 4 x 4 Games

Abstract

We study 4 × 4 games for which the best response dynamics contain a cycle. We give examples in which multiple Shapley polygons occur for these kinds of games. We derive conditions under which Shapley polygons exist and conditions for the stability of these polygons. It turns out that there is a very strong connection between the stability of heteroclinic cycles for the replicator equation and Shapley polygons for the best response dynamics. It is also shown that chaotic behaviour can not occur in this kind of game.

1. Introduction

Identifying cycles in games is easy, but it is not easy to analyse the qualitative behaviour of these cycling structures. It is a priori not clear, if these systems lead to convergence to an interior fixed point, to an periodic attractor or to chaotic behaviour. For example even the structure of the simple RSP game can either lead to convergence to a Nash equilibrium or to convergence to a periodic orbit for the best response dynamics. In [1] the RSP game was analysed—besides some other low dimensional games—for the best response dynamics and the results were compared to results for the replicator equation. A strong connection was found between the limit set of time averages of the orbits for the replicator equation and the $\omega -$ limits of the best response dynamics. A later paper [2] shows that this connection was not specific for these games but is true in a more general sense. It is shown in this paper that the limit set of the time averages (of orbits starting in the interior) for the replicator equation is a subset of the maximal invariant set for the best response dynamics. Cycles for low dimensional games for the replicator equation are for example thoroughly analysed in [3,4]. In these papers conditions are given under which so called heteroclinic cycles are attracting or repelling. Permanence is an important property in evolutionary game theory and the existence of an attracting heteroclinic always excludes the possibility that a system is permanent. Permanent means—biologically speaking—that all species are safe from going extinct. We will show equivalence between permanence for the replicator equation and the non existence of Shapley polygons for the best response for so called monocyclic payoff matrices.

We will also analyse games with embedded RSP cycles for the best response dynamics and give a classification as complete as possible for them. A comparison of the results for the best response dynamics to those for the replicator dynamics is made with respect to [2] where the strong connection between the time average for the replicator equation and the invariant sets for the best response dynamics is shown. For the analysis of the best response dynamics we construct a two dimensional return map. Surprisingly this return map is very similar to the return map for the analysis of the replicator equation in [3], to be more precise the transition matrices are identical. These transition matrices play an important role in the analysis and as they are identical we get the equivalence of the existence of Shapley polygons for the best response dynamics and the existence of a relatively asymptotically stable heteroclinic cycle1. In this paper some counterexamples are given for some conjectures that might be drawn from the analysis of RSP game for the best response dynamics. It is shown that the invariant set $V_0$ for the RSP does not have to be invariant in $4\times 4$ games. It is also shown that $V(\mathbf{x}(t))$ is not always a good Ljapunov function. As a ‘side product’we get that for this class of games no chaotic behaviour can occur.

The paper is structured as follows: It starts with some general assumptions on the payoff matrix. The main results of this paper and their discussion with respect to earlier results for the replicator equation can be found in Section 3. In Section 4 examples are provided for different asymptotical behaviour for these kinds of games. The remaining sections contain the construction and analysis of the return map.

2. Preliminaries and Assumptions on the Payoff Matrix A

In this work we will deal with finite, symmetric 2 person normal form games. The player’s payoffs are summarised in the ($n\times n$) matrix A where $a_{ij}$ describes the payoff of strategy i against strategy j.

$$\begin{array}{c}\hfill A=(a_{ij}),i,j=1,\dots ,n\end{array}$$

The expression ${A|}_I$ always describes the payoff matrix for a game restricted to the strategies contained in the index set I. (If there is no risk of confusion the index set I will not be written down explicitly.)

We use the following notation in this work

$${\Delta }_n:=\{\mathbf{x}\in {\mathbb{R}}^n:x_i\ge 0 and \sum _{i=1}^n{x}_i=1\}$$

which represents the $(n-1)$-dimensional simplex. Vectors are written in bold letters e.g $\mathbf{x}$. The i-th vertex of the simplex is denoted with ${\mathbf{e}}_i$. The standard scalar product of two vectors $\mathbf{u}$ and $\mathbf{v}$ is written in the following way

$$\mathbf{u}·\mathbf{v}:=\sum _{i=1}^n{u}_i{v}_i$$

Lastly we define the set ${\mathbb{R}}_0^n$ by

$${\mathbb{R}}_0^n:=\{\mathbf{x}\in {\mathbb{R}}^n:\sum _{i=1}^n{x}_i=0\}$$

If there is no risk of confusion, we will call the vertex ${\mathbf{e}}_i$ sloppily i. In this paper we will analyse games for the best response (or best reply—used equivalently) dynamics (see [5]), which is of the following form

$$\dot{\mathbf{x}}\in BR(\mathbf{x})-\mathbf{x}$$

(1)

where $BR(\mathbf{x})$ stands for the set of best responses to a given state $\mathbf{x}$. As mentioned we will compare the results of the qualitative behaviour to the behaviour of the replicator equation [6].

$$\begin{array}{c}\hfill {\dot{x}}_i=x_i({(A\mathbf{x})}_i-\mathbf{x}·A\mathbf{x})\end{array}$$

(2)

We define the set $B^i$, which is the set of all $\mathbf{x}\in {\Delta }_n$ for which i is the unique best reply against $\mathbf{x}$. More generally, we define $B^K$ with $K\subseteq \{1,\dots ,n\},K\ne \varnothing$, the set of all $\mathbf{x}\in {\Delta }_n$ for which all pure strategies in K are a best response against $\mathbf{x}$ and there are no other pure best responses,

$$\begin{array}{c}\hfill B^K:=\{\mathbf{x}\in {\Delta }_n:k\in BR(\mathbf{x})\forall k\in Kandj\notin BR(\mathbf{x})forj\notin K\}\end{array}$$

(3)

Definition 1

In this paper we call a game generic, if

$$\begin{array}{cc}\hfill (i)& B^K=\varnothing ordim{B}^K=n-card(K)forallnonemptyK\subseteq \{1,\dots ,n\}and\hfill \end{array}$$

(4)

$$\begin{array}{cc}\hfill (ii)& \bigcup _{i=1}^n\overline{B^i}={\Delta }_n\hfill \end{array}$$

(5)

hold.

Following [6] and [7] we state the following lemma

Lemma 1

Let

$$\begin{array}{c}\hfill V:{\Delta }_n\to \mathbb{R},V(\mathit{x}):=\underset{i}{max}{(A\mathit{x})}_i\end{array}$$

(6)

and let the payoff matrix $A=(a_{ij})$ be normalised in the way that $a_{ii}=0$ holds for all $i=1,\dots ,n$ then V satisfies $\dot{V}(\mathit{x})=-V(\mathit{x})$ for all $\mathit{x}\in B^j$ and hence $|V(\mathit{x}(t))|$ is strictly decreasing along the piecewise linear solutions to Equation (1) inside each $B^j$.

Moreover, if $\mathit{x}(t)$ is in ${\bigcup }_j{B}^j$ for almost all $t>0$ we get $V(\mathit{x}(t))\to 0$ as $t\to \infty$. In other words the orbits converge to the set $V_0$, which is defined as

$$\begin{array}{c}\hfill V_0:=\{\mathit{x}\in {\Delta }_n:V(\mathit{x})=0\}\end{array}$$

(7)

Definition 2

A periodic orbit Γ under the best response dynamic is called a Shapley polygon.

Let us now introduce better and best reply cycles.

Definition 3

If $a_{ji}>a_{ki}$ for all $k\ne j$ and $a_{jj}>a_{ij}$ hold, we call this a best response arc2 from ${\mathit{e}}_i$ to ${\mathit{e}}_j$ and write symbolically ${\mathit{e}}_i\twoheadrightarrow {\mathit{e}}_j$.

This simply means that j is the unique best reply to i and j is a better reply against itself than i. This gives rise to a directed graph $\stackrel{\twoheadrightarrow }{G}$ for all best response arcs.

Definition 4

We call a cycle in this directed graph $\stackrel{\twoheadrightarrow }{G}$ a best response cycle.

For example if the graph is ${\mathbf{e}}_{\mathbf{1}}\twoheadrightarrow {\mathbf{e}}_{\mathbf{2}}\twoheadrightarrow {\mathbf{e}}_{\mathbf{3}}\twoheadrightarrow {\mathbf{e}}_{\mathbf{4}}\twoheadrightarrow {\mathbf{e}}_{\mathbf{2}}$, then the best response cycle connects ${\mathbf{e}}_{\mathbf{2}},{\mathbf{e}}_{\mathbf{3}}$ and ${\mathbf{e}}_{\mathbf{4}}$. Clearly, a game can have more than one best response cycle, but these cycles are disjoint. Note that neither a best response cycle nor a best response arc have to exist.

In analogy we define a better reply arc from ${\mathbf{e}}_i$ to ${\mathbf{e}}_j$, if $a_{ji}>a_{ii}$ and $a_{jj}>a_{ij}$ hold and write symbolically ${\mathbf{e}}_i\to {\mathbf{e}}_j$. Again we get a directed graph $\overrightarrow{G}$ and cycles in this graph $\overrightarrow{G}$ are called better reply cycles. Note that better reply cycles do not have to be disjoint and every best reply cycle is also a better reply cycle. If there is no risk of confusion we will write only the best response (or reply) cycle 1234 instead of ${\mathbf{e}}_{\mathbf{1}}\twoheadrightarrow {\mathbf{e}}_{\mathbf{2}}\twoheadrightarrow {\mathbf{e}}_{\mathbf{3}}\twoheadrightarrow {\mathbf{e}}_{\mathbf{4}}\twoheadrightarrow {\mathbf{e}}_{\mathbf{1}}$. We also write the better reply cycle 1234 instead of ${\mathbf{e}}_{\mathbf{1}}\to {\mathbf{e}}_{\mathbf{2}}\to {\mathbf{e}}_{\mathbf{3}}\to {\mathbf{e}}_{\mathbf{4}}\to {\mathbf{e}}_{\mathbf{1}}$.

In this paper we are especially interested in games with a full better reply cycle, which means a cycle exists using all pure strategies. This also means that no pure strategy can become a Nash equilibrium. Despite this cycling behaviour, there is no need for a periodic orbit to exist for example because Nash equilibria can attract all orbits (see for example Section 7). On the one hand it will turn out that the number of Nash equilibria is very hard to predict (see Section 4); on the other hand it will turn out that for certain classes of payoff matrices only solutions for a set of measure 0 of starting values converge to a Nash equilibrium.

Throughout this paper we consider the following payoff matrix A

$$\begin{array}{c}\hfill A=(a_{ij})=\left(\begin{array}{cccc}0& -c_2& t_3& e_4\\ e_1& 0& -c_3& t_4\\ t_1& e_2& 0& -c_4\\ -c_1& t_2& e_3& 0\end{array}\right)\end{array}$$

(8)

and assume the following for all i for the payoff matrix A, unless stated otherwise

$$\begin{array}{cc}\hfill (i)& e_i>0,\hfill \end{array}$$

(9)

$$\begin{array}{cc}\hfill (ii)& c_i>0,\hfill \end{array}$$

(10)

$$\begin{array}{cc}\hfill (iii)& \mathrm{if}{t}_i>0\mathrm{then}{t}_{i+2}<0\mathrm{and}\hfill \end{array}$$

(11)

$$\begin{array}{cc}\hfill (iv)& \mathrm{the game is generic as in Definition 1}\hfill \end{array}$$

(12)

This notation is from [3], in which the stability of so called heteroclinic cycles for the replicator dynamics was analysed. A heteroclinic cycle corresponds to a better reply cycle. The $e_i$s stand for the expanding eigenvalues in direction of the heteroclinic cycle, the $c_i$s correspond to the contracting eigenvalues along the heteroclinic cycle and the $t_i$s are the eigenvalues transverse to the heteroclinic cycle. Note that we can only speak of eigenvalues with respect to the replicator equation3.

Remark 

The assumptions (9) and (10) guarantee the existence of a heteroclinic cycle for the replicator equation. A heteroclinic cycle is a union of orbits ${\bigcup }_{j=1}^n{\mathbf{x}}_j(t)$ (together with their α and ω limits, which are fixed points for the system), for which the ω-limit of ${\mathbf{x}}_i(t)$ is the α-limit of ${\mathbf{x}}_{i+1}(t)$ (with $i+1$ taken modulo n). The stability of such heteroclinic cycles has thoroughly been studied in [3,4].

Remark 

(9) and (10) assure that a better reply cycle ${\mathbf{e}}_1\to {\mathbf{e}}_2\to {\mathbf{e}}_3\to {\mathbf{e}}_4\to {\mathbf{e}}_1$ exists for A. Whereas (11) assures that no restricted two strategy game has a stable interior Nash equilibrium. This is easy to see: If both $t_i$ and $t_{i+2}$ are greater than zero, we get the following structure in the corresponding matrix of the restricted game

$$P_{i,i+2}=\left(\begin{array}{cc}0& +\\ +& 0\end{array}\right)$$

which means that the interior Nash equilibrium of this restricted game is attracting. This is the only way to get a stable interior equilibrium. If we have two opposite signs, there is no interior equilibrium and if there are two minus then the interior equilibrium is repelling.

The assumption in (11) seems to be somehow arbitrary, but we want to exclude a kind of forced movement 4 as example 1 should explain.

Example 1

We take the following payoff matrix A

$$\begin{array}{c}\hfill A=\left(\begin{array}{cccc}0& -\frac{9}{64}& \frac{15}{64}& \frac{47}{60}\\ \frac{9}{32}& 0& -\frac{3}{16}& \frac{5}{16}\\ \frac{3}{32}& \frac{3}{8}& 0& -\frac{1}{4}\\ -\frac{5}{32}& \frac{1}{8}& \frac{1}{2}& 0\end{array}\right)\end{array}$$

Note that our assumptions (9)-(10) hold for this matrix, but (11) is violated, because all the $t_i$ are positive. This example also shows that $V(\mathit{x}(t))$ is not always a good Ljapunov function. This matrix has a unique Nash equilibrium

$$N_{1234}=\left(\frac{860}{1899},\frac{361}{1899},\frac{181}{633},\frac{15}{211}\right)$$

But the minimum of $V(\mathit{x})={max}_i{(A\mathit{x})}_i$ is not attained at the equilibrium $N_{1234}$, but at the point $\mathit{m}=\left(\frac{5}{9},\frac{1}{9},\frac{1}{3},0\right)$. Its value there is

$$V(\mathit{m})=\frac{3}{32}=0.09375$$

whereas its value at the Nash equilibrium is

$$V\left(N_{1234}\right)=\frac{81}{844}=0.09597$$

Along the line segment s, which connects $\mathit{m}$ and $N_{1234}$ the pure strategies 2, 3 and 4 are best responses.

Figure 1. Sufficiently close to the line segment s, the dynamics is similar to the dynamics for the restricted game ${A|}_{234}$. Every orbit hits the set $B^{24}$, shown by the arrow in the figure. Inside this set there is a forced movement towards the unique Nash equilibrium of the restricted game.

Figure 1. Sufficiently close to the line segment s, the dynamics is similar to the dynamics for the restricted game ${A|}_{234}$. Every orbit hits the set $B^{24}$, shown by the arrow in the figure. Inside this set there is a forced movement towards the unique Nash equilibrium of the restricted game.

Therefore if we start in this segment the solution $\mathbf{x}(t)$ heads towards the unique Nash equilibrium $N_{234}=\left(0,\frac{7}{13},\frac{1}{13},\frac{5}{13}\right)$ of the restricted game ${A|}_{234}$ and $N_{1234}$ is reached in finite time (Along such an orbit $V(\mathit{x}(t))$ does not decrease!). Moreover there is a two dimensional manifold, in which 2 and 4 are the best responses, hence every orbit inside this set tends towards the Nash equilibrium $N_{24}=\left(0,\frac{5}{7},0,\frac{2}{7}\right)$ of the restricted game. After finite time s is reached and $N_{1234}$ is reached in finite time again. The movement inside $B^{24}$ is forced in the way that orbits close by want to cross $B^{24}$ from both sides. Thus the resulting movement is towards $N_{24}$. We can describe the dynamics for the game as follows. Some orbits that head for pure strategies cycle towards $N_{1234}$ and reach it in finite time. All other orbits (especially those $\mathit{x}$, with $V(\mathit{x})<V(N_{1234}))$ converge via s to $N_{1234}$ in finite time.

3. Main Results

In this section the main results of this paper are summarised. The following lemma is a central part for the analysis. It shows the form the return map which plays a crucial role in the analysis of the best response dynamics. One big advantage is that this map is of lower dimension than the game. Due to the lower dimension the map is easier to analyse, but no information on the global dynamics is lost. This is in contrast to the analysis of the replicator equation in [3] where the cross sections for the return map are placed near fixed points (the vertices) via a linearisation. These fixed points cannot be Nash equilibria of the game and hence no information on the behaviour close to Nash equilibria can be achieved directly by this method. This is especially true with respect to the interior Nash equilibrium. Whereas for the best response dynamics these cross-sections for the return map are given more naturally and no linearisation is needed. Almost all orbits for the best response dynamics cross a transition face and so this allows us for the best response dynamics to give results for almost all orbits. Moreover for some cases we are also able to give some general results about the existence and stability of Nash equilibria. Especially for the interior Nash equilibrium $N_{1234}$, if it exists, we can give very precise results about its stability. Clearly if we can state a result on the existence of a Nash equilibrium for the best response dynamics it automatically applies for the replicator equation. The focus in [3,4] was on the study of the heteroclinic cycle and hence no results on the Nash equilibria were given.

Lemma 2

If there is an orbit from $B^{i-1,i}$ to $B^{i,i+1}$ the map from $B^{i-1,i}$ to $B^{i,i+1}$ can be written in the form (after an appropriate parametrisation):

$$\begin{array}{c}\hfill T_i(\mathit{u}):=\frac{P_i\mathit{u}}{1+{\mathit{d}}_i·\mathit{u}},T_i:{\mathbb{R}}_{+}^2\to {\mathbb{R}}_{+}^2\end{array}$$

where $P_i$ is a $2\times 2$ matrix. This is a central projection and the center of the projection (see Section 6.3) is the best response vertex.

If there is an orbit from $B^{i-1,i}$ to $B^{i-1,i}$ following the full cycle the map from $B^{i-1,i}$ to $B^{i-1,i}$ can be written in the form (after an appropriate parametrisation):

$$\begin{array}{c}\hfill \Pi (\mathit{u}):=\frac{P\mathit{u}}{1+\mathit{d}·\mathit{u}},\Pi :{\mathbb{R}}_{+}^2\to {\mathbb{R}}_{+}^2\end{array}$$

(13)

where P is a $2\times 2$ matrix.

Surprisingly the transition matrices for the stability analysis of the replicator equation in [3] are identical to the transition matrices found for the best response dynamics (after a careful choice of variables). Some technical difficulties arise in the analysis of the best response dynamics. This results from the placement of the cross-sections and the fact that the return map Π is a fractional linear map and hence a priori the map is not defined for all $\mathbf{x}\in {\mathbb{R}}^2$. For the replicator equation there must exist an orbit from one cross-section to the next, if only the neighbourhood is chosen small enough. This follows directly from the form of the differential equation: ${\dot{x}}_i=x_i{f}_i(\mathbf{x})$. (In fact there are some other technical difficulties for the replicator equation, regarding the mapping from one cross-section to the next. These problems concern the shape of the image of the domain, which plays an important role in the analysis.) For the best response dynamics it is not clear if there is always an orbit from one cross-section to the next. Preliminarily this can only be guaranteed if an interior Nash equilibrium exists (because in that case no strategy is dominated and so each pure strategy is used for some $\mathbf{x}$), but as the examples in Section 4 below show it is not always true that an interior Nash equilibrium $N_{1234}$ exists. Thus we have to show that no strategy is dominated to prove that there is in fact always an orbit from one cross-section to the next. The problem with the denominator of the map can be solved by using a compactification of ${\mathbb{R}}^2$ by introducing the real projective plane $\mathbb{R}{\mathbb{P}}^2$ (in short notation ${\mathbb{P}}^2$). This is a detour, which was not necessary for the analysis of the replicator equation. But the gain for the best response is that we get more global results. To be more precise in [3,4] all results are local results. In contrast all statements found in this work apply at least to all orbits following a specific cycle. This means in a lot cases a result about almost all orbits.

Let us now turn to the concrete results on the best response dynamics. We start with a result on so called monocyclic matrices. The terminology follows [7] and it describes a payoff matrix for which all $t_i$s are negative and hence the matrix only contains one better reply cycle.

$$\begin{array}{c}\hfill A=\left(\begin{array}{cccc}0& -c_2& t_3& e_4\\ e_1& 0& -c_3& t_4\\ t_1& e_2& 0& -c_4\\ -c_1& t_2& e_3& 0\end{array}\right)\end{array}$$

(14)

where $c_i>0,e_i>0$ and $t_i<0$ for $i=1,\dots ,4$. In [10] is shown that for games with monocyclic payoff matrix and an interior Nash equilibrium ${\mathbf{x}}^{*}$ all orbits converge to the interior Shapley polygon if ${\mathbf{x}}^{*}·A{\mathbf{x}}^{*}<0$ holds. We used a different approach for the return map as in [10] and get more information on the global dynamics. Proposition 16 below gives a complete classification of the attractors for monocyclic matrices and hence a more precise result on the existence of a Shapley polygon. Additionally we get conditions for the stability of the interior Nash equilibrium. In [6] a list of equivalences for monocyclic games is given. With the help of the return map and some considerations on the index of the Nash equilibria we can completely classify $4\times 4$ monocyclic games see Section 7 below. The only parameters needed for the classification are $det(A)$, $\Pi e_i$ and $\Pi c_i$.

A behaviour can be observed similar to a supercritical Hopf bifurcation for monocyclic payoff matrices. In case $N_{1234}·A{N}_{1234}$ is smaller than 0 there exists a Shapley polygon. In case $N_{1234}·A{N}_{1234}=0$ holds this polygon shrank to the point $N_{1234}$. We will call this a degenerated Shapley polygon. In case $N_{1234}·A{N}_{1234}>0$ no Shapley polygon exists.

Theorem 3

Let A be a monocyclic payoff matrix. Then the following statements are equivalent

(i) 

There is no (possibly degenerated) Shapley polygon for the best response dynamics.

(ii) 

All orbits converge in finite time to the interior Nash equilibrium $N_{1234}$.

(iii) 

The system is permanent for the replicator equation.

This result shows the strong connection between the replicator equation and the best response dynamics and it follows immediately from [2] that at least the time average of every interior orbit for the replicator equation converges to the interior Nash equilibrium. So by giving a classification for the best response dynamics for monocyclic games we automatically improve some results for the replicator equation.

The next two theorems give some results on payoff matrices with one additionally embedded RSP cycle.

Remark 

There are some recurring terms in the following results and throughout the analysis in the sections below (mainly in Lemma 11). To enhance readability we summarise these terms here.

$$\begin{array}{ccc}\hfill {\Sigma }_1& =& -(c_1{e}_2{t}_3+c_2{e}_3{t}_1+t_1{t}_2{t}_3)\hfill \\ \hfill {\Sigma }_2& =& -(c_2{e}_3{t}_4+c_3{e}_4{t}_2+t_2{t}_3{t}_4)\hfill \\ \hfill e& =& \Pi e_i,c=\Pi c_i\mathrm{and}q={\left(\sqrt{e}-\sqrt{c}\right)}^2\hfill \end{array}$$

${\Sigma }_1$ and ${\Sigma }_2$ can be interpreted as the stability criteria for the Shapley triangle to exist in the full game. If the restricted game ${A|}_{\{1,2,3\}}$ has a Shapley triangle then ${\Sigma }_1<0$ assures that it still exists in the full game. The same holds for ${\Sigma }_2$ and the 234 restricted game. The expression $det(A)>-q$ is equivalent to the requirement that the return matrix (13) has a real eigenvalue.

Theorem 4

Let A be a payoff matrix as in (8) with $t_{1,2,4}<0$ and $t_3>0$. Then the game has an interior Shapley polygon, which is locally attracting if $detA>0$ or $e<c$ and one of the following conditions hold.

(i) 

${\Sigma }_1>0$

(ii) 

${\Sigma }_1<0,{\Sigma }_2>0anddetA>max\left\{e-c+2t_4{A}^{(24)}-2e_4{A}^{(14)},-q\right\}$

For (ii) there are two interior Shapley polygons. One is locally attracting and one is a saddle. To be more precise every orbit following the 1234 is either attracted by the attracting Shapley polygon or repelled (except a two dimensional manifold) by the saddle-type Shapley polygon to follow a different cycle after some time.

This is exactly the same result as in [3] for the existence of relatively asymptotically stable heteroclinic cycle following the cycle 1234. Again note that that this result is not simply local. It is a result for all orbits following the 1234 cycle at least once. The next theorem shows that the return map for the best response dynamics is again more ‘powerful’than for the replicator equation and gives a result on the existence of the interior Nash equilibrium and its stability.

Theorem 5

Let A be a matrix as in (8) and let $t_{1,2,4}<0$ and $t_3>0$ hold. If $e_1{e}_2{t}_3<|t_1|c_2{c}_3$ holds and

(a) 

${\Sigma }_1<0$ holds, then an attracting Shapley polygon following the 123 cycle exists.

(b) 

${\Sigma }_1>0$ holds and no interior Shapley polygon exists (see theorem 4) then an asymptotically stable interior Nash equilibrium $N_{1234}$ exists.

Theorem 4 together with Theorem 5 also give conditions under which an attracting Shapley triangle, an attracting Shapley polygon in the interior and a second interior Shapley polygon, which is a saddle, exist. The theorem above also provides a connection between the existence of an attracting Shapley polygon and the stability of the interior Nash equilibrium. And hence it draws a connection to the existence of heteroclinic cycles and the interior Nash equilibrium, which was not done in [3] and [4].

The next theorem presents some statements on games with two embedded RSP cycles.

Theorem 6

Let A be a matrix as in (8) and let $t_1<0,t_2<0$ and $t_3>0,t_4>0$ and let ${\Sigma }_1>0$ and ${\Sigma }_2>0$ hold. Then if

(i) 

$det(A)>0ore<c$ hold then an interior Shapley polygon exists, which attracts almost all orbits.

(ii) 

$-q<det(A)<0ande>c$ hold then an interior Nash equilibrium $N_{1234}$ exists, which is globally asymptotically stable.

Note that the results from Theorem 5 can be also applied so with two embedded RSP cycles it also possible to construct examples with two Shapley polygons on the boundary. One following the 123 cycle and one following the 234 cycle. It is important to note that the return map per se only allows a statement that the interior Nash equilibrium $N_{1234}$ is relatively asymptotically stable (for a definition see [3]) with respect to the set of orbits that follow the 1234 cycle. But on one hand we know for the best response dynamics (especially when no orbit can follow a cycle different to 1234 infinitely many times) that only a set of measure 0 does not converge to the interior Nash equilibrium and on the other hand in cases mentioned above we were able with some additional considerations to show that no other Nash equilibrium can exist and hence the interior equilibrium is globally asymptotically stable.

4. Examples

In this section some examples for the different cases in the sections above are presented. These examples show that there is no connection between the support of the Shapley polygon and the support of the Nash equilibria. There is also no connection between the global dynamics and the Nash equilibria. The examples will also show that the support of the best reply cycle and the support of the cycle the Shapley polygon follows, do not have to be identical. There is also an example, where the support of the unique Nash equilibrium is not contained in the best reply cycle. Under this assumption the Shapley polygon can be seen as another solution concept for games which only have unstable Nash equilibria.

Example 2

This example has a unique Shapley polygon. It lies on the 123 face and the game has no interior Nash equilibrium. Note that the best response cycle connects the strategies 234, while the attracting Shapley polygon follows the 123 cycle (Theorem 4). So the support of the best response cycle does not have to be contained in the support of the attracting Shapley polygon and vice versa.

$$A=\left(\begin{array}{cccc}0& -1& \frac{3}{20}& 1\\ 1& 0& -\frac{1}{5}& 2\\ -1& 1& 0& -4\\ -1& -15& 1& 0\end{array}\right)$$

The unique Nash equilibrium is given by

$$\begin{array}{cc}\hfill N_{123}& =\left(\begin{array}{cccc}\frac{11}{81}& \frac{10}{81}& \frac{20}{27}& 0\end{array}\right)\hfill \end{array}$$

Example 3

The second example has a unique Shapley polygon on the 123 face (Theorem 4) and a unique Nash equilibrium on the 124 face. This example stresses the non-correlation of Nash equilibria and Shapley polygons as neither the support of the Nash equilibrium is contained in the support of the Shapley polygon nor is the support of the Shapley polygon contained in the support of the Nash equilibrium.

$$A=\left(\begin{array}{cccc}0& -3& \frac{3}{2}& 1\\ 1& 0& -3& -15\\ -15& 1& 0& -1\\ -1& -\frac{39}{20}& 1& 0\end{array}\right)$$

The unique Nash equilibrium is given by

$$\begin{array}{c}\hfill N_{124}=\left(\begin{array}{cccc}\frac{276}{697}& \frac{20}{41}& 0& \frac{81}{697}\end{array}\right)\end{array}$$

Example 4

The following example has one Nash equilibrium but no interior. The consequence is that it is not necessary to have an interior Nash equilibrium, if there is a Shapley polygon with full support. The Shapley polygon on the boundary lies on the 123 face, whereas the best response cycle connects 234 (Theorem 5).

$$A=\left(\begin{array}{cccc}0& -1& \frac{1}{3}& 1\\ 1& 0& -2& 2\\ -1& 1& 0& -85\\ -2& -2& 1& 0\end{array}\right)$$

The unique Nash equilibrium is given by

$$\begin{array}{c}\hfill N_{123}=\left(\begin{array}{cccc}\frac{13}{30}& \frac{4}{15}& \frac{3}{10}& 0\end{array}\right)\end{array}$$

Example 5

The last example has two Shapley polygons on the boundary and one in the interior. The two Shapley polygons on the boundary lie in the 123 and the 234 face (Theorem 6).

$$A=\left(\begin{array}{cccc}0& -2& \frac{12623}{20000}& 1\\ 1& 0& -\frac{11}{100}& \frac{31}{10}\\ -3& 1& 0& -10\\ -1& -3& 1& 0\end{array}\right)$$

The unique Nash equilibrium is given by

$$\begin{array}{cc}\hfill N_{123}& =\left(\begin{array}{cccc}\frac{19223}{256315}& \frac{57092}{256315}& \frac{36000}{51263}& 0\end{array}\right)\hfill \end{array}$$

We get two attractors (Shapley polygons) on the boundary and an interior unstable Shapley polygon. Additionally there is one orbit from the 234 face that moves towards $N_{123}$.

5. General Properties of the Dynamics

The following lemma gives more insight in the solutions of the game with payoff matrix A and the assumptions made in the beginning.

Lemma 7

Let A be a payoff matrix of the form (8) with the assumptions (9)–(12). Let $\mathit{x}\in B^i$ with $i=1,\dots ,4$ then there exists a $T\in (0,\infty ]$ such that the solution $\mathit{x}(t)$ is unique for $t\in \left[0,T\right]$ and $\mathit{x}(t)\in {\bigcup }_{i=1}^4{B}^i$ holds for almost all $0\le t\le T$. For $t>T$ the solution $\mathit{x}(t)$ is no longer unique or there is an interval $I=\left[t^{\prime },t^{\prime \prime }\right]$ such that the orbit $\mathit{x}(t)\notin {\bigcup }_{i=1}^4{B}^i$ for $t\in I$.

If $T<\infty$ holds, then either an interior Nash equilibrium is reached in finite time or $\mathit{x}(t)$ converges for $t\to \infty$ to a Nash equilibrium on the boundary. If $T=\infty$ holds, then $\mathit{x}(t)\to V_0$ as $t\to \infty$.

Remark 

Note that assumption (11) is needed for this lemma, which excludes forced movement. In general we cannot predict the behaviour of the orbit after the interior Nash equilibrium $N_{1234}$ is reached via a forced movement. If $N_{1234}$ is the unique equilibrium the orbit cannot leave $N_{1234}$, but if the game has several Nash equilibria, then uniqueness is lost and it is possible to continue the path towards each equilibrium at any time. If, for example, $N_{13}$ exists the orbit can move towards $N_{13}$ and then can move towards strategy 1 or 3 at any time. In this case the orbit reenters the set ${\bigcup }_{i=1}^4{B}^i$.

Proof 

$\mathbf{x}\in B^i$ means that

$${(A\mathbf{x})}_i>{(A\mathbf{x})}_j\forall j\ne i$$

which means that the orbit has to move towards ${\mathbf{e}}_i$ and hence can be written as

$$\mathbf{x}(t)=e^{-t}\mathbf{x}+(1-e^{-t}){\mathbf{e}}_i$$

for t small enough. If we look at (after a change of time $t\mapsto 1-e^{-t}$)

$$\begin{array}{cc}\hfill A\mathbf{x}(t)& =A\mathbf{x}+tA({\mathbf{e}}_{\mathbf{i}}-\mathbf{x})\hfill \\ & =(1-t)A\mathbf{x}+tA{\mathbf{e}}_{\mathbf{i}}\hfill \end{array}$$

we can calculate, which strategy becomes the next best response. $A{\mathbf{e}}_i$ is simply the i-th column of the matrix $A=(a_{ij})$. We know by (9) and (10) that $a_{ii}=0$, $a_{i+1,i}>0$ and $a_{i-1,i}<0$. Now there are two possibilities for $a_{i+2,i}$, which corresponds to $t_i$. It can be greater or smaller than zero.

• $a_{i+2,i}<0$:
  In this case it is obvious that only the payoff of the $(i+1)$-st strategy is increasing and for some $\tilde{t}$

  $${(A\mathbf{x}(\tilde{t}))}_i={(A\mathbf{x}(\tilde{t}))}_{i+1}>{(A\mathbf{x}(\tilde{t}))}_{i+2,i+3}$$

  which means that $\mathbf{x}(\tilde{t})\in B^{i,i+1}$ or in other words the best response is not unique at this moment. To find out the possible solutions we have to look at the restricted game in which only these strategies are used, which are best replies at the moment. The orbit can move in the direction of any Nash equilibrium of this restricted game ${A|}_{lm}=(a_{lm}),l,m=i,i+1$.
  This restricted game ${A|}_{lm}$ has only one Nash equilibrium $E_{i+1}$ (because of (9) and (10)). Thus the path can only be continued in one way, so $\mathbf{x}(t)$ enters $B^{i+1}$, which means that the solution stays unique.
• $a_{i+2,i}>0$:
  By (11) we know that in this case $a_{i,i+2}<0$ must hold. Now three strategies can become best replies which means that we have three possibilities

  −

  $\mathbf{x}(\tilde{t})\in B^{i,i+1}$

  as before $\mathbf{x}(t)\in B^{i+1}$ for $t>\tilde{t}$.

  −

  $\mathbf{x}(\tilde{t})\in B^{i,i+2}$

  as before $\mathbf{x}(t)$ enters $B^{i+2}$ for $t>\tilde{t}$.

  −

  $\mathbf{x}(\tilde{t})\in B^{i,i+1,i+2}$

  We have to look at the restricted 3×3 game and check for all possible Nash equilibria. The matrix has the following sign pattern.

  $$A_{i,i+1,i+2}=\left(\begin{array}{ccc}{a}_{ii}=0& a_{i,i+1}<0& a_{i,i+2}<0\\ a_{i+1,i}>0& a_{i+1,i+1}=0& a_{i+1,i+2}<0\\ a_{i+2,i}>0& a_{i+2,i+1}>0& a_{i+2,i+2}=0\end{array}\right)$$

  so it is easy to see that this game has also only one Nash equilibrium (the pure strategy $i+2$). Hence the solution $\mathbf{x}(t)$ remains unique and enters $B^{i+2}$.

To show the second part of the lemma we first assume that $T=\infty$ then we know from Lemma 1 that $\mathbf{x}(t)$ converges to the set $V_0$. Now assume that $T<\infty$. Using Lemma 8 (see below) we know that the orbit $\mathbf{x}(t)$ ultimately follows only one better reply cycle. We distinguish between the following two cases.

• The orbit follows the cycle 1234 for $t<T$.
  We show that in this case the interior Nash equilibrium is reached in finite time. Take the sequence $\mathbf{x}(t_k)$ of turning points (note that at these points at least two strategies have the same payoff), then the sequence $t_k$ converges to T. The map $t\mapsto {\left(A\mathbf{x}(t)\right)}_i$ is continuous for $i=1,\dots ,4$. As the orbit follows the cycle 1234 along one cycle of the orbit the payoff of each strategy is equal to its successor, so because of continuity as the difference between $t_k$ and $t_{k+1}$ can be chosen arbitrarily small, the difference between the different payoffs gets also arbitrarily small. Thus for $t=T$ all payoffs must be equal. This means that all strategies have the same payoff after finite time. It is not possible to reach the boundary (from $\text{int}{\Delta }_n$) so the orbit must reach an interior Nash equilibrium in finite time. To make this verbal argument more precise take a sequence of $t_{1k}$ such that ${(A\mathbf{x})}_1={(A\mathbf{x})}_2$ holds and $t_{2k}$ such that ${(A\mathbf{x})}_2={(A\mathbf{x})}_3$ and so on. Each of these sequences $t_{ik},i=1,2,3,4$ converges to T and hence at T the payoffs for all strategies must be equal.
• The orbit follows the cycle 123 (which we can choose without loss of generality). Note that this can only happen if the 123 better reply cycle exists, e.g. $t_1<0$ and $t_3>0$. We can use the same argument as for the cycle 1234 that for $\mathbf{x}(T)$ at least strategies 123 must have the same payoff. This means that at $\mathbf{x}(T)$ the following holds

  $${\mathbf{e}}_1·A\mathbf{x}={\mathbf{e}}_2·A\mathbf{x}={\mathbf{e}}_3·A\mathbf{x}\ge {\mathbf{e}}_4·A\mathbf{x}$$
  If all strategies have the same payoff a Nash equilibrium is reached, so we assume now that we reach a point $\mathbf{x}(T)$, where only 123 are the best replies. To continue the orbit, we have to look at the restricted game ${A|}_{123}$. It follows from assumptions (9)-(11) that this is an RSP game. Thus if $\text{supp}\left(\mathbf{x}(T)\right)=123$, then the orbit has reached a Nash equilibrium. This can only happen if the starting point of the orbit was already in the 123 face.
  If $\text{supp}\left(\mathbf{x}(T)\right)\ne 123$ then the orbit moves towards the unique Nash equilibrium of the RSP game. Along this movement the payoff of strategies 123 change at the same rate, only the payoff of strategy 4 changes differently. Therefore the orbit either hits an interior Nash equilibrium (if it exists) or converges to the unique Nash equilibrium of the RSP game (which is also a Nash equilibrium of the full game). This means we either get $\mathbf{x}(T)=N_{1234}$ or $\mathbf{x}$ moves towards $N_{123}$.

Remark 

We can formulate the last statement in the proof above a bit stronger. Suppose T is finite and the orbit $\mathbf{x}(t)$ follows the 123 cycle and reaches at time T a point $\mathbf{p}$ with payoff $A\mathbf{p}=\left(a,a,a,b\right)$ with $a>b$, then the orbit reaches an interior Nash equilibrium $N_{1234}$ if and only if the Nash equilibrium $N_{123}$ of the restricted RSP game ${A|}_{123}$ is no Nash equilibrium of the full game. This follows directly from the fact that the payoff of the fourth strategy changes differently to the payoff of the strategies 123.

Lemma 8

An orbit $\mathit{x}(t)$ can switch between better reply cycles at most once.

Proof 

We show this without loss of generality for the 123 and 1234 cycles. First note that for the possibility to switch between these two better reply cycles, there must be some orbits, which follow the 123 cycle and some orbits which follow the 1234 cycle. Now let $\mathbf{x}$ be an orbit, which follows the 123 (at least once). Hence this orbit must cross the sets $B^{12}$, $B^{23}$ and $B^{31}$. Now let $\mathbf{y}$ be an orbit which follows 1234. This orbit must cross the sets $B^{12}$, $B^{23}$, $B^{34}$ and $B^{14}$. If we start in $B^{23}$ then 31 and 34 can become best replies. Thus there is a subset of $B^{23}$ which is mapped to $B^{134}$, which is a one dimensional set by our assumption that A is generic. Hence the preimage of $B^{134}$ on $B^{23}$ is a line segment s. The orbits starting in s and moving to $B^{134}$ span a plane P in $B^3$, which separates the orbits that follow the 123 cycle and the orbits that follow 1234. Because of the uniqueness of solutions in each $B^i$ this plane P can only be crossed in one way and hence switching between cycles is only possible once.

An immediate consequence of this lemma is

Corollary 9

For a matrix fulfilling (8) no chaotic behaviour can occur.

The results for the RSP game with respect to $V_0$ possibly gives rise to the idea that the behaviour is identical for a $4\times 4$ payoff matrix in the sense that if $V_0$ is not empty it is already an attractor. The following example 6 shows that the set $V_0$ in general neither has to be attracting nor invariant. It is possible to enter or leave this set in finite time.

Example 6

We take the following payoff matrix

$$\begin{array}{c}\hfill A=\left(\begin{array}{cccc}0& -1& 1& \frac{1}{16}\\ 1& 0& -8& \frac{1}{4}\\ -1& 3& 0& -\frac{1}{10}\\ -\frac{1}{7}& -2& 5& 0\end{array}\right)\end{array}$$

(15)

This payoff matrix has a unique Nash equilibrium $N_{1234}=\left(\frac{21}{631},\frac{162}{3155},\frac{88}{3155},\frac{560}{631}\right)$ with

$$V(N_{1234})=N_{1234}·A{N}_{1234}=\frac{101}{3155}>0$$

but the minimum of $V(\mathit{x})$ is attained at $\widehat{\mathit{x}}=\left(\frac{77}{111},\frac{118}{555},\frac{52}{555},0\right)$ with $V(\widehat{\mathit{x}})=-\frac{31}{555}$. The results from Theorem 6 above show that almost all orbits converge to the interior Nash equilibrium.

Figure 2. The set $V_0$ is shown by the green pyramid. The red orbit connects $\widehat{\mathbf{x}}$, the top of the pyramid, the Nash equilibrium $N_{1234}$ and the target point $N_{234}$ for the line segment spanned s by $\widehat{\mathbf{x}}$ and $N_{1234}$.

Figure 2. The set $V_0$ is shown by the green pyramid. The red orbit connects $\widehat{\mathbf{x}}$, the top of the pyramid, the Nash equilibrium $N_{1234}$ and the target point $N_{234}$ for the line segment spanned s by $\widehat{\mathbf{x}}$ and $N_{1234}$.

But besides the result from this theorem we can give a complete description of this game. The set $V_0$ is a pyramid with top $\mathbf{p}=\left(43/157,121/1099,57/1099,620/1099\right)$. At this point the payoff vector $A\mathbf{p}$ is of the form $\left(-w,0,0,0\right)$ where $w>0$. This means the trajectory starting at $\mathbf{p}$ continues towards the unique Nash equilibrium $N_{234}$ of the restricted 234 game $N_{234}=\left(0,51/1180,29/1180,55/59\right)$. (Note that $N_{234}$ is not a Nash equilibrium of the full game!) Inside the pyramid $V(\mathbf{x})<0$ holds and outside the pyramid $V(\mathbf{x})>0$ holds. So every orbit that starts inside the pyramid reaches the line segment s (spanned by $\widehat{\mathbf{x}}$ and $N_{1234}$) in finite time, where 234 are the best replies. (This means the orbit reaches a point, where its payoff vector is of the form $\left(-b,-a,-a,-a\right)$, with $b>a$). In s the orbit moves towards $N_{234}$, passes $\mathbf{p}$ and reaches $N_{1234}$ in finite time. Close to s the dynamics is the same as for an RSP game with attracting Nash equilibrium.

Every orbit that starts in $V_0$ spirals (following the cycle 234) towards $\mathbf{p}$ and reaches it in finite time, but after an infinite number of turning points! Then again the orbit reaches $N_{1234}$ in finite time. Orbits outside the pyramid behave similar to the orbits inside, they spiral towards s reach it in finite time and thus reach the Nash equilibrium $N_{1234}$ in finite time. In this example every orbit reaches $N_{1234}$ in finite time. Therefore $N_{1234}$ is globally asymptotically stable.

6. Construction and Properties of the Return Map

The previous example showed that the analysis of the set $V_0$ is not sufficient to analyse $4\times 4$ games. So another tool is needed. We will introduce the concept of Poincaré or –also called– return maps in this section. We just give a rough concept, which should be made intuitively clear by figure 3 below. For more detailed information and all the technical assumptions needed see for example [6]. To create a return map we simply take a cross-section and a starting point $\mathbf{p}$ in this cross-section. We now follow the orbit $\mathbf{p}(t)$ until it returns to the cross section for the first time. We denote this new point in the cross section by ${\mathbf{p}}^{\prime }$. The map $\mathbf{p}\mapsto {\mathbf{p}}^{\prime }$ is called the return map. This map can be used to find periodic orbits, fixed points and to check their stability.

Figure 3. A simplified drawing of the kind of return map we will use below.

Figure 3. A simplified drawing of the kind of return map we will use below.

We will use a set $B^{i-1,i}$ as the cross-section and hence this set is the domain for our return map (which will be defined later). Since solutions are piecewise linear it is not possible to calculate the return map at once. Instead of doing so we have to calculate four transitions maps and glue them together to obtain a return map. First we have to find a proper parametrisation of our four cross-sections. (These cross-sections are simply given by $B^{12}$, $B^{23}$, $B^{34}$ and $B^{41}$ which correspond to the cycle given by the structure of the matrix.) It turns out that the following parametrisation of the set $B^{i-1,i}$ is very useful

$$\begin{array}{c}\hfill \mathbf{m}=\left(m_j\right)=({(A\mathbf{x})}_i-{(A\mathbf{x})}_j)\mathrm{for}\mathbf{x}\in B^{i-1,i}\end{array}$$

(16)

We get $\mathbf{m}\ge 0$. Without loss of generality we assume that $\mathbf{m}\ne \mathbf{0}$ (if $\mathbf{m}=\mathbf{0}$ then $\mathbf{x}$ is an interior Nash equilibrium as all payoffs are equal there. This parametrisation can be interpreted as an incentive function, since it measures the relative success of strategy i compared to all others.) Hence the domain for our special parametrisation is a convex subset of ${\mathbb{R}}_{+}^4$ or is empty, which means that no orbit follows the full cycle.

We calculate the transition from $B^{i-1,i}\to B^{i,i+1}$. We do this by calculating the time it takes a point from the inset $B^{i-1,i}$ to reach the outset $B^{i,i+1}$.

Remark 

The terminology in- and outset is chosen since the set $B^i$ can be entered through $B^{i-1,i}$ and can be left through $B^{i,i+1}$. Note that these need not be the only ways to enter or leave the set $B^i$.

6.1. Proof of Lemma 2

Proof 

To improve the readability of the proof we prove this exemplarily for an orbit from $B^{41}$ to $B^{12}$. So we start with a point $\mathbf{x}\in B^{41}$ and parametrise it as in 16. Since 4 and 1 are the best replies the orbit moves towards 1. For $t\ge 0$ small enough the following holds:

$$\begin{array}{c}\hfill A\mathbf{x}(t)=e^{-t}A\mathbf{x}+(1-e^{-t})A{\mathbf{e}}_1\end{array}$$

(17)

We assume now that 2 becomes the next best reply. We have to solve

$$\begin{array}{c}\hfill {(A\mathbf{x}(t))}_1={(A\mathbf{x}(t))}_2\end{array}$$

(18)

for (17). The solution can be easily calculated and is given by

$$\begin{array}{c}\hfill e^{-t^{*}}=\frac{e_1}{e_1+{(A\mathbf{x})}_1-{(A\mathbf{x})}_2}\end{array}$$

(19)

where $t^{*}$ represents the transition time from $B^{41}$ to $B^{12}$. So we get the following mapping for $\mathbf{m}$:

$$\mathbf{m}=\left(\begin{array}{c}0\\ {(A\mathbf{x})}_1-{(A\mathbf{x})}_2\\ {(A\mathbf{x})}_1-{(A\mathbf{x})}_3\\ 0\end{array}\right)\mapsto \lambda \left(\begin{array}{c}0\\ 0\\ e_1\left({(A\mathbf{x})}_1-{(A\mathbf{x})}_3)-t_1({(A\mathbf{x})}_1-{(A\mathbf{x})}_2\right)\\ c_1\left({(A\mathbf{x})}_1-{(A\mathbf{x})}_2)\right)\end{array}\right)={\mathbf{m}}^{\prime }$$

with $\lambda =\frac{e_1}{e_1+{(A\mathbf{x})}_1-{(A\mathbf{x})}_2}$. Clearly we get ${\mathbf{m}}^{\prime }\ge 0$. As there are two zeros in this map it is possible to interpret this map as a two dimensional map, if we set $u/e_1={(A\mathbf{x})}_1-{(A\mathbf{x})}_2$ and $v/e_1={(A\mathbf{x})}_1-{(A\mathbf{x})}_3$ and $\mathbf{u}=(u,v)$ we obtain the following:

$$\begin{array}{c}\hfill f:\left(\begin{array}{c}u\\ v\end{array}\right)\mapsto \frac{1}{1+\frac{u}{e_1^2}}\left(\begin{array}{c}v-\frac{t_1}{e_1}u\\ \frac{c_1}{e_1}u\end{array}\right)\end{array}$$

(20)

This map (20) is of the form:

$$\begin{array}{c}\hfill T_1(\mathbf{u}):=\frac{P_1\mathbf{u}}{1+{\mathbf{d}}_1·\mathbf{u}},T_1:B^{41}\to B^{12}\end{array}$$

It is easy to see that for a arbitrary map $T_i$ from $B^{i-1,1}$ to $B^{i,i+1}$ we get

$$\begin{array}{c}\hfill P_i=\left(\begin{array}{cc}-t_i/e_i& 1\\ c_i/e_i& 0\end{array}\right),{\mathbf{d}}_i=\left(\begin{array}{c}1/e_i^2\\ 0\end{array}\right)\end{array}$$

(21)

where $P_i$ is called the transition matrix. This map is projective map and properties of such maps can be found in Section 6.3 including that the composition of two projective maps is again a projective map (this follows directly from (31)). Glueing (via a composition) four transition maps together gives us the return map $\Pi (\mathbf{u})$ from $B^{41}$ to itself by

$$\begin{array}{c}\hfill \Pi (\mathbf{u})=\frac{P\mathbf{u}}{1+\mathbf{d}·\mathbf{u}}\end{array}$$

(22)

where $P=P_4{P}_3{P}_2{P}_1$ and $\mathbf{d}$ are given by

$$\begin{array}{cc}\hfill P& =\frac{1}{e}\left(\begin{array}{cc}{c}_1{c}_3{e}_2{e}_4+c_3{e}_4{t}_1{t}_2-t_4{\Sigma }_1& e_1{\Sigma }_2\\ c_4{\Sigma }_1& {\Sigma }_3\end{array}\right)\hfill \end{array}$$

(23)

$$\begin{array}{cc}\hfill \mathbf{d}& =\left(\begin{array}{c}{d}_1\\ d_2\end{array}\right)=\left(\begin{array}{c}\frac{1}{e_1^2}+\frac{c_1}{e_1{e}_3^2}-\frac{t_1}{e_1{e}_2^2}-\frac{c_2{t}_1}{e_1{e}_2{e}_4^2}+\frac{t_1{t}_2}{e_1{e}_2{e}_3^2}-\frac{c_1{t}_3}{e_1{e}_3{e}_4^2}-\frac{t_1{t}_2{t}_3}{e_1{e}_2{e}_3{e}_4^2}\\ \frac{1}{e_2^2}+\frac{c_2}{e_2{e}_4^2}-\frac{t_2}{e_2{e}_3^2}+\frac{t_2{t}_3}{e_2{e}_3{e}_4^2}\end{array}\right)\hfill \end{array}$$

(24)

6.2. A Necessary Condition for Shapley Polygons

The important property of the return map Π is that its fixed points either correspond to an interior fixed point (Nash equilibrium) or to a periodic orbit (Shapley polygon) for the best response dynamics. More precisely, the origin $\mathbf{0}\in {\mathbb{R}}_{+}^2$ corresponds to an interior Nash equilibrium and every other fixed point in $B^{41}$ to a Shapley polygon. To find a fixed point of Π we have to solve the equation

$$\begin{array}{c}\hfill \mathbf{u}=\frac{P\mathbf{u}}{1+\mathbf{d}·\mathbf{u}}\end{array}$$

(25)

which is simply an eigenvalue problem

$$\begin{array}{c}\hfill (1+\mathbf{d}·\mathbf{u})\mathbf{u}=P\mathbf{u}\end{array}$$

Note that the vector $\mathbf{m}$ in (16) is nonnegative. Hence for a full cycle a nonnegative vector must be mapped onto a nonnegative vector under the return map Π. If this is not possible no orbit follows the full cycle. The following corollary follows directly

Corollary 10

A Shapley polygon following the full cycle can only exist if the return matrix P in Equation (13) has a nonnegative eigenvector.

Proof 

A Shapley polygon corresponds to a fixed point for the return map Π in (13). This fixed point is an eigenvector of P by (25) and only nonnegative vectors can correspond to the set $B^{41}$, where the return map initially started.

We state some general results for a certain class of two by two matrices T from [3]. In [3] these are conditions that the replicator equation has a relatively asymptotically stable heteroclinic cycle following the full better reply cycle, whereas for the best response dynamics they are necessary conditions for an attracting interior Nash equilibrium or the existence of an interior Shapley polygon.

Lemma 11

Let ${\Sigma }_1=-(c_1{e}_2{t}_3+c_2{e}_3{t}_1+t_1{t}_2{t}_3)$, ${\Sigma }_2=-(c_2{e}_3{t}_4+c_3{e}_4{t}_2+t_2{t}_3{t}_4)$, $e=\Pi e_i$, $c=\Pi c_i$ and $q={\left(\sqrt{e}-\sqrt{c}\right)}^2$ and let P as in (13) and assume that $p_{ij}\ne 0$ for all $i,j=1,2$ and that $p_{11}\ne p_{22}$. Then P has a positive eigenvalue ${\lambda }_{+}$ with a corresponding positive eigenvector ${\mathit{u}}_{+}$ if and only if one of the following statements hold

$$\begin{array}{cc}\hfill (i)& {\Sigma }_1>0,{\Sigma }_2>0anddet(A)\ge -q\hfill \end{array}$$

(26)

$$\begin{array}{cc}\hfill (ii)& {\Sigma }_2<0,{\Sigma }_1>0anddet(A)>max\{e-c-2e_1{A}^{(21)},-q\}\hfill \end{array}$$

(27)

$$\begin{array}{cc}\hfill (iii)& {\Sigma }_2>0,{\Sigma }_1<0anddet(A)>max\{e-c+2t_4{A}^{(24)}-2e_4{A}^{(14)},-q\}\hfill \end{array}$$

(28)

where $A^{(ij)}$ is the determinant of the matrix we obtain by omitting the ith row and the jth column in A. Additionally for the eigenvalue ${\lambda }_{+}$ holds ${\lambda }_{+}>1$ iff

$$\begin{array}{cc}\hfill (a)det(A)>0& \text{or}(b)e<c\hfill \end{array}$$

(29)

6.3. Projective Geometry and Fractional Linear Maps

The next step is to analyse the behaviour if the iteration of the return map. This can lead to technical difficulties because (22) cannot be defined for all $\mathbf{x}\in {\mathbb{R}}^2$. So before we start with the analysis of the concrete return map as described in Section 2 we give some general results on fractional linear maps of the form

$$\begin{array}{c}\hfill \Pi (\mathbf{x}):=\frac{P\mathbf{x}}{1+\mathbf{d}·\mathbf{x}},\Pi (\mathbf{x}):{\mathbb{R}}^2\setminus \left\{\mathbf{x}\in {\mathbb{R}}^2:\mathbf{d}·\mathbf{u}=-1\right\}\to {\mathbb{R}}^2\end{array}$$

(30)

where $P=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$, $\mathbf{d}=\left(\begin{array}{c}{d}_1\\ d_2\end{array}\right)$ with $det(P)\ne 0$. (We also implicitly assume that the matrix P has no entry equal to zero. The results would not differ, but else the proofs would contain a lot of cases.)

Maps of this form are also called central projections or projective maps. We have already mentioned in Section 6.2 that a nonnegative vector has to mapped onto a nonnegative vector. Consequently we have to find conditions under which an invariant set in ${\mathbb{R}}_{+}^2$ exists. If there is no such set no orbit can follow the full cycle infinitely many often hence no Shapley polygon in the interior can exist. We also know from Section 6.2 the fixed points of (22) to study their stability we have to analyse ${\Pi }^n(\mathbf{x})=\Pi \circ \Pi \circ \dots \circ \Pi (\mathbf{x})$.

To do so we use projective geometry, for more details about projective geometry see [11]. We use homogenous coordinates and get the following: If $x_0\ne 0$ then $\left(x_0,x_1,x_2\right)\sim \left(1,\frac{x_1}{x_0},\frac{x_2}{x_0}\right)$. These points are called regular and this method creates a bijective mapping from the regular points in ${\mathbb{P}}^2$ to ${\mathbb{R}}^2$. Points with $x_0=0$ are called points at infinity and the set of all $\left(0,x_1,x_2\right)$ is called the line at infinity. With this concept we can write the two dimensional fractional linear map Π from (30) in the following form

$$\begin{array}{c}\hfill \mathcal{T}:{\mathbb{P}}^2\mapsto {\mathbb{P}}^2,\mathcal{T}(\mathbf{x})=\mathcal{T}\mathbf{x}=\left(\begin{array}{ccc}1& d_1& d_2\\ 0& a& b\\ 0& c& d\end{array}\right)\left(\begin{array}{c}{x}_0\\ x_1\\ x_2\end{array}\right)\end{array}$$

(31)

In this map $\mathcal{T}$ the real points which satisfy $1+d_1{x}_1^{\prime }+d_2{x}_2^{\prime }=0$ (with $x_1^{\prime }=x_1/x_0$ and $x_2^{\prime }=x_2/x_0$) are mapped to the line at infinity. We denote with $\mathcal{T}$ both the matrix and the map, but as the map is only a matrix times a vector, there is no problem in doing so. This map is a block triangular matrix and hence the product of two such matrices is again a block triangular matrix. This gives any easy proof that the composition of two central projections is again a central projection. Any line $\widehat{l}$ with starting point $\left(x_1,x_2\right)$ and direction $\left(l_1,l_2\right)$

$$\widehat{l}:X=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)+\mu \left(\begin{array}{c}{l}_1\\ l_2\end{array}\right)$$

in ${\mathbb{R}}^2$ can be embedded in ${\mathbb{P}}^2$ in the following form

$$l:X=\left(\begin{array}{c}1\\ x_1\\ x_2\end{array}\right)+\mu \left(\begin{array}{c}0\\ l_1\\ l_2\end{array}\right)$$

(32)

Here l from (32) contains only regular points which exactly correspond to the points defined by $\widehat{l}$. A map through the origin in ${\mathbb{R}}^2$ is mapped under $\mathcal{T}$ to

$$\begin{array}{c}\hfill \mathcal{T}l=\left(\begin{array}{c}{d}_1{l}_1\mu +d_2{l}_2\mu +1\\ \mu (a{l}_1+b{l}_2)\\ \mu (c{l}_1+d{l}_2)\end{array}\right)\end{array}$$

To calculate which lines in ${\mathbb{R}}^2$ embedded in ${\mathbb{P}}^2$ are invariant, we simply have to calculate the eigenvectors of P (not of $\mathcal{T}$! But note that if we project the eigenvectors of $\mathcal{T}$ onto their second and third component, we get the eigenvectors of P and the origin in ${\mathbb{R}}^2$.). These eigenvectors $u_{+,-}$ are given by (note that we assumed in the beginning of this section that the matrix has no zero entry and its determinant is also not zero!)

$$\begin{array}{c}\hfill {\mathbf{u}}_{+,-}=\left(\frac{a-d\pm \sqrt{\mathrm{tr}{(P)}^2-4det(P)}}{2c},1\right)=k\left(1,\frac{a-d\mp \sqrt{\mathrm{tr}{(P)}^2-4det(P)}}{2b}\right)\end{array}$$

(33)

with $k\in \mathbb{R}$ and their corresponding eigenvalues

$$\begin{array}{c}\hfill {\lambda }_{+,-}=\frac{1}{2}\left(\mathrm{tr}(P)\pm \sqrt{\mathrm{tr}{(P)}^2-4det(P)}\right)\end{array}$$

(34)

chosen such that $|{\lambda }_{+}|\ge |{\lambda }_{-}|$. We are only interested in real eigenvalues and hence we assume for all following considerations

$$\begin{array}{c}\hfill \mathrm{tr}{(P)}^2-4det(P)>0\end{array}$$

(35)

which means that one (and hence both) eigenvalue is real. Note that due to the block form of the matrix $\mathcal{T}$ its eigenvalues are given by 1 and the eigenvalues of P. We also get from (35) that P is similar to a diagonal matrix and as a consequence we get that $\mathcal{T}$ is similar to (a matrix we will also call $\mathcal{T}$)

$$\mathcal{T}=\left(\begin{array}{ccc}1& d_1& d_2\\ 0& {\lambda }_{+}& 0\\ 0& 0& {\lambda }_{-}\end{array}\right)$$

(36)

It is easy to see (by induction) that

$${\mathcal{T}}^n\mathbf{x}=\left(\begin{array}{c}{x}_1+d_1\sum _{j=0}^{n-1}{\lambda }_{+}^j{x}_2+d_2\sum _{j=0}^{n-1}{\lambda }_{-}^j{x}_3\\ {\lambda }_{+}^n{x}_2\\ {\lambda }_{-}^n{x}_3\end{array}\right)\sim \left(\begin{array}{c}1\\ \frac{{\lambda }_{+}^n{x}_2}{N}\\ \frac{{\lambda }_{-}^n{x}_3}{N}\end{array}\right)$$

(37)

where $N=x_1+d_1{\sum }_{j=0}^{n-1}{\lambda }_{+}^j{x}_2+d_2{\sum }_{j=0}^{n-1}{\lambda }_{-}^j{x}_3$ and hence ${\mathcal{T}}^n\mathbf{x}\to \left(1,0,0\right)Ê$ for $n\to \infty$, if $|{\lambda }_{+,-}|\le 1$. This means if the absolute value of both eigenvalues of P is smaller than or equal to 1, the iteration of the map Π in (30) leads to convergence to the origin. If we use that

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}{\lambda }_{+}^{-n}{\mathcal{T}}^n\mathbf{x}=k{\mathbf{u}}_{+}^{*}\end{array}$$

(38)

where ${\mathbf{u}}_{+}^{*}$ is the equivalent (or the regular point corresponding to ${\mathbf{u}}_{+}$) of ${\mathbf{u}}_{+}$ in ${\mathbb{P}}^2$ and $k\in \mathbb{R}$ and $\mathbf{x}$ is an arbitrary vector, but not in $span\{\left(1,0,0\right),{\mathbf{u}}_{-}^{*}\}$ (this set corresponds to the eigenspace $E({\lambda }_{-})$ in ${\mathbb{R}}^2$) and $|{\lambda }_{+}|>max\left\{1,|{\lambda }_{-}|\right\}$ holds, we get that all vectors $\mathbf{x}$, which are not eigenvectors, converge to the eigenspace of the eigenvalue with greatest absolute value. (This can be seen easily by using the fact that $\mathcal{T}$ is diagonalizable.) It follows from (35) that $\mathcal{T}$ has 3 different eigenvalues and hence three different eigenvectors. These eigenvectors are regular points in ${\mathbb{P}}^2$ and therefore corresponding to points in ${\mathbb{R}}^2$ and hence the map Π has three fixed points if ${\lambda }_{+,-}>0$ holds and each line connecting two of these fixed points is invariant under the map Π. More precisely, one eigenvector of $\mathcal{T}$ corresponds to the origin in ${\mathbb{R}}^2$ and hence two of these three invariant lines correspond to the eigenspaces $E({\lambda }_{+})$ and $E({\lambda }_{-})$ of P. The third invariant line connects the fixed points inside these eigenspaces and is generically disjoint from the origin. This third line corresponds to the set $V_0$ for the best response dynamics.

Proposition 12

Let $det(P)>0$ and ${\lambda }_{+}>1$ then all $\mathit{x}\in {\mathbb{P}}^2$ (except the two different eigenvectors of $\mathcal{T}$) converge to the fixed point in $E({\lambda }_{+})$ in a monotone way. If $0<{\lambda }_{+}\le 1$ all $\mathit{x}\in {\mathbb{P}}^2$ converge to the origin.

Proof 

Convergence properties follow from (38) and from $det(P)>0$ (both eigenvalues are positive) follows $det(\mathcal{T})>0$ and hence $\mathcal{T}$ is orientation preserving and convergence is monotone.

Corollary 13

It is impossible for an attracting interior Nash equilibrium $N_{1234}$ and an interior Shapley polygon to exist simultaneously.

Proof 

An interior Shapley polygon only exists if the dominating eigenvalue ${\lambda }_{+}$ is greater than 1. Conversely $N_{1234}$ is only attracting (with respect to the orbits that follow the 1234 cycle) if ${\lambda }_{+}$ is smaller or equal 1.

6.4. The Domain of the Return Map

Definition 5

A strategy $\mathit{y}$ is called dominated if there exists $\mathit{p}\in {\Delta }_n$ such that

$$\sum _{i=1}^n{p}_i{a}_{ij}\ge \sum _{i=1}^n{y}_i{a}_{ij}$$

for all $j=1,\dots ,n$ and inequality is strict for one j. If inequality is strict for all j then $\mathit{y}$ is called strictly dominated.

Finally we define the domain of the return map in the following way

$$\begin{array}{c}\hfill \Pi (\mathbf{u})=\frac{P\mathbf{u}}{1+\mathbf{d}·\mathbf{u}},D\to B^{14}\end{array}$$

(39)

where

$$\begin{array}{c}\hfill D=\overline{\left\{\mathbf{u}\in B^{14}:\frac{P\mathbf{u}}{1+\mathbf{d}·\mathbf{u}}\in B^{14}\right\}}\end{array}$$

(40)

A crucial point is to show that D is not empty. To do this we use the proof of a theorem from [6] (page 90, Theorem 8.3.2). We directly get the following

Lemma 14

Let $\mathit{x}\in \text{int}{\Delta }_n$ if ${\mathit{e}}_k$ is contained in the ω-limit $(\mathit{x}(t))$ for (2) then k cannot be a dominated strategy.

The lemma above shows that if the replicator equation has a heteroclinic cycle following the cycle 1234,which attracts an interior orbit, then no strategy can be dominated. Hence, whenever P has a positive eigenvector then D is not empty! This follows directly by Lemma 11. In [3] the conditions from Lemma 11 guarantee the existence of a relatively asymptotically heteroclinic cycle following the cycle 1234. Hence at least one interior orbit is attracted by this heteroclinic cycle.

6.5. Shapley Triangles in 4×4 Games

This section does not apply the methods of the return maps. We constructed the return map to analyse orbits that follow the full cycle. But as we are interested in games with embedded RSP cycle we have to find conditions under which these RSP cycles form have a Shapley triangle. It turns out that a direct approach is easier than an approach via return maps to find this conditions.

Definition 6

If the payoffs of all unused strategies along a Shapley polygon are negative, the Shapley polygon is called regular.

Proposition 15

Given a payoff matrix A as in (8) then

• The 123 cycle has an asymptotically stable regular Shapley polygon, iff all of the following conditions are satisfied

  (i) 

  $t_3>0,t_1<0$,

  (ii) 

  $e_1{e}_2{t}_3<|t_1|c_2{c}_3$ and

  (iii) 

  ${\Sigma }_1=-(c_1{e}_2{t}_3+c_2{e}_3{t}_1+t_1{t}_2{t}_3)<0$.

• The 234 cycle has an asymptotically stable regular Shapley polygon, iff all of the following conditions are satisfied

  (i) 

  $t_4>0,t_2<0$,

  (ii) 

  $e_2{e}_3{t}_4<|t_2|c_3{c}_4$ and

  (iii) 

  ${\Sigma }_2=-(c_2{e}_3{t}_4+c_3{e}_4{t}_2+t_2{t}_3{t}_4)<0$.

Proof 

We take the following payoff matrix

$$\begin{array}{c}\hfill \tilde{A}=\left(\begin{array}{cccc}0& -b_2& a_3& d_1\\ a_1& 0& -b_3& d_2\\ -b_1& a_2& 0& d_3\\ s_1& s_2& s_3& 0\end{array}\right)\end{array}$$

(41)

This is a rock-scissors-paper game, if we take $\tilde{A}{|}_{\{123\}}$. So we simply added a fourth arbitrary strategy to a typical RSP game. It is well known [6] that a Shapley polygon exists for the RSP game iff

$$\begin{array}{c}\hfill a_1{a}_2{a}_3<b_1{b}_2{b}_3\end{array}$$

(42)

holds. We will call the $s_i$s the transversal incentives since they are the positive or negative incentives to leave the 123 surface.

We denote the vertices of the Shapley polygon by $S_1,S_2$ and $S_3$. We need that ${(\tilde{A}{S}_i)}_4<0$ holds for $i=1,2,3$. Because 4 must not be the best reply to a vertex of the Shapley polygon as in this case the dynamics would leave the 123 surface and enter the interior of ${\Delta }_4$. This leads to the following inequalities:

$$\begin{array}{cc}\hfill b_2{b}_3{s}_1+a_1{a}_3{s}_2+b_2{a}_1{s}_3& <0\hfill \end{array}$$

(43)

$$\begin{array}{cc}\hfill b_3{a}_2{s}_1+b_1{b}_3{s}_2+a_1{a}_2{s}_3& <0\mathrm{and}\hfill \end{array}$$

(44)

$$\begin{array}{cc}\hfill a_2{a}_3{s}_1+b_1{a}_3{s}_2+b_1{b}_2{s}_3& <0\hfill \end{array}$$

(45)

Clearly one of the $s_i$ must be negative to fulfil these inequalities. We assume without loss of generality $s_1<0$ holds. Note that these inequalities are trivially fulfilled if $s_i<0$ holds for all $i=1,2,3$.

• Firstly assume that $s_3>0$ holds:
  Now suppose (44) holds. We get

  $$-a_2{s}_1>\frac{b_1{a}_3{s}_2+b_1{b}_2{s}_3}{a_3}$$

  and hence we obtain

  $$\begin{array}{c}\hfill -a_2{b}_3{s}_1>b_3·\frac{b_1{a}_3{s}_2+b_1{b}_2{s}_3}{a_3}=b_1{b}_3{s}_2+b_1{b}_2{b}_3·\frac{s_3}{a_3}>b_1{b}_3{s}_2+a_1{a}_2{s}_3\end{array}$$
  Hence (45) also holds.
  We also have (together with (42))

  $$\begin{array}{cc}\hfill b_2{b}_3>\frac{a_1{a}_2{a}_3}{b_1}& \text{and}-s_1>\frac{b_1{a}_3{s}_2+b_1{b}_2{s}_3}{a_2{a}_3}\hfill \end{array}$$

  so we get

  $$-b_2{b}_3{s}_1>\frac{a_1{a}_2{a}_3}{b_1}·\frac{b_1{a}_3{s}_2+b_1{b}_2{s}_3}{a_2{a}_3}=a_1{a}_3{s}_2+a_1{b}_2{s}_3$$

  and (43) also holds.
• Secondly assume that $s_2>0$ and $s_{1,3}<0$ hold.
  Suppose (44) holds. We have

  $$-s_2>\frac{b_3{a}_2{s}_1+a_1{a}_2{s}_3}{b_1{b}_3}$$
  We get

  $$-b_1{a}_3{s}_2>b_1{a}_3·\frac{b_3{a}_2{s}_1+a_1{a}_2{s}_3}{b_1{b}_3}=a_2{a}_3{s}_1+\frac{a_1{a}_2{a}_3{s}_3}{b_3}$$
  Since $s_3<0$ is satisfied we have (see (42))

  $$\begin{array}{cc}\hfill \frac{a_1{a}_2{a}_3}{b_3}& <b_1{b}_2\mathrm{and}\hfill \\ \hfill \frac{a_1{a}_2{a}_3{s}_3}{b_3}& >b_1{b}_2{s}_3\hfill \end{array}$$

  and (44) holds.
  We also have

  $$\begin{array}{cc}\hfill -a_1{a}_3& >-\frac{b_1{b}_2{b}_3}{a_2}\hfill \\ \hfill -s_2& >\frac{b_3{a}_2{s}_1+a_1{a}_2{s}_3}{b_1{b}_3}\hfill \end{array}$$

  so we get

  $$-a_1{a}_3{s}_2>\frac{b_1{b}_2{b}_3}{a_2}·\frac{b_3{a}_2{s}_1+a_1{a}_2{s}_3}{b_1{b}_3}=b_2{b}_3{s}_1+b_2{a}_1{s}_3$$

  and (43) holds. A simple relabelling of the payoffs proves the proposition.

7. A Complete Classification of the Attractors of Monocyclic 4×4 Matrix

This section splits up in two parts. The first part gives a complete classification of monocyclic payoff matrices and provides a connection of the global stability of the interior Nash equilibrium $N_{1234}$ for the best response dynamics and permanence for the replicator equation. The second part provides the very technical but necessary part on the properties of the payoff matrix.

7.1. Classification of the Asymptotical Behaviour

As shown in 6 the return map Π is of the following form

$$\Pi (\mathbf{u})=\frac{P\mathbf{u}}{1+\mathbf{d}·\mathbf{u}},B^{14}\to B^{14}$$

In the case of a monocyclic matrix we get $D=B^{14}$, as the transition matrices are nonnegative and as a consequence we get that $P>0$ (as a product of four nonnegative matrices) and $d>0$ (because of (24)) hold. Hence for the map ${\mathbb{R}}_{+}^2$ is invariant and as we have shown every $\mathbf{x}\in B^{14}$ returns to this set after one cycle in case our matrix is monocyclic (see Lemma 7). The remaining question is if there are any fixed points in ${\mathbb{R}}_{+}^2$ besides the origin $\mathbf{0}$.

To calculate the fixed points of Π we need to find the eigenvectors of the return matrix P. The Perron-Frobenius theorem states that P has a dominating eigenvalue ${\lambda }_{+}$ to a positive eigenvector ${\mathbf{u}}_{+}$ and that any other eigenvector $\mathbf{v}$ which is not in the eigenspace of ${\lambda }_{+}$, symbolically $\mathbf{v}\notin E({\lambda }_{+})$ is not positive. The remaining question is under which conditions ${\lambda }_{+}$ is greater or smaller than 1. The following theorem answers this question and provides a complete classification for monocyclic payoff matrices:

Proposition 16

For a monocyclic matrix (14) one of the following statements holds for the best response dynamics (1):

(i) 

${\lambda }_{+}<1\iff det(A)<0ande\ge c$: All orbits converge in finite time to the unique interior Nash equilibrium $N_{1234}$.

(ii) 

${\lambda }_{+}=1\iff det(A)=0ande>c$: All orbits converge (no longer in finite time) to the interior Nash equilibrium $N_{1234}$, which we will call a degenerated Shapley polygon.

(iii) 

${\lambda }_{+}>1\iff det(A)>0ore<c$: Almost all orbits converge to the interior Shapley polygon.

Proof 

First note that the classification is complete because $detA=0$ and $e=c$ cannot hold simultaneously as shown in Lemma 19 below. The statements about ${\lambda }_{+}$ follow directly from Lemma 11, because for a monocyclic matrix ${\Sigma }_{1,2}>0$ is automatically fulfilled. Convergence to $N_{1234}$ or an interior Shapley polygon follows from Proposition 12. The equivalence in (ii) follows from some easy calculations. In case of convergence to the interior Nash equilibrium $N_{1234}$ it remains to show that all orbits converge to it (not only those following the 1234 cycle). This follows from the uniqueness of the equilibrium by Lemma 18 below. Convergence in finite time in (i) is an application of Lemma 1. If convergence would not occur in finite time $V(\mathbf{x}(t))$ would go to zero, but $V\left(N_{1234}\right)>0$ holds.

In [6] (p. 178) it is shown that a system is permanent under the replicator equation (2) iff we obtain an M-matrix from A by moving the top row of A to the bottom. The following corollary contains the statements from Theorem 3 and provides a connection between M-matrices, permanence and the interior Nash equilibrium $N_{1234}$. It is a collection of statements in [6], Proposition 16 and Lemma 20 below.

Corollary 17

For a monocyclic matrix (14) the following statements are equivalent:

(i) 

For the best response dynamics (1) there exists no (degenerated) Shapley polygon.

(ii) 

For the best response dynamics all orbits converge in finite time to the interior Nash equilibrium $N_{1234}$

(iii) 

There is an interior Nash equilibrium $N_{1234}$ and $N_{1234}·A{N}_{1234}>0$.

(iv) 

For the replicator equation (2) the system is permanent.

(v) 

$det(A)<0$ and $e\ge c$ hold.

(vi) 

The matrix C obtained by moving the top row of A to the bottom is an M-matrix.

Remark 

As the examples in Section 4 show in the other cases the existence and stability of Nash equilibria is not so easy to predict. There are games, for which $det(A)>0$ holds, but they do not have an interior Nash equilibrium. These examples also show that in case of $e>c$ neither the existence of Nash equilibria on the boundary is guaranteed nor is the uniqueness of a Nash equilibrium guaranteed.

7.2. General Remarks on the Payoff Matrix

We start with a result on the interior Nash equilibrium.

Lemma 18

Let A be a generic monocyclic payoff matrix as in (14). Suppose $N_{1234}$ exists and $det(A)\le 0$ and $e>c$ hold then $N_{1234}$ is the unique Nash equilibrium of the game.

Proof 

First we show that no Nash equilibrium on the 13 or 24 face can exist. We show this only for the 24 face as the proof for the 13 face is the same (modulo some permutations of the indices).

We start with

$$F_{24}=\left(0,\frac{t_4}{t_2+t_4},0,\frac{t_2}{t_2+t_4}\right)$$

and calculate the payoffs there. We have to check, if ${(A{F}_{24})}_1<{(A{F}_{24})}_2$ and ${(A{F}_{24})}_3<{(A{F}_{24})}_2$ can hold simultaneously. Therefore we have to check if this system of inequalities has a solution.

$$\begin{array}{cc}\hfill (i)& e_1{e}_2{e}_3{e}_4-c_1{c}_2{c}_3{c}_4>0\hfill \end{array}$$

(46)

$$\begin{array}{cc}\hfill (ii)& det(A)\le 0\hfill \end{array}$$

(47)

$$\begin{array}{cc}\hfill (iii)& e_4{t}_2-c_2{t}_4\ge t_2{t}_4\mathrm{and}\hfill \end{array}$$

(48)

$$\begin{array}{cc}\hfill (iv)& e_2{t}_4-c_4{t}_2\ge t_2{t}_4\hfill \end{array}$$

(49)

First note that if (47) holds then also

$$\begin{array}{c}\hfill -c_1{c}_2{c}_3{c}_4+c_2{c}_4{e}_1{e}_3+c_1{c}_3{e}_2{e}_4-e_1{e}_2{e}_3{e}_4<0\end{array}$$

(50)

holds as we only omit positive terms. Similarly if (48) and (49) hold then

$$\begin{array}{cc}\hfill e_4{t}_2& \ge c_2{t}_4\mathrm{and}\hfill \end{array}$$

(51)

$$\begin{array}{cc}\hfill e_2{t}_4& \ge c_4{t}_2\hfill \end{array}$$

(52)

also hold. Combining these inequalities leads to the following system

$$\begin{array}{cc}\hfill (i)& c_2{c}_4{e}_1{e}_3+c_1{c}_3{e}_2{e}_4<e_1{e}_2{e}_3{e}_4+c_1{c}_2{c}_3{c}_4\hfill \end{array}$$

(53)

$$\begin{array}{cc}\hfill (ii)& c_2{c}_4\ge e_4{e}_2\mathrm{and}\hfill \end{array}$$

(54)

$$\begin{array}{cc}\hfill (iii)& e_1{e}_3\ge c_1{c}_3\hfill \end{array}$$

(55)

Now (53) can be transformed into

$$\begin{array}{c}\hfill e_2(c_1{c}_3{e}_4-e_1{e}_3{e}_4)<c_1{c}_2{c}_3{c}_4-c_2{c}_4{e}_1{e}_3\end{array}$$

(56)

using (55) for (56) we get

$$\begin{array}{c}\hfill e_2>\frac{c_2{c}_4}{e_4}\end{array}$$

(57)

which is a contradiction to (54). Hence $F_{24}$ cannot be a Nash equilibrium for the game. (Similarly it is impossible for $F_{13}$ to be a Nash equilibrium.)

The next step is to check all possible Nash equilibria $\mathbf{p}$ with $card(supp(\mathbf{p}))=3$. To do so we look at the restricted game 123. (The proof is the same for any other face). We assume that this restricted game has an interior equilibrium $N_{123}$. Now we use the index theorem (see for example [6] page 159). Clearly the pure strategy 3 is a Nash equilibrium of the restricted game, if there is also an interior equilibrium $N_{123}$ there must be a third equilibrium $N_{13}$. We now check the indices. We get

$$\begin{array}{cc}\hfill i({\mathbf{e}}_{\mathbf{3}})& =1\hfill \end{array}$$

(58)

$$\begin{array}{cc}\hfill i(N_{13})& =-1\hfill \end{array}$$

(59)

and hence $i(N_{123})=1$ (as the indices must sum up to 1). Every Nash equilibrium with $card(supp(\mathbf{p}))=3$ has index 1. As a consequence only three Nash equilibria can exist in the full game and the index of the interior Nash equilibrium must be $-1$. We will show that this leads to a contradiction. To do so we use that for a unique interior Nash equilibrium $N_{1234}$ the following holds (see [6] page 165)

$$\begin{array}{c}\hfill i(N_{1234})={(-1)}^{n-1}\mathrm{sgn}\frac{det(A)}{N_{1234}·A{N}_{1234}}={(-1)}^{n-1}\mathrm{sgn}det(A_n)\end{array}$$

(60)

where $A_n$ is the matrix we obtain if we replace the last column in A with the vector which entries are all 1. It turns out (see below) in case of $e>c$ that $A_n$ has the same sign as A and hence we get $i(N_{1234})=1$, which is a contradiction.

$$\begin{array}{c}\hfill det(A_n)=c_1{c}_2{c}_3-c_2{e}_1{e}_3-e_1{t}_2{t}_3+c_1{c}_3{e}_2-e_1{e}_2{e}_3+c_3{t}_1{t}_2+c_2{e}_3{t}_1+\\ \hfill +t_1{t}_2{t}_3+c_1{e}_2{t}_3+e_1{e}_2{t}_3+c_2{c}_3{t}_1\end{array}$$

Suppose now $det(A_n)$ is greater than zero then clearly also the following holds as we have only omitted negative terms

$$\begin{array}{c}\hfill c_1{c}_2{c}_3-c_2{e}_1{e}_3+c_1{c}_3{e}_2-e_1{e}_2{e}_3+c_3{t}_1{t}_2>0\end{array}$$

(61)

Again we get a system of inequalities

$$\begin{array}{cc}\hfill (i)& -c_1{c}_2{c}_3{c}_4+c_1{c}_3{e}_2{e}_4-e_1{e}_2{e}_3{e}_4+c_3{e}_4{t}_1{t}_2+c_2{c}_4{e}_1{e}_3<0\hfill \\ \hfill (ii)& c_1{c}_2{c}_3-c_2{e}_1{e}_3+c_1{c}_3{e}_2-e_1{e}_2{e}_3+c_3{t}_1{t}_2>0\mathrm{and}\hfill \\ \hfill (iii)& e_1{e}_2{e}_3{e}_4>c_1{c}_2{c}_3{c}_4\hfill \end{array}$$

We have to show that this system has no solution. We can transform this system into

$$\begin{array}{cc}\hfill (i)& c_2{c}_4(e_1{e}_3-c_1{c}_3)<e_4(-c_1{c}_3{e}_2+e_1{e}_2{e}_3-c_3{t}_1{t}_2)\hfill \\ \hfill (ii)& c_2{e}_4(c_1{c}_3-e_1{e}_3)>e_4(-c_1{c}_3{e}_2+e_1{e}_2{e}_3-c_3{t}_1{t}_2)\mathrm{and}\hfill \\ \hfill (iii)& e_1{e}_2{e}_3{e}_4>c_1{c}_2{c}_3{c}_4\hfill \end{array}$$

This system can be written as

$$\begin{array}{cc}\hfill (i)& c_2{c}_4(e_1{e}_3-c_1{c}_3)<e_4(-c_1{c}_3{e}_2+e_1{e}_2{e}_3-c_3{t}_1{t}_2)<c_2{e}_4(c_1{c}_3-e_1{e}_3)\mathrm{and}\hfill \end{array}$$

(62)

$$\begin{array}{cc}\hfill (ii)& e_1{e}_2{e}_3{e}_4>c_1{c}_2{c}_3{c}_4\hfill \end{array}$$

(63)

From (62) follows that

$$\begin{array}{c}\hfill (e_1{e}_3-c_1{c}_3)<0\end{array}$$

(64)

If (62) and (63) hold then also

$$\begin{array}{c}\hfill e_2{e}_4(c_1{c}_3-e_1{e}_3)<c_2{c}_4(c_1{c}_3-e_1{e}_3)\end{array}$$

(65)

holds. We get

$$\begin{array}{c}\hfill e_2{e}_4<c_2{c}_4\end{array}$$

(66)

but this is together with (64) a contradiction to $e>c$. Therefore $det(A)$ and $det(A_n)$ cannot be of opposite sign.

Lemma 19

For a monocyclic payoff matrix A as in (14) $det(A)=0$ and $e=c$ cannot hold simultaneously.

Proof 

We have to solve this system of equations:

$$\begin{array}{c}\hfill -c_1{c}_2{c}_3{c}_4+c_2{c}_4{e}_1{e}_3+c_1{c}_3{e}_2{e}_4+c_3{e}_4{t}_1{t}_2+c_4{e}_1{t}_2{t}_3+\end{array}$$

$$\begin{array}{c}\hfill +c_2{e}_3{t}_1{t}_4+c_1{e}_2{t}_3{t}_4+t_1{t}_2{t}_3{t}_4=e_1{e}_2{e}_3{e}_4\end{array}$$

(67)

$$\begin{array}{c}\hfill e_1{e}_2{e}_3{e}_4=c_1{c}_2{c}_3{c}_4\end{array}$$

(68)

Obviously each term in (67) that contains a $t_i$ is positive, so it suffices to show that a system

$$\begin{array}{c}\hfill -c_1{c}_2{c}_3{c}_4+c_2{c}_4{e}_1{e}_3+c_1{c}_3{e}_2{e}_4-e_1{e}_2{e}_3{e}_4+p=0\end{array}$$

(69)

$$\begin{array}{c}\hfill e_1{e}_2{e}_3{e}_4=c_1{c}_2{c}_3{c}_4\end{array}$$

(70)

with $p>0$ has no solution. First note that from (69) follows that $e_1{e}_3\ne c_1{c}_3$ must hold. We assume now (without loss of generality) that $e_1{e}_3>c_1{c}_3$ holds, hence also $c_2{c}_4>e_2{e}_4$ must hold. If we write (69) in the following form

$$\begin{array}{c}\hfill c_2{c}_4(e_1{e}_3-c_1{c}_3)+e_2{e}_4(c_1{c}_3-e_1{e}_3)+p=0\end{array}$$

it is easy to see that the left side is always greater than zero and hence the system has no solution, therefore $det(A)=0$ and $e=c$ cannot hold simultaneously.

Proposition 20

For (14) the following statements are equivalent:

(i) 

$det(A)<0$ and $e\ge c$ holds.

(i) 

The matrix C obtained by moving the top row of A (see (14)) to the bottom is an M-matrix.

Proof 

To prove this we will show that all leading principal minors are positive. Clearly

$$\begin{array}{cc}\hfill e_1& >0,e_1{e}_2>0\text{and}\hfill \end{array}$$

$$\begin{array}{cc}\hfill det(C)& >0\hfill \end{array}$$

(71)

hold. Thus we have only to check if

$$-c_1{c}_3{e}_2+e_1{e}_2{e}_3-c_3{t}_1{t}_2>0$$

also holds. We assume that the converse is true. We will show that the resulting system of inequalities will lead to a contradiction. We have

$$\begin{array}{cc}\hfill -c_1{c}_3{e}_2+e_1{e}_2{e}_3-c_3{t}_1{t}_2& <0\hfill \end{array}$$

(72)

$$\begin{array}{cc}\hfill e_1{e}_2{e}_3{e}_4-c_1{c}_2{c}_3{c}_4& \ge 0\hfill \end{array}$$

(73)

$$\begin{array}{cc}\hfill c_1{c}_2{c}_3{c}_4+e_1{e}_2{e}_3{e}_4& >c_3{e}_4{t}_1{t}_2+c_1{c}_3{e}_2{e}_4+c_2{c}_4{e}_1{e}_3\hfill \end{array}$$

(74)

where (74) comes from (71) after omitting some negative terms on the left side. Multiplying (72) with $e_4$ and putting these inequalities together we get

$$\begin{array}{c}\hfill c_1{c}_2{c}_3{c}_4\le e_1{e}_2{e}_3{e}_4<e_4{c}_3(c_1{e}_2+t_1{t}_2)<e_1{e}_2{e}_3{e}_4+c_1{c}_2{c}_3{c}_4-c_2{c}_4{e}_1{e}_3\end{array}$$

and hence

$$\begin{array}{c}\hfill 0\le e_1{e}_2{e}_3{e}_4-c_1{c}_2{c}_3{c}_4<c_1{c}_3(e_2{e}_4-c_2{c}_4)+c_3{e}_4{t}_1{t}_2<e_1{e}_3(e_2{e}_4-c_2{c}_4)\end{array}$$

From this follows that $e_1{e}_3>c_1{c}_3$ and $e_2{e}_4>c_2{c}_4$ hold and hence we can write

$$\begin{array}{c}\hfill 0\le e_1{e}_2{e}_3{e}_4-e_1{c}_2{e}_3{c}_4<c_1{c}_3(e_2{e}_4-c_2{c}_4)+c_3{e}_4{t}_1{t}_2<e_1{e}_3(e_2{e}_4-c_2{c}_4)\end{array}$$

which is a contradiction. This proof also works in the other direction, clearly if $det(C)>0$ holds then also $det(A)<0$ holds, if additionally all leading principal minors are positive then $e>c$ holds.

8. Proofs

8.1. Proof of Theorem 4

We split the proof in two parts. The first part is on a certain property of the return map.

Lemma 21

With the assumptions from Theorem 4 we get

$$\Pi \left(\begin{array}{c}0\\ v\end{array}\right)\in {\mathbb{R}}_{+}^2$$

for $v>0$.

Proof 

It holds that

$$\Pi \left(\begin{array}{c}0\\ v\end{array}\right)=(1+d_{2}v)\left(\begin{array}{c}{p}_{12}v\\ p_{22}v\end{array}\right)$$

and hence we have to show that under the assumptions made $d_2,p_{12}$ and $p_{22}$ are greater than 0. That $p_{22}>0$ holds can be seen by using the fact that $tr(P)>2\sqrt{detP}>0$ holds. From

$$\begin{array}{c}\hfill p_{22}=\frac{c_2{c}_4{e}_3+c_4{t}_2{t}_3}{e_2{e}_3{e}_4}>0\Rightarrow c_2{c}_4{e}_3+c_4{t}_2{t}_3>0\Rightarrow c_2{e}_3+t_2{t}_3>0\end{array}$$

now follows that

$$\begin{array}{cc}\hfill d_2& =\frac{1}{e_2^2}+\frac{c_2}{e_2{e}_4^2}-\frac{t_2}{e_2{e}_3^2}+\frac{t_2{t}_3}{e_2{e}_3{e}_4^2}>0\iff e_3^2{e}_4^2+c_2{e}_2{e}_3^2-e_2{e}_4^2{t}_2>-e_2{e}_3{t}_2{t}_3\hfill \end{array}$$

holds. Lastly note that $p_{21}=e_1{\Sigma }_2$ and as ${\Sigma }_2>0$ holds under the assumptions made (use Mathematica to prevent some lengthy calculations to show this. The Mathematica file is added as a supplementary file called additionalmaterial.nb), which proves the lemma.

Proof of Theorem 4

It follows from Lemma 11 that the conditions guarantee the existence of a positive eigenvalue ${\lambda }_{+}$ and a corresponding positive eigenvector. It follows from Lemma 14 that no strategy is dominated. Hence each strategy is used and the domain of the return map is not empty. It follows from Lemma 21 that an invariant set in ${\mathbb{R}}_{+}^2$ exists, which is at least given by the set that lies between ${\mathbf{u}}_{+}$ and $\left(0,v\right)$.

8.2. Proof of Theorem 5 and 6

Proof of Theorem 5

The first part is from Lemma 15 and assures the existence of an attracting Shapley polygon on the 123 face. For the asymptotic stability of the Nash equilibrium it only remains to show that there are no other Nash equilibria in the game. This can be seen by using the index theorem [6]. If there are only regular Nash equilibria there must be a Nash equilibrium with index $-1$ to be able to get more than one Nash equilibrium. With the help of Mathematica we get that $N_{24}$ (which has index $-1$) does never exist, if ${\Sigma }_1>0$, ${\Sigma }_2>0$ and $e_1{e}_2{t}_3<|t_1|c_2{c}_3$ hold. Again we use Mathematica to show that the index of the interior Nash equilibrium $N_{1234}$ is $+1$ (with the formula from (60)), so it must be the unique Nash equilibrium and hence it is asymptotically stable. Note that no other Shapley polygon can exist. The Mathematica file is added as a supplementary file called additionalmaterial.nb.

Proof of Theorem 6

This follows directly from the proofs of Theorem 5 and Theorem 4.

9. Conclusions

In this paper we presented some results on the existence and stability of Shapley polygons. It turns out that it is possible to give a complete classification of the attractors for monocyclic matrices, whereas—as the examples in Section 4 show—it is rather impossible to give a classification for general matrices. It should be also mentioned that the support of Nash equilibria, Shapley polygons and best response cycles may be disjoint making it even harder to predict the asymptotical behaviour. As shown in [2] there is a strong connection between the replicator equation and the best response dynamics. This connection is especially stressed by the fact that we were able to construct a a return map which had an identical return matrix as found in the analysis of the replicator equation. The return map found in this work turned out to be able to deliver also results on the interior Nash equilibrium. From this point of view it might be interesting to have a closer look at the replicator equation and check the orbits, whose time averages converge to the saddle-type Shapley polygon.