Z teorii gier wiadomo, że jeśli gracz „A” zastosuje swoją optymalną strategię, a gracz „B” pozostanie w ramach swoich aktywnych strategii, to średnia wypłata pozostanie niezmieniona i będzie równa kosztowi gry w niezależnie od tego, w jaki sposób gracz „B” wykorzystuje swoje aktywne strategie. I w naszym przypadku obie strategie są aktywne, w przeciwnym razie gra miałaby rozwiązanie w czystych strategiach. Zatem jeśli założymy, że gracz „B” zastosuje czystą strategię B 1, to średnia wypłata w będzie:

k 11 p 1 + k 21 p 2 = v (1)

Gdzie: k ij - elementy macierzy płatności.

Z drugiej strony, jeśli założymy, że gracz „B” zastosuje czystą strategię B 2, to średnia wypłata będzie wynosić:

k 12 p 1 + k 22 p 2 = v (2)

Zrównując lewe strony równań (1) i (2) otrzymujemy:

k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2

I biorąc pod uwagę fakt, że P 1 + P 2 = 1 mamy:

k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )

W tym zadaniu:

Z teorii gier wiadomo, że jeśli gracz „B” zastosuje swoją optymalną strategię, a gracz „A” pozostanie w ramach swoich aktywnych strategii, to średnia wypłata pozostanie niezmieniona i będzie równa kosztowi gry w niezależnie od tego, w jaki sposób gracz A wykorzystuje swoje aktywne strategie. Zatem jeśli założymy, że gracz „A” zastosuje czystą strategię A 1, to średnia wypłata w będzie:

k 11 q 1 + k 12 q 2 = v (4)

W tym zadaniu:

Odpowiedź:

Interpretacja geometryczna (rozwiązanie graficzne):

Obrazek 1.
Wykres wypłat k od częstotliwości str. 2 , gdy wróg korzysta ze strategii B 1.

Załóżmy teraz, że gracz „B” zastosuje strategię B 2 w jej czystej postaci. Następnie, jeśli my (gracz „A”) zastosujemy czystą strategię A 1, wówczas nasza wypłata wyniesie 5. Jeśli zastosujemy czystą strategię A 2, wówczas nasza wypłata wyniesie 3/2 (patrz rys. 2). Podobnie, jeśli zmieszamy strategie A 1 i A 2 w różnych proporcjach, nasze wygrane będą się zmieniać wzdłuż linii prostej przechodzącej przez punkty o współrzędnych (0, 5) i (1, 3/2), nazwijmy to linią strategii B 2. Podobnie jak w poprzednim przypadku, odcięta dowolnego punktu na tej prostej jest równa prawdopodobieństwu, z jakim zastosujemy strategię A 2, a rzędną jest wynikowy zysk, ale tylko dla strategii B 2 (patrz ryc. 2).

Rysunek 2.
w i optymalna częstotliwość str. 2 dla gracza "A".

W prawdziwej grze, gdy rozsądny gracz „B” wykorzysta wszystkie swoje strategie, nasza wygrana będzie się zmieniać wzdłuż przerywanej linii pokazanej na ryc. 2 na czerwono. Linia ta definiuje tzw dolny limit wygranych. Oczywiście najwyższy punkt tej linii przerywanej odpowiada naszej optymalnej strategii. W tym przypadku jest to punkt przecięcia linii strategii B 1 i B 2. Należy pamiętać, że jeśli wybierzesz częstotliwość P 2 równy jej odciętej, wówczas nasz zysk pozostanie niezmieniony i równy w dla dowolnej strategii gracza „B”, dodatkowo będzie to maksimum, jakie możemy sobie zagwarantować. Częstotliwość (prawdopodobieństwo) P 2 w tym przypadku jest odpowiednią częstotliwością naszej optymalnej strategii mieszanej. Nawiasem mówiąc, na rysunku 2 widać częstotliwość P 1 , naszą optymalną strategią mieszaną, jest długość segmentu [ P 2 ; 1] na osi x. (To dlatego, że P 1 + P 2 = 1 )

Stosując zupełnie podobne rozumowanie, możemy znaleźć częstości występowania optymalnej strategii dla gracza „B”, co ilustruje rysunek 3.

Rysunek 3.
Graficzne określenie ceny gry w i optymalna częstotliwość q 2 dla gracza "W".

Tylko dla niego powinien być tzw górna granica straty(czerwona linia przerywana) i poszukaj na niej najniższego punktu, ponieważ dla gracza „B” celem jest minimalizacja strat. Ta sama wartość częstotliwości Q 1 , jest to długość odcinka [ Q 2 ; 1] na osi x.

Sekcja „Teoria gier” jest reprezentowana przez trzy kalkulatory internetowe:

1. Optymalne strategie graczy. W takich problemach określona jest matryca płatności. Wymagane jest znalezienie czystych lub mieszanych strategii graczy i, cena gry. Aby rozwiązać, należy określić wymiar macierzy i metodę rozwiązania. Usługa implementuje następujące metody rozwiązywania gry dwuosobowej:
   1. Minimaks. Jeśli chcesz znaleźć czystą strategię graczy lub odpowiedzieć na pytanie dotyczące punktu siodłowego gry, wybierz tę metodę rozwiązania.
   2. Metoda Simplex. Służy do rozwiązywania mieszanych gier strategicznych z wykorzystaniem metod programowania liniowego.
   3. Metoda graficzna. Służy do rozwiązywania mieszanych gier strategicznych. Jeśli istnieje punkt siodłowy, rozwiązanie zostaje zatrzymane. Przykład: Mając macierz wypłat, znajdź optymalne strategie mieszane graczy i cenę gry, korzystając z graficznej metody rozwiązywania gry.
   4. Metoda iteracyjna Browna-Robinsona. Metodę iteracyjną stosuje się wtedy, gdy nie ma zastosowania metoda graficzna oraz gdy metody algebraiczne i macierzowe praktycznie nie mają zastosowania. Metoda ta daje przybliżoną wartość ceny gry, a rzeczywistą wartość można uzyskać z dowolną dokładnością. Ta metoda nie jest wystarczająca do znalezienia optymalnych strategii, ale pozwala prześledzić dynamikę gry turowej i określić koszt gry dla każdego gracza na każdym kroku.
   Na przykład zadanie może brzmieć jak „wskazać optymalne strategie graczy dla gry podane przez macierz wypłat”.
   Wszystkie metody korzystają ze sprawdzania dominujących wierszy i kolumn.
