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.
TWIERDZENIE MINIMAKSOWE VON NEUMANNA
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
WYKA
ADY Z TEORII GIER I DECYZJI
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 : Rm R
określonej dla dowolnego wektora x wzorem
m
F(x) = x
"c j j
j=1
T
gdzie c = [c1,c2 ,K,cm] jest wektorem znanych współczynników.
T
Wektor x = [x1, x2 ,K, xm ] jest poddany n ograniczeniom postaci:
m
x d" bi , i = 1,2,K, n
"kij j
j=1
oraz spełnia tzw. warunki brzegowe x e" 0 , j = 1,2,K,m .
j
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 Dx.
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
ANDRZEJ Z. GRZYBOWSKI
T
którego zadaniem będzie znalezienie wektora y = [y1, y2 ,K, yn] , który
poddany jest poddany m ograniczeniom postaci:
n
yikij e" c , j = 1,K, m
" j
i=1
oraz spełnia warunki brzegowe yi e" 0 , i = 1,K, n oraz minimalizuje
(maksymalizuje) funkcje celu Q, która ma następującą postać:
n
Q(y) = yi
"bi
i=1
T
gdzie b = [b1,b2 ,K,bn] 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 Dy.
W teorii programowania liniowego dowodzi się prawdziwości
następujących dwóch wa\
nych twierdzeń.
TWIERDZENIE TM.1
Ka\
dy niesprzeczny i ograniczony (dualny lub pierwotny) problem
programowania liniowego ma rozwiÄ…zanie.
TWIERDZENIE 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
WYKA
ADY Z TEORII GIER I DECYZJI
2.4.2 Dowód twierdzenia minimaksowego
Z wniosku 1 wiemy, \
e strategia ą""A* jest strategią bezpieczeństwa
Ä…
Ä…
Ä…
gracza I wtedy i tylko wtedy, gdy
m
w = min Ä…i*
"M i
j
j
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* rozwa\
a on związany z nią poziom wypłaty gwarantowanej
Ä…
Ä…
Ä…
tj. wartość
m
wÄ… = min Ä…i
"M i
j
j
i=1
Chciałby on tak wybrać wektor ą, 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 Ä… jest strategiÄ…
Ä…
Ä…
Ä…
mieszaną czyli spełnia określone warunki. Podsumowując, szuka on wektora
ą oraz jak największej wartości w spełniających warunki:
Ä…
Ä…
Ä…
m
1. w d" Ä…i , j=1,..,n
"M i
j
i=1
2. Ä…i e" 0 , i=1,..,m
m
3. = 1
"Ä…i
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
ANDRZEJ Z. GRZYBOWSKI
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. Wprowadz
my nowe zmienne.
Niech
Ä…i
yi = , i = 1,2...,m (ws1)
w
m m
Ä…i 1
Zauwa\
my, \
e yi = = . Zatem poprzedni problem
" "
w w
i=1 i=1
maksymalizacji wielkości w jest równowa\
ny następującemu zadaniu PL:
m
Funkcja celu: Q(y) = yi “! min
"
i=1
m
Warunki ograniczajÄ…ce: yi e" 1, j=1,& ,n
"M ij
i=1
Warunki brzegowe: yi e" 0, i = 1,2...,m
Tak przedstawiony problem jest problemem dualnym
programowania liniowego. Problem ten pozwala nam znalez
ć 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: x d" 1, i = 1,K,m
"Mij j
j=1
Str. 5
WYKA
ADY Z TEORII GIER I DECYZJI
Warunki brzegowe: x e" 0 j=1,& ,n
j
WracajÄ…c do naszego problemu dualnego stwierdzamy, \
e funkcja
celu jest w nim ograniczona przez 0. A
atwo tez sprawdzić, \
e zadanie to nie
jest sprzeczne. W konsekwencji na mocy twierdzenia (tm.1) przedstawiony
wy\
ej problem dualny ma rozwiązanie. W świetle Twierdzenia (tm.2) je\
eli
problem dualny ma rozwiązanie, to problem pierwotny równie\
ma
rozwiązanie. Co więcej wartości funkcji celu w problemie dualnym i
pierwotnym sÄ… takie same, z czego wynika, \
e wartość dolna i wartość górna
gry są sobie równe, co nale\
ało dowieść. Znając tę wartość i korzystając z
wzoru mo\
emy wyliczyć prawdopodobieństwa ąi występujące w strategii
bezpieczeństwa gracza I. Analogicznie otrzymamy te\
strategiÄ™
bezpieczeństwa gracza II. A zatem udowodniliśmy (poprzez konstrukcję)
istnienie strategii bezpieczeństwa obu graczy a tym samym dowód punktów 1
i 2 twierdzenia minimaksowego. Prawdziwość pozostałych punktów
twierdzenia została dowiedziona w poprzednim paragrafie.
Z zaprezentowanego dowodu otrzymujemy praktyczny sposób
rozwiÄ…zywania gier o sumie zero. Poni\
ej przedstawiamy kroki, które
prowadzÄ… do jego otrzymania.
Kroki prowadzÄ…ce do rozwiÄ…zania gry o sumie zerowej:
1) Transformować macierz wypłat przez dodawanie stałej c, by
wszystkie jej elementy były dodatnie M = [M + c]
ij
2) Dla tak otrzymanej macierzy M sformułować zadanie programu
liniowego- problem dualny
3) Rozwiązać zadanie dualne. Otrzymamy optymalne wartości (y1,& ,ym)
oraz minimalna wartość funkcji F=Fmin .
Str. 6
ANDRZEJ Z. GRZYBOWSKI
4) Wartość gry zadanej macierzą M otrzymamy podstawiając
1
w =
Fmin
5) Współrzędne ąi* , i=1,& ,m strategii bezpieczeństwa gracza I
otrzymamy podstawiajÄ…c: Ä…i* = wyi
6) Wartość gry zadanej macierzą M otrzymamy jako róznicę w-c.
7) WspółrzÄ™dne ²i* , i=1,& ,n, strategii bezpieczeÅ„stwa gracza II
otrzymujemy mno\
ąc znaleziona wcześniej wartość w przez
współrzędne xi ,i=1,& ,n, rozwiązania optymalnego zadania
pierwotnego.
Str. 7