Antagonistyczne gry z ciągłymi strategiami. Rozwiązywanie antagonistycznych gier Matrix Rozwiązywanie antagonistycznych gier online

Nazywa się dwuosobową grę o sumie zerowej, w której każda z nich ma skończony zestaw strategii. Zasady gry macierzowej określa macierz wypłat, której elementami są wypłaty pierwszego gracza, które są jednocześnie stratami drugiego gracza.

Gra Matrix jest grą antagonistyczną. Pierwszy gracz otrzymuje maksymalną gwarantowaną (niezależną od zachowania drugiego gracza) wypłatę 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 wariantu działania dla każdego osobistego ruchu gracza, w zależności od aktualnej sytuacji.

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

Macierz wypłat, strategie czyste, cena gry

W gra matrixa jego zasady są ustalone macierz wypłat .

Rozważmy grę, w której bierze udział dwóch graczy: pierwszy gracz i drugi gracz. Niech pierwszy gracz ma m czyste strategie, a do dyspozycji drugiego gracza - n czyste strategie. Ponieważ gra jest rozważana, naturalne jest, że w tej grze są wygrane i przegrane.

W macierz płatności elementami są liczby wyrażające zyski i straty graczy. Wygrane i przegrane mogą być wyrażone w punktach, pieniądzach lub innych jednostkach.

Stwórzmy macierz wypłat:

Jeśli pierwszy gracz wybierze ja-ta czysta strategia i drugi gracz j-th czysta strategia, to wypłata pierwszego gracza wynosi aij jednostek, a strata drugiego gracza też aij jednostki.

Dlatego aij + (- a ij ) = 0, to opisana gra jest grą macierzową o sumie zerowej.

Najprostszym przykładem gry macierzowej jest rzut monetą. Zasady gry są następujące. Pierwszy i drugi gracz rzucają monetą, a wynikiem jest orzeł lub reszka. Jeśli w tym samym czasie zostaną wyrzucone głowy i głowy lub reszki lub reszki, pierwszy gracz wygra jedną jednostkę, aw innych przypadkach straci jedną jednostkę (drugi gracz wygra jedną jednostkę). Te same dwie strategie są do dyspozycji drugiego gracza. Odpowiednia macierz wypłat wyglądałaby następująco:

Zadaniem teorii gier jest określenie wyboru strategii pierwszego gracza, która zagwarantowałaby mu maksymalny średni zysk, a także wyboru strategii drugiego gracza, która zagwarantowałaby mu maksymalną średnią stratę.

Jak wybiera się strategię w grze matrix?

Spójrzmy ponownie na macierz wypłat:

Najpierw określamy wypłatę pierwszego gracza, jeśli użyje ja czysta strategia. Jeśli pierwszy gracz użyje ja-tej czystej strategii, to logiczne jest założenie, że drugi gracz zastosuje taką czystą strategię, dzięki której wypłata pierwszego gracza byłaby minimalna. Z kolei pierwszy gracz zastosuje taką czystą strategię, która zapewni mu maksymalną wypłatę. Na podstawie tych warunków wypłata pierwszego gracza, którą oznaczamy jako w1 , nazywa się zwycięstwo maximina lub niższa cena gry .

Na dla tych wartości pierwszy gracz powinien postępować w następujący sposób. Z każdego wiersza wypisz wartość elementu minimalnego i wybierz z nich maksimum. Zatem wypłata pierwszego gracza będzie maksimum z minimum. Stąd nazwa – maximin win. Numer linii tego elementu będzie numerem czystej strategii wybranej przez pierwszego gracza.

Teraz określmy stratę drugiego gracza, jeśli użyje j-ta strategia. W tym przypadku pierwszy gracz stosuje swoją własną czystą strategię, w której strata drugiego gracza byłaby maksymalna. Drugi gracz musi wybrać taką czystą strategię, w której jego strata byłaby minimalna. Utrata drugiego gracza, którą oznaczamy jako w2 , nazywa się minimalna strata lub najwyższa cena gry .

Na rozwiązywanie problemów dotyczących ceny gry i określanie strategii aby określić te wartości dla drugiego gracza, wykonaj następujące czynności. Z każdej kolumny wypisz wartość elementu maksymalnego i wybierz z nich minimum. Zatem strata drugiego gracza będzie minimalna z maksymalnej. Stąd nazwa - zysk minimax. Numer kolumny tego elementu będzie numerem czystej strategii wybranej przez drugiego gracza. Jeśli drugi gracz użyje „minimax”, to niezależnie od wyboru strategii przez pierwszego gracza, co najwyżej przegra 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, to jest górna cena gry, odpowiada jej druga kolumna, dlatego strategia minimax drugiego gracza jest druga.

Teraz, gdy nauczyliśmy się, jak znaleźć dolną i górną cenę gry, strategie maximin i minimax, nadszedł czas, aby nauczyć się formalnie oznaczać te pojęcia.

Tak więc gwarantowana wypłata pierwszego gracza to:

Pierwszy gracz musi wybrać czystą strategię, która zapewni mu maksymalną z minimalnych wypłat. To wzmocnienie (maksimin) jest oznaczone w następujący sposób:

.

Pierwszy gracz stosuje swoją czystą strategię, aby strata drugiego gracza była maksymalna. Stratę tę definiuje się w następujący sposób:

Drugi gracz musi wybrać swoją czystą strategię, aby jego strata była minimalna. Ta strata (minimaks) jest oznaczona następująco:

.

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.

Decyzja. Na prawo od macierzy wypłat wypisujemy najmniejsze elementy w jej wierszach i zaznaczamy ich maksimum, a od dołu macierzy - największe elementy w kolumnach i wybieramy z nich minimum:

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

Punkt siodłowy w grach matrix

Jeśli górna i dolna cena gry są takie same, uważa się, że gra macierzowa ma punkt siodłowy. Odwrotna sytuacja jest również prawdziwa: jeśli gra macierzowa ma punkt siodłowy, to górna i dolna cena gry macierzowej są takie same. Odpowiedni element jest zarówno najmniejszy w rzędzie, jak i największy w kolumnie i jest równy cenie gry.

Zatem jeśli , to jest optymalną czystą strategią pierwszego gracza i jest optymalną czystą strategią drugiego gracza. Oznacza to, że na tej samej parze strategii osiągane są równe ceny niższe i wyższe w grze.

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

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

.

Decyzja. Na prawo od macierzy wypłat wypisujemy najmniejsze elementy w jej wierszach i zaznaczamy ich maksimum, a od dołu macierzy - największe elementy w kolumnach i wybieramy z nich minimum:

Niższa cena gry jest taka sama jak górna cena gry. Zatem cena gry wynosi 5. To znaczy . Cena gry jest równa wartości punktu siodłowego. Strategia maximin pierwszego gracza jest drugą czystą strategią, a strategia minimax drugiego gracza jest trzecią czystą strategią. Ta gra macierzowa ma rozwiązanie w czystych strategiach.

Rozwiąż samodzielnie problem z grą macierzową, a następnie zobacz 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 Matrix z optymalną mieszaną strategią

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

Ale ma rozwiązanie w optymalnych strategiach mieszanych. Aby je znaleźć, należy założyć, że gra jest powtarzana tyle razy, że na podstawie doświadczenia można odgadnąć, która strategia jest preferowana. Dlatego decyzja jest związana z pojęciem prawdopodobieństwa i średniej (oczekiwania). W ostatecznym rozwiązaniu występuje zarówno analogia punktu siodłowego (czyli równość dolnej i górnej ceny gry), jak i analogia odpowiadających im strategii.

Tak więc, aby pierwszy gracz uzyskał maksymalny średni zysk, a drugi minimalną średnią stratę, należy stosować czyste strategie z pewnym prawdopodobieństwem.

Jeśli pierwszy gracz używa czystych strategii z prawdopodobieństwem , a następnie wektor nazywa się strategią mieszaną pierwszego gracza. Innymi słowy, jest to „mieszanka” czystych strategii. Suma tych prawdopodobieństw jest równa jeden:

.

Jeśli drugi gracz używa czystych strategii z prawdopodobieństwem , a następnie wektor nazywa się strategią mieszaną drugiego gracza. 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 pierwszy gracz wygrywa (drugi gracz przegrywa). Aby go znaleźć, musisz pomnożyć wektor strategii mieszanej pierwszego gracza (który będzie macierzą jednorzędową), 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

.

Wyznacz matematyczne oczekiwanie zysku pierwszego gracza (straty drugiego gracza), jeśli strategia mieszana pierwszego gracza to , a strategia mieszana drugiego gracza to .

Decyzja. Zgodnie ze wzorem na matematyczne oczekiwanie zysku pierwszego gracza (straty drugiego gracza), jest on równy iloczynowi wektora strategii mieszanej pierwszego gracza, macierzy wypłat i wektora strategii mieszanej drugiego gracza:

Pierwszy gracz nazywany jest taką mieszaną strategią, która zapewniłaby mu maksymalną średnią wypłatę, gdyby grę powtórzono odpowiednią liczbę razy.

Optymalna strategia mieszana Drugi gracz nazywa się taką mieszaną strategią, która zapewniłaby mu minimalną średnią stratę, gdyby gra została powtórzona odpowiednią liczbę razy.

Przez analogię z zapisem maximin i minimax w przypadku czystych strategii, optymalne strategie mieszane są oznaczone w następujący sposób (i są powiązane z matematycznym oczekiwaniem, czyli średnią zysku pierwszego gracza i straty drugiego gracza):

,

.

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

W celu znalezienia optymalnych strategii mieszanych i punktu siodłowego, tj. rozwiąż grę macierzową w strategiach mieszanych , musisz zredukować grę macierzową do problemu programowania liniowego, czyli problemu optymalizacji, i rozwiązać odpowiedni problem programowania liniowego.

Redukcja gry macierzowej do problemu programowania liniowego

Aby rozwiązać grę macierzową w strategiach mieszanych, musisz ułożyć linię prostą problem programowania liniowego oraz swoje podwójne zadanie. W problemie dualnym transponowana jest rozszerzona macierz, która przechowuje współczynniki zmiennych w układzie ograniczeń, stałe wyrazy i współczynniki zmiennych w funkcji celu. W tym przypadku minimum funkcji celu pierwotnego problemu jest powiązane z maksimum w problemie dualnym.

Funkcja celu w zadaniu bezpośredniego programowania liniowego:

.

Układ ograniczeń w zadaniu bezpośrednim programowania liniowego:

Funkcja celu w problemie dualnym:

.

Układ ograniczeń w problemie dualnym:

Oznacz plan optymalny problemu bezpośredniego programowania liniowego

,

a optymalny plan problemu dualnego jest oznaczony przez

Formy liniowe dla odpowiednich projektów optymalnych będą oznaczane przez i ,

i musisz je znaleźć jako sumę odpowiednich współrzędnych planów optymalnych.

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

.

Udowodnili to matematycy cena gry wyraża się w postaci liniowych planów optymalnych w następujący sposób:

,

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

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

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

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

.

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

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

Otrzymujemy rozwiązanie bezpośredniego problemu:

.

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

Wyślij swoją dobrą pracę w bazie wiedzy jest prosta. Skorzystaj z poniższego formularza

Studenci, doktoranci, młodzi naukowcy, którzy korzystają z bazy wiedzy w swoich studiach i pracy, będą Wam bardzo wdzięczni.

Wstęp

1. Część teoretyczna

1.3 Kolejność gry 2 na 2

