A. Ogólne sformułowanie problemu
Dwaj gracze mogą w sytuacji konfliktowej podejmować róŜne decyzje (wybierać róŜne
strategie). Wybór strategii następuje jednocześnie i niezaleŜnie – gracze nie wiedzą jaką
strategię wybrał przeciwnik. W zaleŜności od wybranych strategii jeden z graczy odnosi zysk,
a drugi ponosi równą co do wartości stratę – jest to gra o sumie zero.
Zyski i straty moŜna przedstawić w postaci tabeli wypłat:
Gracz B
B
1
B
2
B
3
A
1
a
11
a
12
a
13
A
2
a
21
a
32
a
23
Gracz A
A
3
a
31
a
32
a
33
Zadaniem obu graczy jest taki wybór strategii (A
i
oraz B
j
) aby pewny zysk był jak największy
(ewentualna strata jak najmniejsza) - gracze postępują ostroŜnie, starając się znaleźć
najbezpieczniejsze strategie.
W pierwszym kroku następuje próba wyboru strategii czystych:
gracz A analizuje swoje strategie (A
i
) i dla kaŜdej znajduje minimalny zysk (Z
i
), teraz
porównując te wartości ze sobą wybiera tą strategię, gdzie Z
i
jest maksymalne (reguła
maxmin).
gracz B analizuje swoje strategie (B
j
) i dla kaŜdej znajduje maksymalną stratę (S
j
),
teraz porównując te wartości ze sobą wybiera tą strategię, gdzie S
j
jest minimalne
(reguła minmax).
Gdy obaj gracze znajdą to samo rozwiązanie maxmin = minmax, zagadnienie ma
rozwiązanie w zbiorze strategii czystych, a gra ma punkt siodłowy. Optymalny wybór dla
gracza A jest jednocześnie optymalnym wyborem dla gracza B - gracz A osiąga nie
największy, ale za to pewny zysk, gracz B co prawda traci, ale jest pewny, Ŝe strata nie będzie
większa.
Jeśli nie uda się znaleźć rozwiązania w zbiorze to strategii czystych, to naleŜy dobrać
strategie mieszane: określić z jakimi prawdopodobieństwami p
i
i jakich róŜnych strategii
czystych A
i
naleŜy uŜyć.
Niech gracz A uŜywa swoich strategii A
1
, A
2
i A
3
odpowiednio z prawdopodobieństwami p
1
,
p
2
i p
3
. Wtedy wygrana
ν
A1
gracza A, w przypadku gdy gracz B zastosuje strategię B
1
wyniesie
ν
A1
= p
1
* a
11
+ p
2
* a
21
+ p
3
* a
31
Analogicznie gdy gracz B zastosuje strategie B
2
oraz B
3
wygrane wyniosą
ν
A2
= p
1
* a
12
+ p
2
* a
22
+ p
3
* a
32
ν
A3
= p
1
* a
13
+ p
2
* a
23
+ p
3
* a
33
Oznaczmy wypadkową, nieznaną wygraną gracza A przez
ν
, wtedy warunek optymalności
wyboru prawdopodobieństw moŜna zapisać:
p
1
* a
11
+ p
2
* a
21
+ p
3
* a
31
≥
ν
p
1
* a
12
+ p
2
* a
22
+ p
3
* a
32
≥
ν
p
1
* a
13
+ p
2
* a
23
+ p
3
* a
33
≥
ν
ponadto
p
1
+ p
2
+ p
3
= 1
a funkcja celu
ν
– wygrana gracza A jest maksymalizowana.
PoniewaŜ nie znamy wartości
ν
, uwolnijmy się od niej dzieląc przez nią i wprowadzając
nowe zmienne x
i
= p
i
/
ν
x
1
* a
11
+ x
2
* a
21
+ x
3
* a
31
≥
1
x
1
* a
12
+ x
2
* a
22
+ x
3
* a
32
≥
1
x
1
* a
13
+ x
2
* a
23
+ x
3
* a
33
≥
1
ponadto
x
1
+ x
2
+ x
3
= 1/
ν
i powinno być minimalizowane.
To zagadnienie zostanie rozwiązane jako program liniowy.
Wartość
ν
nie powinna być ujemna, zatem wcześniej naleŜy tabelę wypłat zmodyfikować
dodając do kaŜdego elementu MIN(a
ij
). Po zakończeniu obliczeń wyliczoną wartość
ν
naleŜy
zmodyfikować odejmując od kaŜdego elementu tą liczbę.
B.
Przykład 1.
PoniŜej przedstawiono tabelę wypłat. Określić strategie graczy.
B
B1
B2
B3
A1
3
2
1
A2
4
1
-3
A
A3
5
0
-5
Rozwiązanie.
Dla gracza A MaxMin = a
13
(1)
Dla gracza B MinMax = a
13
(1)
PoniewaŜ MaxMin = MinMax istnieje rozwiązanie w zbiorze strategii czystych.
Przykład 2.
PoniŜej przedstawiono tabelę wypłat. Określić strategie graczy.
B
B1
B2
B3
A1
5
-2
1
A2
2
4
3
A
A3
1
2
5
Rozwiązanie.
W tym przypadku nie istnieje rozwiązanie w zbiorze strategii czystych. NaleŜy zatem
poszukiwać go w zbiorze strategii mieszanych. Program liniowy odpowiadający temu zadaniu
moŜna zapisać następująco:
warunki:
5x
1
+ 2x
2
+ x
3
≥
1
-2x
1
+ 4x
2
+ 2x
3
≥
1
x
1
+ 3x
2
+ 5x
3
≥
1
ponadto
x
1
+ x
2
+ x
3
→
max.
C. Struktura arkusza XLS
Do rozwiązania tego zagadnienia uŜyto dodatku SOLVER z arkusza MS EXCEL.
Przykładową strukturę arkusza przedstawia poniŜszy rysunek
Formuła wyliczająca minimalny
zysk dla danej strategii A
i
=MIN(E6:G6)
Formuła wyliczająca
MaxMin
=MAX(J6:J9)
Podobnie dla gracza B
Minimalny element tabeli
wypłat
=MIN(E6:G9)
Zmodyfikowana tabela wypłat
Poszukiwane
zmienne
=$D21*E21+$D22*E22+$D23*E23
=D21+D22+D23
Obliczone prawdopodobieństwa
=D21/$E$33
Funkcja celu po modyfikacji
1/E33+$E$18
D. Przebieg ćwiczenia.
1. Korzystając z opisanej struktury przygotować arkusz XLS i za pomocą SOLVERA
znaleźć rozwiązanie przykładowego problemu.
2. Zwiększyć liczbę moŜliwych strategii dla gracza A i odpowiednio modyfikując
arkusz znaleźć rozwiązanie problemu.