Teoria Gier i Decyzj - w6.pdf

(127 KB) Pobierz
(Microsoft Word - Teoria Gier i Decyzj - dla student\363w.doc)
W YKŁADY Z T EORII G IER I D ECYZJI
Podstawowe koncepcje rozwiązania gry
Koncepcja strategii dominujących
D EFINICJA .
Dla gracza P k strategia i
a jest nie gorsza od strategii j
a jeŜeli dla
dowolnego wyboru strategii s i , i= 1 ,…,N i≠k graczy pozostałych zachodzi
M k ( s 1 , …, a i ,…, s N ) ≥ M k ( s 1 , …, a j ,…, s N )
D EFINICJA .
Dla gracza P k strategia a i jest lepsza od strategii a j jeŜeli jest nie gorsza i
ponadto istnieje pewien wybór strategii s i , i= 1 ,…,N, i≠k graczy pozostałych
dla którego zachodzi
M k ( s 1 , …, a i ,…, s N ) > M k ( s 1 , …, a j ,…, s N )
JeŜeli strategia a i jest lepsza od strategii a j to mówimy, Ŝe strategia a i
dominuje strategię a j oraz , Ŝe strategia a j jest dominowana przez strategię
a i .
D EFINICJA .
Strategię, która jest zdominowana przez inną strategię nazywamy strategią
niedopuszczalnĄ . W przeciwnym wypadku strategia nazywana jest
dopuszczalnĄ albo niezdominowanĄ .
Oczywiście gracz moŜe, a nawet powinien ograniczyć się do strategii
dopuszczalnych. Czasami okazuje się, Ŝe konsekwentne stosowanie
kryterium dominacji jednoznacznie wskazuje sposób wyboru strategii przez
dla graczy. Tak jest w następującym przykładzie.
P RZYKŁAD .
Dana jest gra
Str. 2
685051135.007.png
 