1.4 Metoda algebraiczna

1.5 Metoda graficzna

1.6 Gry 2xn lub mx2

1.7 Rozwiązywanie gier metodą macierzową

2. Część praktyczna

2.2 gry 2xn i mx2

2.3 Metoda macierzowa

2.4 Metoda Browna

Analiza wyników

Wstęp

Gra antagonistyczna jest grą o sumie zerowej. Gra antagonistyczna to gra niekooperacyjna, w której uczestniczy dwóch graczy, których wypłaty są przeciwne.

Formalnie gra antagonistyczna może być reprezentowana przez trójkę , gdzie X i Y to zbiory strategii odpowiednio pierwszego i drugiego gracza, F to funkcja wypłaty pierwszego gracza, która wiąże każdą parę strategii (x, y), gdzie jest liczbą rzeczywistą odpowiadającą użyteczności pierwszego gracza, który zdał sobie sprawę z tej sytuacji.

Ponieważ interesy graczy są przeciwne, funkcja F reprezentuje jednocześnie utratę drugiego gracza.

Historycznie rzecz biorąc, gry antagonistyczne są pierwszą klasą modeli matematycznych teorii gier, których używano do opisu hazard. Uważa się, że dzięki temu przedmiotowi badań teoria gier zyskała swoją nazwę. Obecnie gry antagonistyczne są uważane za część szerszej klasy gier niekooperacyjnych.

1. Część teoretyczna

1.1 Podstawowe definicje i przepisy gry

Gra charakteryzuje się systemem reguł, które określają liczbę uczestników gry, ich możliwe działania i dystrybucji wygranych w zależności od ich zachowania i wyników. Za gracza uważa się jednego uczestnika lub grupę uczestników gry, którzy mają dla nich wspólne interesy, które nie pokrywają się z interesami innych grup. Dlatego nie każdy uczestnik jest uważany za gracza.

Zasady lub warunki gry określają możliwe zachowania, wybory i posunięcia graczy na każdym etapie rozwoju gry. Dokonanie wyboru dla gracza oznacza zatrzymanie się na jednej z jego możliwości zachowania. Następnie gracz dokonuje tego wyboru za pomocą ruchów. Wykonać ruch oznacza na pewnym etapie gry dokonanie od razu całości lub części wyboru, w zależności od możliwości przewidzianych przez reguły gry. Każdy gracz na pewnym etapie gry wykonuje ruch zgodnie z dokonanym wyborem. Drugi gracz, wiedząc lub nie wiedząc o wyborze pierwszego gracza, również wykonuje ruch. Każdy z graczy stara się uwzględniać informacje o dotychczasowym rozwoju gry, o ile zasady gry dopuszczają taką możliwość.

Zbiór reguł, które jednoznacznie podpowiadają graczowi, jakiego wyboru powinien dokonać przy każdym ruchu, w zależności od sytuacji, która rozwinęła się w wyniku gry, nazywa się strategią gracza. Strategia w teorii gier oznacza pewien kompletny plan działania gracza, pokazujący, jak powinien postępować we wszystkich możliwych przypadkach rozwoju gry. Strategia oznacza całość wszystkich wskazań dowolnego stanu informacji dostępnych dla gracza na dowolnym etapie rozwoju gry. To już pokazuje, że strategie mogą być dobre i złe, udane i nieudane itp.

Będzie gra o sumie zerowej, gdy suma wypłat wszystkich graczy w każdej z jej gier będzie równa zero, tj. w grze o sumie zerowej całkowity kapitał wszystkich graczy nie zmienia się, ale jest redystrybuowany między graczy w zależności od uzyskanych wyników. Tak więc wiele sytuacji ekonomicznych i wojskowych można postrzegać jako gry o sumie zerowej.

W szczególności gra o sumie zerowej dwóch graczy nazywana jest antagonistyczną, ponieważ cele graczy w niej są wprost przeciwne: zysk jednego gracza następuje tylko kosztem utraty drugiego.

1.1.1 Definicja, przykłady i rozwiązania gier macierzowych w strategiach czystych

Gra macierzowa dla dwóch graczy o sumie zerowej może być postrzegana jako następująca abstrakcyjna gra dla dwóch graczy.

Pierwszy gracz ma m strategii i =1, 2,…, m, drugi ma n strategii j = 1, 2,…, n. Każdej parze strategii (i, j) przyporządkowana jest liczba a ij , która wyraża wypłata pierwszego gracza należna drugiemu graczowi, jeśli pierwszy gracz wykorzysta swoją i-ta strategia, a drugi - jego j-ta strategia.

