Pojęcie modeli gier.

Gra o sumie zerowej, w której każdy gracz ma do dyspozycji skończony zestaw strategii. Zasady gry matrixowej wyznacza matryca płatności, której elementami są wygrane pierwszego gracza i jednocześnie straty drugiego gracza.

Gra matrixowa jest grą antagonistyczną. Pierwszy gracz otrzymuje maksymalną gwarantowaną (niezależną od zachowania drugiego gracza) wygraną, równą cenie gry, podobnie drugi gracz osiąga minimalną gwarantowaną stratę.

Pod strategia rozumiany jest jako zbiór reguł (zasad), które określają wybór akcji przy każdym osobistym ruchu gracza, w zależności od aktualnej sytuacji.

Teraz o wszystkim w porządku i szczegółowo.

Matryca płatności, czyste strategie, cena gry

W gra matrixowa jego zasady są określone matryca płatności .

Rozważmy grę, w której bierze udział dwóch uczestników: pierwszy gracz i drugi gracz. Niech pierwszy gracz będzie miał do swojej dyspozycji M czyste strategie, a drugi gracz ma do dyspozycji - N czyste strategie. Ponieważ gra jest brana pod uwagę, naturalnym jest, że w tej grze są zwycięstwa i są porażki.

W matryca płatności elementami są liczby wyrażające zwycięstwa i porażki graczy. Wygrane i przegrane można wyrazić w punktach, kwocie pieniędzy lub innych jednostkach.

Stwórzmy macierz płatności:

Jeśli pierwszy gracz tak zdecyduje I-ta strategia czysta, a drugi gracz - J czystą strategią, wówczas wypłata zostanie przyznana pierwszemu graczowi Aja jednostek, podobnie jak strata drugiego gracza Aja jednostki.

Ponieważ Aij + (- A ij) = 0, to opisana gra jest grą macierzową o sumie zerowej.

Najprostszym przykładem gry matrixowej jest rzut monetą. Zasady gry są następujące. Pierwszy i drugi gracz rzucają monetą, a wynikiem jest orzeł lub reszka. Jeśli jednocześnie rzucone zostaną „reszki” i „reszki” lub „reszki” lub „reszki”, wówczas pierwszy gracz wygra jedną jednostkę, a w pozostałych przypadkach straci jedną jednostkę (drugi gracz wygra jedną jednostkę) . Te same dwie strategie są do dyspozycji drugiego gracza. Odpowiednia macierz płatności będzie wyglądać następująco:

Zadaniem teorii gier jest określenie wyboru strategii pierwszego gracza, która zagwarantuje mu maksymalną średnią wygraną, a także wybór strategii drugiego gracza, która zapewni mu maksymalną średnią stratę.

Jak wybrać strategię w grze matrix?

Przyjrzyjmy się jeszcze raz matrycy płatności:

Najpierw ustalmy wysokość wygranej dla pierwszego gracza, jeśli skorzysta I czysta strategia. Jeśli pierwszy gracz użyje I czystej strategii, logiczne jest założenie, że drugi gracz zastosuje taką czystą strategię, dzięki czemu wypłata pierwszego gracza będzie minimalna. Z kolei pierwszy gracz zastosuje taką czystą strategię, jaka mu zapewni maksymalna wygrana. Na podstawie tych warunków wygrana pierwszego gracza, którą oznaczamy jako w1 , zwany maksymalizujące wygrane Lub spód kosztem gry .

Na dla tych wartości pierwszy gracz powinien postępować w następujący sposób. Z każdej linii zapisz wartość elementu minimalnego i wybierz z nich element maksymalny. Zatem wygrana pierwszego gracza będzie maksymalną z minimalną. Stąd nazwa – maximin wygrywający. Numer linii tego elementu będzie numerem czystej strategii, którą wybierze pierwszy gracz.

Teraz ustalmy wysokość straty drugiego gracza, jeśli skorzysta J strategia. W tym przypadku pierwszy gracz stosuje własną, czystą strategię, w której strata drugiego gracza byłaby maksymalna. Drugi gracz musi wybrać czystą strategię, w której jego strata będzie minimalna. Utrata drugiego gracza, którą oznaczamy jako w2 , zwany strata minimaksowa Lub najwyższa cena gry .

Na rozwiązywanie problemów dotyczących ceny gry i ustalanie strategii Aby określić te wartości dla drugiego gracza, wykonaj następujące czynności. Z każdej kolumny zapisz wartość elementu maksymalnego i wybierz z nich minimum. Zatem strata drugiego gracza będzie minimalna z maksimum. Stąd nazwa - wygrana minimax. Numer kolumny tego elementu będzie numerem czystej strategii, którą wybiera drugi gracz. Jeżeli drugi gracz skorzysta z „minimaxu”, to niezależnie od wyboru strategii przez pierwszego gracza, nie straci on więcej niż w2 jednostki.

Przykład 1.

.

Największym z najmniejszych elementów rzędów jest 2, jest to niższa cena gry, odpowiada temu pierwszy rząd, dlatego strategia maximin pierwszego gracza jest pierwsza. Najmniejszy z największych elementów kolumn to 5, jest to górna cena gry, odpowiada jej druga kolumna, dlatego strategia minimax drugiego gracza jest drugą.

Teraz, gdy nauczyliśmy się znajdować dolną i górną cenę gry, strategie maximin i minimax, czas nauczyć się formalnie definiować te pojęcia.

Zatem gwarantowana wygrana dla pierwszego gracza wynosi:

Pierwszy gracz musi wybrać czystą strategię, która zapewni mu maksimum z minimalnych wygranych. Wzmocnienie to (maksymin) oznacza się następująco:

.

Pierwszy gracz wykorzystuje swoją czystą strategię, aby strata drugiego gracza była maksymalna. Strata ta jest wskazywana w następujący sposób:

Drugi gracz musi wybrać swoją czystą strategię, aby jego strata była minimalna. Strata ta (minimax) jest wskazywana w następujący sposób:

.

Inny przykład z tej samej serii.

Przykład 2. Biorąc pod uwagę grę macierzową z macierzą wypłat

.

Określ strategię maximin pierwszego gracza, strategię minimax drugiego gracza, dolną i górną cenę gry.

Rozwiązanie. Po prawej stronie macierzy płatności wypisujemy w jej wierszach najmniejsze elementy i zaznaczamy ich maksimum, a pod macierzą - największe elementy w kolumnach i wybierz najmniejszy z nich:

Największy z najmniejszych elementów linii to 3, jest to niższa cena gry, odpowiada jej druga linia, dlatego strategią maximin pierwszego gracza jest druga. Najmniejszy z największych elementów kolumn to 5, jest to górna cena gry, odpowiada jej pierwsza kolumna, dlatego strategią minimax drugiego gracza jest pierwsza.

Punkt siodłowy w grach matrixowych

Jeśli górna i dolna cena gry są takie same, wówczas grę matrix uważa się za posiadającą punkt siodłowy. Dzieje się tak również na odwrót: jeśli gra matrixowa ma punkt siodłowy, wówczas górna i dolna cena gry matrix jest taka sama. Odpowiedni element jest zarówno najmniejszy w rzędzie, jak i największy w kolumnie i równa cenie Gry.

Zatem, jeśli , to jest optymalną czystą strategią pierwszego gracza i jest optymalną czystą strategią drugiego gracza. Oznacza to, że równe niższe i wyższe ceny gier osiąga się przy użyciu tej samej pary strategii.

W tym przypadku gra matrixowa ma rozwiązanie w czystych strategiach .

Przykład 3. Biorąc pod uwagę grę macierzową z macierzą wypłat

.

Rozwiązanie. Na prawo od macierzy płatności wypiszemy w jej wierszach najmniejsze elementy i zanotujemy ich maksimum, a pod macierzą największe elementy w kolumnach i wybierzemy ich minimum:

Niższa cena gry pokrywa się z wyższą ceną gry. Zatem cena gry wynosi 5. To znaczy. Cena gry jest równa wartości punktu siodłowego. Strategia maxin pierwszego gracza jest drugą czystą strategią, a strategia minimax drugiego gracza jest trzecią czystą strategią. Ta gra matrixowa ma rozwiązanie w czystych strategiach.

Rozwiąż samodzielnie problem gry macierzowej, a następnie spójrz na rozwiązanie

Przykład 4. Biorąc pod uwagę grę macierzową z macierzą wypłat

.

Znajdź dolną i górną cenę gry. Czy ta gra matrix ma punkt siodłowy?

Gry matrixowe z optymalną strategią mieszaną

W większości przypadków gra macierzowa nie ma punktu siodłowego, więc odpowiadająca jej gra macierzowa nie ma rozwiązań w czystych strategiach.

Ale ma rozwiązanie w optymalnych strategiach mieszanych. Aby je znaleźć, należy założyć, że gra powtarza się wystarczającą liczbę razy, aby na podstawie doświadczenia móc zgadnąć, która strategia jest korzystniejsza. Dlatego decyzja wiąże się z pojęciem prawdopodobieństwa i średniej (oczekiwania matematycznego). W ostatecznym rozwiązaniu istnieje zarówno analogia punktu siodłowego (czyli równość dolnej i górnej ceny gry), jak i analogia odpowiadających im strategii.

Aby więc pierwszy gracz uzyskał maksymalną średnią wygraną, a drugi gracz miał minimalną średnią stratę, należy z pewnym prawdopodobieństwem zastosować czyste strategie.

Jeśli pierwszy gracz zastosuje czyste strategie z prawdopodobieństwem , następnie wektor nazywa się mieszaną strategią pierwszego gracza. Inaczej mówiąc, jest to „mieszanka” czystych strategii. W tym przypadku suma tych prawdopodobieństw jest równa jeden:

.

Jeśli drugi gracz zastosuje czyste strategie z prawdopodobieństwem , następnie wektor nazywa się strategią mieszaną drugiego gracza. W tym przypadku suma tych prawdopodobieństw jest równa jeden:

.

Jeśli pierwszy gracz stosuje strategię mieszaną P, a drugi gracz - strategia mieszana Q, wtedy ma to sens wartość oczekiwana wygrana pierwszego gracza (przegrana drugiego gracza). Aby go znaleźć, należy pomnożyć wektor strategii mieszanej pierwszego gracza (który będzie macierzą jednowierszową), macierz wypłat i wektor strategii mieszanej drugiego gracza (który będzie macierzą jednokolumnową):

.

Przykład 5. Biorąc pod uwagę grę macierzową z macierzą wypłat

.

Określ matematyczne oczekiwanie wygranej pierwszego gracza (przegranej drugiego gracza), jeśli strategia mieszana pierwszego gracza wynosi , a strategia mieszana drugiego gracza wynosi .

Rozwiązanie. Zgodnie ze wzorem na matematyczne oczekiwanie wygranej pierwszego gracza (przegranej drugiego gracza) jest ona równa iloczynowi wektora strategii mieszanej pierwszego gracza, macierzy płatności i wektora strategii mieszanej drugiego gracza:

Pierwszy gracz nazywa się taką strategią mieszaną, która zapewni mu maksymalną średnią wypłatę, jeśli gra zostanie powtórzona odpowiednią liczbę razy.

Optymalna strategia mieszana drugi gracz nazywany jest taką strategią mieszaną, która zapewniłaby mu minimalną średnią stratę, jeśli gra zostanie powtórzona odpowiednią liczbę razy.

Przez analogię do zapisu maksyminu i minimaksu w przypadku strategii czystych, optymalne strategie mieszane oznaczane są następująco (i są powiązane z oczekiwanie matematyczne, czyli średnia wygranych pierwszego gracza i strat drugiego gracza):

,

.

W tym przypadku dla funkcji mi jest punkt siodłowy , co oznacza równość.

Aby znaleźć optymalne strategie mieszane i punkt siodłowy, tj. rozwiązać grę matrix w strategiach mieszanych , należy sprowadzić grę macierzową do problemu programowania liniowego, czyli problemu optymalizacji i rozwiązać odpowiadający mu problem programowania liniowego.

Redukcja gry macierzowej do problemu programowania liniowego

Aby rozwiązać grę macierzową w strategiach mieszanych, należy skonstruować linię prostą Problem programowania liniowego I podwójne zadanie. W zagadnieniu dualnym transponowana jest macierz rozszerzona, przechowująca współczynniki zmiennych w układzie więzów, wyrazy swobodne i współczynniki zmiennych w funkcji celu. W tym przypadku minimum funkcji celu pierwotnego problemu jest dopasowane do maksimum w zadaniu dualnym.

Funkcja celu w zagadnieniu bezpośredniego programowania liniowego:

.

Układ ograniczeń w zagadnieniu bezpośredniego programowania liniowego:

Funkcja celu w zadaniu dualnym to:

.

System ograniczeń w problemie dualnym:

Optymalny plan dla problemu bezpośredniego programowania liniowego jest oznaczony przez

,

a optymalny plan problemu podwójnego jest oznaczony przez

Formy liniowe dla odpowiednich optymalne plany oznaczmy i ,

i należy je znaleźć jako sumy odpowiednich współrzędnych planów optymalnych.

Zgodnie z definicjami z poprzedniego akapitu i współrzędnymi planów optymalnych obowiązują następujące strategie mieszane pierwszego i drugiego gracza:

.

Udowodnili to matematycy-teoretycy cena gry wyraża się w następujący sposób poprzez liniowe formy planów optymalnych:

,

to znaczy jest to odwrotność sum współrzędnych planów optymalnych.

My, praktycy, możemy używać tej formuły jedynie do rozwiązywania gier macierzowych w strategiach mieszanych. Tak jak formuły znajdowania optymalnych strategii mieszanych odpowiednio pierwszy i drugi gracz:

w którym drugie czynniki są wektorami. Optymalne strategie mieszane są także, jak już zdefiniowaliśmy w poprzednim akapicie, wektorami. Dlatego mnożąc liczbę (cenę gry) przez wektor (ze współrzędnymi optymalnych planów) również otrzymujemy wektor.

Przykład 6. Biorąc pod uwagę grę macierzową z macierzą wypłat

.

Znajdź cenę gry V i optymalne strategie mieszane oraz .

Rozwiązanie. Tworzymy problem programowania liniowego odpowiadający tej grze macierzowej:

Otrzymujemy rozwiązanie bezpośredniego problemu:

.

Liniową postać optymalnych planów znajdujemy jako sumę znalezionych współrzędnych.

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. Kompilować matryca 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 schronie 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 maksymalną wygraną 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. i V.daje optymalne rozwiązanie gry wtedy i tylko wtedy, gdy odpowiadający mu element y jest zarówno największy w swojej kolumnie, jak 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)