Wstęp do teorii gier

4.1. Preliminaria matematyczne

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

γ:X→2Y

będziemy oznaczać γ:X⟹Y.

Definicja 4.1

Wykres odwzorowania γ:E⟹F,⁢E,F⊂ℜm jest to zbiór

G⁢r⁢⁢γ:=x,y∈E×F:y∈γ⁢x

Definicja 4.2

Odwzorowanie γ:E⟹F,⁢E,F⊂ℜm jest domknięte w x jeżeli

(xn→x,yn→y,yn∈γ(xn))⇒y∈γ(x).

Odwzorowanie γ jest domknięte jeżeli jest domknięte w każdym punkcie swojej dziedziny, czyli jeżeli jego wykres, G⁢r⁢⁢γ jest domknięty.

Przykład 4.1

Odwzorowanie γ⁢x:=0,1,⁢x∈ℜ nie jest domknięte w x0=1. Weźmy bowiem ciąg xn taki że xn→1, oraz ciąg yn∈γ⁢xn=0,1 taki że yn→y:=1. Mamy więc y∉γ⁢x0.

Odwzorowanie γ⁢x:=0 dla x=0,⁢⁢1/x dla x∈ℜ\0 jest domknięte.

Przykład 4.2

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

f~⁢1/3=2/12,7/12,⁢f~⁢x=f⁢x,⁢x∈0,1\1/3,

to dla tak określonego odwzorowania f~ istnieje x∈0,1:x∈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 Ψ:K⟹K ma punkt stały x∈K jeśli x∈Ψ⁢x

Twierdzenie 4.1 (Kakutani, 1941)

Niech X - niepusty, zwarty, wypukły podzbiór n-wymiarowej przestrzeni euklidesowej ℜn, f:X⟹X -odwzorowanie t. że

1. ∀x∈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 xn,yn takich że xn→x,⁢yn→y,⁢yn∈f⁢xn, zachodzi y∈f⁢x].

