TransWikia.com

How can I build a fixed point theorem argument in pure strategies?

Economics Asked on September 10, 2020

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:Xto 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:Xto 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

2 Answers

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]^2Rightarrow[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 $dbig(BR(a),BR(b)big) = sqrt{2}$ whereas $dbig(a,bbig) = 0.3sqrt{2}$. It is clear that $notexists$ $k>0$ such that $dbig(BR(a), BR(b)big)leq k dbig(a,bbig)$.

Correct answer by Tomcat on September 10, 2020

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.

Answered by induction_is_a_laddah on September 10, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP