Wybrane zagadnienia
Dariusz Badura
Teoria gier
" Gry statyczne
 Statyczne nieskończone
" Ciągłe
 Normalne
" Dyskretne
 Statyczne skończone
" Dyskretne
 Normalne
Macierzowe
" Gry dynamiczne
 Dynamiczne nieskończone (ciągłe, dyskretne)
 Dynamiczne skończone (ciągłe (ciągłe w czasie -
różniczkowe), dyskretne)
Klasyfikacja gier c.d.
" Gry z sumą zerową
" Gry z sumą niezerową:
 Strategiczne lub niestrategiczne
 Kooperacyjne lub niekooperacyjne
 Hierarchiczne
 Koalicyjne
 Deterministyczne lub stochastyczne
Gry z sumą zerową
Gry mają charakter strategiczny; mogą być:
 deterministyczne,
 stochastyczne.
Gra z sumą zerową  gra, w której wartość nie
jest zmieniana tzn. ani nie jest tworzona ani
niszczona. W grze dwóch graczy: cokolwiek
jeden wygra drugi traci.
Gry z sumą zerową
" Dwa typy gier:
 z pełną informacją
 z niepełną informacją
" W grze z pełną informacją, każdy gracz zna rezultaty wszystkich
dotychczasowych gier (np. szachy, kółko-krzyżyk). w tych grach istnieje
przynajmniej jedna  najlepsza droga gry dla każdego z graczy.
" Najlepsza strategia nie koniecznie pozwala im wygrać lecz może
zminimalizować ich straty. Jeżeli nawet jest to optymalna strategia, to nie
zawsze jest możliwa do odnalezienia przez gracza (np. zbyt duża liczba
decyzji do analizy).
" W grach z niepełną informacją gracze nie znają wszystkich
dotychczasowych ruchów (np. w grach prowadzonych przez graczy
równolegle).
Gry z sumą zerową
" strategie dominujące
" punkt siodła
" strategie mieszane
" strategie gry:
 Maximax,
 Maximin,
 Minimax
Strategie dominujące
Gra 1.: Dwóch ludzi gra prostą grę z pięciocentówką i
ćwierćdolarówką. W tym samym czasie każdy z graczy
wykłada jedną z monet. Jeżeli jeden gracz zagra
pięciocentówką, gracz 1 bierze obie monety. W
przeciwnym wypadku gracz drugi bierze obie.
Naturalnie obaj gracze dążą do tego by zdobyć jak
najwięcej monet.
Jak powinni grać, by to uzyskać?
Tabela płatności
 podstawa wyznaczenia strategii.
