Algorithmic Game Theory and Applications
Lecture 3: Nash’s Theorem
Kousha Etessami
U. of Edinburgh
Copyright By PowCoder代写 加微信 powcoder
The Point Theorem
We will use the following to prove Nash’s Theorem.
Theorem(Brouwer, 1909) Every continuous function
f : D → D mapping a compact and convex, nonempty subset D ⊆ Rm to itself has a “fixed point”, i.e., there is x∗ ∈ D such that f (x∗) = x∗.
Explanation:
A “continuous” function is intuitively one whose graph has no “jumps”.
For our current purposes, we don’t need to know exactly what “compact and convex” means.
(See the appendix of this lecture for definitions.) We only state the following fact:
FactThesetofprofilesX =X1 ×…×Xn isacompactand convex subset of Rm, where m = Σni=1mi , with mi = |Si |.
Simple cases of Brouwer’s Theorem
To see a simple example of what Brouwer’s theorem says, consider the interval [0,1] = {x | 0 ≤ x ≤ 1}.
[0, 1] is compact and convex. ( [0, 1]n is also compact & convex.)
For a continuous f : [0, 1] → [0, 1], you can “visualize” why the theorem is true. Here’s the “visual proof” in the 1-dimensional
For f : [0, 1]2 → [0, 1]2, the theorem is already far less obvious: “the crumpled sheet experiment”.
brief remarks
Brouwer’s Theorem is a deep and important result in topology.
It is not very easy to prove, and we won’t prove it.
If you are desperate to see a proof, there are many. See, e.g., any of these:
[Milnor’66] (Differential Topology). (uses, e.g., Sard’s Theorem).
[Scarf’67 & ’73, Kuhn’68, Border’89], uses Sperner’s Lemma.
[Rotman’88] (Algebraic Topology). (uses homology, etc.)
[D. Gale’79], possibly my favorite proof: uses the fact that the game of (n-dimensional) HEX is a finite “win-lose” game.
proof of Nash’s theorem
Proof: (Nash’s 1951 proof)
We will define a continuous function f : X → X , where X=X1×…×Xn,andwewillshowthatiff(x∗)=x∗ then x∗ = (x1∗, . . . , xn∗) must be a .
By Brouwer’s Theorem, we will be done.
(In fact, it will turn out that x∗ is a if and
only if f (x∗) = x∗.) We start with a claim.
Claim: A profile x∗ = (x1∗, . . . , xn∗) ∈ X is a if and only if, for every player i, and every pure strategy πi,j,
U(x∗)≥U(x∗ ;π ). i i −i i,j
Proof of claim: If x∗ is a NE then, it is obvious by definition that Ui(x∗) ≥ Ui(x∗ ,πi,j).
For the other direction: by calculation it is easy to see that for
any mixed strategy xi ∈ Xi , mi
U(x∗ ;x)=x(j)∗U(x∗ ;π ) i−ii i i−ii,j
By assumption, Ui(x∗) ≥ Ui(x∗ ;πi,j), for all j.
So, clearly Ui(x∗) ≥ Ui(x∗ ;xi), for any xi ∈ Xi, because
Ui(x∗ ;xi)=mi xi(j)∗Ui(x∗ ;πi,j)≤mi xi(j)∗Ui(x∗)=
−i j=1 −i j=1 Ui(x∗).
Hence, each x∗ is a best response strategy to x∗ . In other i −i
words, x∗ is a .
So, rephrasing our goal, we want to find x∗ = (x1∗,…,xn∗) such that
i.e., such that
U(x∗ ;π )≤U(x∗) i −i i,j i
U(x∗ ;π )−U(x∗)≤0 i −i i,j i
for all players i ∈ N, and all j = 1,…,mi.
For a mixed profile x = (x1,x2,…,xn) ∈ X: let
φi ,j (x ) = max{0, Ui (x−i ; πi ,j ) − Ui (x )}
Intuitively, φi,j(x) measures “how much better off” player i would be if he/she picked πi,j instead of xi (and everyone else remained unchanged).
Define f : X → X as follows: For x = (x1,x2,…,xn) ∈ X, let f(x) = (x1′,x2′,…,xn′)
where for all i, and j = 1,…,mi,
′ xi(j)+φi,j(x)
xi (j) = 1 + mi φi,k(x) k=1
1. Ifx∈X,thenf(x)=(x1′,…,xn′)∈X.
2. f : X → X is continuous. (These facts are not hard to check.)
Thus, by Brouwer, there exists x∗ = (x1∗, x2∗, . . . , xn∗) ∈ X such that f (x∗) = x∗.
Nowwehavetoshowx∗ isaNE.
For each i, and for j = 1,…,mi,
∗ xi∗(j)+φi,j(x∗)
xi (j)=1+mi φi,k(x∗) k=1
xi∗ (j )(1 + φi ,k (x ∗ )) = xi∗ (j ) + φi ,j (x ∗ )
xi∗(j)φi,k(x∗) = φi,j(x∗)
We will show that in fact this implies φi,j(x∗) must be equal to 0 for all j.
Claim: For any mixed profile x, for each player i, there is some j such that xi(j) > 0 and φi,j(x) = 0.
Proof of claim: For any x ∈ X,
φi ,j (x ) = max{0, Ui (x−i ; πi ,j ) − Ui (x )}
Since Ui(x) is the “weighted average” of Ui(x−i;πi,j)’s, based on the “weights” in xi , there must be some j used in xi , i.e., with xi(j) > 0, such that Ui(x−i;πi,j) is no more than the weighted average. I.e.,
Ui(x−i;πi,j) ≤ Ui(x) Ui (x−i ; πi ,j ) − Ui (x ) ≤ 0
Therefore,
φi ,j (x ) = max{0, Ui (x−i ; πi ,j ) − Ui (x )} = 0
Thus, for such a j, xi∗(j) > 0 and
xi∗(j)φi,k(x∗) = 0 = φi,j(x∗)
But, since φi,k(x∗)’s are all ≥ 0, this means φi,k(x∗) = 0 for
all k = 1,…,mi. Thus, for all players i, and for j = 1,…,mi, U(x∗)≥U(x∗ ;π )
i i −i i,j Q.E.D. (Nash’s Theorem)
Infact,sinceUi(x∗)=mi x∗(j)·Ui(x∗ ;πi,j)isthe j=1 i −i
“weighted average” of Ui(x∗ ,πi,j)’s, we see that: −i
Useful Corollary for :
Ui(x∗) = Ui(x∗ ,πi,j), whenever x∗(j) > 0. −i i
Rephrased: In a x∗, if xi∗(j) > 0 then Ui(x∗ ;πi,j) = Ui(x∗); i.e., each such πi,j is itself a “best
response” to x∗ .
This is a subtle but very important point. It will be useful later
when we want to compute NE’s.
The proof using Brouwer gives ostensibly no clue how to compute a . It just says it exists!
We will come back to the question of computing in general games later in the course.
We start next time with a special case: 2-player zero-sum games (e.g., of the Rock-Paper-Scissor’s variety). These have an elegant theory (von Neumann 1928), predating Nash.
To compute solutions for 2p-zero-sum games, Linear Programming will come into play.
Linear Programming is a very important tool in algorithms and optimization. Its uses go FAR beyond solving zero-sum games. So it will be a good opportunity to learn about LP.
NE need not be “Pareto optimal”
Given a profile x ∈ X in an n-player game, the “(purely utilitarian) social welfare” is: U1(x) + U2(x) + . . . + Un(x). A profile x ∈ X is pareto efficient (a.k.a., pareto optimal) if there is no other profile x′ such that Ui(x) ≤ Ui(x′) for all players i, and Uk(x) < Uk(x′) for some player k.
Note: The Prisoner’s Dilemma game shows NE need not optimize social welfare, nor be Pareto optimal.
Indeed, there is a unique NE, (Defect, Defect), and it neither optimizes social welfare nor is Pareto optimal, because (Cooperate, Cooperate) gives a higher payoff to both players.
application in biology: evolution as a game
One way to view how we might “arrive” at a Nash equilibrium is through a process of evolution.
Smith (1972-3,’82) introduced game theoretic ideas into evolutionary biology with the concept of an Evolutionarily Stable Strategy.
Your extra reading (for fun) is from Straffin(1993) which gives an amusing introduction to this.
Intuitively, a mixed strategy can be viewed as percentages in a population that exhibit different behaviors (strategies).
Their behaviors effect each other’s survival, and thus each strategy has a certain survival value dependent on the strategy of others.
The population is in “evolutionary equilibrium” if no “mutant” strategy could invade it and “take over”.
Large population of same “species”, each behaving as either “hawk” or “dove”.
What proportions will behaviors eventually stabilize to (if at all)?
Definition of ESS
Definition: A 2-player game is symmetric if S1 = S2, and for all s1, s2 ∈ S1, u1(s1, s2) = u2(s2, s1).
Definition: In a 2p-sym-game, mixed strategy x1∗ is an Evolutionarily Stable Strategy (ESS), if:
1. x1∗ is a best response to itself, i.e., x∗ = (x1∗,x1∗) is a symmetric , &
2. If x1′ ̸= x1∗ is another best response to x1∗, then U1(x1′ , x1′ ) < U1(x1∗, x1′ ).
Nash (1951, p. 289) also proves that every symmetric game has a symmetric NE, (x1∗,x1∗). (However, not every symmetric game has a ESS.)
A little justification of the definition of ESS
Suppose x1∗ is an ESS. Consider the “fitness function”, F(x1), for a “mutant” strategy x1′ that “invades” (becoming a small
ε > 0 fraction of) a current ESS population, x1∗. Then, Claim:
F (x1′ ) =. (1 − ε)U1(x1′ , x1∗) + εU1(x1′ , x1′ ) (1) < (1−ε)U1(x1∗,x1∗)+εU1(x1∗,x1′)=. F(x∗) (2)
Proof: if x1′ is a best response to the ESS x1∗, then
U1(x1′ , x1∗) = U1(x1∗, x1∗) and U1(x1′ , x1′ ) < U1(x1∗, x1′ ), and since we assume ε > 0, the strict inequality in (2) follows. If on the other hand x1′ is not a best response to x1∗, then
U1(x1′ , x1∗) < U1(x1∗, x1∗), and for a small enough ε > 0, we have (1 − ε)(U1(x1∗, x1∗) − U1(x1′ , x1∗)) > ε(U1(x1∗, x1′ ) − U1(x1′ , x1′ )). Thus again, the strict inequality in (2) follows.
So, an ESS x1∗ is “strictly fitter” than any other strategy, when it is already dominant in the society. This is the sense in which it is “evolutionarily stable”.
Does an ESS necessarily exist?
As mentioned, Nash (1951) already proved that every symmetric game has a symmetric NE (x∗,x∗).
However, not every symmetric game has a ESS. Example: Rock-paper-scissors:
(0, 0) (−1, 1) (1, −1)
(1, −1) (0, 0) (−1, 1)
(−1, 1) (1, −1)
Obviously, s = (1/3, 1/3, 1/3) is the only NE. But it is not an ESS: any strategy is a best reponse to s, including the pure strategy s1 (rock). We have payoff
U(s1,s1) = 0 = U(s,s1), so s is not an ESS.
But many games do have an ESS. For example, in the Hawk-Dove game, (5/8, 3/8) is an ESS.
Even when a game does have an ESS, it is not at all obvious how to find one.
How hard is it to detect an ESS?
It turns out that even deciding whether a 2-player symmetric game has an ESS is hard. It is both NP-hard and coNP-hard, and contained in ΣP2 :
K. Etessami & A. Lochbihler, “The computational complexity of Evolutionarily Stable Strategies”, International Journal of Game Theory, vol. 31(1), pp. 93–113, 2008.
(And, more recently, it has been shown ΣP2 -complete, see: V. Conitzer, “The exact computational complexity of Evolutionary Stable Strategies”, in Proceeding of Web and Internet Economics (WINE), pages 96-108, 2013. )
For simple 2 × 2 2-player symmetric games, there is a simple way to detect whether there is an ESS, and if so to compute one (described in the reading from Straffin).
There is a huge literature on ESS and “Evolutionary Game Theory”. See, e.g., the book: J. Weibull, Evolutionary Game Theory, 1997.
Appendix: continuity, compactness, convexity
Definition For x , y ∈ Rn , dist(x , y ) = ni =1 (x (i ) − y (i ))2 denotes the Euclidean distance between points x and y.
A function f : D ⊆ Rn → Rn is continuous at a point x ∈ D if for all ε > 0, there exists δ > 0, such that for all y ∈ D: if
dist(x , y ) < δ then dist(f (x ), f (y )) < ε.
f is called continuous if it is continuous at every point x ∈ D. Definition A set K ⊆ Rn is convex if for all x,y ∈ K and all λ∈[0,1], λx+(1−λ)y∈K.
FactAsetK⊆Rn iscompactifandonlyifitisclosedand bounded. (So, we need to define “closed” and “bounded”.) Definition A set K ⊆ Rn is bounded iff there is some non-negative integer M, such that K ⊆ [−M,M]n.
(i.e., K “fits inside” a finite n-dimensional box.)
Definition A set K ⊆ Rn is closed iff for all sequences x0,x1,x2,..., where xi ∈ K for all i, such that x = limi→∞ xi for some x ∈ Rn, then x ∈ K. (In other words, if a sequence of points is in K then its limit (if it exists) must also be in K.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com