2. Gra Bimatrix. Zwykle w takiej grze określone są dwie macierze o tej samej wielkości wypłat pierwszego i drugiego gracza. Rzędy tych macierzy odpowiadają strategiom pierwszego gracza, a kolumny macierzy odpowiadają strategiom drugiego gracza. W tym przypadku pierwsza macierz przedstawia wygrane pierwszego gracza, a druga macierz przedstawia wygrane drugiego.
3. Gry z naturą. Stosuje się go, gdy konieczne jest podjęcie decyzji zarządczej według kryteriów Maximax, Bayes, Laplace, Wald, Savage, Hurwitz.
   Dla kryterium Bayesa konieczne będzie także wprowadzenie prawdopodobieństw wystąpienia zdarzeń. Jeśli nie są określone, pozostaw wartości domyślne (będą zdarzenia równoważne).
   Dla kryterium Hurwitza wskaż poziom optymizmu λ. Jeśli ten parametr nie jest określony w warunkach, możesz użyć wartości 0, 0,5 i 1.

Wiele problemów wymaga znalezienia rozwiązań przy użyciu komputerów. Powyższe usługi i funkcje są jednym z narzędzi.

Teoria gry - zestaw matematycznych metod rozwiązywania sytuacji konfliktowych (konfliktów interesów). W teorii gier gra nazywa się grą model matematyczny sytuacji konfliktowej. Przedmiotem szczególnego zainteresowania teorii gier jest badanie strategii podejmowania decyzji przez uczestników gier w warunkach niepewności. Niepewność wynika z faktu, że dwie lub więcej stron dąży do przeciwstawnych celów, a wynik każdego działania każdej ze stron zależy od posunięć partnera. Jednocześnie każda ze stron dąży do podejmowania optymalnych decyzji, które w jak największym stopniu realizują założone cele.

Teorię gier najkonsekwentniej stosuje się w ekonomii, gdzie powstają sytuacje konfliktowe np. w relacji dostawca – konsument, kupujący – sprzedawca, bank – klient. Zastosowanie teorii gier można znaleźć także w polityce, socjologii, biologii i sztuce militarnej.

Z historii teorii gier

Historia teorii gier jako niezależna dyscyplina rozpoczęła się w 1944 roku, kiedy John von Neumann i Oscar Morgenstern opublikowali książkę „Teoria gier i zachowań ekonomicznych”. Choć z przykładami teorii gier spotykaliśmy się już wcześniej: traktat Talmudu babilońskiego o podziale majątku zmarłego męża pomiędzy jego żony, gry karciane w XVIII w., rozwój teorii szachów na początku XX w. stulecia, dowód twierdzenia o minimaksie tego samego Johna von Neumanna w 1928 roku, bez którego nie byłoby teorii gier.

W latach 50. XX wieku Melvin Drescher i Meryl Flood z Firma Rand John Nash, pierwszy, który eksperymentalnie zastosował dylemat więźnia, rozwinął koncepcję równowagi Nasha w swoich pracach poświęconych stanowi równowagi w grach dwuosobowych.

Reinhard Salten opublikował w 1965 roku książkę „The Treatment of Oligopoly in Game Theory on Demand” („Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit”), dzięki której zastosowanie teorii gier w ekonomii zyskało nową siłę napędową. Krok naprzód w ewolucji teorii gier wiąże się z pracą Johna Maynarda Smitha „Evolutionary Stable Strategy” (1974). Dylemat więźnia został spopularyzowany w książce Roberta Axelroda z 1984 roku The Evolution of Cooperative. W 1994 roku John Nash, John Harsanyi i Reinhard Selten otrzymali Nagrodę Nobla za wkład w teorię gier.

Teoria gier w życiu i biznesie

Zatrzymajmy się bardziej szczegółowo nad istotą sytuacji konfliktowej (konfliktu interesów) w takim sensie, w jakim jest ona rozumiana w teorii gier dla dalszego modelowania różnych sytuacji życiowych i biznesowych. Niech dana osoba znajdzie się w sytuacji, która prowadzi do jednego z kilku możliwych wyników i ma pewne osobiste preferencje dotyczące tych wyników. Choć może w pewnym stopniu kontrolować zmienne determinujące wynik, nie ma nad nimi całkowitej władzy. Czasami kontrola jest w rękach kilku osób, które podobnie jak on mają pewne preferencje co do możliwych wyników, ale generalnie interesy tych osób nie są spójne. W innych przypadkach ostateczny wynik może zależeć zarówno od przypadku (czasami nazywanego w naukach prawnych klęską żywiołową), jak i od innych osób. Teoria gier systematyzuje obserwacje takich sytuacji i formułuje ogólne zasady kierujące inteligentnymi działaniami w takich sytuacjach.

Pod pewnymi względami nazwa „teoria gier” jest niefortunna, ponieważ sugeruje, że teoria gier zajmuje się jedynie społecznie nieistotnymi spotkaniami, które mają miejsce w grach towarzyskich, mimo to teoria ta ma znacznie szersze znaczenie.

Następująca sytuacja ekonomiczna może dać wyobrażenie o zastosowaniu teorii gier. Załóżmy, że jest kilku przedsiębiorców, z których każdy dąży do uzyskania maksymalnego zysku, mając jednocześnie ograniczoną władzę nad zmiennymi determinującymi ten zysk. Przedsiębiorca nie ma wpływu na zmienne, które kontroluje inny przedsiębiorca, ale które mogą znacząco wpłynąć na dochody pierwszego. Traktowanie tej sytuacji jako gry może budzić następujący zarzut. W modelu gry zakłada się, że każdy przedsiębiorca dokonuje jednego wyboru z szeregu możliwych wyborów i te pojedyncze wybory determinują zyski. Oczywiście w rzeczywistości prawie nie może się to zdarzyć, ponieważ w tym przypadku w przemyśle nie byłyby potrzebne skomplikowane aparaty zarządzające. Istnieje po prostu szereg decyzji i modyfikacji tych decyzji, które zależą od wyborów dokonywanych przez innych uczestników systemu gospodarczego (graczy). Jednak w zasadzie można sobie wyobrazić administratora, który przewiduje wszystkie możliwe zdarzenia i szczegółowo opisuje działania, jakie należy podjąć w każdym przypadku, zamiast rozwiązywać każdy problem w miarę jego pojawiania się.

Konflikt militarny z definicji to zderzenie interesów, w którym żadna ze stron nie ma całkowitej kontroli nad zmiennymi determinującymi wynik, o którym decyduje seria bitew. Możesz po prostu uznać wynik za wygraną lub porażkę i przypisać im wartości liczbowe 1 i 0.

Jedną z najprostszych sytuacji konfliktowych, które można zapisać i rozwiązać w teorii gier, jest pojedynek, będący konfliktem pomiędzy dwoma graczami 1 i 2, posiadającymi odpowiednio P I Q strzały. Dla każdego zawodnika dostępna jest funkcja wskazująca prawdopodobieństwo oddania strzału przez zawodnika I w pewnym momencie T zada cios, który będzie śmiertelny.

W rezultacie teoria gier dochodzi do następującego sformułowania pewnej klasy konfliktów interesów: istnieją N graczy i każdy musi wybrać jedną opcję ze stu konkretnych zestawów, a dokonując wyboru, gracz nie ma informacji o wyborach innych graczy. Obszar możliwego wyboru gracza może zawierać takie elementy, jak „gra asem pik”, „produkcja czołgów zamiast samochodów” lub bardziej ogólnie, strategia określająca wszystkie działania, jakie należy podjąć w każdych możliwych okolicznościach. Każdy gracz staje przed zadaniem: jakiego dokonać wyboru, aby jego prywatny wpływ na wynik przyniósł mu jak największe zwycięstwo?

Model matematyczny w teorii gier i formalizacja problemów

Jak już zauważyliśmy, gra jest matematycznym modelem sytuacji konfliktowej i wymaga następujących komponentów:

1. zainteresowane strony;
2. możliwe działania z każdej strony;
3. interesy stron.

Strony zainteresowane grą nazywane są graczami , każdy z nich może wykonać co najmniej dwie akcje (jeśli gracz ma do dyspozycji tylko jedną akcję, to tak naprawdę nie uczestniczy w grze, gdyż z góry wiadomo, co wykona). Wynik gry nazywany jest wygraną .

Nie zawsze ma miejsce prawdziwa sytuacja konfliktowa, ale gra (w ujęciu teorii gier) zawsze toczy się zgodnie z nią pewne zasady , które dokładnie określają:

1. opcje działań graczy;
2. ilość informacji, jakie każdy gracz posiada na temat zachowania swojego partnera;
3. wypłata, do której prowadzi każdy zestaw działań.

Przykładami sformalizowanych gier są piłka nożna, gry karciane i szachy.

Ale w ekonomii powstaje model zachowań graczy, np. gdy kilka firm stara się zająć bardziej korzystne miejsce na rynku, kilka osób próbuje podzielić między siebie jakieś dobro (zasoby, finanse) tak, aby każdy dostał jak najwięcej . Graczami w sytuacjach konfliktowych w gospodarce, które można modelować w formie gry, są firmy, banki, osoby fizyczne i inne podmioty gospodarcze. Z kolei w warunkach wojennych model gry wykorzystywany jest np. przy wyborze najlepszej broni (z istniejącej lub potencjalnej) do pokonania wroga lub zabezpieczenia się przed atakiem.

Grę cechuje niepewność wyniku . Przyczyny niepewności można podzielić na następujące grupy:

1. kombinatoryczny (jak w szachach);
2. wpływ czynników losowych (jak w grze „orła lub reszka”, w kości, w grach karcianych);
3. strategiczne (gracz nie wie, jaką akcję podejmie wróg).

Strategia gracza to zbiór zasad, które określają jego działania przy każdym ruchu w zależności od aktualnej sytuacji.

Cel teorii gier jest określenie optymalnej strategii dla każdego gracza. Ustalenie takiej strategii oznacza rozwiązanie gry. Optymalność strategii osiąga się wtedy, gdy jeden z graczy powinien uzyskać maksymalną wygraną, a drugi trzymać się swojej strategii. Drugi gracz powinien ponieść minimalną stratę, jeśli pierwszy będzie trzymał się swojej strategii.

Klasyfikacja gier

1. Klasyfikacja według liczby graczy (gra dla dwóch lub więcej osób). Gry dwuosobowe zajmują centralne miejsce w całej teorii gier. Podstawową koncepcją teorii gier dla gier dwuosobowych jest uogólnienie bardzo istotnej idei równowagi, która naturalnie pojawia się w grach dwuosobowych. Jeśli chodzi o gry N jednostek, wówczas jedna część teorii gier poświęcona jest grom, w których zabroniona jest współpraca między graczami. W innej części teorii gier N jednostki zakładają, że gracze mogą współpracować dla obopólnych korzyści (patrz dalej w tym akapicie na temat gier niekooperacyjnych i kooperacyjnych).
2. Klasyfikacja według liczby graczy i ich strategii (liczba strategii wynosi co najmniej dwie, może być nieskończona).
3. Klasyfikacja według ilości informacji w odniesieniu do przeszłych ruchów: gry z pełną informacją i niekompletną informacją. Niech będzie gracz 1 – kupujący i gracz 2 – sprzedający. Jeśli gracz 1 nie ma pełnych informacji o działaniach gracza 2, wówczas gracz 1 nie może dokonać rozróżnienia pomiędzy dwiema alternatywami, pomiędzy którymi musi dokonać wyboru. Na przykład wybór pomiędzy dwoma rodzajami jakiegoś produktu i niewiedza, że ​​zgodnie z pewnymi cechami będzie to produkt A gorszy produkt B, gracz 1 może nie widzieć różnicy pomiędzy alternatywami.
4. Klasyfikacja według zasad podziału wygranych : spółdzielczy, koalicja z jednej strony i niekooperacyjny, niekoalicja z drugiej strony. W gra niekooperacyjna , lub w przeciwnym wypadku - gra niekooperacyjna , gracze wybierają strategie jednocześnie, nie wiedząc, którą strategię wybierze drugi gracz. Komunikacja pomiędzy graczami jest niemożliwa. W gra kooperacyjna , lub w przeciwnym wypadku - gra koalicyjna , gracze mogą tworzyć koalicje i podejmować zbiorowe działania w celu zwiększenia swoich wygranych.
5. Skończona dwuosobowa gra o sumie zerowej lub gra antagonistyczna to gra strategiczna z pełną informacją, w której biorą udział strony o przeciwstawnych interesach. Gry antagonistyczne są gry matrixowe.

Klasycznym przykładem z teorii gier jest dylemat więźnia.

Obaj podejrzani zostają zatrzymani i rozdzieleni od siebie. Prokurator okręgowy jest przekonany, że dopuścili się oni poważnego przestępstwa, jednak nie ma wystarczających dowodów, aby postawić im zarzuty na rozprawie. Mówi każdemu więźniowi, że ma dwie możliwości: przyznać się do przestępstwa, które zdaniem policji popełnił, lub nie przyznać się do winy. Jeśli obaj się nie przyznają, prokurator oskarży ich o drobne przestępstwo, takie jak drobna kradzież lub nielegalne posiadanie broni, i obaj otrzymają niewielki wyrok. Jeśli obaj przyznają się do winy, staną przed sądem, ale on nie będzie domagał się najsurowszego wyroku. Jeśli jeden się przyzna, a drugi nie, wówczas temu, który się przyznał, złagodzi się wyrok za ekstradycję wspólnika, a temu, który będzie się upierał, otrzyma „w pełni”.

Jeśli sformułować to strategiczne zadanie w kategoriach konkluzji, to sprowadza się ono do następujących kwestii:

Zatem jeśli obaj więźniowie nie przyznają się do winy, każdy z nich otrzyma po roku więzienia. Jeśli obaj się przyznają, każdy dostanie 8 lat. A jeśli jeden się przyzna, drugi się nie przyzna, to temu, który się przyznał, grozi 3 miesiące więzienia, a temu, który się nie przyznaje, 10 lat. Powyższa matryca trafnie odzwierciedla dylemat więźnia: każdy staje przed pytaniem, czy się przyznać, czy nie. Gra, którą prokurator okręgowy oferuje więźniom, to gra niekooperacyjna lub w przeciwnym wypadku - gra niekooperacyjna . Jeżeli obaj więźniowie mieliby możliwość współpracy (tj. gra miałaby charakter kooperacyjny albo gra koalicyjna ), wówczas obaj nie przyznaliby się do winy i każdy otrzymałby rok więzienia.

Przykłady wykorzystania narzędzi matematycznych teorii gier

Przejdźmy teraz do rozważenia rozwiązań przykładów typowych klas gier, dla których istnieją metody badań i rozwiązań w teorii gier.

Przykład sformalizowania niekooperacyjnej (niekooperacyjnej) gry dwóch osób

W poprzednim akapicie przyjrzeliśmy się już przykładowi gry niekooperacyjnej (niekooperacyjnej) (dylemat więźnia). Wzmacniajmy nasze umiejętności. Nadaje się do tego również klasyczna fabuła inspirowana „Przygodami Sherlocka Holmesa” Arthura Conana Doyle’a. Można oczywiście sprzeciwić się: przykład nie pochodzi z życia, ale z literatury, ale Conan Doyle nie dał się poznać jako pisarz science fiction! Klasyczne także dlatego, że zadania tego dokonał Oskar Morgenstern, jak już ustaliliśmy, jeden z twórców teorii gier.

Przykład 1. Podane zostanie skrócone streszczenie fragmentu jednego z „Przygód Sherlocka Holmesa”. Zgodnie ze znanymi koncepcjami teorii gier stwórz model sytuacji konfliktowej i formalnie zapisz przebieg gry.

Sherlock Holmes zamierza udać się z Londynu do Dover, a dalszym celem jest przedostanie się na kontynent (europejski), aby uciec przed ścigającym go profesorem Moriartym. Wsiadłszy do pociągu, na peronie zobaczył profesora Moriarty'ego. Sherlock Holmes przyznaje, że Moriarty może wybrać specjalny pociąg i go wyprzedzić. Sherlock Holmes ma dwie możliwości: kontynuować podróż do Dover lub wysiąść na stacji Canterbury, która jest jedyną stacją pośrednią na jego trasie. Akceptujemy fakt, że jego przeciwnik jest wystarczająco inteligentny, aby określić możliwości Holmesa, ma więc te same dwie możliwości. Obaj przeciwnicy muszą wybrać stację, na której wysiądą z pociągu, nie wiedząc, jaką decyzję każdy z nich podejmie. Jeśli w wyniku podjęcia decyzji obaj znajdą się na tym samym stanowisku, to z pewnością możemy założyć, że Sherlock Holmes zostanie zabity przez profesora Moriarty'ego. Jeśli Sherlock Holmes bezpiecznie dotrze do Dover, zostanie uratowany.

Rozwiązanie. Bohaterów Conana Doyle’a możemy uznać za uczestników gry, czyli graczy. Dostępne dla każdego gracza I (I=1,2) dwie czyste strategie:

• wysiąść w Dover (strategia Si1 ( I=1,2) );
• wysiąść na stacji pośredniej (strategia Si2 ( I=1,2) )

W zależności od tego, którą z dwóch strategii wybierze każdy z dwóch graczy, zostanie utworzona specjalna kombinacja strategii jako para S = (S1 , S 2 ) .

Każdą kombinację można powiązać z jakimś wydarzeniem - skutkiem próby morderstwa Sherlocka Holmesa dokonanej przez profesora Moriarty'ego. Tworzymy matrycę tej gry z możliwymi zdarzeniami.

Pod każdym z wydarzeń znajduje się indeks wskazujący na przejęcie profesora Moriarty'ego i wyliczany w zależności od ocalenia Holmesa. Obaj bohaterowie jednocześnie wybierają strategię, nie wiedząc, co wybierze wróg. Gra nie ma zatem charakteru kooperacyjnego, ponieważ po pierwsze gracze jadą różnymi pociągami, a po drugie mają przeciwstawne interesy.

Przykład formalizacji i rozwiązania gry kooperacyjnej (koalicyjnej). N osoby

W tym miejscu część praktyczną, czyli proces rozwiązywania przykładowego problemu, poprzedzi część teoretyczna, w której zapoznamy się z koncepcjami teorii gier służącymi do rozwiązywania gier kooperacyjnych (niekooperacyjnych). W przypadku tego zadania teoria gier sugeruje:

• funkcja charakterystyczna (w uproszczeniu odzwierciedla wielkość korzyści płynących z połączenia graczy w koalicję);
• pojęcie addytywności (właściwość wielkości polegająca na tym, że wartość wielkości odpowiadającej całemu obiektowi jest równa sumie wartości wielkości odpowiadających jego częściom w pewnej klasie przegród obiektu na części) i superaddytywność (wartość wielkości odpowiadającej całemu obiektowi jest większa niż suma wartości wielkości odpowiadających jego częściom) funkcji charakterystycznej.

Superaddytywność funkcji charakterystycznej sugeruje, że przyłączenie się do koalicji jest korzystne dla graczy, gdyż w tym przypadku wartość wypłaty koalicji rośnie wraz z liczbą graczy.

Aby sformalizować grę, należy wprowadzić notacje formalne dla powyższych pojęć.

Do gry N oznaczmy zbiór wszystkich jego graczy jako N= (1,2,...,n) Dowolny niepusty podzbiór zbioru N oznaczmy to jako T(w tym siebie N i wszystkie podzbiory składające się z jednego elementu). Na stronie znajduje się lekcja ” Zbiory i operacje na zbiorach", który otwiera się w nowym oknie po kliknięciu linku.

Funkcja charakterystyczna jest oznaczona jako w a jego dziedzina definicji składa się z możliwych podzbiorów zbioru N. w(T) - wartość funkcji charakterystycznej dla danego podzbioru, np. dochód uzyskiwany przez koalicję, ewentualnie obejmującą koalicję złożoną z jednego gracza. Jest to o tyle ważne, że teoria gier wymaga sprawdzenia obecności superaddytywności dla wartości funkcji charakterystycznej wszystkich koalicji rozłącznych.

Dla dwóch niepustych koalicji podzbiorów T1 I T2 Addytywność charakterystycznej funkcji gry kooperacyjnej (koalicyjnej) zapisuje się następująco:

A superaddytywność wygląda następująco:

Przykład 2. Trzej uczniowie szkoły muzycznej pracują na pół etatu w różnych klubach, a dochody czerpią od gości klubowych. Ustal, czy opłaca się im łączyć siły (jeśli tak, to na jakich warunkach), wykorzystując koncepcje teorii gier do rozwiązywania gier kooperacyjnych N osób, z następującymi danymi początkowymi.

Średni przychód na wieczór wynosił:

• skrzypek ma 600 jednostek;
• gitarzysta ma 700 jednostek;
• piosenkarka ma 900 jednostek.

Próbując zwiększyć przychody, studenci w ciągu kilku miesięcy utworzyli różne grupy. Wyniki pokazały, że łącząc siły, mogliby zwiększyć swoje wieczorne przychody poprzez:

• skrzypek + gitarzysta zarobił 1500 jednostek;
• skrzypek + śpiewak zarobił 1800 jednostek;
• gitarzysta + piosenkarz zarobił 1900 jednostek;
• skrzypek + gitarzysta + piosenkarz zarobili 3000 jednostek.

Rozwiązanie. W tym przykładzie liczba graczy w grze N= 3, zatem dziedzina definicji funkcji charakterystycznej gry składa się z 2³ = 8 możliwych podzbiorów zbioru wszystkich graczy. Wypiszmy wszystkie możliwe koalicje T:

• koalicje jednego elementu, z których każda składa się z jednego gracza – muzyka: T{1} , T{2} , T{3} ;
• koalicja dwóch elementów: T{1,2} , T{1,3} , T{2,3} ;
• koalicja trzech elementów: T{1,2,3} .

Każdemu graczowi przypiszemy numer seryjny:

• skrzypek - 1. gracz;
• gitarzysta - drugi gracz;
• piosenkarz - trzeci gracz.

Na podstawie danych problemowych wyznaczamy charakterystyczną funkcję gry w:

v(T(1)) = 600 ; v(T(2)) = 700 ; v(T(3)) = 900 ; te wartości funkcji charakterystycznej ustalane są na podstawie wypłat odpowiednio pierwszego, drugiego i trzeciego gracza, gdy nie zjednoczą się oni w koalicję;

v(T(1,2)) = 1500 ; v(T(1,3)) = 1800 ; v(T(2,3)) = 1900 ; te wartości funkcji charakterystycznej są określone przez dochód każdej pary graczy zjednoczonych w koalicji;

v(T(1,2,3)) = 3000 ; tę wartość funkcji charakterystycznej wyznacza średni dochód w przypadku, gdy gracze łączą się trójkami.

Wyszczególniliśmy zatem wszystkie możliwe koalicje graczy, jest ich, jak powinno być, gdyż dziedzina określenia funkcji charakterystycznej gry składa się z dokładnie ośmiu możliwych podzbiorów zbioru wszystkich graczy. Tego wymaga teoria gier, ponieważ musimy sprawdzić obecność superaddytywności dla wartości funkcji charakterystycznej wszystkich rozłącznych koalicji.

W jaki sposób warunki superaddytywności są spełnione w tym przykładzie? Ustalmy, w jaki sposób gracze tworzą rozłączne koalicje T1 I T2 . Jeśli niektórzy gracze są częścią koalicji T1 , wówczas wszyscy pozostali gracze wchodzą w skład koalicji T2 i z definicji koalicja ta powstaje jako różnica całego zestawu graczy i zestawu T1 . A następnie, jeśli T1 - koalicja jednego gracza, potem w koalicji T2 jeśli będą w koalicji, będzie drugi i trzeci gracz T1 będzie pierwszy i trzeci gracz, potem koalicja T2 będzie składać się tylko z drugiego gracza i tak dalej.