Każdy gracz ma dwie strategie: wyrzucić pięciocentówkę lub ćwierćdolarówkę.
gracz 2
Pięciocent. Ćwierćdolar.
gracz 1 Pięciocent. 5 (-5) 25 (-25) strategia
dominująca
Ćwierćdolar. 5 (-5) -25 (25)
Wiersze  możliwe strategie pierwszego gracza,
Kolumny  możliwe strategie drugiego gracza.
gracz 2
Pięciocent. Ćwierćdolar.
gracz 1 Pięciocent. 5 (-5) 25 (-25) strategia
dominująca
strategia dominująca drugiego gracza
Punkt siodłowy
Definicja:
" Wynik gry (macierzowej)  dla tabeli zawierającej wypłaty gracza
wybierającego wiersze  nazywamy punktem siodłowym, jeżeli jego
wartość jest mniejsza lub równa każdej wartości w jego wierszu, a
większa lub równa każdej wartości w jego kolumnie.
Kryterium punktu siodłowego:
" Jeżeli gra macierzowa ma punkt siodłowy, obaj gracze powinni
wybrać zawierające go strategie.
Definicja:
" Dla każdej gry macierzowej, dla której istnieje taka liczba v, że
Wiersz ma strategię gwarantującą mu wygranie co najmniej v, a
Kolumna ma strategię gwarantującą, że Wiersz nie wygra więcej, v
jest wartością gry.
Punkt siodłowy
Punkt siodłowy
Gra 2.: Dwóch ludzi gra prostą grę z pięciocentówką i ćwierćdolarówką.
Zasady są następujące: Jeżeli gracz 1 gra pięciocentówką, gracz 2 daje
jemu 5 centów. Jeżeli gracz 2 zagra pięciocentówką i gracz 1 zagra
ćwierćdolarówką gracz 1 bierze 25 centów. Jeżeli obaj gracze grają
ćwierćdolarówkami gracz 2 bierze 25 centów.
gracz 2
Pięciocent. Ćwierćdolar.
gracz 1 Pięciocent. 5 (-5) 5 (-5)
Ćwierćdolar. 25 (-25) -25 (25)
Punkt siodłowy
Brak strategii dominującej.
1. zdefiniowanie dolnej i górnej wartości gry.  Najmniejsza i
największa spodziewana wygrana przy racjonalnej grze obu graczy.
2. Dla znalezienia najmniejszej wartości wygranej szukamy minimum
w każdym wierszu
3. Dla znalezienia największej wartości wygranej szukamy maximum
w każdej kolumnie
4. Zastosuj zasadę MiniMax
Pięciocent. Ćwierćdolar. Min
Pięciocent. 5 5 5
Ćwierćdolar. 25 -25 -25
Max 25 5
Punkt siodła
Punkt siodłowy
Ogólny sposób poszukiwania punktu siodłowego jest następujący (sposób skuteczny
zarówno dla gier 2x2 jak i większych).
a) wypisz minima z każdego wiersza i wybierz największe z nich
b) wypisz maksima z każdej kolumny i wybierz najmniejsze z nich
Jeżeli obie liczby są równe, to gra ma punkt siodłowy i gracze powinni wybrać te
strategie, które odpowiadają wyznaczonemu wierszowi i kolumnie.
Tabela wypłat:
B1 B2 B1 B2
A1 6 3 A1 6 3 3
A2 5 1 A2 5 1 1
6 3
Punkt siodła
Punkt siodłowy
" Czy może istnieć więcej punktów siodłowych
dla danej tabeli wypłat?
B1 B2 B3 B4
A1 4 2 5 2
A2 2 1 -1 -20
A3 3 2 4 2
A4 -16 0 16 1
Strategie mieszane
Gra 3.: Zasady w trzeciej grze są następujące: obaj gracze posiadają
pięciocentówki i ćwierćdolarówki. W tym samym momencie każdy zagrywa
jedną monetą. Jeżeli obaj zagrają tą samą monetą, gracz 2 daje graczowi 1
wartość średnią wartości monet; w przeciwnym przypadku gracz 1 daje
graczowi 2 średnią obu monet.
gracz 2
Pięciocent. Ćwierćdola .Min
r
gracz 1 Pięciocent. 5 -15 -15
Ćwierćdolar. -15 25 -15
Max 5 25
Strategie mieszane
" Dla pierwszego gracza (stosując zasadę MiniMax):
 wartość minimalna wynosi  15
 wartość maksymalna wynosi 25
