0
$\begingroup$

To begin with, I am recalling the Banach Fixed Point Theorem.

Let $(X,d)$ be a non-empty complete metric space with a contraction mapping $T:X\to X$. Then $T$ admits a unique fixed-point $x^*$ in $X$ i.e. $T(x^*) = x^*$.

In order to prove that the combinantion of the best response strategies of $N \geqslant 2$ agents consitutes a Nash Equilibrium, we need to use a fixed point theorem argument. Is this necessary only in cases where the agents employ mixed strategies or this holds in the case where they also follow pure strategies? I am searcing for some guidance to use the Banch fixed point theorem in guadratic utility functions when agents act by submitting pure strategies. How can I build this argument? What confuses me the most is that the mapping $T:X\to X$ is about the strategies isn't it?

I can provide more details of my problem if you wish so. I would also be glad if you could answer with great details, since I do not have any idea about the topic

$\endgroup$
17
  • $\begingroup$ From reading your question I indeed do not understand what you are and aren't familiar with. Have you ever seen a fixed point theorem based proof for the existence of a Nash-equilibrium? If yes, that should tell you a lot about what the space $X$ is. If not, read one? Perhaps also clarify what is that you are trying to do, what is your goal? $\endgroup$ – Giskard Jul 31 '20 at 17:32
  • $\begingroup$ Well, this $X$ is a complete metric space as the definition says, but in our case it is the set of the cartesian product of the individual sets of strategies, i.e. if we have three agents that compete, that is $X=S_1\times S_2 \times S_3$, where $S_i$ is the strategy set of agent $i$, isnt it? $\endgroup$ – Nav89 Jul 31 '20 at 18:23
  • 1
    $\begingroup$ I don't really understand whether you want to prove existence of NE in pure strategies for some general case or whether you want to calculate a NE in pure strategies for some class of games? (Or something completely different...) $\endgroup$ – VARulle Jul 31 '20 at 20:02
  • $\begingroup$ I want to prove the existence of NE in pure strategies for a general case $\endgroup$ – Nav89 Jul 31 '20 at 20:21
  • $\begingroup$ What is the pure NE for matching pennies or rock-paper-scissors? $\endgroup$ – Giskard Jul 31 '20 at 21:26
2
$\begingroup$

There is no apriori reason for the Best Response map to be a contraction in general. Here's a simple example (since Battle of Sexes has been my go-to for the past few days): $$ \begin{array}{c|lcr} \text{Player1/Player 2$\rightarrow$} & \text{F} & \text{T} \\ \hline \text{F} & 3,1 & 0,0 \\ \text{T} & 0,0 & 1,3 \\ \end{array} $$ Denote the strategy of player 1: $x = Pr(T)$ and that of player 2 by: $y=Pr(T)$. The best response of player 1 is a map $BR_1:[0,1]\rightarrow[0,1]$ defined by: $ BR_1(y) = \begin{cases} 0 & \text{ if } y<\frac{3}{4}\\ [0,1] & \text{ if } y = \frac{3}{4}\\ 1 & \text{ if } y>\frac{3}{4}\\ \end{cases} $

Similarly, the best response of player 2 is a map $BR_2:[0,1]\rightarrow[0,1]$ defined by: $ BR_2(x) = \begin{cases} 0 & \text{ if } x<\frac{1}{4}\\ [0,1] & \text{ if } x = \frac{1}{4}\\ 1 & \text{ if } x>\frac{1}{4}\\ \end{cases} $

Define the Best Response profile $BR:[0,1]^2\Rightarrow[0,1]^2$ as $BR(y,x) \equiv \big(BR_1(y), BR_2(x)\big)$. A Nash equilibrium of this game is a fixed point of $BR$.

This, however, need not be a contraction map. Take two points on the domain: $a = (0.8,0.5)$ and $b = (0.5,0.2)$. Its easy to see that $BR(0.8,0.5) =(1,1)$ and $BR(0.5,0.2)=(0,0)$. Thus the Euclidean distance $d\big(BR(a),BR(b)\big) = \sqrt{2}$ whereas $d\big(a,b\big) = 0.3\sqrt{2}$. It is clear that $\not\exists$ $k>0$ such that $d\big(BR(a), BR(b)\big)\leq k d\big(a,b\big)$.

$\endgroup$
5
  • $\begingroup$ @Tomcat...ok! In your paradigm it works fine, but it seems to me that nobody takes a look at my comments. Could you please take a look at this link? it is a game palyed in demand schedules...What about this? math.stackexchange.com/questions/3773106/… $\endgroup$ – Nav89 Aug 2 '20 at 16:32
  • $\begingroup$ The fact that the Best Response profile need not be a contraction is not dependent on the "paradigm" used. I checked the other post - the relevant part of the payoff function $g_i(y)= -d_1(y_1)p(y_1,y_2)$. Its not clear the best response will be a contraction even in this case. Is there a proof for this? $\endgroup$ – user28372 Aug 2 '20 at 16:48
  • $\begingroup$ I will do the proff and post it, and I will tell you again, ok? Thanks for the time being! $\endgroup$ – Nav89 Aug 2 '20 at 16:54
  • $\begingroup$ take a look in the link again math.stackexchange.com/questions/3773106/… $\endgroup$ – Nav89 Aug 2 '20 at 23:37
  • $\begingroup$ Well, maybe you are right! Maybe I can not apply the Banch fixed point theorem. Thus, I could take a closer look to see if I can use some other fixed point theorem. But I do not think that I can use the Brouwer's theorem...or maybe not...I am still trying to see what I can do... $\endgroup$ – Nav89 Aug 5 '20 at 15:33
1
$\begingroup$

To prove that that some given combination of strategies is a Nash equilibrium you don't need to use a fixed-point theorem (such as Brouwer's or the fixed-point theorem for contractions on Banach spaces). What you do have to do, is check that they are best responses to one another. This true for mixed and pure strategies.

You also seem to be asking how you can use the Banach fixed-point theorem to prove existence of a pure strategy equilibrium. As @Giskard pointed out, this is doomed to failure without restrictions on the game, as not every game admits a pure strategy equilibrium.

If you wanted to try anyway: Let $S_{i}$ denote $i$'s set of pure strategies. Let $X = \times_{i} S_{i}$ and define $T \colon X \to X$ as follows: $T(x) = (T_{i}(x))_{i}$ where $T_{i}(x)$ is some pure strategy of the best response correspondence of agent $i$ to the strategy profile $x_{-i}$ of the others. (If $T$ is supposed to be a contraction on $X$, then it has to map to $X$, not the power set. Note, however, that this selection is irrelevant if the game happens to be such that best responses are always unique.) A profile of pure strategies is a Nash equilibrium if it is a fixed-point of $T$. Conversely, for every Nash equilibrium $x$, there is a way to define the selection from the correspondence such that $x$ is a fixed-point of the thusly defined mapping $T$.

The difficult in this approach thus lies in finding a selection from the best response correspondence together with a metric such that $X$ is a complete metric space on which $T$ is a contraction.

But this is not possible in general: Not every game admits a pure strategy Nash equilibirum, as pointed out by @Giskard. Not only that: Not every game which does admit such an equilibrium has a unique one (consider the standard coordination game, where best responses are always unique but which has multiple pure strategy equilibria). There is simply no good reason (at least one that I can see) why, without restrictions on the game, best responses would allow you to define a contraction. (But perhaps someone knows a class of games where this is actually the case.)

All of this is to say that there is no existence result for pure strategy Nash equilibria in the generality that you seem to describe. Results for games in which such pure equilibria can be proven to existence abstractly (e.g. via Kakutani's fixed-point theorem) rely on more special features of the game (e.g. in Athey (2001), certain single-crossing properties are key). What tools might be useful to you will depend, to a degree, on the details of your problem.

$\endgroup$
4
  • $\begingroup$ thank you for your answer. Well, I have a problem, where the game is played in the demand scedules, where I parametrie a part of the intercept point in particoular. Within this class of games, that is common way of introducing some strategic behavior in demands, I have not seen to much work of trying to prove the existence, maybe beacause they do not have restrictions? What type of restrictions? On the other hand, I refer to Banach fixed point theorem since I work in $\mathbb{L}^2$. However, I have cited a link of a simplified version of my problem in the commets above $\endgroup$ – Nav89 Aug 2 '20 at 7:35
  • $\begingroup$ I do not know if you are in mood to take a look... $\endgroup$ – Nav89 Aug 2 '20 at 7:37
  • $\begingroup$ Actually, its easy to come up with simple examples where there is a unique pure strategy equilibrium but the Best Response map is not a contraction. eg. take the game in the answer I provided and modify as follows: $o(F,F) = (1,1), o(F,T) = (2,2), o(T,F) = (0,1), o(T,T) = (3,2)$. The Best response is still not a contraction. My conjecture is that the map will be a contraction if the Nash equilibrium is in strictly dominant strategies (then the BR maps are trivially constant functions). $\endgroup$ – user28372 Aug 2 '20 at 18:53
  • $\begingroup$ @Tomcat you can check again the link math.stackexchange.com/questions/3773106/… I have written down the answer $\endgroup$ – Nav89 Aug 3 '20 at 6:29

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.