Spis treści 1 Informacje ogólne 2 1.1 Gry. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Ruchy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Strategie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Gra Matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Punkt szlaku. Strategie czyste 7 2.1 Przykłady. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Przykład 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Przykład 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Strategie mieszane 9 3.1 Gra 2×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Przykłady. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Przykład 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Przykład 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Interpretacja geometryczna. . . . . . . . . . . . . . . . . . . . 12 3.2 Gry 2×n i m×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Przykład 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Informacje ogólne z teorii gier 1.1. Gry Teoria gier to matematyczna teoria sytuacji konfliktowych, tj. sytuacje, w których kolidują interesy dwóch lub więcej stron realizujących różne cele. Gra to sytuacja konfliktowa regulowana pewnymi regułami, które muszą wskazywać: możliwe opcje działania uczestników; ilościowy wynik gry lub płatności (wygrana, przegrana), do której prowadzi dany zestaw ruchów; ilość informacji każdej strony na temat zachowania drugiej. Gra podwójna to gra, w której biorą udział tylko dwie strony (dwóch graczy). Gra parami o sumie zerowej to gra parami, w której suma wpłat wynosi zero, tj. Strata jednego gracza równa się zyskowi drugiego. W zależności od stosunku każdego gracza do wartości funkcji wypłaty, gry parowe dzielą się na: Gra parowa o sumie zerowej (antagonistyczna) - gra parowa, w której wysokość wpłat jest równa zeru, tj. Strata jednego gracza równa się zyskowi drugiego. Gra nieantagonistyczna to gra w parach, w której gracze dążą do różnych, ale nie bezpośrednio przeciwnych celów. 2 1.2. Ruchy Ruch - wybór jednej z akcji przewidzianych przez reguły gry, realizacja tego wyboru. Ruchy dzielą się na dwa rodzaje: Ruch osobisty - + świadomy wybór jednej z akcji przewidzianych przez zasady gry + realizacja tego wyboru Losowy ruch - Losowy ruch to wybór spośród szeregu możliwości, dokonywany nie na podstawie decyzji gracza, ale przez jakiś mechanizm losowego wyboru. Poniżej rozważamy gry w parach o sumie zerowej, zawierające wyłącznie ruchy osobiste. Każdej ze stron brakuje informacji o zachowaniu drugiej. 3 1.3. Strategie Strategia gracza to zbiór zasad, które określają wybór akcji dla każdego osobistego ruchu tego gracza, w zależności od sytuacji, która pojawi się w trakcie gry. W zależności od liczby możliwych strategii gry dzielą się na skończone i nieskończone. Gra nieskończona to gra, w której co najmniej jeden z graczy ma nieskończoną liczbę strategii. Gra skończona to gra, w której każdy gracz ma tylko skończoną liczbę strategii. Liczba kolejnych ruchów dowolnego gracza określa podział partii na jednoruchowe i wieloruchowe, czyli pozycyjne. + W grze składającej się z jednej tury każdy gracz dokonuje tylko jednego wyboru spośród możliwych opcji, a następnie ustala wynik gry. + Gra wieloruchowa, czyli pozycyjna, rozwija się z biegiem czasu, reprezentując serię kolejnych etapów, z których każdy następuje po ruchu jednego z graczy i odpowiadającej mu zmianie sytuacji. W grze składającej się z jednej tury każdy gracz dokonuje tylko jednego wyboru spośród możliwych opcji, a następnie ustala wynik gry. Optymalna strategia gracza to strategia, która przy wielokrotnym powtarzaniu gry zapewnia temu graczowi maksymalną możliwą średnią wygraną (lub co za tym idzie minimalną możliwą średnią stratę). W teorii gier wszystkie rekomendacje opierają się na założeniu rozsądnego zachowania graczy. Błędne obliczenia i błędy graczy, nieuniknione w każdej sytuacji konfliktowej, a także elementy emocji i ryzyka, nie są brane pod uwagę w teorii gier. 4 1.4. Gra macierzowa Gra macierzowa to gra jednoruchowa o skończonej sumie zerowej Gra macierzowa to teoretyczny model sytuacji konfliktowej, w której przeciwnicy, aby osiągnąć diametralnie przeciwne cele, dokonują jednego wyboru (ruchu) ze skończonej liczba możliwych kierunków działania.Według wybranych metod działania (strategii) określany jest osiągnięty wynik. Spójrzmy na przykład. Niech będzie dwóch graczy A i B, z których jeden może wybrać i-tą strategię spośród m swoich możliwych strategii A1, A2, ...Am, a drugi wybiera j-tą strategię spośród swoich możliwych strategii B1, B2 ,..Bm. W rezultacie pierwszy gracz zdobywa wartość aij, a drugi gracz traci tę wartość. Z liczb aij tworzymy macierz   a11 a11 · · · a1n  a21 a22 · · · a2n    A = (aij) =  .. .. ..   . . . .  am1 am2 · · · amn Macierz A = (aij), i = 1, m, j = 1, n nazywana jest macierzą wypłat lub macierzą gry m × n. W tej macierzy wiersze dotyczą zawsze strategii zwycięskiego (maksymalizującego) gracza A, czyli gracza, który dąży do maksymalizacji swoich wygranych. Kolumny przypisane są do strategii przegrywającego gracza B, czyli gracza, który dąży do minimalizacji kryterium efektywności. Normalizacja gry to proces sprowadzania gry pozycyjnej do gry macierzowej. Gra w postaci normalnej jest grą pozycyjną zredukowaną do gry macierzowej. Przypomnijmy, że pozycyjna gra wieloruchowa jest teoretycznym modelem gry sytuacja konfliktowa, w której przeciwnicy po kolei dokonują jednego wyboru (ruchu) ze skończonej liczby możliwych kierunków działania na każdym etapie rozwoju tej sytuacji. Rozwiązaniem gry jest znalezienie optymalnej strategii obu graczy i ustalenie ceny gry.Ceną gry jest oczekiwany zysk (strata) graczy. Rozwiązanie tej gry można znaleźć albo w strategiach czystych – gdy gracz musi zastosować jedną, pojedynczą strategię, albo w strategiach mieszanych, gdy gracz musi zastosować dwie lub więcej czystych strategii z określonym prawdopodobieństwem. Te ostatnie w tym przypadku nazywane są aktywnymi. 5 Strategia mieszana jednego gracza to wektor, którego każdy składnik pokazuje częstotliwość stosowania przez gracza odpowiedniej strategii czystej. Maximin lub niższa cena gry - liczba α = max min aij i j Strategia Maximin (linia) - strategia, którą wybrał gracz, aby zmaksymalizować swoje minimalne wygrane. Oczywiście, wybierając najbardziej ostrożną strategię maximin, gracz A zapewnia sobie (niezależnie od zachowania przeciwnika) gwarantowaną wypłatę co najmniej α. Maximin czyli górna cena gry - liczba β = min max aij j i Strategia Minimax (kolumna) - strategia, którą wybrał gracz, aby zminimalizować swoją maksymalną stratę. Oczywiście, wybierając najbardziej ostrożną strategię minimax, gracz B w żadnym wypadku nie pozwala graczowi A wygrać więcej niż β. Niższa cena gry nie zawsze przekracza górną cenę gry α = max min aij 6 min max aij = β i j j i Twierdzenie 1 (główne twierdzenie teorii gier macierzowych). Każda skończona gra ma co najmniej jedno rozwiązanie, prawdopodobnie w dziedzinie strategii mieszanych. 6 2. Gry z punktem siodłowym. Rozwiązanie w strategiach czystych Gra z punktem siodłowym to gra, dla której α = max min aij = min max aij = β i j j i W przypadku gier z punktem siodłowym znalezienie rozwiązania polega na wyborze optymalnych strategii maximin i minimax. , Cena netto gry - suma wartości dolnej i górnej ceny gry α=β=ν 2.1. Przykłady Przykład 1 Znajdź rozwiązanie w czystych strategiach gry podanych przez macierz   8 4 7 A= 6 5 9  7 7 8 Rozwiązanie: określ górną i dolną cenę gry. W tym celu znajdziemy minimum liczb aij w i-tym wierszu αi = min aij j oraz maksimum liczb aij w j-tej kolumnie βj = max aij i Zapiszemy liczby αi (wiersz minima) obok matrycy płatności po prawej stronie w formie dodatkowej kolumny. Liczby βi (maksyma kolumny) zapisujemy pod macierzą w postaci dodatkowej linii: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Znajdź maksimum liczb αi α = max αi = 7 i oraz minimum liczb βj β = min βj = 7 j α = β – gra ma punkt siodłowy. Optymalną strategią dla gracza jest strategia A3, a dla gracza B strategia B2, cena gry netto ν = 7 Przykład 2 Dana jest macierz płatności:   2 2 1 1 2  0 1 1 1 1  A=  1 1 1 1 2   1 2 1 1 2 Znajdź rozwiązanie gry w czystych strategiach. Rozwiązanie: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Gra ma sześć punktów siodłowych. Optymalnymi strategiami będą: A1 i B3 lub B4 A3 i B3 lub B4 A4 i B3 lub B4 8 3. Rozwiązanie gry w strategiach mieszanych Gdy α = β. W przypadku, gdy przy wyborze swoich strategii obaj gracze nie mają informacji o wyborze drugiej, gra ma rozwiązanie w strategiach mieszanych. SA = (p1, p2, ..., pm) - strategia mieszana gracza A, w której stosowane są strategie A1, A2, ..., Am z prawdopodobieństwami ∑ m p1, p2, ..., pm, pi = 1, pi > 0, i = 1, m i=1 SB = (q1, q2, ..., qn) - strategia mieszana gracza B, w której stosowane są strategie B1, B2, ..., Bm z prawdopodobieństwem ∑ n q1, q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 Jeśli: SA∗ jest optymalną strategią gracza A, SB∗ jest optymalną strategią gracza B, to koszt gry wynosi ∑ n ∑ m ν = aij · p∗i · qi∗ j=1 i=1 Poniższe twierdzenie odpowiada na pytanie, jak znaleźć rozwiązanie dla gier 2 × 2, 2 × n, m × 2 Twierdzenie 2 (jak znaleźć rozwiązanie gier 2 × 2, 2 × n, m × 2). Jeżeli jeden z graczy zastosuje optymalną strategię mieszaną, to jego wypłata będzie równa kosztowi gry ν, niezależnie od prawdopodobieństwa, z jakim drugi gracz zastosuje strategie zawarte w strategii optymalnej (w tym strategie czyste). 9 3.1. Gra 2 × 2 Rozważmy grę 2 × 2 z macierzą: () a11 a21 a21 a22 Niech gra nie ma rozwiązania w czystych strategiach. Znajdźmy optymalne strategie SA∗ i SB∗. Najpierw definiujemy strategię SA∗ = (p∗1 , p∗2). Zgodnie z twierdzeniem, jeśli strona A będzie trzymać się strategii ν, to niezależnie od kierunku działania strony B, wypłata pozostanie równa kosztowi gry ν. W konsekwencji, jeśli strona A zastosuje optymalną strategię SA∗ = (p∗1 , p∗2), to strona B może zastosować dowolną ze swoich strategii bez zmiany swojej wypłaty. Następnie, gdy gracz B zastosuje czystą strategię B1 lub B2, otrzyma średnią wypłatę równą kosztowi gry: a11 p∗1 + a21 p∗2 = ν ← dla strategii B1 a12 p∗1 + a22 p∗ 2 = ν ← dla strategii B2 Biorąc pod uwagę, że p∗1 + p∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Cena gry: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 W podobny sposób można znaleźć optymalną strategię gracza B: SB∗ = (q1∗ , q2∗). Biorąc pod uwagę, że q1∗ + q2∗ = 1: q1∗ = a2 2−a1 2 a11 +a22 −a12 −a21 q2∗ = a1 1−a2 1 a11 +a22 −a12 −a21 3.1.1. Przykłady Przykład 3 Znajdź rozwiązanie gry z macierzą () −1 1 A= 1 −1 10 Rozwiązanie: gra nie ma punktu siodłowego, ponieważ α= -1, β = 1, α ̸= β. Rozwiązania szukamy w strategiach mieszanych. Korzystając ze wzorów na p∗ i q∗ otrzymujemy p∗1 = p∗2 = 0,5 i q1∗ = q2∗ = 0,5, ν = 0 Zatem SA∗ = (0,5, 0,5) SB∗ = (0,5, 0,5 ) Przykład 4 Znajdź rozwiązanie gry z macierzą () 2 5 A= 6 4 Rozwiązanie: gra nie ma punktu siodłowego, gdyż α= 4, β = 5, α ̸= β. Rozwiązania szukamy w strategiach mieszanych. Korzystając ze wzorów na p∗ i q∗ otrzymujemy p∗1 = 0,4, p∗2 = 0,6 i q1∗ = 0,2 q2∗ = 0,8, ν = 4,4 Zatem SA∗ = (0,4, 0,6) SB∗ = ( 0,2, 0,8) 11 3.1.2. Interpretacja geometryczna Gra 2 × 2 może mieć prostą interpretację geometryczną. Weźmy pojedynczy odcinek osi odciętych, którego każdy punkt kojarzymy z jakąś strategią mieszaną S = (p1, p2) = (p1, 1 − p1) i prawdopodobieństwo p1 strategii A1 będzie równe odległości od punkt SA na prawy koniec przekroju i prawdopodobieństwo p2 , strategia A2 - odległość do lewego końca. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ W szczególności lewy koniec przekroju (punkt z odciętą = 0) odpowiada do strategii A1, prawy koniec odcinka (x = 1) - strategia A2 Na końcach odcinka przywracane są dwie prostopadłe do osi x: oś I - I - wypłata dla strategii A1 zostaje odroczona, oś II - II - wypłata za strategię A2 zostaje odroczona Niech gracz B zastosuje strategię B1; daje na osiach odpowiednio I – I i II – II punkty o rzędnych a11 i a21. Przez te punkty rysujemy linię prostą B1 − B1′. Dla dowolnej strategii mieszanej SA = (p1, p2) wypłatę gracza wyznacza punkt N na prostej B1 − B1′, odpowiadający punktowi SA na osi x dzielącej odcinek w stosunku p2: p1. Oczywiście linię prostą B2 − B2′, która wyznacza wypłatę dla strategii B2, można skonstruować dokładnie w ten sam sposób. 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Należy znaleźć optymalną strategię SA∗ , tj. w taki sposób, że minimalna wypłata gracza A (biorąc pod uwagę najgorsze zachowanie gracza B) zamieniła się w maksymalną. Aby to zrobić, skonstruuj dolną granicę wypłaty gracza A dla strategii B1, B2, tj. linia przerywana B1 N B2′ ;. Na tej granicy będzie znajdować się minimalna wypłata gracza A dla dowolnej jego strategii mieszanej, punkt N, w którym wypłata ta osiąga maksimum i określa decyzję oraz cenę gry. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S. 1∗ P Współrzędna punktu N to nic innego jak koszt gry ν, jego odcięta wynosi ∗2, a odległość do prawego końca odcinka wynosi ∗1, tj. odległości punktu SA∗ do końców odcinka są równe prawdopodobieństwom ∗2 i ∗1 strategii A2 i A1 optymalnej strategii mieszanej gracza A. w tym przypadku o rozwiązaniu gry zadecydowała punkt przecięcia strategii B1 i B2. Poniżej znajduje się przypadek, w którym optymalną strategią gracza jest czysta strategia A2. Tutaj strategia A2 (dla dowolnej strategii wroga) jest bardziej opłacalna niż strategia A1, 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I .I . .x.I . .X. 2∗ P. A∗S = A2. 2∗ P. A∗ S = A2 Po prawej stronie pokazany jest przypadek, gdy gracz B ma oczywiście nieopłacalną strategię. Interpretacja geometryczna pozwala również zwizualizować niższą cenę gry α i wyższą cenę β .y .I .I I .B2 .B1′ .N .B1 .B2′ .β = a21 .α = a22 .I Ja .I .∗ .x .P2 . A∗ S. 1∗ P Na tym samym wykresie możemy także podać interpretację geometryczną optymalnych strategii gracza B. Łatwo sprawdzić, że udział q1∗ strategii B1 w optymalnej strategii mieszanej SB∗ = (q1∗ , q2∗) jest równy stosunkowi długości odcinka KB2 do sumy długości odcinków KB1 oraz KB2 na osi I – I: .y .I .I I .B2 .B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S. 1∗ P 14 KB2 q1∗ = KB2 + KB1 lub LB2′ q1∗ = LB2′ + LB1′ Optymalną strategię SB∗ = (q1∗ , q2∗) można znaleźć w inny sposób, zamieniając graczy B i B, i zamiast maksimum dolnego limitu wygranych, rozważ minimum górnego limitu. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. Gry 2 × n i m × 2 Rozwiązanie gier 2 × n i m × 2 opiera się na następującym twierdzeniu. Twierdzenie 3. Każda skończona gra m × n ma rozwiązanie, w którym liczba aktywnych strategii każdej ze stron nie przekracza najmniejszej z liczb m i n. Zgodnie z tym twierdzeniem gra 2 × n zawsze ma rozwiązanie, w którym każdy gracz ma co najwyżej dwie aktywne strategie. Po znalezieniu tych strategii gra 2 × n zamienia się w grę 2 × 2, którą można rozwiązać w elementarny sposób. Wyszukiwanie aktywnych strategii można przeprowadzić graficznie: 1) konstruuje się interpretację graficzną; 2) ustala się dolną granicę wygranej; 3) przy dolnej granicy wypłaty identyfikowane są dwie strategie drugiego gracza, które odpowiadają dwóm liniom przecinającym się w punkcie o maksymalnej rzędnej (jeśli w tym punkcie przecinają się więcej niż dwie linie, wybierana jest dowolna para) – te strategie reprezentują aktywne strategie gracza B. Zatem gra 2 × n sprowadza się do gry 2 × 2. Gra m × 2 również może zostać rozwiązana, z tą różnicą, że nie dolna, ale górna granica wypłaty wynosi skonstruowany, a nie maksimum, ale szuka się na nim minimum. Przykład 5 Znajdź rozwiązanie gry () 7 9 8 A= 10 6 9 Rozwiązanie: stosując metodę geometryczną dobieramy strategie aktywne. Linie bezpośrednie B1 – B1′, B2 – B2′ i B3 – B3′ odpowiadają strategiom B1, B2, B3. Linia przerywana B1 N B2 to dolna granica wygranej gracza. Gra ma rozwiązanie S∗A = (23, 31); S∗B = (0,5; 0,5; 0); v = 8. 16 .y .I .I Ja . 1′ B. B. 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .X. 2∗ P. A∗ S. 1∗ P 17 Gra indeksowa, 2 ruchy, 3 2 × 2, 10 osobiste, 3 2 × 2, 9 losowe, 3 geometria, 12 cena gry netto, 7 przykładów, 10 2 × n, 9, 16 m × 2, 9 , 16 nieskończonych, 4 w postaci normalnej, 5 skończonych, 4 wieloruchowych, 4 jednoruchowych, 4 macierzowych, 5 parowych, 2 o sumie zerowej, 2 antagonistycznych, 2 nieantagonistycznych, 2 rozwiązań, 5 w strategiach mieszanych, 5 , 9 w strategiach czystych, 5 z punktem siodłowym, 7 cena, 5 górna, 6 dolna, 6 czysta, 7 maximin, 6 gra matrix, 5 wypłata, 5 minimax, 6 normalizacja gry, 5 strategia, 4 maximin, 6 minimax, 6 optymalna, 4 mieszana, 5 teoria gier, 2 18