Zagadnienia

2.1 Gra strategiczna
2.2 Równowaga Nasha w strategiach czystych
2.3 Strategie mieszane
2.4 Dominacje strategii

2. Gry w postaci strategicznej

2.1. Gra strategiczna

Wprowadzamy oznaczenia

N=1,2,…⁢n-zbiór graczy

Ai,i=1,2,…⁢n-niepusty zbiór akcji (strategii czystych) gracza⁢⁢i

A=×Ai,i∈N.

ui:A→ℜ-wypłata (funkcja wypłat) gracza⁢⁢i,⁢i=1,…⁢n

Definicja (ważna) 2.1

Gra strategiczna jest to trójka G⁢S=N,Aii∈N,uii∈N

Używa się też terminów: gra w postaci strategicznej, gra w postaci normalnej, gra niekooperacyjna.

Oznaczamy

a=a1,a2,…⁢an=aii∈N-profil (strategii czystych) gry,⁢ai∈Ai.

ui⁢a-wypłata gracza i z profilu a

Niekiedy, chcąc wyróżnić gracza i, np. by porównywać wartości funkcji wypłat w profilach w których zmieniamy jedną współrzędna, będziemy profil zapisywali w postaci ai,a-i, gdzie a-i oznacza ciąg wyrazów profilu aj dla wszystkich graczy poza i: a-i=ajj∈N\i. Konsekwentnie oznaczamy A-i=×Ak,k∈N\{i}

Uwaga 2.1

Tam gdzie nie będzie wątpliwości, będziemy utożsamiać akcję ze strategią. W ogólności, dla wielu typów gier strategia to scenariusz, plan działań, akcji na wszystkie możliwe sytuacje. Odpowiednie formalne definicje będą podane w dalszych rozdziałach.

Uwaga 2.2

Ogólniejsza definicja gry strategicznej wprowadza pojęcie wynikow gry i zastepuje funkcje wypłat graczy przez relacje preferencji na zbiorze wyników gry. W tym wykładzie relacje preferencji specyfikujemy przez podanie funkcji użyteczności - funkcji wypłat, które te relacje określają. Więcej na ten temat - patrz np. [13, 16, 20, 14].

Przykład 2.1

N=1,2, A1=1,2,…⁢m1,⁢A2=1,2,…⁢m2. Niech a=a1,a2∈A=A1×A2 - profil strategii czystych, ui⁢a - wyplata gracza i z profilu a, i=1,2. W ogólności zbiory Ai mogą być zbiorami różnych strategii. Zbiory ui⁢a,a∈A mają po m1×m2 elementów, które tworzą m1×m2 elementowe macierze - macierze wypłat graczy. Niech E oznacza macierz wypłat gracza 1, F–gracza 2:

E=eh⁢k,⁢eh⁢k=u1⁢h,k,⁢F=fh⁢k,⁢fh⁢k=u2⁢h,k⁢⁢∀h∈A1,∀k∈A2.

Numer wiersza odpowiada numerowi strategii gracza 1, numer kolumny - numerowi strategii gracza 2.

Przykład 2.2

Jako szczególny przypadek Przykładu 2.1 przyjmijmy

N=1,2,⁢A1=A2=C,D, oraz

u1⁢C,C=R,⁢u1⁢C,D=S,⁢u1⁢D,C=T,⁢u1⁢D,D=P,

u2⁢C,C=R,⁢u2⁢C,D=T,⁢u2⁢D,C=S,⁢u2⁢D,D=P,⁢T,R,P,S∈ℜ. Macierze E,F wypłat gracza 1 i 2 mają postać odpowiednio

E	C	D
C	R	S
D	T	P

F	C	D
C	R	T
D	S	P

Będziemy używać łącznego zapisu

	C	D
C	R,R	S,T
D	T,S	P,P

W szczególoności dla T>R>P>S otrzymujemy Dylemat Więźnia, z oznaczeniami: C = Cooperation, D = Defection.

2.2. Równowaga Nasha w strategiach czystych

Definicja (ważna) 2.2

Równowaga Nasha w strategiach czystych (RN) gry strategicznej

G⁢S=N,Aii∈N,uii∈N

