Wykład - tw minimaksowe.pdf

(105 KB) Pobierz
(Microsoft Word - Wyk\263ad - tw minimaksowe.doc)
2.4 Twierdzenie minimaksowe Johna von Neumanna
BieŜący paragraf jest poświęcony centralnemu rezultatowi teorii gier
o sumie zerowej, a zarazem jednemu z fundamentalnych twierdzeń teorii
gier. Twierdzenie minimaksowe von Neumanna ma duŜe znaczenie dla
zastosowań teorii gier, ale z naszego (pasjonatów królowej nauk) punktu
widzenia jest przede wszystkim bardzo ciekawym wynikiem
matematycznym. Oto ono.
T WIERDZENIE MINIMAKSOWE VON N EUMANNA
1)
KaŜda gra macierzowa
<
A
*
,
B
*
,
M
>
ma wartość oraz
2)
KaŜdy z graczy ma co najmniej jedną strategię bezpieczeństwa
3)
Dowolna para strategii bezpieczeństwa graczy jest w równowadze
4)
Dowolna para strategii w równowadze tworzona jest przez strategie
bezpieczeństwa graczy
Od momentu jego opublikowania twierdzenie von Neumanna
wzbudziło znaczne zainteresowanie w społeczności matematyków czego
przejawem jest to, Ŝe doczekało się wielu zupełnie niezaleŜnych dowodów.
Idee tych dowodów sięgają do rozmaitych dziedzin matematycznych. Są
więc wśród nich dowody sięgające do róŜnych wersji twierdzeń o punkcie
stałym - twierdzenia Brouvera i twierdzenia Kokutaniego. Znane są bardzo
ciekawe dowody oparte na teorii zbiorów wypukłych (a dokładniej na
własności oddzielenia zbiorów wypukłych) oraz, w pewnym sensie z nimi
związany, dowód oparty na twierdzeniach z teorii programowania liniowego.
Na naszym wykładzie przedstawimy ten ostatni. Wydaje się być on
szczególnie ciekawy z praktycznego punktu widzenia, gdyŜ wskazuje się w
nim od razu efektywną metodę rozwiązywania gier o sumie zero. Co więcej
wyłania się z niego ogólna metoda znajdowania strategii i poziomów
W YKŁADY Z T EORII G IER I D ECYZJI
bezpieczeństwa gracza - przydatna takŜe w nieściśle antagonistycznych grach
macierzowych.
2.4.1 Programowanie liniowe
Przedstawmy więc pokrótce niezbędne przy dowodzie twierdzenia
minimaksowego pojęcia i twierdzenia z teorii programowania liniowego.
Zadaniem programowania liniowego (PL) nazywamy problem
maksymalizacji (minimalizacji) pewnej liniowej funkcji celu
F
:
R
m
®
R
określonej dla dowolnego wektora x wzorem
( ) ∑ =
m
F
x
=
c
j x
j
j
1
gdzie
c
=
[
c 2
1
,
c
2
,
,
c
m
] T
jest wektorem znanych współczynników.
Wektor [
x
=
x
1
,
x
2
,
2
,
x
m
] T
jest poddany n ograniczeniom postaci:
∑ =
k
ij
x
j
£
b
i
,
i
=
1
2
2
,
n
j
1
oraz spełnia tzw. warunki brzegowe
x
j
³
0
,
j
=
1 2
2
,
m
.
Zadanie optymalizacji liniowej polega na znalezieniu takiego wektora
x , który maksymalizuje (minimalizuje) funkcję celu F oraz spełnia
ograniczenia i warunki brzegowe.
Wektor x , który spełnia powyŜsze ograniczenia nazywamy wektorem
(rozwiązaniem) dopuszczalnym. Zbiór wszystkich rozwiązań dopuszczalnych
oznaczmy jako D x .
Tak przedstawiony problem nazwiemy problemem pierwotnym
programowania liniowego. Z kaŜdym takim problem związany jest problem
dualny. Problemem dualnym dla danego problemu pierwotnego jest problem,
Str. 2
m
647637097.006.png
 
