Evolutionarily Stable Strategies for the Game "Shooting Fingers", with Different Payoffs

Mayla Boguslav (Columbia University)

Peter Johnson (Auburn University)

Adam Purcilly (St. Peter's University)

Evolutionarily stable strategies and their stability indices are computed for all 2-player games of a certain type.

The games to be considered here are two-person games of a very peculiar, elementary nature. In each instance the game is played in one "go". The contestants each choose from a fixed list, the same for each contestant, of "plays", the two plays are played, the game is over. Who won?

Here we come to a distinctive feature of these games: they are not about winning, as in a battle to the death, but about payoff. We distinguish between the players: they are player \(1\) and player \(2\). There is an \(n \times n\) real matrix \(U = [u_{ij}]\), the payoff matrix for player \(1\), with respect to some ordering of the plays, of which there are \(n\): for \(i\), \(j = 1, \dots, n\), \(u_{ij}\) is the payoff to player \(1\) when player \(1\) chooses the \(i\)th play and player \(2\) chooses the \(j\)th play.

In modeling applications in which the game might be played over and over, in varying environments, \(u_{ij}\) may stand for an average payoff to player \(1\).

What about player \(2\)? Is there a payoff for player \(2\)? Whether there is or not, and whether or not player \(2\) is getting a better deal than player \(1\), may be of emotional interest to player \(1\), but it is irrelevant to the playing of the game; if player \(1\) is going to play at all, player \(1\)'s only interest is the payoff, which player \(1\) would like to be large. If the game is to be played many times, player \(1\) would like to maximize the average player\(1\) payoff.

Player \(1\)'s problem is that player \(1\) has no idea which play player \(2\) will choose. This is a mathematical assumption. In situations such as the Traveler's or Prisoner's Dilemma (Barker, 2009), which seemingly have to do with precisely the kind of game under discussion here, it seems to us pretty clear that in actual trials, player \(1\), knowing that the payoffs to the two players are symmetric, and knowing that player \(2\) is human, has a good deal of probabilistic information on player \(2\)'s choice, and this violation of the "player \(1\) is clueless" assumption is an obvious explanation of the "paradoxical" divergence of experimental and "theoretical" results, especially in the case of the Traveler's Dilemma.

There are numerous "real" situations modeled by these games, or by superpositions of several such games, in which the cluelessness hypothesis is reasonable; we shall operate under this assumption from here on. We are carrying on about it because we think that mathematical assumptions about models, especially probabilistic or information theoretic assumptions, should be explicit. After all, if you do not look too closely, you can "use" the Poisson distribution to "show" that the probability that the sun will rise two or more times tomorrow is \(1 - (\frac {2}{e})\), not much less than \(\frac {1}{3}\).

Let \(P_n\) be \[\{ (p_1, p_2, \dots, p_n) \in \mathbb {R} ^n \mid p_i \geq 0, i = 1, 2, \dots, n \text{ and } \sum _{i=1}^n p_i = 1\},\] the set of probability vectors of length \(n\). Suppose we have a game with a list of \(n\) plays and corresponding payoff-for-player-\(1\) matrix \(U\). A strategy for either player is a vector \(p = (p_1, p_2, \dots, p_n) \in P_n\); at each instance of the game, the player following this strategy will choose the \(i\)th play with probability \(p_i\).

From elementary probability and statistics, it follows that if player \(1\) follows strategy \(p\), and player \(2\) follows strategy \(q\), then the average payoff for player \(1\) (over all instances of the game in which the players follow these strategies) is \begin{equation} \label{e11} \sum _{i=1}^n \sum _{j=1}^n p_i u_{ij} q_j = pUq^T \end{equation}

This interpretation is also valid when the \(u_{ij}\) are themselves averages.

Following (Barker, 2009), we will denote \(pUq^T\) by \(W(p. q)\), and sometimes by \(W_U(p, q)\). Note that \(W\) is actually defined on \(\mathbb {R} ^n \times \mathbb {R}^n\), and is bilinear: \[W(w, au + bv) = aW(w, u) + bW (w, v)\] and\[W(au + bv, w) = a W(u, w) + bW (v, w)\] for all \(u, v, w \in \mathbb {R}^n\) and \(a, b \in \mathbb {R}\).

Definition 1. A strategy \(p \in P_n\) is a Nash equilibrium for the the game if and only if \[ W(q, p) \leq W(p, p) \mbox { for all } q \in P_n \]

That is, if player \(2\) uses strategy \(p\), player \(1\) is not able to increase average payoff by using any strategy other than \(p\).

Definition 2. Suppose \(\epsilon \in (0, 1]\); \(p \in P_n\) is an evolutionarily stable strategy (ESS) with stability at least \(\epsilon\) (for the game under discussion) if and only if, for all \(q \in P_n \backslash \{p\}\), \begin{equation} \label{2e} W(q, \epsilon q + (1 - \epsilon)p)) < W(p, \epsilon q + (1 - \epsilon)p) \end{equation}

The motivation for this definition is reasonable, but requires following a story outline. Imagine a society in which player \(1\) plays randomly selected members of the population, and everybody uses strategy \(p\), until one fine day player \(1\) awakes to find that a proportion of the population (excluding player \(1\)) has defected to a new strategy \(q\). Now, when player \(2\) is chosen at random from the population to engage player \(1\) in the game, the probability is \(\epsilon\) that player \(2\) will use strategy \(q\), and \(1 - \epsilon\) that player \(2\) will use strategy \(p\). Therefore, whatever strategy \(r \in P_n\) player \(1\) uses, the average payoff for playing the game with player \(2\) chosen at random from the population excluding player \(1\) will be \(W(r, \epsilon q + (1 - \epsilon)p)\). Inequality (\ref{2e}) expresses that, between the choices for player \(1\) of joining the rebels and adopting strategy \(q\), and sticking with the established, old-school strategy \(p\), the average payoff will be greater with the latter choice.

Lemma 1. Suppose \(\epsilon \in (0, 1]\) and \(p \in P_n\) is an ESS with stability at least \(\epsilon\), for some game. Then for each \(\epsilon ' \in (0, \epsilon)\), \(p\) is also an ESS with stability at least \(\epsilon '\).

Proof. Keep in mind that \(P_n\) is convex. Suppose that \(\epsilon ' \in (0, \epsilon)\). We want to show that inequality (\ref{2e}) holds for every \(q \in P_n \backslash \{p\}\). Suppose that \(q \in P_n \backslash \{p\}\); note that \(\epsilon ' = t \epsilon\) for some \(t \in (0, 1)\).

Let \(r = tq + (1 - t)p\). Then \(r \in P_n \backslash \{p\}\), so inequality (\ref{2e}) holds, with \(r\) replacing \(q\).

We have: \begin{eqnarray*} \epsilon r + (1 - \epsilon)p & = & \epsilon t q + \epsilon (1 - t)p + (1 - \epsilon)p\\ & = & \epsilon t q + (1 - \epsilon t)p\\ & = & \epsilon ' q + (1 - \epsilon ')p \end{eqnarray*}

Therefore: \begin{eqnarray*} W(tq + (1 - t)p, \epsilon ' q + (1 - \epsilon ')p) & = & W(r, \epsilon r + (1 - \epsilon)p) \\ & < & W(p, \epsilon r + (1 - \epsilon)p) \\ & = & W(p, \epsilon ' q + (1 - \epsilon ')p).\\ \end{eqnarray*}

So, \[ tW(q, \epsilon ' q + (1 - \epsilon ')p) + (1 - t)W(p, \epsilon ' q + (1 - \epsilon ')p) \] \[ < W(p, \epsilon ' q + (1 - \epsilon ')p)\] and \[tW(q, \epsilon ' q + (1 - \epsilon ')p) < tW (p, \epsilon ' q + (1 - \epsilon ')p). \] Therefore, inequality (\ref{2e}) holds. \(\Box\)

Corollary 1. If, for some game, \(p \in P_n\) is an ESS, then \(p\) is a Nash equilibrium for that game.

Proof. Let \(\epsilon \in (0, 1]\) be such that inequality (\ref{2e}) holds for all \(q \in P_n \backslash \{p\}\). Fix \(q \in P_n \backslash \{p\}\): by Lemma 1, inequality (\ref{2e}) holds for all \(\epsilon ' \in (0, \epsilon)\). Let \(\epsilon ' \downarrow 0\), to obtain \(W(q, p) \leq W(p, p)\). \(\Box\)

Definition 3. If \(p \in P_n\) is an ESS for some game, then \[\mu (p) = \sup \left[\epsilon \in (0, 1]; \mbox{ (\ref{2e}) holds for all } q \in P_n \backslash \{p\}\right]\] is the stability index of \(p\).

Our aim here is to find all ESS's \(p\), and \(\mu (p)\), for all possible \(2\)-play games --that is, for all possible \(2 \times 2\) payoff matrices. The term "shooting fingers" in the title of this article refers to one well-known incarnation of such a game: somebody says "one, two, three, shoot!" and on the word "shoot" each of the two contestants flings forward a hand with either \(1\) or \(2\) fingers extended (or, in some precincts, with \(0\) or \(1\) finger extended). Usually, when this game is played the payoff is determined purely by whether the total number of fingers extended is odd or even, which would correspond to a payoff matrix of the form \(\binom {a \quad b}{b \quad a}\), but here we allow any \(2 \times 2\) real matrix \(U\).

It is possible to reduce our problem from a \(4\) variable problem to a \(2\) variable problem. Let \(J_n\) denote the \(n \times n\) matrix of all \(1\)'s.

Lemma 2. Suppose \(U\) is the \(n \times n\) player-\(1\)-payoff matrix for a two-person game, and \(c\) is a non-zero real number. Then for any \(p\), \(q \in P_n\), \[ W_{cU} (p, q) = cW_U(p, q)\] and \[W_{U + cJ_n} (p, q) = W_U (p, q) + c\]

We leave the proof to the reader.

Corollary 2. With \(U\) and \(c\) as in Lemma 2, a strategy \(p \in P_n\) is a Nash equilibrium or an ESS with respect to the payoff matrix \(U + cJ_n\), if and only if \(p\) is a Nash equilibrium or an ESS, respectively, with respect to \(U\). If \(c > 0\) an analogous statement holds for the payoff matrices \(cU\) and \(U\). In each case, for ESS's the stability index \(\mu (p)\) stays the same as the payoff matrix is replaced.

