纳什均衡存在性：Brouwer , Sperner and Nash

Lecturer: Constantinos Daskalakis

Nash & Brouwer

Brouwer’s Fixed Point Theorm

Fixed Point Theorem [Brouwer’10]

Let f:D→D be a continuous function from a convex and compact (closed and bounded) subset D of the Euclidean space to itself. Then, there exists an x∈D s.t. x=f(x).

这个定理表明：在二维球面上，任意映到自身的一一连续映射，必定至少有一个点是不变的。他把这一定理推广到高维球面。尤其是，在n维球内映到自身的任意连续映射至少有一个不动点。

Existence of Equilibrium in Finite Game [Nash’50]

A Nash equilibrium exists in every finite game.

Brouwer ⇒ Nash

Let f:Δn×Δm→Δn×Δm, and assume f(x,y)→(x′,y′). Define

, and let

From Brouwer’s fixed point theorem, there exist f(x∗,y∗)→(x′,y′)=(x∗,y∗).

We use contradiction to finish this proof.

Assume eTiRy∗>x∗TRy for some i, then GainRi(x∗,y∗)>0⇒0<x∗i<1.

e可以当作单方向向量

Then there must exists i′ s.t. eTi′Ry∗<x∗TRy. Then GainRi′(x∗,y∗)=0 and ∑nk=1GainRi(x,y)>0, so we have x∗i′<x∗i′, which is a contradiction.

Then the assumption is wrong, so GainRi(x∗,y∗)=0  ∀i.

Sperner’s Lemma [Sperner’28]

Color the boundary using three colors in a legal way (no blue for the left edge, no red for the bottom edge, no yellow for the right and above edge). No matter how the internal nodes are colored, there exists a tri-chromatic triangle. In fact an odd number of those.

Sperner ⇒ Brouwer

1. For all ϵ, existence of approximate fixed point |f(x)−x|<ϵ can be shown via Sperner’s lemma.

   Assume D is the set of the points, |D|=n2, and f:D→D, then color the nodes acoording to f(x)−x:

​ From Sperner’s Lemma, there must exist a tri-chromatic triangle.

​ Suppose f:[0,1]2→[0,1]2 , continuous.

Heine-Cantor theorem ⇒ must be uniformly continuous

​ where, d is l∞ norm and we chose some ϵ so that the diameter of cells is δ<δ(ϵ)

Claim : If zY is the yellow corner of a trichromatic triangle, then |f(zY)−zY|∞<ϵ+δ

---

Proof:

Let zY,zR,zB are yellow/red/blue corners of a trichromatic triangle, (f(zY)−zY)x•(f(zB)−zB)x≤0.

|(f(zY)−zY)x|≤|(f(zY)−zY)x−(f(zB)−zB)x|

≤|(f(zY)−f(zB))x|+|zY−zB|≤d(f(zY),f(zB))+d(zY,zB)

≤ϵ+δ

Similarly in y, then we choose δ=min(δ(ϵ),ϵ), we have |f(zY)−zY|∞<2ϵ

---

1. Use compactness:
   
   • pick a sequence of epsilons: ϵi=2−i.i=1,2...
   • define a sequence of triangulations of diameter: δi=min(δ(ϵi),ϵ)
   • pick a trichromatic triangle, call its yellow corner zYi
   • by compactness, this sequence has converging subsequence wi with limit point w∗

Claim: f(w∗)=w∗

---

Proof:

def continuous function g(x)=d(f(x),x) since d and f are continuous

g(wi)→g(w∗),i→+∞

0≤g(wi)≤2−i+1

Thus, g(w)=0. d(f(w∗),w∗)=0⇒f(w∗)=w∗