jest to profil akcji (strategii czystych) a*=a1*,a2*,…,aN*∈A t. że ∀i∈N⁢⁢∀ai∈Ai

ui⁢ai*,a-i*≥ui⁢ai,a-i*

Okazuje się że wiele gier nie ma RN w strategiach czystych, np. gra Orzeł - Reszka z Przykładu 1.4.

2.3. Strategie mieszane

Rozważmy grę ”W Kotka i Myszkę” z Przykładu 1.5, o macierzy wypłat

	L	P
L	0,2	1,0
P	1,0	0,2

gdzie myszka (M) jest graczem wierszowym, kot (K) - graczem kolumnowym i nie ma RN w strategiach czystych.

Rozważmy intuicyjny sposób wprowadzenia strategii mieszanych. Niech M wybiera akcję L z prawdopodobieństwem x, P z 1-x, K wybiera L z p-stwem y, P z 1-y. Nazwijmy pary x,1-x,⁢y,1-y strategiami mieszanymi odpowiednio M i K. Można pokazać że para strategii 1/2,1/2,1/2,1/2 ma tę własność że oczekiwana wartość wypłaty M (K) nie podniesie się (w istocie–nie ulegnie zmianie, co będzie wynikało z ogólnej teorii przedstawionej w następnej części) jeżeli dowolnie zmienimy x⁢y (patrz Ćwiczenie 3.2, Ćwiczenie 3.3 ).

Można więc nazwać tę parę równowagą Nasha dla strategii mieszanych.

Definicja 2.3

GS jest skończona jeżeli mi≡Ai<∞,i=1,2,…⁢n.

W dalszym ciągu, o ile nie będzie to powiedziane explicite inaczej, będziemy rozważać gry skończone. Definiujemy

Definicja 2.4

Strategia mieszana σi gracza i w grze strategiczej G⁢S=N,Aii∈N,uii∈N jest to rozkład prawdopodobieństwa na zbiorze jego strategii czystych Ai:

σi=σi⁢1,σi⁢2,…,σi⁢mi

Współrzędna σi⁢h≥0 jest prawdopodobieństwem że gracz i zagra strategią czystą (wybierze akcję) h∈Ai. Wprowadzamy oznaczenia:

Σi=σi:Ai→0,1:∑k=1miσi⁢k=1,⁢σi⁢k≥0– zbiór strategii mieszanych gracza i

σ≡σjj∈N=σ1,σ2,…⁢σn-profil gry

Σ=×Σi,i∈N – zbiór wszystkich profili gry

σ-i=(σ1,σ2,..σ✓i.,.,σN) - profil strategii wszystkich graczy poza graczem i.

ui⁢σ=ui⁢σi,σ-i-wypłata gracza i z profilu σ

W dalszym ciągu zamiast strategia mieszana będziemy mówić strategia. Strategia czysta jest szczególnym przypadkiem strategii mieszanej; czasami gdy będziemy chcieli podkreślić że mamy do czynienia ze strategią czystą będziemy zamiast strategia mówić strategia czysta.

Strategie mieszane opisują sytuacje w których gracze podejmują akcje z pewnym prawdopodobieństwem. Można sobie wyobrażać że każdy gracz posiada urządzenie dające rozkład p-stwa określający jego strategię mieszaną i używaja tego urządzenia do gry. Alternatywna interpretacja strategii mieszanych jest następująca. Każdemu graczowi odpowiada jedna ”bardzo duża” populacja graczy. Częstość występowania w niej graczy grających każdą z akcji ze zbioru Ai jest równa p-stwu występowania tej akcji w strategii mieszanej. Gracz i losuje z tej populacji jednego gracza i gra jego strategią.

Każda strategia mieszana σi każdego gracza i jest opisana przez wektor pewien wektor xi=xi⁢1,…,xi⁢mi w przestrzeni euklidesowej Rmi. Będziemy używać alternatywnie zapisu: σi=σi⁢1,…,σi⁢mi oraz, gdy będziemy chcieli podkreślić algebraiczną strukture wprowadzanego formalizmu, powyższej reprezentacji xi. Profil σ gry będziemy alternatywnie oznaczać przex x, x=x1,…⁢xN. Z definicji rozkładu p-stwa mamy

