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 oligopoly game will be examined. It describes a reallife economic situation when firms produce a homogeneous good to a market, or offers the same service. This model is known as the classical Cournot model. The firms are the players. The strategy of each player is its production level with strategy set , where is its capacity limit. It is assumed that the market price depends on the total production level offered to the market: , and the cost of each player depends on its own production level: . The profit of each firm is given as
In this way an person game is defined.
It is usually assumed that functions and are twice continuously differentiable, furthermore
;
;
for all , and . Under assumptions 1–3. the game satisfies all conditions of Theorem 10.3, so there is at least one equilibrium.
Notice that with the notation , the payoff function of player can be rewritten as
Since is a compact set and this function is strictly concave in , with fixed there is a unique profit maximizing production level of player , which is its best reply and is denoted by .
It is easy to see that there are three cases: if , if , and otherwise is the unique solution of the monotonic equation
Assume that . Then implicit differentiation with respect to shows that
showing that
Notice that from assumptions 2. and 3.,
which is also true for the other two cases except for the break points.
As in Subsection 10.2.1 we can introduce the best reply mapping:
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:
Based on relation (10.52) we see that for the right hand side mapping is a contraction, so it converges, however if , then no convergence can be established. Consider next a slight modification of this system: with some :
for . Clearly the steadystates of this system are the equilibria, and it can be proved that if is sufficiently small, then sequences are all convergent to the equilibrium strategies.
Consider next the continuous counterpart of model (10.55), when (similarly to the method of von Neumann) continuous time scales are assumed:
The following result shows the convergence of this process.
Theorem 10.20 Under assumptions 1–3, system (10.56) is asymptotically stable, that is, if the initial values are selected close enough to the equilibrium, then as , converges to the equilibrium strategy for all .
Proof. It is sufficient to show that the eigenvalues of the Jacobian of the system have negative real parts. Clearly the Jacobian is as follows:
where at the equilibrium. From (10.52) we know that for all . In order to compute the eigenvalues of we will need a simple but very useful fact. Assume that and are element real vectors. Then
where is the identity matrix. This relation can be easily proved by using finite induction with respect to . By using (10.58), the characteristic polynomial of can be written as
where we used the notation
The roots of the first factor are all negative: , and the other eigenvalues are the roots of equation
Notice that by adding the terms with identical denominators this equation becomes
with , and the are different. If denotes the left hand side then clearly the values are the poles,
so strictly decreases locally. The graph of the function is shown in Figure 10.5. Notice first that (10.59) is equivalent to a polynomial equation of degree , so there are real or complex roots. The properties of function indicate that there is one root below , and one root between each and . Therefore all roots are negative, which completes the proof.
The general discrete model (10.55) can be examined in the same way. If for all , then model (10.55) reduces to the simple dynamic process (10.54).
Example 10.21 Consider now a person oligopoly with price function
strategy sets , and cost functions
The profit of firm is therefore the following:
The best reply of play can be obtained as follows. Following the method outlined at the beginning of “Best reply mappings.” we have the following three cases. If , then is the best choice. If , then is the optimal decision. Otherwise is the solution of equation
where the only positive solution is
After the best replies are found, we can easily construct any of the methods presented before.
Consider an firm oligopoly with price function and cost functions (). Introduce the following function
and define
for and let
Notice that if , then all elements of are also in this interval, therefore is a singledimensional pointtoset mapping. Clearly is an equilibrium of the firm oligopoly game if and only if is a fixed point of mapping and for all , . Hence the equilibrium problem has been reduced to find fixed points of only onedimensional mappings. This is a significant reduction in the difficulty of the problem, since best replies are dimensional mappings.
If conditions 1–3 are satisfied, then has exactly one element for all and :
where is the unique solution of the monotonic equation
in the interval . In the third case, the left hand side is positive at , negative at , and by conditions 2–3, it is strictly decreasing, so there is a unique solution.
In the entire interval , is nonincreasing. In the first two cases it is constant and in the third case strictly decreasing. Consider finally the singledimensional equation
At the left hand side is nonnegative, at it is nonpositive, and is strictly decreasing. Therefore there is a unique solution (that is, fixed point of mapping ), which can be obtained by any method known to solve singledimensional equations.
Let be the initial interval for the solution of equation (10.65). After bisection steps the accuracy becomes , which will be smaller than an error tolerance if .
OligopolyEquilibrium(
)
1 solve equation (10.65) for 2FOR
to 3DO
solve equation (10.64), and let 4 is equilibrium
Example 10.22 Consider the 3person oligopoly examined in the previous example. From (10.63) we hav
where is the unique solution of equation
The first case occurs for , the second case never occurs, and in the third case there is a unique positive solution:
And finally equation (10.65) has the special form
A single program based on the bisection method gives the solution and then equation (10.66) gives the equilibrium strategies , , .
Notice first that in the case of player oligopolies , so we select
and since the payoff functions are
the KuhnTucker conditions (10.9) have the following form. The components of the 2dimensional vectors will be denoted by and . So we have for ,
One might either look for feasible solutions of these relations or rewrite them as the optimization problem (10.10), which has the following special form in this case:
Computational cost in solving (10.69) or (10.70) depends on the type of functions and . No general characterization can be given.
Example 10.23 In the case of the threeperson oligopoly introduced in Example 10.21 we have
A professional optimization software was used to obtain the optimal solutions:
and all .
If is an equilibrium of an person oligopoly, then with fixed maximizes the payoff of player . Assuming that condition 1–3 are satisfied, is concave in , so maximizes if and only if at the equilibrium
So introduce the slack variables
and
Then clearly at the equilibrium
and by the definition of the slack variables
and if we add the nonnegativity conditions
then we obtain a system of nonlinear relations (10.71)–(10.75) which are equivalent to the equilibrium problem.
We can next show that relations (10.71)–(10.75) can be rewritten as a nonlinear complementarity problem, for the solution of which standard methods are available. For this purpose introduce the notation
then system (10.72)–(10.75) can be rewritten as
This problem is the usual formulation of nonlinear complementarity problems. Notice that the last condition requires that in each component either or or both must be zero.
The computational cost in solving problem (10.76) depends on the type of the involved functions and the choice of method.
Example 10.24 In the case of the 3person oligopoly introduced and examined in the previous examples we have:
In this section player oligopolies will be examined under the special condition that the price and all cost functions are linear :
where , , and are positive, but . Assume again that the strategy set of player is the interval . In this special case
for all , therefore
and relations (10.71)–(10.75) become more special:
where we changed the order of them. Introduce the following vectors and matrixes:
Then the above relations can be summarized as:
Next we prove that matrix is negative definite. With any nonzero vector ,
which proves the assertion.
Observe that relations (10.79) are the KuhnTucker conditions of the strictly concave quadratic programming problem:
and since the feasible set is a bounded linear polyhedron and the objective function is strictly concave, the KuhnTucker conditions are sufficient and necessary. Consequently a vector is an equilibrium if and only if it is the unique optimal solution of problem (10.80). There are standard methods to solve problem (10.80) known from the literature.
Since (10.79) is a convex quadratic programming problem, several algorithms are available. Their costs are different, so computation cost depends on the particular method being selected.
Example 10.25 Consider now a duopoly (twoperson oligopoly) where the price function is and the cost functions are and with capacity limits . That is,
Therefore,
so the quadratic programming problem can be written as:
It is easy to see by simple differentiation that the global optimum at the objective function without the constraints is reached at and . They however satisfy the constraints, so they are the optimal solutions. Hence they provide the unique equilibrium of the duopoly.
Exercises
10.31 Consider a duopoly with , and costs . Examine the convergence of the iteration scheme (10.55).
10.32 Select , , and
Show that there are infinitely many equilibria:
10.33 Consider the duopoly of Exercise 10.31 above. Find the best reply mappings of the players and determine the equilibrium.
10.34 Consider again the duopoly of the previous problem.
(a) Construct the onedimensional fixed point problem of mapping (10.62) and solve it to obtain the equilibrium.
(b) Formulate the KuhnTucker equations and inequalities (10.69).
(c) Formulate the complementarity problem (10.76) in this case.
CHAPTER NOTES

(Economic) Nobel Prize was given only once, in 1994 in the field of game theory. One of the winner was John Nash , who received this honor for his equilibrium concept, which was introduced in 1951 [ 190 ].
Backward induction is a more restrictive equilibrium concept. It was developed by Kuhn and can be found in [ 154 ]. 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 theoremssuch as that of Brouwer [ 33 ], Kakutani [ 135 ], Tarski [ 255 ] are successfully used to prove existence in many game classes. The article [ 194 ] uses the fixed point theorem of Kakutani. The books [ 254 ] and [ 77 ] discuss computer methods for computing fixed points. The most popular existence result is the well known theorem of Nikaido and Isoda [ 194 ].
The Fan inequality is discussed in the book of Aubin [ 15 ]. The KuhnTucker conditions are presented in the book of Martos [ 175 ]. By introducing slack and surplus variables the KuhnTucker conditions can be rewritten as a system of equations. For their computer solutions well known methods are available ([ 254 ] and [ 175 ]).
The reduction of bimatrix games to mixed optimization problems is presented in the papers of Mills [ 183 ] and Shapiro [ 235 ]. The reduction to quadratic programming problem is given in ([ 173 ]).
The method of fictitious play is discussed in the paper of Robinson [ 215 ]. In order to use the Neumann 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 [ 254 ].
The paper of Rosen [ 216 ] introduces diagonally strictly concave games. The computer method to find the equilibria of person concave games is introduced in Zuhovitsky et al. [ 283 ].
The different extensions and generalizations of the classical Cournot model can be found in the books of Okuguchi and Szidarovszky [ 196 ], [ 197 ]. The proof of Theorem 10.20 is given in [ 253 ]. For the proof of Lemma 10.58 see the monograph [ 197 ]. The bisection method is described in [ 254 ]. The paper [ 137 ] contains methods which are applicable to solve nonlinear complementarity problems. The solution of problem (10.80) is discussed in the book of Hadley [ 105 ].
The book of von Neumann and Morgenstern [ 193 ] is considered the classical textbook of game theory. There is a large variety of game theory textbooks (see for example [ 77 ]).