Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm taking my first (graduate-level) game theory class. I understand how to find Nash equilibria in simple games, such as those given in finite tables, and can see (usually) how to find the mixed equilibria in those cases, but most of our problems have been discussing continuous games such as auctions, firm pricings with continuous prices, etc. Is there a good method of knowing when there exist and finding the mixed Nash equilibria in such cases? The pure equilibria are generally easy to find, but the only thing I can think of in most cases is to check uniform distributions over all possibilities.

share|improve this question
2  
There is no really general method. What is usual done is that you guess the support of the strategies, plug in the condition that everything in the support should give the same payoff and hope that you can solve the resulting functional equations. –  Michael Greinecker Feb 3 '13 at 7:46

1 Answer 1

Ing general, when you face with the problem of finding mixed Nash equilibrium in a 2-player game, you must use the best response functions (BRF). With the BRFs you can solve both finite table games and continuous game.

Let $S_1$ and $S_2$ be the sets of strategies for player 1 and 2 respectively, and let $x_1 \in S_1$ and $x_2 \in S_2$ the strategies played by each player. The payoff functions are $f_1(x_1, x_2)$ for player 1 and $f_2(x_1,x_2)$ for player 2.

The BRF of the player 1 $\beta_1(x_2)$ is a "function" which return the best strategy(ies) that player 1 must choose when player 2 plays a given strategy $x_2$. It is a "function" since for every $x_2$ there can be more than one best strategy for player 1. It is more correct to say that $\beta_1(x_2)$ is a set. The same construction is used for $\beta_2(x_1)$. Namely we have the following:

$$ \beta_1(x_2) = \{ x_1 \in S_1 : f_1(x_1,x_2) \geq f_1(y, x_2) ~ \forall y \in S_1\}$$ $$ \beta_2(x_1) = \{ x_2 \in S_2 : f_2(x_1,x_2) \geq f_2(x_1, z) ~ \forall z \in S_2\}$$

Once you have build the BRFs, you have to solve the following system:

$$ \left\{ \begin{array}{l} x_1^* \in \beta_1(x_2^*) \\ x_2^* \in \beta_2(x_1^*) \end{array}\right.$$

All the solutions $(x_1^*, x_2^*)$ are Nash equilibria. They can be mixed or pure.


Example with continuous strategies

A classical example is the Cournout duopoly. Two firms produce the same good and they act on the same market. They must decide the quantities $x_1$ and $x_2$ of good that they have to produce. Produced quantities must not be greater than the demand $D$. We have that $S_1 = S_2 = [0, D]$.
The firms are different in the sense that they have different cost of production (say $c_1$ and $c_2$ are the unitary cost for firm 1 and firm 2 respectively). Payoff functions are:

$$f_1(x_1,x_2) = k(D - x_1 - x_2)x_1 - c_1x_1$$ $$f_2(x_1,x_2) = k(D - x_1 - x_2)x_2 - c_2x_1$$

where $k$ is a positive constant.

The way to evaluate the BRF is to maximize the payoff functions w.r.t. own strategy when the opponent strategy is fixed. We use the derivative to maximize (note that, since $k>0$, then each payoff function has second derivative negative and this guarantees that the stationary point is a local maximum):

$$\frac{\partial f_1}{\partial x_1} = k(D - x_2) - 2kx_1 - c_1$$ $$\frac{\partial f_2}{\partial x_2} = k(D - x_1) - 2kx_2 - c_2$$

and we equate them to 0 in order to find the maximum:

$$ \left\{ \begin{array}{l} \frac{\partial f_1}{\partial x_1} = 0 \Rightarrow x_1 = \frac{k(D-x_2)-c_1}{2k} = \beta_1(x_2) \\ \frac{\partial f_2}{\partial x_2} = 0 \Rightarrow x_2 = \frac{k(D-x_1)-c_2}{2k} = \beta_2(x_1) \end{array}\right.$$

The last equations on the right holds since, for every $x_2$ ($x_1$) fixed we can find the best $x_1$ ($x_2$) that firm 1 (2) can adopt. It is worthwhile to note that in this case the BRFs are real function, since there is a 1-on-1 correspondence between an opponent strategy and the best response to it.

At this point, we can solve the system:

$$ \left\{ \begin{array}{l} x_1* = \beta_1(x_2^*) \Rightarrow x_1^* = \frac{kD-2c_1+c_2}{3k} \\ x_2* = \beta_2(x_1^*) \Rightarrow x_2^* = \frac{kD-2c_2+c_1}{3k} \end{array}\right.$$

and you obtain the Nash equilibrium!


About the usage of BRF with finite table games

When you are in this case, you have $2$ payoff matrix, say $A, B \in \mathbb{R}^{2 \times 2}$. From these you can build you payoff functions:

$$f_1(x_1,x_2) = [x_1 ~~~(1-x_1)]~A~[x_2 ~~~(1-x_2)]^T$$ $$f_2(x_1,x_2) = [x_1 ~~~(1-x_1)]~B~[x_2 ~~~(1-x_2)]^T$$

At this point, you act as in the previous example. Note that $S_1 = S_2 = [0, 1]$ instead of $\{0, 1\}$ because you have to extend to a continuous situation if you want to find the mixed equilibria.

In this case, when you use the BRF, you will find (if there exists at least one) mixed Nash equilibria. Some times it will find also pure equilibria, but in general you have to restrict the maximization on the border of the set $\Delta = \{ (x_1, x_2) : x_1, x_2 \in [0, 1] \wedge x_1+x_2 = 1\}$.

share|improve this answer
1  
I don't see the point of your Cournot example. There you have a single-valued best response and an equilibrium in pure strategies. At a nondegenerate mixed strategy equilibrium, best replies can never be single-valued. As for the rest, you just restated that NE are fxed points of the BR correspondence. Since this does not tell you how to find fixed points, this is of little help. –  Michael Greinecker Feb 3 '13 at 10:49
    
Sorry, I got it late... I think I understand your point of view. You are saying that finding fixed point is not in general a trivial task, that's right? –  the_candyman Feb 3 '13 at 11:00
    
The set of mixed best replies to a profile is always the convex hull of the pure best replies in finite games. For games with a continuum of strategies, essentially the same holds true (almost all pure strategies in your support have to be best responses). –  Michael Greinecker Feb 3 '13 at 11:05
    
@MichaelGreinecker ok, but I still don't get the point. I proposed the use of BRF as a method for finding Nash Equilibria. It's clear that there is no standard way to determinate a BRF and it is also clear that there are no standard techniques to find out the way to achieve a larger knowledge of the game you are facing with and hence you can find NE more easily I think. –  the_candyman Feb 4 '13 at 8:24
1  
You restated the definition of NE, but this does not give rise to any way of finding NE. And your example does not adres OPs question. –  Michael Greinecker Feb 4 '13 at 8:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.