Zagadnienia

4.1 Preliminaria matematyczne
4.2 Odwzorowania najlepszej odpowiedzi
4.3 Twierdzenie Nasha
4.4 Uogólnienia Twierdzenia Nasha

4. Twierdzenia o istnieniu Równowagi Nasha

4.1. Preliminaria matematyczne

Odwzorowania (funkcje wielowartościowe) ze zbioru X w Y, czyli funkcje

$\gamma:X\rightarrow 2^{Y}$

będziemy oznaczać $\gamma:X\Longrightarrow Y.$

Definicja 4.1

Wykres odwzorowania $\gamma:E\Longrightarrow F,\ E,F\subset\Re^{m}$ jest to zbiór

$Gr\ \gamma:=\{(x,y)\in E\times F:y\in\gamma(x)\}$

Definicja 4.2

Odwzorowanie $\gamma:E\Longrightarrow F,\ E,F\subset\Re^{m}$ jest domknięte w $x$ jeżeli

$(x^{n}\rightarrow x,\ y^{n}\rightarrow y,\ y^{n}\in\gamma(x^{n}))\Rightarrow y\in\gamma(x).$

Odwzorowanie $\gamma$ jest domknięte jeżeli jest domknięte w każdym punkcie swojej dziedziny, czyli jeżeli jego wykres, $Gr\ \gamma$ jest domknięty.

Przykład 4.1

Odwzorowanie $\gamma(x):=(0,1),\ x\in\Re$ nie jest domknięte w $x_{0}=1$ . Weźmy bowiem ciąg $x^{n}$ taki że $x^{n}\rightarrow 1,$ oraz ciąg $y^{n}\in\gamma(x^{n})=(0,1)$ taki że $y^{n}\rightarrow y:=1.$ Mamy więc $y\notin\gamma(x_{0}).$

Odwzorowanie $\gamma(x):=\{ 0\}$ dla $x=0,\ \ \{ 1/x\}$ dla $x\in\Re\backslash\{ 0\}$ jest domknięte.

Przykład 4.2

Nieciągła funkcja $f:[0,1]\rightarrow[0,1]:f(x)=x+1/4\ dla\ x\in[0,1/3),\ f(x)=x-1/4\ dla\ x\in[1/3,1]$ nie ma punktu stałego. Jeżeli przyjmiemy jednak że wartościami $f$ są zbiory, definiując np.

$\tilde{f}(1/3)=[2/12,7/12],\ \tilde{f}(x)=\{ f(x)\},\ x\in[0,1]\backslash\{ 1/3\},$

to dla tak określonego odwzorowania $\tilde{f}$ istnieje $x\in[0,1]:x\in\tilde{f}(x)$ . W naszym przykładzie oczywiście $x=1/3$ .

Do dowodu twierdzenia o istnieniu RN będzie nam potrzebne uogólnienie twierdzenia Brouwera na odwzorowania. Ogólnie, niech $K$ - dowolny zbiór.

Definicja 4.3

Odwzorowanie $\Psi:K\Longrightarrow K$ ma punkt stały $x\in K$ jeśli $x\in\Psi(x)$

Twierdzenie 4.1 (Kakutani, 1941)

Niech $X$ - niepusty, zwarty, wypukły podzbiór n-wymiarowej przestrzeni euklidesowej $\Re^{n}$ , $f:X\Longrightarrow X$ -odwzorowanie t. że

1. $\forall x\in X$ zbiór $f(x)$ jest niepusty i wypukły (mówimy że odwzorowanie $f$ jest wypukłe).

2. Wykres $f$ jest domknięty [i.e. dla wszystkich ciągów $x^{n},y^{n}$ takich że $x^{n}\rightarrow x,\ y^{n}\rightarrow y,\ y^{n}\in f(x^{n}),$ zachodzi $y\in f(x)$ ].

Wtedy odwzorowanie $f$ ma punkt stały (i.e. $\exists x\in X:x\in f(x).)$

Twierdzenie Kakutaniego jest uogólnieniem na odwzorowania twierdzenia Brouwera o punkcie stałym.

4.2. Odwzorowania najlepszej odpowiedzi

W dalszych rozważaniach istotną rolę będą grały zbiory i odwzorowania najlepszych odpowiedzi. W ogólności zbiory takie mogą być puste lub zawierać wiele elementów. Podamy wpierw odpowiednie definicje dla strategii czystych, a nastepnie uogólnimy powyższe pojęcia dla strategii mieszanych.

Definicja 4.4

Dla każdego podprofilu $a_{{-i}}\in A_{{-i}},\ i\in N$ zbiór

$B_{i}(a_{{-i}})=\{ a_{i}\in A_{i}:u_{i}(a_{i},a_{{-i}})\ge u_{i}(\tilde{a}_{i},a_{{-i}})\ \forall\tilde{a}_{i}\in A_{i}\}$

nazywamy zbiorem najlepszych odpowiedzi gracza $i$ na podprofil $a_{{-i}}$ .

Odwzorowanie $B_{i}:A_{{-i}}\rightarrow 2^{{A_{i}}}$ nazywamy odwzorowaniem najlepszej odpowiedzi (best reply correspondence) gracza $i$ . Jego wartościami są podzbiory zbioru $A_{i}$ strategii czystych gracza $i.$

Odwzorowanie $B:A\rightarrow\times 2^{{A_{i}}},i\in N$ zdefiniowane wzorem

$B(a)=\times B_{i}(a_{{-i}}),\ i\in N$

nazywamy odwzorowaniem najlepszej odpowiedzi gry strategicznej GS.

Za pomocą odwzorowań $B_{i},\ i=1,...n$ oraz $B$ uzyskujemy równowane z wyjściową definicje RN.

Definicja 4.5

RN (w strategiach czystych) jest to profil $a^{*}=(a_{1}^{*},...,a_{N}^{*})$ taki że

$\forall i\in N\ \ a_{i}^{*}\in B_{i}(a_{{-i}}^{*})$

lub krócej

$a^{*}\in B(a^{*})$

Przykład 4.3

$\$ W grze o macierzy wypłat

	L	M
T	1,1	1,0
B	1,0	0,1

mamy

$B_{1}(L)=\{ T,B\},\ B_{1}(M)=\{ T\},\ B_{2}(T)=\{ L\},\ B_{2}(B)=\{ M\},$

$B(a^{*})=B((a_{1}^{{*}},a_{2}^{{*}}))=B_{1}(a_{2}^{{*}})\times B_{2}(a_{1}^{{*}})$

Zbiór RN (w strategiach czystych) to zbiór

$\{(a_{1}^{*},a_{2}^{*}):a_{1}^{*}\in B_{1}(a_{2}^{*})\wedge a_{2}^{*}\in B_{2}(a_{1}^{*})\}=\{(T,L)\}.$

Dla strategii mieszanych odpowiednie definicje mają postać:

Definicja 4.6

Dla każdego podprofilu $\sigma _{{-i}}\in\Sigma _{{-i}},\ i\in N$ zbiór

$B_{i}(\sigma _{{-i}})=\{\sigma _{i}\in\Sigma _{i}:u_{i}(\sigma _{i},\sigma _{{-i}})\ge u_{i}(\tilde{\sigma}_{i},\sigma _{{-i}})\ \forall\tilde{\sigma}_{i}\in\Sigma _{i}\}$

nazywamy zbiorem najlepszych odpowiedzi gracza $i$ na podprofil $\sigma _{{-i}}$ .

Odwzorowanie $B_{i}:\Sigma _{{-i}}\rightarrow 2^{{\Sigma _{i}}}$ nazywamy odwzorowaniem najlepszej odpowiedzi gracza $i$ . Jego wartościami są podzbiory zbioru $\Sigma _{i}.$

Odwzorowanie $B:\Sigma\rightarrow\times 2^{{\Sigma _{i}}},i\in N$ zdefiniowane wzorem

$B(\sigma)=\times B_{i}(\sigma _{{-i}}),\ i\in N$

nazywamy odwzorowaniem najlepszej odpowiedzi gry strategicznej GS.

Za pomocą odwzorowań $B_{i},\ i=1,...n$ oraz $B$ uzyskujemy równoważną z wyjściową definicję RN.

Definicja (ważna) 4.7

RN gry strategicznej GS jest to profil $\sigma^{*}=(\sigma _{1}^{*},...,\sigma _{N}^{*})$ taki że

$\forall i\in N\ \ \sigma _{i}^{*}\in B_{i}(\sigma _{{-i}}^{*})$

lub krócej

$\sigma^{*}\in B(\sigma^{*})$

Inaczej mówiąc, RN gry strategicznej GS jest punktem stałym (wielowartościowego) odwzorowania najlepszej odpowiedzi $B$ tej gry. W RN gracze grają wzajemnie najlepsze odpowiedzi.

Uwaga 4.1

Powyższa definicja RN jest równoważna definicji 3.1. Dowód pozostawiamy czytelnikowi jako proste ćwiczenie.

4.3. Twierdzenie Nasha

Twierdzenie (ważne) 4.2

Twierdzenie Nasha, J. Nash, 1950

Każda skończona GS = $<N,(\Sigma _{i}),(u_{i})>$ ma równowagę Nasha w strategiach mieszanych.

Fakt 1.

Zbiór $\Sigma$ jest niepustym, zwartym i wypukłym podzbiorem skończeniewymiarowej przestrzeni euklidesowej.

Wynika to z faktu że $\Sigma _{i}$ jest $|A_{i}|-1$ - wymiarowym sympleksem, a $\Sigma=\times\Sigma _{i},\ i\in N.$

Fakt 2.

$\forall\sigma\in\Sigma\ \ B(\sigma)\neq\emptyset$

By to wykazać ustalmy $i$ . $u_{i}$ jest liniowa w argumencie odpowiadającym strategii mieszanej $\sigma _{i}$ :

$\forall\lambda\in[0,1]\ \ u_{i}(\lambda\sigma _{i}^{{\prime}}+(1-\lambda)\sigma _{i}^{{{}^{{\prime\prime}}}},\sigma _{{-i}})=\lambda u_{i}(\sigma _{i}^{{\prime}},\sigma _{{-i}})+(1-\lambda)u_{i}(\sigma _{i}^{{{}^{{\prime\prime}}}},\sigma _{{-i}})$

i jest określona na zwartym sympleksie jednostkowym $\Sigma _{i}$ , więc $u_{i}$ , jako funkcja ciągła, osiąga maksimum na sympleksie gry $\Sigma$ .

Fakt 3.

$\forall\sigma\in\Sigma$ zbiór $B(\sigma)$ jest wypukły.

By to wykazać ustalmy gracza $i$ . Weźmy $\sigma _{i}^{{{}^{{\prime}}}},\sigma _{i}^{{{}^{{\prime\prime}}}}\in B_{i}(\sigma _{i})$ . Mamy, z definicji odwzorowania najlepszej odpowiedzi:

$u_{i}(\sigma _{i}^{{{}^{{\prime}}}},\sigma _{{-i}})\ge u_{i}(\sigma _{i},\sigma _{{-i}}),\ {\mbox{oraz}}\ u_{i}(\sigma _{i}^{{{}^{{\prime\prime}}}},\sigma _{{-i}})\ge u_{i}(\sigma _{i},\sigma _{{-i}}).$

Stąd

$\forall\lambda\in[0,1],\ \forall\sigma _{i}\in\Sigma _{i}\ u_{i}(\lambda\sigma _{i}^{{\prime}}+(1-\lambda)\sigma _{i}^{{{}^{{\prime\prime}}}},\sigma _{{-i}})\ge u_{i}(\sigma _{i},\sigma _{{-i}}),$

a zatem $\lambda\sigma _{i}^{{\prime}}+(1-\lambda)\sigma _{i}^{{{}^{{\prime\prime}}}}\in B_{i}(\sigma _{{-i}}),$ czyli $B_{i}(\sigma _{{-i}})$ jest wypukły. $B(\sigma)$ jest wypukły jako iloczyn $\times B_{i}(\sigma _{{-i}})$ zbiorów wypukłych.

Fakt 4.

Odwzorowanie $B:\Sigma\rightarrow 2^{\Sigma}$ ma wykres domknięty.

Weżmy dwa ciągi $(\sigma^{n}),(\hat{\sigma}^{n})$ takie, że

$\sigma^{n}\longrightarrow\sigma,\quad\hat{\sigma}^{n}\longrightarrow\hat{\sigma},\quad\hat{\sigma}^{n}\in B(\sigma^{n}).$

Pokażemy że

$\hat{\sigma}\in B(\sigma).$

Pamiętajmy że zbieżność jest w odpowiedniej przestrzeni euklidesowej, a zatem zbiegają współrzędne profili, czyli strategie mieszane graczy, oraz podprofili, co będziemy wykorzystywali w dalszej części dowodu.

Załóżmy że $\hat{\sigma}\notin B(\sigma):=\times B_{i}(a_{{-i}}).$

Wtedy dla pewnego $i$

$\hat{\sigma}_{i}\notin B_{i}(\sigma _{i}),$

a zatem

$\exists\epsilon>0\ \ \exists\sigma _{i}^{{{}^{{\prime}}}}:\ u_{i}(\sigma _{i}^{{{}^{{\prime}}}},\sigma _{{-i}})>u_{i}(\hat{\sigma}_{i},\sigma _{{-i}})+3\epsilon$

Ponieważ $u_{i}$ jest ciągła we wszystkich argumentach, więc dla dostatecznie dużych $n$

$u_{i}(\sigma _{i}^{{{}^{{\prime}}}},\sigma _{{-i}}^{n})>u_{i}(\sigma _{i}^{{{}^{{\prime}}}},\sigma _{{-i}})-\epsilon>u_{i}(\hat{\sigma}_{i},\sigma _{{-i}})+2\epsilon>u_{i}(\hat{\sigma}_{i}^{n},\sigma _{{-i}}^{n})+\epsilon>u_{i}(\hat{\sigma}_{i}^{n},\sigma _{{-i}}^{n}).$

