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.

However, 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.

  • 3
    $\begingroup$ 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. $\endgroup$ Feb 3 '13 at 7:46

In 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\}$.

  • 1
    $\begingroup$ 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. $\endgroup$ Feb 3 '13 at 10:49
  • $\begingroup$ 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? $\endgroup$ Feb 3 '13 at 11:00
  • $\begingroup$ 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). $\endgroup$ Feb 3 '13 at 11:05
  • $\begingroup$ @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. $\endgroup$ Feb 4 '13 at 8:24
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 4 '13 at 8:45

Computing Nash equilibria "in general" is a hard problem. You can model it as a complementarity problem (look it up). There are good solvers out there for such problems, a good one I saw many years ago was the PATH solver (search PATH solver for complementarity problems). There may be better solutions these days.

However, in many cases, you can prove that the equilibria has certain structure (see, for example, supermodular games). That structure can simplify things a lot (but it depends on the structure, for supermodular games, things become much easier). Look up papers on computing Nash equilibrium.

The question is also if you need to find just one Nash equilibrium, or all. You can try, like someone mentioned, guessing the support (you can eliminate strictly dominated strategies) and using the fact that in equilibrium each strategy "component/action" yields the same payoff to find the equilibria.

Depending on what you want to do, you may want to find the set of correlated equilibria first (that's easier) and go from there.

As for when Nash equilibria exists, well, check Nash's theorem (there are some stronger existence theorems, especially in some special circumstances, again, check supermodular games for some cool examples). But from Nash's theorem, the sufficient conditions for existence are a compact, convex set of strategies and continuous utility functions.

I'm posting this as a brain dump, so please forgive small inaccuracies.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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