Charles West Cope (1811-1890) was an English painter.
The topics are
\begin{equation}{\label{a}}\tag{A}\mbox{}\end{equation}
Definitions of Games.
Let \(X\) and \(Y\) be two nonempty sets. We consider the function \(K:X\times Y\rightarrow\mathbb{R}\).
- The elements \(x\in X\) and \(y\in Y\) are called the strategies of players 1 and 2, respectively.
- The elements of the Cartesian product \(X\times Y\), i.e., the pairs of strategies \((x,y)\), where \(x\in X\) and \(y\in Y\), are called situations.
- The function \(K\) is the {\bf payoff} of player 1. The payoff of Player 2 in situation \((x,y)\) is set equal to \(-K(x,y)\).
The system \(\Gamma =(X,Y,K)\) is called a two-person zero-sum game. The function \(K\) is also called the payoff function of the game \(\Gamma\). The game \(\Gamma\) is interpreted as follows. Players 1 and 2 simultaneously and independently choose strategies \(x\in X\) and \(y\in Y\). Under this situation, player 1 receives the payoff \(K(x,y)\) and player 2 receives the payoff \(-K(x,y)\).
If the sets of strategies \(X\) and \(Y\) are finite, then the two-person zero-sum game \(\Gamma\) is also called a matrix game. Suppose that player 1 in matrix game \(\Gamma\) has a total of \(m\) strategies. Therefore, we can order the strategy set \(X\) of the first player by setting up a one-to-one correspondence between the sets \(M=\{1,2,\cdots ,m\}\) and \(X\). Similarly, if player 2 has \(n\) strategies, then we can also set up a one-to-one correspondence between the sets \(N=\{1,2,\cdots ,n\}\) and \(Y\). The game \(\Gamma\) is then fully defined by specifying the matrix \(A=(a_{ij})\), where \(a_{ij}=K(x_{i},y_{j})\), \((i,j)\in M\times N\), \((x_{i},y_{j})\in X\times Y\), \(i\in M\), \(j\in N\). In this case the game \(\Gamma\) is realized as follows. Player 1 chooses row \(i\in M\) and player 2 simultaneously and independently chooses column \(j\in N\). Under this situation, player 1 receives the payoff \(a_{ij}\) and player 2 receives the payoff \(-a_{ij}\). If the payoff is equal to a negative number, then we are dealing with the actual loss of player 1. In this case, we denote the game \(\Gamma\) with the payoff matrix \(A\) by \(\Gamma_{A}\) and call it the \(m\times n\) game according to the dimension of matrix \(A\).
Examples of Matrix Game.
Example. Players 1 and 2 choose integers \(i\) and \(j\) from the set \(\{1,2,\cdots ,n\}\). Player wins the amount \(|i-j|\). This is a two-person zero-sum game. The payoff matrix \(A\) is a square \(n\times n\) matrix with \(a_{ij}=|i-j|\). \(\sharp\)
Example. This example is known as Colonel Blotto game. Colonel Blotto has \(m\) regiments and his enemy has \(n\) regiments. The enemy is defending two posts. Next, we define the payoff to the Colonel Blotto (player 1) at each post. If Colonel Blotto has more regiments than the enemy (player 2) at the post, then his payoff at this post is equal to the number of the enemy’s regiments plus one (the occupation of the post is equivalent to capturing of one regiment). If player 2 has more regiments than Colonel Blotto (player 2), Colonel Blotto loses his regiments at the post plus one (for the lost of the post). If each side has the same number of regiments at the post, it is a draw and each side gets zero. The total payoff to Colonel Blotto (player 1) is the sum of the payoffs at the two posts. This is a two-person zero-sum game. We shall describe the strategies of the players. Suppose that \(m>n\). Colonel Blotto (player 1) has the following strategies:
- \(x_{0}=(m,0)\) means to place all of the regiments at the first post.
- \(x_{1}=(m-1,1)\) means to place \(m-1\) regiments at the first post and one regiment at the second post.
- \(x_{2}=(m-2,2)\), \(\cdots\), \(x_{m-1}=(1,m-1)\) and \(x_{m}=(0,m)\).
The enemy (player 2) has the strategies: \(y_{0}=(n,0)\), \(y_{1}=(n-1,1)\), \(\cdots\), \(y_{n}=(0,n)\). Suppose that Colonel Blotto (player 1) chooses strategy \(x_{0}\) and enemy (player 2) chooses strategy \(y_{0}\). Since \(m>n\), Colonel Blotto (player 1) wins at the first post with payoff \(n+1\) (one for holding the post). At the second post, it is draw. Therefore, the total payoff is \(a_{00}=n+1\). Now, we want to compute \(a_{01}\); that is Colonel Blotto (player 1) chooses strategy \(x_{0}\) and the enemy (player 2) chooses the strategy \(y_{1}\). Since \(m>n-1\), Colonel Blotto (player 1) also wins the first post with payoff \(n-1+1=n\). However, the enemy (player 2) wins at the second post; that is, the loss of Colonel Blotto (player 1) at the second post is one. Therefore, the total payoff is \(a_{01}=n-1\). Similarly, for \(1\leq j\leq n\), we can obtain the payoff \(a_{0j}=n-j+1-1=n-j\). If \(m-1>n\), then we can also obtain the payoff \(a_{10}=n+1+1=n+2\), \(a_{11}=n-1+1=n\) and \(a_{1j}=n-j+1-1-1=n-j-1\) for \(2\leq j\leq n\). In general, the payoff matrix is given by
\[a_{ij}=K(x_{i},y_{j})=\left\{\begin{array}{ll}
n+2 & \mbox{if \(m-i>n-j\) and \(i>j\)}\\
n-j+1 & \mbox{if \(m-i>n-j\) and \(i=j\)}\\
n-j-i & \mbox{if \(m-i>n-j\) and \(i<j\)}\\
-m+i+j & \mbox{if \(m-i<n-j\) and \(i>j\)}\\
j+1 & \mbox{if \(m-i=n-j\) and \(i>j\)}\\
-m-2 & \mbox{if \(m-i<n-j\) and \(i<j\)}\\
-i-1 & \mbox{if \(m-i=n-j\) and \(i<j\)}\\
-m+i-1 & \mbox{if \(m-i<n-j\) and \(i=j\)}\\
0 & \mbox{if \(m-i=n-j\) and \(i=j\)}.
\end{array}\right . \sharp\]
Example. Players approach one another by taking \(n\) steps. After each step, a player may or may not fire a bullet, but during the game, the player may fire only once. The probability that the player will hit his opponent at the \(k\)th step is assumed to be \(k/n\) for \(k\leq n\). A strategy for player 1 consists in taking a decision on shooting at the \(i\)th step, and a strategy for player 2 consists in taking a decision on shooting at the \(j\)th step. Suppose that \(i<j\) and player 1 makes a decision to shoot at the \(i\)th step, and player 2 makes a decision to shoot at the \(j\)th step. The payoff \(a_{ij}\) of player 1 is defined as the difference in the probabilities of hitting the opponent and failing to survive, which is given by
\[a_{ij}=\frac{i}{n}-\left (1-\frac{i}{n}\right )\cdot\frac{j}{n}=\frac{n\cdot (i-j)+i\cdot j}{n^{2}}.\]
In the case of \(i>j\), player 2 is the first to fire with \(a_{ij}=-a_{ji}\). If \(i=j\), then we set \(a_{ij}=0\). \(\sharp\)
Example. Suppose that player 1 wants to attack one of the targets \(c_{1},\cdots ,c_{n}\) having positive values \(\tau_{1},\cdots ,\tau_{n}\), respectively. Player 2 defends one of these targets. We assume that if the un-defended target \(c_{i}\) is attacked, it is necessarily destroyed. In this case, player 1 wins \(\tau_{i}\). Suppose that the defended target is hit with probability \(\beta_{i}\). Then player 1 wins \(\beta_{i}\cdot\tau_{i}\). The strategies for player 1 chooses a target for attack, and the strategies for player 2 chooses a target for defense. The payoff matrix \(A\) is given by
\[A=\left [\begin{array}{cccc}
\beta_{1}\cdot\tau_{1} & \tau_{1} & \cdots & \tau_{1}\\
\tau_{2} & \beta_{2}\cdot\tau_{2} & \cdots & \tau_{2}\\
\cdots & \vdots & \cdots & \vdots\\
\tau_{n} & \tau_{n} & \cdots & \beta_{n}\cdot\tau_{n}
\end{array}\right ]. \sharp\]
Example. There \(n\) cells. Player 2 conceals am object in one of the \(n\) cells, and player 1 wishes to find it. In examining the \(i\)th cell, player 1 exerts \(\tau_{i}>0\) efforts, and the probability of finding the object in the \(i\)th cell (if it is concealed there) is \(\beta_{i}\). If the object is found, player 1 receives the amount \(\alpha\). The players’ strategies are the numbers of cells wherein the players conceal and search for the object, respectively. Player 1’s payoff is equal to the difference in the expected receipts and the efforts made in searching for the object. Therefore, the problem of concealing and searching for the object reduces to rge game with payoff matrix \(A\) given by
\[A=\left [\begin{array}{ccccc}
\alpha\cdot\beta_{1}-\tau_{1} & -\tau_{1} & -\tau_{1} & \cdots & -\tau_{1}\\
-\tau_{2} & \alpha\cdot\beta_{2}-\tau_{2} & -\tau_{2} & \cdots & -\tau_{2}\\
\cdots & \vdots & \cdots & \cdots & \vdots\\
-\tau_{n} & -\tau_{n} & -\tau_{n} & \cdots & \alpha\cdot\beta_{n}-\tau_{n}
\end{array}\right ] \sharp.\]
Example. Suppose that player 1 is searching for a mobile object (player 2) for the purpose of detecting it. Player 2’s objective is the opposite one (i.e., he seeks to avoid being detected). Player 1 can move at velocities of \(\beta_{1}=1\), \(\beta_{2}=2\) and \(\beta_{3}=3\), respectively. The range of the detecting device used by player 1, depending on the velocities of the players, is determined by the matrix
\[D=\left [\begin{array}{c|ccc}
& \beta_{1} & \beta_{2} & \beta_{3}\\ \hline
\alpha_{1} & 4 & 5 & 6\\
\alpha_{2} & 3 & 4 & 5\\
\alpha_{3} & 1 & 2 & 3
\end{array}\right ].\]
Strategies of the players are the velocities, and player 1’s payoff in the situation \((\alpha_{i},\beta_{j})\) is assumed to be the search efficiency \(a_{ij}=\alpha_{i}\cdot\delta_{ij}\) for \(i,j=1,2,3\), where \(\delta_{ij}\) is an element of the matrix \(D\). Then, the problem of selecting velocities in a noisy search can be represented by the game with payoff matrix
\[A=\left [\begin{array}{c|ccc}
& \beta_{1} & \beta_{2} & \beta_{3}\\ \hline
\alpha_{1} & 4 & 5 & 6\\
\alpha_{2} & \6 & 8 & 10\\
\alpha_{3} & 3 & 6 & 9
\end{array}\right ].\]
Examples of Infinite Game.
Example. Player 2 (hider) chooses a point \(y\in [0,1]\) and player 1 (searcher) chooses simultaneously and independently a point \(x\in [0,1]\). We say that the point \(y\) is detected if and only if \(|x-y|\leq r\) for \(0<r<1\). In this case, player 1 wins an amount \(1\); otherwise, the payoff is zero. Therefore, the payoff function is given by
\[H(x,y)=\left\{\begin{array}{ll}
1 & \mbox{if \(|x-y|\leq r\).}\\
0 & \mbox{otherwise.}
\end{array}\right .\]
Since the game is zero-sum, the payoff of player 2 is \(-H(x,y)\). \(\sharp\)
Example. Let \(S\) be a sphere in \(\mathbb{R}^{3}\). Player 1 (searcher) chooses a system of the points \({\bf x}_{1},\cdots ,{\bf x}_{n}\in S\), and player 2 chooses simultaneously and independently a point \({\bf y}\in S\). Player 2 is said to be detected if and only if the point \({\bf y}\in S\) is found in the \(r\)-neighborhood of one of the points \({\bf x}_{i}\) for \(i=1,\cdots ,n\). The \(r\)-neighborhood of the point \({\bf x}_{i}\) means the segment of the sphere (cup) having its apex at the point \({\bf x}_{i}\) with \(r\) as the base of radius. The \(r\)-neighborhood of \({\bf x}_{i}\) is denoted by \(N({\bf x}_{i};r)\). The objective of player 1 is to find player 2. Therefore, the payoff of player 1 is given by
\[H({\bf x},{\bf y})=\left\{\begin{array}{ll}
1 & \mbox{if \({\bf y}\in \bigcup_{i=1}^{n}N({\bf x}_{i};r)\)}\\
0 & \mbox{otherwise}.
\end{array}\right .\]
The payoff of player 2 is \(-H({\bf x},{\bf y})\). \(\sharp\)
Example. Consider two players in the duel. Each player has only one bullet to fire. Let \(p_{1}(x)\) be the probability of hitting the opponent at the instant \(x\) for player 1, which is defined on \([0,1]\) and is assumed to be continuous and increasing on \([0,1]\) satisfying \(p_{1}(0)=0\) and \(p_{1}(1)=1\). The probability function \(p_{2}(y)\) for player 2 can be similarly defined and realized, where \(p_{2}(0)=0\) and \(p_{2}(1)=1\). If player 1 hits player 2, then the payoff for player 1 is \(+1\), and if players 2 hits player 1, then the payoff for player 1 is \(-1\). If both players fire simultaneously and hit each other, then the payoff for player 1 is \(0\). We are going to construct the payoff function \(H(x,y)\). If \(x<y\), then player will first fire. The probability for player 1 to hit player 2 is \(p_{1}(x)\), and the probability for player 1 to miss hitting player 2 is \(1-p_{1}(x)\). When player 1 is missing to hit player 2 and player 2 has not fired knowing that player 1 cannot fire any more, player 2 can obtain a sure hit by waiting until \(y\) is equal to \(1\). Therefore, if \(x<y\), then
\[H(x,y)=1\cdot p_{1}(x)+(-1)\cdot\left (1-p_{1}(x)\right ).\]
For \(x>y\), we can similarly obtain
\[H(x,y)=(-1)\cdot p_{2}(y)+1\cdot\left (1-p_{2}(y)\right ).\]
For \(x=y\), we have
\[H(x,y)=1\cdot p_{1}(x)\cdot\left (1-p_{2}(y)\right )+(-1)\cdot p_{2}(y)\cdot\left (1-p_{1}(x)\right ).\]
Therefore, for \(x,y\in [0,1]\), the payoff function for player 1 is given by
\[H(x,y)=\left\{\begin{array}{ll}
2\cdot p_{1}(x)-1 & \mbox{if \(x<y\)}\\
p_{1}(x)-p_{2}(y) & \mbox{if \(x=y\)}\\
1-2\cdot p_{2}(y) & \mbox{if \(x>y\)}.
\end{array}\right .\]
Now, we assume that neither player knows his opponent has fired, and consider the probability functions \(p_{1}(x)=p_{2}(x)=x\). Since neither player can determine the time of his opponent’s firing provided the opponent misses, the payoff function is given by
\[H(x,y)=\left\{\begin{array}{ll}
x-(1-x)\cdot y & \mbox{if \(x<y\)}\\
0 & \mbox{if \(x=y\)}\\
-y+(1-y)\cdot x & \mbox{if \(x>y\)}.
\end{array}\right .\sharp\]
Example. Consider the search problem for a noisy target. In this problem, the noisy target (player 2) is to be detected by a mobile facility (player 1). The detector range \(r(x,y)\), depending on the velocities \(x\in [x_{0},x_{1}]\) and \(y\in [y_{0},y_{1}]\) of players 1 and 2, respectively, is of the form
\[r(x,y)=\bar{r}(y)\cdot\frac{x_{1}-x}{x_{1}-x_{0}},\]
where \(\bar{r}(y)=r_{0}+\beta\cdot (y-y_{0})\) and
\[\beta =\frac{r_{1}-r_{0}}{y_{1}-y_{0}}\mbox{ with }r_{1}=\bar{r}(y_{1})\mbox{ and }r_{0}=\bar{r}(y_{0}).\]
The positive numbers \(r_{1}\) and \(r_{0}\) are assumed to be given. Therefore, we have
\[r(x,y)=\frac{r_{0}\cdot (y_{1}-y)+r_{1}\cdot (y-y_{0})}{y_{1}-y_{0}}\cdot\frac{x_{1}-x}{x_{1}-x_{0}}.\]
The payoff function \(H(x,y)\) of player 1 means the search capacity, i.e., the searched area per unit time, which is given by
\[H(x,y)=2x\cdot r(x,y).\]
The payoff of player 2 is \(-H(x,y)\). More precisely, for \(x\in [x_{0},x_{1}]\) and \(y\in [y_{0},y_{1}]\), the payoff function is given by
\[H(x,y)=2x\cdot\frac{r_{0}\cdot (y_{1}-y)+r_{1}\cdot (y-y_{0})}{y_{1}-y_{0}}\cdot\frac{x_{1}-x}{x_{1}-x_{0}}. \sharp\]
\begin{equation}{\label{b}}\tag{B}\mbox{}\end{equation}
Game Value and Equilibrium Point.
Consider a two-person zero-sum game \(\Gamma =(X,Y,K)\). In this game, each of the players seeks to maximize the payoff by choosing a proper strategy. But for player 1 the payoff is determined by the function \(K(x,y)\), and for player 2 it is determined by \(-K(x,y)\), i.e. the players’ objectives are directly opposite. We assume that the behavior of both players is rational. In other words, they wish to obtain the maximum payoff when the opponent is acting in the best possible way. Suppose that player 1 chooses strategy \(x\) in \(X\). Then, at worst case, player 1 will win
\[\min_{y\in Y}K(x,y).\]
Therefore, player 1 can always guarantee the payoff
\[\max_{x\in X}\min_{y\in Y}K(x,y).\]
Since \(X\) and \(Y\) can be infinite sets, if the \(\max\) and \(\min\) are not reached, then player 1 can guarantee to obtain the payoff arbitrarily close to the following quantity
\[\underline{v}_{\Gamma}=\sup_{x\in X}\inf_{y\in Y}K(x,y),\]
which is called the {\bf lower value} of the game \(\Gamma\). Similarly, suppose that player 2 chooses strategy \(y\) in \(Y\). Then, at the worst case, player 2 will lose
\[\max_{x\in X}K(x,y).\]
Therefore, player 2 can always guarantee minimum loss
\[-\min_{y\in Y}\max_{x\in X}K(x,y),\]
which can be regarded as the payoff of player 2. Therefore, the number
\[\bar{v}_{\Gamma}=\inf_{y\in Y}\sup_{x\in X}K(x,y)\]
is called the upper value of the game \(\Gamma\). For the matrix game \(\Gamma_{A}\), the lower and upper values of \(\Gamma_{A}\) are, respectively, given by
\[\underline{v}_{A}=\max_{1\leq i\leq m}\min_{1\leq j\leq n} a_{ij}\mbox{ and }
\bar{v}_{A}=\min_{1\leq j\leq n}\max_{1\leq i\leq m}a_{ij}.\]
\begin{equation}{\label{ga11}}\tag{1}\mbox{}\end{equation}
Proposition \ref{ga11}. In the two-person zero-sum game \(\Gamma =(X,Y,K)\), we have \(\underline{v}_{\Gamma}\leq\bar{v}_{\Gamma}\) or
\[\sup_{x\in X}\inf_{y\in Y}K(x,y)\leq\inf_{y\in Y}\sup_{x\in X}K(x,y).\]
Proof. Let \(x\in X\) be an arbitrary strategy chosen by player 1. Then, we have
\[K(x,y)\leq\sup_{x\in X}K(x,y),\]
which implies
\begin{equation}{\label{ga1}}\tag{2}
\inf_{y\in Y}K(x,y)\leq\inf_{y\in Y}\sup_{x\in X}K(x,y).
\end{equation}
Since the right-hand side of (\ref{ga1}) is a constant, it follows that
\[\sup_{x\in X}\inf_{y\in Y}K(x,y)\leq\inf_{y\in Y}\sup_{x\in X}K(x,y),\]
which completes the proof. \(\blacksquare\)
Definition. In the two-person zero-sum game \(\Gamma =(X,Y,K)\), the point \((x^{*},y^{*})\in X\times Y\) is called an equilibrium point, or a saddle point, if and only if
\[K(x,y^{*})\leq K(x^{*},y^{*})\leq K(x^{*},y)\]
for all \(x\in X\) and \(y\in Y\). The set of all equilibrium points in the game \(\Gamma\) will be denoted as \(Z(\Gamma )\subseteq X\times Y\). \(\sharp\)
The equilibrium point can be regarded as an optimal situation \((x^{*},y^{*})\) in the sense of deviation from which there is no advantages for both players. For the matrix game \(\Gamma_{A}\), the equilibrium points of the payoff matrix \(A\) are the points \((i^{*},j^{*})\in M\times N\) satisfying the following inequalities
\[a_{ij^{*}}\leq a_{i^{*}j^{*}}\leq a_{i^{*}j}\]
for all \(i\in M\) and \(j\in N\). The equilibrium point \(a_{i^{*}j^{*}}\) is simultaneously the minimum of row of \(A\) and the maximum of column of \(A\).
Example. For the matrix game \(\Gamma_{A}\) with payoff matrix \(A\) given by
\[\left [\begin{array}{ccc}
1 & 0 & 4\\ 5 & 3 & 8\\ 6 & 0 & 1
\end{array}\right ].\]
We see that \((2,2)\) is an equilibrium point of \(\Gamma_{A}\). \(\sharp\)
\begin{equation}{\label{ga3}}\tag{3}\mbox{}\end{equation}
Proposition \ref{ga3}. Let \((x_{1}^{*},y_{1}^{*})\) and \((x_{2}^{*},y_{2}^{*})\) be two arbitrarily equilibrium points in the two-person zero-sum game \(\Gamma =(X,Y,K)\). Then, \((x_{1}^{*},y_{2}^{*})\) and \((x_{2}^{*},y_{1}^{*})\) are equilibrium points in \(\Gamma\) and
\[K(x_{1}^{*},y_{1}^{*})=K(x_{2}^{*},y_{2}^{*})=K(x_{2}^{*},y_{1}^{*})=K(x_{1}^{*},y_{2}^{*}).\]
Proof. By the definition of equilibrium point, for all \(x\in X\) and \(y\in X\), we see that
\begin{equation}{\label{ga4}}\tag{4}
K(x,y_{1}^{*})\leq K(x_{1}^{*},y_{1}^{*})\leq K(x_{1}^{*},y)
\end{equation}
and
\begin{equation}{\label{ga5}}\tag{5}
K(x,y_{2}^{*})\leq K(x_{2}^{*},y_{2}^{*})\leq K(x_{2}^{*},y).
\end{equation}
From (\ref{ga4}), we have
\begin{equation}{\label{ga6}}\tag{6}
K(x_{2}^{*},y_{1}^{*})\leq K(x_{1}^{*},y_{1}^{*})\leq K(x_{1}^{*},y_{2}^{*})
\end{equation}
From (\ref{ga5}), we also have
\begin{equation}{\label{ga7}}\tag{7}
K(x_{1}^{*},y_{2}^{*})\leq K(x_{2}^{*},y_{2}^{*})\leq K(x_{2}^{*},y_{1}^{*}).
\end{equation}
Combining (\ref{ga6}) and (\ref{ga7}), we obtain
\[K(x_{2}^{*},y_{1}^{*})\leq K(x_{1}^{*},y_{1}^{*})\leq K(x_{1}^{*},y_{2}^{*})\leq K(x_{2}^{*},y_{2}^{*})\leq K(x_{2}^{*},y_{1}^{*}),\]
which implies
\[K(x_{2}^{*},y_{1}^{*})=K(x_{1}^{*},y_{1}^{*})=K(x_{1}^{*},y_{2}^{*})=K(x_{2}^{*},y_{2}^{*}).\]
Now, considering the point \((x_{2}^{*},y_{1}^{*})\), for all \(x\in X\) and \(y\in X\), we have
\[K(x,y_{1}^{*})\leq K(x_{1}^{*},y_{1}^{*})=K(x_{2}^{*},y_{1}^{*})=K(x_{2}^{*},y_{2}^{*})\leq K(x_{2}^{*},y),\]
which shows that \((x_{2}^{*},y_{1}^{*})\in Z(\Gamma )\). We can similarly show that \((x_{1}^{*},y_{2}^{*})\in Z(\Gamma)\). This completes the proof. \(\blacksquare\)
Proposition \ref{ga3} says that the payoff function takes the same values at all equilibrium points. Therefore, it is meaningful to introduce the following definition.
Definition. Let \((x^{*},y^{*})\) be a equilibrium point in the two-person zero-sum game \(\Gamma =(X,Y,K)\). The number \(v_{\Gamma}=K(x^{*},y^{*})\) is called the value of the game \(\Gamma\). \(\sharp\)
From Proposition \ref{ga3}, it follows that any pair of optimal strategies forms an equilibrium point, and the corresponding payoff is the value of the game. In the two-person zero-sum game \(\Gamma =(X,Y,K)\), we define the following two sets:
\[X^{*}=\left\{x^{*}\in X:\mbox{there exists \(y^{*}\in Y\) such that \((x^{*},y^{*})\in Z(\Gamma )\)}\right\}\]
and
\[Y^{*}=\left\{y^{*}\in X:\mbox{there exists \(x^{*}\in Y\) such that \((x^{*},y^{*})\in Z(\Gamma )\)}\right\}.\]
Then, we have the following interesting result.
\begin{equation}{\label{ga8}}\tag{8}\mbox{}\end{equation}
Proposition \ref{ga8}. In the two-person zero-sum game \(\Gamma =(X,Y,K)\), we have
\[Z(\Gamma )=X^{*}\times Y^{*}.\]
Proof. The desired result follows from the second assertion of Proposition \ref{ga3} immediately. \(\blacksquare\)
Proposition \ref{ga8} says that \(X^{*}\) and \(Y^{*}\) are the projections of the set \(Z(\Gamma )\) onto \(X\) and \(Y\), respectively. In this case, the set \(X^{*}\) (resp. \(Y^{*}\)) is called the set of optimal strategies of player 1 (resp. player 2).
\begin{equation}{\label{ga14}}\tag{9}\mbox{}\end{equation}
Proposition \ref{ga14}. Let \(\Gamma =(X,Y,K)\) and \(\Gamma^{\prime}=(X,Y,K’)\) be two-person zero-sum games with \(K'(x,y)=\beta\cdot K(x,y)+\alpha\), where \(\alpha\geq 0\) and \(\beta >0\) are constants. Then
\[Z(\Gamma^{\prime})=Z(\Gamma )\mbox{ and }v_{\Gamma^{\prime}}=\beta v_{\Gamma}+\alpha .\]
Proof. Let \((x^{*},y^{*})\) be an equilibrium point of \(\Gamma\). Then, for all \(x\in X\) and \(y\in Y\), we have
\[K'(x^{*},y^{*})=\beta\cdot K(x^{*},y^{*})+\alpha\leq\beta\cdot K(x^{*},y)+\alpha =K'(x^{*},y)\]
and
\[K'(x,y^{*})=\beta\cdot K(x,y^{*})+\alpha\leq\beta\cdot K(x^{*},y^{*})+\alpha =K'(x^{*},y^{*}),\]
which show that \((x^{*},y^{*})\in Z(\Gamma^{\prime})\). For the converse, we first observe
\[K(x,y)=\frac{1}{\beta}\cdot K'(x,y)-\frac{\alpha}{\beta}\equiv\beta^{\prime}\cdot K'(x,y)+\alpha^{\prime},\]
where \(\beta^{\prime}=1/\beta\) and \(\alpha^{\prime}=-\alpha /\beta\). Given any \((x^{*},y^{*})\in Z(\Gamma^{\prime})\), using the above similar argument, we can show that \((x^{*},y^{*})\in Z(\Gamma )\). Therefore, we obtain the equality \(Z(\Gamma^{\prime})=Z(\Gamma )\). On the other hand, we also have
\[v_{\Gamma^{\prime}}=K'(x^{*},y^{*})=\beta\cdot K(x^{*},y^{*})+\alpha =\beta\cdot v_{\Gamma}+\alpha .\]
This completes the proof. \(\blacksquare\)
\begin{equation}{\label{ga2}}\tag{10}\mbox{}\end{equation}
Theorem \ref{ga2} (Existence of the Equilibrium Point). Let \(\Gamma =(X,Y,K)\) be a two-person zero-sum game. Then, we have the following properties.
(i) If \((x^{*},y^{*})\in X\times Y\) is an equilibrium point of \(\Gamma\), then
\begin{equation}{\label{ga12}}\tag{11}
\bar{v}_{\Gamma}=\min_{y\in Y}\sup_{x\in X}K(x,y)=\sup_{x\in X}K(x,y^{*})=v_{\Gamma}
=\inf_{y\in Y}K(x^{*},y)=\max_{x\in X}\inf_{y\in Y}K(x,y)=\underline{v}_{\Gamma}.
\end{equation}
(ii) If the following equalities holds
\begin{equation}{\label{ga13}}\tag{12}
\underline{v}_{\Gamma}=\sup_{x\in X}\inf_{y\in Y}K(x,y)
=\max_{x\in X}\inf_{y\in Y}K(x,y)=\min_{y\in Y}\sup_{x\in X}K(x,y)
=\inf_{y\in Y}\sup_{x\in X}K(x,y)=\bar{v}_{\Gamma},
\end{equation}
then the equilibrium point \((x^{*},y^{*})\in X\times Y\) of \(\Gamma\) exists and satisfies the equalities \((\ref{ga12})\).
Proof. To prove part (i), let \((x^{*},y^{*})\in X\times Y\) be an equilibrium point of \(\Gamma\). By definition, for all \(x\in X\) and \(y\in Y\), we have
\[K(x,y^{*})\leq K(x^{*},y^{*})\leq K(x^{*},y),\]
which says
\begin{equation}{\label{ga9}}\tag{13}
\sup_{x\in X}K(x,y^{*})\leq K(x^{*},y^{*})\mbox{ and }K(x^{*},y^{*})\leq\inf_{y\in Y}K(x^{*},y).
\end{equation}
Since \(x^{*}\in X\) and \(y^{*}\in Y\), we also have
\begin{equation}{\label{ga10}}\tag{14}
\inf_{y\in Y}\sup_{x\in X}K(x,y)\leq\sup_{x\in X}K(x,y^{*})\mbox{ and }
\inf_{y\in Y}K(x^{*},y)\leq\sup_{x\in X}\inf_{y\in Y}K(x,y).
\end{equation}
From (\ref{ga9}) and (\ref{ga10}), we obtain
\[\inf_{y\in Y}\sup_{x\in X}K(x,y)\leq\sup_{x\in X}K(x,y^{*})\leq K(x^{*},y^{*}).\]
and
\[K(x^{*},y^{*})\leq\inf_{y\in Y}K(x^{*},y)\leq\sup_{x\in X}\inf_{y\in Y}K(x,y).\]
Using Proposition \ref{ga11}, we obtain
\[\bar{v}_{\Gamma}=\inf_{y\in Y}\sup_{x\in X}K(x,y)=\sup_{x\in X}K(x,y^{*})=K(x^{*},y^{*})
=\inf_{y\in Y}K(x^{*},y)=\sup_{x\in X}\inf_{y\in Y}K(x,y)=\underline{v}_{\Gamma},\]
which also says that
\[\bar{v}_{\Gamma}=\min_{y\in Y}\sup_{x\in X}K(x,y)=\sup_{x\in X}K(x,y^{*})=K(x^{*},y^{*})
=\inf_{y\in Y}K(x^{*},y)=\max_{x\in X}\inf_{y\in Y}K(x,y)=\underline{v}_{\Gamma}.\]
To prove part (ii), since the exterior extrema of the \(\inf\sup\) and \(\sup\inf\) are attained, there exists \(x^{*}\in X\) and \(y^{*}\in Y\) such that
\[\max_{x\in X}\inf_{y\in Y}K(x,y)=\inf_{y\in Y}K(x^{*},y)\mbox{ and }
\min_{y\in Y}\sup_{x\in X}K(x,y)=\sup_{x\in X}K(x,y^{*}).\]
We want to show that \((x^{*},y^{*})\) is an equilibrium point of \(\Gamma\). We first have
\[K(x^{*},y^{*})\geq\inf_{y\in Y}K(x^{*},y)=\max_{x\in X}\inf_{y\in Y}K(x,y)\]
and
\[K(x^{*},y^{*})\leq \sup_{x\in X}K(x,y^{*})=\min_{y\in Y}\sup_{x\in X}K(x,y).\]
Using (\ref{ga13}), we obtain
\[K(x^{*},y^{*})=\inf_{y\in Y}K(x^{*},y)=\max_{x\in X}\inf_{y\in Y}K(x,y)
=\min_{y\in Y}\sup_{x\in X}K(x,y)=\sup_{x\in X}K(x,y^{*}),\]
which also says
\[K(x^{*},y^{*})=\min_{y\in Y}K(x^{*},y)=\max_{x\in X}\inf_{y\in Y}K(x,y)
=\min_{y\in Y}\sup_{x\in X}K(x,y)=\max_{x\in X}K(x,y^{*})\]
and
\[K(x,y^{*})\leq K(x^{*},y^{*})\leq K(x^{*},y)\mbox{ for all }x\in X\mbox{ and }y\in Y.\]
This completes the proof. \(\blacksquare\)
Corollary. The equilibrium point of the \(m\times n\) matrix game \(\Gamma_{A}\) exists if and only if the following equalities hold
\[\max_{1\leq i\leq m}\min_{1\leq j\leq n}a_{ij}=\min_{1\leq j\leq n}\max_{1\leq i\leq m}a_{ij}.\]
Proof. The result follows from Theorem \ref{ga2} immediately. \(\blacksquare\)
Definition. The point \((x_{\epsilon},y_{\epsilon})\) in the two-person zero-sum game \(\Gamma =(X,Y,H)\) is called the \(\epsilon\)-equilibrium point when, for any strategies \(x\in X\) and \(y\in Y\) of the players 1 and 2, respectively, the following inequality holds true:
\begin{equation}{\label{ga21}}\tag{15}
H(x,y_{\epsilon})-\epsilon\leq H(x_{\epsilon},y_{\epsilon})\leq H(x_{\epsilon},y)+\epsilon .
\end{equation}
The point \((x_{\epsilon},y_{\epsilon})\) is called the \(\epsilon\)-saddle point or \(\epsilon\)-equilibrium point. The strategies \(x_{\epsilon}\) and \(y_{\epsilon}\) are called the \(\epsilon\)-optimal strategies for the players 1 and 2, respectively. \(\sharp\)
Example. Suppose that each of the players 1 and 2 chooses a number from the open interval \((0,1)\). Then, players 1 receives a payoff equal to the sum of the chosen numbers, i.e., \(H(x,y)=x+y\) for \(x,y\in (0,1)\). We can show that \((1,0)\) is the equilibrium point with value \(v=1\). Player 1 can always receive the payoff sufficiently close to the game value \(v=1\) by choosing a number \(1-\epsilon\) with \(\epsilon >0\) which is sufficiently close to \(1\). Also, by choosing a number \(\epsilon >)\) that is sufficiently close to \(0\), player 2 can guarantee that his loss will be arbitrarily close to the game value \(v=1\). This says that \((1-\epsilon ,\epsilon )\) is an \(\epsilon\)-equilibrium point for \(0<\epsilon <1\). The strategy \(x_{\epsilon}=1-\epsilon\) and \(y_{\epsilon}=\epsilon\) are the optimal strategies for the players 1 and 2, respectively. \(\sharp\)
Proposition. Let \(\Gamma =(X,Y,H)\) and \(\Gamma^{\prime}=(X,Y,H’)\) be two strategically equivalent games, i.e., \(H’=\beta H+\alpha\) and \(\beta >0\). If \((x_{\epsilon},y_{\epsilon})\) is the \(\epsilon\)-equilibrium point in the game \(\Gamma\), then it is the \((\beta\epsilon )\)-equilibrium point in the game \(\Gamma^{\prime}\). \(\sharp\)
Theorem. Let \(\Gamma =(X,Y,H)\) be a two-person zero-sum game. Then, we have the following properties
(i) If the game value \(v_{\Gamma}\) exists and is finite, then the \(\epsilon\)-equilibrium point exists for any \(\epsilon >0\) and
\begin{equation}{\label{ga20}}\tag{16}
\lim_{\epsilon\rightarrow 0}H(x_{\epsilon},y_{\epsilon})=v_{\Gamma}.
\end{equation}
(ii) If the \(\epsilon\)-equilibrium point exists for any \(\epsilon >0\), then the game value \(v_{\Gamma}\) exists and is finite with
\[\lim_{\epsilon\rightarrow 0}H(x_{\epsilon},y_{\epsilon})=v_{\Gamma}.\]
Proof. To prove part (i), given any \(\epsilon >0\), from (\ref{ga12}), since
\[\min_{y\in Y}\sup_{x\in X}K(x,y)=v_{\Gamma},\]
we can choose a strategies \(y_{\epsilon}\) such that the following condition is satisfied
\[\sup_{x\in X}H\left (x,y_{\epsilon}\right )-\frac{\epsilon}{2}\leq v_{\Gamma},\]
Also, from (\ref{ga12}), since
\[\max_{x\in X}\inf_{y\in Y}K(x,y)=v_{\Gamma},\]
we can choose a strategy \(x_{\epsilon}\) such that the following condition is satisfied
\[\inf_{y\in Y}H\left (x_{\epsilon},y\right )+\frac{\epsilon}{2}\geq v_{\Gamma}.\]
which imply
\begin{equation}{\label{ga22}}\tag{17}
H\left (x,y_{\epsilon}\right )-\frac{\epsilon}{2}\leq v_{\Gamma}\leq
H\left (x_{\epsilon},y\right )+\frac{\epsilon}{2}
\end{equation}
for all \(x\in X\) and \(y\in Y\). In particular, by taking \(x=x_{\epsilon}\) and \(y=y_{\epsilon}\), we obtain
\begin{equation}{\label{ga23}}\tag{18}
\left |H(x_{\epsilon},y_{\epsilon})-v_{\Gamma}\right |\leq\frac{\epsilon}{2}<\epsilon ,
\end{equation}
which implies (\ref{ga20}), since \(v_{\Gamma}\) is assumed to be finite. Also, using (\ref{ga22}) and (\ref{ga23}), we can also obtain (\ref{ga21}).
To prove part (ii), given any \(\epsilon >0\), according to the concept of infimum, there exist \(x_{\epsilon}\) and \(y_{\epsilon}\) such that
\begin{equation}{\label{ga24}}\tag{19}
H(x_{\epsilon},y_{\epsilon})\leq\inf_{y\in Y}H(x_{\epsilon},y)+\epsilon .
\end{equation}
Therefore, we obtain
\begin{align}
\bar{v}_{\Gamma} & =\inf_{y\in Y}\sup_{x\in X}H(x,y)\leq\sup_{x\in X}
H\left (x,y_{\epsilon}\right )\leq H\left (x_{\epsilon},y_{\epsilon}\right )+\epsilon\mbox{ (by (\ref{ga21}))}\nonumber\\
& \leq\inf_{y\in Y}H\left (x_{\epsilon},y\right )+ 2\epsilon\mbox{ (by (\ref{ga24}))}\label{ga26}\tag{20}\\
& \leq\sup_{x\in X}\inf_{y\in Y}H(x,y)+2\epsilon=\underline{v}_{\Gamma}+2\epsilon ,\nonumber
\end{align}
which implies \(\bar{v}_{\Gamma}\leq\underline{v}_{\Gamma}\). Using Proposition \ref{ga11}, we obtain \(\bar{v}_{\Gamma}=\underline{v}_{\Gamma}\). Next, we claim
\begin{equation}{\label{ga25}}\tag{21}
\lim_{\epsilon\rightarrow 0}H(x_{\epsilon},y_{\epsilon})<\infty .
\end{equation}
Let \(\{\epsilon_{n}\}_{n=1}^{\infty}\) be a sequence such that \(\epsilon_{n}\rightarrow 0\). We want to show that \(\{H(x_{\epsilon_{n}},y_{\epsilon_{n}})\}_{n=1}^{\infty}\) is a Cauchy sequence. From (\ref{ga21}), we have
\[H\left (x_{\epsilon_{m+k}},y_{\epsilon_{k}}\right )+\epsilon_{m+k}\geq H\left (x_{\epsilon_{m+k}},y_{\epsilon_{m+k}}\right )\geq H\left (x_{\epsilon_{k}},y_{\epsilon_{m+k}}\right )-\epsilon_{m+k}\]
and
\[H\left (x_{\epsilon_{k}},y_{\epsilon_{m+k}}\right )+\epsilon_{k}\geq
H\left (x_{\epsilon_{k}},y_{\epsilon_{k}}\right )\geq
H\left (x_{\epsilon_{m+k}},y_{\epsilon_{k}}\right )-\epsilon_{k},\]
which imply
\[\left |H\left (x_{\epsilon_{k}},y_{\epsilon_{k}}\right )-H\left (x_{\epsilon_{m+k}},y_{\epsilon_{m+k}}\right )\right |\leq
\epsilon_{k}+\epsilon_{m+k}\rightarrow 0\mbox{ for any fixed \(m\)}.\]
This shows that \(\{H(x_{\epsilon_{n}},y_{\epsilon_{n}})\}_{n=1}^{\infty}\) is indeed a Cauchy sequence, which proves (\ref{ga25}). Since \(\bar{v}_{\Gamma}=\underline{v}_{\Gamma}\), from (\ref{ga26}), we have
\[\left |H\left (x_{\epsilon},y_{\epsilon}\right )-\bar{v}_{\Gamma}\right |\leq\epsilon ,\]
which shows
\[\lim_{\epsilon\rightarrow 0}H(x_{\epsilon},y_{\epsilon})=\bar{v}_{\Gamma}=\underline{v}_{\Gamma}<\infty .\]
From part (ii) of Theorem \ref{ga2}, it follows that the game value \(v_{\Gamma}\) exists. This completes the proof. \(\blacksquare\)
\begin{equation}{\label{c}}\tag{C}\mbox{}\end{equation}
Mixed Extension of Matrix Game.
The random variable whose values are strategies of a player is called a mixed strategy of the player. Therefore, for the matrix game \(\Gamma_{A}\), a mixed strategy of player 1 is a random variable whose values are the row numbers \(i\in M=\{1,2,\cdots ,m\}\) of the matrix \(A\). Similarly, the mixed strategy of player 2 is a random variable whose values are the column numbers \(j\in N=\{1,2,\cdots ,n\}\) of the matrix \(A\).
Since the random variable is characterized by its distribution, the mixed strategy will be identified with the probability distribution over the set \(M\). Therefore, the mixed strategy \({\bf x}\) of player 1 in the matrix game \(\Gamma_{A}\) is the \(m\)-dimensional vector
\[{\bf x}=(\xi_{1},\cdots ,\xi_{m})\mbox{ with }\sum_{i=1}^{m}\xi_{i}=1\mbox{ and }\xi_{i}\geq 0\mbox{ for }i=1,\cdots ,m.\]
Similarly, the mixed strategy \({\bf y}\) of player 2 is the \(n\)-dimensional vector
\[{\bf y}=(\eta_{1},\cdots ,\eta_{n})\mbox{ with }\sum_{j=1}^{n}\eta_{j}=1\mbox{ and }\eta_{j}\geq 0\mbox{ for }j=1,\cdots ,n.\]
In this case, \(\xi_{i}\geq 0\) and \(\eta_{j}\geq 0\) are the probabilities of choosing the strategies \(i\in M\) and \(j\in N\), respectively, when the players use mixed strategies \({\bf x}\) and \({\bf y}\).
We denote by \({\bf X}\) and \({\bf Y}\) the sets of mixed strategies for the first and second players, respectively. It can be easily seen that the set of mixed strategies of each player is a closed and bounded set in the corresponding finite-dimensional Euclidean space. Let \({\bf x}=(\xi_{1},\cdots ,\xi_{m})\in {\bf X}\) be a mixed strategy of player 1. The set of indices \(M_{\bf x}\equiv\{i:i\in M, \xi_{i}>0\}\) is called the spectrum of strategy \({\bf x}\). Similarly, for the mixed strategy \({\bf y}=(\eta_{1},\cdots ,\eta_{n})\in {\bf Y}\) of player 2, the spectrum \(N_{\bf y}\) is defined as \(N_{\bf y}\equiv\{j:j\in N,\eta_{j}>0\}\).
Since the players choose their strategies independently, we shall define the payoff at mixed strategy \(({\bf x},{\bf y})\) as the mathematical expectation as follows:
\[K({\bf x},{\bf y})=\sum_{i=1}^{m}\sum_{j=1}^{n} a_{ij}\cdot\xi_{i}\cdot\eta_{j}
=({\bf x}^{\top}A){\bf y}={\bf x}^{\top}(A{\bf y}).\]
The function \(K({\bf x},{\bf y})\) is continuous in \({\bf x}\in {\bf X}\) and \({\bf y}\in {\bf Y}\).
Given a matrix game \(\Gamma_{A}=(M,N,A)\), we can induce a new game \(\widehat{\Gamma}_{A}=({\bf X},{\bf Y},K)\), where \({\bf X}\) and \({\bf Y}\) are the sets of mixed strategies in the game \(\Gamma_{A}\) and \(K\) is the payoff function in the mixed strategies. The game \(\widehat{\Gamma}_{A}\) will be called a mixed extension of the game \(\Gamma_{A}\). The game \(\Gamma_{A}\) is a subgame \(\widehat{\Gamma}_{A}\). Similarly, the point \(({\bf x}^{*},{\bf y}^{*})\) in the game \(\widehat{\Gamma}_{A}\) is said to be an equulibrium point if and only if, for all \({\bf x}\in {\bf X}\) and \({\bf y}\in {\bf Y}\), we have
\[K({\bf x},{\bf y}^{*})\leq K({\bf x}^{*},{\bf y}^{*})\leq K({\bf x}^{*},{\bf y}).\]
In this case, the number \(\widehat{v}_{A}=K({\bf x}^{*},{\bf y}^{*})\) is the value of the game \(\widehat{\Gamma}_{A}\).
\begin{equation}{\label{ga18}}\tag{22}\mbox{}\end{equation}
Proposition \ref{ga18}. Let \(\Gamma_{A}\) and \(\Gamma_{A’}\) be two \(m\times n\) matrix games, where \(A’=\alpha A+B\), \(\alpha >0\) a constant, where \(B\) is the matrix with the same elements \(\beta\), i.e., \(b_{ij}=\beta\) for all \(i\) and \(j\). Then, we have
\[Z(\widehat{\Gamma}_{A’})=Z(\widehat{\Gamma}_{A})\mbox{ and }\widehat{v}_{A’}=\alpha\widehat{v}_{A}+\beta,\]
where \(\widehat{\Gamma}_{A’}\) and \(\widehat{\Gamma}_{A}\) are the mixed extensions of the games \(\Gamma_{A’}\) and \(\Gamma_{A}\), respectively, and \(\widehat{v}_{A’}\) and \(\widehat{v}_{A}\) are the values of the games \(\widehat{\Gamma}_{A’}\) and \(\widehat{\Gamma}_{A}\), respectively.
Proof. Since the matrices \(A\) and \(A’\) have the same dimension \(m\times n\), the set of mixed strategies of the games \(\Gamma_{A}\) and \(\Gamma_{A’}\) coincide. Given any mixed strategies \(({\bf x},{\bf y})\), we want to show that
\[K'({\bf x},{\bf y})=\alpha\cdot K({\bf x},{\bf y})+\beta ,\]
where \(K\) and \(K’\) are the payoffs of \(\Gamma_{A}\) and \(\Gamma_{A’}\), respectively. Now, we have
\[K'({\bf x},{\bf y})={\bf x}^{\top}A'{\bf y}=\alpha ({\bf x}^{\top}A{\bf y})+{\bf x}^{\top}B{\bf y}
=\alpha K({\bf x},{\bf y})+\beta ,\]
where \({\bf x}B{\bf y}=\beta\) since \(\sum_{i}x_{i}=1=\sum_{j}y_{j}\). The results follow from Proposition \ref{ga14} immediately. \(\blacksquare\)
\begin{equation}{\label{ga19}}\tag{23}\mbox{}\end{equation}
Theorem \ref{ga19} (von Neumann (1928)). Let \(\Gamma_{A}\) be a matrix game. Then, the mixed extension \(\widehat{\Gamma}_{A}\) of \(\Gamma_{A}\) has an equilibrium point.
Proof. Let \(\Gamma_{A}\) be an arbitrary \(m\times n\) matrix game with a strictly positive matrix \(A\), where \(a_{ij}>0\) for all \(i=1,\cdots ,m\) and \(j=1,\cdots ,n\). We first show that the desired result is true when \(A\) is strictly positive. We denote by \({\bf 1}^{m}=(1,\cdots ,1)\in\mathbb{R}^{m}\). Then, we consider the following primal and dual pair of linear programming problems:
\begin{equation}{\label{ga15}}\tag{24}
\min {\bf x}^{\top}{\bf 1}^{m}\mbox{ subject to }{\bf x}^{\top}A\geq {\bf 1}^{n}\mbox{ and }{\bf x}\geq {\bf 0}
\end{equation}
and
\begin{equation}{\label{ga16}}\tag{25}
\max {\bf y}^{\top}{\bf 1}^{n}\mbox{ subject to }A{\bf y}\leq {\bf 1}^{m}\mbox{ and }{\bf y}\geq {\bf 0}.
\end{equation}
Since \(A\) is strictly positive, there exists \({\bf x}>{\bf 0}\) satisfying \({\bf x}^{\top}A>{\bf 1}^{n}\), which says that problem (\ref{ga15}) is feasible. Since \({\bf y}={\bf 0}\) is a feasible solution, i.e., problem (\ref{ga16}) is feasible, the strong duality theorem says that there exist an optimal solution \(\bar{\bf x}\) of problem (\ref{ga15}) and an optimal solution \(\bar{\bf y}\) of problem (\ref{ga16}) satisfying
\begin{equation}{\label{ga17}}\tag{26}
\bar{\bf x}^{\top}{\bf 1}^{m}=\bar{\bf y}^{\top}{\bf 1}^{n}\equiv\gamma >0.
\end{equation}
Now, we consider \({\bf x}^{*}=\bar{\bf x}/\theta\geq {\bf 0}\) and \({\bf y}^{*}=\bar{\bf y}/\theta\geq {\bf 0}\). From (\ref{ga17}), we have
\[({\bf x}^{*})^{\top}{\bf 1}^{m}=(\bar{\bf x}^{\top}{\bf 1}^{m})/\gamma
=(\bar{\bf y}^{\top}{\bf 1}^{n})/\gamma =({\bf y}^{*})^{\top}{\bf 1}^{n}=1,\]
which says that \(({\bf x}^{*},{\bf y}^{*})\) is a mixed strategies of players 1 and 2, respectively. The payoff of player 1 at \(({\bf x}^{*},{\bf y}^{*})\) is given by
\begin{equation}{\label{ga*18}}\tag{27}
K({\bf x}^{*},{\bf y}^{*})=({\bf x}^{*})^{\top}A{\bf y}^{*}=(\bar{\bf x}^{\top}A\bar{\bf y})/\gamma^{2}.
\end{equation}
According to the feasibility of \(\bar{\bf x}\) and \(\bar{\bf y}\) for problems (\ref{ga15}) and (\ref{ga16}), respectively, using (\ref{ga17}), we obtain
\[\gamma =({\bf 1}^{n})^{\top}\bar{\bf y}\leq (\bar{\bf x}^{\top}A)\bar{\bf y}
=\bar{\bf x}^{\top}(A\bar{\bf y})\leq\bar{\bf x}^{\top}{\bf 1}^{m}=\gamma ,\]
which says that \(\bar{\bf x}^{\top}A\bar{\bf y}=\gamma\). Using (\ref{ga18}), we obtain \(K({\bf x}^{*},{\bf y}^{*})=1/\gamma\). Let \({\bf x}\in X\) and \({\bf y}\in Y\) be arbitrary mixed strategies for players 1 and 2, respectively. According to the feasibility of \(\bar{\bf x}\) and \(\bar{\bf y}\) for problems (\ref{ga15}) and (\ref{ga16}), respectively, we have the following inequalities:
\[K({\bf x}^{*},{\bf y})=({\bf x}^{*})^{\top}A{\bf y}
=(\bar{\bf x}^{\top}A){\bf y}/\gamma\geq ({\bf 1}^{n})^{\top}{\bf y}/\gamma =1/\gamma=K({\bf x}^{*},{\bf y}^{*})\]
and
\[K({\bf x},{\bf y}^{*})={\bf x}^{\top}A{\bf y}^{*}
={\bf x}^{\top}(A\bar{\bf y})/\gamma\leq {\bf x}^{\top}{\bf 1}^{m}/\gamma =1/\gamma=K({\bf x}^{*},{\bf y}^{*}),\]
which shows that \(({\bf x}^{*},{\bf y}^{*})\) is an equilibrium point of \(\widehat{\Gamma}_{A}\) with value \(1/\gamma\), when \(A\) is strictly positive. Now, we consider the \(m\times n\) matrix game \(\Gamma_{A’}\) with an arbitrary matrix \(A’\). Then, there exists a constant \(\beta >0\) such that \(A=A’+B\) is strictly positive, where each entry \(b_{ij}\) of \(B\) is \(\beta\) for \(i=1,\cdots ,m\) and \(j=1,\cdots ,n\). Since \(\widehat{\Gamma}_{A}\) has an equilibrium point \(({\bf x}^{*},{\bf y}^{*})\), Proposition \ref{ga*18} says that \(({\bf x}^{*},{\bf y}^{*})\) is also an equilibrium point of \(\widehat{\Gamma}_{A’}\) with value \(1/\gamma -\beta\). This completes the proof. \(\blacksquare\)
The proof of Theorem \ref{ga19} is constructive, where the solution of the matrix game is equivalent to solve a linear programming problem. Now, the algorithm for the matrix game \(\Gamma_{A’}\) is given below.
- Step 1. Given an arbitrary matrix \(A’\), construct a strictly positive matrix \(A=A’+B\), where \(b_{ij}=\beta >0\) for all \(i=1,\cdots ,m\) and \(j=1,\cdots ,n\).
- Step 2. Solve the linear programming problems (\ref{ga15}) and (\ref{ga16}) to obtain the optimal solutions \(\bar{\bf x}\) and \(\bar{\bf y}\) with the objective value \(\gamma\).
- Step 3. The equilibrium point \(({\bf x}^{*},{\bf y}^{*})\) is given by \({\bf x}^{*}=\bar{\bf x}/\gamma\) and \({\bf y}^{*}=\bar{\bf y}/\gamma\).
- Step 4. The value of \(\Gamma_{A’}\) is \(1/\gamma -\beta\).
Example. Consider a matrix game \(\Gamma_{A}\) with
\[A=\left [\begin{array}{cc}
4 & 0\\ 2 & 3
\end{array}\right ].\]
The corresponding primal and dual pair of linear programming problems are given by
\[\begin{array}{rl}
\min & x_{1}+x_{2}\\
\mbox{subject to} & 4x_{1}+2x_{2}\geq 1\\
& 3x_{2}\geq 1\\
& x_{1},x_{2}\geq 0
\end{array}\]
and
\[\begin{array}{rl}
\max & y_{1}+y_{2}\\
\mbox{subject to} & 4y_{1}\leq 1\\
& 2y_{1}+3y_{2}\leq 1\\
& y_{1},y_{2}\geq 0.
\end{array}\]
Using the simplex method, we can obtain the optimal solutions \(\bar{\bf x}\) and \(\bar{\bf y}\). \(\sharp\)
Mixed Strategies.
Let \({\cal X}\) denote the \(\sigma\)-field of the set \(X\) including the singletons \(x\in X\) and let \({\cal Y}\) be the \(\sigma\)-field of \(Y\). We denote by \(\widehat{X}\) and \(\widehat{Y}\) the sets of all probability measures on the \(\sigma\)-fields \({\cal X}\) and \({\cal Y}\), respectively, and let the function \(H\) be measurable with respect to the \(\sigma\)-field \({\cal X}\times {\cal Y}\). For \(\mu\in\widehat{X}\) and \(\nu\in\widehat{Y}\), the integral
\begin{equation}{\label{ga27}}\tag{28}
K(\mu ,\nu )\equiv\int_{X}\int_{Y} H(x,y)d\mu (x)d\nu (y),
\end{equation}
represents the mathematical expectation of the payoff \(H(x,y)\) with respect to the probability measures \(\mu\) and \(\nu\). If the probability measures \(\mu\) and \(\nu\) have the density functions \(f(x)\) and \(g(y)\), respectively, then we have
\[K(\mu ,\nu )\equiv K(f,g)=\int_{X}\int_{Y} H(x,y)\cdot f(x)\cdot f(y)dxdy.\]
Strictly speaking, the integral in (\ref{ga27}) should be taken over the product probability measure \(\mu\times\nu\) on the product measurable space \(X\times Y\).
Definition. Let \(\Gamma =(X,Y,H)\) be a two-person zero-sum game. A mixed extension of \(\Gamma\) is a two-person zero-sum game with the strategy sets \(\widehat{X}\), \(\widehat{Y}\) and the payoff function \(K(\mu ,\nu )\), i.e., the game \(\widehat{\Gamma}=(\widehat{X},\widehat{Y},K)\). \(\sharp\)
The mixed strategies (probability measures) \(\mu\) and \(\nu\) are selected by the players simultaneously and independently, i.e., the probability measures \(\mu\) and \(\nu\) are stochastically independent. Every pure strategy \(x\) (resp. \(y\)) can be placed in correspondence with the probability measure \(\mu_{x}\in\widehat{X}\) (resp. \(\nu_{y}\in\widehat{Y}\)) concentrated at the point \(x\in X\) (resp. \(y\in Y\)). Identifying the strategies \(x\) with \(\mu_{x}\) and \(y\) with \(\nu_{y}\), we see that the pure strategies are a special case of mixed strategies, i.e., the inclusions \(X\subset\widehat{X}\) and \(Y\subset\widehat{Y}\) hold true. Then, the payoffs of player 1 at the points \((x,\nu )\) and \((\mu ,y)\) are, respectively, the mathematical expectations given below
\[K(x,\nu )\equiv K(\mu_{x},\nu )=\int_{Y}H(x,y)d\nu (y)\mbox{ and }
K(\mu ,y)\equiv K(\mu ,\nu_{y})=\int_{X}H(x,y)d\mu (x).\]
The game \(\Gamma\subset\widehat{\Gamma}\) is a subgame of its mixed extension \(\widehat{\Gamma}\).
Definition. Let \(\Gamma =(X,Y,H)\) be a two-person zero-sum game and let \(\widehat{\Gamma}=(\widehat{X},\widehat{Y},K)\) be its mixed extension.
- The point \((\mu^{*},\nu^{*})\in\widehat{X}\times\widehat{Y}\) is called an equilibrium point of \(\Gamma\) when for all \(\mu\in\widehat{X}\) and \(\nu\in\widehat{Y}\), the following inequality holds
\[K(\mu ,\nu^{*})\leq K(\mu^{*},\nu^{*})\leq K(\mu^{*},\nu );\]
that is, \((\mu^{*},\nu^{*})\) is an equilibrium point of \(\widehat{\Gamma}\), and \(\mu^{*}\) (resp. \(\nu^{*}\)) is player 1’s (resp. player 2’s) optimal strategy in \(\widehat{\Gamma}\). - The point \((\mu_{\epsilon}^{*},\nu_{\epsilon}^{*})\in\widehat{X}\times\widehat{Y}\) is called the \(\epsilon\)-equilibrium point of the game \(\widehat{\Gamma}\) if and only if, for all \(\mu\in\widehat{X}\) and \(\nu\in\widehat{Y}\), the following inequalities hold
\[K(\mu ,\nu_{\epsilon}^{*})-\epsilon\leq K(\mu_{\epsilon}^{*},
\nu_{\epsilon}^{*})\leq K(\mu_{\epsilon}^{*},\nu )+\epsilon ,\]
i.e., \(\mu_{\epsilon}^{*}\) (resp. \(\nu_{\epsilon}^{*}\)) is the \(\epsilon\)-optimal strategy of player 1 (resp. player 2) in \(\widehat{\Gamma}\). \(\sharp\)
Proposition. Let \(\Gamma =(X,Y,H)\) be a two-person zero-sum game and let \(\widehat{\Gamma}=(\widehat{X},\widehat{Y},K)\) be its mixed extension. The pair \((\mu^{*},\nu^{*})\in\widehat{X}\times\widehat{Y}\) is an equilibrium point \((\)resp. \(\epsilon\)-equilibrium point$)$ of the game \(\Gamma\) if and only if, for all \(x\in X\) and \(y\in Y\), the following inequalities hold
\begin{equation}{\label{ga28}}\tag{29}
K(x,\nu^{*})\leq K(\mu^{*},\nu^{*})\leq K(\mu^{*},y)
\mbox{ \((\)resp. \(K(x,\nu^{*})-\epsilon\leq K(\mu^{*},\nu^{*})\leq K(\mu^{*},y)+\epsilon )\)}.
\end{equation}
In particular, if \((x^{*},y^{*})\) is the pure strategy equilibrium point (resp. \(\epsilon\)-equilibrium point) of the game \(\Gamma\), then it is also the equilibrium point (resp. \(\epsilon\)-equilibrium point) of the mixed extension \(\widehat{\Gamma}\).
Proof. Since the pure strategies are special case of mixed strategies, the sufficiency is obvious. To prove the necessity, given any \(\mu\in\widehat{X}\) and \(\nu\in\widehat{Y}\), from (\ref{ga28}), we have
\[K(\mu ,\nu^{*})=\int_{X}K(x,\nu^{*})d\mu (x)\leq K(\mu^{*},\nu^{*})\]
and
\[K(\mu^{*},\nu )=\int_{Y}K(\mu^{*},y)d\nu (y)\leq K(\mu^{*},\nu^{*}),\]
which shows that \((\mu^{*},\nu^{*})\in\widehat{X}\times\widehat{Y}\) is an equilibrium point. Now, suppose that \((x^{*},y^{*})\) is the pure strategy equilibrium point. Then, we have
\[K(x,y^{*})\leq K(x^{*},y^{*})\leq K(x^{*},y)\]
for all \(x\in X\) and \(y\in Y\). By taking \(\mu^{*}=x^{*}\) and \(\nu^{*}=y^{*}\), the inequalities (\ref{ga28}) says that \((x^{*},y^{*})\) is also an equilibrium point of the mixed extension \(\widehat{\Gamma}\). This completes the proof. \(\blacksquare\)
\begin{equation}{\label{ga29}}\tag{30}\mbox{}\end{equation}
Proposition \ref{ga29}. Let \(\Gamma =(X,Y,H)\) be a two-person zero-sum game, and let \(\widehat{\Gamma}=(\widehat{X},\widehat{Y},K)\) be the mixed extension of \(\Gamma\). Then, we have the following properties.
(i) If \((\mu^{*},\nu^{*})\in\widehat{X}\times\widehat{Y}\) is the equilibrium point of \(\widehat{\Gamma}\) with the value \(v_{\widehat{\Gamma}}=K(\mu^{*},\nu^{*})\), then
\begin{equation}{\label{ga33}}\tag{31}
\max_{\mu\in\widehat{X}}\inf_{y\in Y}K(\mu ,y)=\inf_{y\in Y}K(\mu^{*},y)
=v_{\widehat{\Gamma}}=\sup_{x\in X}K(x,\nu^{*})=\min_{\nu\in\widehat{Y}}\sup_{x\in X}K(x,\nu ).
\end{equation}
(ii) If the following equalities holds
\[\sup_{\mu\in\widehat{X}}\inf_{y\in Y}K(\mu ,y)=\max_{\mu\in\widehat{X}}\inf_{y\in Y}K(\mu ,y)
=\min_{\nu\in\widehat{Y}}\sup_{x\in X}K(x,\nu )=\inf_{\nu\in\widehat{Y}}\sup_{x\in X}K(x,\nu ),\]
then the equilibrium point \((\mu^{*},\nu^{*})\in\widehat{X}\times\widehat{Y}\) of \(\widehat{\Gamma}\) exists and satisfies the equalities \((\ref{ga33})\).
Proof. We first prove the following equality
\begin{equation}{\label{ga31}}\tag{32}
\inf_{\nu\in\widehat{Y}}K(\mu ,\nu )=\inf_{y\in Y}K(\mu ,y).
\end{equation}
Since \(Y\subseteq\widehat{Y}\), we immediately have
\[\inf_{\nu\in\widehat{Y}}K(\mu ,\nu )\leq\inf_{y\in Y}K(\mu ,y).\]
Suppose that
\[\inf_{\nu\in\widehat{Y}}K(\mu ,\nu )<\inf_{y\in Y}K(\mu ,y).\]
We want to lead to a contradiction. There is a sufficiently small \(\epsilon >0\) satisfying
\[\inf_{\nu\in\widehat{Y}}K(\mu ,\nu )+\epsilon <\inf_{y\in Y}K(\mu ,y).\]
Therefore, for all \(y\in Y\),
\[\inf_{\nu\in\widehat{Y}}K(\mu ,\nu )+\epsilon <K(\mu ,y),\]
which says that, given any \(\nu\in\widehat{Y}\),
\[\inf_{\nu\in\widehat{Y}}K(\mu ,\nu )+\epsilon\leq\int_{Y}K(\mu ,y)d\nu (y)=K(\mu ,\nu ).\]
Therefore, we obtain
\[\inf_{\nu\in\widehat{Y}}K(\mu ,\nu )+\epsilon\leq\inf_{\nu\in\widehat{Y}}K(\mu ,\nu ).\]
This contradiction proves the equality (\ref{ga31}).
To prove part (i), by taking the supremum for \(\mu\) on \(\widehat{X}\) in (\ref{ga31}), we obtain
\[\sup_{\mu\in\widehat{X}}\inf_{y\in Y}K(\mu ,y)=
\sup_{\mu\in\widehat{X}}\inf_{\nu\in\widehat{Y}}K(\mu ,\nu )=v_{\widehat{\Gamma}}.\]
From (\ref{ga32}), we also have
\[\max_{\mu\in\widehat{X}}\inf_{y\in Y}K(\mu ,y)=
\max_{\mu\in\widehat{X}}\inf_{\nu\in\widehat{Y}}K(\mu ,\nu )=v_{\widehat{\Gamma}}
=\inf_{y\in Y}K(\mu^{*},y)=\inf_{\nu\in\widehat{Y}}K(\mu^{*},\nu ).\]
We can similarly prove
\[\min_{\nu\in\widehat{Y}}\sup_{x\in X}K(x,\nu )=
\min_{\nu\in\widehat{Y}}\sup_{\mu\in\widehat{X}}K(\mu ,\nu )=v_{\widehat{\Gamma}}
=\sup_{x\in X}K(x,\nu^{*})=\sup_{\mu\in\widehat{X}}K(\mu ,\nu^{*}).\]
Let \(v_{\widehat{\Gamma}}\) be the value of .By part (i) of Theorem \ref{ga2}, we have
\begin{equation}{\label{ga32}}\tag{33}
\min_{\nu\in\widehat{Y}}\sup_{\mu\in\widehat{X}}K(\mu ,\nu )
=\sup_{\mu\in\widehat{X}}K(\mu ,\nu^{*})=v_{\widehat{\Gamma}}
=\inf_{\nu\in\widehat{Y}}K(\mu^{*},\nu )
=\max_{\mu\in\widehat{X}}\inf_{\nu\in\widehat{Y}}K(\mu ,\nu ).
\end{equation}
Part (ii) can be obtained by using (\ref{ga31}) and part (ii) of Theorem \ref{ga2}. This completes the proof. \(\blacksquare\)
Let \(\Gamma =(X,Y,H)\) be a two-person zero-sum game. The pure strategy \(x_{0}\in X\) (resp. \(y_{0}\in Y\)) of player 1 (resp. player 2) is called the concentration point of the mixed strategies \(\mu\) (resp. \(\nu\)) if \(\mu (x_{0})>0\) (resp. \(\nu (y_{0})>0\)). Suppose that \(X\) and \(Y\) are assumed to be the topological spaces. The pure strategy \(x_{0}\in X\) (resp. \(y_{0}\in Y\)) is called the point of the mixed strategy spectrum \(\mu\) (resp. \(\nu\)) given on Borel \(\sigma\)-field of subsets of \(X\) (resp. \(Y\)) if and only if, for any measurable neighborhood \(N\) of the point \(x_{0}\) (resp. \(y_{0}\)), the following inequality holds
\[\mu (N)=\int_{N}d\mu (x)>0\mbox{ \((\)resp. }\nu (N)=\int_{N}d\nu (y)>0).\]
The least closed set whose \(\mu\)-measure (resp. \(\nu\)-measure) is equal to \(1\) will be called the {\bf spectrum} of the mixed strategy \(\mu\) (resp. \(\nu\)).
The mixed strategy concentration points are the spectrum points. The opposite is not true. Thus, the pure strategies on which the density of a mixed strategy is positive are the spectrum points, but not the concentration points. The mixed strategy spectrum \(\mu\) (resp. \(\nu\)) will be denoted by \(X_{\mu}\) (resp. \(Y_{\nu}\)).
Proposition. Suppose \(\Gamma =(X,Y,H)\) is a zero-sum two-person game having the value \(\widehat{v}\) in mixed strategies. If \(x_{0}\in X\) and \(\nu^{*}\) is an optimal mixed strategy of player 2 and \(K(x_{0},\nu^{*})<\widehat{v}\) then \(x_{0}\) cannot be the concentration point for an optimal strategy of player 1. \(\sharp\)
Definition. Player 1’s strategy \(\mu_{1}\in\widehat{X}\) dominates strictly strategy \(\mu_{2}\in\widehat{X}\), denoted by \(\mu_{1}>\mu_{2}\), if \(H(\mu_{1},y)>H(\mu_{2},y)\) for all \(y\in Y\), Similarly, player 2’s strategy \(\nu_{1}\in\widehat{Y}\) dominates strictly \(\nu_{2}\in\widehat{Y}\), denoted by \(\nu_{1}>\nu_{2}\), if \(H(x,\nu_{1})<H(x,\nu_{2})\) for all \(x\in X\). Strategies \(\mu_{2}\) and \(\nu_{2}\) are called the strictly dominated if there exist \(\mu_{1}>\mu_{2}\) and \(\nu_{1}>\nu_{2}\). \(\sharp\)
If the last inequalities are satisfied as nonstrict, then we say that \(\mu_{1}\) dominates \(\mu_{2}\), denoted by \(\mu_{1}\geq\mu_{2}\), and \(\nu_{1}\) dominates \(\nu_{2}\), denoted by \(\nu_{1}\geq\nu_{2}\).
Proposition. For a zero-sum infinite game having a solution, none of the player’s strictly dominated pure strategies is contained in the spectrum of his (her) optimal mixed strategies. \(\sharp\)
Proposition. Let \(\Gamma =(X,Y,H)\) be a zero-sum infinite game having a solution ($X$ and \(Y\) are topological spaces), and each element of the open set \(X_{0}\subseteq X\) is dominated by a strategy \(\mu_{0}\) whose spectrum does not intersect \(X_{0}\). Then any solution of the game \(\Gamma^{\prime}=(X\setminus X_{0},Y,H)\) is a solution of the game \(\Gamma\). \(\sharp\)
Games with Continuous Payoff Functions.
Now the two-person zero-sum games \(\Gamma =(X,Y,H)\) are considered with the assumption that the strategy sets \(X\) and \(Y\) are compact sets (more often they will be the subsets of Euclidean spaces), and the function \(H\) is continuous in both variables. The sets \(\widehat{X}\) and \(\widehat{Y}\) of mixed strategies of the players 1 and 2 mean the sets of probability measures given on the \(\sigma\)-fields \({\cal X}\) and \({\cal Y}\) of the Borel subsets of the sets \(X\) and \(Y\), respectively.
Proposition. If \(\Gamma =(X,Y,H)\) is the zero-sum infinite game having the value \(\widehat{v}\) in mixed strategies and the equilibrium point \((\mu^{*},\nu^{*})\), and the functions \(K(\mu^{*},y)\) and \(K(x,\nu^{*})\) are continuous respectively in \(y\) and \(x\), then the folloiwng equalities hold
\[K(\mu^{*},y)=\widehat{v}=K(x,\nu^{*})\mbox{ for }x\in X_{\mu^{*}}\mbox{ and }y\in Y_{\nu^{*}},\]
where \(X_{\mu^{*}}\) and \(Y_{\nu^{*}}\) are the spectrums of mixed strategies \(\mu^{*}\) and \(\nu^{*}\), respectively. \(\sharp\)
Proposition. If the function \(H:X\times Y\rightarrow\mathbb{R}\) is continuous on \(X\times Y\) then the integrals of \(K(\mu ,y)\) and \(K(x,\nu )\) are respectively continuous functions of \(y\) and \(x\) for any fixed mixed strategies \(\mu\in\widehat{X}\) and \(\nu\in\widehat{Y}\). \(\sharp\)
\begin{equation}{\label{petp3}}\tag{34}\mbox{}\end{equation}
Theorem \ref{petp3}. The zero-sum infinite game \(\Gamma =(X,Y,H)\), where \(X\) and \(Y\) are metric compact sets and \(H\) is a continuous function, has a solution in mixed strategies (the value and optimal strategies). \(\sharp\)
The proof of this theorem needs the following lemmas. Recall that the sequence of Borel measures \(\{\mu_{n}\}\) given on the Borel \(\sigma\)-field \(X\) of the compact metric space \(X\) is called weakly convergent if
\[\lim_{n\rightarrow\infty}\int_{X}\phi (x)d\mu_{n}(x)=\int_{X}\phi(x)d\mu (x)\]
for any continuous function \(\phi (x)\) on \(X\).
Lemma. In terms of Theorem \ref{petp3}, the mixed strategy sets \(\widehat{X}\) and \(\widehat{Y}\) (the sets of all Borel probability measures) are compact metric sets in the topology of weak convergence. \(\sharp\)
Note that under conditions of Proposition \ref{petp3}, the set of mixed strategies \(\widehat{X}\) (resp. \(\widehat{Y}\)) of player 1 (resp. player 2) is also a compact set in the ordinary sense, since in this case, the weak convergence of the measure sequence \(\{\mu_{n}\}\) is equivalent to the convergence in the ordinary sense
\[\lim_{n\rightarrow\infty}\mu_{n}(A)=\mu (A)\]
for any Borel set \(A\subseteq X\) with the bound \(A’\) having the zero measure \(\mu (A’)=0\). Denote by \(\underline{v}\) and \(\bar{v}\) respectively the lower and upper values of the game \(\Gamma =(X,Y,H)\).
\begin{equation}{\label{peteq2}}\tag{35}
\underline{v}=\sup_{\mu}\inf_{y}K(\mu, y)\mbox{ and }\bar{v}=\inf_{\nu}\sup_{x}K(x,\nu ).
\end{equation}
Lemma. If the conditions of Theorem \ref{petp3} are satisfied, the extrema in (\ref{peteq2}) are achieved and hence
\[\underline{v}=\max_{\mu\in\widehat{X}}\min_{y\in Y}K(\mu ,y)\mbox{ and }
\bar{v}=\min_{\nu\in\widehat{Y}}\max_{x\in X}K(x,\nu ). \sharp\]
\begin{equation}{\label{petp4}}\tag{36}\mbox{}\end{equation}
Theorem \ref{petp4}. An infinite two-person zero-sum game \(\Gamma =(X,Y,H)\), where \(X\) and \(Y\) are metric compact sets and \(H\) is a continuous function on their product, has \(\epsilon\)-optimal mixed strategies with a finite spectrum for any \(\epsilon >0\). \(\sharp\)
By combining the results of Theorems \ref{petp3} and \ref{petp4}, we may conclude that the infinite two-person zero-sum game with the continuous payoff function and compact strategy sets for any \(\epsilon >0\) has \(\epsilon\)-optimal strategies of the players that are mixtures of a finite number of pure strategies, and the optimal mixed strategies in the class of Borel probability measures.
Games with a Convex Payoff Function.
Definition. Suppose \(X\subset\mathbb{R}^{m}\) and \(Y\subset\mathbb{R}^{n}\) are compact sets, the set \(Y\) is convex, the payoff function \(H:X\times Y\rightarrow\mathbb{R}\) is continuous in all its arguments and is convex with respect to \(y\in Y\) for any fixed value of \(x\in X\). Then the game \(\Gamma =(X,Y,H)\) is called the game with a convex payoff function (a convex game). \(\sharp\)
Definition. Suppose \(X\subset\mathbb{R}^{m}\) and \(Y\subset\mathbb{R}^{n}\) are compact sets, the set \(X\) is convex, the payoff function \(H:X\times Y\rightarrow\mathbb{R}\) is continuous in all its arguments and is concave with respect to \(x\in X\) for any fixed value of \(y\in Y\). Then the game \(\Gamma =(X,Y,H)\) is called the game with a concave payoff function (a concave game). \(\sharp\)
If, however, \(X\subset\mathbb{R}^{m}\) and \(Y\subset\mathbb{R}^{n}\) are compact sets, the sets \(X\) and \(Y\) are convex, the payoff function \(H:X\times Y\rightarrow\mathbb{R}\) is continuous in all its arguments, is convex with respect to \(y\in Y\) for any fixed value of \(x\in X\) and is concave with respect to \(x\in X\) for any fixed value of \(y\in Y\), then the game \(\Gamma =(X,Y,H)\) is called the game with a concave-convex payoff function (a concave-convex game). We shall now consider convex games. Note that similar results are also true for concave games.
Proposition. Suppose \(\Gamma =(X,Y,H)\) is a convex game. Then player 2 has an optimal pure strategy, with the game value being equal to
\[v=\min_{y\in Y}\max_{x\in X}H(x,y). \sharp\]
Proposition. Let \(\Gamma =(X,Y,H)\) be a convex game with a strictly convex payoff function. Player 2 then has a unique optimal strategy that is pure. \(\sharp\)
Proposition. Let \(\Gamma =(X,Y,H)\) be a concave game. The game value \(v\) equals to
\begin{equation}{\label{peteq3}}\tag{37}
v=\max_{x\in X}\min_{y\in Y}H(x,y)
\end{equation}
and every pure strategy \(x^{*}\), on which \(\max\min\) (\ref{peteq3}) is achieved, is optimal for player 1. Moreover, if the function \(H(x,y)\) is strictly concave with respect to \(x\) for every fixed \(y\in Y\), player 1’s optimal strategy is unique. \(\sharp\)
Proposition. Let \(\Gamma =(X,Y,H)\) be a concave-convex game. Then the game value \(v\) is equal to
\begin{equation}{\label{peteq4}}\tag{38}
v=\min_{y\in Y}\max_{x\in X}H(x,y)=\max_{x\in X}\min_{y\in Y}H(x,y).
\end{equation}
In the game \(\Gamma\) there always exists a pure strategy saddle point \((x^{*},y^{*})\), where \(x^{*}\in X\) and \(y^{*}\in Y\) are pure strategies for players 1 and 2, on which exterior extrema in \((\)\ref{peteq4}$)$ are achieved. In this case, if the function \(H(x,y)\) is strictly concave (resp. convex) with respect to \(x\) (resp. \(y\)) for any fixed \(y\in Y\) (resp. \(x\in X\)), then player 1 (resp. player 2) has an optimal unique strategy that is pure. \(\sharp\)
Theorem. In the convex game \(\Gamma =(X,Y,H)\), player 1 has an optimal mixed strategy \(\mu^{*}\) with the finite spectrum composed of no more than \((n+1)\) points of the set \(X\). \(\sharp\)
Theorem. In the concave game \(\Gamma =(X,Y,H)\), player 2 has an optimal mixed strategy \(\nu^{*}\) with a finite spectrum composed of no more than \((m+1)\) points of the set \(Y\). \(\sharp\)
We shall now summarize the results in the following theorem.
Theorem. Let \(\Gamma =(X,Y,H)\) be a convex game. Then the valued \(v\) of the game \(\Gamma\) is determined from
\[v=\min_{y\in Y}\max_{x\in X}H(x,y).\]
Player 1 has an optimal mixed strategy \(\mu_{0}\) with a finite spectrum composed of no more than \((n+1)\) points of the set \(X\). However, all pure strategies \(y_{0}\), on which \(\min_{y}\max_{x}H(x,y)\) is achieved, are optimal for player 2. Furthermore, if the function \(H(x,y)\) for every fixed \(x\in X\) is strictly convex in \(y\), then player 2’s optimal strategy is unique. \(\sharp\)
 
