\chapter[ Game Theory]{Game Theory}
In many situations in engineering and economy there are cases when
the conflicting interests of several decision makers have to be
taken into account simultaneously, and the outcome of the situation
depends on the actions of these decision makers. One of the most
popular methodology and modeling is based on game theory.

Let $N$ denote the number of decision makers (who will be called
\ki{players}\inddef{players}), and for each $k = 1, 2, \ldots, N$ let
$S_k$ be the set of all feasible actions of player $\mathcal{P}_k.$ 
The elements $s_k \in S_k$ are called 
\ki{strategies}\inddef{strategies} of player $\mathcal{P}_k$, $S_k$
is the \ki{strategy set}\inddef{strategy set} of this player. In any
realization of the \ki{game}\inddef{games} each player selects a 
strategy, then the vector $\mathbf{s}=(s_1, s_2, \ldots, s_N)$ $(s_k
\in S_k$, $k = 1, 2, \ldots, N)$ is called a \ki{simultaneous strategy
vector}\inddef{simultaneous strategy vector} of the players. For
each $\mathbf{s} \in S = S_1 \times S_2 \times \cdots \times S_N$ each
player has an outcome which is assumed to be a real value. This
value can be imagined as the utility function value of the
particular outcome, in which this function represents how player
$\mathcal{P}_k$ evaluates the outcomes of the game. If $f_k(s_1,
\ldots, s_N)$ denotes this value, then $f_k:S\rightarrow\R$ is
called the \ki{payoff function}\inddef{payoff
function}\inddef{payoff} of player $\mathcal{P}_k$. The value
$f_k(\mathbf{s})$ is called the \ki{payoff}\inddef{payoff} of player
$\mathcal{P}_k$ and $(f_1(\mathbf{s}), \ldots, f_N(\mathbf{s}))$ is
called the \ki{payoff vector.}\inddef{payoff vector} The number $N$
of players, the sets $S_k$ of strategies and the payoff functions
$f_k$ $(k =1, 2, \ldots, N)$ completely determine and define the
$N$-person game. We will also use the notation
$G=\{N;S_1, S_2, \ldots, S_N; f_1, f_2, \ldots, f_N \}$ for this game.


The solution of game $G$ is the
\ki{Nash-equilibrium,}\inddef{Nash-equilibrium}\nevindex{Nash, John
F., Jr.} which is a simultaneous strategy vector
$\mathbf{s}^{\star} = (s_1^{\star},\ldots,s_N^{\star})$ such that
for all $k$,
\begin{enumerate}
\item $s_k^{\star} \in S_k$;
\item for all $s_k \in S_k$,
\begin{equation}\label{eq1}
 f_k(s_1^{\star},s_2^{\star},\ldots,s_{k-1}^{\star},s_k,s_{k+1}^{\star},\ldots,s_N^{\star})\hspace{-1mm}\leq\hspace{-1mm}
f_k(s_1^{\star},s_2^{\star},\ldots,s_{k-1}^{\star},s_k^{\star},s_{k+1}^{\star},\ldots,s_N^{\star}).
\end{equation}
\end{enumerate}
\noindent Condition $1$ means that the $k$-th component of the
equilibrium is a feasible strategy of player $\mathcal{P}_k$, and
condition $2$ shows that none of the players can increase its payoff
 by unilaterally changing its strategy. In other
words, it is the interest of all players to keep the equilibrium
since if any player departs from the equilibrium, its payoff does
not increase.


\newpage
\section{Finite games \inddef{finite games}}\label{sec1.1}

