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.