Zagadnienia

5.1 Definicje
5.2 Własności. Podstawowe twierdzenia

5. Gry o sumie zerowej

Dwuosobowe gry o sumie zerowej (ogólniej: o sumie stałej) byly–chronologicznie–pierwszym typem gier rozważanym przez natematyków, w szczególności w pracach J. von Neumanna w latach 20ych i 30ych XX wieku. Gry o sumie zerowej były podstawą opracowanej przez J. von Neumanna i O. Morgensterna matematycznej teorii gier [16].

5.1. Definicje

Definicja 5.1

GS jest grą o sumie stałej jeżeli

∃c∈ℜ:⁢∀a∈A⁢⁢⁢∑i=1nui⁢a=c.

Jeśli c=0 to GS nazywamy grą o zumie zerowej i oznaczamy GS0.

Gry dwuosobowe (n=2) o sumie zero nazywa się też grami ściśle konkurencyjnymi. Nazwa gry ściśle konkurencyjne wynika stąd że w takich grach interesy graczy są ”ściśle przeciwstawne”: aby uzyskać maksymalną wypłatę gracz dąży do tego by zminimalizować sumę wypłat przeciwników. W takich grach gracze mają przeciwne wypłaty:

u1⁢a=-u2⁢a,a∈A.

Do takich gier można zaklasyfikować (pomijając remisy) gry towarzyskie (parlor games): szachy, GO, warcaby, klasyczne dwuosobowe gry karciane. ”Teoriogrowe” przykłady ściśle konkurencyjnych GS to: gra Kamień-Papier-Nożyczki, Orzeł-Reszka.

Skończone gry dwuosobowe o sumie zerowej nazywa się też grami macierzowymi.

Uwaga 5.1

Możemy sformułować równoważną definicję GS o sumie stałej używając strategii mieszanych: GS jest grą o sumie stałej jeżeli

∃c∈ℜ:⁢∀σ∈Σ⁢⁢∑i=1nui⁢σ=c.

Równoważność wynika z liniowości funkcji wypłat względem poszczególnych argumentów profilu GS0.

Wszystkie poniższe definicje, o ile nie zostanie napisane inaczej, odnoszą sie do GS0.

Uwaga 5.2

Wypłaty w takich grach możeny zapisać w formie macierzowej:

u1⁢σ=u1⁢σ1,σ2=σ1⁢A⁢σ2T,⁢⁢u2⁢σ=-u1⁢σ⁢⁢∀σ∈Σ,

gdzie profil σ1 jest wektorem wierszowym, σ2T - wektorem kolumnowym.

Zdefiniujemy dwie liczby: v1: maximin, oraz v2: minimax.

Definicja 5.2

v1:=m⁢a⁢xσ1∈Σ1⁢m⁢i⁢nσ2∈Σ2⁢u1⁢σ1,σ2

v2:=m⁢i⁢nσ2∈Σ2⁢m⁢a⁢xσ1∈Σ1⁢u1⁢σ1,σ2.

v1,⁢v2 nazywamy też odpowiednio dolną i górna wartością GS0.

Uwaga 5.3

Gdy zastąpimy w tej definicji Σi przez Ai, czyli weźmiemy pod uwagę tylko strategie czyste, to w celu obliczenia v1 bierzemy minimum z każdego wiersza macierzy wypłat gracza 1 i z tak uzyskanej kolumny znajdujemy maksimum.

Heurystycznie, maximin v1 jest maksymalną wypłatą gracza 1 gdy gracz 2 minimalizuje wypłaty u1 gracza 1. Dokładniej: dla każdego profilu σ1 gracz 1 znajduje profil σ2 który minimalizuje u1 a ”następnie” 1 swoimi profilami σ1 maksymalizuje u1. Otrzymana wartość u1 to maximin; minimax v2 jest wynikiem procedury optymalizacyjnej gracza 2, który wpierw maksymalizuje u1 profilami σ1 przy ustalonym σ2, a następnie minimalizuje u1 swoimi profilami σ2.

Zauważmy że v1,v2 można zdefiniować dla dowolnych (niekoniecznie o sumie zero) dwuosobowych GS.

Definicja 5.3

Profil σ1*,σ2* jest punktem siodłowym jeżeli

u1(σ1,σ2*)≤u1(σ1*,σ2*)≤u1(σ1*,σ2)∀σi∈Σi,i=1,2.)

Wypłatę u1⁢σ1*,σ2* nazwiemy wartością gry (w punkcie siodłowym, saddle point value of the game).

Uwaga 5.4

Ponieważ

-u1⁢σ1*,σ2*≥-u1⁢σ1*,σ2,

więc, z uwagi na u2=-u1, mamy

u2⁢σ1*,σ2*≥u2⁢σ1*,σ2,