Każdy z graczy wykonuje jeden ruch: pierwszy gracz wybiera swoją i-tą strategię (i = 1, 2, ..., m), drugi --Twój j-ty strategia (j = 1, 2,…, n), po której pierwszy gracz otrzymuje wypłatę ij kosztem drugiego gracza (jeśli ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Każda strategia gracza i = 1, 2,…, t; j = 1, 2,…, n jest często nazywane strategią czystą.

Gra macierzowa o sumie zerowej dla dwóch graczy będzie nazywana po prostu grą macierzową. Oczywiście gra matrix należy do gier antagonistycznych. Z jej definicji wynika, że ​​aby zdefiniować grę macierzową, wystarczy podać macierz A = (a ij) rzędu m wypłat pierwszego gracza.

Biorąc pod uwagę macierz wypłat

wtedy wykonanie każdej gry z gry macierzowej z macierzą A sprowadza się do wyboru przez pierwszego gracza i-ta linia, a przez drugiego gracza w j-tej kolumnie i pierwszego gracza (kosztem drugiego) otrzymuje wypłatę znajdującą się w macierzy A na przecięciu i-tego rzędu i j-tej kolumny.

Aby sformalizować prawdziwą sytuację konfliktową w postaci gry macierzowej, konieczne jest zidentyfikowanie i przenumerowanie czystych strategii każdego gracza oraz zestawienie macierzy wypłat.

Kolejnym krokiem jest określenie optymalnych strategii i wypłat graczy.

Najważniejsze w badaniu gier jest koncepcja optymalnych strategii dla graczy. Pojęcie to intuicyjnie ma następujące znaczenie: strategia gracza jest optymalna, jeśli zastosowanie tej strategii zapewnia mu największą gwarantowaną wypłatę ze wszystkich możliwych strategii drugiego gracza. Na podstawie tych pozycji pierwszy gracz bada macierz A swoich wypłat według wzoru (1.1) w następujący sposób: dla każdej wartości i (i = 1, 2, ..., m) wyznacza się minimalną wartość wypłaty w zależności od od strategii stosowanych przez drugiego gracza

(i = 1, 2,..., m) (1,2)

tj. wyznacza się minimalną wypłatę dla pierwszego gracza, pod warunkiem, że zastosuje on swoją i-tą czystą strategię, to z tych minimalnych wypłat znajduje się taką strategię i=i 0, dla której ta minimalna wypłata będzie maksymalna, tj.

Definicja. Liczba b określona wzorem (1.3) nazywana jest niższym kosztem netto gry i pokazuje, jaką minimalną wypłatę pierwszy gracz może sobie zagwarantować, stosując swoje czyste strategie dla wszystkich możliwych działań drugiego gracza.

Drugi gracz, swoim optymalnym zachowaniem, powinien dążyć w miarę możliwości do minimalizacji wypłaty pierwszego gracza kosztem jego strategii. Dlatego dla drugiego gracza znajdujemy

tj. ustalana jest maksymalna wypłata pierwszego gracza, pod warunkiem, że drugi gracz zastosuje swoją j-ty czysty strategii, to drugi gracz znajduje swoją własną strategię j = j 1, za którą pierwszy gracz otrzymuje minimalną wypłatę, tj. znajduje

Definicja. Liczba β wyznaczona ze wzoru (1,5) nazywana jest górnym kosztem gry netto i pokazuje, jaki maksymalny zysk może sobie zapewnić pierwszy gracz dzięki swoim strategiom. Innymi słowy, stosując swoje czyste strategie, pierwszy gracz może zapewnić sobie wypłatę co najmniej b, a drugi gracz, stosując swoje czyste strategie, może uniemożliwić pierwszemu graczowi wygranie więcej niż c.

Definicja. Jeśli w grze z macierzą A dolna i górna cena netto gry pokrywają się, tj. b = c, to mówi się, że ta gra ma punkt siodłowy w czystych strategiach i cenę gry netto:

n = b = c (1,6)

Punkt siodłowy to para czystych strategii () odpowiednio pierwszego i drugiego gracza, przy których osiągana jest równość

Pojęcie punktu siodłowego ma następujące znaczenie: jeśli jeden z graczy trzyma się strategii odpowiadającej punktowi siodłowemu, to drugi gracz nie może zrobić nic lepszego niż trzymać się strategii odpowiadającej punktowi siodłowemu. Pamiętając, że najlepsze zachowanie gracza nie powinno prowadzić do zmniejszenia jego wypłaty, a najgorsze zachowanie może prowadzić do zmniejszenia jego wypłaty, warunki te można zapisać matematycznie w postaci następujących zależności:

gdzie i, j to dowolne czyste strategie odpowiednio pierwszego i drugiego gracza; (i 0 , j 0) -- strategie tworzące punkt siodłowy. Poniżej pokażemy, że definicja punktu siodłowego jest równoważna warunkom (1.8).

Zatem na podstawie (1.8) elementem siodłowym jest minimum w i-tym rzędzie i maksimum w j-0-tej kolumnie macierzy A. Znalezienie punktu siodłowego macierzy A jest łatwe: w macierzy A, kolejno w każdym wierszu, znajdź element minimalny i sprawdź, czy ten element jest maksimum w swojej kolumnie. Jeśli tak jest, to jest to element siodłowy, a odpowiadająca mu para strategii tworzy punkt siodłowy. Parę czystych strategii (i 0 , j 0) pierwszego i drugiego gracza, tworzących punkt siodłowy i element siodłowy, nazywamy rozwiązaniem gry.

Czyste strategie i 0 i j 0 tworzące punkt siodłowy nazywane są optymalnymi czystymi strategiami odpowiednio pierwszego i drugiego gracza.

Twierdzenie 1. Niech f (x, y) będzie funkcją rzeczywistą dwóch zmiennych x A i y B i istnieje

wtedy b = c.

Dowód. Z definicji minimum i maksimum wynika, że

Skoro x jest dowolne po lewej stronie (1.11), to

Po prawej stronie nierówności (1.12) y jest dowolne, więc

co było do okazania

W szczególności macierz () jest szczególnym przypadkiem funkcji f (x, y), tzn. jeśli wstawimy x = i, y = j, = f (x, y), to z Twierdzenia 1 otrzymamy, że im niższa cena netto nie przekracza górnej wartości netto gry w grze matrix.

Definicja. Niech f (x, y) będzie rzeczywistą funkcją dwóch zmiennych x A i y B. Punkt (x 0, y 0) nazywamy punktem siodłowym dla funkcji f (x, y), jeśli zachodzą następujące nierówności:

fa (x, y 0) fa (x 0, y 0) fa (x 0, y) (1,14)

dla dowolnych x A i y B.

1.2 Optymalne strategie mieszane i ich właściwości

Badanie gry macierzowej rozpoczyna się od znalezienia punktu siodłowego w czystych strategiach. Jeśli gra macierzowa ma punkt siodłowy w czystych strategiach, znalezienie tego punktu kończy badanie gry. Jeżeli w grze macierzowej w czystych strategiach nie ma punktu siodłowego, to możemy znaleźć dolną i górną czystą cenę tej gry, które wskazują, że pierwszy gracz nie powinien liczyć na wypłatę większą niż górna cena gry, a może być pewien, że otrzyma wypłatę nie mniejszą niż niższa cena gry. Takie zalecenia dotyczące zachowania graczy w grze macierzowej bez punktu siodłowego w czystych strategiach nie mogą zadowolić badaczy i praktyków. Udoskonalenia rozwiązania gier macierzowych należy szukać w wykorzystaniu tajemnicy stosowania czystych strategii oraz możliwości wielokrotnego powtarzania gier w formie partii. Na przykład rozgrywa się serię partii w szachy, warcaby, piłkę nożną i za każdym razem gracze stosują swoje strategie w taki sposób, że ich przeciwnicy nie są świadomi ich treści, a po drodze osiągają określone wypłaty średnio o grając w całą serię gier. Te wypłaty są średnio większe niż dolna cena gry i mniejsze niż górna cena gry. Im większa jest ta średnia wartość, tym lepsza strategia zastosowany przez gracza. W związku z tym zrodził się pomysł stosowania czystych strategii w sposób losowy, z pewnym prawdopodobieństwem. To w pełni zapewnia poufność ich użycia. Każdy gracz może zmienić prawdopodobieństwo zastosowania swoich czystych strategii w taki sposób, aby zmaksymalizować swoją średnią wypłatę i uzyskać po drodze optymalne strategie. Pomysł ten doprowadził do koncepcji strategii mieszanej.

Definicja. Strategia mieszana gracza to pełny zestaw prawdopodobieństw zastosowania jego czystych strategii.

Zatem, jeśli pierwszy gracz ma m czystych strategii 1, 2, … i, … m, to jego strategia mieszana x jest zbiorem liczb x = (x 1 , x 2 , ..., x i ,…, x t ) spełniających relacje

x ja 0 (ja = 1, 2, ... , m), = 1. (1,15)

Podobnie dla drugiego gracza, który ma n czystych strategii, strategia mieszana y jest zbiorem liczb y = (y 1 ,…, y j , … y n) spełniających zależności

y jot 0 (j = 1, 2, ... , n), = 1. (1,16)

Ponieważ za każdym razem, gdy gracz używa jednej czystej strategii, wyklucza użycie innej, czyste strategie są zdarzeniami niekompatybilnymi. Ponadto są to jedyne możliwe zdarzenia.

Oczywiście strategia czysta jest szczególnym przypadkiem strategii mieszanej. Rzeczywiście, jeśli w strategii mieszanej i-ta siatka strategia jest stosowana z prawdopodobieństwem jeden, to wszystkie inne czyste strategie nie są stosowane. A ta i-ta czysta strategia jest szczególnym przypadkiem strategii mieszanej. Aby zachować tajemnicę, każdy gracz stosuje własne strategie, niezależnie od wyboru drugiego gracza.

Definicja. Średnia wypłata pierwszego gracza w grze macierzowej z macierzą A jest wyrażona jako matematyczne oczekiwanie jego wypłat

E (A, x, y) = (1,20)

Oczywiście średnia wypłata pierwszego gracza jest funkcją dwóch zestawów zmiennych x i y. Pierwszy gracz dąży do maksymalizacji swojej średniej wypłaty E (A, x, y) poprzez zmianę swoich strategii mieszanych x, a drugi gracz stara się, aby E (A, x, y) była minimalna poprzez swoje strategie mieszane, tj. aby rozwiązać grę, należy znaleźć takie x, y, dla których została osiągnięta górna cena gry.

1.3 Zamów 22 gry

Gra macierzowa rzędu 22 jest dana przez następującą macierz wypłat dla pierwszego gracza:

Rozwiązanie tej gry należy rozpocząć od znalezienia punktu siodłowego w czystych strategiach. W tym celu znajdź element minimalny w pierwszym wierszu i sprawdź, czy jest on maksymalny w swojej kolumnie. Jeśli taki element nie zostanie znaleziony, druga linia jest sprawdzana w ten sam sposób. Jeśli taki element znajduje się w drugim wierszu, to jest to element siodłowy.

Znalezienie elementu siodłowego, jeśli taki istnieje, kończy proces znajdowania jego rozwiązania, ponieważ w tym przypadku ustalana jest cena gry – element siodłowy i punkt siodłowy, czyli para czystych strategii dla pierwszej i drugiej graczy, stanowiących optymalne czyste strategie. Jeśli w czystych strategiach nie ma punktu siodłowego, to w strategiach mieszanych trzeba znaleźć punkt siodłowy, który koniecznie istnieje zgodnie z głównym twierdzeniem gier macierzowych.

Oznaczmy przez x=(x 1 ,x 2), y=(y 1 ,y 2) strategie mieszane odpowiednio pierwszego i drugiego gracza. Przypomnijmy, że x 1 oznacza prawdopodobieństwo, że pierwszy gracz użyje swojej pierwszej strategii, a x 2 \u003d 1 - x 1 to prawdopodobieństwo użycia drugiej strategii. Podobnie dla drugiego gracza: 1 – prawdopodobieństwo zastosowania pierwszej strategii, y 2 = 1 – 1 – prawdopodobieństwo zastosowania drugiej strategii.

Zgodnie z wnioskiem twierdzenia, dla optymalności strategii mieszanych x i y konieczne i wystarczające jest, aby dla nieujemnych x 1 , x 2 , y 1 , y 2 zachodziły następujące zależności:

Pokażemy teraz, że jeśli gra macierzowa nie ma punktu siodłowego w czystych strategiach, to te nierówności muszą przekształcić się w równości:

W rzeczy samej. Niech gra nie ma punktu siodłowego w czystych strategiach, wtedy optymalne wartości strategii mieszanych spełniają nierówności

0<<1, 0<< 1,

0< <1, 01. (1.25)

Załóżmy, że obie nierówności z (1.22) są ścisłe

wtedy, zgodnie z twierdzeniem, y 1 = y 2 = 0, co jest sprzeczne z warunkami (1,25).

Podobnie można udowodnić, że obie nierówności w (1.23) nie mogą być nierównościami ścisłymi.

Załóżmy teraz, że jedna z nierówności (1.22) może być ścisła, na przykład pierwsza

Oznacza to, że zgodnie z twierdzeniem y 1 = 0, y 2 = 1. Zatem z (1.23) otrzymujemy

Jeśli obie nierówności (1.24) są ścisłe, to z twierdzenia x1 = x2 = 0, co jest sprzeczne z (1.25). Ale jeśli a 12 a 22 , to jedna z nierówności (1,27) jest ścisła, a druga jest równością. Co więcej, równość będzie obowiązywać dla większego elementu z 12 i 22 , tj. jedna nierówność z (1.27) musi być ścisła. Na przykład 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Pokazano więc, że jeśli gra macierzowa nie ma punktu siodłowego w czystych strategiach, to nierówności (1,22) zamieniają się w równości dla optymalnych strategii pierwszego gracza. Podobne argumenty dotyczące nierówności (1.23) doprowadzą do tego, że w tym przypadku nierówności (1.23) muszą być równościami.

Jeśli więc gra macierzowa rzędu 22 nie ma punktu siodłowego, to optymalne strategie mieszane graczy i cenę gry można określić rozwiązując układ równań (1.24). Ustalono również, że jeśli w grze macierzowej 2x2 jeden z graczy ma optymalną czystą strategię, to drugi gracz również ma optymalną czystą strategię.

Jeśli więc gra macierzowa nie ma punktu siodłowego w czystych strategiach, to musi mieć rozwiązanie w strategiach mieszanych, które wyznacza się z równań (1.24). Rozwiązanie systemowe (1.25)

1.4 Metoda algebraiczna

Istnieją dwa przypadki rozwiązywania problemów metodą algebraiczną:

1. matryca ma punkt siodłowy;

2. matryca nie posiada punktu siodłowego.

W pierwszym przypadku rozwiązaniem jest para strategii, które tworzą punkt siodłowy gry. Rozpatrzmy drugi przypadek. Rozwiązań należy tu szukać w strategiach mieszanych:

Znajdź strategie i Kiedy pierwszy gracz stosuje swoją optymalną strategię, drugi gracz może na przykład zastosować dwie takie czyste strategie

Jednocześnie, na mocy własności, jeżeli jeden z graczy stosuje optymalną strategię mieszaną, a drugi dowolną czystą, zawartą w jego optymalnej strategii mieszanej z niezerowym prawdopodobieństwem, to matematyczne oczekiwanie wypłaty zawsze pozostaje niezmieniona i równa cenie gry, tj.

Wypłata musi w każdym z tych przypadków być równa wartości gry V. W tym przypadku obowiązują następujące zależności:

Dla optymalnej strategii drugiego gracza można również ułożyć układ równań podobny do (2.5), (2.6):

Biorąc pod uwagę warunek normalizacji:

Rozwiążmy równanie (1.37) - (1.41) razem w odniesieniu do niewiadomych i nie wszystkie naraz, ale trzy naraz: osobno (1,36), (1,38), (1,40) i (1,37), (1,39) , (1.41). W wyniku rozwiązania otrzymujemy:

1.5 Metoda graficzna

Przybliżone rozwiązanie gry 22 można dość łatwo uzyskać metodą graficzną. Jego istota jest następująca:

Rysunek 1.1 - znajdowanie odcinka o długości jednostkowej

Wybierz odcinek o długości jednostkowej na osi odciętych. Lewy koniec będzie przedstawiał pierwszą strategię pierwszego gracza, a prawy koniec drugiej. Wszystkie punkty pośrednie odpowiadają strategiom mieszanym pierwszego gracza, a długość odcinka na prawo od punktu jest równa prawdopodobieństwu użycia pierwszej strategii, a długość odcinka na lewo jest prawdopodobieństwem użycia druga strategia pierwszego gracza.

Realizowane są dwie osie I-I oraz II-II. Na I-I odłożymy wypłatę, gdy pierwszy gracz zastosuje pierwszą strategię, na II-II, gdy zastosuje drugą strategię. Niech np. drugi gracz zastosował swoją pierwszą strategię, wtedy wartość należy wykreślić na osi I-I, a wartość na osi II-II

W przypadku każdej strategii mieszanej pierwszego gracza, jego wypłata będzie uzależniona od wielkości segmentu. Linia I-I odpowiada zastosowaniu pierwszej strategii przez drugiego gracza, będziemy ją nazywać pierwszą strategią drugiego gracza. Druga strategia drugiego gracza może być skonstruowana podobnie. Wtedy ogólnie graficzne przedstawienie matrycy gry przybierze następującą postać:

Rysunek 1.2 - znalezienie ceny gry

Należy jednak zaznaczyć, że ta konstrukcja została przeprowadzona dla pierwszego gracza. Tutaj długość odcinka jest równa wartości gry V.

Linia 1N2 nazywana jest dolną linią wypłaty. Widać tu wyraźnie, że punkt N odpowiada maksymalnej wartości gwarantowanej wypłaty pierwszego gracza.

Ogólnie rzecz biorąc, strategię drugiego gracza można również określić na podstawie tej figury, na przykład w taki sposób. Na osi I-I:

lub na osi II-II

Jednak strategię drugiego gracza można również zdefiniować w taki sam sposób, jak w przypadku pierwszego gracza, tj. zbudować taki wykres.

Rysunek 1.3 – definicja strategii drugiego gracza

Tutaj linia 1N2 jest górną granicą straty. Punkt N odpowiada minimalnej możliwej stracie drugiego gracza i określa strategię.

W zależności od konkretnych wartości współczynników, macierze wykresów mogą mieć również inną postać, na przykład następującą:

Rysunek 1.4 – określa optymalną strategię pierwszego gracza

W takiej sytuacji optymalna strategia pierwszego gracza jest czysta:

1.6 Gry 2n lub m2

W grach rzędu 2n pierwszy gracz ma 2 czyste strategie, a drugi n czystych strategii, tj. Macierz wypłat dla pierwszego gracza to:

Jeśli taka gra ma punkt siodłowy, to łatwo go znaleźć i uzyskać rozwiązanie.

Załóżmy, że gra ma punkty siodłowe. Następnie należy znaleźć takie strategie mieszane i odpowiednio pierwszego i drugiego gracza oraz cenę gry v, które spełniają zależności:

Ponieważ gra nie ma punktu siodłowego, nierówność (1,54) zostaje zastąpiona nierównościami

Do rozwiązywania układów (1.56), (1.55), (1.53) celowe jest użycie metody graficznej. W tym celu wprowadzamy oznaczenie dla lewej strony nierówności (1.53)

model matematyczny gry macierzowej

lub wychodząc z (1.55) i wykonując proste przekształcenia, otrzymujemy

gdzie jest średnia wypłata pierwszego gracza, pod warunkiem, że stosuje swoją strategię mieszaną, a drugiego - jego j-tej czystej strategii.

Zgodnie z wyrażeniem każda wartość j=1, 2, …, n odpowiada prostej w prostokątnym układzie współrzędnych.

Celem drugiego gracza jest zminimalizowanie wypłaty pierwszego gracza poprzez wybór jego strategii. Dlatego obliczamy

gdzie jest dolna granica zestawu ograniczeń. Na rysunku 1.6 wykres funkcji jest pokazany grubą linią.

Hostowane na http://www.allbest.ru/

Rysunek 1.6 – wykres funkcji

Celem pierwszego gracza jest maksymalizacja swojej wypłaty poprzez wybór, tj. Oblicz

Na rycinie 1.6 kropka oznacza maksymalną wartość uzyskaną przy. Cena gry, ponieważ:

W ten sposób optymalna strategia mieszana pierwszego gracza i para czystych strategii drugiego gracza są wyznaczane graficznie, które tworzą punkt na przecięciu.Rysunek 1.6 pokazuje 2. i 3. strategię drugiego gracza. Dla takich strategii nierówności (1,53) zamieniają się w równości. Na rysunku 1.6 są to strategie j=2, j=3.

Teraz możemy rozwiązać układ równań

i dokładnie określić wartości i (graficznie są one określane w przybliżeniu). Następnie umieszczając wszystkie wartości w tych j, dla których nie tworzą one punktu, rozwiązując układ równań (1.56) Dla przykładu pokazanego na rysunku 1.6 jest to następujący system:

i reszta Układ ten można rozwiązać nachylając Jeśli dla pewnych j=j 0 strategie drugiego gracza tworzą punkt M 0 i wtedy maksymalna wartość dolnej granicy zbiorów ograniczeń jest reprezentowana przez odcinek równoległy do oś W tym przypadku pierwszy gracz ma nieskończenie wiele optymalnych wartości i ceny gry Ten przypadek pokazano na rysunku 1.7, gdzie i odcinek MN reprezentują górną granicę, optymalne wartości mieszczą się w granicach. drugi gracz ma czystą strategię optymalną j=j 0 .

Gry macierzowe rzędu m2 są również rozwiązywane metodą graficzną. Macierz wypłat pierwszego gracza ma w tym przypadku postać

Strategie mieszane odpowiednio pierwszego i drugiego gracza są definiowane w taki sam sposób jak w grach rzędu 2n. Niech wartość od 0 do 1 zostanie wykreślona na osi poziomej, wartość średniej wypłaty) pierwszego gracza na osi pionowej pod warunkiem, że pierwszy gracz zastosuje swoją czystą i-tą strategię (i=1, 2, ..., m), drugi - jego strategia mieszana (y 1 , 1- y 1) = y. Na przykład, gdy graficznie m=4) można przedstawić tak, jak pokazano na rysunku 1.7.

Rysunek 1.7 - wykres funkcji)

Pierwszy gracz stara się zmaksymalizować swoją średnią wypłatę, więc próbuje znaleźć

Funkcja jest pokazana jako gruba linia i reprezentuje górną granicę zestawu ograniczeń. Drugi gracz stara się zminimalizować, wybierając swoją strategię, tj. wartość odpowiada

Na rysunku wartość jest oznaczona kropką. Innymi słowy, określa się takie dwie strategie pierwszego gracza i prawdopodobieństwo drugiego gracza, dla których równość zostanie osiągnięta

Z rysunku widzimy, że cena gry jest rzędną punktu, prawdopodobieństwo jest odciętą punktu. Dla reszty czystych strategii pierwszego gracza w optymalnej strategii mieszanej musi ().

W ten sposób rozwiązując układ (1.69) otrzymujemy optymalną strategię drugiego gracza i wartość gry. Optymalną strategię mieszaną dla pierwszego gracza znajdujemy rozwiązując następujący układ równań:

1.7 Macierzowa metoda rozwiązywania gier

Oznaczenia:

Dowolna kwadratowa podmacierz macierzy rzędów

Matryca (1);

Matryca transponowana do;

Matryca dołączona do B;

- (1) macierz uzyskana z X poprzez usunięcie elementów odpowiadających wierszom usuniętym po otrzymaniu;

- (1) macierz uzyskana z usunięcia elementów odpowiadających wierszom usuniętym po otrzymaniu.

Algorytm:

1. Wybierz kwadratową podmacierz macierzy rzędów () i oblicz

2. Jeśli niektóre lub, odrzuć znalezioną macierz i wypróbuj inną macierz.

3. Jeżeli (), (), obliczamy i budujemy X oraz z i, dodając zera w odpowiednich miejscach.

Sprawdzenie, czy nierówności są spełnione

za każdy (1,75)

i nierówności

za każdy (1,76)

Jeśli jeden ze współczynników nie jest spełniony, próbujemy innego. Jeśli wszystkie relacje są poprawne, to X i pożądane rozwiązania.

1.8 Metoda sukcesywnego przybliżania ceny gry

W badaniu sytuacji w grze często może się zdarzyć, że uzyskanie dokładnego rozwiązania gry nie jest konieczne lub z jakiegoś powodu niemożliwe lub bardzo trudne jest znalezienie dokładnej wartości kosztu gry i optymalnych strategii mieszanych. Następnie możesz użyć przybliżonych metod rozwiązania gry macierzowej.

Opiszmy jedną z tych metod – metodę sukcesywnego przybliżania ceny gry. Liczba wypłat obliczonych tą metodą wzrasta w przybliżeniu proporcjonalnie do liczby wierszy i kolumn macierzy wypłat.

Istota metody polega na tym, że mentalnie gra się wielokrotnie, tj. kolejno, w każdej grze, gracz wybiera strategię, która daje mu największą ogólną (całkowitą) wypłatę.

Po takiej implementacji niektórych gier oblicza średnią wartość wygranej pierwszego gracza i przegranej drugiego gracza, a ich średnia arytmetyczna jest traktowana jako przybliżona wartość ceny gry. Metoda umożliwia znalezienie przybliżonej wartości optymalnych strategii mieszanych obu graczy: należy obliczyć częstotliwość stosowania każdej czystej strategii i przyjąć ją jako przybliżoną wartość w optymalnej strategii mieszanej odpowiedniego gracza.

Można udowodnić, że przy nieograniczonym wzroście liczby gier programowych średni zysk pierwszego gracza i średnia strata drugiego gracza będą zbliżać się w nieskończoność do ceny gry, a przybliżone wartości strategii mieszanych w przypadek, gdy rozwiązanie gry jest unikalne, będzie dążył do optymalnych strategii mieszanych każdego gracza. Ogólnie rzecz biorąc, przybliżenie wartości powyżej określonych wartości do wartości prawdziwych jest powolne. Proces ten można jednak łatwo zmechanizować, a tym samym pomóc w uzyskaniu rozwiązania gry z wymaganym stopniem dokładności nawet przy macierzach wypłat o stosunkowo dużym rzędzie.

2. Część praktyczna

Para decyduje, gdzie wybrać się na spacer i spędzić czas dla dobra dwojga.

Dziewczyna postanawia wyjść na spacer do parku, by zaczerpnąć świeżego powietrza, a wieczorem wybrać się na film do najbliższego kina.

Facet proponuje, że pójdzie do technoparku po obejrzeniu meczu piłkarzy lokalnego klubu na centralnym stadionie.

Zgodnie z tym musisz dowiedzieć się, jak długo cel jednego z graczy zostanie osiągnięty. Macierz wypłat będzie wyglądać następująco:

Tabela 1. Macierz wypłat

Od 1 2 , nie ma oczywiście punktu siodłowego w tej grze w czystych strategiach. Dlatego używamy następujących wzorów i otrzymujemy:

Hostowane na http://www.allbest.ru/

2.2 Granie 2xn i mx2

Zadanie 1(2xn)

W klimacie suchym i wilgotnym uprawia się dwie rośliny.

A stan natury można uznać za: suchy, mokry, umiarkowany.

Hostowane na http://www.allbest.ru/

Maksymalna wartość M() jest osiągnięta w punkcie M utworzonym przez przecięcie prostych odpowiadających j=1, j"=2. Zakładamy zatem: ,

Zadanie 2 (mx2)

Facet i dziewczyna zastanawiają się, gdzie wybrać się na weekend.

Wybór miejsca wypoczynku można przedstawić jako: park, kino, restauracja.

Hostowane na http://www.allbest.ru/

Maksymalna wartość M() jest osiągnięta w punkcie E utworzonym przez przecięcie prostych odpowiadających j=1, j"=2. Zakładamy zatem: ,

Aby określić wartość v, musisz rozwiązać następujące równania:

2.5 Metoda macierzowa

Dwie konkurencyjne restauracje (placówki gastronomiczne) świadczą następujące zestawy usług. Pierwsza restauracja zlokalizowana jest w centrum, druga na obrzeżach miasta.

Centralna restauracja obejmuje następujące usługi:

1) droższa i lepsza obsługa klienta;

2) dania nastawione są na kuchnię francuską;

Druga restauracja zapewnia:

1) niedroga i wysokiej jakości usługa;

2) menu łączy różne znane kuchnie świata;

3) także regularne promocje i rabaty;

4) realizuje dostawy i przyjmuje zamówienia z dostawą do domu.

Zgodnie z zadaniem zysk za jeden dzień pomiędzy dwiema restauracjami zostanie rozdzielony w następujący sposób:

Tabela 2. Macierz wypłat

Rozwiązywanie gry postaci w sposób macierzowy:

Istnieje sześć podmacierzy i:

Rozważ macierz:

x 1 =? 0,x2=? 0

Ponieważ x 2 =< 0, то мы отбрасываем.

Rozważmy teraz macierz:

x 1 =? 0,x2=? 0

Cena gry.

Ten stosunek jest sprzeczny z wymaganiami, więc nie jest odpowiedni.

Rozważmy teraz macierz:

x 1 = , x 2 = ? 0,

y 1 =< 0, y 2 = ? 0.