" Załóżmy, że gracz 2 zna którą monetą zagra gracz 1  Gracz 2 zawsze wygrywa.
Dlatego gracz 1 nie może grać stałym wzorcem. Jego strategia musi być zmienna. Z
prawdopodobieństwem p gra pięciocentówką i z prawdopodobieństwem 1-p gra
ćwierćdolarówką. Najkorzystniej, gdy gracz 2 gra 2/3 pięciocentówką i 1/3
ćwierćdolarówką.
gracz 2
Pięciocent. Ćwierćdolar .Min
gracz 1 Pięciocent. 5 -15 -15
Ćwierćdolar. -15 25 -15
Max 5 25
Teoria gry mieszanej
" tabela płatności gry z sumą zerową:
Gracz B
strategia b1 strategia b2
strategia a1 c11 c12 r1
Gracz A
strategia a2 c21 c22 r2
s1 s2
r1 = c11 - c12 r2 = c21 - c22 s1 = c11 - c21 s2 = c12 - c22
Dla gracza A:
p  prawdopodobieństwo wyboru strategii a1;
1 - p  prawdopodobieństwo wyboru strategii a2;
Dla gracza B:
q  prawdopodobieństwo wyboru strategii b1;
1 - q  prawdopodobieństwo wyboru strategii b2;
Zysk gracza A:
WA = pqc11 + p(1 - q)c12 + (1 - p)qc21 + (1 - p)(1 - q)c22
WA = q ( p (s1 - s2) + s2 ) + pr2 + c22
wpływ strategii gracza A
Teoria gry mieszanej
tabela płatności gry z sumą zerową:
Gracz B
strategia b1 strategia b2
strategia a1 c11 c12 r1
Gracz A
strategia a2 c21 c22 r2
s1 s2
r1 = c11 - c12 r2 = c21 - c22 s1 = c11 - c21 s2 = c12 - c22
WA = q ( p (s1 - s2) + s2 ) + pr2 + c22
Dla zneutralizowania wpływu strategii gracza B na zysk gracz A powinien dążyć do
zerowania wartości wyrażenia zawartego w nawiasach. Wówczas:
p =  s2 / (s1  s2) przy założeniu, że (0 =< p =< 1)
s1 >= 0 i s2 =< 0 i s1 > s2 lub
s1 =< 0 i s2 >= 0 i s1 < s2
Teoria gry mieszanej
Analogicznie zysk gracza B:
WB = - WA
WB = p ( q (r1 - r2) + r2 ) + qs2 + c22
Dla zneutralizowania wpływu strategii gracza B na zysk gracz A powinien dążyć
do zerowania wartości wyrażenia zawartego w nawiasach. Wówczas:
q =  r2 / (r1  r2) przy założeniu, że (0 =< q =< 1)
Gra z sumą niezerową
Tablica wypłat dla gracza A
Zysk gracza A:
WA = q ( p (s1 - s2) + s2 ) + pr2 + c22
Gracz B
strategia b1 strategia b2
strategia a1 c11 c12 r1
Gracz A
strategia a2 c21 c22 r2
s1 s2
Gra z sumą niezerową
Tablica wypłat dla gracza B
Zysk gracza B:
WB = p ( q (r1  r2 ) + r2 ) + qs 2 + d22
Gracz B
strategia b1 strategia b2
strategia a1 d11 d12 r1
Gracz A
strategia a2 d21 d22 r2
s1 s2
Gry 2xn o sumie zerowej
" Gry 2xn różnią się od gier 2x2 tym, że jeden z graczy ma do swojej
dyspozycji więcej niż dwie strategie czyste. Rozwiązaniem takiej gry
jest albo punkt siodłowy, albo strategia mieszana złożona z dwóch
strategii czystych.
" Do rozwiązywania gier 2xn konieczna jest umiejętność
rozwiązywania gier 2x2.
" Rozwiązanie zaczyna się od poszukiwania punktu siodłowego.
" W przypadku jego braku są do wyboru dwie metody postępowania.
 Pierwsza - zwana rachunkową - prowadzi do celu drogą obliczeń.
 Druga - metoda graficzna - pozwala na pominąć rachunki.
Metoda rachunkowa
1. Po pierwsze szukamy punktu siodłowego.
2. Jeżeli go znajdujemy, to jest on rozwiązaniem
naszych poszukiwań.
3. Jeżeli punktu siodłowego nie ma, odrzucamy
strategie, które z punktu widzenia danego gracza
są podporządkowane innym strategiom.
4. Układamy z pozostałych strategii gry 2x2 aż do
momentu gdy znajdziemy wśród nich grę
spełniającą pewne szczególne wymagania.
Metoda rachunkowa - przykład
Tabela płatności
B1 B2 B3 B4
A1 -4 -2 3 4
A2 6 5 0 1
1. Gra nie posiada punktu siodłowego.
2. Szukamy teraz strategii podporządkowanych. Gracz B z pewnością zauważy że
nie opłaca mu się nigdy stosować strategii B4 gdyż przynosi mu ona wyniki
słabsze od strategii B3, niezależnie od tego, jakiej strategii użyje jego
przeciwnik.
3. Zatem usuwamy strategię B4 i ponownie przyglądamy się macierzy wypłat.
B1 B2 B3
A1 -4 -2 3
A2 6 5 0
Metoda rachunkowa
4. Z trzech pozostałych strategii gracza B można ułożyć 3 różne gry 2x2
(ogólnie - z n strategii można utworzyć (n*(n-1))/2 gier 2x2). Oto
one:
rozwiązaniem jest punkt siodłowy. Gracz A powinien
B1 B2
stosować tylko strategię A2, gracz B wyłącznie
A1 -4 -2
Gra I
strategię B2. Cena tej gry jest równa 5.
A2 6 5
B2 B3
korzystając z wyliczonych dla gracza A
Gra II
A1 -2 3
częstotliwości (0:1) liczymy cenę gry przeciw
A2 5 0
pozostałym strategiom gracza B. Jeżeli choć
raz wyliczona cena gry przeciw jednej z
pozostałych strategii gracza B będzie niższa od
ceny badanej gry 2x2, wówczas dana gra 2x2
B1 B3
Gra III
nie zawiera rozwiązania całej gry 2xn.
A1 -4 3
A2 6 0
Metoda graficzna
Tabela wypłat
b1 b2
a1 1 -4
a2 -1 1
a3 -6 9