a zatem punkt siodłowy GS0 jest RN GS0.

5.2. Własności. Podstawowe twierdzenia

Sformułujemy podstawowe twierdzenie dla rozważanych gier.

Twierdzenie 5.1 (”O minimaksie”, J. von Neumann, 1928)

Dla każdej 2-osobowej skończonej GS o sumie zerowej

1. Istnieje punkt siodłowy.

2. Istnieje v*∈ℜ taka że v1=v2=v*, patrz Definicja 5.2.

3. Jeżeli σ1*,σ2* jest punktem siodłowym to u1⁢σ1*,σ2*=v*.

4. σ1*,σ2* jest punktem siodłowym wtedy i tylko wtedy gdy

σ1*∈a⁢r⁢g⁢m⁢a⁢xσ1⁢m⁢i⁢nσ2⁢u1⁢σ1,σ2

oraz

σ2*∈a⁢r⁢g⁢m⁢i⁢nσ2⁢m⁢a⁢xσ1⁢u1⁢σ1,σ2

Punkt 1 jest szczególnym ptzypadkiem Twieredzenia Nasha.

Punkt 2. mówi że w dwuosobowych GS0 maximin i minimaks są sobie równe.

Punkt 3. mówi że v* jest taka sama we wszystkich punktach siodłowych. W każdym punkcie siodłowym są jednocześnie spełnione najbardziej pesymistyczne przewidywania obu graczy. Gracz 1 otrzymuje wypłatę u1⁢σ1*,σ2=v*, gracz 2 otrzymuje wypłatę -u1⁢σ1*,σ2=-v*.

Punkt 4 mówi że w punkcie siodłowym gracz 1 gra strategią maximinową, gracz 2-i minimaksową.

1. Jest to szczególny przypadek twierdenia Nasha o istnieniu. Oryginalny dowód von Neumanna korzystał z innych technik matematycznych.

2. Wykażemy wpierw że v2≥v1. Niech σi∈Σi,i=1,2. Zachodzi

m⁢i⁢nσ2′∈Σ2⁢u1⁢σ1,σ2′≤u1⁢σ1,σ2.

(5.1)

Działając na powyższą nierówność operatorem m⁢a⁢xσ1∈Σ1 otzymujemy

v1=m⁢a⁢xσ1∈Σ1⁢m⁢i⁢nσ2′∈Σ2⁢u1⁢σ1,σ2′≤m⁢a⁢xσ1∈Σ1⁢u1⁢σ1,σ2.

(5.2)

Nierówność ta zachodzi dla każdego σ2∈Σ2. Działając na powyższą nierówność operatorem m⁢i⁢nσ2∈Σ2 otzymujemy

v1≤m⁢i⁢nσ2∈Σ2⁢m⁢a⁢xσ1∈Σ1⁢u1⁢σ1,σ2=v2.

(5.3)

co dowodzi nierowności v2≥v1.

Pokażemy teraz że v1≥v2. Wykorzystamy fakt istnienia RN. Niech σ1*,σ2* będzie RN, czyli

u1⁢σ1*,σ2*≥u1⁢σ1,σ2*⁢∀σ1∈Σ1,

(5.4)

oraz

u1⁢σ1*,σ2*≤u1⁢σ1*,σ2⁢∀σ1∈Σ1.

(5.5)

Zachodzi też

v1=m⁢a⁢xσ1∈Σ1⁢m⁢i⁢nσ2∈Σ2⁢u1⁢σ1,σ2≥m⁢i⁢nσ2∈Σ2⁢u1⁢σ1*,σ2.

(5.6)

Ponieważ, na mocy (5.5)

m⁢i⁢nσ2∈Σ2⁢u1⁢σ1*,σ2=u1⁢σ1*,σ2*,

(5.7)

więc

v1≥u1⁢σ1*,σ2*.

(5.8)

Z uwagi na (5.4) mamy

u1⁢σ1*,σ2*=m⁢a⁢xσ1∈Σ1⁢u1⁢σ1,σ2*

(5.9)

a więc

v1≥m⁢a⁢xσ1∈Σ1⁢u1⁢σ1,σ2*≥m⁢i⁢nσ2∈Σ2⁢m⁢a⁢xσ1∈Σ1⁢u1⁢σ1,σ2=v2.

(5.10)

Wykazaliśmy v1≥v2 i v1≤v2, a zatem równość v1=v2=v*.

3. Punkt 3 jest bezpośrednia konsekwencją powyższej równości. W każdej równowadze mamy więc:

Dla gracza 1:

u1⁢σ1*,σ2*=m⁢a⁢xσ1∈Σ1⁢m⁢i⁢nσ2∈Σ2⁢u1⁢σ1,σ2=v*,

(5.11)

a dla gracza 2