Ponieważ y 1 =< 0, то мы отбрасываем и.

Rozważmy teraz macierz:

x 1 \u003d, x 2 \u003d 0, ponieważ x 2 \u003d 0, to odrzucamy i.

Rozważmy teraz macierz:

x 1 = , x 2 = ? 0. Ponieważ x 1 \u003d 0, odrzucamy i.

Rozważmy teraz macierz:

x 1 = , x 2 =, y 1 = , y 2 =, to przechodzimy dalej:

x 1 = , x 2 =, y 1 = , y 2 = lub

Cena gry.

Teraz sprawdzane są główne relacje:

Hostowane na http://www.allbest.ru/

Odpowiedź: x 1 =, x 2 =, y 1 =, y 2 =, y 3 = 0, y 4 = 0,.

Metoda Browna

Na prośbę pracowników pewnej firmy związek zawodowy negocjuje ze swoim kierownictwem organizację ciepłych posiłków na koszt firmy. Związek zawodowy reprezentujący interesy pracowników dba o to, aby posiłek był najwyższej możliwej jakości, a przez to droższy. Kierownictwo firmy ma sprzeczne interesy. Ostatecznie strony uzgodniły, co następuje. Związek zawodowy (gracz 1) wybiera jedną z trzech firm (A 1 , A 2 , A 3) dostarczających gorące posiłki, a kierownictwo firmy (gracz 2) wybiera zestaw naczyń z trzech możliwych opcji (B 1 , B 2 , B3) . Po podpisaniu porozumienia związek zawodowy tworzy następującą macierz płatności, której elementy reprezentują koszt kompletu naczyń:

Niech gra będzie dana przez następującą macierz wypłat:

Załóżmy, że drugi gracz wybrał swoją drugą strategię, wtedy pierwszy otrzyma:

2 jeśli użyje swojej pierwszej strategii,

3, jeśli użyje swojej trzeciej strategii.

Uzyskane wartości zestawiono w tabeli 1.

Tabela 3. Strategia drugiego gracza

Tabela 3 pokazuje, że przy drugiej strategii drugiego gracza, pierwszy gracz otrzyma największą wypłatę 3 przy użyciu swojej drugiej lub trzeciej strategii. Ponieważ pierwszy gracz chce uzyskać maksymalną wypłatę, odpowiada swoją drugą strategią na drugą strategię drugiego gracza. Przy drugiej strategii pierwszego gracza drugi przegra:

1 jeśli zastosuje swoją pierwszą strategię,

3 jeśli użyje swojej drugiej strategii,

4, jeśli użyje swojej trzeciej strategii.

Tabela 4. Strategia pierwszego gracza

Tabela 2 pokazuje, że przy drugiej strategii pierwszego gracza, drugi gracz poniesie najmniejszą stratę 1, jeśli zastosuje swoją pierwszą strategię. Ponieważ drugi gracz chce stracić mniej, to w odpowiedzi na drugą strategię pierwszego gracza zastosuje swoją pierwszą strategię. Otrzymane wyniki podsumowano w tabeli 5.

Tabela 5. Strategie odpowiednio pierwszego i drugiego gracza

w tabeli. 5 w kolumnie strategii drugiego gracza w drugim wierszu znajduje się cyfra 1, która oznacza, że ​​w drugiej grze korzystne jest, aby drugi gracz zastosował swoją pierwszą strategię; w kolumnie i jest największą średnią wypłatą 3 pierwszego gracza, otrzymaną przez niego w pierwszej grze; kolumna w zawiera najmniejszą średnią stratę 1 otrzymaną przez drugiego gracza w pierwszej grze; kolumna v zawiera średnią arytmetyczną v = (u + w) — czyli przybliżoną wartość ceny gry, uzyskaną w wyniku rozegrania jednej partii gry. Jeśli drugi gracz użyje swojej 1. strategii, to pierwszy gracz otrzyma odpowiednio 3, 1, 2 ze swoimi 1., 2., 3. strategią, a łączna wypłata pierwszego gracza w obu grach wyniesie:

2 + 3=5 z jego 1. strategią,

3 + 1=4 z jego drugą strategią,

3 + 2=5 z jego trzecią strategią.

Te całkowite wygrane są zapisywane w drugim wierszu tabeli. 3 oraz w kolumnach odpowiadających strategiom pierwszego gracza: 1, 2, 3.

Ze wszystkich łącznych wypłat największa wynosi 5. Uzyskuje się ją za pomocą 1. i 3. strategii pierwszego gracza, następnie może on wybrać dowolną z nich; powiedzmy, w takich przypadkach, gdy są dwie (lub kilka) identyczne całkowite wypłaty, wybierana jest strategia z najmniejszą liczbą (w naszym przypadku musimy przyjąć pierwszą strategię).

Przy pierwszej strategii pierwszego gracza, drugi gracz straci odpowiednio 3, 2, 3 do swojej pierwszej, drugiej, trzeciej strategii, a łączna strata drugiego gracza w obu grach wyniesie:

1 + 3=4 z jego pierwszą strategią,

3 + 2=5 z jego drugą strategią,

4 + 3=7 z jego trzecią strategią.

Te całkowite straty są rejestrowane w drugim wierszu tabeli. 5 oraz w kolumnach odpowiadających 1., 2., 3. strategii drugiego gracza.

Ze wszystkich całkowitych strat drugiego gracza najmniejsza wynosi 4. Otrzymuje ją swoją pierwszą strategią, dlatego w trzeciej grze drugi gracz musi zastosować swoją pierwszą strategię. W kolumnie umieść największą łączną wypłatę pierwszego gracza w dwóch grach, podzieloną przez liczbę gier, tj.; kolumna w zawiera najmniejszą łączną przegraną drugiego gracza w dwóch grach, podzieloną przez liczbę gier, tj. ; średnią arytmetyczną tych wartości umieszcza się w kolumnie v, tj. = Ta liczba jest traktowana jako przybliżona wartość ceny gry z dwoma „rozegranymi” grami.

W ten sposób otrzymuje się następującą tabelę 4 dla dwóch zestawów gry.

Tabela 6. Suma zysków i strat graczy w dwóch rozegranych grach

W trzecim wierszu Tabeli 6, w kolumnie strategii drugiego gracza, znajduje się cyfra 1, która oznacza, że ​​w trzeciej grze drugi gracz musi zastosować swoją pierwszą strategię. W tym przypadku pierwszy gracz wygrywa 3, 1, 2, stosując odpowiednio swoją pierwszą, drugą i trzecią strategię, a jego całkowita wypłata za trzy gry będzie wynosić:

3 + 5 = 8 przy jego pierwszej strategii,

1 +4 = 5 z jego drugą strategią,

2 + 5 = 7 dla jego trzeciej strategii.

Te całkowite wypłaty pierwszego gracza są zapisane w trzecim wierszu tabeli 6 i kolumnach odpowiadających jego strategiom 1, 2, 3. Ponieważ największa łączna wypłata 8 pierwszego gracza jest uzyskiwana przy pierwszej strategii, wybiera on odpowiednio pierwszą strategię .

Przy 1. strategii pierwszego gracza, drugi gracz straci odpowiednio 3, 1, 2 do 1., 2., 3. strategii, a łączna strata drugiego gracza w obu grach wyniesie:

3 + 4=7 z jego pierwszą strategią,

2 + 5=7 z jego drugą strategią,

3 + 7=10 z jego trzecią strategią.

Te całkowite straty są rejestrowane w trzecim wierszu tabeli. 6 oraz w kolumnach odpowiadających 1., 2., 3. strategii drugiego gracza. Spośród wszystkich jego całkowitych strat 7 jest najmniejszą i uzyskuje się je za pomocą jego 1. i 2. strategii, wtedy drugi gracz musi zastosować swoją 1. strategię.

w tabeli. 6 w trzecim rzędzie w kolumnie i największa łączna wygrana pierwszego gracza w trzech grach podzielona przez numer gry, tj. ; kolumna w zawiera najmniejszą całkowitą przegraną drugiego gracza w trzech grach, podzieloną przez liczbę gier, czyli ; w kolumnie v umieść ich średnią arytmetyczną

W ten sposób otrzymujemy tabelę. 7 na trzy imprezy.

Tabela 7. Suma zysków i strat graczy w trzech rozegranych grach

Tabela 8. Stół finałowy z dwudziestoma rozegranymi partiami

Ze stołu. 7 i 8 widać, że w 20 przegranych grach strategie 1, 2, 3 dla pierwszego gracza występują odpowiednio 12, 3, 5 razy, zatem ich względne częstości są odpowiednio równe; strategie 1, 2, 3 dla drugiego gracza występują odpowiednio 7, 11,2 razy, stąd ich względne częstości są odpowiednio równe; przybliżona wartość ceny gry. To przybliżenie jest wystarczająco dobre.

Podsumowując, zauważamy, że jeśli gra ma więcej niż jedno rozwiązanie, to przybliżone wartości kosztu gry nadal będą zbliżać się do rzeczywistego kosztu gry w nieskończoność, a względne częstotliwości pojawiania się strategii gracze nie będą już koniecznie zbliżać się do prawdziwie optymalnych strategii mieszanych graczy.

Analiza wyników

W tej pracy kursowej materiał do znajdowania rozwiązań gier antagonistycznych jest badany metodą graficzną, macierzową, metodą kolejnych przybliżeń ceny gry. Wyznaczono optymalne strategie pierwszego i drugiego gracza oraz koszt gry w grach 2x2, 2xn i mx2, a także w grach wykorzystujących metodę macierzową i metodę Browna.

Na przykładzie pary zamodelowano grę 2x2, którą rozwiązano metodą algebraiczną i graficzną. Rozwiązując grę metodą algebraiczną, rozwiązanie pokazuje, że stosując swoje optymalne strategie mieszane, pierwszy i drugi gracz spędzą razem 4,6 godziny. Graficzne rozwiązanie problemu okazało się z małym błędem i trwało 4,5 godziny.

Modelowano również dwa zadania 2xn i mx2. W zadaniu 2xn wzięto pod uwagę kulturę rolniczą i ze strategii wynika, że ​​lepiej obsiać pole 50 na 50, a cena gry wyniosła 3,75 mln rubli. A w problemie mx2 rozważono parę, której strategia wykazała, że ​​​​taniej jest iść do parku i kina, a cena i koszt wyniosą 4,3 rubla.

Zadanie zostało zamodelowane dla metody macierzowej, w której rozpatrzono dwie restauracje, rozwiązanie problemu wykazało, że przy zastosowaniu jej optymalnej strategii mieszanej zysk pierwszej restauracji wyniesie 15,6 mln rubli, a przy zastosowaniu jej optymalnej strategii mieszanej przez drugiej restauracji, nie pozwoli pierwszej zarobić więcej niż 15,6 mln rubli. Rozwiązanie metodą graficzną dało błąd, a cena gry wyniosła 14,9 miliona rubli.

Dla metody Browna opracowano zadanie, w którym uwzględniono kierownictwo związku i firmy, których zadaniem jest zapewnienie żywności pracownikom. Kiedy obaj gracze zastosują swoje optymalne strategie, jedzenie na osobę wyniesie 2,45 tysiąca rubli.

Lista wykorzystanych źródeł

1) Vilisov V.Ya. Notatki z wykładów "Teoria gier i rozwiązania statystyczne", - Filia - "Woschod" MAI. 1979. 146 s.

2) Krushevsky A.V. Teoria gier, - Kijów: szkoła Vishcha, 1977. - 216 s.

3) Cherchmen U., Akof R., Arnof L., Wprowadzenie do badań operacyjnych. - M.: Nauka. 1967. - 488 s.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0 %B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

Hostowane na Allbest.ru

Podobne dokumenty

Podejmowanie decyzji jako szczególny rodzaj działalności człowieka. Racjonalne przedstawienie macierzy gry. Przykłady gier macierzowych w strategiach czystych i mieszanych. Badania operacyjne: związek problemów programowania liniowego z modelem teorii gier.

praca semestralna, dodano 05.05.2010


Wielokrotnie powtarzane gry, ich charakterystyczne właściwości i etapy. Strategie mieszane, warunki i możliwości ich wykorzystania w praktyce. Analityczna metoda rozwiązywania gry 2 x 2. Podstawowe twierdzenia dotyczące gier prostokątnych. Rozwiązania algebraiczne.

prezentacja, dodano 23.10.2013


Podstawowe definicje teorii gier dwumacierzowych. Przykład gry dwumacierzowej „Uczeń-Nauczyciel”. Strategie mieszane w grach dwumacierzowych. Wyszukaj „sytuację równowagi”. Gry bimacierzowe 2x2 i formuły dla przypadku, gdy każdy gracz ma dwie strategie.

streszczenie, dodano 13.02.2011


Badanie ogólnych informacji o grach macierzowych i antagonistycznych. Koncepcja gry pozycyjnej, drzewo, zestaw informacji. Uwzględnienie zasady maksymina i zasady równowagi. optymalność Pareto. Gra pozycyjna nieantagonistyczna, jej własności.

praca semestralna, dodano 17.10.2014


Teoria gier to dział matematyki, którego przedmiotem jest badanie modeli matematycznych służących do podejmowania optymalnych decyzji w konflikcie. Iteracyjna metoda Browna-Robinsona. Monotoniczny algorytm iteracyjny do rozwiązywania gier macierzowych.

praca dyplomowa, dodano 08.08.2007


Zestawienie macierzy wypłat, poszukiwanie dolnych i górnych cen netto gry, strategii maximin i minimax graczy. Uproszczenie macierzy płatności. Rozwiązywanie gry macierzowej z wykorzystaniem redukcji do problemu programowania liniowego i dodatku „Szukaj rozwiązania”.

test, dodano 11.10.2014


Teoria gier jest matematyczną teorią sytuacji konfliktowych. Opracowanie modelu matematycznego dwuosobowej gry o sumie zerowej, jego implementacja w postaci kodów programu. Metoda rozwiązywania problemów. Dane wejściowe i wyjściowe. Program, instrukcja obsługi.

praca semestralna, dodano 17.08.2013


Podstawowe informacje o metodzie simpleks, ocena jej roli i znaczenia w programowaniu liniowym. Interpretacja geometryczna i znaczenie algebraiczne. Znajdowanie maksimum i minimum funkcji liniowej, przypadki szczególne. Rozwiązanie problemu metodą matrix simplex.

praca dyplomowa, dodano 06.01.2015


Techniki konstruowania modeli matematycznych systemów komputerowych odzwierciedlających strukturę i procesy ich funkcjonowania. Liczba dostępów do plików podczas przeciętnego zadania. Określenie możliwości umieszczania plików na zewnętrznych nośnikach pamięci.

praca laboratoryjna, dodano 21.06.2013


Projektowanie modelu matematycznego. Opis gry w kółko i krzyżyk. Model gry logicznej oparty na algebrze Boole'a. Cyfrowe urządzenia elektroniczne i opracowanie ich modelu matematycznego. Konsola do gier, kontroler do gier, plansza do gry.

Teoria gier to teoria matematycznych modeli podejmowania decyzji w warunkach konfliktu lub niepewności. Przyjmuje się, że działania stron w grze charakteryzują się pewnymi strategiami – zbiorami reguł działania. Jeśli zysk jednej strony nieuchronnie prowadzi do utraty drugiej strony, wtedy mówi się o grach antagonistycznych. Jeśli zestaw strategii jest ograniczony, wtedy gra nazywa się grą macierzową, a rozwiązanie można uzyskać w bardzo prosty sposób. Rozwiązania otrzymane za pomocą teorii gier są przydatne w konstruowaniu planów w obliczu ewentualnego sprzeciwu ze strony konkurentów lub niepewności w otoczeniu zewnętrznym.

Jeżeli gra dwumacierzowa jest antagonistyczna, to macierz wypłat gracza 2 jest całkowicie zdeterminowana przez macierz wypłat gracza 1 (odpowiadające sobie elementy tych dwóch macierzy różnią się tylko znakami). Dlatego antagonistyczna gra dwumacierzowa jest całkowicie opisana przez pojedynczą macierz (macierz wypłat gracza 1) i odpowiednio nazywana jest grą macierzową.

Ta gra jest antagonistyczna. W nim j \u003d x2 - O, P i R (O, O] \u003d H (P, P) \u003d -I i R (O, P) \u003d R (P, O) \u003d 1 lub w formie macierzowej o str

Niech jakaś klasa gier Г będzie „lustrzana”, tj. wraz z każdą ze swoich gier zawiera lustrzaną grę izomorficzną (skoro wszystkie gry, które są lustrzanie izomorficzne względem danej gry, są między sobą izomorficzne, to zgodnie z tym, co przed chwilą powiedziano, możemy mówić o jednej grze lustrzano izomorficznej). Taką klasą jest na przykład klasa wszystkich gier antagonistycznych lub klasa wszystkich gier macierzowych.

Przywołując definicję dopuszczalnych sytuacji w grze antagonistycznej, otrzymujemy, że sytuacja (X, Y) w mieszanym rozszerzeniu gry macierzowej jest akceptowalna dla gracza 1 wtedy i tylko wtedy, gdy dla dowolnego x G x nierówność

Proces przekształcania gier w gry symetryczne nazywa się symetryzacją. Opisujemy tutaj jedną metodę symetryzacji. Inna, zasadniczo odmienna wersja symetryzacji zostanie podana w podrozdziale 26.7. Oba te warianty symetryzacji mają w rzeczywistości zastosowanie do dowolnych gier antagonistycznych, ale zostaną sformułowane i udowodnione tylko dla gier macierzowych.

Zatem początkowe terminy i oznaczenia teorii ogólnych gier antagonistycznych pokrywają się z odpowiednimi terminami i oznaczeniami teorii gier macierzowych.

W przypadku skończonych gier antagonistycznych (macierzowych) istnienie tych ekstremów zostało przez nas udowodnione w rozdziale 10. 1, a cała rzecz polegała na ustaleniu ich równości lub przynajmniej znalezieniu sposobów na przezwyciężenie ich nierówności.

Rozważanie gier macierzowych pokazuje już, że istnieją gry antagonistyczne bez sytuacji równowagi (a nawet bez sytuacji e-równowagi dla odpowiednio małego e > 0) w początkowo zadanych strategiach graczy.

Ale każdą grę skończoną (macierzową) można rozszerzyć do gry nieskończonej, na przykład poprzez zapewnienie każdemu graczowi dowolnej liczby strategii zdominowanych (patrz 22 rozdz. 1). Oczywiście takie rozszerzenie zestawu strategii gracza nie będzie tak naprawdę oznaczało rozszerzenia jego możliwości, a jego rzeczywiste zachowanie w grze rozszerzonej nie powinno różnić się od jego zachowania w grze oryginalnej. W ten sposób od razu uzyskaliśmy wystarczającą liczbę przykładów nieskończonych gier antagonistycznych, które nie mają punktów siodłowych. Istnieją również tego rodzaju przykłady.

Aby zatem zrealizować zasadę maksymina w nieskończonej grze antagonistycznej, konieczne jest, podobnie jak w przypadku gry skończonej (macierzowej), pewne rozszerzenie możliwości strategicznych graczy. dla 96

Podobnie jak w przypadku gier macierzowych (zob. rozdz. 1, 17), w przypadku gier o charakterze generalnie antagonistycznym ważną rolę odgrywa pojęcie spektrum strategii mieszanych, które tutaj jednak wymaga bardziej ogólnego zdefiniowania.

Na koniec zauważmy, że zbiór wszystkich strategii mieszanych gracza 1 w dowolnej grze antagonistycznej jest taki, jak w macierzy

Nawet rozważenie gier antagonistycznych pokazuje, że duża liczba takich gier, w tym skończonych gier macierzowych, ma sytuacje równowagi nie w oryginalnych, czystych strategiach, ale tylko w uogólnionych, mieszanych strategiach. Dlatego w przypadku ogólnych, nieantagonistycznych, niekooperacyjnych gier naturalne jest szukanie sytuacji równowagi właśnie w strategiach mieszanych.

Na przykład (patrz rys. 3.1) zauważyliśmy już, że „Kontrahent” prawie nigdy nie ma do czynienia z niepewnością behawioralną. Ale jeśli weźmiemy poziom koncepcyjny typu „Administrator”, wtedy wszystko jest dokładnie odwrotnie. Z reguły głównym rodzajem niepewności, z którym musi się zmierzyć taki „nasz decydent”, jest „Konflikt”. Teraz możemy wyjaśnić, że jest to zazwyczaj nieścisła rywalizacja. Nieco rzadziej „Administrator” podejmuje decyzje w warunkach „naturalnej niepewności”, a jeszcze rzadziej spotyka się z ostrym, antagonistycznym konfliktem. Poza tym zderzenie interesów przy podejmowaniu decyzji przez „Administratora” zdarza się niejako „raz”, czyli w naszej klasyfikacji często rozgrywa on tylko jedną (niekiedy bardzo małą liczbę) partii gry. Skale oceny konsekwencji są częściej jakościowe niż ilościowe. Strategiczna niezależność „Administratora” jest raczej ograniczona. Biorąc pod uwagę powyższe, można stwierdzić, że sytuacje problemowe tej wielkości najczęściej muszą być analizowane przy użyciu niekooperacyjnych nieantagonistycznych gier dwumacierzowych, zresztą w czystych strategiach.

Zasady rozwiązywania macierzy antagonistycznych gier

W efekcie zasadne jest oczekiwanie, że w opisanej powyżej grze przeciwnicy będą trzymać się obranych przez siebie strategii. Matrycowa gra antagonistyczna, dla której max min fiv = min max Aiy>

Jednak nie wszystkie antagonistyczne gry matrixa są całkiem określone iw ogólnym przypadku

Tak więc, w ogólnym przypadku, aby rozwiązać macierzową grę antagonistyczną o wymiarze /uxl, konieczne jest rozwiązanie pary dualnych problemów programowania liniowego , co daje zestaw optymalnych strategii , / i koszt gry v.

Jak definiowana jest macierzowa antagonistyczna gra dwóch osób?

Jakie są metody upraszczania i rozwiązywania macierzowych gier antagonistycznych

W przypadku gry dwuosobowej naturalne jest traktowanie ich interesów jako przeciwstawnych – gra jest antagonistyczna. Zatem wypłata jednego gracza jest równa stracie drugiego (suma wypłat obu graczy wynosi zero, stąd nazwa gra o sumie zerowej). Rozważymy gry, w których każdy gracz ma skończoną liczbę alternatyw. Funkcję wypłaty dla takiej dwuosobowej gry o sumie zerowej można podać w postaci macierzowej (w postaci macierzy wypłat).

Jak już wspomniano, ostateczna antagonistyczna gra nazywa się matrix.

GRY MATRYCOWE – klasa gier antagonistycznych, w których bierze udział dwóch graczy, a każdy gracz ma skończoną liczbę strategii. Jeśli jeden gracz ma m strategii, a drugi n strategii, to możemy skonstruować macierz gry o wymiarze txn. Mi. może mieć punkt siodłowy lub nie. W tym ostatnim przypadku

Rozważ skończoną grę w pary o sumie zerowej. Oznacz przez a wypłata gracza A i przez b- zwycięstwo gracza B. Dlatego a = –b, to analizując taką grę nie trzeba brać pod uwagę obu tych liczb – wystarczy wziąć pod uwagę wypłatę jednego z graczy. Niech to będzie np. A. Poniżej, dla wygody prezentacji, z boku A warunkowo nazwiemy „ my"i z boku B – "wróg".

Pozwól nam mieć m możliwe strategie A 1 , A 2 , …, Rano i wroga n możliwe strategie B 1 , B 2 , …, B n(taka gra nazywa się grą m×n). Załóżmy, że każda ze stron wybrała określoną strategię: my wybraliśmy Aj, przeciwnik Bj. Jeśli gra składa się tylko z ruchów osobistych, to wybór strategii Aj oraz Bj jednoznacznie określa wynik gry - naszą wypłatę (dodatnią lub ujemną). Oznaczmy ten zysk jako aj(wygrana, gdy wybieramy strategię Aj, a wróg - strategie Bj).

Jeśli gra zawiera, oprócz osobistych losowych ruchów, to wypłata dla pary strategii Aj, Bj jest zmienną losową, która zależy od wyników wszystkich ruchów losowych. W tym przypadku naturalne oszacowanie oczekiwanej wypłaty wynosi matematyczne oczekiwanie losowej wygranej. Dla wygody oznaczymy przez aj zarówno samą wypłatę (w grze bez ruchów losowych), jak i jej matematyczne oczekiwanie (w grze z ruchami losowymi).

Załóżmy, że znamy wartości aj dla każdej pary strategii. Te wartości można zapisać jako macierz, której wiersze odpowiadają naszym strategiom ( Aj), a kolumny przedstawiają strategie przeciwnika ( Bj):

Taka macierz nazywa się macierz wypłat w grze lub po prostu matryca gry.

Należy zauważyć, że konstrukcja macierzy wypłat dla gier z dużą liczbą strategii może być trudnym zadaniem. Na przykład dla gry w szachy liczba możliwych strategii jest tak duża, że ​​skonstruowanie macierzy wypłat jest praktycznie niemożliwe. Jednak w zasadzie każdą skończoną grę można sprowadzić do postaci macierzowej.

Rozważać Przykład 1 Antagonistyczna gra 4×5. Mamy do dyspozycji cztery strategie, wróg ma pięć strategii. Matryca gry wygląda następująco:

Jaką strategię powinniśmy (czyli gracz A) używać? Bez względu na to, jaką strategię wybierzemy, rozsądny przeciwnik odpowie na nią strategią, dla której nasza wypłata będzie minimalna. Na przykład, jeśli wybierzemy strategię A 3 (skuszony wygraną 10), przeciwnik w odpowiedzi wybierze strategię B 1 , a nasza wypłata wyniesie tylko 1. Oczywiście kierując się zasadą ostrożności (a jest to główna zasada teorii gier), musimy wybrać strategię, w której nasz minimalny zysk jest maksymalny.

Oznacz przez ja minimalna wartość wypłaty dla strategii Aj:

i dodaj kolumnę zawierającą te wartości do macierzy gry:

Wybierając strategię, musimy wybrać tę, dla której wartość ja maksymalny. Oznaczmy tę maksymalną wartość przez α :

Wartość α zwany niższa cena gry lub maksymina(maksymalna minimalna wygrana). Strategia gracza A odpowiada maksiminowi α , nazywa się strategia maximina.

W tym przykładzie maximin α jest równa 3 (odpowiednia komórka w tabeli jest podświetlona na szaro), a strategia maximin jest równa A 4 . Wybierając taką strategię możemy być pewni, że za każde zachowanie wroga wygramy nie mniej niż 3 (a może więcej przy „nierozsądnym” zachowaniu wroga).Ta wartość to nasze gwarantowane minimum, które możemy zapewnić na siebie, stosując najbardziej ostrożną („reasekuracyjną”) strategię.

Teraz przeprowadzimy podobne rozumowanie dla wroga B B A B 2 - odpowiemy mu A .

Oznacz przez βj A B) dla strategii Aj:

βj β :

7. CZYM JEST GRA NA WYŻSZĄ WARTOŚĆ Teraz przeprowadzimy podobne rozumowanie dla przeciwnika B. Jest zainteresowany minimalizacją naszego zysku, czyli dawaniem nam mniej, ale musi liczyć na nasze zachowanie, które jest dla niego najgorsze. Na przykład, jeśli wybierze strategię B 1 , wtedy odpowiemy mu strategią A 3 , a da nam 10. Jeśli zechce B 2 - odpowiemy mu A 2 , a on da 8 itd. Oczywiście ostrożny przeciwnik musi wybrać strategię w której nasz maksymalny zysk będzie minimalny.

Oznacz przez βj maksymalne wartości w kolumnach macierzy wypłat (maksymalna wypłata gracza A lub, co jest tym samym, maksymalna strata gracza B) dla strategii Aj:

i dodaj wiersz zawierający te wartości do macierzy gry:

Wybierając strategię, wróg będzie preferował tę, dla której wartość βj minimum. Oznaczmy to przez β :

Wartość β zwany najwyższa cena gry lub minimaks(minimalna maksymalna wygrana). Strategia przeciwnika (gracza) odpowiadająca minimaksowi B), nazywa się strategia minimaksu.

Minimax to wartość zysku, powyżej którego rozsądny przeciwnik na pewno nam nie da (innymi słowy rozsądny przeciwnik nie straci więcej niż β ). W tym przykładzie minimaks β jest równa 5 (odpowiednia komórka w tabeli jest podświetlona na szaro) i jest osiągana dzięki strategii przeciwnika B 3 .

Opierając się więc na zasadzie ostrożności („zawsze spodziewaj się najgorszego!”), musimy wybrać strategię A 4 , a wróg - strategia B 3 . Zasada ostrożności jest fundamentalna w teorii gier i nazywana jest zasada minimaksu.

Rozważać przykład 2. Niech gracze A oraz W jedna z trzech liczb jest zapisywana jednocześnie i niezależnie od siebie: „1”, „2” lub „3”. Jeśli suma zapisanych liczb jest parzysta, gracz B płaci graczowi A ta ilość. Jeśli kwota jest nieparzysta, gracz płaci tę kwotę A gracz W.

Zapiszmy macierz wypłat gry i znajdźmy dolną i górną cenę gry (numer strategii odpowiada zapisanej liczbie):

Gracz A musi stosować się do strategii maximin A 1, aby wygrać co najmniej -3 (czyli przegrać co najwyżej 3). Strategia gracza Minimax B którąkolwiek ze strategii B 1 i B 2 , co gwarantuje, że nie da więcej niż 4.

Ten sam wynik otrzymamy, jeśli napiszemy macierz wypłat z punktu widzenia gracza W. W rzeczywistości matrycę tę uzyskuje się poprzez transpozycję macierzy skonstruowanej z punktu widzenia gracza A, oraz zmiana znaków elementów na przeciwne (od wypłaty gracza A oznacza stratę gracza W):

Na podstawie tej macierzy wynika, że ​​gracz B musi stosować się do którejkolwiek ze strategii B 1 i B 2 (i wtedy straci nie więcej niż 4) i gracza A– strategie A 1 (a wtedy straci nie więcej niż 3). Jak widać wynik jest dokładnie taki sam jak ten uzyskany powyżej, więc analiza nie ma znaczenia z punktu widzenia jakiego gracza ją przeprowadzamy.

8 CO TO JEST WARTOŚCIOWA GRA.

9. Z CZEGO SKŁADA SIĘ ZASADA MINIMAX. 2. Dolna i górna cena gry. Zasada minimaksu

Rozważmy grę macierzową typu z macierzą wypłat

Jeśli gracz ORAZ wybierze strategię ja, to wszystkie możliwe wypłaty będą elementami ja-ty wiersz macierzy Z. Najgorsze dla zawodnika ORAZ przypadku, gdy gracz W stosuje odpowiednią strategię minimum element tej linii, wypłata gracza ORAZ będzie równa liczbie.

Dlatego, aby uzyskać maksymalną wypłatę, gracz ORAZ musisz wybrać jedną ze strategii, dla której numer maksymalny.

Najprostszym przypadkiem, szczegółowo omówionym w teorii gier, jest gra skończonych par o sumie zerowej (antagonistyczna gra dwóch osób lub dwóch koalicji). Rozważmy grę G, w której biorą udział dwaj gracze A i B, mający przeciwne interesy: zysk jednego jest równy stracie drugiego. Ponieważ wypłata gracza A jest równa wypłacie gracza B z przeciwnym znakiem, możemy interesować się tylko wypłatą gracza a. Oczywiście A chce zmaksymalizować, a B chce zminimalizować a.

Dla uproszczenia utożsamijmy się mentalnie z jednym z graczy (niech to będzie A) i nazwijmy go „my”, a gracza B – „przeciwnikiem” (oczywiście żadne realne korzyści dla A nie wynikają z tego). Miejmy strategie możliwe, a przeciwnika strategie możliwe (taka gra nazywa się grą). Oznaczmy naszą wypłatę, jeśli my stosujemy strategię, a przeciwnik stosuje strategię

Tabela 26.1

Załóżmy, że dla każdej pary strategii znana jest wypłata (lub średnia wypłata) a. Wtedy w zasadzie można sporządzić prostokątną tabelę (macierz), która zawiera strategie graczy i odpowiadające im wypłaty (patrz tabela 26.1).

Jeśli taka tabela zostanie ułożona, to mówi się, że gra G jest zredukowana do postaci macierzowej (samo doprowadzenie gry do takiej postaci może już być zadaniem trudnym, a czasem praktycznie niemożliwym, ze względu na ogromną liczbę strategii ). Zauważ, że jeśli gra jest zredukowana do postaci macierzowej, to gra z wieloma ruchami jest właściwie zredukowana do gry z jednym ruchem - gracz musi wykonać tylko jeden ruch: wybrać strategię. Pokrótce oznaczymy macierz gry

Rozważmy przykład gry G (4X5) w postaci macierzowej. Do naszej dyspozycji (do wyboru) cztery strategie, wróg ma pięć strategii. Matrycę gry przedstawiono w tabeli 26.2

Zastanówmy się, jakiej strategii używamy my (gracz A)? Matrix 26.2 ma kuszącą wypłatę „10”; ciągnie nas do wyboru strategii, w której dostaniemy ten „smakołyk”.

Ale poczekaj, wróg też nie jest głupi! Jeśli wybierzemy strategię, on na złość wybierze strategię , a my dostaniemy marną wypłatę „1”. Nie, nie możesz wybrać strategii! Jak być? Oczywiście wychodząc z zasady ostrożności (a jest to główna zasada teorii gier), musimy wybrać strategię, dla której nasz minimalny zysk jest maksymalny.

Tabela 26.2

Jest to tak zwana „zasada mini-max”: działaj w taki sposób, aby przy najgorszym zachowaniu przeciwnika uzyskać maksymalny zysk.

Przepiszmy tabelę 26.2 iw prawej dodatkowej kolumnie wpisujemy minimalną wartość wzmocnienia w każdym wierszu (minimum wiersza); oznaczmy to dla wiersza a (patrz tabela 26.3).

Tabela 26.3

Spośród wszystkich wartości (prawa kolumna) wybierana jest największa (3). Pasuje do strategii. Decydując się na tę strategię, możemy być w każdym przypadku pewni, że (za dowolne zachowanie przeciwnika) zyskamy nie mniej niż 3. Ta wartość jest naszym gwarantowanym zyskiem; zachowując się ostrożnie, nie możemy dostać mniej niż to, możemy dostać więcej).

Wypłata ta nazywana jest niższą ceną gry (lub „maximin” – maksimum z minimalnych wypłat). Oznaczymy to jako a. W naszym przypadku

Przyjmijmy teraz punkt widzenia wroga i spierajmy się za nim. Nie jest jakimś pionkiem, ale też rozsądnym! Wybierając strategię, chciałby dać mniej, ale musi liczyć się z naszym zachowaniem, które jest dla niego najgorsze. Jeśli wybierze strategię, odpowiemy mu, a on da 10; jeśli wybierze, odpowiemy mu, a on zwróci itd. Do tabeli 26.3 dodajemy dodatkowy dolny wiersz i wpisujemy w nim maksima kolumn.Oczywiście ostrożny przeciwnik musi wybrać strategię, dla której ta wartość jest minimalna (odpowiednia wartość 5 jest zaznaczona w tabeli 26.3) . Ta wartość P to wartość zysku, ponad którą rozsądny przeciwnik na pewno nam nie da. Nazywa się to górną ceną gry (lub „mi-nimax” - minimum maksymalnej wygranej). W naszym przykładzie i jest osiągany ze strategią przeciwnika

Opierając się więc na zasadzie ostrożności (reguła reasekuratorów „licz się zawsze na najgorsze!”), musimy wybrać strategię A i wroga – strategię. Takie strategie nazywane są „minimax” (zgodnie z zasadą minimax). Tak długo, jak obie strony w naszym przykładzie będą trzymać się swoich strategii minimaksowych, wypłata będzie

A teraz wyobraź sobie przez chwilę, że dowiedzieliśmy się, że wróg postępuje zgodnie ze strategią. Daj spokój, karzemy go za to i wybieramy strategię, dostajemy 5, a to nie jest takie złe. Ale w końcu wróg też nie jest chybiony; daj mu znać, że nasza strategia to , on też pospieszy się z wyborem , zmniejszając naszą wypłatę do 2 itd. (partnerzy „rzucili się po strategiach”). Krótko mówiąc, strategie minimax w naszym przykładzie są niestabilne w odniesieniu do informacji o zachowaniu drugiej strony; strategie te nie mają właściwości równowagi.

Czy zawsze tak jest? Nie, nie zawsze. Rozważmy przykład z macierzą podaną w tabeli 26.4.

W tym przykładzie dolna cena gry jest równa górnej: . Co z tego wynika? Strategie minimax graczy A i B będą stabilne. Tak długo, jak obaj gracze będą się ich trzymać, wypłata wynosi 6. Zobaczmy, co się stanie, jeśli (A) dowiemy się, że przeciwnik (B) trzyma się strategii B?

Tabela 26.4

I właściwie nic się nie zmieni, bo każde odstępstwo od strategii może tylko pogorszyć naszą sytuację. Podobnie informacje otrzymane przez przeciwnika nie skłonią go do wycofania się ze swojej strategii. Oznaką obecności punktu siodłowego i zrównoważonej pary strategii jest równość dolnej i górnej ceny gry; łączna wartość nazywana jest ceną gry. Oznakujemy to

Strategie (w tym przypadku ), przy których osiąga się ten zysk, nazywane są optymalnymi czystymi strategiami, a ich kombinacja jest rozwiązaniem gry. W tym przypadku mówi się, że sama gra jest rozwiązana w czystych strategiach. Obie strony A i B mogą otrzymać swoje optymalne strategie, w których ich pozycja jest najlepsza z możliwych. I ten gracz A wygrywa 6, a gracz B przegrywa, cóż, takie są warunki gry: są one korzystne dla A i niekorzystne dla B.

Czytelnik może mieć pytanie: dlaczego optymalne strategie nazywane są „czystymi”? Wybiegając trochę w przyszłość, odpowiedzmy sobie na to pytanie: istnieją strategie „mieszane”, które polegają na tym, że gracz stosuje nie jedną strategię, ale kilka, naprzemiennie losowo. Jeśli więc przyjmiemy, oprócz czystych, także strategie mieszane, każda gra skończona ma rozwiązanie - punkt równowagi. Ale więcej na ten temat dopiero przed nami.

Obecność punktu siodłowego w grze nie jest regułą, a raczej wyjątkiem. Większość gier nie ma punktu siodłowego. Istnieje jednak wiele gier, które zawsze mają punkt siodłowy i dlatego są rozwiązywane w czystych strategiach. Są to tak zwane „gry z pełną informacją”. Gra z pełną informacją to gra, w której każdy gracz zna całą prehistorię swojego rozwoju przy każdym osobistym ruchu, czyli wyniki wszystkich poprzednich ruchów, zarówno osobistych, jak i losowych. Przykładami gier z pełnymi informacjami są warcaby, szachy, kółko i krzyżyk itp.

W teorii gier udowodniono, że każda gra z pełną informacją ma punkt siodłowy, a zatem może być rozwiązana w czystych strategiach. W każdej grze z doskonałą informacją istnieje para optymalnych strategii, która daje stabilną wypłatę równą cenie gry i. Jeśli taka gra składa się tylko z osobistych posunięć, to kiedy każdy gracz stosuje swoją optymalną strategię, musi się ona zakończyć w dość określony sposób - z wypłatą równą cenie gry. Jeśli więc rozwiązanie gry jest znane, sama gra traci sens!

Weźmy elementarny przykład gry z pełną informacją: dwóch graczy na przemian kładzie monety na okrągłym stole, wybierając dowolnie położenie środka monety (niedopuszczalne jest wzajemne nakładanie się monet). Wygrywa ten, kto dołoży ostatni grosz (gdy nie ma już miejsca dla innych). Łatwo zauważyć, że wynik tej gry jest zasadniczo przesądzony. Istnieje pewna strategia, która gwarantuje, że gracz, który pierwszy postawi monetę, wygrywa.

Mianowicie musi po raz pierwszy położyć pięciocentówkę na środek stołu, a następnie na każdy ruch przeciwnika odpowiedzieć ruchem symetrycznym. Oczywiście, bez względu na to, jak zachowuje się przeciwnik, nie da się uniknąć przegranej. Sytuacja jest dokładnie taka sama w przypadku szachów i gier z kompletną informacją w ogóle: każda z nich, zapisana w formie macierzowej, ma punkt siodłowy, a zatem rozwiązanie jest w czystych strategiach, a zatem ma sens tylko tak długo, jak to rozwiązanie ma nie znaleziono. Powiedzmy gra w szachy albo zawsze kończy się zwycięstwem białych, albo zawsze kończy się zwycięstwem czarnych, albo zawsze kończy się remisem, ale co dokładnie – jeszcze nie wiemy (na szczęście dla miłośników szachów). Dodajmy jeszcze jedno: raczej nie dowiemy się w dającej się przewidzieć przyszłości, bo ilość strategii jest tak ogromna, że ​​niezwykle trudno (jeśli nie niemożliwie) sprowadzić grę do postaci macierzowej i znaleźć w niej punkt siodłowy.

A teraz zastanówmy się, co zrobić, jeśli gra nie ma punktu siodłowego: Cóż, jeśli każdy gracz jest zmuszony wybrać jedną czystą strategię, to nie ma nic do zrobienia: musimy kierować się zasadą minimax. Inną rzeczą jest to, że jeśli możesz „mieszać” swoje strategie, naprzemiennie je losowo z pewnymi prawdopodobieństwami. Stosowanie strategii mieszanych jest pomyślane w ten sposób: gra jest powtarzana wiele razy; przed każdą partią gry, gdy gracz otrzymuje osobisty ruch, „powierza” swój wybór przypadkowi, „rzuca losy” i przyjmuje strategię, która wypadła (wiemy już, jak zorganizować losowanie z poprzedniego rozdziału ).

Strategie mieszane w teorii gier to model zmiennej, elastycznej taktyki, gdy żaden z graczy nie wie, jak przeciwnik zachowa się w danej grze. Ta taktyka (choć zwykle bez uzasadnienia matematycznego) jest często stosowana w gry karciane. Zauważmy jednocześnie, że najlepszym sposobem na ukrycie swojego zachowania przed wrogiem jest nadanie mu losowego charakteru, a więc nie wiedzieć z góry, co zrobisz.

Porozmawiajmy więc o strategiach mieszanych. Będziemy oznaczać strategie mieszane odpowiednio graczy A i B

W szczególnym przypadku, gdy wszystkie prawdopodobieństwa, z wyjątkiem jednego, są równe zero, a to jest równe jeden, strategia mieszana zamienia się w czystą.

Istnieje fundamentalne twierdzenie teorii gier: każda dwuosobowa gra o skończonej sumie zerowej ma co najmniej jedno rozwiązanie - parę optymalnych strategii, na ogół mieszanych, oraz odpowiadającą im cenę

Para optymalnych strategii tworzących rozwiązanie gry ma następującą właściwość: jeśli jeden z graczy trzyma się swojej optymalnej strategii, to drugiemu nie może być opłacalne odejście od jego strategii. Ta para strategii tworzy rodzaj równowagi w grze: jeden gracz chce obrócić wypłatę do maksimum, drugi do minimum, każdy ciągnie w swoją stronę i przy rozsądnym zachowaniu obu, równowaga i ustalona jest stała wypłata v. Jeśli więc gra jest korzystna dla nas, jeśli - dla wroga; gdy gra jest „fair”, jednakowo korzystna dla obu uczestników.

Rozważ przykład gry bez punktu siodłowego i podaj (bez dowodu) jej rozwiązanie. Gra przebiega następująco: dwóch graczy A i B jednocześnie i bez słowa pokazuje jeden, dwa lub trzy palce. O wygranej decyduje łączna liczba palców: jeśli jest parzysta, A wygrywa i otrzymuje od B kwotę równą tej liczbie; jeśli jest nieparzysta, to wręcz przeciwnie, A płaci B kwotę równą tej liczbie. Co powinni zrobić gracze?

Stwórzmy macierz gry. W jednej grze każdy gracz ma trzy strategie: pokaż jeden, dwa lub trzy palce. Macierz 3x3 podana jest w tabeli 26.5; dodatkowa prawa kolumna pokazuje minima wierszy, a dodatkowy dolny wiersz pokazuje maksima kolumn.

Niższa cena gry jest zgodna ze strategią, co oznacza, że ​​przy rozsądnym, ostrożnym zachowaniu gwarantujemy, że nie stracimy więcej niż 3. Małe pocieszenie, ale i tak lepsze niż, powiedzmy, wygrana - 5, znalezione w niektórych komórkach matrycy. Niekorzystnie nam to idzie, graczowi L... Ale pocieszmy się: pozycja przeciwnika wydaje się być jeszcze gorsza: niższa cena gry na. rozsądne zachowanie, da nam minimum 4.