∑h=1mixi⁢h=1,⁢xi⁢h≥0⁢⁢∀i∈N.

Współrzędna xi⁢h jest prawdopodobieństwem że gracz i zagra strategią czystą (wybierze akcję) h∈Ai.

Definicja 2.5

Niech ∀i∈N⁢⁢Ai=A, czyli zbiór akcji jest ten sam dla wszystkich graczy. GS jest symetryczna ⇔∀i≠j,⁢∀a=a1,…⁢an zachodzi

uj⁢a1,…,ai,…⁢aj,…⁢an=ui⁢a1,…,aj,…,ai,…,an.

Mówimy że GS jest symetryczna jeżeli wypłaty każdych dwóch graczy nie ulegają zmianie przy zamianie ról tych graczy.

Uwaga 2.3

Dla n=2 i gry symetrycznej u2⁢a1,a2=u1⁢a2,a1, macierze wypłat graczy są transponowane. Ogólniej, dla n=2 symetria sprowadza sie do stwierdzenia że macierze wypłat są kwadratowe i jedna powstaje z drugiej przez transpozycję.

Wypłaty graczy z profili strategii mieszanych.

Dla każdego gracza i definiujemy Δi - sympleks jednostkowy gracza i (sympleks strategii mieszanych gracza i) oraz Δ - sympleks strategii mieszanych GS:

Definicja 2.6

Δi=xi=xi⁢1,xi⁢2,…,xmi∈Rmi:∑h=1mixi⁢h=1,⁢xi⁢h≥0⁢⁢∀⁢h∈Ai.

Δ=×iΔi.

Tak więc elementy sympleksu jednostkowego gracza utożsamiamy z jego strategiami mieszanymi. Zbiory Δi,⁢i=1,…⁢n,⁢Δ są zwarte i wypukłe, co bedzie w szczegolności odgrywało rolę w dowodzie istnienia równowagi Nasha.

Przykład 2.3

Dla N=1,2,⁢m1=m2=2,⁢x1=x11,x12,⁢x2=x21,x22, sympleksy obu graczy są odcinkami o długości 2. Dla N=1,2,⁢m1=m2=3 sympleksy obu graczy są trójkątami równobocznymi.

Strategia czysta jest szczególnym przypadkiem strategii mieszanej. Oznaczając

eik=0,…⁢0,1,0,…⁢0

(2.1)

- k-ty wersor w ℜmi, możemy zapisać wektorową reprezentację profilu xi=xi⁢1,…,xi⁢mi w nastepujący sposób:

xi=∑k=1mixi⁢k⁢eik∈Δi.

(2.2)

Można powiedzieć że wektor eik jest strategią (mieszaną) gracza i przypisującą akcji o numerze k ze zbioru Ai prawdopodobieństwo 1, eik jest k-tą strategią czystą gracza i. Dla każdego gracza i wierzchołki sympleksu Δi są to elementy bazy kanonicznej ei1,…,eimi przestrzeni wektorowej Rmi.

Rozważmy G⁢S=N,Aii∈N,uii∈N. Założenie że każdy gracz podejmuje decyzję o wyborze akcji ”niezależnie”, bez wiedzy o wyborze innych graczy, formalizujemy w postaci tzw. postulatu niezależności stochastycznej.

Definicja 2.7

Niech a=a1,…⁢an,⁢ai∈Ai - profil strategii czystych GS. Postulat niezależności statystycznej mówi że (łączne) p-stwo że 1-y gracz wybierze akcję (zagra) a1, …, n-ty zagra an jest dane wyrażeniem

x⁢a=x1⁢a1⁢x2⁢a2⁢…⁢xn⁢an

gdzie xi⁢ai jest p-stwem że gracz i zagra ai,⁢i=1,…⁢n.

W ten sposób każdemu profilowi strategii czystych a∈A gry GS przyporządkowaliśmy liczbę x⁢a≥0. Zachodzi przy tym

∑a∈Ax⁢a=1

(2.3)

Dla każdego gracza i procedura ta definiuje na zbiorze A=×Ai,i=1,…n profili strategii czystych gry pewną zmienna losową Ui o rozkładzie

