Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Wstęp do teorii gier – 4. Twierdzenia o istnieniu Równowagi Nasha – MIM UW

Zagadnienia

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.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.