Ć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.