teoria gier, Ekonomia&Matematyka
[ Pobierz całość w formacie PDF ]
Kazimierz Cegiełka
SzkołaGłówna Słuzby Pozarniczej, Warszawa
Teoria gier o sumie zerowej z MuPADem
W zyciu codziennym spotykami si
˛
ezróznymi rodzajami gier. Pojawiaj
˛
asie
gry: zr ecznosciowe, hazardowe, salonowe, karciane, komputerowe, decyzyjne, symu-
lacyjne, macierzowe. W dalszej cz esci zajmowa´csi
˛
ebedziemy tylko grami macie-
rzowymi.
Jako pocz atek teorii gier przyjmuje si
˛
eukazaniesie monografii: John von Neu-
mann i Oskar Morgenstern (urodzony na Sl asku, ekonomista), Theory of Games
and Economic Behavior, Princeton University Press 1944 (Niemal cał a monograf
i
˛
e1200stronnapisał von Neumann, Morgenstern natomiast napisał przedmow e
izredagował całos
´
ctak,ze ksi azka wywołała poruszenie wsród matematyków i
ekonomistów.) Ponowny rozwój teorii gier nast apił wtedy, gdy w roku 1994 nagrod e
Nobla z ekonomii otrzymali: John Nash, John Harsányi i Reinhard Selten za okresle-
nie równowagi w grach niekooperacyjnych. Nagroda ta została ustanowiona w roku
1968 jako Nagroda Centralnego Banku Szwecji w dziedzinie Nauk Ekonomicznych
imienia Alfreda Nobla. Nobel w swoim testamencie z roku 1894 nie utworzył na-
grody z ekonomii. Po przyznaniu nagrody w roku 1994 rozszerzono jej zakres na
inne dziedziny nauk społecznych (socjologia, psychologia).
Teoria gier jest cz esto kojarzona z matematyczn ateoriakonfliktu.
B edziemy zajmowa
´
csi
˛
egłównie grami strategicznymi. Aby mówi
´
cogrze,musi
byc co najmniej dwóch graczy. Graczem nie koniecznie musi by´cczłowiek. Ka zdy
gracz dysponuje pewnym zbiorem strategii, przy czym kazdy gracz zna strate-
gie przeciwnika. Poszczególny gracz nie wie, któr a strategi
˛
ewybierzeprzeciwnik.
Wyborowi kazdej strategii towarzyszy wielkosc liczbowa, zwana wypłat a.Wprzy-
padku dwóch graczy mamy wi ec nast epuj ac
˛
asytuacje. Załózmy, ze gracz A dys-
ponuje strategiami A
1
,A
2
, ..., A
n
, a gracz B dysponuje strategiami B
1
,B
2
, ..., B
m
.
Dowolnemu wyborowi strategii (A
i
,B
j
) odpowiada wypłata (a
i
,b
j
),przyczyma
i
i b
j
s a liczbami rzeczywistymi. Par e (a
i
,b
j
) nazywamy wynikiem wyboru strategii
A
i
przez gracza A i strategii B
j
przez gracza B.
Teoria gier (jak kazda teoria matematyczna) opiera si
˛
enapewnychzałozeniach.
Rozwazmy tak
˛
asytuacje, ze kazdy z graczy d azy do uzyskania najwi ekszej efekty-
wnosci (wygranej). Zwrócmy uwag e, ze załozenie to nie zawsze jest spełnione (np.
w grze przeciwko naturze nie mozemy nawet załozyc, ze natura b edzie zachowywała
si e w sposób racjonalny).
Przykład 1.Rozwazmy gr
˛
edwóchgraczyAiB,zktórychkazdy dysponuje
dwoma strategiami odpowiednio A
1
, A
2
i B
1
,B
2
. Przyjmijmy, ze gr
˛
et
˛
eopisuje
nast epuj aca tabela
Gracz B
B
1
B
2
Gracz
A
1
(10,
−
3) (4,
−
7)
A A
2
(−4, 2) (−5, 1)
Przyjmujemy, ze pierwsza liczba w parze uporz adkowanej oznacza wygran a gracza
A. Wobec tego, jesli np. gracz A wybierze strategi e A
2
, a gracz B wybierze strategi e
1
B
1
, to wtedy gracz A otrzymuje wygran
˛
awwysokosci −4, zas gracz B wygran a
wwysokosci 2.
A. Gry o sumie zerowej
Na III konferencji o MuPADzie b edziemy zajmowa
´
csie tylko grami o sumie
zerowej. Je´sliteoriagierspotkasie z zainteresowaniem, to innym rodzajom gier
b edzie mozna poswi eci
´
cczes
´
czaje
´
cnanastepnej konferencji.
Rozwazmy gr e, w której uczestnicz a gracze A i B. Załózmy, ze gracz A dysponuje
strategiami A
1
,A
2
, ..., A
n
, a gracz B dysponuje strategiami B
1
,B
2
,...,B
m
. Jak wiemy,
dowolnemu wyborowi strategii (A
i
,B
j
) odpowiada wypłata (a
i
,b
j
), przy czym a
i
i b
j
s a liczbami rzeczywistymi. Gr
˛
etak
˛
anazywamygr a o sumie zerowej (krótko: gr a
zerow a), gdy
a
i
+ b
j
=0dla i ∈ {1, 2, ..., n},j∈ {1, 2, ..., m} .
Wobec tego wygrane obu graczy s a liczbami przeciwnymi. W takiej sytuacji
mozna podawa´ctylkowygranejednegozgraczy,gdyz wygrana drugiego gracza jest
liczb a przeciwn a. Zwykle podaje si e wygrane gracza A. Otrzymujemy wi ec macierz
W wypłat w tej grze, gdzie
w
11
w
12
... w
1
m
(1) W =
w
21
w
22
... w
2
m
... ... ... ...
w
n
1
w
n
2
... w
nm
.
przy czym w
ij
oznacza wygran a gracza A.
Przykład 2.Macierzwypłat
"
#
10 −69
−502
W =
oznacza, ze gracz A dysponuje dwiema strategiami A
1
i A
2
, a gracz B ma do dys-
pozycji trzy strategie B
1
,B
2
i B
3
. Przy strategii np. (A
2
,B
3
) gracz A otrzymuje
wygran awwysokosci 2, a gracz B w wysokosci −2. Przy strategii (A
1
,B
2
) gracz A
otrzymuje wygran a −6, a gracz B otrzymuje wygran a6.
Przykład 3 Załózmy, ze
mamy gr e o sumie zerowej o macierzy wypłat:
Gracz B
B
1
B
2
A
1
4 −5
Gracz
A
2
1 4
A A
3
−6 8
Oznacza to, ze jesli np. Gracz A wybierze strategi e A
3
,aGraczBwybierze
strategi e B
2
, to Gracz A wygra 8, a Gracz B przegra 8. Jesli Gracz A wybierze A
3
,
aGraczBwybierzeB
1
, to Gracz A przegra 6, a Gracz B wygra 6. Zakładamy, ze
obaj gracze pragn awygra
´
cmozliwie najwi ecej, przy czym obaj post epuj awsposób
racjonalny.
Zatem Gracz A moze najwi ecej wygrac 8. Tym samym powinien wybra
´
cstrate-
gi e A
3
. Ale Gracz B to podejrzewa i wobec tego zagra B
1
(bomawtedywygrana
równ a 6). Gracz A, przewiduj ac to, powinien zagrac A
1
(ma wtedy najwi eksz a
wygran
˛
arówna 4). W tej sytuacji Gracz B winnien zagrac B
2
(ma wówczas na-
jwi eksz
˛
awygran
˛
arówna 5). Lecz w sytuacji, gdy Gracz B wybierze strategi e B
2
,
to wtedy Gracz A zagra A
3
(bo wtedy ma najwi eksz awygranarówna 8). Jestesmy
2
wi ec na pocz atku rozumowania i post epowanie mozna kontynuowac.
Podobnie jest, gdy gr e rozpoczyna Gracz B: Aby wygra´cnajwiecej wybiera B
1
.
Wówczas Gracz A, przewiduj ac to, wybierze A
1
(ma wtedy najwi eksz
˛
awygrana
równ a4).Mamywiec to co wyzej.
Zauwazmy, ze Gracz A wybiera najwi eksz a liczb ewsród wierszy macierzy wypłat,
a Gracz B wybiera najmniejsz aliczb
˛
ewsród kolumn macierzy wypłat.
Przykład 3 wskazuje, ze nalezy poda´ckryteria,którepozwolauznac, ze gra jest
zakonczona. Jednym z takich jest kryterium punktu siodłowego. Opiera si
˛
eonona
nast epuj acym fakcie dotycz acym funkcji dwóch zmiennych.
Załózmy, ze D ⊂
R
i f, g: D →
R
s a takimi funkcjami, ze f (x)
6
g (x) dla x ∈D.
Wceluunikniecia rozwaza´ndotyczacych nierównosci mi edzy nieskonczonosciami,
załózmy, ze funkcje f i g s a ograniczone. Wówczas z okreslenia kresu dolnego i kre-
su górnego funkcji mamy
sup
x∈D
f (x)
6
sup
x∈D
g (x), inf
x∈D
f (x)
6
inf
x∈D
g (x) .
Przypominamy, ze: M =sup
a∈A
A (M ∈
R
) wtedy i tylko wtedy, gdy:
V
1)
a
6
M,
a∈A
V
W
2)
a>M−ε;
ε>
0
a∈A
oraz
m =inf
V
a∈A
A (m∈
R
) wtedy i tylko wtedy, gdy
1)
a
>
m,
a∈A
W
2)
a<m+ε
ε>
0
a∈A
Twierdzenie 1. Jesli X ⊂
R
,Y⊂
R
i f : X × Y →
R
jest dowoln a funkcj a
ograniczon a, to
sup
x∈X
y∈Y
f (x, y)
6
inf
y∈Y
sup
x∈X
f (x, y) .
Dowód. Z definicji kresu górnego mamy dla kazdego (x, y) ∈X × Y
f (x, y)
6
sup
x∈X
f (x, y)
Wob e c t e go
inf
y∈Y
f (x, y)
6
inf
y∈Y
sup
x∈X
f (x, y) .
Poniewa z prawa strona jest stała, wi ec
sup
x∈X
y∈Y
f (x, y)
6
inf
y∈Y
sup
x∈X
f (x, y) .
Definicja.Punkt(x, y) nazywamy punktem siodłowym funkcji f wtedy i tylko
wtedy, g
d
y dla
ka
z
d
ego (x
, y
) ∈X × Y
f (x, y)
6
f (x, y)
6
f (x, y) .
John von Neumann przy załozeniu zwarto
´
sciiwypukłosci zbiorów X i Y udowod-
nił, ze f spełniaj aca pewne własnosci dotycz ace ci agło´sciiwypukłosci ma punkt
siodłowy. Dowód tego twierdzenia opiera sie na nastepuj acym lemacie, którego
dowód pomijamy.
Lemat. Funkc j a f: X × Y →
R
ma punkt siodłowy wtedy i tylko wtedy, gdy
istniej a minimaksy
3
V
inf
inf
ma
X
in
Y
f (x, y), mi
Y
su
X
f (x, y)
iliczbytesarówne,czylima
X
in
Y
f (x, y)=mi
Y
su
X
f (x, y) .
St ad w przypadku teorii gier przyjmuje si
˛
enastepuj ac a definicj e:
Definicja. Gra o sumie zerowej i macierzy wypłat [w
ij
] ma punkt siodłowy
wtedy i tylko wtedy, gdy
max
i
w
ij
} =min
j
{max
i
w
ij
}.
Wówczas liczb e max
i
{min
j
w
ij
}(= min
j
{max
i
w
ij
}) nazywamy wartosci apunktusio-
dłowego.
Gr e nazywamy gr
˛
azamkniet a, gdy ma ona punkt siodłowy. Gr e bez punktu
siodłowego nazywamy gr aotwarta.
Przykład 4. Rozwazmy gr e o sumie
zerowej i macierzy wypłat
Gracz B
B
1
B
2
B
3
B
4
A
1
5 2 6 3
Gracz
A
2
−
9 1
−
3
−
4
A
A
3
6
−
3 5 6
A
4
8 −5 1 0
W celu ustalenia, czy gra ta ma punkt siodłowy, wyznaczamy minimum wierszy,
maksimum kolumn, a nast epnie wyznaczamy maksimum z minimum wiersza oraz
mi
nimum z maksimum kolumn. Mozna zapisywa
´
ctownastepuj acej postaci:
Gracz B minimum
B
1
B
2
B
3
B
4
wiersza
A
1
5
2 6 3
2 ←− maksimin
Gracz A
2
−9
1 −3 −4
−9
A
A
3
6
−3 5 6
−3
A
4
8
−5 1 0
−5
maksimum
8
2 6 6
kolumny ↑
minimaks
Powy zsza gra ma wi ec punkt siodłowy. Punkt ten jest realizowany przez strategi e
A
1
(Gracz A) oraz stategi e B
2
(Gracz B) i odpowiada mu wartos´c2.Liczbatama
nast epuj ac awłasnos
´
cwtejgrze:
jesli Gracz A wybierze strategi e A
1
,tomazapewnion
˛
awygran
˛
aconajmniej
równ
˛
a2(jesli Gracz B wybierze B
1
, to gracz A wygrywa 5; jesli Gracz B wybierze
B
2
,toGraczAwygrywa2;jesli Gracz B wybierze B
3
,toGraczAwygrywa6ijesli
Gracz B wybierze B
4
,toGraczAwygrywa3);
jesli Gracz B wybierze strategi e B
2
,tomazapewnion
˛
awygran
˛
aconajmniej
równ a −2 (jesli Gracz A wybierze A
1
, to Gracz B wygrywa −2; jesli Gracz A
wybierze A
2
, to Gracz B wygrywa −1;j sli Gracz A wybierze A
3
,toGraczB
wygrywa 3; jesli Gracz A wybierze A
4
, to Gracz B wygrywa 5).
Zatem strategia (A
1
,B
2
) jest wi ec strategi a najbezpieczniejsz
˛
adlaobugraczy.
Strategie o tej własnosci nazywa´cbedziemy strategiami optymalnymi.
4
{min
j
Wobec tego przyjmuje si
˛
enastepuj acy sposób post epowania:
Kryterium punktu siod÷owego:Jesli gra ma punkt siodłowy, to obaj gracze
powinni wybra
´
cstrategiedajace punkt siodłowy.
Nie kazda gra o sumie zerowej ma punkt siodłowy (np. gry w przykładach 2
i3niemaja punktu siodłowego). W przykładzie 4 omówilismy własnos
´
cpunktu
siodłowego. W przypadku dowolnej gry o sumie zerowej przyjmijmy:
Definicja.Załózmy, ze w grze o sumie zerowej wyst epuj a gracze A i B. Jesli
istnieje liczba w taka, ze Gracz A ma strategi
˛
ezapewniajac
˛
amuwygranieconaj-
mniej w,aGraczBmastrategi
˛
ezapewniajac a,
˙
zeGraczAniewygrawiecej ni z w,
to liczb e w nazywamy wartosci atejgry.
Jesli gra ma punkt siodłowy, to jego wartosc jest wartosci agry. Ponizsze twierdze-
nie przyjmiemy bez dowodu.
Twierdzenie (orównowaznosci i wymiennosci ). Kazde dwa punkty siodłowe
tej samej gry maj
˛
at
˛
esam
˛
awartosc. Jesli Gracz A iGraczB wybior
˛
astrategie
zawieraj acepunktysiodłowe, to wartosci agrybedzie punkt siodłowy.
Przykład 5. Gracze A i B wybieraj
˛
ajedn
˛
aliczb
˛
esposród liczb ze zbioru
{1, 2, 3, 4, 5}.Jsli pierwszy z nich wybrał liczb e x, a drugi liczb e y,topierwszy
gracz otrzymuje od przeciwnika x−y zł,gdyx
>
y,apłaci przeciwnikowi x + y zł,
gdy x<y. Oznaczmy przez A
i
strategi e, ze gracz A wybrał liczb e i oraz oznaczmy
przez B
j
strategi e, ze gracz B wybrał liczb e j (i ∈ {1, 2, 3, 4, 5}, j ∈ {1, 2, 3, 4, 5}).
Wówczas macierz awypłat tej gry jest macierz (jest to macierz wypłat Gracza A)
0 −3 −4 −5 −6
W =
10−5 −6 −7
210−7 −8
3210−9
43210
Gramapunktsiodłowy (strategie pi ate). Wartosc gry jest równa 0.
Do wyznaczenia punktu siodłowego mo zna oczywiscie uzyc programu MuPAD.
Wtymceluposługujemy si
˛
emacierz
˛
awypłat. Jednym ze sposobów wprowadzenia
macierzy jest polecenie
W:=matrix(5,5,[[0,-3,-4,-5,-6],[1,0,-5,-6,-7],[2,1,0,-7,-8],[3,2,1,0,-9],[4,3,2,1,0]])
przy czym liczby 5, 5 wskazuj a wymiar macierzy (pierwsza liczba to liczba wierszy,
a druga to liczba kolumn), w nawiasach kwadratowych wypisujemy kolejne wiersze.
Mozna zrezygnowac z podawania wymiaru macierzy, gdyz MuPAD na podstawie
nawiasów kwadratowych odgadnie wymiar macierzy.
Polecenie
W[i,j]
zwraca wyraz macierzy W w i−tym wierszu oraz j−tej kolumnie. Zatem
W[2, 3];
5
okresla wyraz w drugim wierszu i trzeciej kolumnie. Wobec tego polecenie
min(W[i,j]$i=1..5)$j=1..5;
podaje
0
3
,−
5
,−
7
,−
9
5
,−
[ Pobierz całość w formacie PDF ]