ui⁢a,x⁢a,⁢a∈A

(2.4)

gdzie ui⁢a jest wypłatą gracza i z profilu a, natomiast x⁢a jest zdefiniowanym wyżej prawdopodobieństwem zagrania tego profilu.

Definicja 2.8

Wypłata gracza i z profilu strategii mieszanych x=x1,…⁢xn jest to wartość oczekiwana zmiennej losowej Ui:

u~i⁢x=∑a∈Aui⁢a⁢x⁢a

W dalszym ciagu będziemy na ogół zastępować u~i⁢x przez ui⁢x, oraz pomijać jedną parę nawiasów tam gdzie nie budzi to wątpliwości. Np. zamiast ui⁢x1,x2 będziemy pisać ui⁢x1,x2.

Funkcje wypłat są liniowe względem poszczególnych współrzędnych profilu gry (w dalszym ciagu będziemy używali zwrotu: wypłaty są liniowe). Mówi o tym

Stwierdzenie 2.1

O liniowości wypłat względem każdej współrzednej pofilu

∀i∈N⁢⁢⁢∀j∈N⁢⁢⁢ui⁢x1,…,∑k=1mjxj⁢k⁢ejk,…⁢xn=∑k=1mjxj⁢k⁢ui⁢x1,…,ejk,…,xn

(2.5)

Wykorzystując postulat niezależności statystycznej [x⁢a=x1⁢a1⁢…⁢xj⁢aj⁢…⁢xn⁢an] prawą stronę przepisujemy w postaci

∑k=1mjxj⁢k⁢∑a1,…,a✓j,…⁢anui⁢a1,…,k,…,an⁢x1⁢a1⁢…⁢1...⁢xn⁢an.

Lewa strona ma postać

ui⁢xi,x-i=∑aj∑a1,…,a✓j,…⁢anx⁢a⁢ui⁢a,

Wyciągając xj⁢aj z x⁢a przed ”wewnętrzną” sumę i pamiętając że ∑aj∈Ajxj⁢aj=∑k=1mjxj⁢k otrzymujemy tezę.

∎

W szczególności dla j=i otrzymujemy wykorzystywana w dalszych rozważaniach równość

∀i∈N⁢⁢⁢ui⁢∑k=1mixi⁢k⁢eik,x-i=∑k=1mixi⁢k⁢ui⁢eik,x-i.

Przykład 2.4

N=2. Oznaczmy A,B - macierze wypłat odpowiednio gracza 1,2. Wypłata gracza 1 z profilu x=x1,x2:

u1⁢x1,x2=∑a1,a2∈Ax1⁢a1⁢x2⁢a2⁢u1⁢a1,a2=x1⁢A⁢x2T.

Analogicznie dla drugiego gracza u2⁢x1,x2=x1⁢B⁢x2T. W szczególności dla gry symetrycznej, tzn. gdy u1⁢x1,x2=u2⁢x2,x1, czyli A=BT.

Uwaga: xi,x-i oznacza profil x1,x2,…⁢xn, a nie profil xi,x1,…⁢x✓i,…,xn. W szczególności, dla n=2,i=2 mamy x-i=x1, ale formalny zapis ui⁢xi,x-i≡u2⁢x2,x1 jest to wartość funkcji wypłat u2 na profilu (w punkcie) x1,x2, a nie na x2,x1.

Definicja 2.9

Rozszerzenie mieszane skończonej gry strategicznej G⁢S⁢⁢N,Aii∈N,uii∈N jest to trójka

G⁢S~=N,Σii∈N,u~ii∈N.

W dalszym ciągu rozszerzenie mieszane także oznaczamy skrótem G⁢S.

2.4. Dominacje strategii

Definicja 2.10

Strategia σi∈Σi ściśle dominuje strategię ηi∈Σi jeżeli

∀⁢σ-i∈Σ-i⁢⁢⁢⁢ui⁢σi,σ-i>ui⁢ηi,σ-i

Definicja 2.12

Strategia σi∈Σi słabo dominuje strategię ηi∈Σi jeżeli

∀⁢σ-i∈Σ-i⁢⁢⁢⁢ui⁢σi,σ-i≥ui⁢ηi,σ-i