A NDRZEJ Z. G RZYBOWSKI
(
12
,
(
)
(
12
)
(
14
,
17
)
( ) ( ) ( ) ( )
( ) ( ) ( )
(
12
,
8
3
14
,
(
) ( ) ( ) ( )
−
3
15
8
18
0
11
4
9
19
5
10
1
10
17
,
JeŜeli gracze są racjonalni (czyli teŜ wiedzą, Ŝe takŜe drugi gracz
postępuje racjonalnie) i konsekwentnie stosują kryterium dominacji, to
kolejno otrzymujemy następujące postaci tej gry. PoniewaŜ gracz I ma
niedopuszczalna strategię nr 1 więc wystarczy rozwaŜać grę:
12
,
( ) ( ) ( )
8
3
14
,
(
−
3
15
)
(
18
)
(
0
11
)
(
4
)
(
19
)
(
10
)
(
10
)
(
7
PoniewaŜ obaj zdają sobie sprawę z tej sytuacji więc w zasadzie mamy
„nową” grę. W tej „nowej” grze gracz II ma niedopuszczalną strategię nr 4
zatem wystarczy ograniczyć się do kolejnej gry
(
12
,
(
6
(
(
−
3
15
)
(
18
)
(
0
11
)
(
19
)
(
10
)
(
10
)
Konsekwentnie rozumując w ten sposób ostatecznie otrzymujemy, grę
[ ]
(
Ostatecznie okazało się, Ŝe gracz I powinien wybrać strategię nr 2 a
gracz II strategię nr 3 ( w grze wyjściowej oczywiście).
NaleŜy jednak zauwaŜyć, Ŝe takie sytuacje w których moŜemy
wskazać optymalne postępowanie graczy jedynie poprzez stosowanie
koncepcji strategii niezdominowanych są bardzo rzadkie
Str. 3
(
685051135.008.png
 
W YKŁADY Z T EORII G IER I D ECYZJI
Koncepcja strategii bezpieczeństwa
D EFINICJA
Strategię
s Î
k S
nazywamy strategiĄ bezpieczeŃstwa gracza P k w grze
k
<
S
,
S
,
2
,
S
;
M
1
,
M
2
,
2
M
N
>
jeśli spełniony jest warunek:
1
2
N
min
M
k
(
s
,...,
s
*
,...,
s
)
=
max
min
M
k
(
s
,...,
s
,...,
s
)
(2.gmm)
s
Î
S
,
¹
k
1
k
N
s
Î
S
s
Î
S
,
i
¹
k
1
k
N
1
i
k
k
1
i
Z powodu warunku ją definiującego, strategie bezpieczeństwa nazywa się teŜ
często strategią maksyminowĄ .
D EFINICJA
Jeśli
s Î
k S
*
jest strategiĄ bezpieczeŃstwa gracza P k to wartość
k
v
=
min
M
k
(
s
,...,
s
*
,...,
s
)
nazywamy poziomem bezpieczeństwa tego
k
s
Î
S
i ¹
,
i
k
1
k
N
1
gracza.
Z definicji strategii bezpieczeństwa wynika, Ŝe jest to strategia, która
daje graczowi największa wypłatę gwarantowaną. Inaczej: bez względu na to
co zrobią pozostali gracze on dostanie co najmniej k
v i Ŝadna inna strategia
nie zagwarantuje mu więcej.
W przypadku gier macierzowych strategię bezpieczeństwa graczy
określa zatem warunki
- dla gracza P 1 :
min
M
1
0 j
=
max
min
M ij =
1
v
i
1
- dla gracza P 2
min
M
2
0
=
max
min
M ij =
2
v
ij
2
j
Zilustrujmy te pojęcia następującym przykładem. RozwaŜmy grę G1:
Str. 4
*
i
685051135.001.png 685051135.002.png
 
A NDRZEJ Z. G RZYBOWSKI
(
(
2
−
1
(
11
,
(
−
18
,
23
)
(
11
,
(
4
(
15
,
(
2
−
5
(
−
10
,
(
18
,
−
2
(
14
,
4
(
−
3
))
Dla gracza I wartości najgorsze jakie moŜe uzyskać stosując
poszczególne swoje strategie to -18 dla a 1 , 2 dla a 2 i -10 dla a 3 . Zatem
strategią bezpieczeństwa jest dla niego strategia a 2 a poziomem
bezpieczeństwa
v
1 =
2
. Analogicznie rozumując w przypadku gracza II
otrzymujemy, Ŝe w jego przypadku występują dwie strategie bezpieczeństwa
b 1 , oraz b 3 . Obie zapewniają ten sam poziom bezpieczeństwa
v
2 =
1
Zatem
widzimy, Ŝe moŜe być kilka strategii bezpieczeństwa i gracz moŜe mieć
kłopot z wyborem jednej z nich. MoŜe wtedy zastosować inne koncepcje
rozwiązania.
Koncepcja punktu równowagi
D EFINICJA .
Punktem równowagi w grze
<
S
,
S
,
2
,
S
;
M
1
,
M
2
,
2
M
k
>
nazywamy
1
2
N
układ strategii
(
s 2 , s i Î S i , dla którego zachodzi warunek: dla
1
,
s
2
,
,
s
N
)
dowolnego k i dowolnej strategii q Î S k ,
M
k
(
s
,...,
s
,
2 ³
,
s
)
M
k
(
s
,...,
q
,
2
,
s
)
1
k
N
1
N
Z powyŜszej definicji wynika, Ŝe Ŝadnemu z graczy nie opłaca się zmienić
swojej strategii z punktu równowagi na inną o ile pozostali nie zmieniĄ
swoich , gdyŜ w wyniku takiej zamiany nie mogą nic zyskać, mogą co
najwyŜej stracić.
W przypadku gry macierzowej
<
A
,
B
,
M
1
,
M
2
>
warunek z definicji
zapiszemy w postaci następującej: para strategii ( a i0 ,b j0 ) jest punktem
równowagi z definicji wtedy, gdy dla dowolnych i= 1,…, m, j =1,…, n ,
Str. 5
685051135.003.png 685051135.004.png 685051135.005.png
 
W YKŁADY Z T EORII G IER I D ECYZJI
zachodzi
M
1
(
a
,
b
)
£
M
1
(
a
,
b
)
Ù
M
2
(
a
,
b
)
£
M
2
(
a
,
b
)
i
0
0
0
i
0
j
0
j
0
O takiej parze strategii mówimy często, Ŝe są w równowadze.
RozwaŜmy ponownie grę G1
(
(
2
−
1
(
11
,
(
−
18
,
23
)
(
11
,
(
4
(
15
,
(
2
−
5
(
−
10
,
(
18
,
−
2
(
14
,
4
(
−
3
))
W powyŜszej grze parą strategii w równowadze jest para ( a 2 ,b 3 ) . Jest
oczywiste, Ŝe Ŝadnemu z graczy nie opłaca się zamienić strategii
występującej w tej parze na jakąkolwiek inną, jeśli drugi nie zmieni swojej
strategii równowagi. Mówiąc jeszcze inaczej, jeśli jeden z graczy będzie się
upierał przy swojej strategii równowagi to ma zagwarantowaną przynajmniej
taka wypłatę jaka w punkcie równowagi jest dla niego określona. Jeśli drugi
z graczy zmieni swoją strategię, to pierwszy z nich i tak dostanie to co ma
zagwarantowane, zaś drugi na zamianie moŜe tylko stracić. Zatem koncepcja
przyjęcia tej pary jako rozwiązania problemu wyboru strategii przez graczy
wydaje się być oczywista. ZauwaŜmy ponadto, Ŝe obie te strategie są
strategiami bezpieczeństwa graczy. Czy zatem zawsze jest tak, Ŝe pary
strategii w równowadze tworzone są przez strategie bezpieczeństwa graczy?
Gdyby tak było to byłyby to mocny argument za ich wyborem. Jednak nie
zawsze tak jest. Problem moŜe pojawić się wtedy gdy punktów równowagi
jest więcej, tak jak w kolejnej grze danej macierzą
(
2
(
2
−
1
(
20
,
2
(
−
18
,
23
)
(
11
,
(
)
(
−
5
(
2
−
5
(
10
,
(
−
2
(
14
,
4
(
Str. 6
j
i
j
i
685051135.006.png
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin