Rozważmy sparowaną grę skończoną. Pozwól graczowi A ma T strategie osobiste, które oznaczamy
Pozwól graczowi W dostępny P strategie osobiste, wyznaczmy je. Mówią, że gra ma wymiary T X P.
W wyniku wyboru przez graczy dowolnej pary strategii, wynik gry jest jednoznacznie określony, tj. wygrana A;. gracz A(dodatnie lub ujemne) i stratę (-tak) gracz W. Załóżmy, że wartości A.. znany z dowolnej pary strategii (A:, B;). Matryca P. =(A..), ja = = 1, 2, ..., m j = 1, 2, ..., P, których elementami są wygrane odpowiadające strategiom A. I Bj, zwany matryca płatności, Lub matryca gry. Formularz ogólny taką macierz przedstawiono w tabeli. 12.1. Wiersze tej tabeli odpowiadają strategiom gracza A, a kolumny – strategie gracza W.
Tabela 12.1
Stwórzmy matrycę płatności na następną grę.
12.1. Szukaj gry.
Gracz A może ukryć się w jednym z dwóch schronów (I i II); gracz W szukam gracza A, a jeśli go znajdzie, otrzymuje karę w wysokości 1 den. jednostki z A, w przeciwnym razie płaci graczowi A 1 dzień jednostki Konieczne jest zbudowanie matrycy płatności gry.
ROZWIĄZANIE. Aby skompilować matrycę płatności, należy przeanalizować zachowanie każdego gracza. Gracz A może ukryć się w schronie I - tę strategię oznaczamy przez A v lub do schronu II – strategia A. d Gracz W może szukać pierwszego gracza w schronisku I - strategia W(lub do schronu II - strategia W.,. Jeśli gracz A znajduje się w Krypcie I i zostaje tam odkryty przez gracza W, te. wdrażanych jest kilka strategii (Α ν W{), potem gracz A płaci karę, tj. A n = -1. Podobnie dostajemy A. n = -1 (A 2, W.,). Jest oczywiste, że strategie (A, W.,) i (L2, /1,) dają graczowi A wypłata wynosi 1, więc A P = za. n = I. Zatem dla gry polegającej na szukaniu o wymiarach 2x2 otrzymujemy macierz wypłat:
Rozważ grę T X P z matrycą P = a J) , ja = 1,2, ..., τη; J= 1, 2, ..., i i określ najlepszą spośród strategii A Na A v..., A t. Wybór strategii A jo gracz A należy oczekiwać, że gracz W odpowie na nie, stosując jedną ze strategii W., za co wypłata dla gracza A minimalny (gracz W ma na celu „zaszkodzenie” graczowi A).
Oznaczmy przez a; najmniejsze wygrane gracza A kiedy wybiera strategię L; dla wszystkich możliwych strategii gracza W(najmniejsza liczba w i-ta linia matryca płatności), tj.
Spośród wszystkich liczb a (r = 1,2,..., T) Wybierzmy największy: . Zadzwońmy i niższą cenę gry, Lub maksymalne wygrane (maximin). Ten gwarantowana wygrana gracza A dla dowolnej strategii gracza B. Stąd,
(12.2)
Strategia odpowiadająca maximinowi nazywa się strategia maksymalizacji. Gracz W zainteresowany zmniejszeniem wygranych gracza A; wybór strategii W., uwzględnia maksymalny możliwy zysk dla A. Oznaczmy
Wśród wszystkich liczb β. wybierzmy najmniejszego,
i zadzwoń do β najwyższa cena gry, Lub wygrana minimax (minimax). Ten gwarantowana strata dla gracza B. Stąd,
(12.4)
Strategia odpowiadająca minimaxowi nazywa się strategia minimaxu.
Zasada, która nakazuje graczom wybierać najbardziej „ostrożne” strategie minimaksu i maksyminacji, nazywa się zasadą minimaks. Zasada ta wynika z rozsądnego założenia, że każdy gracz dąży do osiągnięcia celu przeciwnego do celu przeciwnika. Określmy dolną i górną cenę gry oraz odpowiadające im strategie w zadaniu 12.1. Rozważmy macierz płatności
z zadania 12.1. Przy wyborze strategii L, (pierwszy wiersz macierzy) minimalne wygrane jest równe a, =min(-l; 1) = -1 i odpowiada strategii β1 gracza W. Przy wyborze strategii L 2 (drugi rząd macierzy) to minimalna wygrana A 2 = min(l; -1) = -1, osiąga się to za pomocą strategii W.,.
Gwarantując sobie maksymalna wygrana dla dowolnej strategii gracza W, tj. niższa cena gry a = max(a, a2) = = max(-l; -1) = -1, gracz A może wybrać dowolną strategię: Aj lub A 2, tj. każda z jego strategii to maksymalizacja.
Wybierając strategię B, (kolumna 1), gracz W rozumie, że gracz A odpowie strategią A 2, aby zmaksymalizować swoje wygrane (przegrana W). Zatem maksymalna strata gracza wynosi W gdy wybiera strategię B, wynosi β, = check(-1; 1) = 1.
Podobnie maksymalna strata gracza B (wygrana A) gdy wybierze strategię B2 (kolumna 2) wynosi β2 = max(l; -1) = 1.
Zatem dla każdej strategii gracza A gwarantowana minimalna strata gracza B jest równa β = = πιίη(β1, β2) = min(l; 1) = 1 – górna cena gry.
Dowolna strategia gracza B to minimax. Po dodaniu tabeli 12,1 linia β; i kolumna a;, otrzymujemy tabelę. 12.2. Na przecięciu dodatkowych wierszy i kolumn zapiszemy górną i dolną cenę gier.
Tabela 12.2
W omówionym powyżej zadaniu 12.1 górna i dolna cena gry są różne: F β.
Jeśli górna i dolna cena gry pokrywają się, to Ogólne znaczenie nazywa się górną i dolną cenę gry α = β = υ czysta cena gry, Lub kosztem gry. Strategie Minimax odpowiadające cenie gry to optymalne strategie, i ich całość - optymalne rozwiązanie, Lub decyzja Gry. W tym przypadku gracz A otrzymuje maksimum gwarantowane (niezależne od zachowania gracza) W) wypłata to υ i gracz W osiąga minimalną gwarantowaną (niezależnie od zachowania gracza A) stratę υ. Mówią, że rozwiązanie gry ma stabilność, te. jeśli jeden z graczy będzie trzymał się swojego optymalna strategia, wówczas odejście od optymalnej strategii nie może być opłacalne dla drugiej strony.
Kilka czystych strategii A. oraz B. daje optymalne rozwiązanie gry wtedy i tylko wtedy, gdy odpowiedni element y jest jednocześnie największy w swojej kolumnie i najmniejszy w swoim rzędzie. Taka sytuacja, jeśli istnieje, nazywa się punkt siodłowy(podobnie jak powierzchnia siodełka, która zakrzywia się w górę w jednym kierunku i w dół w drugim).
Oznaczmy A* I W*– para czystych strategii, które prowadzą do rozwiązania problemu punktu siodłowego w grze. Przedstawmy funkcję wypłaty pierwszego gracza dla każdej pary strategii: ROCZNIE:, W-) = i y. Następnie, z warunku optymalności w punkcie siodłowym, zachodzi podwójna nierówność: P(Aj, B*)<Р(А*, В*)<Р(А", В ), co jest sprawiedliwe dla wszystkich ja = 1, 2, ..., m;j = 1, 2, ..., P. Rzeczywiście, wybór strategii A* pierwszy gracz z optymalną strategią W" drugi gracz maksymalizuje minimalną możliwą wypłatę: ROCZNIE*, B")> ROCZNIE G W"), i wybór strategii B" drugi gracz, stosując optymalną strategię pierwszego, minimalizuje maksymalną stratę: P(D, W*)<Р(А", В).
12.2. Określ dolną i górną cenę gry podaną przez matrycę płatności
Czy gra ma punkt siodłowy?
Tabela 12. 3
Rozwiązanie. Wygodnie jest przeprowadzić wszystkie obliczenia w tabeli, która oprócz macierzy R, wprowadzono kolumnę a; i sznurek)