oraz istnieje podprofil σ-i∈Σ-i dla którego powyższa nierówność jest ostra.

Mówimy że odpowiednie strategie ηi sa ściśle (słabo) zdominowane przez powyższe strategie σi. Strategia jest słabo zdominowana jeżeli istnieje inna która ją słabo dominuje.

Przykład 2.5

W DW (czysta) strategia D (i.e. σi=0,1,⁢i=1,2) ściśle dominuje każdą inną strategię gracza i.

Przykład 2.6

W Słabym DW

	C	D
C	R,R	S,T
D	T,S	S,S

T>R>S, strategia D nie dominuje ściśle strategii C gracza. Mamy bowiem np. dla i=1–ego gracza, oznaczając σ2=β,1-β:

u1⁢D,σ2=β⁢T+1-β⁢S,

u1⁢C,σ2=β⁢R+1-β⁢S,

a zatem dla β=0, czyli dla σ2=0,1, zachodzi równość u1⁢D,σ2=u1⁢C,σ2.

Przykład 2.7

W Słabym DW (czysta) strategia σ1=D słabo dominuje strategię η1=C 1–go gracza. Mamy bowiem, dla i=1, ⁢σ-i≡σ2:=β,1-β, z liniowości,

u1⁢D,σ2≥u1⁢C,σ2,

oraz ∀σ2≠1,0:

u1⁢D,σ2>u1⁢C,σ2

Uwaga 2.4

Scisła dominacja implikuje słabą dominację.

Definicja 2.13

Strategia σi∈Σi dominuje strategię ηi∈Σi jeżeli

∀⁢σ-i∈Σ-i⁢⁢⁢⁢ui⁢σi,σ-i≥ui⁢ηi,σ-i

Stwierdzenie 2.2

Strategia mieszana która dominuje każdą strategię czystą danego gracza, dominuje każdą strategię nieszaną tego gracza.

W szczególności strategia czysta która dominuje każdą inną strategię czystą danego gracza, dominuje każdą strategię nieszaną tego gracza. Dowód wynikający z liniowości wypłat, pomijamy.

Uwaga 2.5

Strategia ściśle zdominowana nie może wystepować w profilu równowagowym (”nie może być grana w równowadze”), gdyż gracz grający tą strategią mógłby podwyższyć swą wypłatę zmieniając ją na ścisle dominującą.

Usuwając ze zbioru strategii gracza strategię ściśle zdominowaną nie zmieniamy zbioru równowag Nasha. Jeżeli metoda eliminacji strategii ściśle zdominowanych prowadzi do jednego profilu gry, to jest on RN. Nie jest to prawda w przeciwną stronę - w wielu GS istnieją jednoznaczne RN które nie mogą być uzyskane tą metodą.

Uwaga 2.6

Algorytm usuwania strategii ściśle zdominowanych ( wynik nie zależy od kolejności usuwania):

1. Jeśli nie istnieje gracz który ma strategię ściśle zdominowaną, to stop. W przeciwnym razie przejdź do p. 2.

2. Usuń tę strategię i powróć do punktu 1.

Przykład 2.9

	L	S	R
U	4,3	5,1	6,2
M	2,1	8,4	3,6
D	3,0	9,6	2,8

Strategia R ściśle dominuje S, po usunięciu S strategia U ściśle dominuje M i D, po ich usunięciu L ściśle dominuje R. RN to profil (U,L).

Strategia czysta, jeśli nawet nie jest ścisle zdominowana przez żadną inną czystą, może być ściśle zdominowana przez mieszana, jak pokazuje

Przykład 2.10

	L	R
U	2,0	-1,0
M	0,0	0,0
D	-1,0	2,0

M nie jest ściśle zdominowana ani przez R ani D, natomiast jest ściśle zdominowana przez strategię σ=1/2,0,1/2.

Stwierdzenie 2.3

Strategia która nie jest strategią czystą nie może być strategią ściśle dominującą.

Dowód pozostawiamy czytelnikowi jako ćwiczenie.

Ćwiczenie 2.1

Znależć wszystkie strategie słabo zdominowane i ściśle zdominowane w Słabym Dylemacie Więźnia.

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

Wstęp do Teorii Gier