4
$\begingroup$

How can one use Brouwer's Fixed Point Theorem to prove that the following game F has a solution:

F is defined as N={L,R} Ai=(g,1-g) where g must be positive and smaller than 1, that is, each player plays a completely mixed strategy and has the following payoff matrix:

\begin{array}{|c|c|c|} \hline &LU&LD\\\hline RU&0,0&6,3\\\hline RD&3,6&0,0\\\hline \end{array}

I reached the conclusion that one cannot use such theorem to prove there exists a solution to the game since the plays do not belong to a compact set. Can anyone use it?

$\endgroup$
  • 2
    $\begingroup$ This question seems rather odd. Why would you use Brouwer to demonstrate the existence of a completely mixed equilibrium when, as you point out, the space of completely mixed strategies is not compact, and the existence of a completely mixed equilibrium is easy enough to demonstrate by construction? $\endgroup$ – Theoretical Economist Oct 22 '17 at 20:40
4
$\begingroup$

Rather than deprive you of the joy of solving your own problem, I will show how one can also use Brouwer's theorem to show that the function $f:\mathbb{R} \to \mathbb{R}$ $$ f(x) = \frac{33+x}{16+x^4} $$ has a fixed point, even though its range is not compact.

Note that $f(1) = 2$ and $f(2) = 35/32$. As $f$ is monotonically decreasing over $[1,2]$, this also means that $f([1,2]) \subset [1,2]$. Also, $[1,2]$ is compact and $f$ is continuous over this set. So $f: [1,2] \to [1,2]$ will have a fixed point by Brouwer's fixed point theorem.

Similar tricks are used in game theory and general equilibrium theory. By showing that the optimal decisions by some players cannot possibly be outside of some boundaries one can frequently create a compact space over which fixed point theorems are applicable.

$\endgroup$
  • $\begingroup$ Thank you for the input, although, I am familiar with such reasoning. My problem here is one cannot set a priori restrictions without knowing the completely mixed strategy equilibrium indeed exists, giving no point to the use of the theorem... $\endgroup$ – Ramiro Oct 23 '17 at 9:47
  • 1
    $\begingroup$ @Ramiro Yes, the easy to see equilibrium is difficult to ignore. You can define some sort of $g$-best response which assigns at least probability $g$ to all strategies. (E.g. g = 5%.) Trivially this maps the $[g,1-g]^2$ subset of the mixed strategy space unto itself, so it has a fixed point. Then all you have to show is that the fixed point is not at the boundary. If the fixed point is indeed in the interior than the $g$-best response is also a best response. $\endgroup$ – Giskard Oct 23 '17 at 10:03
0
$\begingroup$

Just wanted to add that in general, you can show this holds for any finite two-player game. I will not repeat the proof, as it is easily found online (e.g. this one). It is also worth nothing that you can prove this result with other fixed point theorems. The most notable example is probably Kakutani's fixed point theorem, where the existence of NE is proven with correspondences (see Fudenberg and Tirole).

Just thought you might want to know if you are looking more into this!

$\endgroup$
  • $\begingroup$ Bear in mind that the OP is asking about guaranteeing the existence of equilibria in completely mixed strategies. The results you refer do not seem to apply, since they only guarantee the existence of some equilibrium (which may we’ll be pure). $\endgroup$ – Theoretical Economist Oct 24 '17 at 7:31
  • $\begingroup$ @TheoreticalEconomist I am quite sure that for any finite game there will also be a fixed point over the restricted mixed strategy place the OP is asking about. E.g. for Prisoner's Dilemma it would be $(g,g)$, as lower probabilites of cooperation are not allowed. $\endgroup$ – Giskard Oct 24 '17 at 13:39
  • 1
    $\begingroup$ @denesp That is true, but in general I believe there is no way to guarantee that the equilibria of the restricted game (where players are required to play all strategies with positive probability) are also equilibria of the original game. $\endgroup$ – Theoretical Economist Oct 24 '17 at 13:43
  • $\begingroup$ @TheoreticalEconomist You are correct, and that was indeed part of the question. It slipped my mind. $\endgroup$ – Giskard Oct 24 '17 at 14:18
  • $\begingroup$ Exactly, the problem is one cannot guarante, without further restrictions on utility functions, using proofs like those of Nash Theorem, that the fixed point exists in completely mixed strategies. $\endgroup$ – Ramiro Oct 24 '17 at 19:26

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.