Corollary 3. The sets of Nash equilibria and of ESS's, and the values of \(\mu (p)\) for ESS's \(p \in P_n\), with respect to any non-constant \(n \times n\) payoff matrix \(U\), are the same as for some \(n \times n\) payoff matrix \(U'\) that has all entries in \([0, 1]\), and has at least one \(0\) and one \(1\) entry.

Proof omitted, but here is an example to illustrate it:

Let \[ U = \begin{bmatrix} 1 & -2\\ 0 & 4 \end{bmatrix} \] Take \[\begin{array}{ll} U' = & \frac {1}{6} [U + 2J_2]\\ [.1in] = & \begin{bmatrix} 1/2 & 0\\ 1/3 & 1 \end{bmatrix} \end{array}\]

If \(U = cJ_n\), a constant matrix, then every \(p \in P_n\) is a Nash equlibrium with respect to \(U\), and there are no ESS's.

Main Results

Given a class of non-constant payoff matrices \(U\), the results preceding suggest the application of either or both of the following to the task of finding all ESS's for these matrices, and their stability indices:

(a)

Look for the ESS's among the Nash equilibria for the different payoff matrices--the requirement for a Nash equilibrium is less complicated than the requirement for an ESS.

(b)

Replace each matrix \(U\) in the class by a "normalized" matrix \(U'\), as suggested in Corollary 3.

So, for the non-constant \(2 \times 2\) payoff matrices, we could break the task into \(12\) cases, \[ \begin{bmatrix} 0 & 1\\ a & b \end{bmatrix}, \begin{bmatrix} 1 & 0\\ a & b \end{bmatrix}, \begin{bmatrix} 0 & a\\ b & 1 \end{bmatrix}, \dots, \begin{bmatrix} 1 & b\\ 1 & 0 \end{bmatrix}, \] with \(a, b \in [0, 1]\) in each case. Some of these cases are equivalent--you get one case from the other by re-ordering the plays. But, also, there are pesky subcases: it makes a differnce whether \(a\) is \(0\), or \(1\), or in between, and the same with \(b\).

We choose to attack the problem of finding all ESS's, and their stability indices, for non-constant \(2 \times 2\) payoff matrices directly, without resorting to either (a) or (b), above. We recommend (a) and (b) as sources of exercises, and for use in analyzing other classes of payoff matrices.

Let \(p = (x, 1 - x)\) and \(q = (s, 1 - s)\) such that \(x, s \in [0, 1]\) and \(x \neq s\).

Let \[ U = \begin{bmatrix} u_{11} & u_{12}\\ u_{21} & u_{22} \end{bmatrix} \]

From Definition 2: \(p\) is an ESS if and only if there exists some \(\epsilon \in (0, 1]\) such that \[ W(q, \epsilon q + (1 - \epsilon) p) < W(p, \epsilon q + (1 - \epsilon) p)\] whenever \(x \neq s\).

Since \(W\) is bilinear, we can open up the parenthesis as follows: \begin{equation} \label {e21} \epsilon W(q, q) + (1 - \epsilon) W(q, p) < \epsilon W(p, q) + (1 - \epsilon) W(p, p) \end{equation}

Writing this out and grouping like terms, we eventually arrive at: \begin{eqnarray} \label {e22} (x-s) \left[ \epsilon (x-s)(u_{11} - u_{12} - u_{21} + u_{22}) - x(u_{11} - u_{22} - u_{21} + u_{22}) + u_{22} - u_{12} \right] < 0 \end{eqnarray}

If \(x - s < 0\), then (\ref{e22}) becomes \[ \epsilon (x-s)(u_{11} - u_{12} - u_{21} + u_{22}) - x(u_{11} - u_{12} - u_{21} + u_{22}) + u_{22} - u_{12} > 0. \]

As \(s \to x\), \(\epsilon (x-s)(u_{11} - u_{12} - u_{21} + u_{22}) \to 0 \).

Therefore: \[\begin{array}{c} -x (u_{11} - u_{12} - u_{21} + u_{22}) + u_{22} - u_{12} \geq 0\\ \Leftrightarrow u_{22} - u_{12} \geq x (u_{11} - u_{12} - u_{21} + u_{22}) \end{array}\]

If \(u_{11} - u_{12} - u_{21} + u_{22} > 0\) then \[\frac {u_{22} - u_{12}}{u_{11} - u_{12} - u_{21} + u_{22}} \geq x\] and if \(u_{11} - u_{12} - u_{21} + u_{22} < 0\) then \[\frac {u_{22} - u_{12}}{u_{11} - u_{12} - u_{21} + u_{22}} \leq x.\]

Or, if \(x - s > 0\), then (\ref{e22}) becomes \[ \epsilon (x - s)(u_{11} - u_{12} - u_{21} + u_{22}) - x(u_{11} - u_{12} - u_{21} + u_{22}) + u_{22} - u_{12} < 0. \]

Therefore: \[\begin{array}{c} - x (u_{11} - u_{12} - u_{21} + u_{22}) + u_{22} - u_{12} \leq 0\\ \Leftrightarrow u_{22} - u_{12} \leq x(u_{11} - u_{12} - u_{21} + u_{22}) \end{array}\]

If \(u_{11} - u_{12} - u_{21} + u_{22} > 0\), then \[\frac {u_{22} - u_{12}}{u_{11} - u_{12} - u_{21} + u_{22}} \leq x\] and if \(u_{11} - u_{12} - u_{21} + u_{22} < 0\), then \[\frac {u_{22} - u_{12}}{u_{11} - u_{12} - u_{21} + u_{22}} \geq x.\]

Let \[z = \frac {u_{22} - u_{12}}{u_{11} - u_{12} - u_{21} + u_{22}}\] and \(y = u_{11} - u_{12} - u_{21} + u_{22}\).

Conclusions so far:

(i)

If \(y \neq 0\) then the only candidate \(p = (x, 1 - x)\) for an ESS with \(0 < x < 1\) is the \(p\) with \(x = z\). Therefore, if \(y \neq 0\) and \(z \notin (0, 1)\), then the only possible ESS's are \((0, 1), (1, 0)\).

We shall deal with these possibilities, and the case \(y = 0\), but first let us suppose that \[ 0 < x = z < 1. \] (Equivalently, \(u_{22} - u_{12}\) and \(u_{11} - u_{21}\) are each non-zero, and they have the same sign.) Is \(p = (x, 1 - x)\) an ESS? (It is a Nash equilibrium---verification left to the reader.)

Plugging \(z = x\) into (\ref{e22}) and rearranging, we obtain \[ \epsilon (x - s)^2 (u_{11} - u_{12} - u_{21} + u_{22}) < 0; \] clearly this holds for all \(\epsilon \in (0, 1]\) and \(s \in [0, 1] \backslash \{x\}\), if and only if \(y < 0\). Conclusion:

If \(u_{11} - u_{21}\), \(u_{22} - u_{12} < 0\), then \[p = (z, 1 - z) = \left(\frac {u_{22} - u_{12}}{u_{11} - u_{12} - u_{21} + u_{22}}, \frac {u_{11} - u_{21}}{u_{11} - u_{12} - u_{21} + u_{22}}\right)\] is an ESS for this game, and \(\mu (p) = 1\). Further, \(p\) is the only possible ESS, in this case, other than \((0, 1)\) or \((1, 0)\).

(ii)

Suppose \(y \neq 0\); we test to see if \(p = (0, 1)\) is an ESS by plugging \(x = 0\) into (\ref{e22}) and letting \(s\) roam over \((0, 1]\). After rearranging, we see that the inequality that must be satisfied for all such \(s\) is: \begin{equation} \label {e23} \epsilon s(u_{11} - u_{12} - u_{21} + u_{22}) < u_{22} - u_{12} \end{equation}

Letting \(s \to 0\) we see that it is necessary that \(u_{22} - u_{12} \geq 0\). Therefore we never have that the ESS of case (i) is an alternative ESS to \((0, 1)\).

Conclusions, from (\ref{e23}):

If \(y>0\) and \(u_{22} - u_{12} \leq 0\) then \((0, 1)\) is not an ESS.

If \(y<0\) and \(u_{22} - u_{12} \geq 0\), then \(p = (0, 1)\) is an ESS and \(\mu (p) = 1\).

If \(y>0\) and \(u_{22} - u_{12} > 0\), then \(p = (0, 1)\) is an ESS, and \[ \mu (p) = \min \left [ 1, \frac {u_{22} - u_{12}}{u_{11} - u_{12} - u_{21} + u_{22}} \right ] . \]

(iii)

When \(y \neq 0\) and \(x = 1\), the situation is equivalent to the case \(x = 0\): reverse the order of the plays. This amounts to interchanging \(u_{11}, u_{22}\) and \(u_{12}, u_{21}\),

Conclusions:

If \(y>0\) and \(u_{11} - u_{21} \leq 0\), then \((1, 0)\) is not an ESS.

If \(y<0\) and \(u_{11} - u_{21} \geq 0\), then \(p = (1, 0)\) is an ESS, and \(\mu (p) = 1\).

If \(y>0\) and \(u_{11} - u_{21} > 0\), then \(p = (1, 0)\) is an ESS and \[ \mu (p) = \min \left [ 1, \frac {u_{11} - u_{21}}{u_{11} - u_{12} - u_{21} + u_{22}} \right ]. \]

It is somewhat surprising that if both \(u_{22} - u_{12}\) and \(u_{11} - u_{21}\) are positive, then both \(p_0 = (0, 1)\) and \(p_1 = (1, 0)\) are evolutionarily stable strategies, with stability indices summing to \(1\).

(iv)

Suppose that \(y = 0\). The inequality (\ref{e22}) that must be satisfied for all \(s \in [0, 1] \backslash \{x\}\) for \((x, 1 - x)\) to be an ESS becomes \[ (x - s)(u_{22} - u_{12}) < 0. \] We conclude:

If \(y = 0\) and \(u_{22} - u_{12} < 0\), then \(p = (1, 0)\) is the only ESS, and \(\mu (p) = 1\).

If \(y = 0\) and \(u_{22} - u_{12} > 0\), then \(p = (0, 1)\) is the only ESS, and \(\mu (p) = 1\).

If \(y = 0\) and \(u_{22} - u_{12} = 0\) then there is no ESS.

Let \(d_1 = u_{11} - u_{21}\) and \(d_2 = u_{22} - u_{12}\), so \(y = d_1 + d_2\). We summarize our findings in the following table. Remember that \(U\) is non-constant.

Case	ESS's	\(\mu\)
\(d_1, d_2 < 0\)	\((\frac {d_2}{d_1 + d_2}, \frac {d_1}{d_1 + d_2})\)	\(1\)
\(d_2 \geq 0\) \(d_1 + d_2 < 0\)	\((0, 1)\)	\(1\)
\(d_2 > 0\), \(d_1 + d_2 > 0\)	\((0, 1)\)	\(\min \left [ 1, \frac {d_2}{d_1 + d_2} \right ]\)
\(d_1 \geq 0\), \(d_1 + d_2 < 0\)	\((1, 0)\)	\(1\)
\(d_1 > 0\), \(d_1 + d_2 > 0\)	\((1, 0)\)	\(\min \left [ 1, \frac {d_1}{d_1 + d_2} \right ]\)
\(d_2 < 0\), \(d_1 + d_2 = 0\)	\((1, 0)\)	\(1\)
\(d_2 > 0\), \(d_1 + d_2 = 0\)	\((0, 1)\)	\(1\)
\(d_1 = d_2 = 0\)	None

References

• Barker, A. T. (2009). Evolutionary stability in the traveler's dilemma. The College Mathematics Journal, 40(1), 33-38.