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$
1
  • 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$ Oct 22, 2017 at 20:40

2 Answers 2

6
$\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$
2
  • $\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$
    – RAGMS
    Oct 23, 2017 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, 2017 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$
7
  • $\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$ Oct 24, 2017 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, 2017 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$ Oct 24, 2017 at 13:43
  • $\begingroup$ @TheoreticalEconomist You are correct, and that was indeed part of the question. It slipped my mind. $\endgroup$
    – Giskard
    Oct 24, 2017 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$
    – RAGMS
    Oct 24, 2017 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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