A NDRZEJ Z. G RZYBOWSKI
którego zadaniem będzie znalezienie wektora
y
=
[
y
1
,
y
2
,
2
,
y
n
] T
, który
poddany jest poddany m ograniczeniom postaci:
∑ =
n
y
i
k
ij
³
c
j
,
j
=
1 2
,
m
i
1
oraz spełnia warunki brzegowe
y
i
³
0
,
i
=
1 2
,
n
oraz minimalizuje
(maksymalizuje) funkcje celu Q , która ma następującą postać:
( ) ∑ =
n
Q
y
=
b
i y
i
i
1
gdzie
b
=
[
b 2
1
,
b
2
,
,
b
] T
to wektor znanych współczynników.
Wektor y, który spełnia powyŜsze ograniczenia jest wektorem
(rozwiązaniem) dopuszczalnym. Natomiast zbiór wszystkich wektorów
dopuszczalnych będziemy oznaczać przez D y .
W teorii programowania liniowego dowodzi się prawdziwości
nast ę puj ą cych dwóch wa Ŝ nych twierdze ń .
T WIERDZENIE TM .1
KaŜdy niesprzeczny i ograniczony (dualny lub pierwotny) problem
programowania liniowego ma rozwiązanie.
T WIERDZENIE TM .2 ( O DUALNOŚCI )
Jeśli problem pierwotny zadania programowania liniowego ma
rozwiązanie, to rozwiązanie ma równieŜ odpowiadający mu problem dualny i
na odwrót. Co więcej, wartości obu funkcji celu w punkcie rozwiązania są
identyczne.
W następnym paragrafie wykorzystamy przedstawione wyniki do
dowodu twierdzenia minimaksowego.
Str. 3
647637097.007.png
 
W YKŁADY Z T EORII G IER I D ECYZJI
2.4.2 Dowód twierdzenia minimaksowego
Z wniosku 1 wiemy, Ŝ e strategia A * Î A * jest strategi ą bezpiecze ń stwa
gracza I wtedy i tylko wtedy, gdy
∑ =
m
w
=
min
M
A
*
j
i
j
i
i
1
gdzie w jest największą moŜliwą gwarantowaną wypłatą dla gracza I.
Spójrzmy na grę z pozycji gracza I. Dla kaŜdej ustalonej swojej
strategii AÎ A * rozwaŜa on związany z nią poziom wypłaty gwarantowanej
tj. wartość
∑ =
m
w
=
min
j
M
i
j
A
i
i
1
Chciałby on tak wybrać wektor A, aby zapewnić sobie maksimum
takich wypłat gwarantowanych, czyli uzyskać jak największą wielkość
w max
w
. Oczywiście musi uwzględnić fakt, Ŝe wektor A jest strategią
mieszaną czyli spełnia określone warunki. Podsumowując, szuka on wektora
A oraz jak największej wartości w spełniających warunki:
∑ =
m
1.
w
£
M
i
j
A , j =1,.., n
i
1
2.
A
³
0
, i =1,.., m
3.
∑ =
m
A
=
1
i
1
Przeformułujemy nieco ten problem. Na początek załóŜmy, Ŝe
wszystkie elementy macierzy M są dodatnie. MoŜemy tak uczynić bez straty
Str. 4
A
=
i
647637097.001.png 647637097.002.png 647637097.003.png
 
A NDRZEJ Z. G RZYBOWSKI
na ogólności dowodu, wynika to z własności funkcji uŜyteczności.
Z tego, Ŝe macierz M ma wszystkie elementy dodatnie wynika, Ŝe
dodatnia jest teŜ poszukiwana wartość w . Wprowadźmy nowe zmienne.
Niech
y
=
A
i
,
i
=
1
2
...,
m
(ws1)
i
w
ZauwaŜmy, Ŝe
∑
m
y
= ∑
m
A
i
=
1
. Zatem poprzedni problem
i
w
w
=
1
i
=
1
maksymalizacji wielkości w jest równowaŜny następującemu zadaniu PL:
= ∑ =
m
Funkcja celu:
Q y
(
)
y
i
¯
min
i
1
∑ =
m
Warunki ograniczające:
M
ij y
i
³
1
, j =1,…, n
i
1
Warunki brzegowe:
y
i
³
0
i
=
1
2
...,
m
Tak przedstawiony problem jest problemem dualnym
programowania liniowego. Problem ten pozwala nam znaleźć wartość dolną
gry.
Analogicznie moŜna przeformułować problem stojący przed graczem
II i otrzymać zadanie PL dla znalezienia wartości górnej gry. Jest ono
postaci:
= ∑ =
m
Funkcja celu:
F x
(
)
x
-
max
j
i
1
∑ =
n
Warunki ograniczające:
M
ij x
j
£
1
,
i
=
1 2
,
m
j
1
Str. 5
i
647637097.004.png 647637097.005.png
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin