Lecture VI:Existence of Nash equilibrium
Markus M.M¨o bius
新内飞鸟February26,2008
•Osborne,chapter4
质量月报•Gibbons,ctions1.3.B
1Nash’s Existence Theorem
When we introduced the notion of Nash equilibrium the idea was to come up with a solution concept which is stronger than IDSDS.Today we show that NE is not too strong in the n that it guarantees the existence of at least one mixed Nash equilibrium in most games(for sure in allfinite games). This is reassuring becau it tells that there is at least one way to play most games.1
Let’s start by stating the main theorem we will prove:
Theorem1(Nash Existence)Everyfinite strategic-form game has a mixed-strategy Nash equilibrium.
Many game theorists therefore regard the t of NE for this reason as the lower bound for the t of reasonably solution concept.A lot of rearch has gone into refining the notion of NE in order to retain the existence result but get more preci predictions in games with multiple equilibria(such as coordination games).
However,we have already discusd games which are solvable by IDSDS and hence have a unique Nash equilibrium as well(for example,the two thirds of the average game),but subjects in an experiment will not follow tho equilibrium prescription.Therefore,if we want to describe and predict 1Note,that a pure Nash equilibrium is a(degenerate)mixed equilibrium,too.
1
the behavior of real-world people rather than come up with an explanation of how they should play a game,then the notion of NE and even even IDSDS can be too restricting.
Behavioral game theory has tried to weaken the joint assumptions of rationality and common knowledge in order to come up with better theories of how real people play real games.Anyone interested should take David Laibson’s cour next year.
Despite the rervation about Nash equilibrium it is still a very uful benchmark and a starting point for any game analysis.
In the following we will go through three proofs of the Existence Theorem using various levels of mathematical sophistication:
•existence in2×2games using elementary techniques古诗手抄报
•existence in2×2games using afixed point approach
•general existence theorem infinite games
You are only required to understand the simplest approach.The rest is for the intellectually curious.
2Nash Existence in2×2Games
Let us consider the simple2×2game which we discusd in the previous
equilibria:
lecture on mixed Nash
2
Let’s find the best-respon of player 2to player 1playing strategy α:
u 2(L,αU +(1−α)D )=2−α
u 2(R,αU +(1−α)D )=1+3α(1)
Therefore,player 2will strictly prefer strategy L iff2−α>1+3αwhich implies α<14.The best-respon correspondence of player 2is therefore:BR 2(α)=⎧⎨⎩1if α<14[0,1]if α=140if α>14
(2)We can similarly find the best-respon correspondence of player 1:
BR 1(β)=⎧⎨⎩0if β<23[0,1]if β=231if β>23(3)
We draw both best-respon correspondences in a single graph (the graph is in color -so looking at it on the computer screen might help you):
We immediately e,that both correspondences interct in the single point α=14and β=23which is therefore the unique (mixed)Nash equilibrium of the game.
3
What’s uful about this approach is that it generalizes to a proof that any two by two game has at least one Nash its two best respon correspondences have to interct in at least one point.
An informal argument runs as follows:
1.The best respon correspondence for player2maps eachαinto at
五开头的四字成语
least oneβ.The graph of the correspondence connects the left and right side of the square[0,1]×[0,1].This connection is continuous -the only discontinuity could happen when player2’s best respon switches from L to R or vice versa at someα∗.But at this switching point player2has to be exactly indifferent between both strategies-hence the graph has the value BR2(α∗)=[0,1]at this point and there cannot be a discontinuity.Note,that this is precily why we need mixed strategies-with pure strategies the BR graph would generally be discontinuous at some point.
2.By an analogous argument the BR graph of player1connects the upper
and lower side of the square[0,1]×[0,1].
3.Two lines which connect the left/right side and the upper/lower side
of the square respectively have to interct in at least one point.Hence each2by2game has a mixed Nash equilibrium.
3Nash Existence in2×2Games using Fixed Point Argument
There is a different way to prove existence of NE on2×2games.The advantage of this new approach is that it generalizes easily to generalfinite games.
Consider any strategy profile(αU+(1−α)D,βL+(1−β)R)reprented by the point(α,β)inside the square[0,1]×[0,1].Now imagine the following: player1assumes that player2follows strategyβand player2assumes that player1follows strategyα.What should they do?They should play their BR to player1should play BR1(β)and player2should play BR2(α).So we can imagine that the strategy profile(α,β)is mapped onto(BR1(β),BR2(α)).This would describe the actual play of both players if their beliefs would be summarizes by(α,β).We can therefore define a
4
giant correspondence BR:[0,1]×[0,1]→[0,1]×[0,1]in the following way:
BR(α,β)=BR1(β)×BR2(α)(4) The followingfigure illustrates the properties of the combined best-respo
n map BR:
The neat fact about BR is that the Nash equilibriaσ∗are precily the fixed points of σ∗∈BR(σ∗).In other words,if players have beliefs σ∗thenσ∗should also be a best respon by them.The next lemma follows
顶成语
directly from the definition of mixed Nash equilibrium:
Lemma1A mixed strategy profileσ∗is a Nash equilibrium if and only if it is afixed point of the BR σ∗∈BR(σ∗).
We therefore look precily for thefixed points of the correspondence BR which maps the square[0,1]×[0,1]onto itlf.There is well developed mathematical theory for the types of maps which we utilize to prove Nash hat BR has at least onefixed point).
3.1Kakutani’s Fixed Point Theorem
The key result we need is Kakutani’sfixed point theorem.You might have ud Brower’sfixed point theorem in some mathematics class.This is not
5
冬至>法甲在哪里看直播sufficient for proving the existence of nash equilibria becau it only applies to functions but not to correspondences.
Theorem2Kakutani A correspondence r:X→X has afixed point x∈X such that x∈r(x)if
成语游戏大全1.X is a compact,convex and non-empty subt of n.
2.r(x)is non-empty for all x.
3.r(x)is convex for all x.
4.r has a clod graph.
There are a few concepts in this definition which have to be defined: Convex Set:A t A⊆ n is convex if for any two points x,y∈A the straight line connecting the two points lies inside the t as well.Formally,λx+(1−λ)y∈A for allλ∈[0,1].
Clod Set:A t A⊆ n is clod if for any converging quence {x n}∞n=1with x n→x∗as n→∞we have x∗∈A.Clod intervals such as[0,1]are clod ts but open or half-open intervals are not.For example
(0,1]cannot be clod becau the quence1
n converges to0which is not in
the t.
Compact Set:A t A⊆ n is compact if it is both clod and bounded.
For example,the t[0,1]is compact but the t[0,∞)is only clod but unbounded,and hence not compact.
Graph:The graph of a correspondence r:X→Y is the t{(x,y)|y∈r(x)}. If r is a real function the graph is simply the plot of the function.
Clod Graph:A correspondence has a clod graph if the graph of the correspondence is a clod t.Formally,this implies that for a quence of point on the graph{(x n,y n)}∞n=1such that x n→x∗and y n→y∗as n→∞
we have y∗∈r(x∗).2
It is uful to understand exactly why we need each of the conditions in Kakutani’sfixed point theorem to be fulfilled.We discuss the conditions by looking correspondences on the real : → .In this ca,afixed point simply lies on the interction between the graph of the correspondence
and the diagonal y=x.Hence Kakutani’sfixed point theorem tells us that 2If the correspondence is a function then the clod graph requirement is equivalent to assuming that the function is continuous.It’s easy to e that a continuous function has
a clod graph.For the rever,you’ll need Baire’s category theorem.
6