Wtedy odwzorowanie f ma punkt stały (i.e. ∃x∈X:x∈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∈A-i,⁢i∈N zbiór

Bi⁢a-i=ai∈Ai:ui⁢ai,a-i≥ui⁢a~i,a-i⁢⁢∀a~i∈Ai

nazywamy zbiorem najlepszych odpowiedzi gracza i na podprofil a-i.

Odwzorowanie Bi:A-i→2Ai nazywamy odwzorowaniem najlepszej odpowiedzi (best reply correspondence) gracza i. Jego wartościami są podzbiory zbioru Ai strategii czystych gracza i.

Odwzorowanie B:A→×2Ai,i∈N zdefiniowane wzorem

B(a)=×Bi(a-i),i∈N

nazywamy odwzorowaniem najlepszej odpowiedzi gry strategicznej GS.

Za pomocą odwzorowań Bi,⁢i=1,…⁢n oraz B uzyskujemy równowane z wyjściową definicje RN.

Definicja 4.5

RN (w strategiach czystych) jest to profil a*=a1*,…,aN* taki że

∀i∈N⁢⁢⁢ai*∈Bi⁢a-i*

lub krócej

a*∈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

B1⁢L=T,B,⁢B1⁢M=T,⁢B2⁢T=L,⁢B2⁢B=M,

B⁢a*=B⁢a1*,a2*=B1⁢a2*⁢B2⁢a1*

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

a1*,a2*:a1*∈B1⁢a2*∧a2*∈B2⁢a1*=T,L.

Dla strategii mieszanych odpowiednie definicje mają postać:

Definicja 4.6

Dla każdego podprofilu σ-i∈Σ-i,⁢i∈N zbiór

Bi⁢σ-i=σi∈Σi:ui⁢σi,σ-i≥ui⁢σ~i,σ-i⁢⁢∀σ~i∈Σi

nazywamy zbiorem najlepszych odpowiedzi gracza i na podprofil σ-i.

Odwzorowanie Bi:Σ-i→2Σi nazywamy odwzorowaniem najlepszej odpowiedzi gracza i. Jego wartościami są podzbiory zbioru Σi.

Odwzorowanie B:Σ→×2Σi,i∈N zdefiniowane wzorem

B(σ)=×Bi(σ-i),i∈N

nazywamy odwzorowaniem najlepszej odpowiedzi gry strategicznej GS.

Za pomocą odwzorowań Bi,⁢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 σ*=σ1*,…,σN* taki że

∀i∈N⁢⁢⁢σi*∈Bi⁢σ-i*

lub krócej

σ*∈B⁢σ*

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,(Σi),(ui)> ma równowagę Nasha w strategiach mieszanych.

Fakt 1.

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

Wynika to z faktu że Σi jest Ai-1 - wymiarowym sympleksem, a Σ=×Σi,i∈N.

Fakt 2.

∀σ∈Σ⁢⁢⁢B⁢σ≠∅

By to wykazać ustalmy i. ui jest liniowa w argumencie odpowiadającym strategii mieszanej σi:

∀λ∈0,1⁢⁢⁢ui⁢λ⁢σi′+1-λ⁢σi′′,σ-i=λ⁢ui⁢σi′,σ-i+1-λ⁢ui⁢σi′′,σ-i

i jest określona na zwartym sympleksie jednostkowym Σi, więc ui, jako funkcja ciągła, osiąga maksimum na sympleksie gry Σ.

Fakt 3.

∀σ∈Σ zbiór B⁢σ jest wypukły.

By to wykazać ustalmy gracza i. Weźmy σi′,σi′′∈Bi⁢σi. Mamy, z definicji odwzorowania najlepszej odpowiedzi:

ui⁢σi′,σ-i≥ui⁢σi,σ-i,⁢oraz⁢⁢ui⁢σi′′,σ-i≥ui⁢σi,σ-i.

Stąd

∀λ∈0,1,⁢∀σi∈Σi⁢⁢ui⁢λ⁢σi′+1-λ⁢σi′′,σ-i≥ui⁢σi,σ-i,

a zatem λ⁢σi′+1-λ⁢σi′′∈Bi⁢σ-i, czyli Bi⁢σ-i jest wypukły. B⁢σ jest wypukły jako iloczyn ×Bi(σ-i) zbiorów wypukłych.

Fakt 4.

Odwzorowanie B:Σ→2Σ ma wykres domknięty.

Weżmy dwa ciągi σn,σ⌃n takie, że

σn⟶σ,⁢σ⌃n⟶σ⌃,⁢σ⌃n∈B⁢σn.

Pokażemy że

σ⌃∈B⁢σ.

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 σ⌃∉B(σ):=×Bi(a-i).

Wtedy dla pewnego i

σ⌃i∉Bi⁢σi,

a zatem

∃ϵ>0⁢⁢⁢∃σi′:⁢ui⁢σi′,σ-i>ui⁢σ⌃i,σ-i+3⁢ϵ

Ponieważ ui jest ciągła we wszystkich argumentach, więc dla dostatecznie dużych n

ui⁢σi′,σ-in>ui⁢σi′,σ-i-ϵ>ui⁢σ⌃i,σ-i+2⁢ϵ>ui⁢σ⌃in,σ-in+ϵ>ui⁢σ⌃in,σ-in.

W pierwszej nierówności wykorzystujemy fakt że σ-in→σ-i gdyż σn→σ, w drugiej nierówność otrzymaną powyżej, trzecia zachodzi ponieważ założyliśmy że σn,σ⌃n⟶σ,σ⌃, czyli w szczególności zbieżność po współrzędnych: ⁢σ-in→σ-i,⁢⁢σ⌃in→σ⌃i. Tak więc ui⁢σi′,σ-in>ui⁢σ⌃in,σ-in, sprzeczność z faktem że σ⌃in∈Bi⁢σn.

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

∃σ*∈Σ:σ*∈B⁢σ*,

a zatem σ* 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⊂ℜm - zbiór wypukły, ⁢f:E→ℜ. Powiemy że

1. f jest quasi-wklęsła ⇔∀α∈ℜ⁡⁢⁢x∈E:f⁢x≥α jest wypukły.

2. f jest quasi-wypukła ⇔∀α∈ℜ⁡⁢⁢x∈E:f⁢x≤α jest wypukly.

Twierdzenie 4.3 (Glicksberg, 1952)

Niech w GS ∀i∈N⁢⁢⁢Ai⊂ℜm jest niepustym, zwartym podzbiorem ℜm, i ui:A→ℜ jest funkcją ciągłą ∀i∈N. Wtedy GS ma RN (w strategiach mieszanych).

Twierdzenie 4.5

Debreu, 1952, Fan, 1952, Glicksberg, 1952 Rozważmy GS taka że ∀i∈N⁢⁢⁢Ai⊂ℜm są to niepuste, zwarte i wypukłe podzbiory przestrzeni euklidesowej ℜn, a ui sa ciągłe w a i quasi-wklęsłe w ai. Wtedy istnieje RN w strategiach CZYSTYCH.

Uwaga 4.3

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

Uwaga 4.4

f jest quasi-wypukła ⇔ (-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.

Zagadnienia

4. Twierdzenia o istnieniu Równowagi Nasha