u2⁢σ1*,σ2*=-m⁢i⁢nσ2∈Σ2⁢m⁢a⁢xσ1∈Σ1⁢u1⁢σ1,σ2=-v*.

(5.12)

Punkt 4 zostawiamy czytelnikowi jako ćwiczenie.

∎

Definicja 5.4

Liczbę v* nazywamy wartością (value) dwuosobowej GS o sumie zerowej.

Wartość ściśle konkurencyjnej GS0 jest to więc wypłata gracza 1 w punkcie siodłowym.

Definicja 5.5

Strategia σi gracza i rozwiązująca problem

m⁢a⁢xσi⁢m⁢i⁢nσ-i⁢ui⁢σi,σ-i,⁢⁢i=1,2,

nazywa sie strategią maksyminową gracza i.

Twierdzenie 5.2

Jeżeli v1=v2 to (każdy) profil σ1*,σ2*, gdzie σi* jest strategią maksyminową gracza i,⁢i=1,2 jest punktem siodłowym.

Przykład 5.1

Znajdziemy strategię maksyminową i wypłatę ze strategii maksyminowej gracza 1 (wierszowego) w grze Orzeł – Reszka.

	B	S
B	1,-1	-1,1
S	-1,1	1,-1

Niech σ1=p,1-p,⁢σ2=y,1-y. Obliczamy

u1⁢σ1,σ2=1-2⁢p⁢1-2⁢y.

Przy ustalonym p: dla p<1/2 u1 przyjmuje minimum dla y=1, wynosi ono 2⁢p-1<0. Dla p=1/2 minimum u1 wynosi 0. Dla p>1/2 minimum u1 jest dla y=0 i jest mniejsze od zera. Tak więc m⁢a⁢xp⁢m⁢i⁢n⁢u1=0, strategia maksyminowa to profil 1/2,1/2 z wypłatą 0. Analogicznie postępujemy dla gracza 2.

W każdej RN GS0 gracze otrzymują takie same (przeciwne co do znaku) wypłaty. Zachodzi też interesująca własność ”wymienności równowag” (equilibrium interchangeability). W 2-osobowych GS o sumie zerowej jeżeli gracz 1 wybierze swój profil z pewnej RN a drugi gracz wybierze swój z innej RN, to para tych profili też jest RN. Mówi o tym

Twierdzenie 5.3 (O wymienności równowag)

Niech a,b∈Σ,⁢c,d∈Σ - dwie RN dwuosobowej GS o sumie zerowej. Wtedy profile a,d,c,b też są RN.

Niech v* - wartość gry. W RN a,b, ponieważ suma wypłat graczy jest zero oraz

u2⁢a,b≥u2⁢a,b~⁢⁢∀⁢b~∈Σ2

(a zatem -u2⁢a,b≤-u2⁢a,b~⁢⁢∀⁢b~∈Σ2), więc otrzymujemy

v*=u1⁢a,b=-u2⁢a,b≤-u2⁢a,b~⁢⁢∀⁢b~∈Σ2.

Podstawiając b~=d otrzymujemy obustronne oszacowanie

v*≤-u2⁢a,d=u1⁢a,d≤u1⁢c,d=v*,

gdzie równość wynika z faktu że gra jest o sumie zerowej, a ostatnia nierówność z tego że c,d jest RN. Wypłata u1⁢a,d została obustronnie oszacowana przez v*, a zatem zachodzi równość u1⁢a,d=v*. Otrzymujemy

u1⁢a,d=v*=u1⁢a,b≥u1⁢σ1,d⁢⁢⁢∀σ1∈Σ1,

gdzie nierówność z faktu że a,b jest RN. Mamy też

u1⁢a,d=u1⁢a,b=-u2⁢a,b≤-u2⁢a,σ2=u1⁢a,σ2⁢⁢⁢∀σ2∈Σ2,

nierówność wynika z faktu że a,b jesr RN. Mnożąc przez -1 otrzymujemy stąd

-u1⁢a,d≥-u1⁢a,σ2⁢⁢⁢∀σ2∈Σ2,

a zatem

u2⁢a,d=-u1⁢a,d≥-u1⁢a,σ2=u2⁢a,σ2⁢⁢⁢∀σ2∈Σ2.

Profil a,d jest więc RN. Analogicznie dowodzimy że profil c,b jest RN.

∎

Uwaga 5.5

Dla GS0 można podać efektywne algorytmy szukanie wartości gry za pomocą programowania liniowego, patrz np. monografia Luce, Reiffa [13].

Ćwiczenie 5.1

W symetrycznej GS0 A1=A2,⁢u1⁢a1,a2=u2⁢a2,a1⁢⁢∀ai∈Ai,i=1,2 w mieszanej RN (jeżeli istnieje) zachodzi ui=0,⁢i=1,2.

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

Wstęp do Teorii Gier