Game $G$ is called finite if the number of players is finite and all
strategy sets $S_k$ contain finitely many strategies. The most
famous two-person finite game is the \ki{prisoner's
dilemma,}\inddef{prisoner's dilemma} which is the following.


\begin{figure}[!t]
$$
\begin{tabular}{|r|cc|}
\hline
& \multicolumn{2}{|c|}{$Player$  $\mathcal{P}_2$} \\
& N & C \\
\hline $Player$  $\mathcal{P}_1 $ $\begin{array}{r}
\textup{N} \\
\textup{C}
\end{array}$ &
$\begin{array}{c}
(-2,-2) \\
(-1,-10)
\end{array}$ &
$\begin{array}{c}
(-10,-1) \\
(-5,-5)
\end{array}$ \\
\hline
\end{tabular}
$$
\caption{Prisoner's dilemma.}\label{fig:fd}
\end{figure}



\begin{pelda}
The players are two prisoners who committed a serious crime, but the
prosecutor has only insufficient evidence to prosecute them. The
prisoners are held in separate cells and cannot communicate, and the
prosecutor wants them to cooperate with the authorities in order to
get the needed additional information. So $N=2$, and the strategy
sets for both players have two elements: cooperating ($C$), or not
cooperating ($N$). It is told to both prisoners privately that if he
is the only one to confess, then he will get only a light sentence
of $1$ year, while the other will go to prison for a period of 10
years. If both confess, then their reward will be a 5 year prison
sentence each, and if none of them confesses, then they will be
convicted to a less severe crime with sentence of 2 years each. The
objective of both players are to minimize the time spent in prison,
or equivalently to maximize its negative. Figure \ref{fig:fd}  shows
the payoff values, where the rows correspond to the strategies of
player $\mathcal{P}_1$, the columns show the strategies of player
$\mathcal{P}_2$, and for each strategy pair the first number is the
payoff of player $\mathcal{P}_1$, and the second number is the
payoff of player $\mathcal{P}_2$. \noindent Comparing the payoff
values, it is clear that only $(C,C)$ can be equilibrium, since
\begin{eqnarray*}
f_2(\textrm{N,N})=-2&<& f_2(\textrm{N,C})=-1 \koz , \\
f_1(\textrm{N,C})=-10&<& f_1(\textrm{C,C})=-5 \koz , \\
f_2(\textrm{C,N})=-10&<& f_2(C,C)=-5  \koz .
\end{eqnarray*}
\noindent The strategy pair $(C,C)$ is really an equilibrium, since
\begin{equation*}
\begin{split}
f_1(\textrm{C,C}) = -5> f_1(\textrm{N,C}) = -10 \koz , \\
f_2(\textrm{C,C}) = -5> f_2(\textrm{C,N}) = -10  \koz .
\end{split}
\end{equation*}
\noindent In this case we have a unique equilibrium.
\end{pelda}

The existence of an equilibrium is not guaranteed in general, and if
equilibrium exists, it might not be unique.

\begin{pelda}
Modify the payoff values of Figure \ref{fig:fd} as shown in Figure
\ref{fig:fdm}. It is easy to see that no equilibrium exists:
\begin{eqnarray*}
f_1(\textrm{N,N})=1&<&f_1(\textrm{C,N})=2  \koz , \\
f_2(\textrm{C,N})=4&<&f_2(\textrm{C,C})=5  \koz , \\
f_1(\textrm{C,C})=0&<&f_1(\textrm{N,C})=2  \koz , \\
f_2(\textrm{N,C})=1&<&f_2(\textrm{N,N})=2  \koz .
\end{eqnarray*}
\end{pelda}


\begin{figure}[!t]
$$
\begin{tabular}{|r|cc|}
\hline
& \multicolumn{2}{|c|}{$Player$ $\mathcal{P}_2$} \\
& N & C \\
\hline $Player$ $\mathcal{P}_1$ $\begin{array}{r}
\textup{N} \\
\textup{C}
\end{array}$ &
$\begin{array}{c}
(1,2) \\
(2,4)
\end{array}$ &
$\begin{array}{c}
(2,1) \\
(0,5)
\end{array}$ \\
\hline
\end{tabular}
$$
\caption{\label{fig:fdm} Game with no equilibrium.}
\end{figure}

If all payoff values are identical, then we have multiple
equilibria: any strategy pair is an equilibrium.

\subsection{Enumeration}

Let $N$ denote the number of players, and for the sake of notational
convenience let $s_k^{(1)},\ldots,s_k^{(n_k)}$ denote the feasible
strategies of player $\mathcal{P}_k$. That is, $S_k=\{
s_k^{(1)},\ldots,s_k^{(n_k)} \}$. A strategy vector
$\mathbf{s}^\star=(s_1^{(i_1)},\ldots,s_N^{(i_N)})$ is an
equilibrium if and only if for all $k=1,2,\ldots,N$ and $j \in
\{1,2,\ldots,n_k \} \setminus {i_k}$,
$$
f_k(s_1^{(i_1)},\ldots,s_{k-1}^{(i_{k-1})},s_k^{(j)},s_{k+1}^{(i_{k+1})},\ldots,s_N^{(i_N)})
$$
\begin{equation}\label{eq2}
\leq f_k(s_1^{(i_1)},\ldots,s_{k-1}^{(i_{k-1})},s_k^{(i_k)},s_{k+1}^{(i_{k+1})},\ldots,s_N^{(i_N)}).
\end{equation}
Notice that in the case of finite games inequality \eqref{eq1} reduces to \eqref{eq2}.

In applying the enumeration method, inequality \eqref{eq2} is
checked for all possible strategy $N$-tuples $\mathbf{s}^\star
=(s_1^{(i_1)},\ldots,s_N^{(i_N)})$ to see if \eqref{eq2} holds for
all $k$ and $j$. If it does, then $\mathbf{s}^\star$ is an
equilibrium, otherwise not. If during the process of checking for a
particular $\mathbf{s}^\star$ we find a $k$ and $j$ such that
\eqref{eq2} is violated, then $\mathbf{s}^\star$ is not an
equilibrium and we can omit checking further values of $k$ and $j$.
This algorithm is very simple, it consists of $N+2$ imbedded loops
with variables $i_1,i_2,\ldots,i_N,k$ and $j$.

The maximum number of comparisons needed equals
\begin{equation*}
 \left ( \prod_{k=1}^{N}n_k \right ) \left ( \sum_{k=1}^N(n_k -1) \right)  ,
\end{equation*}
\noindent however in practical cases it might be much lower, since
if \eqref{eq2} is violated with some $j$, then the comparison must
stop for the same strategy vector.

The algorithm can formally be given as follows:

\begin{algN}{Prisoner-Enumeration$(S_k)$}\inddef{\textsc{Prisoner-Enumeration}}
1 \' \key{for} \= $i_1 \leftarrow 1$ \key{to} $n_1$ \\
2 \'           \> \key{do} \key{for} \= $i_2 \leftarrow 1$ \key{to} $n_2$\\
3 \'   \>   \>  $\ddots$ \\
4 \'   \>   \>    \>  \key{do} \=  \key{for} \= $i_N \leftarrow 1$ \key{to} $n_N$ \\
5 \'   \>   \>    \>           \>            \> \key{do} \textit{key} $\leftarrow 0$\\
6 \'   \>   \>  \>   \>   \key{for} \= $k \leftarrow 1$ \key{to} $N$\\
7 \'   \>   \>  \>   \>             \> \key{do} \key{for} \= $j \leftarrow 1$ \key{to} $n_k$ \\
8 \'   \>   \>  \>   \>             \>                    \>  \key{do} \key{if} \= (\ref{eq2}) fails \\
9 \'   \>   \>  \>   \>             \>                    \>                    \> \key{then}
\textit{key} $\leftarrow 1$  and go to 10\\
10 \'   \>   \>  \>   \>   \key{if} \> $key=0$ \\
11 \'   \>   \>  \>   \>            \>  \key{then} \= ($s_1^{(i_1)}, \ldots, s_N^{(i_N)}$) is equilibrium  \\
12 \' \key{return} ($s_1^{(i_1)}, \ldots, s_N^{(i_N)}$)
\end{algN}


Consider next the two-person case, $N$=2, and introduce the $n_1
\times n_2$ real matrixes $\mathbf{A}^{(1)}$ and $\mathbf{A}^{(2)}$
with $(i,j)$ elements $f_1(i,j)$ and $f_2(i,j)$ respectively.
Matrixes $\mathbf{A}^{(1)}$ and $\mathbf{A}^{(2)}$ are called the
\ki{payoff matrixes} \inddef{payoff matrixes} of the two players. A
strategy vector $\left(s_1^{(i_1)},s_2^{(i_2)} \right)$ is an
equilibrium if and only if the $(i_1,i_2)$ element in matrix
$\mathbf{A}^{(1)}$ is the largest in its column, and in matrix
$\mathbf{A}^{(2)}$ it is the largest in its row. In the case when
$f_2=-f_1$, the game is called \ki{zero-sum,}\inddef{zero-sum games} 
and $\mathbf{A}^{(2)}=-\mathbf{A}^{(1)}$, so the game can be
completely described by the payoff matrix $\mathbf{A}^{(1)}$ of the
first player. In this special case a strategy vector
$(s_1^{(i_1)},s_2^{(i_2)})$ is an equilibrium if and only if the
element $(i_1,i_2)$ is the largest in its column and smallest in its
row. In the zero-sum cases the equilibria are also called the
\ki{saddle points}\inddef{saddle points} of the games. Clearly, the
enumeration method to find equilibria becomes more simple since we
have to deal with a single matrix only.

The simplified algorithm is as follows:

\begin{algN}{Equilibrium$\mathbf{A}^{(2)}$}\inddef{Equilibrium@\textsc{Equilibrium}}
1 \' \key{for} $i_1 \leftarrow 1$ \key{to} $n_1$ \\
2 \'   \> \key{do} \key{for} $i_2 \leftarrow 1$ \key{to} $n_2$\\
3 \'   \>   \> \key{do} \textit{key} $\leftarrow 0 $\\
4 \'   \>   \>  \key{for} $j \leftarrow 1$ \key{to} $n_1$ \\
5 \'   \>   \>  \> \key{do} \key{if} $a_{ji_2}^{(1)}>a_{i_1i_2}^{(1)}$ \\
6 \'   \>   \>  \> \>  \key{then} \= \textit{key} $\leftarrow 1$ \\
7  \'   \>   \>  \> \>            \> go to 12 \\
8 \'   \>   \> \key{for} $j \leftarrow 1$ \key{to} $n_2$ \\
9 \'   \>   \>  \> \key{do} \key{if} $a_{i_1j}^{(2)}>a_{i_1i_2}^{(2)}$ \\
10 \' \>  \>  \> \> \key{then} \= \textit{key} $\leftarrow 1$ \\
11  \' \>  \>   \>  \>         \> go to 12 \\
12 \'   \>   \>  \key{if} \= \textit{key} = 0 \\
13 \'   \>   \>           \> \key{then} \key{return} ($s_{i_1}^{(1)}, s_{i_2}^{(2)}$) 
\end{algN}

\subsection{Games represented by finite trees}
Many finite games have the common feature that they can be
represented by a finite directed tree with the following properties:
\begin{enumerate}
\item there is a unique root of the tree (which is not the endpoint
of any arc), and the game starts at this node;
\item to each node of the tree a player is assigned and if the game
reaches this node at any time, then this player will decide on the
continuation of the game by selecting an arc originating from this
node. Then the game moves to the endpoint of the chosen arc;
\item to each terminal node (in which no arc originates) an $N$-dimensional
real vector is assigned which gives the payoff values for the
players if the game terminates at this node;
\item each player knows the tree, the nodes he is assigned to, and all
payoff values at the terminal nodes.
\end{enumerate}

For example, the chess-game satisfies the above properties in which
$N=2$, the nodes of the tree are all possible configurations on the
chessboard twice: once with the white player and once with the black
player assigned to it. The arcs represent all possible moves of the
assigned player from the originating configurations. The endpoints
are those configurations in which the game terminates. The payoff
values are from the set $\{ 1,0,-1 \}$ where $1$ means win, $-1$
represents loss, and $0$ shows that the game ends with a tie.

\begin{tetel}\label{th1}
All games represented by finite trees have at least one equilibrium.
\end{tetel}
\inddef{games representable by finite trees}

\begin{biz}
We present the proof of this result here, since it suggests a
practical algorithm to find equilibria. The proof goes by induction
with respect to the number of nodes of the game tree. If the game
has only one node, then clearly it is the only equilibrium.

Assume next that the theorem holds for any tree with less than $n$
nodes ($n \geq 2$), and consider a game $T_0$ with  $n$ nodes. Let
$R$ be the root of the tree and let $r_1,r_2,\ldots,r_m$ ($m < n$)
be the nodes connected to $R$ by an arc. If $T_1,T_2,\ldots,T_m$
denote the disjoint subtrees of $T_0$ with roots
$r_1,r_2,\ldots,r_m$, then each subtree has less than $n$ nodes, so
each of them has an equilibrium. Assume that player $\mathcal{P}_k$
is assigned to $R$. Let $e_1,e_2,\ldots,e_m$ be the equilibrium
payoffs of player $\mathcal{P}_k$ on the subtrees
$T_1,T_2,\ldots,T_m$ and let $e_j=\max \{e_1,e_2,\ldots,e_m \}$.
Then player $\mathcal{P}_k$ will move to node $r_j$ from the root,
and then the equilibrium continues with the equilibrium obtained on
the subtree $T_j$. We note that not all equilibria can be obtained
by this method, however the payoff vectors of all equilibria, which
can obtained by this method, are identical.
\end{biz}

We note that not all equilibria can be obtained by this method,
however the payoff vectors of all equilibria, which can be obtained
by this method, are identical.

The proof of the theorem suggests a dynamic programming-type
algorithm which is called \ki{backward induction.}\inddef{backward
induction} It can be extended to the more general case when the
tree has chance nodes from which the continuations of the game are
random according to given discrete distributions.

\epskep{figs/18.1}{Finite tree of Example 10.3.\label{fig:vegesfa}}

The solution algorithm can be formally presented as follows. Assume
that the nodes are numbered so each arc connects nodes $i$ and $j$
only for $i<j$. The root has to get the smallest number $1$, and the
largest number $n$ is given to one of the terminal nodes. For each
node $i$ let $J(i)$ denote the set of all nodes $j$ such that there
is an arc from $i$ to $j$. For each terminal node $i$, $J(i)$ is
empty, and let $\mathbf{p}^{(i)}=(p_1^{(i)},\ldots,p_N^{(i)})$
denote the payoff vector associated to this node. And finally we
will denote player assigned to node $i$ by $K_i$ for all $i$. The
algorithm starts at the last node $n$ and moves backward in the
order $n,n-1,n-2,\ldots,2$ and $1$. Node $n$ is an endpoint, so
vector $\mathbf{p}^{(n)}$ has been already assigned. If in the
process the next node $i$ is an endpoint, then $\mathbf{p}^{(i)}$ is
already given, otherwise we find the largest among the values
$p^{(j)}_{K_i}$, $j \in J(i)$. Assume that the maximal value occurs
at node $j_i$, then we assign $\mathbf{p}^{(i)}=\mathbf{p}^{(j_i)}$
to node $i$, and move to node $i-1$. After all payoff vectors
$\mathbf{p}^{(n)}, \ \mathbf{p}^{(n-1)}, \ \ldots,\mathbf{p}^{(2)}$
and $\mathbf{p}^{(1)}$ are determined, then vector
$\mathbf{p}^{(1)}$ gives the equilibrium payoffs and the equilibrium
path is obtained by nodes:
$$1 \rightarrow i_1=j_1 \rightarrow i_2=j_{i_1} \rightarrow
i_3=j_{i_2} \rightarrow \ldots ,$$ \noindent until an endpoint is
reached, when the equilibrium path terminates.

At each node the number of comparisons equals the number of arcs
starting at that node minus $1$. Therefore the total number of
comparisons in the algorithm is the total number of arcs minus the
number of nodes.

This algorithm can be formally given as follows:

\begin{alg}{Backward-Induction}\inddef{Backward-Induction@\textsc{Backward-Induction}}
1 \' \key{for} $i \leftarrow n$ \key{to} $1$ \\
2 \'   \> \key{do} \= $p_{K_i}^{(j_i)} \leftarrow \max \{ p_{K_i}^{(l)},l\in J(i) \}$\\
3 \'   \>          \> $\mathbf{p}^{(i)} \leftarrow \mathbf{p}^{(j_i)}$\\
4 \'   print sequence $1$, $i_1(=j_1)$, $i_2(=j_{i_1})$, $i_3(=j_{i_2})$, $\ldots$ \\
  \'   until an endpoint is reached
\end{alg}

\begin{pelda}
Figure \ref{fig:vegesfa} shows a finite tree. In the circle at each
nonterminal node we indicate the player assigned to that node. The
payoff vectors are also shown at all terminal nodes. We have three
players, so the payoff vectors have three elements.

First we number the nodes such that the beginning of each arc has a
smaller number than its endpoint. We indicated these numbers in a
box under each node. All nodes $i$ for $i \geq 11$ are terminal
nodes, as we start the backward induction with node $10$. Since
player $\mathcal{P}_3$ is assigned to this node we have to compare
the third components of the payoff vectors $(2,0,0)$ and $(1,0,1)$
associated to the endpoints of the two arcs originating from node
$10$. Since $1> 0$, player $\mathcal{P}_3$ will select the arc to
node $22$ as his best choice. Hence $j_{10}=22$, and
$\mathbf{p}^{(10)}=\mathbf{p}^{(22)}=(1,0,1)$. Then we check node
$9$. By comparing the third components of vectors
$\mathbf{p}^{(19)}$ and $\mathbf{p}^{(20)}$ it is clear that player
$\mathcal{P}_3$ will select node $20$, so $j_9=20$, and
$\mathbf{p}^{(9)}=\mathbf{p}^{(20)}=(4,1,4)$. In the graph we also
indicated the choices of the players by thicker arcs. Continuing the
procedure in the same way for nodes $8,7,\ldots,1$ we finally obtain
the payoff vector\pelindex{payoff vector} $\mathbf{p}^{(1)}=(4,1,4)$ and equilibrium path $1
\rightarrow 4 \rightarrow 9 \rightarrow 20$.
\end{pelda}



\begin{gyak}
\ujgyak \label{jat1.1} An entrepreneur (E) enters to a market, which
is controlled by a chain store (C). Their competition is a
two-person game. The strategies of the chain store are soft (S),
when it allows the competitor to operate or tough (T), when it tries
to drive out the competitor. The strategies of the entrepreneur are
staying in (I) or leaving (L) the market. The payoff tables \gyakindex{payoff table} of the
two player are assumed to be

%\begin{figure}[!t]
$$
\begin{tabular}{c|cc}
& I & L \\
\hline
S & 2 & 5 \\
T & 0 & 5 \\
\multicolumn{3}{c}{\scriptsize{payoffs of C}}
\end{tabular} \mspace{130mu}
\begin{tabular}{c|cc}
& I & L \\
\hline
S & 2 & 1 \\
T & 0 & 1 \\
\multicolumn{3}{c}{\scriptsize{payoffs of E}}
\end{tabular}
$$
Find the equilibrium.\gyakindex{equilibrium}
\ujgyak \label{1.2} A salesman sells
an equipment to a buyer, which has 3 parts, under the following
conditions. If all parts are good, then the customer pays \$$\alpha$
to the salesman, otherwise the salesman has to pay \$$\beta$ to the
customer. Before selling the equipment, the salesman is able to
check any one or more of the parts, but checking any one costs him
\$$\gamma$. Consider a two-person game in which player
$\mathcal{P}_1$ is the salesman with strategies $0,1,2,3$ (how many
parts he checks before selling the equipment), and player
$\mathcal{P}_2$ is the equipment with strategies $0,1,2,3$ (how many
parts are defective). Show that the payoff matrix of player
$\mathcal{P}_1$ is given as below when we assume that the different
parts can be defective with equal probability.
$$
\begin{tabular}{r|cccc}
& \multicolumn{4}{|c}{player $\mathcal{P}_2$} \\
& 0 & 1 & 2 & 3 \\
\hline player $\mathcal{P}_1$ $\begin{array}{r}
\textup{0} \\
\textup{1} \\
\textup{2} \\
\textup{3}
\end{array}$ &
$\begin{array}{c}
\alpha \\
\alpha - \gamma \\
\alpha - 2\gamma \\
\alpha - 3\gamma
\end{array}$ &
$\begin{array}{c}
-\beta \\
-\frac{2}{3}\beta - \gamma \\
-\frac{1}{3}\beta - \frac{5}{3}\gamma \\
-2\gamma
\end{array}$ &
$\begin{array}{c}
-\beta \\
-\frac{1}{3}\beta - \gamma \\
-\frac{4}{3}\gamma \\
-\frac{4}{3}\gamma
\end{array}$ &
$\begin{array}{c}
-\beta \\
-\gamma \\
-\gamma \\
-\gamma
\end{array}$ \\
\end{tabular}
$$
\ujgyak \label{jat1.3} Assume that in the previous problem the
payoff of the second player is the negative of the payoff of the
salesman. Give a complete description of the number of equilibria as
a function of the parameter values $\alpha,\beta,\gamma.$ Determine
the equilibria in all cases. 
\ujgyak Assume that the  payoff
function of the equipment is its value ($V$ if all parts are good,
and zero otherwise) in the previous exercise. Is there an equilibrium point? 
\vspace{-4mm}
\ujgyak \label{1.5} Exercise \ref{jat1.1}
 can be represented by the tree shown in Figure \ref{gyak:elso}.
 
\epskep{figs/18.2}{Tree for Exercise \ref{1.5}\label{gyak:elso}}

\noindent Find the equilibrium with backward induction. 
\ujgyak Show
that in the one-player case backward induction reduces to the
classical dynamic programming method. 
\ujgyak \label{1.7} Assume
that in the tree of a game some nodes are so called ``chance nodes"
from which the game continuous with given probabilities assigned to
the possible next nodes. Show the existence of the equilibrium for
this more general case. 
\ujgyak Consider the tree given in Figure
\ref{fig:vegesfa}, and double the payoff values of player
$\mathcal{P}_1$, change the sign of the payoff values of player
$\mathcal{P}_2$, and do not change those for Player $\mathcal{P}_3.$
Find the equilibrium of this new game.
\end{gyak}

\section{Continuous games\inddef{continuous games}}
If the strategy sets $S_k$ are connected subsets of finite
dimensional Euclidean Spaces and the payoff functions are
continuous, then the game is considered continuous.

\subsection{Fixed-point methods based on best responses}\label{2.1}

It is very intuitive and usefull from algorithmic point of view to
reformulate the equilibrium concept as follows. For all players
$\mathcal{P}_k$ and $\mathbf{s}=(s_1,s_2,\ldots,s_N) \in S = S_1
\times S_2 \times \cdots \times S_N$ define the mapping:
\begin{equation}\label{eq3}
\begin{split}
B_k(\mathbf{s})=\{ s_k \in S_k |
f_k(s_1,s_2,\ldots,s_{k-1},s_k,s_{k+1},\ldots,s_N) \\
 = \max_{t_k \in S_k} f_k(s_1,s_2,\ldots,s_{k-1},t_k,s_{k+1},\ldots,s_N) \} ,
\end{split}
\end{equation}
\noindent which is the set of the best choices of player
$\mathcal{P}_k$ with given strategies $s_1,s_2,\ldots,s_{k-1},$
$s_{k+1},\ldots,s_N$ of the other players. Note that
$B_k(\mathbf{s})$ does not depend on $s_k$, it depends only on all
other strategies $\mathbf{s}_l$, $k \neq l$. There is no guarantee
that maximum exists for all $\mathbf{s} \in S_1 \times S_2 \times
\cdots \times S_N$. Let $\sum \subseteq S$ be the subset of $S$ such
that $B_k(\mathbf{s})$ exists for all $k$ and
 $\mathbf{s} \in \sum $. A simultaneous strategy vector
$\mathbf{s}^\star=(s_1^\star,s_2^\star,\ldots,s_N^\star)$ is an
equilibrium if and only if $\mathbf{s}^\star \in \sum $, and
$s_k^\star \in B_k(\mathbf{s}^\star)$ for all $k$. By introducing
the \ki{best reply mapping,}\inddef{best reply mapping}
$\mathbf{B}_k(\mathbf{s})=(B_1(\mathbf{s}),\ldots,B_N(\mathbf{s}))$
we can further simplify the above reformulation:

\begin{tetel}\label{th2}
Vector $\mathbf{s}^\star$ is equilibrium if and only if
$\mathbf{s}^\star \in \sum $ and $\mathbf{s}^\star \in
\mathbf{B}(\mathbf{s}^\star).$ 
\end{tetel}

Hence we have shown that the equilibrium-problem of $N$-person games
is equivalent to find fixed points of certain point-to-set mappings.

The most frequently used existence theorems of equilibria are based
on fixed point theorems such as the theorems of
Brouwer,\nevindex{Brouwer, Luitzer Egbertus Jan (1881--1966)}
Kakutani,\nevindex{Kakutani, Shizou}
Banach,\nevindex{Banach, Stephan (1892--1945)}
Tarski\nevindex{Tarski, Alfred (1902--1983)} etc. Any algorithm for finding fixed
points can be successfully applied for computing equilibria.

The most popular existence result is a straightforward application
of the Kakutani-fixed point theorem.

\begin{tetel}\label{th3}
Assume that in an $N$-person game
\begin{enumerate}
\item the strategy sets $S_k$ are nonempty, closed, bounded, convex
subsets of finite dimensional Euclidean spaces;\\
for all $k,$
\item the payoff function $f_k$ are continuous on $S;$ 
\item  $f_k$ is concave in $s_k$ with all fixed
$s_1,\ldots,s_{k-1},s_{k+1},\ldots,s_N.$
\end{enumerate}
\noindent Then there is at least one equilibrium.
\end{tetel}

\begin{pelda}\label{ex4}
Consider a 2-person game, $N=2,$ with strategy sets $S_1=S_2=[0,1],$ 
and payoff functions $f_1(s_1,s_2)=s_1s_2-2s_1^2 +5,$ and
$f_2(s_1,s_2)=s_1s_2 -2s_2^2 + s_2 +3.$ We will first find the best
responses of both players. Both payoff functions are concave
parabolas in their variables with vertices:
$$s_1 = \frac{s_2}{4} \mspace{10mu} \mbox{and} \mspace{10mu} s_2=\frac{s_1+1}{4}.$$
\noindent For all $s_2 \in [0,1]$ and $s_1 \in [0,1]$ these values
are clearly feasible strategies, so
$$B_1(\mathbf{s})=\frac{s_2}{4} \mspace{10mu} \mbox{and} \mspace{10mu}
B_2(\mathbf{s})=\frac{s_1+1}{4}  .$$ \noindent So
$(s_1^\star,s_2^\star)$ is equilibrium if and only if it satisfies
equations:
$$s_1^\star = \frac{s_2^\star}{4} \mspace{10mu} \mbox{and} \mspace{10mu} s_2^\star = \frac{s_1^\star+1}{4}  .$$
\noindent It is easy to see that the unique solution is:
$$s_1^\star = \frac{1}{15} \mspace{10mu} \mbox{and} \mspace{10mu} s_2^\star
=\frac{4}{15}  ,$$ \noindent which is therefore the unique
equilibrium of the game.
\end{pelda}

\begin{pelda}
Consider a portion of a sea-channel, assume it is the unit interval
$[0,1].$ Player $\mathcal{P}_2$ is a submarine hiding in location
$s_2 \in [0,1]$, player $\mathcal{P}_1$ is an airplane dropping a
bomb at certain location $s_1 \in [0,1]$ resulting in a damage
$\alpha e ^{-\beta(s_1-s_2)^2}$ to the submarine. Hence a special
two-person game is defined in which $S_1=S_2=[0,1],$ 
$f_1(s_1,s_2)=\alpha e ^{-\beta(s_1-s_2)^2}$ and
$f_2(s_1,s_2)=-f_1(s_1,s_2).$ With fixed $s_2,$ $f_1(s_1,s_2)$ is
maximal if $s_1=s_2$, therefore the best response of player
$\mathcal{P}_1$ is $B_1(\mathbf{s})=s_2$. Player $\mathcal{P}_2$
wants to minimize $f_1$ which occurs if $|s_1 - s_2|$ is as large as
possible, which implies that
\[ B_2(\mathbf{s}) = \left\{
\begin{array}{ll}
1, & \mbox{if}\mspace{10mu} s_1 < 1/2  , \\
0, & \mbox{if}\mspace{10mu} s_1 > 1/2  ,\\
\{0,1\}, & \mbox{if}\mspace{10mu} s_1= 1/2  .
\end{array}
\right. \] \noindent Clearly, there is no $(s_1,s_2) \in [0,1]
\times [0,1]$ such that $s_1=B_1(\mathbf{s})$ and $s_2 \in
B_2(\mathbf{s}),$ consequently no equilibrium exists.
\end{pelda}



\subsection{Applying Fan's inequality}\nevindex{Fan, Ky}
Define the \ki{aggregation function}\inddef{aggregation function}
$H: S \times S \rightarrow \R$
 as:
\begin{equation}\label{eq4}
H_{\mathbf{r}}(\mathbf{s},\mathbf{z})= \sum_{k=1}^N r_k
f_k(s_1,\ldots,s_{k-1},z_k,s_{k+1},\ldots,s_N)
\end{equation}
\noindent for all $\mathbf{s}=(s_1,\ldots,s_N)$ and
$\mathbf{z}=(z_1,\ldots,z_N)$ from $S$ and some $\mathbf{r} =
(r_1,r_2,\ldots,r_N) > \mathbf{0}.$

\begin{tetel}\label{th4}
Vector $\mathbf{s}^{\star} \in S$ is an equilibrium if and only if
\begin{equation}\label{eq5}
H_{\mathbf{r}}(\mathbf{s}^\star,\mathbf{z}) \leq
H_{\mathbf{r}}(\mathbf{s}^\star,\mathbf{s}^\star)
\end{equation}
\noindent for all $\mathbf{z} \in S.$
\end{tetel}

\begin{biz}
Assume first that $\mathbf{s}^\star$ is an equilibrium, then
inequality \eqref{eq1} holds for all $k$ and $s_k \in S_k$. Adding
the $r_k$-multiples of these relations for $k=1,2,\ldots,N$ we
immediately have \eqref{eq5}.

Assume next that \eqref{eq5} holds for all $\mathbf{z} \in S.$ 
Select any $k$ and $s_k \in S_k$, define
$\mathbf{z}=(s_1^\star,\ldots,s_{k-1}^\star,s_k,s_{k+1}^\star,\ldots,s_N^\star),$ 
and apply inequality \eqref{eq5}. All but the $k$-th terms cancel
and the remaining term shows that inequality \eqref{eq1} holds.
Hence $\mathbf{s}^\star$ is an equilibrium.
\end{biz}

Introduce function $\phi (\mathbf{s},\mathbf{z})=
H_{\mathbf{r}}(\mathbf{s},\mathbf{z})-H_{\mathbf{r}}(\mathbf{s},\mathbf{s}),$ 
then clearly $\mathbf{s}^\star \in S$ is an equilibrium if and only
if
\begin{equation}\label{eq6}
\phi (\mathbf{s}^\star, \mathbf{z}) \leq 0 \mspace{10mu} \mbox{for
all} \mspace{10mu} \mathbf{z} \in S.
\end{equation}
\noindent Relation \eqref{eq6} is known as \ki{Fan's
inequality.}\inddef{Fan's inequality}\nevindex{Fan, Ky}
 It can be rewritten as a variational inequality (see Section
\ref{2.9.2} later), or as a fixed point problem. We show here the
second approach. For all $\mathbf{s} \in S$ define
\begin{equation}\label{eq7}
\Phi (\mathbf{s})= \{ \mathbf{z} | \mathbf{z} \in S, \ \phi
(\mathbf{s},\mathbf{z})= \max_{\mathbf{t} \in S} \phi
(\mathbf{s},\mathbf{t}) \} .
\end{equation}
\noindent Since $\phi (\mathbf{s},\mathbf{s})=0$ for all $\mathbf{s}
\in S,$ relation \eqref{eq6} holds if and only if $\mathbf{s}^\star
\in \Phi (\mathbf{s}^\star),$ that is  $\mathbf{s}^\star$ is a
fixed-point of mapping $\Phi : S \rightarrow 2^S.$ Therefore any
method to find fixed point is applicable for computing equilibria.

The computation cost depends on the type and size of the fixed point
problem and also on the selected method.

\begin{pelda}
Consider again the problem of Example \ref{ex4}. In this case
$$f_1(z_1,s_2)=z_1s_2-2z_1^2+5  \koz ,$$
$$f_2(s_1,z_2)=s_1z_2-2z_2^2+z_2+3  \koz ,$$
\noindent so the aggregate function has the form with $r_1=r_2=1:$
$$H_{\mathbf{r}}(\mathbf{s},\mathbf{z})=z_1s_2-2z_1^2+s_1z_2-2z_2^2+z_2+8 \koz .$$
\noindent Therefore
$$H_{\mathbf{r}}(\mathbf{s},\mathbf{s})=2s_1s_2-2s_1^2-2s_2^2+s_2+8  \koz ,$$
\noindent and
$$\phi(\mathbf{s},\mathbf{z})=z_1s_2-2z_1^2+s_1z_2-2z_2^2+z_2-2s_1s_2+2s_1^2+2s_2^2-s_2  \koz .$$
\noindent Notice that this function is strictly concave in $z_1$ and
$z_2$, and is separable in these variables. At the stationary
points:
$$\frac{\partial \phi}{\partial z_1}=s_2-4z_1 = 0$$
$$\frac{\partial \phi}{\partial z_2}=s_1-4z_2+1=0$$
\noindent implying that at the optimum
$$ z_1 = \frac{s_2}{4} \mspace{10mu} \mbox{and}\mspace{10mu}  z_2=\frac{s_1 +
1}{4}\ \koz ,$$
\noindent since both right hand sides are feasible. At
the fixed point:
$$s_1 = \frac{s_2}{4}\mspace{10mu}  \mbox{and}\mspace{10mu}  s_2=\frac{s_1 +
1}{4}  \koz ,$$ \noindent giving the unique solution:
$$s_1 = \frac{1}{15} \mspace{10mu}  \mbox{and} \mspace{10mu}  s_2=\frac{4}{15}  \koz .$$
\end{pelda}



\subsection{Solving the Kuhn-Tucker conditions}
\index{Kuhn-Tucker conditions}\label{2.3}\nevindex{Kuhn, Harold
W.}\nevindex{Tucker, Albert W.}

Assume that for all $k,$
$$S_k = \{ s_k | \mathbf{g}_k(s_k) \geq \mathbf{0} \}  \koz ,$$
\noindent where  $\mathbf{g}_k : \R^{n_k} \rightarrow \R^{m_k}$ is a
vector variable vector valued function which is continuously
differentiable in an open set $O_k$ containing $S_k$. Assume
furthermore that for all $k$, the payoff function $f_k$ is
continuously differentiable in $s_k$ on $O_k$ with any fixed
$s_1,\ldots,s_{k-1},s_{k+1},\ldots,s_N.$

If $\mathbf{s}^\star = (s_1^\star,\ldots,s_N^\star)$ is an
equilibrium, then for all $k$, $s_k^\star$ is the optimal solution
of problem:
\begin{equation}\label{eq8}
\begin{array}{rcl}
\mbox{maximize}  & &
f_k(s_1^\star,\ldots,s_{k-1}^\star,s_k,s_{k+1}^\star,\ldots,s_N^\star) \\
\mbox{subject to}  & &
 \mathbf{g}_k(s_k)  \geq
\mathbf{0}  .
\end{array}
\end{equation}

By assuming that at $s_k$ the Kuhn-Tucker regularity condition is
satisfied, the solution has to satisfy the Kuhn-Tucker necessary
condition:
\begin{equation}\label{eq9}
\begin{array}{rcl}
\mathbf{u}_k & \geq &  \mathbf{0} \\
\mathbf{g}_k(s_k) & \geq & \mathbf{0} \\
\nabla_k f_k(\mathbf{s}) + \mathbf{u}_k^T \nabla_k \mathbf{g}_k(s_k) & = & \mathbf{0}^T \\
\mathbf{u}_k^T \mathbf{g}_k(s_k) & = & 0  \koz ,
\end{array}
\end{equation}
\noindent where $\mathbf{u}_k$ is an $m_k$-element column vector,
$\mathbf{u}_k^T$ is its transpose, $\nabla_k f_k$ is the gradient of
$f_k$ (as a row vector) with respect to $s_k$ and $\nabla_k
\mathbf{g}_k$ is the Jacobian of function
$g_k.$\nevindex{Jacobi, Carl Gustav Jacob (1804--1851)}

\begin{tetel}\label{th5}
If $\mathbf{s}^{\star}$ is an equilibrium, then there are vectors
$\mathbf{u}_k^\star$ such that relations \eqref{eq9} are satisfied.
\end{tetel}

Relations \eqref{eq9} for $k=1,2,\ldots,N$ give a (usually large)
system of equations and inequalities for the unknowns $s_k$ and
$\mathbf{u}_k$ ($k=1,2,\ldots,N$). Any equilibrium (if exists) has
to be among the solutions. If in addition for all $k$, all
components of $\mathbf{g}_k$ are concave, and $f_k$ is concave in
$s_k$, then the Kuhn-Tucker conditions are also sufficient, and
therefore all solutions of \eqref{eq9} are equilibria.

The computation cost in solving system \eqref{eq9} depends on its
type and the chosen method.

\begin{pelda}\label{ex7}
Consider again the two-person game of the previous example. Clearly,
$$ S_1 = \{ s_1 | s_1 \geq 0, \ 1-s_1 \geq 0 \}  ,$$
$$ S_2 = \{ s_2 | s_2 \geq 0, \ 1-s_2 \geq 0 \}  ,$$
\noindent so we have
$$ \mathbf{g}_1(s_1)=\binom{s_1}{1-s_1} \mspace{10mu} \mbox{and} \mspace{10mu}
\mathbf{g}_2(s_2)=\binom{s_2}{1-s_2}  .$$ \noindent Simple
differentiation shows that
$$ \nabla_1\mathbf{g}_1(s_1)=\binom{1}{-1}, \mspace{10mu}
\nabla_2\mathbf{g}_2(s_2)=\binom{1}{-1}  \koz,$$
$$ \nabla_1 f_1(s_1,s_2)=s_2-4s_1, \mspace{10mu} \nabla_2
f_2(s_1,s_2)=s_1-4s_2+1  ,$$ \noindent therefore the Kuhn-Tucker
conditions can be written as follows:
\begin{eqnarray*}
u_1^{(1)},u_2^{(1)} & \geq & 0 \\
s_1 & \geq & 0  \\
s_1 & \leq & 1 \\
s_2-4s_1+u_1^{(1)}-u_2^{(1)} & = & 0 \\
u_1^{(1)}s_1 + u_2^{(1)}(1-s_1) & = & 0 \\
u_1^{(2)},u_2^{(2)} & \geq & 0 \\
s_2 & \geq & 0 \\
s_2 & \leq & 1 \\
s_1-4s_2+1+u_1^{(2)}-u_2^{(2)} & = & 0 \\
u_1^{(2)}s_2 + u_2^{(2)}(1-s_2) & = & 0  \koz.
\end{eqnarray*}
Notice that $f_1$ is concave in $s_1$, $f_2$ is concave in
$s_2$, and all constraints are linear, therefore all solutions of
this equality-inequality system are really equilibria. By
systematically examining the combination of cases
$$ s_1 =0, \mspace{10mu} 0 < s_1 < 1, \mspace{10mu} s_1=1 \koz, 
$$
and
$$s_2 =0, \mspace{10mu} 0 < s_2 < 1, \mspace{10mu} s_2=1 \koz, 
$$
it is easy to see that there is a unique solution
$$ u_1^{(1)}=u_1^{(2)}=u_2^{(1)}=u_2^{(2)}=0  , \mspace{10mu}
s_1=\frac{1}{15}, \mspace{10mu} s_2=\frac{4}{15}  \koz.$$
\end{pelda}

By introducing slack and surplus variables the
Kuhn-Tucker conditions can be rewritten as a system of equations
with some nonnegative variables. The nonnegativity conditions can be
formally eliminated by considering them as squares of some new
variables, so the result becomes a system of (usually) nonlinear
equations without additional constraints. There is a large set of
numerical methods for solving such systems.


\subsection{Reduction to optimization problems}
Assume that all conditions of the previous section hold. Consider
the following optimization problem:
\begin{equation}\label{eq10}
\begin{array}{rcl}
\mbox{minimize} \mspace{20mu} & & \sum_{k=1}^N \mathbf{u}_k^T
\mathbf{g}_k(s_k) \\
\mbox{subjective to} & & \mathbf{u}_k  \geq  \mathbf{0}  \\
 & & \mathbf{g}_k(s_k)  \geq  \mathbf{0}  \\
 & & \nabla_k f_k (\mathbf{s})+ \mathbf{u}_k^T \nabla_k \mathbf{g}_k(s_k)  =  0 \koz .
\end{array}
\end{equation}

The two first constraints imply that the objective function is
nonnegative, so is the minimal value of it. Therefore system
\eqref{eq9} has feasible solution if and only if the optimal value
of the objective function of problem \eqref{eq10} is zero, and in
this case any optimal solution satisfies relations \eqref{eq9}.

\begin{tetel}\label{th6}
The $N$-person game has equilibrium only if the optimal value of the
objective function is zero. Then any equilibrium is optimal solution
of problem \eqref{eq10}. If in addition all components of
$\mathbf{g}_k$ are concave and $f_k$ is concave in $s_k$ for all
$k$, then any optimal solution of problem \eqref{eq10} is
equilibrium.
\end{tetel}

Hence the equilibrium problem of the $N$-person game has been
reduced to finding the optimal solutions of this (usually nonlinear)
optimization problem. Any nonlinear programming method can be used
to solve the problem.

The computation cost in solving the optimization problem
\eqref{eq10} depends on its type and the chosen method. For example,
if \eqref{eq10} is an LP, and solved by the simplex method, then the
maximum number of operations is exponential. However in particular
cases the procedure terminates with much less operations.

\begin{pelda}
In the case of the previous problem the optimization problem has the
following form:
\begin{eqnarray*}
\mbox{minimize} & & u_1^{(1)}s_1 + u_2^{(1)}(1-s_1)+u_1^{(2)}s_2+u_2^{(2)}(1-s_2)  \\
\mbox{subject to} & & u_1^{(1)},u_1^{(2)},u_2^{(1)},u_2^{(2)}  \geq  0 \\
& & s_1  \geq  0 \\
& & s_1  \leq  1 \\
& & s_2  \geq  0 \\
& & s_2  \leq  1 \\
& & s_2 - 4s_1 + u_1^{(1)} - u_2^{(1)}  =  0 \\
& & s_1 - 4s_2 + 1 + u_1^{(2)} - u_2^{(2)}  =  0 \koz.
\end{eqnarray*}
\noindent Notice that the solution $u_1^{(1)} = u_1^{(2)} =
u_2^{(1)} = u_2^{(2)} = 0$, $s_1=1/15$ and $s_2=4/15$ is feasible
with zero objective function value, so it is also optimal. Hence it
is a solution of system \eqref{eq9} and consequently an equilibrium.
\end{pelda}

\subsubsection{Mixed extension of finite games\inddef{mixed extensions of finite games}}
We have seen earlier that a finite game does not necessary have
equilibrium. Even if it does, in the case of repeating the game many
times the players wish to introduce some randomness into their
actions in order to make the other players confused and to seek an
equilibrium in the stochastic sense. This idea can be modeled by
introducing probability distributions as the strategies of the
players and the expected payoff values as their new payoff
functions.

Keeping the notation of Section \ref{sec1.1}. assume that we have
$N$ players, the finite strategy set of player $\mathcal{P}_k$ is
$S_k = \{ s_k^{(1)},\ldots,s_k^{(n_k)} \}$. In the mixed extension
of this finite game each player selects a discrete probability
distribution on its strategy set and in each realization of the game
an element of $S_k$ is chosen according to the selected
distribution. Hence the new strategy set of player $\mathcal{P}_k$
is
\begin{equation}\label{eq11}
\overline{S}_k = \{ \mathbf{x}_k | \mathbf{x}_k =
(x_k^{(1)},\ldots,x_k^{(n_k)}),\ \sum_{i=1}^{n_k} x_k^{(i)} = 1,\
x_k^{(i)} \geq 0\ \text{for all}\ i \}  ,
\end{equation}
which is the set of all $n_k$-element probability vectors.
The new payoff function of this player is the expected value:
$$
\overline{f}_k(\mathbf{x}_1,\ldots,\mathbf{x}_N)=
$$
\begin{equation}\label{eq12} 
\sum_{i_1= 1}^{n_1} \sum_{i_2 = 1}^{n_2} \ldots \sum_{i_N =1}^{n_N}
f_k(s_1^{(i_1)},s_2^{(i_2)},\ldots,s_N^{(i_N)})x_1^{(i_1)}x_2^{(i_2)}
\ldots x_N^{(i_N)} .
\end{equation}
Notice that the original ``pure'' strategies $s_k^{(i)}$
can be obtained by selecting  $\mathbf{x}_k$ as the $k$-th basis
vector. This is a continuous game and as a consequence of Theorem
\ref{th3} it has at least one equilibrium. Hence if a finite game is
without an equilibrium, its mixed extension has always at least one
equilibrium, which can be obtained by using the methods outlined in
the previous sections.

\begin{pelda}\label{ex9}
Consider the two-person case in which $N=2$, and as in section
\ref{sec1.1} introduce matrices $\mathbf{A}^{(1)}$ and
$\mathbf{A}^{(2)}$ with $(i,j)$ elements $f_1(s_1^{(i)},s_2^{(j)})$
and $f_2(s_1^{(i)},s_2^{(j)})$. In this special case
\begin{equation}\label{eq13}
\overline{f}_k(\mathbf{x}_1,\mathbf{x}_2) = \sum_{i=1}^{n_1}
\sum_{j=1}^{n_2} a_{ij}^{(k)} x_i^{(1)} x_j^{(2)} = \mathbf{x}_1^T
\mathbf{A}^{(k)}\mathbf{x}_2 \    .
\end{equation}
The constraints of $\overline{S}_k$ can be rewritten as:
\begin{eqnarray*}
x_k^{(i)} & \geq & 0 \mspace{40mu} (i=1,2,\ldots,n_k)  \koz, \\
-1 + \sum_{i=1}^{n_k} x_k^{(i)} & \geq & 0  \koz, \\
1 - \sum_{i=1}^{n_k} x_k^{(i)} & \geq & 0  \koz.
\end{eqnarray*}
\noindent so we may select
\begin{equation}\label{eq14}
\mathbf{g}_k (\mathbf{x}_k) = \left(
\begin{array}{c}
x_k^{(1)} \\
\vdots \\
x_k^{(n_k)} \\
\sum_{i=1}^{n_k} x_k^{(i)}- 1 \\
-\sum_{i=1}^{n_k} x_k^{(i)} + 1
\end{array}\right)  \koz.
\end{equation}
\noindent The optimization problem \eqref{eq10} now reduces to the
following:
\begin{equation}\label{eq15}
\begin{array}{rcl}
\mbox{minimize} & & \sum_{k=1}^2 [ \sum_{i=1}^{n_k} u_k^{(i)}
x_k^{(i)} + u_k^{(n_k + 1)} (\sum_{j=1}^{n_k} x_k^{(j)} - 1) +
u_k^{(n_k + 2)} (-
\sum_{j=1}^{n_k} x_k^{(j)} +1 ) ]  \\
\mbox{subject to} & & u_k^{(i)}  \geq  0 \mspace{20mu} (1 \leq i \leq n_k + 2)  \\
& & x_k^{(i)}  \geq  0 \mspace{20mu} (1 \leq i \leq n_k)  \\
& & \mathbf{1}^T \mathbf{x}_k = 1 \\
& & \mathbf{x}_2^T (\mathbf{A}^{(1)})^T + \mathbf{v}_1^T +
(u_1^{(n_1
+1)} - u_1^{(n_1 + 2)})\mathbf{1}_1^T  =  \mathbf{0}_1^T  \\
& & \mathbf{x}_1^T (\mathbf{A}^{(2)}) + \mathbf{v}_2^T + (u_2^{(n_2
+1)} - u_2^{(n_2 + 2)})\mathbf{1}_2^T  =  \mathbf{0}_2^T  \koz,
\end{array}
\end{equation}
\noindent where $\mathbf{v}_k^T = (u_k^{(1)},\ldots.u_k^{(n_k)})$,
$\mathbf{1}_k^T = (1^{(1)},\ldots,1^{(n_k)})$ and $\mathbf{0}_k^T =
(0^{(1)},\ldots,0^{(n_k)})$, $\ k=1,2$  .
\end{pelda}

\noindent Notice this is a quadratic optimization problem.
Computation cost depends on the selected method. Observe that the
problem is usually nonconvex, so there is the possibility of
stopping at a local optimum.

\subsubsection{Bimatrix games.}
Mixed extensions of two-person finite games are called \ki{bimatrix
games.}\inddef{bimatrix games} They were already examined in
Example \ref{ex9}. For notational convenience introduce the
simplifying notation:
$$\mathbf{A}=\mathbf{A}^{(1)},\mathbf{B}=\mathbf{A}^{(2)}, \mathbf{x}
= \mathbf{x}_1,\mathbf{y}=\mathbf{x}_2,m=n_1 \mspace{10mu}
\mbox{and} \mspace{10mu} n=n_2 \koz .$$

\noindent We will show that problem \eqref{eq15} can be rewritten as
quadratic programming problem with linear constraints.

Consider the objective function first. Let
$$ \alpha = u_1^{(m+2)} - u_1^{(m+1)},\mspace{10mu} \mbox{and} \mspace{10mu}
\beta=u_2^{(n+2)}-u_2^{(n+1)} \koz  ,$$ 
then the objective function can be rewritten as follows:
\begin{equation}\label{eq16}
\mathbf{v}_1^T \mathbf{x} + \mathbf{v}_2^T \mathbf{y} - \alpha (
\mathbf{1}_m^T \mathbf{x} - 1) - \beta (\mathbf{1}_n^T \mathbf{y} \koz-
1)  .
\end{equation}
The last two constraints also simplify:
\begin{eqnarray*}
\mathbf{y}^T \mathbf{A}^T + \mathbf{v}_1^T - \alpha \mathbf{1}_m^T
& = & \mathbf{0}_m^T  \koz, \\
\mathbf{x}^T \mathbf{B} + \mathbf{v}_2^T - \beta \mathbf{1}_n^T & =
& \mathbf{0}_n^T,
\end{eqnarray*}
\noindent implying that
\begin{equation}\label{eq17}
\mathbf{v}_1^T = \alpha \mathbf{1}_m^T - \mathbf{y}^T \mathbf{A}^T
\mspace{10mu} \text{and} \mspace{10mu}  \mathbf{v}_2^T = \beta
\mathbf{1}_n^T - \mathbf{x}^T \mathbf{B}\koz,
\end{equation}
\noindent so we may rewrite the objective function again:
$$(\alpha \mathbf{1}_m^T - \mathbf{y}^T \mathbf{A}^T ) \mathbf{x} +
(\beta \mathbf{1}_n^T - \mathbf{x}^T \mathbf{B}) \mathbf{y} - \alpha
( \mathbf{1}_m^T \mathbf{x} - 1) - \beta (\mathbf{1}_n^T \mathbf{y} - 1)$$ 
$$= \alpha + \beta - \mathbf{x}^T(\mathbf{A} + \mathbf{B})\mathbf{y} \koz,
$$
since 
$$\mathbf{1}_m^T \mathbf{x} = \mathbf{1}_n^T \mathbf{y} = 1 \koz.
$$
Hence we have the following quadratic programming problem:
\begin{equation}\label{eq18}
\begin{array}{rcl}
\mbox{maximize} & & \mathbf{x}^T(\mathbf{A} + \mathbf{B})\mathbf{y} - \alpha - \beta   \\
\mbox{subject to} & & \mathbf{x}  \geq  \mathbf{0}  \\
& & \mathbf{y}  \geq  \mathbf{0}  \\
& & \mathbf{1}_m^T \mathbf{x}  =  1  \\
& & \mathbf{1}_n^T \mathbf{y}  =  1  \\
& & \mathbf{A}\mathbf{y}  \leq  \alpha \mathbf{1}_m  \\
& & \mathbf{B}^T \mathbf{x}  \leq  \beta \mathbf{1}_n  \koz,
\end{array}
\end{equation}
\noindent where the last two conditions are obtained from
\eqref{eq17} and the nonnegativity of vectors $\mathbf{v}_1$,
$\mathbf{v}_2$.

\begin{tetel}\label{th7}
Vectors $\mathbf{x}^{\star}$ and $\mathbf{y}^{\star}$ are equilibria
of the bimatrix game if and only if with some $\alpha^{\star}$ and
$\beta^{\star}$,
$(\mathbf{x}^{\star},\mathbf{y}^{\star},\alpha^{\star},\beta^{\star})$
is optimal solution of problem \eqref{eq18}. The optimal value of
the objective function is zero.
\end{tetel}

This is a quadratic programming problem. Computation cost depends on
the selected method. Since it is usually nonconvex, the algorithm
might terminate at local optimum. We know that at the global optimum
the objective function must be zero, which can be used for
optimality check.

\begin{pelda}\label{ex10}
Select
\[ \mathbf{A} = \left(
\begin{array}{rr}
2 & -1 \\
-1 & 1
\end{array}
\right) \]   and
\[ \mathbf{B} = \left(
\begin{array}{rr}
1 & -1 \\
-1 & 2
\end{array}
\right) . \]
Then
\[ \mathbf{A} + \mathbf{B} = \left(
\begin{array}{rr}
3 & -2 \\
-2 & 3
\end{array}
\right) \koz, \]
so problem \eqref{eq18} has the form:
\begin{eqnarray*}\label{eq:eq19}
\mbox{maximize} & & 3x_1 y_1 - 2x_1y_2 - 2x_2 y_1 + 3x_2 y_2 - \alpha - \beta  \\
\mbox{subject to} & & x_1,x_2,y_1,y_2  \geq  0 \\
& & x_1 + x_2  =  1 \\
& & y_1 + y_2  =  1 \\
& & 2y_1 - y_2  \leq  \alpha \\
& & -y_1 + y_2  \leq  \alpha \\
& & x_1 - x_2  \leq  \beta \\
& & -x_1 + 2x_2  \leq  \beta  \koz,
\end{eqnarray*}
\noindent where $\mathbf{x}=(x_1,x_2)^T$ and
$\mathbf{y}=(y_1,y_2)^T$. \noindent We also know from Theorem
\ref{th7} that the optimal objective function value is zero,
therefore any feasible solution with zero objective function value
is necessarily optimal. It is easy to see that the solutions
\begin{eqnarray*}
\mathbf{x}=\binom{1}{0}, \ \mathbf{y}=\binom{0}{1}, \ \alpha = 2, \beta = 1 \koz,  \\
\mathbf{x}=\binom{0}{1}, \ \mathbf{y}=\binom{1}{0}, \ \alpha = 1, \ \beta = 2 \koz,  \\
\mathbf{x}=\binom{0.6}{0.4}, \ \mathbf{y}=\binom{0.4}{0.6}, \ \alpha = 0.2, \ \beta = 0.2
\end{eqnarray*}
are all optimal, so they provide equilibria.
\end{pelda}

One might apply relations \eqref{eq9} to find equilibria by solving
the equality-inequality system instead of solving an optimization
problem. In the case of bimatrix games problem \eqref{eq9}
simplifies as
\begin{equation}\label{eq19}
\begin{array}{rcl}
\mathbf{x}^T\mathbf{A}\mathbf{y} & = & \alpha \\
\mathbf{x}^T\mathbf{B}\mathbf{y} & = & \beta  \\
\mathbf{A}\mathbf{y} & \leq & \alpha \mathbf{1}_m  \\
\mathbf{B}^T \mathbf{x} & \leq & \beta \mathbf{1}_n  \\
\mathbf{x} & \geq & \mathbf{0}_m  \\
\mathbf{y} & \geq & \mathbf{0}_n  \\
\mathbf{1}_m^T \mathbf{x} = \mathbf{1}_n^T \mathbf{y} & = & 1  \koz,
\end{array}
\end{equation}
\noindent which can be proved along the lines of the derivation of
the quadratic optimization problem.

The computation cost of the solution of system \eqref{eq19} depends
on the particular method being selected.

\begin{pelda}\label{ex11}
Consider again the bimatrix game of the previous example. Substitute
the first and second constraints $\alpha= \mathbf{x}^T \mathbf{A}
\mathbf{y}$ and $\beta=\mathbf{x}^T\mathbf{B}\mathbf{y}$ into the
third and fourth condition to have
\begin{eqnarray*}
2y_1 -y_2 & \leq & 2x_1 y_1 - x_1 y_2 - x_2y_1 + x_2y_2 \\
-y_1 + y_2 & \leq & 2x_1y_1 - x_1 y_2 - x_2 y_1 + x_2 y_2 \\
x_1 - x_2 & \leq & x_1 y_1 -x_1 y_2 -x_2 y_1 + 2x_2 y_2 \\
-x_1 + 2x_2 & \leq & x_1 y_1 - x_1y_2 - x_2y_1 + 2x_2y_2 \\
x_1,x_2,y_1,y_2 & \geq & 0  \\
x_1 +x_2  =  y_1 + y_2 &  = & 1  \koz.
\end{eqnarray*}
\noindent It is easy to see that the solutions given in the previous
example solve this system, so they are equilibria.
\end{pelda}

We can also rewrite the equilibrium problem of bimatrix games as an
equality-inequality system with mixed variables. Assume first that
all elements of $\mathbf{A}$ and $\mathbf{B}$ are between $0$ and
$1$. This condition is not really restrictive, since by using linear
transformations
$$ \overline{\mathbf{A}} = a_1 \mathbf{A} + b_1 \mathbf{1} \mspace{10mu}
\mbox{and} \mspace{10mu} \overline{\mathbf{B}} = a_2 \mathbf{B} +
b_2 \mathbf{1}  \koz,
$$ 
where $a_1,a_2 > 0$, and $\mathbf{1}$ is the matrix all elements of which equal $1$, 
the equilibria remain the same and all matrix elements can be transformed into interval $[0,1]$.
\begin{tetel}\label{th8}
Vectors $\mathbf{x}$, $\mathbf{y}$ are an equilibrium if and only if
there are real numbers $\alpha,\beta$ and zero-one vectors
$\mathbf{u}$, and $\mathbf{v}$ such that
\begin{equation}\label{eq20}
\begin{array}{rcccccl}
 0 & \leq & \alpha \mathbf{1}_m - \mathbf{A} \mathbf{y} & \leq &
\mathbf{1}_m - \mathbf{u} &  \leq & \mathbf{1}_m - \mathbf{x} \\
0 & \leq & \beta \mathbf{1}_n - \mathbf{B}^T \mathbf{x} &  \leq &
\mathbf{1}_n -\mathbf{v} & \leq & \mathbf{1}_n - \mathbf{y} \\
 & & & & \mathbf{x} & \geq & \mathbf{0}_m \\
& & & & \mathbf{y} &  \geq & \mathbf{0}_n \\
& & \mathbf{1}_m^T \mathbf{x} &  = & \mathbf{1}_n^T \mathbf{y} &  =
& 1  \koz,
\end{array}
\end{equation}
\end{tetel}
where $\mathbf{1}$ denotes the vector with all unit elements.

\begin{biz}
Assume first that $\mathbf{x}$, $\mathbf{y}$ is an equilibrium, then
with some $\alpha$ and $\beta$, \eqref{eq19} is satisfied. Define
\[ u_i = \left\{
\begin{array}{ll}
1, & \mbox{if  } x_i > 0  \koz,\\
0, & \mbox{if  } x_i = 0  \koz,
\end{array}\right. \mspace{10mu}
\text{and} \mspace{10mu} v_j = \left \{
\begin{array}{cr}
1, & \mbox{if  } y_j > 0  \koz, \\
0, & \mbox{if  } y_j = 0  \koz.
\end{array}\right. \]
Since all elements of $\mathbf{A}$ and $\mathbf{B}$ are
between $0$ and $1$, the values $\alpha = \mathbf{x}^T
\mathbf{A}\mathbf{y}$ and $\beta = \mathbf{x}^T \mathbf{B}\mathbf{y}
$ are also between $0$ and $1$. Notice that
$$ 0 = \mathbf{x}^T (\alpha \mathbf{1}_m - \mathbf{A} \mathbf{y})
= \mathbf{y}^T (\beta \mathbf{1}_n - \mathbf{B}^T \mathbf{x}) \koz,$$
which implies that \eqref{eq20} holds.

Assume next that \eqref{eq20} is satisfied. Then
$$ \mathbf{0} \leq \mathbf{x} \leq \mathbf{u} \leq \mathbf{1}_m \mspace{10mu}
\mbox{and}\mspace{10mu} \mathbf{0} \leq \mathbf{y} \leq \mathbf{v}
\leq \mathbf{1}_n  \koz.$$ 
If $u_i=1$, then $\alpha -
\mathbf{e}_i^T \mathbf{A}\mathbf{y} = 0$, (where $\mathbf{e}_i$ is
the $i$-th basis vector), and if $u_i=0$, then $x_i=0$. Therefore
$$ \mathbf{x}^T (\alpha \mathbf{1}_m - \mathbf{A}\mathbf{y}) = 0  \koz,$$
implying that $\alpha = \mathbf{x}^T
\mathbf{A}\mathbf{y}$. We can similarly show that $\beta =
\mathbf{x}^T \mathbf{B} \mathbf{y}$. Thus \eqref{eq19} is satisfied,
so, $\mathbf{x},\mathbf{y}$ is an equilibrium.
\end{biz}

The computation cost of the solution of system \eqref{eq20} depends
on the particular method being seleced.

\begin{pelda}\label{ex12}
In the case of the bimatrix game introduced earlier in Example
\ref{ex10} we have the following:
\[ %begin{equation*}
\begin{split}
\begin{array}{rcccccl}
0 & \leq & \alpha - 2y_1 + y_2 & \leq & 1 - u_1 &  \leq & 1 - x_1 \\
0 & \leq & \alpha + y_1 - y_2 & \leq & 1 - u_2 & \leq & 1 - x_2 \\
0 & \leq & \beta - x_1 + x_2 & \leq & 1 - v_1 & \leq & 1 - y_1 \\
0 & \leq & \beta + x_1 - 2x_2 & \leq & 1 - v_2 & \leq & 1 - y_2 \\
& & x_1+x_2 &  = & y_1 + y_2 & = & 1
\end{array}
\\
\begin{array}{rcl}
x_1,x_2,y_1,y_2 & \geq & 0 \\
u_1,u_2,v_1,v_2 & \in & \{0,1\} \koz.
\end{array}
\end{split}
\] 
Notice that all three solutions given in Example
\ref{ex10} satisfy these relations with
$$\mathbf{u}=(1,0), \ \  \mathbf{v}=(0,1)$$
$$\mathbf{u}=(0,1), \ \ \mathbf{v}=(1,0)$$
and 
$$\mathbf{u}=(1,1), \ \ \mathbf{v}=(1,1)\koz,$$ 
respectively.
\end{pelda}

\subsubsection{Matrix games.}
In the special case of $\mathbf{B}=-\mathbf{A}$, bimatrix games are
called \ki{matrix games}\inddef{matrix games} and they are
represented by matrix $\mathbf{A}$. Sometimes we refer to the game
as matrix $\mathbf{A}$ game. Since $\mathbf{A} + \mathbf{B} =
\mathbf{0}$, the quadratic optimization problem \eqref{eq18} becomes
linear:
\begin{equation}\label{eq21}
\begin{array}{rcl}
\mbox{minimize} & & \alpha + \beta \\
\mbox{subject to} & & \mathbf{x}  \geq  \mathbf{0}  \\
& & \mathbf{y}  \geq  \mathbf{0}  \\
& & \mathbf{1}_m \mathbf{x}  =   1  \\
& & \mathbf{1}_n \mathbf{y}  =  1  \\
& & \mathbf{A} \mathbf{y}  \leq  \alpha \mathbf{1}_m \\
& & \mathbf{A}^T \mathbf{x}  \geq   -\beta \mathbf{1}_n \koz.
\end{array}
\end{equation}

From this formulation we see that the set of the equilibrium
strategies is a convex polyhedron. Notice that variables
$(\mathbf{x}, \beta)$ and $(\mathbf{y},\alpha)$ can be separated, so
we have the following result.

\begin{tetel}\label{th9}
Vectors $\mathbf{x}^\star$ and $\mathbf{y}^\star$ give an
equilibrium of the matrix game if and only if with some
$\alpha^\star$ and $\beta^\star$, $(\mathbf{x}^\star, \beta^\star)$
and $(\mathbf{y}^\star,\alpha^\star)$ are optimal solutions of the
linear programming problems:
\begin{equation}\label{eq22}
\begin{array}{rclcrcl}
\mbox{minimize} & & \alpha   & & \mbox{minimize} & & \beta  \\
\mbox{subject to} & & \mathbf{y}  \geq  \mathbf{0}_n
& & \mbox{subject to} & & \mathbf{x}  \geq  \mathbf{0}_m \\
& & \mathbf{1}_n^T \mathbf{y}  =  1 & &  & & \mathbf{1}_m^T \mathbf{x}   =  1  \\
& & \mathbf{A} \mathbf{y}  \leq  \alpha \mathbf{1}_m & & & &
\mathbf{A}^T \mathbf{x}   \geq  -\beta \mathbf{1}_n  \koz.
\end{array}
\end{equation}
\end{tetel}
Notice that at the optimum, $\alpha + \beta = 0$. The
optimal $\alpha$ value is called the \ki{value of the matrix game.}\inddef{value of matrix games} 

Solving problem \eqref{eq22} requires exponential number of
operations if the simplex method is chosen. With polynomial
algorithm (such as the interior point method) the number of
operations is only polynomial.

\begin{pelda}\label{ex13}
Consider the matrix game with matrix:
$$ \mathbf{A} = \left(
\begin{array}{rrr}
2 & 1 & 0 \\
2 & 0 & 3 \\
-1 & 3 & 3
\end{array}
\right)  \koz. $$ 
In this case problems \eqref{eq22} have the form:
\begin{equation*}
\begin{array}{rclcrcl}
\mbox{minimize}   & & \mspace{50mu} \alpha
\mspace{100mu}  \mbox{and}   & & \mbox{minimize} & & \mspace{50mu} \beta  \\
\mbox{subject to} & & y_1,y_2,y_3  \geq 0  & & \mbox{subject to}  & & x_1,x_2,x_3  \geq  0 \\
 & & y_1+y_2+y_3  =  1 & & & & x_1+x_2+x_3  =  1 \\
& & 2y_1 + y_2 - \alpha  \leq  0  & & & & 2x_1 + 2x_2 -x_3 + \beta  \geq  0 \\
& & 2y_1 + 3y_3 - \alpha  \leq  0 & & & & x_1 + 3x_3 + \beta  \geq  0 \\
& & -y_1 + 3y_2 + 3y_3 - \alpha  \leq  0 & & & & 3x_2 + 3x_3 + \beta
\geq
 0  \koz.
\end{array}
\end{equation*}
\noindent The application of the simplex method shows that the
optimal solutions are $\alpha = 9/7$, $\mathbf{y}=(3/7,3/7,1/7)^T$,
$\beta = -9/7$, and $\mathbf{x}=(4/7,4/21,5/21)^T$.
\end{pelda}

We can also obtain the equilibrium by finding feasible solutions of
a certain set of linear constraints. Since at the optimum of problem
(\ref{eq21}), $\alpha + \beta = 0$, vectors $\mathbf{x}$,
$\mathbf{y}$ and scalers $\alpha$ and $\beta$ are optimal solutions
if and only if
\begin{equation}\label{eq23}
\begin{array}{rcl}
\mathbf{x}, \mathbf{y} & \geq & \mathbf{0} \\
\mathbf{1}_m^T \mathbf{x} &  = & 1 \\
\mathbf{1}_n^T  \mathbf{y} & = & 1 \\
\mathbf{A} \mathbf{y} & \leq & \alpha \mathbf{1}_m  \\
\mathbf{A}^T \mathbf{x} & \geq & \alpha \mathbf{1}_n  \koz.
\end{array}
\end{equation}

The first phase of the simplex method has to be used to solve system
\eqref{eq23}, where the number of operations might be experimental.
However in most practical examples much less operations are needed.


\begin{pelda}\label{ex14}
Consider again the matrix game of the previous example. In this case
system \eqref{eq23} has the following form:
\begin{eqnarray*}
x_1,x_2,x_3,y_1,y_2,y_3 & \geq & 0 \\
x_1 + x_2 + x_3 = y_1 + y_2 +y_3 & = & 1 \\
2y_1 + y_2 & \leq & \alpha \\
2y_1 + 3y_3 & \leq & \alpha \\
-y_1 + 3y_2 + 3y_3 & \leq & \alpha \\
2x_1 + 2x_2 - x_3 & \geq & \alpha \\
x_1 + 3x_3 & \geq & \alpha \\
3x_2 + 3x_3 & \geq & \alpha \koz .
\end{eqnarray*}
\noindent It is easy to see that $\alpha = 9/7$, $\mathbf{x} =
(4/7,4/21,5/21)^T$, $\mathbf{y}=(3/7,3/7,1/7)^T$ satisfy these
relations, so $\mathbf{x}$, $\mathbf{y}$ is an equilibrium.
\end{pelda}



\subsection{Method of fictitious play}
Consider now a matrix game with matrix $\mathbf{A}$. The main idea
of this method is that at each step both players determine their
best pure strategy choices against the average strategies of the
other player of all previous steps. Formally the method can be described as follows.

Let $\mathbf{x}_1$ be the initial (mixed) strategy of player
$\mathcal{P}_1$. Select $\mathbf{y}_1=\mathbf{e}_{j_1}$ (the $j_1$st
basis vector) such that
\begin{equation}\label{eq24}
\mathbf{x}_1^T \mathbf{A} \mathbf{e}_{j_1} = \min_j \{
\mathbf{x}_1^T \mathbf{A} \mathbf{e}_{j} \}  \koz.
\end{equation}
In any further step $k \geq 2$, let
\begin{equation}\label{eq25}
\overline{\mathbf{y}}_{k-1}=\frac{1}{k-1}((k-2)\overline{\mathbf{y}}_{k-2}+\mathbf{y}_{k-1}) \koz,
\end{equation}
and select $\mathbf{x}_k = \mathbf{e}_{i_k}$so that
\begin{equation}\label{eq26}
\mathbf{e}_{i_k}^T \mathbf{A} \overline{\mathbf{y}}_{k-1} = \max_i
\{ \mathbf{e}_i^T \mathbf{A} \overline{\mathbf{y}}_{k-1} \}  \koz.
\end{equation}
Let then
\begin{equation}\label{eq27}
\overline{\mathbf{x}}_k = \frac{1}{k} ((k-1)
\overline{\mathbf{x}}_{k-1} + \mathbf{x}_k)  \koz,
\end{equation}
and select $\mathbf{y}_k = \mathbf{e}_{j_k}$ so that
\begin{equation}\label{eq28}
\overline{\mathbf{x}}_k^T \mathbf{A} \mathbf{e}_{j_k} = \min_j \{
\overline{\mathbf{x}}_k^T \mathbf{A} \mathbf{e}_j \}  \koz.
\end{equation}

By repeating the general step for $k=2,3,\ldots$ two sequences are
generated: $\{ \overline{\mathbf{x}}_k \}$, and $\{
\overline{\mathbf{y}}_k \}$. We have the following result:

\begin{tetel}\label{th10}
Any cluster point of these sequences is an equilibrium of the matrix
game. Since all $ \overline{\mathbf{x}}_k $ and
$\overline{\mathbf{y}}_k $ are probability vectors, they are
bounded. Therefore there is at least one cluster point.
\end{tetel}


Assume, matrix $\mathbf{A}$ is $m \times n$. In \eqref{eq24} we need
$mn$ multiplications. In \eqref{eq25} and \eqref{eq27} $m+n$
multiplications and divisions. In \eqref{eq26} and \eqref{eq28} $mn$
multiplications. If we make $L$ iteration steps, then the total
number of multiplications and divisions is:
$$ 
mn + L [2(m+n) + 2mn] =\ominus (Lmn)\koz.
$$

The formal algorithm is as follows:

\begin{algN}{Matrix-Equilibrium$(\mathbf{A},\overline{\mathbf{x}}_1^T)$}
\inddef{Matrix-Equilibrium@\textsc{Matrix-Equilibrium}}
1 \' $k \leftarrow 1$\\
2 \' define $j_1$ such that $\mathbf{x}_1^T \mathbf{A}
\mathbf{e}_{j_1} = \min_j \{ \mathbf{x}_1^T \mathbf{A}
\mathbf{e}_{j} \}$ \\
3 \' $\mathbf{y}_1 \leftarrow \mathbf{e}_{j_1}$ \\
4 \' $k \leftarrow k+1$ \\
5 \' $\overline{\mathbf{y}}_{k-1} \leftarrow
\frac{1}{k-1}((k-2)\overline{\mathbf{y}}_{k-2}+\mathbf{y}_{k-1})$\\
6 \' define $i_k$ such that $\mathbf{e}_{i_k}^T \mathbf{A}
\overline{\mathbf{y}}_{k-1} = \max_i \{ \mathbf{e}_i^T \mathbf{A}
\overline{\mathbf{y}}_{k-1} \}$ \\
7 \' $\mathbf{x}_k \leftarrow \mathbf{e}_{i_k}$ \\
8 \' $\overline{\mathbf{x}}_k \leftarrow \frac{1}{k} ((k-1)
\overline{\mathbf{x}}_{k-1} + \mathbf{x}_k)$ \\
9 \' define $j_k$ such that $\overline{\mathbf{x}}_k^T \mathbf{A}
\mathbf{e}_{j_k} = \min_j \{ \overline{\mathbf{x}}_k^T \mathbf{A}
\mathbf{e}_j \}$ \\
10 \' $\mathbf{y}_k \leftarrow \mathbf{e}_{j_k}$ \\
11 \' \key{if} $||\overline{\mathbf{x}}_k-\overline{\mathbf{x}}_{k-1}||<\varepsilon$
and $||\overline{\mathbf{y}}_{k-1}-\overline{\mathbf{x}}_{k-2}||<\varepsilon$ \\
12 \' \> \key{then} \= $\left( \overline{\mathbf{x}}_k, \overline{\mathbf{y}}_{k-1} \right)$ is equilibrium \\
13 \' \>            \> \key{else} go back to 4
\end{algN}
\noindent Here $\varepsilon >0$ is a user selected error tolerance.


\begin{pelda}\label{ex15}
We applied the above method for the matrix game of the previous
example and started the procedure with $\mathbf{x}_1 = (1,0,0)^T$.
After 100 steps we obtained $\overline{\mathbf{x}}_{101} =
(0.446,0.287,0.267)^T$ and $\overline{\mathbf{y}}_{101} =
(0.386,0.436,0.178)^T$. Comparing it to the true values of the
equilibrium strategies we see that the error is below $0.126$,
showing the very slow convergence of the method.
\end{pelda}


\subsection{Symmetric matrix games}\inddef{symmetric matrix games}
A matrix game with skew-symmetric matrix is called symmetric. In
this case $\mathbf{A}^T = - \mathbf{A}$ and the two linear
programming problems are identical. Therefore at the optimum $\alpha
= \beta = 0$, and the equilibrium strategies of the two players are
the same. Hence we have the following result:
\begin{tetel}\label{th11}
A vector $\mathbf{x}^\star$ is equilibrium of the symmetric matrix
game if and only if
\begin{equation}\label{eq29}
\begin{array}{rcl}
\mathbf{x} & \geq & \mathbf{0} \\
\mathbf{1}^T \mathbf{x} & = & 1 \\
\mathbf{A} \mathbf{x} & \leq & \mathbf{0}  \koz.
\end{array}
\end{equation}
\end{tetel}

Solving system \eqref{eq29} the first phase of the simplex method is
needed, the number of operations is exponential in the worst case
but in practical case usually much less.

\begin{pelda}\label{ex16}
Consider the symmetric matrix game with matrix $ \mathbf{A} = \left(
\begin{array}{rr}
0 & 1 \\
-1 & 0
\end{array}
\right)$. In this case relations \eqref{eq29} simplify as follows:
\begin{eqnarray*}
x_1,x_2 & \geq & 0 \\
x_1 +x_2 & = & 1 \\
x_2 & \leq & 0 \\
-x_1 & \leq & 0  \koz.
\end{eqnarray*}
\noindent Clearly the only solution is $x_1 = 1$ and $x_2 =0$, that
is the first pure strategy.
\end{pelda}

We will see in the next subsection that linear programming problems
are equivalent to symmetric matrix games so any method for solving
such games can be applied to solve linear programming problems, so
they serve as alternative methodology to the simplex method. As we
will see next, symmetry is not a strong assumption, since any matrix
game is equivalent to a symmetric matrix game.

Consider therefore a matrix game with matrix $\mathbf{A}$, and
construct the skew-symmetric matrix
$$ \mathbf{P} = \left(
\begin{array}{ccc}
\mathbf{0}_{m \times m} & \mathbf{A} & -\mathbf{1}_m \\
-\mathbf{A}^T & \mathbf{0}_{n \times n} & \mathbf{1}_n \\
\mathbf{1}_m^T & -\mathbf{1}_n^T & 0
\end{array}\right)  ,$$
\noindent where all components of vector $\mathbf{1}$ equal 1.
Matrix games $\mathbf{A}$ and $\mathbf{P}$ are equivalent in the
following sense. Assume that $\mathbf{A} > \mathbf{0}$, which is not
a restriction, since by adding the same constant to all element of
$\mathbf{A}$ they become positive without changing equilibria.

\begin{tetel}\label{th12}
\begin{enumerate}
\item If $\mathbf{z}= \left(
\begin{array}{ccc}
\mathbf{u} \\
\mathbf{v} \\
\lambda
\end{array} \right)$
is an equilibrium strategy of matrix game $\mathbf{P}$ then with
$\mathbf{a}=(1-\lambda)/2$, $\mathbf{x} = (1/a) \mathbf{u}$ and
$\mathbf{y}=(1/a)\mathbf{v}$ is an equilibrium of matrix game
$\mathbf{A}$ with value $v = \lambda/a$;
\item If $\mathbf{x},\mathbf{y}$ is an equilibrium of matrix game
$\mathbf{A}$ and $v$ is the value of the game, then
$$ \mathbf{z} = \frac{1}{2+v} \left(
\begin{array}{ccc}
\mathbf{x} \\
\mathbf{y} \\
v
\end{array} \right)$$
\noindent is equilibrium strategy of matrix game $\mathbf{P}$.
\end{enumerate}
\end{tetel}
\begin{biz}
Assume first that $\mathbf{z}$ is an equilibrium strategy of game
$\mathbf{P}$, then $\mathbf{u} \geq \mathbf{0}$, $\mathbf{v} \geq
\mathbf{0}$, $\mathbf{P} \mathbf{z} \leq \mathbf{0}$, so
\begin{equation}\label{eq30}
\begin{array}{rcl}
\mathbf{A}\mathbf{v} - \lambda \mathbf{1}_m & \leq & \mathbf{0} \\
-\mathbf{A}^T \mathbf{u} + \lambda \mathbf{1}_n & \leq & \mathbf{0} \\
\mathbf{1}_m^T \mathbf{u} - \mathbf{1}_n^T \mathbf{v} & \leq & 0  \koz.
\end{array}
\end{equation}
\noindent First we show that $0< \lambda <1$, that is $a \neq 0$. If
$\lambda = 1$, then (since $\mathbf{z}$ is a probability vector)
$\mathbf{u} = \mathbf{0}$ and $\mathbf{v} = \mathbf{0}$,
contradicting the second inequality of \eqref{eq30}. If $\lambda =
0$, then $\mathbf{1}_m^T \mathbf{u} + \mathbf{1}_n^T \mathbf{v} =
1$, and by the third inequality of \eqref{eq30}, $\mathbf{v}$ must
have at least one positive component which makes the first
inequality impossible.

Next we show that $\mathbf{1}^T \mathbf{u} = \mathbf{1}^T
\mathbf{v}$. From \eqref{eq30} we have
\begin{eqnarray*}
\mathbf{u}^T \mathbf{A} \mathbf{v} - \lambda \mathbf{u}^T
\mathbf{1}_m & \leq & 0  \koz, \\
-\mathbf{v}^T \mathbf{A}^T \mathbf{u} + \lambda \mathbf{u}^T
\mathbf{1}_n & \leq & 0
\end{eqnarray*}
and by adding these inequalities we see that
$$ 
\mathbf{v}^T \mathbf{1}_n - \mathbf{u}^T
\mathbf{1}_m  \leq  0\koz , 
$$ 
and combining this relation with the third inequality of \eqref{eq30} we see that
$\mathbf{1}_m^T \mathbf{u} - \mathbf{1}_n ^T \mathbf{v} = 0$.

Select $a = (1 - \lambda)/2 \neq 0$, then $\mathbf{1}_m^T \mathbf{u}
= \mathbf{1}_n ^T \mathbf{v} = a$, so both $\mathbf{x} =
\mathbf{u}/a$, and $\mathbf{y} = \mathbf{v}/a$ are probability
vectors, furthermore from \eqref{eq30},
\begin{equation*}
\begin{array}{rcccl}
\mathbf{A}^T \mathbf{x} & = & \frac{1}{a} \mathbf{A}^T \mathbf{u}
& \geq & \frac{\lambda}{a} \mathbf{1}_n \koz, \\
\mathbf{A} \mathbf{y} & = & \frac{1}{a} \mathbf{A} \mathbf{v} & \leq
& \frac{\lambda}{a} \mathbf{1}_m \koz.
\end{array}
\end{equation*}
So by selecting $\alpha = \lambda / a$ and $\beta =
-\lambda / a$, $\mathbf{x}$ and $\mathbf{y}$ are feasible solutions
of the pair \eqref{eq22} of linear programming problems with $\alpha
+ \beta =0$, therefore $\mathbf{x},\mathbf{y}$ is an equilibrium of
matrix game $\mathbf{A}$. Part 2. can be proved in a similar way,
the details are not given here.
\end{biz}



\subsection{Linear programming and matrix games}
In this section we will show that linear programming problems can be
solved by finding the equilibrium strategies of symmetric matrix
games and hence, any method for finding the equilibria of symmetric
matrix games can be applied instead of the simplex method.

Consider the primal-dual linear programming problem pair:
\begin{equation}\label{eq31}
\begin{array}{rclcrcl}
\mbox{maximize} & & \mathbf{c}^T \mathbf{x}  \mspace{100mu}
\mbox{and} & & \mbox{minimize} & & \mathbf{b}^T \mathbf{y} \\
\mbox{subject to} & & \mathbf{x} \geq \mathbf{0} & & \mbox{subject to}  & & \mathbf{y} \geq  \mathbf{0} \\
& & \mathbf{A} \mathbf{x} \leq  \mathbf{b} & &  & &  \mathbf{A}^T
\mathbf{y} \geq \mathbf{c} \koz.
\end{array}
\end{equation}
Construct the skew-symmetric matrix:
$$ 
\mathbf{P}= \left(
\begin{array}{ccc}
\mathbf{0} & \mathbf{A} & -\mathbf{b} \\
-\mathbf{A}^T & \mathbf{0} & \mathbf{c} \\
\mathbf{b}^T & -\mathbf{c}^T & 0
\end{array}\right)  \koz. 
$$

\begin{tetel}\label{th13} Assume $\mathbf{z} = \left(
\begin{array}{ccc}
\mathbf{u} \\
\mathbf{v} \\
\lambda
\end{array}\right)$ is an equilibrium strategy of the symmetric matrix
game $\mathbf{P}$ with $\lambda >0$. Then
$$ 
\mathbf{x} = \frac{1}{\lambda} \mathbf{v}\ \ \ \text{and}\ \ \
\mathbf{y}=\frac{1}{\lambda} \mathbf{u}
$$ 
are optimal solutions of the primal and dual problems, respectively.
\end{tetel}

\begin{biz}
If $\mathbf{z}$ is an equilibrium strategy, then $\mathbf{P}
\mathbf{z} \leq \mathbf{0}$, that is,
\begin{equation}\label{eq32}
\begin{array}{rcl}
\mathbf{A} \mathbf{v} - \lambda \mathbf{b} & \leq & \mathbf{0} \\
-\mathbf{A}^T \mathbf{u} + \lambda \mathbf{c} & \leq & \mathbf{0} \\
\mathbf{b}^T \mathbf{u} - \mathbf{c}^T \mathbf{v} & \leq & 0  \koz.
\end{array}
\end{equation}
\noindent Since $\mathbf{z} \geq \mathbf{0}$ and $\lambda > 0$, both
vectors $\mathbf{x} = (1/\lambda)\mathbf{v}$, and $\mathbf{y} =
(1/\lambda) \mathbf{u}$ are nonnegative, and by dividing the first
two relations of \eqref{eq32} by $\lambda$,
$$ \mathbf{A} \mathbf{x} \leq \mathbf{b}\ \ \ \text{and}\ \ \
\mathbf{A}^T \mathbf{y} \geq \mathbf{c}\koz,
$$
showing that $\mathbf{x}$ and $\mathbf{y}$ are feasible for the primal and
dual, respectively. From the last condition of \eqref{eq32} we have
$$\mathbf{b}^T \mathbf{y} \leq \mathbf{c}^T \mathbf{x} \koz.
$$
However
$$ \mathbf{b}^T \mathbf{y} \geq (\mathbf{x}^T
\mathbf{A}^T)\mathbf{y}= \mathbf{x}^T (\mathbf{A}^T \mathbf{y}) \geq
\mathbf{x}^T \mathbf{c} = \mathbf{c}^T \mathbf{x} \koz,
$$
consequently, $\mathbf{b}^T \mathbf{y} = \mathbf{c}^T \mathbf{x}$,
showing that the primal and dual objective functions are equal. The
duality theorem implies the optimality of $\mathbf{x}$ and
$\mathbf{y}$.
\end{biz}

\begin{pelda}\label{ex17}
Consider the linear programming problem:
\begin{eqnarray*}
\mbox{maximize} & &  x_1 + 2x_2  \\
\mbox{subject to} & & x_1  \geq  0 \\
& &  -x_1 + x_2  \geq  1 \\
& & 5x_1 + 7x_2  \leq  25 \koz.
\end{eqnarray*}
First we have to rewrite the problem as a primal problem.
Introduce the new variables:
$$ x_2^+ = \left\{
\begin{array}{ll}
x_2, & \mbox{if} \mspace{10mu} x_2 \geq 0 \koz, \\
0 & \mbox{otherwise} \koz,
\end{array}\right. 
$$
$$ x_2^- = \left\{
\begin{array}{cl}
-x_2, & \mbox{if} \mspace{10mu} x_2 < 0 \koz, \\
0 & \mbox{otherwise} \koz.
\end{array}\right. 
$$
and multiply the $\geq$-type constraint by $-1$. Then the problem becomes the following:
\begin{eqnarray*}
\mbox{maximize} & & x_1 + 2x_2^+ - 2x_2^- \\
\mbox{subject to} & & x_1,x_2^+,x_2^- \geq  0 \\
& & x_1 - x_2^+ + x_2^-  \leq -1 \\
& & 5x_1 + 7x_2^+ -7x_2^- \leq  25 \koz.
\end{eqnarray*}
Hence
$$ \mathbf{A} = \left(
\begin{array}{rrr}
1 & -1 & 1 \\
5 & 7 & -7 \\
\end{array}\right),\mspace{10mu} \mathbf{b}=\binom{-1}{25},\mspace{10mu}
\mathbf{c}^T=(1,2,-2) ,$$
and so matrix $\mathbf{P}$ becomes:
$$ \mathbf{P} = \left(
\begin{array}{rrcrrrcr}
0 & 0 & \vdots & 1 & -1 & 1 & \vdots & 1 \\
0 & 0 & \vdots & 5 & 7 & -7 & \vdots & -25 \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
-1 & -5 & \vdots & 0 & 0 & 0 & \vdots & 1 \\
1 & -7 & \vdots & 0 & 0 & 0 & \vdots & 2 \\
-1 & 7 & \vdots & 0 & 0 & 0 & \vdots & -2 \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
-1 & 25 & \vdots & -1 & -2 & 2 & \vdots & 0
\end{array}\right) \koz . $$
\end{pelda}

\subsection{The method of von Neumann}\nevindex{Neumann, John, von (1903--1957)}
The fictitious play method is an iteration algorithm in which at
each step the players adjust their strategies based on the
opponent's strategies. This method can therefore be considered as
the realization of a discrete system where the strategy selections
of the players are the state variables. For symmetric matrix games
John von Neumann introduced a continuous systems approach when the
players continuously adjust their strategies. This method can be
applied to general matrix games, since--as we have seen earlier--any
matrix game is equivalent to a symmetric matrix game. The method can
also be used to solve linear programming problems as we have seen
earlier that any primal-dual pair can be reduced to the solution of
a symmetric matrix game.

Let now $\mathbf{P}$ be a skew-symmetric $n \times n$ matrix. The
strategy of player $\mathcal{P}_2$, $\mathbf{y}(t)$ is considered as
the function of time $t \geq 0$. Before formulating the dynamism of
the system, introduce the following notation:
\begin{equation}\label{eq33}
\begin{array}{llclcrcl}
u_i: & \R^n &  \rightarrow & \R, & \mspace{40mu} & u_i(\mathbf{y}(t)) & = &
\mathbf{e}_i^T \mathbf{P} \mathbf{y}(t)  \mspace{20mu} \ (i=1,2,\ldots,n) \koz , \\
\phi : & \R & \rightarrow & \R, & & \phi(u_i) & = & \max \{ 0, u_i \}  \koz ,  \\
\Phi : & \R^n & \rightarrow & \R, & & \Phi (\mathbf{y}(t)) & = &
\sum_{i=1}^n \phi(u_i(\mathbf{y}(t))) \koz .
\end{array}
\end{equation}
For arbitrary probability vector $\mathbf{y}_0$ solve the
following nonlinear initial-value problem:
\begin{equation}\label{eq34}
y_j'(t) = \phi(u_j(\mathbf{y}(t))) - \Phi(\mathbf{y}(t))y_j(t), \mspace{20mu}
y_j(0)=y_{j0} \mspace{20mu} (1 \leq j \leq n) \koz .
\end{equation}
Since the right-hand side is continuous, there is at least
one solution. The right hand side of the equation can be interpreted
as follows. Assume that $\phi(u_j(\mathbf{y}(t))) > 0$. If player
$\mathcal{P}_2$ selects strategy $\mathbf{y}(t)$, then player
$\mathcal{P}_1$ is able to obtain a positive payoff by choosing the
pure strategy $\mathbf{e}_j$, which results in a negative payoff for
player $\mathcal{P}_2$. However if player $\mathcal{P}_2$ increases
$y_j(t)$ to one by choosing the same strategy $\mathbf{e}_j$ its
payoff $\mathbf{e}_j^T \mathbf{P} \mathbf{e}_j$ becomes zero, so it
increases. Hence it is the interest of player $\mathcal{P}_2$ to
increase $y_j(t)$. This is exactly what the first term represents.
The second term is needed to ensure that $\mathbf{y}(t)$ remains a
probability vector for all $t \geq 0$.

The computation of the right hand side of equations \eqref{eq34} for
all $t$ requires $n^2+n$ multiplications. The total computation cost
depends on the length of solution interval, on the selected step
size, and on the choice of the differential equation solver.

\begin{tetel}\label{th14}
Assume that $t_1,t_2,\ldots$ is a positive strictly increasing
sequence converging to $\infty$, then any cluster point of the
sequence $\{\mathbf{y}(t_k)\}$ is equilibrium strategy, furthermore
there is a constant $c$ such that
\begin{equation}\label{eq35}
\mathbf{e}_i^T \mathbf{P} \mathbf{y}(t_k) \leq
\frac{\sqrt{n}}{c+t_k} \mspace{20mu} (i=1,2,\ldots,n) \koz .
\end{equation}
\end{tetel}

\begin{biz}
First we have to show that $\mathbf{y}(t)$ is a probability vector
for all $t \geq 0$. Assume that with some $j$ and $t_1 > 0$,
$y_j(t_1) < 0$. Define
$$ t_0 = \sup \{ t | 0 < t < t_1, y_j(t) \geq 0 \} \koz . $$
\noindent Since $y_j(t)$ is continuous and $y_j(0) \geq 0$, clearly
$y_j(t_0)=0$, and for all $\tau \in (t_0,t_1)$, $y_j(\tau) < 0$.
Then for all $\tau \in (t_0,t_1]$,
$$ y'_j(\tau) = \phi(u_j(\mathbf{y}(\tau))) - \Phi(\mathbf{y}(\tau))y_j(\tau)
\geq 0 \koz,
$$
and the Lagrange mean-value theorem
 \nevindex{Lagrange, Joseph Louis (1736--1813)} implies that with some $\tau \in (t_0,t_1)$,
$$ y_j(t_1) = y_j(t_0) + y_j'(\tau)(t_1 - t_0) \geq 0 \koz , 
$$
which is a contradiction. Hence $y_j(t)$ is nonnegative.
Next we show that $\sum_{j=1}^n y_j(t) = 1$ for all $t$. Let $f(t) =
1 - \sum_{j=1}^n y_j(t)$, then
$$ f'(t) = -\sum_{j=1}^n y_j'(t) = -\sum_{j=1}^n
\phi(u_j(\mathbf{y}(t))) + \Phi(\mathbf{y}(t))(\sum_{j=1}^ny_j(t))
 = -\Phi(\mathbf{y}(t))(1- \sum_{j=1}^n y_j(t)) \koz , 
$$
so $f(t)$ satisfies the homogeneous equation
$$ f'(t) = -\Phi( \mathbf{y}(t)) f(t)
$$
with the initial condition $f(0) = 1 - \sum_{j=1}^n y_{j0}
= 0$. Hence for all $t \geq 0$, $f(t)=0$, showing that
$\mathbf{y}(t)$ is a probability vector.

Assume that for some $t$,   $\phi(u_i(\mathbf{y}(t))) > 0$. Then
\begin{equation}\label{eq36}
\begin{split}
\frac{d}{dt} \phi(u_i(\mathbf{y}(t)))= \sum_{j=1}^n p_{ij}y_j'(t)
= \sum_{j=1}^n p_{ij} [\phi (u_j(\mathbf{y}(t))) -
\Phi (\mathbf{y}(t))y_j(t)]  \\
= \sum_{j=1}^n p_{ij} \phi(u_j(\mathbf{y}(t))) - \Phi(\mathbf{y}(t))
\phi(u_i(\mathbf{y}(t))) \koz.
\end{split}
\end{equation}
\noindent By multiplying both sides by $\phi(u_i(\mathbf{y}(t)))$
and adding the resulted equations for $i=1,2,\ldots,n$ we have:
\begin{equation}\label{eq37}
\begin{split}
\sum_{i=1}^n \phi(u_i(\mathbf{y}(t))) \frac{d}{dt}
\phi(u_i(\mathbf{y}(t))) = \sum_{i=1}^n \sum_{j=1}^n p_{ij}
\phi(u_i(\mathbf{y}(t))) \phi(u_j(\mathbf{y}(t))) \\
-\Phi(\mathbf{y}(t))(\sum_{i=1}^n \phi^2 (u_i(\mathbf{y}(t)))) \koz.
\end{split}
\end{equation}
\noindent The first term is zero, since $\mathbf{P}$ is
skew-symmetric. Notice that this equation remains valid even as
$\phi(u_i(\mathbf{y}(t)))=0$ except the break-points (where the
derivative of $\phi(u_i(\mathbf{y}(t)))$ does not exist) since
\eqref{eq36} remains true.

Assume next that with a positive $t$, $\Phi (\mathbf{y}(t)) = 0$.
Then for all $i$, $\phi (u_i (\mathbf{y}(t))) =0$. Since equation
\eqref{eq37} can be rewritten as
\begin{equation}\label{eq38}
\frac{1}{2} \frac{d}{dt} \Psi(\mathbf{y}(t)) = -
\Phi(\mathbf{y}(t))\Psi(\mathbf{y}(t))
\end{equation}
\noindent with
$$\Psi : \R^n \rightarrow \R \mspace{20mu} \mbox{and} \mspace{20mu}
\Psi(\mathbf{y}(t))= \sum_{i=1}^n \phi^2 (u_i (\mathbf{y}(t))) \koz
,$$ \noindent we see that $\Psi(\mathbf{y}(t))$ satisfies a
homogeneous equation with zero initial solution at $t$, so the
solution remains zero for all $\tau \geq t$. Therefore
$\phi(u_i(\mathbf{y}(\tau)))=0$ showing that $\mathbf{P}
\mathbf{y}(\tau) \leq \mathbf{0}$, that is, $\mathbf{y}(\tau)$ is
equilibrium strategy.

If $\Phi(\mathbf{\mathbf{y}(t)}) > 0$ for all $t \geq 0 $, then
$\Psi (\mathbf{y}(t)) > 0$, and clearly
$$ \frac{1}{2}\frac{d}{dt}\Psi(\mathbf{y}(t)) \leq -
\sqrt{\Psi(\mathbf{y}(t))}\Psi (\mathbf{y}(t)) \koz , $$
\noindent
that is
$$ \frac{1}{2}\frac{d}{dt}\Psi(\mathbf{y}(t)) (\Psi
(\mathbf{y}(t)))^{-\frac{3}{2}} \leq -1 \koz . $$
\noindent
Integrate both sides in interval $[0,t]$ to have
$$ - \Psi(\mathbf{y}(t))^{-(1/2)} + c \leq -t \koz ,$$
\noindent with $c = (\Psi(\mathbf{y}(0)))^{-(1/2)}$, which implies
that
\begin{equation}\label{eq39}
(\Psi(\mathbf{y}(t)))^{1/2} \leq \frac{1}{c+t} \koz .
\end{equation}
By using the Cauchy--Schwartz inequality
\nevindex{Cauchy, Augustin-Louis (1789--1857)}\nevindex{Schwartz, Jacob Theodore}
we get
\begin{equation}\label{eq40}
\mathbf{e}_i^T \mathbf{P} \mathbf{y}(t) = u_i (\mathbf{y}(t)) \leq
\phi(u_i(\mathbf{y}(t))) \leq \Phi(\mathbf{y}(t)) \leq \sqrt{n
\Psi(\mathbf{y}(t))} \leq \frac{\sqrt{n}}{c+t} \koz ,
\end{equation}
\noindent which is valid even at the break points because of the
continuity of functions $u_i$. And finally, take a sequence $\{
\mathbf{y}(t_k) \}$ with $t_k$ increasingly converging to $\infty$.
The sequence is bounded (being probability vectors), so there is at
least one cluster point $\mathbf{y}^\star$. From \eqref{eq40}, by
letting $t_k\rightarrow \infty$ we have that $\mathbf{P}
\mathbf{y}^\star \leq \mathbf{0}$ showing that $\mathbf{y}^\star$ is
an equilibrium strategy.
\end{biz}

\begin{pelda}\label{ex18}
Consider the matrix game with matrix
$$ \mathbf{A} = \left(
\begin{array}{ccc}
2 & 1 & 0 \\
2 & 0 & 3 \\
-1 & 3 & 3
\end{array}\right) \koz ,$$
which was the subject of our earlier Example \ref{ex13} In order to
apply the method of von Neumann we have to find first an equivalent
symmetric matrix game. The application of the method given in
Theorem \ref{th12}. requires that the matrix has to be positive.
Without changing the equilibria we can add 2 to all matrix elements
to have
$$ \mathbf{A}_{new} = \left(
\begin{array}{ccc}
4 & 3 & 2 \\
4 & 2 & 5 \\
1 & 5 & 5
\end{array}\right) \koz ,$$
\noindent and by using the method we get the skew-symmetric matrix
$$ \mathbf{P} = \left(
\begin{array}{rrrcrrrcr}
0 & 0 & 0 & \vdots & 4 & 3 & 2 & \vdots & -1 \\
0 & 0 & 0 & \vdots & 4 & 2 & 5 & \vdots & -1 \\
0 & 0 & 0 & \vdots & 1 & 5 & 5 & \vdots & -1 \\
\cdots & \cdots  & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
-4 & -4 & -1 & \vdots & 0 & 0 & 0 & \vdots & 1 \\
-3 & -2 & -5 & \vdots & 0 & 0 & 0 & \vdots & 1 \\
-2 & -5 & -5 & \vdots & 0 & 0 & 0 & \vdots & 1 \\
\cdots & \cdots  & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
1 & 1 & 1 & \vdots & -1 & -1 & -1 & \vdots & 0
\end{array}\right) \koz .$$
\noindent The differential equations \eqref{eq34} were solved by
using the $4$th order Runge--Kutta
method\nevindex{Runge, Carl David Tolmé (1856--1927)}\nevindex{Kutta, Wilhelm Martin (1867--1944)} 
in the interval $[0,100]$ with the step size $h=0.01$ and initial vector
$\mathbf{y}(0) = (1,0,\ldots,0)^T$. From $\mathbf{y}(100)$ we get
the approximations
$$ \mathbf{x} \approx (0.563619,0.232359,0.241988)  \koz, 
$$
$$ \mathbf{y} \approx (0.485258,0.361633,0.115144)
$$
of the equilibrium strategies of the original game.
Comparing these values to the exact values:
$$\mathbf{x} = \left ( \frac{4}{7},\frac{4}{21},\frac{5}{21} \right ) \mspace{20mu} \mbox{and}
\mspace{20mu}  \mathbf{y} = \left
(\frac{3}{7},\frac{3}{7},\frac{1}{7} \right )
$$
we see that the maximum error is about $0.067$.
\end{pelda}


\subsection{Diagonally strictly concave games}\label{2.9}
Consider an $N$-person continuous game and assume that all
conditions presented at the beginning of Subsection \ref{2.3} are
satisfied. In addition, assume that for all $k$, $S_k$ is bounded,
all components of $g_k$ are concave and $f_k$ is concave in $s_k$
with any fixed $s_1,\ldots,s_{k-1},s_{k+1},\ldots,s_N$. Under these
conditions there is at least one equilibrium (Theorem \ref{th3}).
The uniqueness of the equilibrium is not true in general, even if
all $f_k$ are strictly concave in $s_k$. Such an example is shown
next.

\begin{pelda}\label{ex19}
Consider a two-person game with $S_1 = S_2 = [0,1]$ and
$f_1(s_1,s_2) = f_2(s_1,s_2) = 1 - (s_1 - s_2)^2$. Clearly both
payoff functions are strictly concave and there are infinitely many
equilibria:  $s_1^\star = s_2^\star \in [0,1]$.
\end{pelda}

Select an arbitrary nonnegative vector $\mathbf{r} \in \R^N$ and
define function
\begin{equation}\label{eq41}
\mathbf{h}: \R^M \rightarrow \R^M, \mspace{20mu}
\mathbf{h}(\mathbf{s},\mathbf{r}) = \left(
\begin{array}{cccc}
r_1 \nabla_1 f_1 (\mathbf{s})^T \\
r_2 \nabla_2 f_2 (\mathbf{s})^T \\
\vdots \\
r_N \nabla_N f_N (\mathbf{s})^T
\end{array}\right) \koz ,
\end{equation}
\noindent where $M = \sum_{k=1}^N n_k$, and $\nabla_k f_k$ is the
gradient (as a row vector) of $f_k$ with respect to $s_k$. The game
is said to be \ki{diagonally strictly concave}\inddef{diagonally
strictly concave games} if for all $\mathbf{s}^{(1)} \neq
\mathbf{s}^{(2)}$, $\mathbf{s}^{(1)},\mathbf{s}^{(2)} \in S$ and for
some $\mathbf{r} \geq \mathbf{0}$,
\begin{equation}\label{eq42}
(\mathbf{s}^{(1)} - \mathbf{s}^{(2)})^T
(\mathbf{h}(\mathbf{s}^{(1)},\mathbf{r}) -
\mathbf{h}(\mathbf{s}^{(2)},\mathbf{r})) < 0  .
\end{equation}

\begin{tetel}\label{th15}
Under the above conditions the game has exactly one equilibrium.
\end{tetel}

\begin{biz}
The existence of the equilibrium follows from Theorem \ref{th3}. In
proving uniqueness assume that $\mathbf{s}^{(1)}$ and
$\mathbf{s}^{(2)}$ are both equilibria, and both satisfy relations
\eqref{eq9}. Therefore for $l=1,2$,
\begin{eqnarray*}
{\mathbf{u}_k^{(l)}}^T \mathbf{g}_k (s_k^{(l)}) & = & 0 \\
\nabla_k f_k (\mathbf{s}^{(l)}) + \mathbf{u}_k^{(l)^T} \nabla_k
\mathbf{g}_k(s_k^{(l)}) & = &\mathbf{0}^T ,
\end{eqnarray*}
\noindent and the second equation can be rewritten as
\begin{equation}\label{eq43}
\nabla_k f_k (\mathbf{s}^{(l)}) + \sum_{j=1}^{m_k}  u_{kj}^{(l)}
\nabla_k g_{kj}(s_k^{(l)})= 0 \koz ,
\end{equation}
\noindent where $u_{kj}^{(l)}$ and $g_{kj}$ are the $j$th components
of $\mathbf{u}_{k}^{(l)}$ and $g_{k}$, respectively. Multiplying
\eqref{eq43} by $(r_k(s_k^{(2)} - s_k^{(1)})^T)$ for $l=1$ and by
$r_k(s_k^{(1)} - s_k^{(2)})^T$ for $l=2$ and adding the resulted
equalities for $k=1,2,\ldots,N$ we have
\begin{equation}\label{eq44}
\begin{split}
0= \{(\mathbf{s}^{(2)} - \mathbf{s}^{(1)})^T
\mathbf{h}(\mathbf{s}^{(1)},\mathbf{r}) + (\mathbf{s}^{(1)} -
\mathbf{s}^{(2)})^T
\mathbf{h}(\mathbf{s}^{(2)},\mathbf{r}) \} \\
+ \sum_{k=1}^N
\sum_{j=1}^{m_k} r_k [u_{kj}^{(1)}(s_k^{(2)} - s_k^{(1)})^T
\nabla_k g_{kj} (s_k^{(1)}) + u_{kj}^{(2)}(s_k^{(1)} -
s_k^{(2)})^T \nabla_k g_{kj} (s_k^{(2)}) ] \koz .
\end{split}
\end{equation}
\noindent Notice that the sum of the first two terms is positive by
the diagonally strict concavity of the game, the concavity of the
components of $g_k$ implies that
$$ (s_k^{(2)} - s_k^{(1)})^T \nabla_k g_{kj} (s_k^{(1)}) \geq
g_{kj}(s_k^{(2)}) - g_{kj}(s_k^{(1)})$$
\noindent and
$$ (s_k^{(1)} - s_k^{(2)})^T \nabla_k g_{kj} (s_k^{(2)}) \geq
g_{kj}(s_k^{(1)}) - g_{kj}(s_k^{(2)}) \koz.$$
\noindent Therefore
from \eqref{eq44} we have
\begin{equation*}
\begin{split}
0 > \sum_{k=1}^N  \sum_{j=1}^{m_k} r_k
[u_{kj}^{(1)}(g_{kj}(s_k^{(2)}) - g_{kj}(s_k^{(1)})) +
u_{kj}^{(2)}(g_{kj}(s_k^{(1)}) - g_{kj}(s_k^{(2)})) ] \\
= \sum_{k=1}^N  \sum_{j=1}^{m_k} r_k
[u_{kj}^{(1)}g_{kj}(s_k^{(2)}) + u_{kj}^{(2)}g_{kj}(s_k^{(1)}) ]
\geq 0 \koz ,
\end{split}
\end{equation*}
\noindent where we used the fact that for all $k$ and $l$,
$$ 0 = {\mathbf{u}_k^{(l)}}^T \mathbf{g}_k(s_k^{(l)}) = \sum_{j=1}^{m_k} u_{kj}^{(l)}
g_{kj}(s_k^{(l)}) \koz.$$
\noindent This is an obvious contradiction,
which completes the proof.
\end{biz}

\subsubsection{Checking for uniqueness of equilibrium.}
In practical cases the following result is very useful in checking
diagonally strict concavity of $N$-person games.

\begin{tetel}\label{th16}
Assume $S$ is convex, $f_k$ is twice continuously differentiable for
all $k$, and $\mathbf{J}(\mathbf{s},\mathbf{r}) +
\mathbf{J}(\mathbf{s},\mathbf{r})^T$ is negative definite with some
$\mathbf{r} \geq \mathbf{0}$, where
$\mathbf{J}(\mathbf{s},\mathbf{r})$ is the Jacobian of
$\mathbf{h}(\mathbf{s},\mathbf{r})$. Then the game is diagonally
strictly concave.
\end{tetel}

\begin{biz}
Let $\mathbf{s}^{(1)} \neq \mathbf{s}^{(2)}$,
$\mathbf{s}^{(1)},\mathbf{s}^{(2)} \in S$. Then for all $\alpha \in
[0,1]$, $\mathbf{s}(\alpha) = \alpha \mathbf{s}^{(1)} + (1 - \alpha)
\mathbf{s}^{(2)} \in S$ and
$$ \frac{d}{d \alpha} \mathbf{h}(\mathbf{s}(\alpha),\mathbf{r}) =
\mathbf{J}(\mathbf{s}(\alpha),\mathbf{r})(\mathbf{s}^{(1)} -
\mathbf{s}^{(2)}) \koz .$$
\noindent Integrate both side in $[0,1]$
to have
$$ \mathbf{h}(\mathbf{s}^{(1)},\mathbf{r}) -
\mathbf{h}(\mathbf{s}^{(2)},\mathbf{r}) = \int_0^1
\mathbf{J}(\mathbf{s}(\alpha),\mathbf{r})(\mathbf{s}^{(1)} -
\mathbf{s}^{(2)})d\alpha \koz ,$$ \noindent and by premultiplying
both sides by $(\mathbf{s}^{(1)} - \mathbf{s}^{(2)})^T$ we see that
\begin{equation*}
\begin{split}
(\mathbf{s}^{(1)} - \mathbf{s}^{(2)})^T (\mathbf{h}(\mathbf{s}^{(1)},\mathbf{r}) -
\mathbf{h}(\mathbf{s}^{(2)},\mathbf{r})) = \int_0^1
(\mathbf{s}^{(1)} - \mathbf{s}^{(2)})^T
\mathbf{J}(\mathbf{s}(\alpha),\mathbf{r})(\mathbf{s}^{(1)} -
\mathbf{s}^{(2)})d\alpha   \\
= \frac{1}{2}\int_0^1 (\mathbf{s}^{(1)} -
\mathbf{s}^{(2)})^T
(\mathbf{J}(\mathbf{s}(\alpha),\mathbf{r}) + \mathbf{J}(\mathbf{s}(\alpha),
\mathbf{r})^T)(\mathbf{s}^{(1)}-\mathbf{s}^{(2)})d\alpha < 0 \koz ,
\end{split}
\end{equation*}
\noindent completing the proof.
\end{biz}

\begin{pelda}\label{ex20}
Consider a simple two-person game with strategy sets $S_1 = S_2 =
[0,1]$, and payoff functions
$$ f_1 (s_1,s_2) = -s_1^2 + s_1 - s_1s_2$$
\noindent and
$$ f_2(s_1,s_2) = -s_2^2 + s_2 -s_1s_2 \koz .$$
\noindent Clearly all conditions, except diagonally strict
concavity, are satisfied. We will use Theorem \ref{th16} to show
this additional property. In this case
$$ \nabla_1 f_1(s_1,s_2) = -2s_1 + 1 -s_2, \mspace{20mu} \nabla_2f_2(s_1,s_2)
= -2s_2 + 1 - s_1 \koz , $$
\noindent so
$$ \mathbf{h}(\mathbf{s},\mathbf{r}) = \binom{r_1(-2s_1 + 1 - s_2)}{r_2(-2s_2 + 1 -s_1} $$
\noindent with Jacobian
$$ \mathbf{J}(\mathbf{s},\mathbf{r}) = \left(
\begin{array}{rr}
-2r_1 & -r_1 \\
-r_2 & -2r_2
\end{array}\right) .$$
\noindent We will show that
$$ \mathbf{J}(\mathbf{s},\mathbf{r}) +  \mathbf{J}(\mathbf{s},\mathbf{r})^T = \left(
\begin{array}{cc}
-4r_1 & -r_1-r_2 \\
-r_1-r_2 & -4r_2
\end{array}\right)$$
\noindent is negative definite with some $\mathbf{r} \geq
\mathbf{0}$. For example, select $r_1 = r_2 = 1$, then this matrix
becomes
$$\left(
\begin{array}{rr}
-4 & -2 \\
-2 & -4
\end{array}\right) $$
\noindent with characteristic polynomial
$$\phi(\lambda) = \textup{det}
\left(
\begin{array}{rr}
-4 - \lambda & -2 \\
-2 & -4 - \lambda
\end{array}\right)= \lambda^2 + 8\lambda + 12 \koz ,$$
\noindent having negative eigenvalues $\lambda_1 = -2$, $\lambda_2 =
-6$.
\end{pelda}

\subsubsection{Iterative computation of equilibrium.}\label{2.9.2}

We have see earlier in Theorem \ref{th4} that $\mathbf{s}^\star \in
S$ is an equilibrium if and only if
\begin{equation}\label{eq45}
\mathbf{H}_\mathbf{r}(\mathbf{s}^\star,\mathbf{s}^\star) \geq
\mathbf{H}_\mathbf{r}(\mathbf{s}^\star,\mathbf{s})
\end{equation}
\noindent for all $\mathbf{s} \in S$, where $\mathbf{H}_\mathbf{r}$
is the aggregation function \eqref{eq4}. In the following analysis
we assume that the $N$-person game satisfies all conditions
presented at the beginning of Subsection \ref{2.9} and \eqref{eq42}
holds with some positive $\mathbf{r}$.

We first show the equivalence of \eqref{eq45} and a variational
inequality.

\begin{tetel}\label{th17}
A vector $\mathbf{s}^\star \in S$ satisfies \eqref{eq45} if and only
if
\begin{equation}\label{eq46}
\mathbf{h}(\mathbf{s}^\star,\mathbf{r})^T(\mathbf{s} -
\mathbf{s}^\star) \leq 0
\end{equation}
\noindent for all $\mathbf{s} \in S$, where
$\mathbf{h}(\mathbf{s},\mathbf{r})$ is defined in \eqref{eq41}.
\end{tetel}

\begin{biz}
Assume $\mathbf{s}^\star$ satisfies \eqref{eq45}. Then
$\mathbf{H}_\mathbf{r}(\mathbf{s}^\star,\mathbf{s})$ as function of
$\mathbf{s}$ obtains maximum at $\mathbf{s} = \mathbf{s}^\star$,
therefore
$$\nabla_\mathbf{s}\mathbf{H}_\mathbf{r}(\mathbf{s}^\star,\mathbf{s}^\star)(\mathbf{s}
- \mathbf{s}^\star) \leq 0$$ \noindent for all $\mathbf{s} \in S$,
and since
$\nabla_\mathbf{s}\mathbf{H}_\mathbf{r}(\mathbf{s}^\star,\mathbf{s}^\star)$
is $\mathbf{h}(\mathbf{s}^\star,\mathbf{r})$, we proved that
$\mathbf{s}^\star$ satisfies \eqref{eq46}.

Assume next that $\mathbf{s}^\star$ satisfies \eqref{eq46}. By the
concavity of $\mathbf{H}_\mathbf{r}(\mathbf{s}^\star,\mathbf{s})$ in
$\mathbf{s}$ and the diagonally strict concavity of the game we have
$$ \mathbf{H}_\mathbf{r}(\mathbf{s}^\star,\mathbf{s}^\star) -
\mathbf{H}_\mathbf{r}(\mathbf{s}^\star,\mathbf{s})\geq
\mathbf{h}(\mathbf{s},\mathbf{r})^T(\mathbf{s}^\star - \mathbf{s})
\geq \mathbf{h}(\mathbf{s},\mathbf{r})^T(\mathbf{s}^\star -
\mathbf{s}) + \mathbf{h}(\mathbf{s}^\star,\mathbf{r})^T(\mathbf{s} -
\mathbf{s}^\star) > 0 \koz ,$$
\noindent so $\mathbf{s}^\star$
satisfies \eqref{eq45}.
\end{biz}

Hence any method available for solving variational inequalities can
be used to find equilibria.

Next we construct a special two-person, game the equilibrium problem
of which is equivalent to the equilibrium problem of the original
$N$-person game.

\begin{tetel}\label{th18}
Vector $\mathbf{s}^\star \in S$ satisfies \eqref{eq45} if and only
if $(\mathbf{s}^\star,\mathbf{s}^\star)$ is an equilibrium of the
two-person game $D=\{2;S,S;f,-f\}$ where $f(\mathbf{s},\mathbf{z}) =
\mathbf{h}(\mathbf{z},\mathbf{r})^T(\mathbf{s} - \mathbf{z}).$
\end{tetel}

\begin{biz}
\begin{itemize}
    \item Assume first that $\mathbf{s}^\star \in S$ satisfies \eqref{eq45}.
Then it satisfies \eqref{eq46} as well, so
$$ f(\mathbf{s},\mathbf{s}^\star) \leq 0 =
f(\mathbf{s}^\star,\mathbf{s}^\star).$$ \noindent We need in
addition to show that
$$ -f(\mathbf{s}^\star,\mathbf{s}) \leq 0 = -
f(\mathbf{s}^\star,\mathbf{s}^\star).$$ In contrary assume that with
some $\mathbf{s}$, $f(\mathbf{s}^\star,\mathbf{s}) < 0$. Then
\begin{eqnarray*}
0 > f(\mathbf{s}^\star,\mathbf{s}) & = &
\mathbf{h}(\mathbf{s},\mathbf{r})^T(\mathbf{s}^\star - \mathbf{s})
> \mathbf{h}(\mathbf{s},\mathbf{r})^T(\mathbf{s}^\star -
\mathbf{s})+ (\mathbf{s} - \mathbf{s}^\star)^T
(\mathbf{h}(\mathbf{s},\mathbf{r}) -
\mathbf{h}(\mathbf{s}^\star,\mathbf{r}))  \\
& =&  \mathbf{h}(\mathbf{s}^\star,\mathbf{r})^T(\mathbf{s}^\star -
\mathbf{s}) \geq 0,
\end{eqnarray*}
\noindent where we used \eqref{eq42} and \eqref{eq46}. This is a
clear contradiction.
    \item Assume next that $(\mathbf{s}^\star,\mathbf{s}^\star)$ is an
equilibrium of game $D$. Then for any $\mathbf{s},\mathbf{z} \in S$,
$$ f(\mathbf{s},\mathbf{s}^\star) \leq
f(\mathbf{s}^\star,\mathbf{s}^\star)=0 \leq
f(\mathbf{s}^\star,\mathbf{z})  .$$ \noindent The first part can be
rewritten as
$$ \mathbf{h}(\mathbf{s}^\star,\mathbf{r})^T(\mathbf{s} -
\mathbf{s}^\star) \leq 0  ,$$
\noindent showing that \eqref{eq46} is
satisfied, so is \eqref{eq45}.
\end{itemize}
\end{biz}

Consider the following iteration procedure.

Let $\mathbf{s}^{(1)} \in S$ be arbitrary, and solve problem
\begin{equation}\label{eq47}
\begin{array}{rcl}
\mbox{maximize} & & f(\mathbf{s},\mathbf{s}^{(1)}) \\
\mbox{subject to} & & \mathbf{s} \in S  \koz.
\end{array}
\end{equation}
Let $\mathbf{s}^{(2)}$ denote an optimal solution and
define $\mu_1 = f(\mathbf{s}^{(2)},\mathbf{s}^{(1)})$. If $\mu_1 =
0$, then for all $\mathbf{s} \in S$,
$$ f(\mathbf{s},\mathbf{s}^{(1)}) =
\mathbf{h}(\mathbf{s}^{(1)},\mathbf{r})^T(\mathbf{s} -
\mathbf{s}^{(1)}) \leq 0 \koz,
$$ 
so by Theorem \ref{th17}, $\mathbf{s}^{(1)}$ is an equilibrium. Since
$f(\mathbf{s}^{(1)},\mathbf{s}^{(1)}) = 0$, we assume that $\mu_1 >
0$. In the general step $k \geq 2$ we have already $k$ vectors
$\mathbf{s}^{(1)},\mathbf{s}^{(2)},\ldots,\mathbf{s}^{(k)}$, and
$k-1$ scalers $\mu_1,\mu_2,\ldots,\mu_{k-1} > 0$. Then the next
vector $\mathbf{s}^{(k+1)}$ and next scaler $\mu_k$ are the
solutions of the following problem:
\begin{equation}\label{eq48}
\begin{array}{rcl}
\mbox{maximize} & & \mu  \\
\mbox{subject to} & & f(\mathbf{s},\mathbf{s}^{(i)})  \geq  \mu
\mspace{30mu}
(i=1,2,\ldots,k) \\
& & \mathbf{s} \in  S  .
\end{array}
\end{equation}
\noindent Notice that
$$ f(\mathbf{s}^{(k)},\mathbf{s}^{(i)}) \geq \mu_{k-1} \geq 0 \mspace{30mu}
(i=1,2,\ldots,k-1)$$
\noindent and
$$ f(\mathbf{s}^{(k)},\mathbf{s}^{(k)}) = 0\koz ,
$$
\noindent so we know that $\mu_k \geq 0  .$

The formal algorithm is as follows:

\begin{alg}{Continuous-Equilibrium}\inddef{\textsc{Continuous-Equilibrium}}
1 \'  $k \leftarrow 1$ \\
2 \' solve problem (\ref{eq47}), let $\mathbf{s}^{(2)}$ be optimal
solution \\
3 \' \key{if} $ f(\mathbf{s}^{(2)},\mathbf{s}^{(1)}) = 0$ \\
4 \' \> \key{then} \= $\mathbf{s}^{(1)}$ is equilibrium  \\
5 \' \>            \> \key{return} $\mathbf{s}^{(1)}$ \\
6 \' $k \leftarrow k+1$ \\
7 \' solve problem (\ref{eq48}), let $\mathbf{s}^{(k+1)}$ be optimal
solution \\
8 \' \key{if} $||\mathbf{s}^{(k+1)}-\mathbf{s}^{(k)}||<\varepsilon$ \\
9 \' \> \key{then} \= $\mathbf{s}^{(k+1)}$ is equilibrium\\
10 \'\>            \> \key{return} $\mathbf{s}^{(k+1)}$ \\
11 \' \> \key{else} \> go to 5
\end{alg}

Before stating the convergence theorem of the algorithm we notice
that in the special case when the strategy sets are defined by
linear inequalities (that is, all functions $g_k$ are linear) then
all constraints of problem \eqref{eq48} are linear, so at each
iteration step we have to solve a linear programming problem.

In this linear case the simplex method has to be used in each
iteration step with exponential computational cost, so the overall
cost is also exponential (with prefixed number of steps).

\begin{tetel}\label{th19}
There is a subsequence $\{ \mathbf{s}^{(k_i)} \}$ of $\{
\mathbf{s}^{(k)} \}$ generated by the method that converges to the
unique equilibrium of the $N$-person game.
\end{tetel}

\begin{biz}
The proof consists of several steps.

First we show that $\mu_k \rightarrow 0$ as $k\rightarrow\infty$.
Since at each new iteration an additional constraint is added to
\eqref{eq48}, sequence $\{ \mu_k \}$ is nonincreasing. Since it is
also nonnegative, it must be convergent. Sequence $\{
\mathbf{s}^{(k)}\}$ is bounded, since it is from the bounded set
$S$, so it has a convergent subsequence $\{ \mathbf{s}^{(k_i)} \}$.
Notice that from \eqref{eq48} we have
$$ 0 \leq \mu_{k_i - 1} = \min_{1 \leq k \leq k_i - 1}
\mathbf{h}(\mathbf{s}^{(k)},\mathbf{r})^T (\mathbf{s}^{(k_i)} -
\mathbf{s}^{(k)}) \leq
\mathbf{h}(\mathbf{s}^{(k_{i-1})},\mathbf{r})^T (\mathbf{s}^{(k_i)}
- \mathbf{s}^{(k_{i-1})}) \koz ,$$ \noindent where the right hand
side tends to zero. Thus $\mu_{k_i - 1} \rightarrow 0$ and since the
entire sequence $\{ \mu_k \}$ is monotonic, the entire sequence
converges to zero.

Let next $\mathbf{s}^\star$ be an equilibrium of the $N$-person
game, and define
\begin{equation}\label{eq49}
\delta(t) = \min \{ (\mathbf{h}(\mathbf{s},\mathbf{r}) -
\mathbf{h}(\mathbf{z},\mathbf{r}))^T (\mathbf{z} - \mathbf{s}) | \|
\mathbf{s} - \mathbf{z} \| \geq t,\ \mathbf{z},\mathbf{s} \in S \} \koz.
\end{equation}
By \eqref{eq42}, $\delta(t) >0$ for all $t > 0$. Define the indices $k_i$ so that
$$ \delta (\| \mathbf{s}^{(k_i)} - \mathbf{s}^\star  \| ) = \min_{1 \leq k
\leq i} \delta (\| \mathbf{s}^{(k)} - \mathbf{s}^\star  \| )\ \ \
(i=1,2,\ldots)  \koz,
$$
then for all $k=1,2,\ldots,i$,
\begin{eqnarray*}
\delta (\| \mathbf{s}^{(k_i)} - \mathbf{s}^\star  \| ) & \leq & (\mathbf{h}(\mathbf{s}^{(k)},\mathbf{r}) -
\mathbf{h}(\mathbf{s}^\star,\mathbf{r}))^T (\mathbf{s}^\star -
\mathbf{s}^{(k)}) \\
& = & \mathbf{h}(\mathbf{s}^{(k)},\mathbf{r})^T (\mathbf{s}^\star -
\mathbf{s}^{(k)}) - \mathbf{h}(\mathbf{s}^\star,\mathbf{r})^T (\mathbf{s}^\star - \mathbf{s}^{(k)}) \\
& \leq & \mathbf{h}(\mathbf{s}^{(k)},\mathbf{r})^T (\mathbf{s}^\star
- \mathbf{s}^{(k)})  \koz,
\end{eqnarray*}
which implies that
\begin{eqnarray*}
\delta (\| \mathbf{s}^{(k_i)} - \mathbf{s}^\star  \| )
& \leq & \min_{1 \leq k \leq i} \mathbf{h}(\mathbf{s}^{(k)},\mathbf{r})^T (\mathbf{s}^\star - \mathbf{s}^{(k)}) \\
& \leq & \max_{\mathbf{s} \in S} \min_{1 \leq k \leq i}
\mathbf{h}(\mathbf{s}^{(k)},\mathbf{r})^T(\mathbf{s} - \mathbf{s}^{(k)}) \\
& = & \min_{1 \leq k \leq i}
\mathbf{h}(\mathbf{s}^{(k)},\mathbf{r})^T (\mathbf{s}^{(i+1)} -
\mathbf{s}^{(k)}) \\
& = & \mu_i
\end{eqnarray*}
where we used again problem \eqref{eq48}. From this
relation we conclude that $\delta (\| \mathbf{s}^{(k_i)} -
\mathbf{s}^\star \|) \rightarrow 0$ as $i \rightarrow \infty$. And
finally, notice that function $\delta(t)$ satisfies the following
properties:
\begin{enumerate}
\item $\delta (t)$ is continuous in $t$;
\item $\delta (t) > 0$ if $t > 0$ (as it was shown just below
relation \eqref{eq49});
\item if for a convergent sequence  $\{ t^{(k)} \}$, $\delta
(t^{(k)}) \rightarrow 0$, then necessarily $t^{(k)} \rightarrow 0$.
\end{enumerate}
\noindent By applying property $3.$ with sequence $\{ \|
\mathbf{s}^{(k_i)} - \mathbf{s}^\star  \|  \}$ it is clear that  $
\| \mathbf{s}^{(k_i)} - \mathbf{s}^\star  \|  \rightarrow 0$ so
$\mathbf{s}^{(k_i)} \rightarrow \mathbf{s}^\star $. Thus the proof
is complete.
\end{biz}

\begin{gyak}
\ujgyak \label{ec1.1} Consider a 2-person game with strategy sets
$S_1=S_2=[0,1]$, and payoff functions $f_1(x_1,x_2)=x_1^2 + x_1x_2 +
2$ and $f_2(x_1,x_2)=x_1+x_2$. Show the existence of a unique
equilibrium point by computing it. Show that Theorem \ref{th3}.
cannot be applied to prove existence.
\ujgyak \label{ec1.2} Consider
the ``price war" game in which two firms are price setting. Assume
that $p_1$ and  $p_2$ are the strategies of the players, $p_1,p_2
\in [0,p_{max}]$ and the payoff functions are:
\[ f_1(p_1,p_2) = \left\{
\begin{array}{ll}
p_1, & \mbox{if}\mspace{10mu} p_1 \leq p_2  \koz, \\
p_1-c, & \mbox{if}\mspace{10mu} p_1 > p_2 \koz,
\end{array}\right. \]
\[ f_2(p_1,p_2) = \left\{
\begin{array}{ll}
p_2, & \mbox{if}\mspace{10mu} p_2 \leq p_1  \koz,  \\
p_2 - c, & \mbox{if}\mspace{10mu} p_2 > p_1  \koz,
\end{array}\right. \]
\noindent by assuming that $c < p_{max}$. Is there an equilibrium?
How many equilibria were found?
\ujgyak \label{ec1.3} A portion of the sea is modeled by the unit
square in which a submarine is hiding. The strategy of the submarine
is the hiding place $\mathbf{x} \in [0,1] \times [0,1]$. An airplane
drops a bomb in a location $\mathbf{y} = [0,1] \times [0,1]$,j which
is its strategy. The payoff of the airplane is the damage $\alpha e
^{- \beta \|\mathbf{x}-\mathbf{y}\|}$ occurred by the bomb, and the
payoff of the submarine is its negative. Does this 2-person game
have an equilibrium?
\ujgyak \label{ec1.4} In the second-price auction they sell one unit
of an item to $N$ bidders. They value the item as $v_1 < v_2 <
\cdots < v_N$. Each of them offers a price for the item
simultaneously without knowing the offers of the others. The bidder
with the highest offer will get the item, but he has to pay only the
second highest price. So the strategy of bidder $k$ is $[0,
\infty]$, so $x_k \in [0,\infty]$, and the payoff function for this
bidder is:
\begin{equation*}
f_k(x_1,x_2,\ldots,x_N)= \left\{
\begin{array}{ll}
v_k - \max_{j \neq k} {x_j}, & \mbox{if}\mspace{10mu} x_k = \max_j {x_j}\koz , \\
0 & \mbox{otherwise} \koz.
\end{array}\right.
\end{equation*}
What is the best response function of bidder $k$? Does
this game have equilibrium? \ujgyak Formulate Fan's inequality for
Exercise \nevindex{Fan, Ky} \ref{ec1.1}
\ujgyak Formulate and solve Fan's inequality\gyakindex{fan's inequality} for Exercise \ref{ec1.2}. 
\ujgyak Formulate and solve Fan's inequality for Exercise \ref{ec1.4}.
\ujgyak \label{ec2.4} Consider a 2-person game with strategy sets
$S_1=S_2=[0,1]$, and payoff functions
$$ f_1(x_1,x_2)=-(x_1 - x_2)^2+ 2x_1 - x_2 +1$$
$$ f_2(x_1,x_2)=-(x_1 - 2x_2)^2 - 2x_1 + x_2 -1 \koz.  $$
\noindent Formulate Fan's inequality. 
\ujgyak Let $n=2$,
$S_1=S_2=[0,10]$, $f_1(x_1,x_2)=f_2(x_1,x_2)=2x_1+2x_2-(x_1+x_2)^2$.
Formulate the Kuhn-Tucker conditions\gyakindex{Kuhn-Tucker conditions} to find the equilibrium. Solve
the resulted system of inequalities and equations. 
\ujgyak Consider
a 3-person game with $S_1=S_2=S_3=[0,1]$,
$f_1(x_1,x_2,x_3)=(x_1-x_2)^2+x_3$,
$f_2(x_1,x_2,x_3)=(x_2-x_3)^2+x_1$ and
$f_3(x_1,x_2,x_3)=(x_3-x_1)^2+x_2$. Formulate the Kuhn-Tucker
condition. 
\ujgyak\label{ec3.1} Formulate and solve system
\eqref{eq9} for exercise \ref{ec2.4} 
\ujgyak Repeat the previous
problem for the game given in exercise  \ref{ec1.1} 
\ujgyak Rewrite
the Kuhn-Tucker conditions for exercise \ref{ec2.4} into the
optimization problem \eqref{eq10} and solve it. 
\ujgyak\label{ec4.2} Formulate the mixed extension of the finite game given
in Exercise \ref{jat1.1}. 
\vspace{-4mm}
\ujgyak Formulate and solve optimization
problem \eqref{eq10} for the game obtained in the previous problem.
\ujgyak \label{ec4.4} Formulate the mixed extension of the game
introduced in Exercise \ref{ec1.3}.
Formulate and solve the corresponding linear optimization problems \eqref{eq22} with 
$\alpha = 5$, $\beta = 3$, $\gamma=1$.
\ujgyak \label{ec5.1} Use fictitious play method for solving the
matrix game of exercise  \ref{ec4.4}
\vspace{-4mm}
\ujgyak \label{ec5.4} Generalize the fictitious play method for
bimatrix games.
\ujgyak Generalize the fictitious play method for the mixed
extensions of finite $n$-person games.
\ujgyak Solve the bimatrix game with matrics
 $\mathbf{A} = \left(
\begin{array}{rr}
2 & -1 \\
-1 & 1
\end{array} \right)$ and
$\mathbf{B} = \left(
\begin{array}{rr}
1 & -1 \\
-1 & 2
\end{array} \right)$ with the method you have developed in Exercise \ref{ec5.4}. 
\ujgyak \label{ec6.1} Solve the symmetric matrix game
$\mathbf{A} = \left(
\begin{array}{rrr}
0 & 1 & 5 \\
-1 & 0 & -3 \\
-5 & 3 & 0
\end{array}\right)$ by linear programming.
\ujgyak \label{ec6.2} Repeat exercise \ref{ec6.1} with the method of
fictitious play.
\ujgyak \label{ec6.3} Develop the Kuhn-Tucker conditions
\eqref{eq9} for the game
given in Exercise \ref{ec6.1} above.
\hardgyak \label{ec6.4} Repeat Exercises \ref{ec6.1}, \ref{ec6.2} and
\ref{ec6.3} for the matrix game $\mathbf{A} = \left(
\begin{array}{rrr}
1 & 2 & 3 \\
-1 & 0 & 1
\end{array}\right).$ (First find the equivalent symmetric matrix
game!).
\ujgyak Formulate the linear programming problem to solve the matrix
game with matrix $\mathbf{A} = \left(
\begin{array}{cc}
1 & 2 \\
3 & 1
\end{array}\right)$.
\ujgyak \label{ec7.2} Formulate a linear programming solver based on
the method of fictitious play and solve the LP problem:
\begin{eqnarray*}
\textup{maximize} & &  x_1 + x_2   \\
\textup{subject to} & & x_1,x_2  \geq  0 \\
& & 3x_1 + x_2  \leq  4 \\
& & x_1 + 3x_2  \leq  4 \koz.
\end{eqnarray*}
\ujgyak Solve the LP problem given in Example 8.17 by the method of
fictitious play.
\ujgyak \label{ec8.1} Solve Exercise \ref{ec6.1} by the method of von
Neumann.
\ujgyak \label{ec8.2} Solve Exercise \ref{ec6.4} by the method of von
Neumann.
\ujgyak \label{ec8.3} Solve Exercise \ref{ec5.1} by the method of von
Neumann.
\hardgyak Check the solution obtained in the previous exercises by
verifying that all constraints of  \eqref{eq21} are satisfied with
zero objective function. \textit{Hint.} What $\alpha$ and $\beta$ should be
selected?
\ujgyak Solve exercise \ref{ec7.2} by the method of von Neumann.
\ujgyak Let $N=2$, $S_1 = S_2 = [0,10]$, $f_1(x_1,x_2)=f_2(x_1,x_2)
= 2x_1 +2x_2 - (x_1 + x_2)^2$. Show that both payoff functions are
strictly concave in $x_1$ and $x_2$ respectively. Prove that there
are infinitely many equilibria, that is , the strict concavity of
the payoff functions does not imply the uniqueness of the
equilibrium.
\ujgyak Can matrix games be strictly diagonally concave?
\ujgyak \label{ec9.3} Consider a two-person game with strategy sets
$S_1=S_2 = [0,1]$, and payoff functions $f_1(x_1,x_2) = -2x_1^2 +
x_1(1 - x_2) $, $f_2(x_1,x_2) = -3x_2^2 + x_2 (1 - x_1)$. Show that
this game satisfies all conditions of Theorem \ref{th16}.
\ujgyak Solve the problem of the previous exercise by algorithm
\eqref{eq47}--\eqref{eq48}.
\end{gyak}

\section{The oligopoly problem}
The previous sections presented general methodology, however special
methods are available for almost all special classes of games. In
the following parts of this chapter a special game, the
\ki{oligopoly game}\inddef{oligopoly game} will be examined. It
describes a real-life economic situation when $N$-firms produce a
homogeneous good to a market, or offers the same service. This model
is known as the \ki{classical Cournot model.}\inddef{classical
Cournot model} \nevindex{Cournot, Antoine Augustin (1801--1877)}
The firms are the players. The strategy of each player is its
production level $x_k$ with strategy set $S_k = [0,L_k]$, where
$L_k$ is its capacity limit. It is assumed that the market price
depends on the total production level $s = x_1 + x_2 + \cdots + x_N$
offered to the market: $p(s)$, and the cost of each player depends
on its own production level: $c_k(x_k)$. The profit of each firm is
given as
\begin{equation}\label{eq50}
f_k(x_1,\ldots,x_N) = x_k  p \left(\sum_{l = 1}^N x_l \right ) -
c_k(x_k) .
\end{equation}
\noindent In this way an $N$-person game $G = \{
N;S_1,\ldots,S_N;f_1,\ldots,f_N \}$ is defined.

It is usually assumed that functions $p$ and $c_k \
(k=1,2,\ldots,N)$ are twice continuously differentiable, furthermore
\begin{enumerate}
\item $p'(s) < 0$;
\item $p'(s) + x_k p''(s) \leq 0$;
\item $p'(s) - c_k''(x_k) < 0$
\end{enumerate}
for all $k$, $x_k \in [0,L_k]$ and $s \in [0,\sum_{l=1}^N
L_l]$. Under assumptions 1--3. the game satisfies all conditions of
Theorem \ref{th3}, so there is at least one equilibrium.

\subsubsection{Best reply mappings.}\label{2.10.1}

Notice that with the notation $s_k = \sum_{l \neq k} x_l$, the
payoff function of player $\mathcal{P}_k$ can be rewritten as
\begin{equation}\label{eq51}
x_k p(x_k + s_k) - c_k (x_k) \koz .
\end{equation}
\noindent Since $S_k$ is a compact set and this function is strictly
concave in $x_k$, with fixed $s_k$ there is a unique profit
maximizing production level of player $\mathcal{P}_k$, which is its
best reply and is denoted by $B_k(s_k)$.

It is easy to see that there are three cases: $B_k(s_k) = 0$ if
$p(s_k) - c'_k(0) \leq 0$, $B_k(s_k) = L_k$ if $p(s_k + L_k) + L_k
p'(s_k + L_k) - c'_k(L_k) \geq 0$, and otherwise $B_k(s_k)$ is the
unique solution of the monotonic equation
$$ p(s_k + x_k) + x_k p'(s_k + x_k) - c'_k(x_k) = 0 \koz .$$
\noindent Assume that $x_k \in (0,L_k)$. Then implicit
differentiation with respect to  $s_k$ shows that
$$ p'(1 + B_k') + B_k' p' + x_k p''(1 + B_k') - c''_k B_k' = 0 $$
\noindent showing that
$$ B_k'(s_k) = -\frac{p' + x_k p''}{2p' + x_k p'' -c_k''} \koz .$$
\noindent Notice that from assumptions 2. and 3.,
\begin{equation}\label{eq52}
-1 < B_k'(s_k) \leq 0 \koz ,
\end{equation}
\noindent which is also true for the other two cases except for the
break points.

As in Subsection \ref{2.1}. we can introduce the best reply mapping:
\begin{equation}\label{eq53}
\mathbf{B}(x_1,\ldots,x_N) = \left (B_1 \left (\sum_{l \neq 1} x_l
\right ),\ldots,B_N \left ( \sum_{l \neq N}  x_l \right ) \right )
\end{equation}
\noindent and look for its fixed points. Another alternative is to
introduce dynamic process which converges to the equilibrium.

Similarly to the method of fictitious play a discrete system can be
developed in which each firm selects its best reply against the
actions of the competitors chosen at the previous time period:
\begin{equation}\label{eq54}
x_k(t+1) = B_k (\sum_{l \neq k} x_l(t)) \mspace{40mu} (k=1,2,\ldots,N) \koz .
\end{equation}
\noindent Based on relation \eqref{eq52} we see that for $N = 2$ the
right hand side mapping $\R^2 \rightarrow \R^2$ is a contraction, so
it converges, however if $N> 2$, then no convergence can be
established. Consider next a slight modification of this system:
with some $K_k > 0$:
\begin{equation}\label{eq55}
x_k(t+1) = x_k(t) + K_k (B_k (\sum_{l \neq k} x_l(t)) - x_k(t))
\end{equation}
\noindent for $k=1,2,\ldots,N$. Clearly the steady-states of this
system are the equilibria, and it can be proved that if $K_k$ is
sufficiently small, then sequences $x_k(0),x_k(1),x_k(2),\ldots$ are
all convergent to the equilibrium strategies.

Consider next the continuous counterpart of model \eqref{eq55}, when
(similarly to the method of von Neumann) continuous time scales are
assumed:
\begin{equation}\label{eq56}
\dot{x}_k(t) = K_k (B_k (\sum_{l \neq k} x_l(t)) - x_k(t))\ \ \ \
(k=1,2,\ldots,N) \koz .
\end{equation}
\noindent The following result shows the convergence of this
process.

\begin{tetel}\label{th20}
Under assumptions 1--3, system \eqref{eq56} is asymptotically
stable, that is, if the initial $x_k(0)$ values are selected close
enough to the equilibrium, then as $t\rightarrow\infty$, $x_k(t)$
converges to the equilibrium strategy for all $k$.
\end{tetel}

\begin{biz}
It is sufficient to show that the eigenvalues of the Jacobian of the
system have negative real parts. Clearly the Jacobian is as follows:
\begin{equation}\label{eq57}
\mathbf{J} = \left(
\begin{array}{cccc}
-K_1 & K_1b_1 & \cdots & K_1b_1 \\
K_2b_2 & -K_2 & \cdots & K_2b_2 \\
\vdots & \vdots & & \vdots \\
K_Nb_N & K_Nb_N & \cdots & -K_N
\end{array}\right) \koz ,
\end{equation}
where $b_k = B_k'(\sum_{l \neq k} x_l)$ at the
equilibrium. From \eqref{eq52} we know that $-1 < b_k \leq 0$ for
all $k$. In order to compute the eigenvalues of $\mathbf{J}$ we will
need a simple but very useful fact. Assume that $\mathbf{a}$ and
$\mathbf{b}$ are $N$-element real vectors. Then
\begin{equation}\label{eq58}
\textup{det}(\mathbf{I} + \mathbf{a}\mathbf{b}^T) = 1 +
\mathbf{b}^T\mathbf{a} \koz ,
\end{equation}
where $\mathbf{I}$ is the $N \times N$ identity matrix.
This relation can be easily proved by using finite induction with
respect to  $N$. By using \eqref{eq58}, the characteristic
polynomial of $\mathbf{J}$ can be written as
\begin{eqnarray*}
\phi(\lambda) & = & \textup{det}(\mathbf{J} - \lambda \mathbf{I}) = \textup{det} (\mathbf{D} +
\mathbf{a}\mathbf{b}^T - \lambda \mathbf{I}) \\
& = & \textup{det}(\mathbf{D} - \lambda \mathbf{I}) \textup{det}(\mathbf{I} +
(\mathbf{D} - \lambda \mathbf{I})^{-1} \mathbf{a}\mathbf{b}^T) \\
& = & \textup{det}(\mathbf{D} - \lambda \mathbf{I}) [1 + \mathbf{b}^T(\mathbf{D}
- \lambda \mathbf{I})^{-1} \mathbf{a}] \\
& = & \Pi_{k=1}^N (-K_k(1+ b_k)- \lambda)[1+ \sum_{k=1}^N
\frac{K_kb_k}{-K_k(1+b_k)-\lambda}]  \koz,
\end{eqnarray*}
where we used the notation
$$ \mathbf{a}= \left(
\begin{array}{cccc}
K_1b_1 \\
K_2b_2 \\
\vdots \\
K_Nb_N
\end{array}\right), \ \
\mathbf{b}^T = (1,1,\ldots,1), \ \ \mathbf{D}= \left(
\begin{array}{rrr}
-K_1(1 + b_1) & & \\
& \ddots &  \\
& & -K_N(1+b_N)
\end{array}\right)  \koz.
$$
\noindent The roots of the first factor are all negative: $\lambda =
-K_k(1+b_k)$, and the other eigenvalues are the roots of equation
$$ 1 + \sum_{k=1}^N \frac{K_kb_k}{-K_k(1+b_k)-\lambda} = 0  . $$
\noindent Notice that by adding the terms with identical
denominators this equation becomes
\begin{equation}\label{eq59}
1 + \sum_{l=1}^m \frac{\alpha_k}{\beta_k + \lambda} = 0
\end{equation}
\noindent with $\alpha_k,\beta_k > 0$, and the $\beta_ks$ are
different. If $g(\lambda)$ denotes the left hand side then clearly
the values $\lambda = - \beta_k$ are the poles,
\begin{equation*}
\begin{split}
\lim_{\lambda \rightarrow \pm \infty} g(\lambda) = 1,\ \
\lim_{\lambda \rightarrow - \beta_k \pm 0} g(\lambda) =
\pm \infty  , \\
g'(\lambda) = \sum_{l=1}^m \frac{-\alpha_l}{(\beta_l + \lambda)^2} <
0 \koz ,
\end{split}
\end{equation*}
\noindent so $g(\lambda)$ strictly decreases locally. The graph of
the function is shown in Figure \ref{jatekkep:2}. Notice first that
\eqref{eq59} is equivalent to a polynomial equation of degree $m$,
so there are $m$ real or complex roots. The properties of function
$g(\lambda)$ indicate that there is one root below $-\beta_1$, and
one root between each $-\beta_k$ and $-\beta_{k+1}$
$(k=1,2,\ldots,m-1).$ Therefore all roots are negative, which
completes the proof.
\end{biz}

\epskep{figs/18.3}{The graph of function $g(\lambda).$}\label{jatekkep:2}


The general discrete model \eqref{eq55} can be examined in the same
way. If $K_k = 1$ for all $k$, then model \eqref{eq55} reduces to
the simple dynamic process \eqref{eq54}.

\begin{pelda}\label{ex21}
Consider now a $3$-person oligopoly with price function
$$ p(s) = \left\{
\begin{array}{ll}
2-2s-s^2, & \mbox{if} \mspace{20mu} 0 \leq s \leq \sqrt{3} - 1 \koz , \\
0 & \mbox{otherwise} \koz ,
\end{array}\right.$$
\noindent strategy sets $S_1 = S_2 = S_3 = [0,1]$, and cost
functions
$$ c_k(x_k) = kx_k^3 + x_k \mspace{30mu} (k=1,2,3) \koz .$$
\noindent The profit of firm $k$ is therefore the following:
$$ x_k(2-2s-s^2) - (kx_k^3 + x_k) = x_k(2 - 2x_k - 2s_k -x_k^2 - 2x_ks_k - s_k^2
)- kx_k^3 -x_k \koz .$$
\noindent The best reply of play $k$ can be
obtained as follows. Following the method outlined at the beginning
of Section \ref{2.10.1} we have the following three cases. If
$1-2s_k-s_k^2 \leq 0$, then $x_k = 0$ is the best choice. If
$(-6-3k)-6s_k-s_k^2 \geq 0$, then $x_k = 1$ is the optimal decision.
Otherwise $x_k$ is the solution of equation
\begin{equation*}
\begin{split}
\frac{\partial}{\partial x_k}[x_k(2-2x_k - 2s_k -s_k^2 -2s_kx_k - x_k^2) -kx_k^3 -
x_k] \\
=2-4x_k -2s_k - s_k^2 -4s_kx_k -3x_k^2 - 3kx_k^2 -1 =0 \koz ,
\end{split}
\end{equation*}
where the only positive solution is
$$ x_k = \frac{-(4 + 4s_k) + \sqrt{(4+4s_k)^2 - 12(1+k)(s_k^2 + 2s_k
-1)}}{6(1+k)} \koz .
$$
After the best replies are found,
we can easily construct any of the methods presented before.
\end{pelda}

\subsubsection{Reduction to single-dimensional fixed point problems.}
Consider an $N$-firm oligopoly with price function $p$ and cost
functions $c_k$ ($k=1,2,\ldots,N$). Introduce the following function
\begin{equation}\label{eq60}
\Psi_k(s,x_k,t_k) = t_k p (s-x_k+t_k) - c_k(t_k) \koz ,
\end{equation}
and define
\begin{equation}\label{eq61}
X_k(s) = \{ x_k | x_k \in S_k,\ \ \Psi_k(s,x_k,x_k) = \max_{t_k \in
S_k} \Psi_k(s,x_k,t_k) \}
\end{equation}
for $k=1,2,\ldots,N$ and let
\begin{equation}\label{eq62}
X(s) = \{ u | u=\sum_{k=1}^N x_k,\ \ x_k \in X_k(s),\ \
k=1,2,\ldots,N \} \koz.
\end{equation}
Notice that if $s \in [0,\sum_{k=1}^N L_k]$, then all
elements of $X(s)$ are also in this interval, therefore $X$ is a
single-dimensional point-to-set mapping. Clearly
$(x_1^\star,\ldots,x_N^\star)$ is an equilibrium of the $N$-firm
oligopoly game if and only if $s^\star = \sum_{k=1}^N x_k^\star$ is
a fixed point of mapping $X$ and for all $k$, $x_k^\star \in
X_k(s^\star)$. Hence the equilibrium problem has been reduced to
find fixed points of only one-dimensional mappings. This is a
significant reduction in the difficulty of the problem, since best
replies are $N$-dimensional mappings.

If conditions 1--3 are satisfied, then $X_k(s)$ has exactly one
element for all $s$ and $k$:
\begin{equation}\label{eq63}
X(s) =\left\{
\begin{array}{ll}
0, & \mbox{if  } p(s) -c'_k(0) \leq 0 \koz , \\
L_k, & \mbox{if  } p(s) + L_kp'_k(s) - c_k'(L_k) \geq 0  \koz , \\
z^\star & \mbox{otherwise}  \koz,
\end{array}\right.
\end{equation}
\noindent where $z^\star$ is the unique solution of the monotonic
equation
\begin{equation}\label{eq64}
p(s) + zp'(s) - c_k'(z) = 0
\end{equation}
\noindent in the interval $(0,L_k)$. In the third case, the left
hand side is positive at $z = 0$, negative at $z = L_k$, and by
conditions 2--3, it is strictly decreasing, so there is a unique
solution.

In the entire interval $[0,\sum_{k=1}^N L_k]$, $X_k(s)$ is
nonincreasing. In the first two cases it is constant and in the
third case strictly decreasing. Consider finally the
single-dimensional equation
\begin{equation}\label{eq65}
\sum_{k=1}^N X_k(s) -s = 0 \koz .
\end{equation}
\noindent At $s = 0$ the left hand side is nonnegative, at $s=
\sum_{k=1}^N L_k$ it is nonpositive, and is strictly decreasing.
Therefore there is a unique solution (that is, fixed point of
mapping $X$), which can be obtained by any method known to solve
single-dimensional equations.

Let $[0,S_{max}]$ be the initial interval for the solution of
equation \eqref{eq65}. After $K$ bisection steps the accuracy
becomes $S_{max}/{2^K}$, which will be smaller than an error
tolerance $\epsilon> 0$ if $K > \log_2 (S_{max}/\epsilon).$

\begin{alg}{Oligopoly-Equilibrium$(p(s),X(s))$}\inddef{\textsc{Oligopoly-Equilibrium}}
1 \' solve equation (\ref{eq65}) for $s$\\
2 \' \key{for} \= $k \leftarrow 1$ to $n$ \\
3 \'           \> \key{do} solve equation (\ref{eq64}), and let $x_k \leftarrow z$ \\
4 \' $(x_1,\ldots,x_N)$ is equilibrium
\end{alg}

\begin{pelda}\label{ex22}
Consider the 3-person oligopoly examined in the previous example.
From \eqref{eq63} we have
$$ X(s) =\left\{
\begin{array}{ll}
0, & \mbox{if} \mspace{20mu} 1-2s -s^2 \leq 0  , \\
1, & \mbox{if} \mspace{20mu}  -(1+3k) - 4s -s^2 \geq 0  , \\
z^\star & \mbox{otherwise}  ,
\end{array}\right. $$
\noindent where $z^\star$ is the unique solution of equation
$$ 3kz^2 + z (2s + 2) + (-1 + 2s + s^2) = 0.$$
\noindent The first case occurs for $s \geq \sqrt{2} -1$, the second
case never occurs, and in the third case there is a unique positive
solution:
\begin{equation}\label{eq66}
z^\star = \frac{-(2s + 2) + \sqrt{(2s + 2)^2 - 12k(-1 + 2s +
s^2)}}{6k} \koz .
\end{equation}
\noindent And finally equation \eqref{eq65} has the special form
$$ \sum_{k=1}^3 \frac{-(s + 1) + \sqrt{(s + 1)^2 - 3k(-1 + 2s +
s^2)}}{3k} - s =0 \koz . $$ \noindent A single program based on the
bisection method gives the solution $s^\star \approx 0.2982$ and
then equation \eqref{eq66} gives the equilibrium strategies
$x_1^\star \approx 0.1077$, $x_2^\star \approx 0.0986$, $x_3^\star
\approx 0.0919$.
\end{pelda}

\subsubsection{Methods based on Kuhn-Tucker conditions}

Notice first that in the case of $N$-player oligopolies $S_k = \{
x_k | x_k \geq 0,\ L_k -x_k \geq 0 \}$, so we select
\begin{equation}\label{eq67}
\mathbf{g}_k(x_k) = \binom{x_k}{L_k - x_k} \koz ,
\end{equation}
\noindent and since the payoff functions are
\begin{equation}\label{eq68}
f_k(x_1,\ldots,x_N) = x_k p(x_k + s_k) - c_k(x_k) \koz ,
\end{equation}
\noindent the Kuhn-Tucker conditions \eqref{eq9} have the following
form. The components of the 2-dimensional vectors $\mathbf{u}_k$
will be denoted by $u_k^{(1)}$ and $u_k^{(2)}$. So we have for
$k=1,2,\ldots,N$,
\begin{equation}\label{eq69}
\begin{array}{rcl}
u_k^{(1)},u_k^{(2)} & \geq & 0 \\
x_k & \geq & 0 \\
L_k - x_k & \geq & 0 \\
p(\sum_{l=1}^N x_l) + x_k p'(\sum_{l=1}^N x_l) - c'_k(x_k) +
(u_k^{(1)},u_k^{(2)}) \binom{1}{-1} & = & 0 \\
u_k^{(1)}x_k + u_k^{(2)}(L_k - x_k) & = & 0  \koz .
\end{array}
\end{equation}
\noindent One might either look for feasible solutions of these
relations or rewrite them as the optimization problem \eqref{eq10},
which has the following special form in this case:
\begin{equation}\label{eq70}
\begin{array}{rcl}
\mbox{minimize} & & \sum_{k=1}^N (u_k^{(1)}x_k + u_k^{(2)}(L_k -
x_k)) \\
\mbox{subject to} & & u_k^{(1)},u_k^{(2)}  \geq  0   \\
& & x_k  \geq  0  \\
 & & L_k - x_k  \geq  0   \\
& & p(\sum_{l=1}^N x_l) + x_k p'(\sum_{l=1}^N x_l) - c'_k(x_k) +
u_k^{(1)} - u_k^{(2)}  =  0 \\
& & \mspace{200mu} (k=1,2,\ldots,N) .
\end{array}
\end{equation}

Computational cost in solving \eqref{eq69} or \eqref{eq70} depends
on the type of functions $p$ and $c_k$. No general characterization
can be given.

\begin{pelda}\label{ex23}
In the case of the three-person oligopoly introduced in Example
\ref{ex21} we have
\begin{eqnarray*}
\mbox{minimize} & &  \sum_{k=1}^3 (u_k^{(1)}x_k + u_k^{(2)}(1 -
x_k))  \\
\mbox{subject to} & & u_k^{(1)},u_k^{(2)}  \geq  0 \\
 & & x_k  \geq  0 \\
 & & 1 - x_k  \geq  0 \\
 & & 1 -2s -s^2 - 2x_k - 2x_k s -3kx_k^2 + u_k^{(1)} -
u_k^{(2)}  =  0 \\
 & & x_1 + x_2 + x_3  =  s  .
\end{eqnarray*}
\noindent A professional optimization software was used to obtain
the optimal solutions:
$$ x_1^\star \approx 0.1077,\ \ x_2^\star \approx 0.0986,\ \
x_3^\star \approx 0.0919 \koz ,$$ \noindent and all $u_k^{(1)} =
u_k^{(2)} = 0 \koz .$
\end{pelda}

\subsubsection{Reduction to complementarity problems.}
If $(x_1^\star,\ldots,x_N^\star)$ is an equilibrium of an $N$-person
oligopoly, then with fixed $x_1^\star,\ldots,$
$x_{k-1}^\star,x_{k+1}^\star,\ldots,x_N^\star$, $x_k = x_k^\star$
maximizes the payoff $f_k$ of player $\mathcal{P}_k$. Assuming that
condition 1--3 are satisfied, $f_k$ is concave in $x_k$, so
$x_k^\star$ maximizes $f_k$ if and only if at the equilibrium
$$ \frac{\partial f_k}{\partial x_k}(\mathbf{x}^\star) = \left\{
\begin{array}{ll}
\leq 0, & \mbox{if} \mspace{20mu} x_k^\star = 0  \koz, \\
= 0, & \mbox{if} \mspace{20mu} 0 < x_k^\star < L_k  \koz, \\
 \geq 0, & \mbox{if} \mspace{20mu} x_k^\star = L_k  \koz.
\end{array}\right. 
$$
So introduce the slack variables
$$ z_k =\left\{
\begin{array}{ll}
= 0, & \mbox{if} \mspace{20mu} x_k > 0  \koz,\\
\geq 0, & \mbox{if} \mspace{20mu} x_k = 0
\end{array}\right. $$
$$ v_k =\left\{
\begin{array}{ll}
= 0, & \mbox{if} \mspace{20mu} x_k < L_k  \koz, \\
\geq 0, & \mbox{if} \mspace{20mu} x_k = L_k
\end{array}\right. $$
and
\begin{equation}\label{eq71}
w_k = L_k - x_k  \koz.
\end{equation}
Then clearly at the equilibrium
\begin{equation}\label{eq72}
\frac{\partial f_k}{\partial x_k}(\mathbf{x}) - v_k + z_k = 0
\end{equation}
and by the definition of the slack variables
\begin{equation}\label{eq73} z_k x_k = 0
\end{equation}
\begin{equation}\label{eq74}
v_k w_k =0 \koz,
\end{equation}
and if we add the nonnegativity conditions
\begin{equation}\label{eq75}
x_k,z_k,v_k,w_k \geq 0 \koz ,
\end{equation}
then we obtain a system of nonlinear relations
\eqref{eq71}--\eqref{eq75} which are equivalent to the equilibrium
problem.

We can next show that relations \eqref{eq71}--\eqref{eq75} can be
rewritten as a nonlinear complementarity problem, for the solution
of which standard methods are available. For this purpose introduce
the notation
$$ \mathbf{v} = \left(
\begin{array}{cccc}
v_1 \\
v_2 \\
\vdots \\
v_N
\end{array}\right),\mspace{20mu} \mathbf{L} = \left(
\begin{array}{cccc}
L_1 \\
L_2 \\
\vdots \\
L_N
\end{array}\right),\mspace{20mu} \mathbf{h}(\mathbf{x}) = \left(
\begin{array}{cccc}
\frac{\partial f_1}{\partial x_1} (\mathbf{x}) \\
\frac{\partial f_2}{\partial x_2} (\mathbf{x})  \\
\vdots \\
\frac{\partial f_N}{\partial x_N} (\mathbf{x})
\end{array}\right)  ,$$
$$ \mathbf{t} = \binom{\mathbf{x}}{\mathbf{v}},\mspace{20mu} \mbox{and}\mspace{20mu}
\mathbf{g}(\mathbf{t}) = \binom{-\mathbf{h}(\mathbf{x}) +
\mathbf{v}}{\mathbf{L} - \mathbf{x}} \koz,$$
then system
\eqref{eq72}--\eqref{eq75} can be rewritten as
\begin{equation}\label{eq76}
\begin{array}{rcl}
\mathbf{t} & \geq & \mathbf{0} \\
\mathbf{g}(\mathbf{t}) & \geq & \mathbf{0} \\
\mathbf{t}^T \mathbf{g}(\mathbf{t}) & = & 0 \koz.
\end{array}
\end{equation}

This problem is the usual formulation of \ki{nonlinear
complementarity}\inddef{nonlinear complementarity problem} problems.
Notice that the last condition requires that in each component
either $\mathbf{t}$ or $\mathbf{g}(\mathbf{t})$ or both must be
zero.

The computational cost in solving problem \eqref{eq76} depends on
the type of the involved functions and the choice of method.


\begin{pelda}\label{ex24}
In the case of the 3-person oligopoly introduced and examined in the
previous examples we have:
$$ \mathbf{t} = \hspace{-1mm} \left(
\begin{array}{cccccc}
x_1 \\
x_2 \\
x_3 \\
v_1 \\
v_2 \\
v_3
\end{array}\right)\mspace{2mu} \text{and}\mspace{5mu} \mathbf{g}(\mathbf{t}) =\hspace{-1mm} \left(
\begin{array}{cccccc}
-1 + 2\sum_{l=1}^3 x_l + (\sum_{l=1}^3 x_l)^2 + 2x_1 + 2x_1 \sum_{l=1}^3 x_l + 3x_1^2 + v_1 \\
-1 + 2\sum_{l=1}^3 x_l + (\sum_{l=1}^3 x_l)^2 + 2x_2 + 2x_2 \sum_{l=1}^3 x_l + 6x_2^2 + v_2 \\
-1 + 2\sum_{l=1}^3 x_l + (\sum_{l=1}^3 x_l)^2 + 2x_3 + 2x_3 \sum_{l=1}^3 x_l + 9x_3^2 + v_3 \\
1 - x_1 \\
1 - x_2 \\
1 - x_3
\end{array}\right) .$$
\end{pelda}

\subsubsection{Linear oligopolies and quadratic programming.}
In this section $N$-player oligopolies will be examined under the
special condition that the price and all cost functions are linear :
$$ p(s) = As + B, \mspace{20mu} c_k(x_k) = b_kx_k + c_k \mspace{20mu}
(k=1,2,\ldots,N) \koz ,$$ \noindent where $B$, $b_k$, and $c_k$ are
positive, but $A < 0$. Assume again that the strategy set of player
$\mathcal{P}_k$ is the interval $[0,L_k]$. In this special case
\begin{equation}\label{eq77}
f_k(x_1,\ldots,x_N) = x_k(Ax_1 + \cdots + Ax_N + B) - (b_k x_k + c_k)
\end{equation}
for all $k$, therefore
\begin{equation}\label{eq78}
\frac{\partial f_k}{\partial x_k}(\mathbf{x}) = 2Ax_k + A \sum_{l
\neq k} x_l + B - b_k \koz,
\end{equation}
and relations \eqref{eq71}--\eqref{eq75} become more special:
\begin{eqnarray*}
2Ax_k + A \sum_{l \neq k} x_l + B - b_k - v_k +z_k & = & 0 \\
z_kx_k = v_kw_k & = & 0 \\
x_k + w_k & = & L_k \\
x_k,v_k,z_k,w_k & \geq & 0 \koz,
\end{eqnarray*}
\noindent where we changed the order of them. Introduce the
following vectors and matrixes:
$$ \mathbf{Q} = \left(
\begin{array}{cccc}
2A & A & \cdots & A \\
A & 2A & \cdots & A \\
\vdots & \vdots & & \vdots \\
A & A & \cdots & 2A
\end{array}\right),\mspace{20mu} \mathbf{B} = \left(
\begin{array}{cccc}
B \\
B \\
\vdots \\
B
\end{array}\right),\mspace{20mu} \mathbf{b} = \left(
\begin{array}{cccc}
b_1 \\
b_2 \\
\vdots \\
b_N
\end{array}\right) \koz ,$$
$$ \mathbf{v} = \left(
\begin{array}{cccc}
v_1 \\
v_2 \\
\vdots \\
v_N
\end{array}\right),\mspace{20mu} \mathbf{w} = \left(
\begin{array}{cccc}
w_1 \\
w_2 \\
\vdots \\
w_N
\end{array}\right),\mspace{20mu} \mathbf{z} = \left(
\begin{array}{cccc}
z_1 \\
z_2 \\
\vdots \\
z_N
\end{array}\right),\mspace{20mu} \mbox{and}\mspace{20mu} \mathbf{L} = \left(
\begin{array}{cccc}
L_1 \\
L_2 \\
\vdots \\
L_N
\end{array}\right) \koz .
$$
Then the above relations can be summarized as:
\begin{equation}\label{eq79}
\begin{array}{rcl}
\mathbf{Q}\mathbf{x} + \mathbf{B} - \mathbf{b} - \mathbf{v} +
\mathbf{z} & = & \mathbf{0} \\
\mathbf{x} + \mathbf{w} & = & \mathbf{L} \\
\mathbf{x}^T \mathbf{z} = \mathbf{v}^T \mathbf{w} & = & 0 \\
\mathbf{x},\mathbf{v},\mathbf{z},\mathbf{w} & \geq & \mathbf{0} \koz .
\end{array}
\end{equation}
Next we prove that matrix $\mathbf{Q}$ is negative
definite. With any nonzero vector $\mathbf{a} = (a_i)$,
\begin{equation*}
\mathbf{a}^T \mathbf{Q} \mathbf{a} = 2A\sum_i a_i^2 + A \sum_i
\sum_{j \neq i} a_i a_j = A(\sum_i a_i^2 + (\sum_i a_i)^2) < 0 \koz ,
\end{equation*}
\noindent which proves the assertion.

Observe that relations \eqref{eq79} are the Kuhn-Tucker conditions
of the strictly concave quadratic programming problem:
\begin{equation}\label{eq80}
\begin{array}{rcl}
\mbox{maximize} & & \frac{1}{2} \mathbf{x}^T \mathbf{Q} \mathbf{x} +
(\mathbf{B} -
\mathbf{b}) \mathbf{x}  \\
\mbox{subject to} & & \mathbf{0} \leq \mathbf{x}  \leq  \mathbf{L}\koz,
\end{array}
\end{equation}
\noindent and since the feasible set is a bounded linear polyhedron
and the objective function is strictly concave, the Kuhn-Tucker
conditions are sufficient and necessary. Consequently a vector
$\mathbf{x}^\star$ is an equilibrium if and only if it is the unique
optimal solution of problem \eqref{eq80}. There are standard methods
to solve problem \eqref{eq80} known from the literature.

Since \eqref{eq79} is a convex quadratic programming problem,
several algorithms are available. Their costs are different, so
computation cost depends on the particular method being selected.


\begin{pelda}
Consider now a duopoly (two-person oligopoly) where the price
function is  $p(s) = 10 - s$ and the cost functions are $c_1(x_1) =
4x_1 + 1$ and $c_2(x_2) = x_2 + 1$ with capacity limits $L_1 = L_2 =
5$. That is,
$$ B=10,\ \ A=-1,\ \ b_1=4,\ \ b_2=1,\ \ c_1 = c_2 = 1 \koz .$$
\noindent Therefore,
$$ \mathbf{Q} = \left(
\begin{array}{rr}
-2 & -1 \\
-1 & -2
\end{array}\right),\mspace{20mu}  \mathbf{B} = \binom{10}{10},\mspace{20mu}
\mathbf{b} = \binom{4}{1},\mspace{20mu} \mathbf{L} = \binom{5}{5},
$$
so the quadratic programming problem can be written as:
\begin{eqnarray*}
\mbox{maximize} & & \frac{1}{2}(-2x_1^2 - 2x_1x_2 - 2x_2^2) + 6x_1 + 9x_2 \\
\mbox{subject to} & & 0 \leq x_1  \leq  5 \\
& & 0 \leq x_2  \leq  5  \koz.
\end{eqnarray*}
It is easy to see by simple differentiation that the
global optimum at the objective function without the constraints is
reached at $x_1^\star=1$ and $x_2^\star =4$. They however satisfy
the constraints, so they are the optimal solutions. Hence they
provide the unique equilibrium of the duopoly.
\end{pelda}

\begin{gyak}
\ujgyak \label{ec10.1} Consider a duopoly with $S_1 = S_2 = [0,1]$,
$p(s) = 2 -s$ and costs $c_1(x) = c_2(x) = x^2 + 1$. Examine the
convergence of the iteration scheme \eqref{eq55}. 
\ujgyak Select $n
= 2$, $S_1 = S_2 = [0,1.5]$, $c_k(x_k) = 0.5x_k$ $(k=1,2)$ and
$$ p(s) =\left\{
\begin{array}{ll}
1.75 - 0.5s, & \mbox{if} \mspace{20mu} 0 \leq s \leq 1.5  \koz, \\
2.5 - s, & \mbox{if} \mspace{20mu} 1.5 \leq s \leq 2.5  \koz, \\
0, & \mbox{if} \mspace{20mu} 2.5 \leq s  \koz .
\end{array}\right.
$$
Show that there are infinitely many equilibria:
$$ \{ (x_1^\star,x_2^\star) | 0.5 \leq x_1 \leq 1,\ \ 0.5 \leq x_2
\leq 1,\ \ x_1 + x_2 = 1.5 \}  \koz.
$$
\ujgyak Consider the duopoly of Exercise \ref{ec10.1} above. Find the best reply mappings of the
players and determine the equilibrium.
\ujgyak Consider again the
duopoly of the previous problem.\\ (a) Construct the one-dimensional
fixed point problem of mapping
 \eqref{eq62} and solve it to obtain the equilibrium.\\
(b) Formulate the Kuhn-Tucker equations\gyakindex{Kuhn-Tucker equations} and inequalities \eqref{eq69}.\\
(c) Formulate the complementarity problem \eqref{eq76} in this case.
\end{gyak}


\begin{fejmegj}
(Economic) Nobel Prize was given only once, in 1994 in the field of
game theory. One of the winner was John Nash \nevindex{Nash, John
F., Jr.}, who received this honor for his equilibrium concept, which
was introduced in 1951 \cite{Nash51}.

Backward induction is a more restrictive equilibrium concept. It was
developed by Kuhn\nevindex{Kuhn, Harold W.} and can be found in
\cite{KuhnTu53}.\nevindex{Tucker, Albert W.} Since it is more
restrictive equilibrium, it is also a Nash equilibrium.

The existence and computation of equilibria can be reduced to those
of fixed points. the different variants of fixed point theorems-such
as that of Brouwer
\cite{Brouwer12}\nevindex{Brouwer, Luitzer Egbertus Jan (1881--1966)},
Kakutani\cite{Kakutani41},\nevindex{Kakutani, Shizou} Tarski
\cite{Tarski55}\nevindex{Tarski, Alfred (1902--1983)} are successfully used to
prove existence in many game classes. The article \cite{
Nikaido55}\nevindex{Nikaido, Hukukane} uses the fixed point theorem
of Kakutani. The books \cite{SzidarovszkyYa78} and \cite{ForgoSz99}
\nevindex{Forgó, Ferenc}\nevindex{Szidarovszky,
Ferenc}\nevindex{Szép, Jenõ (1920--2004)} discuss computer methods for
computing fixed points. The most popular existence result is the
well known theorem of Nikaido and Isoda \cite{Nikaido55}.


The Fan \nevindex{Fan, Ky} inequality is discussed in
the book of Aubin \cite{Aubin79}.\nevindex{Aubin, Jean-Pierre} The
Kuhn-Tucker conditions are presented in the book of Martos
\cite{Martos75}.\nevindex{Martos, Béla} By introducing slack and
surplus variables the Kuhn-Tucker conditions can be rewritten as a
system of equations. For their computer solutions well known methods
are available  (\cite{SzidarovszkyYa78} and \cite{Martos75}).

The reduction of bimatrix games to mixed optimization problems is
presented in the papers of Mills \cite{Mills60} and Shapiro
\cite{Shapiro58}. The reduction to quadratic programming problem is
given in (\cite{Mangasarian64}).

The method of fictitious play is discussed in the paper of Robinson
\cite{Robinson51}. \nevindex{Robinson, Julia} In order to use the
Neumann \nevindex{Neumann, John, von (1903--1957)} method we have
to solve a system of nonlinear ordinary differential equations. The
Runge--Kutta method is the most popular procedure for doing it. It
can be found in \cite{SzidarovszkyYa78}.

The paper of Rosen \cite{Rosen65} introduces diagonally strictly
concave games.  \nevindex{Rosen, J. B.} The computer method to find
the equilibria of $N$-person concave games is introduced in
Zuhovitsky et al. \nevindex{Zuhovitsky, S. I.} \cite{Zuhovitsky71}.

The different extensions and generalizations of the classical
Cournot model \nevindex{Cournot, Antoine Augustin (1801--1877)}
can be found in the books of Okuguchi and Szidarovszky
\cite{Okuguchi76,OkuguchiSz99}. \nevindex{Okuguchi,
Koji}\nevindex{Szidarovszky, Ferenc} The proof of Theorem \ref{th20}
is given in \cite{SzidarovszkyCh01}.\nevindex{Chiarella, Carl} For
the proof of Lemma \eqref{eq58} see the monograph
\cite{OkuguchiSz99}. The bisection method is described in
\cite{SzidarovszkyYa78}\nevindex{Yakowitz, Sidney}. The paper
\cite{Karamardian69} contains methods which are applicable to solve
nonlinear complementarity problems. The solution of problem
(\ref{eq80}) is discussed in the book of Hadley
\cite{Hadley64}.\nevindex{Hadley, George F.}

The book of von Neumann and Morgenstern \cite{NeumannMo} is
considered the classical textbook of game theory.
\nevindex{Neumann, John, von (1903--1957)}\nevindex{Morgenstern,
Oscar (1902--1976)} There is a large variety of game theory textbooks (see for
example \cite{ForgoSz99}).
\end{fejmegj}

