Ćwiczenie 1
GRY MACIERZOWE O SUMIE ZEROWEJ
STRATEGIE CZYSTE
1. Wprowadzenie
Centralnym punktem wszelkich procesów decyzyjnych jest konflikt
interesów jawnie lub niejawnie (natura) biorących udział w tym procesie
decydentów (graczy). Sytuacja konfliktowa jest wynikiem faktu, iŜ wszystkie
działania (decyzje) wpływają w określony sposób na wynik procesu, który z
kolei jest róŜnie oceniany przez decydentów. Przyczyną konfliktu moŜe być nie
tylko kolizja interesów poszczególnych graczy, ale ograniczenia informacyjne
istniejące w procesie, które uniemoŜliwiają porozumienie się lub przynajmniej
sygnalizowanie zachowań. W przypadku problemów o sumie zerowej sytuacja
konfliktowa jest najbardziej klarowna, wygrana jednego z graczy jest przegraną
drugiego, a porozumienie jest całkowicie niemoŜliwe.
Ściślej z grą o sumie zerowej mamy do czynienia wówczas, gdy
określony jest tylko jeden wskaźnik kosztów (funkcja celu), przy czym jeden z
graczy ma na celu minimalizację, a drugi maksymalizację tego wskaźnika.
JeŜeli gracze podejmują decyzje w tym samym momencie, lub ogólniej rzecz
biorąc, porządek podejmowania decyzji nie jest istotny dla przebiegu procesu,
gra jest statyczna. JeŜeli zbiór moŜliwych do podjęcia decyzji kaŜdego z graczy
jest skończony, mówimy o grze skończonej. PoniewaŜ jest on wówczas zbiorem
dyskretnym, mamy do czynienia z dyskretnym procesem decyzyjnym. W grze o
sumie zerowej moŜe brać udział tylko dwóch graczy. Tematem tego ćwiczenia
są właśnie statyczne skończone (dyskretne) gry o sumie zerowej (dwuosobowe).
- 8 -
2. Podstawowe definicje i własności
Skoro zbiory decyzji graczy są dyskretne moŜna je utoŜsamiać z
kolejnymi liczbami naturalnymi, a sam proces decyzyjny z wyborem jednej z
tych liczb. Wynikiem wyboru przez gracza D
1
liczby i, a gracza D
2
liczby j jest
zatem rezultat a
ij
. Przypuśćmy, Ŝe gracz D
1
ma n, a gracz D
2
m moŜliwych
decyzji. Zbiór wszystkich moŜliwych rezultatów gry tworzy zatem tablicę
(macierz) o wymiarach n x m, decyzje gracza D
1
definiujemy jako wiersze tej
tablicy (macierzy), a D
2
- kolumny. Stąd tego typu proces decyzyjny nazywany
jest grą macierzową o sumie zerowej i całkowicie reprezentowany jest przez
macierz A={a
ij
} gry (postać normalna statycznej skończonej gry o sumie
zerowej). Dla skupienia uwagi przyjmujemy, Ŝe zadaniem gracza D
1
jest
minimalizacja, a D
2
maksymalizacja wskaźnika jakości. Racjonalnym
postępowaniem
obu
decydentów
jest
zatem
poszukiwanie
strategii
bezpiecznych. MoŜna je określić w następujący sposób:
Strategią bezpieczną gracza D
1
jest wybór wiersza i
o
zapewniający, Ŝe:
j
i j
j
ij
Max a
Max a
o
≤
dla dowolnego i=1,2,...,n
Strategią bezpieczną gracza D
2
jest wybór kolumny j
o
zapewniający, Ŝe:
i
ij
i
ij
Min a
Min a
0
≥
dla dowolnego j=1,2,..., m
Wynikające z uŜycia tych strategii rezultaty noszą nazwę poziomów
bezpieczeństwa, odpowiednio
S
dla D
1
i
S
dla D
2
, przy czym zachodzi
(spróbuj udowodnić):
i
ij
j
i j
Min a
S
S
Max a
o
o
=
≤
=
MoŜna wykazać, Ŝe dla obu graczy istnieje jeden i tylko jeden poziom
bezpieczeństwa i co najmniej jedna (ale niekoniecznie jedna) strategia
bezpieczna.
Stosowanie przez graczy strategii bezpiecznych gwarantuje, Ŝe wynik gry
będzie naleŜał do przedziału 〈
〉
S S
,
. Nie znaczy to jednak, iŜ po takich
zagraniach decydenci są zadowoleni z wyniku, co świadczyłoby o równowadze
w grze.
Dla przykładu rozpatrzmy grę macierzową:
- 9 -
D
2
D
1
1
2
3
4
1
1
3
3
-2
2
0
-1
2
1
3
-2
2
0
0
w której strategiami bezpiecznymi dla D
1
są i
o1
=2 oraz i
o2
=3, a odpowiadający
im poziom bezpieczeństwa wynosi
S = 2
, zaś dla gracza D
2
, j
o
= 3 i S=0. Jeśli
gracze wybiorą parę (i
o1
, j
o
), to wynik będzie 2, jeśli zaś (i
o2
,j
o
), to 0. Jednak
jeśli D
2
będzie wiedział, Ŝe D
1
wybiera i
o2
=3 to zagra j=2 co da wynik 2. Z kolei
gdyby D
1
był pewien, Ŝe D
2
zagra j
o
=3, to wybierze i
o1
=3, co prowadzi do
wyniku 0. W kaŜdym przypadku po grze, któryś z graczy nie będzie
zadowolony, co świadczy o braku równowagi w grze. Przyczyną tego nie jest
bynajmniej niejednoznaczność strategii bezpiecznych. MoŜna to zauwaŜyć na
kolejnym przykładzie:
D
2
D
1
1
2
3
1
4
0
-1
2
0
-1
3
3
1
2
1
Strategiami bezpiecznymi są tu i
o
=3, j
o
=1 a odpowiednie poziomy wynoszą
S
S
=
=
2
0
,
. Zagrania bezpieczne obu graczy dają wynik gry równy 1. Z kolei
gdyby kaŜdy z graczy był pewny Ŝe przeciwnik wybierze strategię bezpieczną,
to wybrałby decyzję inną niŜ wynika ze strategii bezpiecznej np. D
1
wybrałby
i=1, zaś D
2
, j=2.
Inaczej rzecz się ma w następującym przykładzie:
D
2
D
1
1
2
1
3
1
2
-1
1
- 10 -
Strategie bezpieczne wynoszą odpowiednio i
o
=2, j
o
=2, a poziomy
bezpieczeństwa są sobie równe i wynoszą 1. Po grze, w której obaj gracze
wybiorą strategie bezpieczne Ŝaden z nich nie będzie czuł niedosytu, bo
jakiekolwiek jednostronne odstępstwo od strategii bezpiecznej prowadziłoby do
pogorszenia rezultatu dla gracza, który je zaryzykował. Mamy więc do
czynienia z równowagą zwaną punktem siodłowym gry, a strategie graczy
zwane są strategiami punktu siodłowego (równowagi siodłowej). Natomiast o
procesie mówimy, Ŝe posiada punkt równowagi siodłowej w strategiach
czystych.
Ściślej rzecz biorąc, będziemy mówili, Ŝe strategie i
o
, j
o
są strategiami
równowagi siodłowej, jeśli dla wszystkich i=1,2,..., n, j=1,2,..., m. zachodzi:
a
a
a
i j
i j
ij
o
o o
o
≤
≤
Wynik
S
a
i j
o o
=
jest wartością punktu siodłowego.
Warunkiem koniecznym i wystarczającym istnienia równowagi jest równość
poziomów bezpieczeństwa obu graczy (udowodnić). Warunek ten moŜna
zapisać w postaci:
S =
a = S =a
=
a = S
i
j
ij
i j
j
i
ij
o o
min max
max min
a zatem warunkiem istnienia punktu siodłowego jest przemienność operacji
minimalizacji i maksymalizacji wykonywanych na elementach macierzy A.
Łatwo zauwaŜyć, Ŝe strategie równowagi muszą być strategiami bezpiecznymi i
tym samym nie muszą być określone jednoznacznie. Skoro jednak wartość
punktu siodłowego jest określona jednoznacznie, to musi zachodzić własność
wymienialności strategii równowagi, którą moŜna sformułować następująco:
Jeśli pary (i
1
, j
1
) oraz (i
2
, j
2
) są strategiami równowagi siodłowej, to
równieŜ są nimi pary (i
1
, j
2
) i (i
2
, j
1
) (wykazać).
MoŜna zastanowić się co naleŜy zrobić, jeśli warunek S=S nie zachodzi
i występuje tzw. szczelina, tzn. S < S
, nie ma zatem rozwiązania w klasie
czystych strategii rozwaŜanych dotychczas. Jedną z moŜliwości jest
wprowadzenie hierarchii, tzn. przyjęcie, iŜ jeden z graczy czeka na zagranie
drugiego i wówczas odpowiada najkorzystniejszą dla siebie strategią. Gracz,
który zagrywa jako pierwszy musi wybrać strategię bezpieczną, gra jednak
przestaje być statyczną, poniewaŜ gracz działający jako drugi korzysta
„dynamicznie” ze znajomości decyzji swego przeciwnika.
- 11 -
3. Program ćwiczenia
W trakcie realizacji ćwiczenia studenci korzystają z programu
komputerowego pozwalającego na znajdowanie rozwiązań gier macierzowych o
sumie zerowej.
1. Zapoznać się z obsługą i działaniem programu gry.exe.
2. Dla podanej przez prowadzącego gry macierzowej znaleźć:
a) strategie bezpieczne oraz poziomy bezpieczeństwa graczy
b) sprawdzić istnienie punktu siodłowego
c) zbadać wpływ zmiany ról (minimalizacja, maksymalizacja) graczy
biorących udział w grze
3. Skonstruować macierz gry mxn (m, n > 4), w której kaŜdy z graczy posiada
kilka strategii bezpiecznych, a poziomy bezpieczeństwa dla obu graczy są
róŜne.
a) przedyskutować wpływ wyboru róŜnych strategii bezpiecznych na
wynik gry
b) pokazać w jaki sposób naleŜy zmodyfikować macierz gry, aby istniały:
pojedyncze strategie bezpieczne dla obu graczy.
punkt równowagi siodłowej
c) określić wpływ wprowadzenia hierarchii (dynamiki) na wynik gry
4. Przedstawić wybrany proces decyzyjny jako dwuosobową grę macierzową o
sumie zerowej. Znaleźć jego rozwiązanie i przedyskutować własności.
LITERATURA
1. Basar T., Olsder G. J.: Dynamic Noncooperative Game Theory, Academic
Press, London, 1982
2. Luce R. D., Raiffa H.: Gry i decyzje. PWN, Warszawa 1967.
3. Świerniak A.: Podejmowanie decyzji w sytuacjach konfliktowych. Skrypt
Uczelniany Politechniki Śląskiej Nr 1791, Gliwice 1993.