W pierwszej nierówności wykorzystujemy fakt że $\sigma _{{-i}}^{n}\rightarrow\sigma _{{-i}}$ gdyż $\sigma^{n}\rightarrow\sigma$ , w drugiej nierówność otrzymaną powyżej, trzecia zachodzi ponieważ założyliśmy że $(\sigma^{n},\hat{\sigma}^{n})\longrightarrow(\sigma,\hat{\sigma})$ , czyli w szczególności zbieżność po współrzędnych: $\ \sigma _{{-i}}^{n}\rightarrow\sigma _{{-i}},\ \ \hat{\sigma}_{i}^{n}\rightarrow\hat{\sigma}_{i}.$ Tak więc $u_{i}(\sigma _{i}^{{{}^{{\prime}}}},\sigma _{{-i}}^{n})>u_{i}(\hat{\sigma}_{i}^{n},\sigma _{{-i}}^{n}),$ sprzeczność z faktem że $\hat{\sigma}_{i}^{n}\in B_{i}(\sigma^{n})$ .

Konkludując, odwzorowanie $B:\Sigma\rightarrow 2^{{\Sigma}}$ jest wypukłym, domkniętym (posiadającym wykres domknięty) odwzorowaniem niepustego, zwartego i wypukłego podzbioru $\Sigma$ skończenie wymiarowej przestrzeni euklidesowej w niepusty zbiór podzbiorów $\Sigma$ . Z twierdzenia Kakutaniego 4.1 o punkcie stałym

$\exists\sigma^{*}\in\Sigma:\sigma^{*}\in B(\sigma^{*}),$

a zatem $\sigma^{*}$ jest RN.

∎

Uwaga 4.2

Pojęcie RN jest centralnym pojęciem teorii gier. Na ogół interesujące gry posiadają wiele równowag Nasha. Teoria gier nie posiada zadowalającego aparatu formalnego prowadzącego do wyboru takiej a nie innej RN. Problem niejednoznaczności RN jest szeroko omawiany w cytowanej w Wykładzie 1 literaturze. Problemem też jest jak ”dojść” do równowagi Nasha. Pewne formalne procedury w pewnych sytuacjach daje teoria gier ewolucyjnych. Okazuje się też że (co zostało potwierdzone m. in. przez eksperymenty laboratoryjne), że ludzie często nie ”grają” RN. Implikuje to konieczność dalszych badań i wprowadzenie bardziej ogólnego aparatu formalnego teorii gier, który dawałby wyniki lepiej zgadzające się z rzeczywistością.

4.4. Uogólnienia Twierdzenia Nasha

Definicja 4.8

Niech $E\subset\Re^{m}$ - zbiór wypukły, $\ f:E\rightarrow\Re$ . Powiemy że

1. $f$ jest quasi-wklęsła $\Leftrightarrow\forall\alpha\in\Re\ \ \{ x\in E:f(x)\ge\alpha\}$ jest wypukły.

2. $f$ jest quasi-wypukła $\Leftrightarrow\forall\alpha\in\Re\ \ \{ x\in E:f(x)\le\alpha\}$ jest wypukly.

Twierdzenie 4.3 (Glicksberg, 1952)

Niech w GS $\forall i\in N\ \ A_{i}\subset\Re^{m}$ jest niepustym, zwartym podzbiorem $\Re^{m}$ , i $u_{i}:A\rightarrow\Re$ jest funkcją ciągłą $\forall i\in N$ . Wtedy GS ma RN (w strategiach mieszanych).

Twierdzenie 4.5

Debreu, 1952, Fan, 1952, Glicksberg, 1952 Rozważmy GS taka że $\forall i\in N\ \ A_{i}\subset\Re^{m}$ są to niepuste, zwarte i wypukłe podzbiory przestrzeni euklidesowej $\Re^{n}$ , a $u_{i}$ sa ciągłe w $a$ i quasi-wklęsłe w $a_{i}$ . Wtedy istnieje RN w strategiach CZYSTYCH.

Uwaga 4.3

Idea dowodu: ciągłość $u_{i}$ implikuje że odwzorowanie $B$ ma wykres domknięty i zbiór $B$ jest niepusty. Quasi-wklęsłość w $a_{i}$ implikuje że wartościami $B_{i}$ są zbiory wypukłe.

Uwaga 4.4

f jest quasi-wypukła $\Leftrightarrow$ (-f) jest quasi-wklęsła.

Uwaga 4.5

Dasgupta, Maskin (1986) udowodnili twierdzenie o istnieniu odrzucając założenia o ciągłości wypłat (np. niespełnianego dla ważnego w ekonomii matematycznej oligopolu Bertranda). Ich słabsze założenia są spełniane w większości modeli ważnych dla zastosowań.

Ćwiczenie 4.1

Wykaż że Słaby Dylemat Więźnia ma continuum RN.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Wstęp do Teorii Gier