Jeśli gra nie ma punktu siodłowego, wówczas występują trudności w ustaleniu ceny gry i optymalnych strategii graczy. Weźmy na przykład grę:
W tej grze i . Pierwszy gracz może więc zagwarantować sobie wypłatę równą 4, a drugi ograniczyć swoją stratę do 5. Obszar pomiędzy i jest niejako remisem, a każdy gracz może spróbować poprawić swój wynik kosztem ten teren. Co powinno być w tym przypadku optymalne strategie gracze?
Jeśli każdy z graczy zastosuje strategię oznaczoną gwiazdką ( i ), to zysk pierwszego gracza i strata drugiego wyniosą 5. Jest to niekorzystne dla drugiego gracza, ponieważ pierwszy wygrywa więcej niż on może sobie zagwarantować. Jeśli jednak drugi gracz ujawni w jakiś sposób zamiar pierwszego gracza, aby użyć strategii, może zastosować strategię i zmniejszyć wypłatę pierwszego gracza do 4. Jeśli jednak pierwszy gracz ujawni zamiar drugiego gracza, aby użyć strategii, następnie stosując strategię , zwiększy swoją wypłatę do 6. W ten sposób powstaje sytuacja, w której każdy gracz musi zachować w tajemnicy strategię, którą zamierza zastosować. Jednak jak to zrobić? W końcu, jeśli gra jest rozgrywana wiele razy, a drugi gracz cały czas stosuje strategię a, to pierwszy gracz szybko odgadnie intencje drugiego i po zastosowaniu strategii będzie miał dodatkową wypłatę. Oczywiście drugi gracz musi zmieniać strategię w każdej nowej grze, ale musi to robić w taki sposób, aby pierwszy nie zgadywał, którą strategię zastosuje w każdym przypadku.
W przypadku mechanizmu losowego wyboru zyski i straty graczy będą zmiennymi losowymi. Wynik gry w tym przypadku można oszacować przeciętny strata drugiego gracza. Wróćmy do przykładu. Tak więc, jeśli drugi gracz użyje strategii i losowo z prawdopodobieństwem 0,5; 0,5, to przy strategii pierwszego gracza średnia wartość jego straty wyniesie:
i ze strategią pierwszego gracza
Dlatego drugi gracz może ograniczyć swoją średnią stratę do 4,5, niezależnie od strategii zastosowanej przez pierwszego gracza.
Dlatego w wielu przypadkach celowe okazuje się nie nakreślanie strategii z góry, ale wybranie jednej lub drugiej losowo, przy użyciu pewnego rodzaju mechanizmu losowego wyboru. strategia oparta na losowy wybór, zwany strategia mieszana, w przeciwieństwie do zamierzonych strategii, które są tzw czyste strategie.
Podajmy bardziej rygorystyczną definicję czystych i mieszanych strategii.
Niech będzie gra bez punktu siodłowego:
Oznaczmy częstotliwość stosowania czystej strategii pierwszego gracza przez , (prawdopodobieństwo zastosowania i-tej strategii). Podobnie częstość stosowania czystej strategii drugiego gracza oznaczamy przez , (prawdopodobieństwo zastosowania j-tej strategii). W przypadku gry z punktem siodłowym istnieje rozwiązanie w czyste strategie. Dla gry bez punktu siodłowego istnieje rozwiązanie w strategiach mieszanych, czyli gdy wybór strategii opiera się na prawdopodobieństwach. Następnie
Wiele czystych strategii pierwszego gracza;
Wiele mieszanych strategii pierwszego gracza;
Wiele czystych strategii drugiego gracza;
Wiele strategii mieszanych dla drugiego gracza.
Rozważmy przykład: niech będzie gra
Drugi gracz wybiera prawdopodobieństwo 
. Oszacujmy średnią stratę drugiego gracza przy zastosowaniu odpowiednio strategii i .
Wśród skończonych gier, które mają wartość praktyczna, gry z punktem siodłowym są stosunkowo rzadkie; bardziej typowy jest przypadek, gdy dolna i górna cena - gry są różne. Analizując macierze takich gier, doszliśmy do wniosku, że każdy gracz ma wybór
jedna - jedyna strategia., to w oparciu o rozsądnie działającego przeciwnika wybór ten powinien być determinowany zasadą minimaksu. Trzymając się naszej strategii maximin, z pewnością gwarantujemy sobie wypłatę równą niższej cenie gry, a, za każde zachowanie przeciwnika. Powstaje naturalne pytanie: czy można zagwarantować sobie średnią wypłatę większą niż a, jeśli zastosuje się nie tylko jedną „czystą” strategię, ale naprzemiennie kilka losowo wybranych strategii?
Takie strategie łączone, polegające na stosowaniu naprzemiennie kilku czystych strategii zgodnie z prawem losowości z określonym stosunkiem częstotliwości, nazywane są w teorii gier strategiami mieszanymi.
Oczywiście każda strategia czysta jest szczególnym przypadkiem strategii mieszanej, w której wszystkie strategie oprócz jednej stosowane są z częstotliwością zerową, a ta z częstotliwością 1.
Okazuje się, że stosując nie tylko czyste, ale i mieszane strategie, możliwe jest uzyskanie rozwiązania dla każdej skończonej gry, tj. równa cenie gra, aw przypadku jednostronnego odchylenia od strategii optymalnej, wypłata może zmienić się tylko w kierunku niekorzystnym dla dewianta.
Stwierdzone stwierdzenie jest treścią tzw. głównego twierdzenia teorii gier. Twierdzenie to zostało po raz pierwszy udowodnione przez von Neumanna w 1928 r. Znane dowody twierdzenia są stosunkowo złożone; dlatego przedstawiamy tylko jego sformułowanie.
Każda skończona gra ma co najmniej jedno rozwiązanie (być może w dziedzinie strategii mieszanych).
Wypłata wynikająca z decyzji nazywana jest ceną gry. Z głównego twierdzenia wynika, że każda skończona gra ma swoją cenę. Oczywiście wartość gry v zawsze leży pomiędzy Niższa cena gra a i najwyższa cena gry:
Rzeczywiście, istnieje maksymalna gwarantowana wypłata, którą możemy sobie zapewnić, używając tylko naszych własnych czystych strategii. Ponieważ strategie mieszane obejmują, jako szczególny przypadek, wszystkie czyste, to dopuszczając, oprócz czystych, również mieszane
strategia, w żadnym wypadku nie pogarszamy naszych możliwości; W konsekwencji,
Podobnie, biorąc pod uwagę możliwości przeciwnika, pokazujemy to
skąd wynika wymagana nierówność (3.1).
Wprowadźmy specjalną notację dla strategii mieszanych. Jeżeli np. nasza strategia mieszana polega na stosowaniu strategii AL, z częstotliwościami i taką strategię będziemy oznaczać
Podobnie mieszana strategia przeciwnika będzie oznaczona przez:
gdzie są częstotliwości, przy których strategie są mieszane
Załóżmy, że znaleźliśmy rozwiązanie gry składającej się z dwóch optymalnych strategii mieszanych S, S. W ogólnym przypadku nie wszystkie czyste strategie dostępne dla danego gracza mieszczą się w jego optymalnej strategii mieszanej, ale tylko niektóre z nich. Strategie zawarte w optymalnej strategii mieszanej gracza będziemy nazywać jego strategiami „użytecznymi”.
Okazuje się, że rozwiązanie gry ma jeszcze jedną niezwykłą cechę: jeśli jeden z graczy trzyma się swojej optymalnej strategii mieszanej 5 (5). wtedy wypłata pozostaje niezmieniona i równa cenie gry v, niezależnie od tego, co zrobi drugi gracz, jeśli on. tylko nie wykracza poza swoje „użyteczne” strategie. Na przykład może użyć dowolnej ze swoich „użytecznych” strategii w czysta forma, a także można je mieszać w dowolnych proporcjach.
Udowodnijmy to stwierdzenie. Niech będzie rozwiązanie gry. Dla ścisłości przyjmiemy, że optymalna strategia mieszana składa się z mieszanki trzech
„użyteczne” strategie odpowiednio składają się z mieszanki trzech „użytecznych” strategii
oraz Stwierdza się, że jeśli będziemy trzymać się strategii S, to przeciwnik może stosować strategie w dowolnych proporcjach, a wypłata pozostanie niezmieniona i nadal będzie równa cenie gry
Strategia mieszana SA gracza A to zastosowanie czystych strategii A1, A2, ..., Am z prawdopodobieństwami p1, p2, ..., pi, ..., pm, a suma prawdopodobieństw jest równa 1: Strategie mieszane gracza A są zapisywane jako macierz lub ciąg znaków SA = (p1, p2, ..., pi, ..., pm) Podobnie strategie mieszane gracza B są oznaczane: , lub, SB = (q1, q2, ..., qi, ..., qn ), gdzie suma prawdopodobieństw wystąpienia strategii jest równa 1: Strategie czyste można uznać za szczególny przypadek strategii mieszanych i można je określić jako ciąg znaków gdzie 1 odpowiada czystej strategii. W oparciu o zasadę minimaksu, optymalne rozwiązanie(lub rozwiązanie) gry: jest to para optymalnych strategii S*A , S*B w ogólnym przypadku mieszanym, o następującej własności: jeżeli jeden z graczy trzyma się swojej optymalnej strategii, to nie może być to opłacalne dla drugi odbiega od swojego. Wypłata odpowiadająca rozwiązaniu optymalnemu nazywana jest wartością gry v. Cena gry spełnia nierówność: ? ? v? ? (3.5) gdzie? oraz? - dolną i górną cenę gry. Obowiązuje następujące główne twierdzenie teorii gier - twierdzenie Neumanna. Każda skończona gra ma co najmniej jedno optymalne rozwiązanie, być może wśród strategii mieszanych. Niech S*A = (p*1, p*2, ..., p*i, ..., p*m) i S*B = (q*1, q*2, ..., q* i, ..., q*n) - para strategii optymalnych. Jeśli strategia czysta jest zawarta w optymalnej strategii mieszanej z niezerowym prawdopodobieństwem, to nazywa się ją aktywną. Obowiązuje twierdzenie o strategiach aktywnych: jeśli jeden z graczy trzyma się swojej optymalnej strategii mieszanej, to wypłata pozostaje niezmieniona i równa kosztowi gry v, jeśli drugi gracz nie wykracza poza swoje aktywne strategie. Twierdzenie to ma ogromne znaczenie praktyczne - podaje konkretne modele znajdowania optymalnych strategii przy braku punktu siodłowego. Rozważmy grę 2×2, która jest najprostszym przypadkiem skończonej gry. Jeżeli taka gra ma punkt siodłowy, to optymalnym rozwiązaniem jest para czystych strategii odpowiadających temu punktowi. Gra, w której nie ma punktu siodłowego, zgodnie z głównym twierdzeniem teorii gier, rozwiązanie optymalne istnieje i jest określone przez parę strategii mieszanych S*A = (p*1, p*2) i S*B = (q*1, q*2) . Aby je znaleźć, używamy twierdzenia o strategiach aktywnych. Jeśli gracz A trzyma się swojej optymalnej strategii S „A, to jego średnia wypłata będzie równa cenie gry v, bez względu na to, jakiej aktywnej strategii używa gracz B. W przypadku gry 2 × 2 każda czysta strategia przeciwnika jest aktywny jeśli nie ma punktu siodłowego Wypłata gracza A (utrata gracza B) - zmienna losowa, wartość oczekiwana(średnia), która jest ceną gry. Dlatego średnia wypłata gracza A (strategia optymalna) będzie równa v zarówno dla pierwszej, jak i drugiej strategii przeciwnika. Niech grę da nam macierz wypłat Średnia wypłata gracza A, jeśli stosuje optymalną strategię mieszaną, a gracza B - czystą strategię B1 (odpowiada to kolumnie 1 macierz płatności P) jest równe wartości gry v: a11 p*1+ a21 p*2= v. Gracz A otrzymuje taką samą średnią wypłatę, jeśli drugi gracz stosuje strategię B2, tj. a12 p*1+ a22 p*2= w. Biorąc pod uwagę, że p * 1 + p * 2 = 1, otrzymujemy układ równań do określania optymalnej strategii S "A i wartość gry v: (3.6) Rozwiązując ten układ, otrzymujemy optymalną strategię (3.7) i wartość gry (3.8) Stosując twierdzenie o strategiach aktywnych przy znajdowaniu SВ* - optymalnej strategii gracza B, otrzymujemy, że dla dowolnej czystej strategii gracza A (A1 lub A2) średnia strata gracza B jest równa cena gry v, czyli (3.9) Wtedy optymalną strategię określają wzory: (3.10 )
Czysta strategia- deterministyczny (wykluczający losowość) plan działania. W poprzednim rozdziale rozważaliśmy tylko czyste strategie. Strategie mieszane zostaną omówione w podrozdziale 2.2, ale na razie, o ile nie zaznaczono inaczej, przez strategię zawsze rozumiemy czystą strategię.
Bardzo często w procesie prezentacji będziemy ilustrować koncepcje rozwiązania przykładami gier dwumacierzowych, więc podamy odpowiednie definicje.
Definicja 2.1. gra końcowa to gra, w której zbiór graczy i zbiór strategii każdego gracza zawiera skończoną liczbę elementów. Nazywa się ostateczna gra dwóch osób gra dwumacierzowa.
Nazwisko pochodzi od wygodnej formy zapisywania wygranych w takiej grze – za pomocą podwójnej matrycy.
Dla dalszej analizy wygodnie jest podzielić strategie w dowolnym profilu strategii s na strategię jednego /-tego gracza s i strategie wszystkich pozostałych graczy s_ (formalnie s = (.y, s,). Nie sugeruje się tutaj, że zamieniamy współrzędne profilu strategii, wprowadzamy tylko inny sposób jego oznaczenia.
Pierwszą koncepcją rozwiązania gry, którą rozważymy, jest równowaga w strategiach dominujących.
Definicja 2.2. Strategia /-tego gracza ściśle zdominowany jego strategia jest „jeśli”. Uj(s jt s ,) > h,(s", s ,) dla dowolnego zestawu s strategii pozostałych graczy. W tym przypadku strategia s" nazywa się ściśle zdominowany.
Zasadniczo oznacza to, że dla każdego naprawił w zbiorze strategii pozostałych graczy i-ty gracz, wybierając strategię s, uzyskuje ściśle większa wygrana niż przy wyborze strategii s”. Logiczne jest założenie, że racjonalny gracz nie powinien wybierać strategii ściśle zdominowanych. Takie założenie w najprostszych grach może wystarczyć do znalezienia rozwiązania gry.
Definicja 2.3. Profil strategii s* =(s*, s^,..., s*) jest wywoływana saldo w (ściśle) strategie dominujące, jeśli dla dowolnego i-tego gracza strategia s ściśle dominuje nad innymi jego strategiami.
Mogłoby się wydawać, że taka koncepcja rozwiązania może prowadzić tylko do banalnych wniosków. Każdy gracz ma wśród swoich strategii taką, która zapewni mu wyższą wypłatę niż jakakolwiek inna, bez względu na to, jak postąpią jego przeciwnicy. Wtedy zastosuje dokładnie tę strategię w równowadze. Wszystko jest dość oczywiste. Ale to właśnie ta sytuacja jest typowa dla być może najbardziej znanego i bardzo ważnego dla analizy szeregu praktycznych sytuacji gry „dylemat więźnia”.
Przykład 2.1 (dylemat więźnia). Dwóch przestępców przebywa w areszcie w różnych celach i nie może się komunikować. Śledztwo ma wystarczające dowody, aby skazać każdego z nich za drobne przestępstwo na rok. Ale w przypadku poważnego przestępstwa, za które przestępcom grozi dziesięć lat więzienia, śledztwo nie ma wystarczających dowodów. Przedstawiciele śledztwa proponują każdemu z przestępców układ: przestępca otrzyma termin
o rok krócej, jeśli złoży zeznania przeciwko partnerowi, co wystarczy, by oskarżyć go o poważne przestępstwo. Załóżmy, że przestępcy interesują się tylko liczbą lat, które spędzą w więzieniu, każdy dodatkowy rok to minus jedna jednostka użyteczności. Wtedy wypłaty przestępców można przedstawić za pomocą następującej podwójnej macierzy:
W przypadku, gdy uczestnicy gry nie są wymienieni, przyjmiemy, że wierszom podwójnej macierzy odpowiadają różne strategie pierwszego uczestnika, a kolumnom strategie drugiego uczestnika. Jeśli w naszym przykładzie pierwszy więzień zeznaje, a drugi nie zezna, to pierwszy zostanie zwolniony, a drugi dostanie dziesięć lat więzienia.
Łatwo zauważyć, że bez względu na to, jak zachowuje się drugi więzień, zysk jest większy (okres pozbawienia wolności jest krótszy), jeśli składasz zeznania (dla pierwszego gracza pierwsze współrzędne w pierwszym rzędzie podwójnej matrycy są ściśle większa niż w drugim rzędzie, dla drugiego gracza drugie współrzędne w podwójnej macierzy pierwszej kolumny są ściśle większe niż w drugiej kolumnie). Wtedy równowaga w dominujących strategiach będzie profilem strategii (zeznawać, świadczyć).
Interesujące w tym przykładzie jest to, że gracze, wybierając zachowanie, które zwiększa ich wypłatę, znajdują się w sytuacji, w której ich wypłaty są niskie w porównaniu do odwrotnej sytuacji, w której obaj decydują się na milczenie. Wyjaśnienie leży w obecności silnego efektu zewnętrznego, tj. silny wpływ działań jednego gracza na wypłaty innego gracza. W rezultacie profil równowagi strategii okazuje się jedynym nieefektywnym w sensie Pareto w tej grze. Należy zauważyć, że efektywność Pareto, pożądana z punktu widzenia uczestników gry, może nie być pożądana ze społecznego punktu widzenia, jak w tym przypadku.
Sytuacje takie jak Dylemat Więźnia często pojawiają się w analizie sytuacji ekonomicznych. Rozważmy na przykład konkurencję między dwoma sklepami sprzedającymi podobny zestaw produktów. Dla uproszczenia załóżmy, że sklepy mogą naliczać tylko dwa poziomy cen – wysokie lub niskie. Konsumenci naturalnie wolą kupować w sklepie z niższymi cenami. Wówczas wypłaty sklepów, scharakteryzowane ich zyskami, mogą wyglądać np. następująco:
Z punktu widzenia równowagi sytuacja jest tu analogiczna do Dylematu Więźnia – równowaga w strategiach dominujących (niskie ceny, niskie ceny) jest jedynym profilem nieefektywnym w sensie Pareto (a także pożądanym ze społecznego punktu widzenia).
Wspomniana już duża popularność Dylematu Więźnia była powodem, dla którego na jego przykładzie próbowano eksperymentalnie sprawdzić poprawność przewidywań teorii gier. Test polegał na tym, że dwa nieznajomi zaproponowano grę na pieniądze z nagrodami (na przykład w dolarach) zbliżonymi do wskazanych w grze w dwa sklepy. Każdy z uczestników podejmował decyzję osobno (często anonimowo) i nie znał decyzji drugiego gracza przed otrzymaniem wygranej. Okazało się, że w takich warunkach w wielu zagraniach gracze nie doszli do wyniku równowagi, jeśli założymy, że Nagrody pieniężne poprawnie oszacować swoją wygraną. Oczywiście z wyników tych eksperymentów nie wynika, że przewidywania teorii gier są błędne, a jedynie, że oceniając swoją wypłatę, gracze brali pod uwagę czynniki niepieniężne – względy altruizmu, uczciwości itp. Jeśli wypłaty graczy są poprawnie oszacowane, to gracze powinni preferować strategię dominującą, a więc ją wybrać (w duchu preferencji ujawnionych w mikroekonomii). Dlatego wartość tego rodzaju eksperymentów nie polega na testowaniu przewidywań teorii gier, ale na ocenie roli motywacji niematerialnej w działaniach jednostek.
Znacznie mniej niż koncepcja silnej dominacji, teoria gier wykorzystuje koncepcję słabej dominacji.
Definicja 2.4. Strategia /-tego gracza s, słabo dominujący jego strategia jest „jeśli”. m, (s, s ,) > m ; (sJ, s ,) dla dowolnego zestawu strategii innych graczy s_j, ponadto dla co najmniej jednego zestawu strategii innych graczy nierówność jest ściśle spełniona. Następnie wywoływana jest strategia s”. słabo zdominowany.
W przypadku nierówności nieścisłych nie można już twierdzić, że racjonalny gracz nie wybierze strategii słabo zdominowanej, choć takie zachowanie wydaje się całkiem logiczne. Istnieje, choć rzadko stosowana, definicja równowagi w strategiach słabo dominujących, analogiczna do przypadku silnej dominacji.
Definicja 2.5. Profil strategii s* = (s*, Sj,..., s*) jest wywoływany równowagi w strategiach słabo dominujących, jeśli dla dowolnego i-tego gracza strategia s słabo dominuje nad innymi jego strategiami.
Przykład 2.2 (zamknięta aukcja drugiej ceny). Zamknięta licytacja drugiej ceny odbywa się między dwiema osobami. Aukcja jest zorganizowana w następujący sposób. Każdy z uczestników wskazuje stawkę nieujemną, nie znając stawek innych uczestników (w kopercie). Członek, który stworzył najwyższa oferta, płaci maksymalną kwotę spośród ofert innych uczestników (tj. kwotę drugiego, ale wartość oferty) i otrzymuje jakiś przedmiot. Jeśli np. gracze licytowali 100 i 90, to licytację wygrywa uczestnik, który złożył ofertę 100, nabywa przedmiot za 90 - wielkość drugiej licytacji. Niech każdy uczestnik ma ocenę przedmiotu, wyrażoną w jednostki monetarne, v2> 0. Szacunki te są znane wszystkim uczestnikom. Niech dla uproszczenia opisu gry, jeśli obaj uczestnicy wskażą tę samą stawkę, to przedmiot trafia do pierwszego uczestnika.
W tej grze strategią pierwszego gracza będzie wielkość jego zakładu. Ponieważ stopa jest nieujemna, zbiór wszystkich możliwych strategii
5, = 0 = u,(o, s 2) > w,(s, s 2) = u, - s 2 v x słabo dominuje nad strategią s,.
Pokazaliśmy, że dla pierwszego gracza strategia nazywania swojego wyniku zakładem słabo dominuje nad jakąkolwiek inną strategią. Łatwo sprawdzić, że podobne stwierdzenie jest prawdziwe również dla drugiego gracza. Zauważmy, że w naszym rozumowaniu nigdy nie wykorzystaliśmy faktu, że gracz zna oszacowanie drugiego gracza, a co za tym idzie, w przypadku gry z niepełnymi informacjami w aukcja zamknięta drugi kurs, aby wymienić twoją ocenę, będzie nie mniej opłacalny niż jakikolwiek inny zakład.
Może się wydawać, że sprzedającemu nie opłaca się organizować licytacji drugiej ceny, kiedy może zorganizować licytację pierwszej ceny i otrzymać wartość nie drugiej, ale pierwszej oferty. Jednak wartość kursów w przypadku aukcji pierwszej ceny w równowadze będzie niższa. Porozmawiamy więcej o rentowności aukcji w Rozdz. 5. Tymczasem zauważamy, że aukcja drugiej ceny jest bardzo popularna i jest szeroko stosowana np. przez firmy Google i „Yandex” przy sprzedaży reklam kontekstowych w Internecie.
Równowaga w dominujących strategiach istnieje tylko w mała klasa Gry. Zazwyczaj gracze nie mają jednej strategii, która dominuje nad wszystkimi innymi. Ale koncepcja dominacji pozwala znaleźć rozwiązania w szerszej klasie gier. Aby to zrobić, musisz prowadzić spójne rozumowanie na temat działań graczy. Zauważyliśmy już, że racjonalny gracz nie wybierze strategii ściśle zdominowanej. Oznacza to jednak, że drugi gracz może analizować grę, ignorując możliwość wyboru takiej strategii przez przeciwnika. Być może niektóre analizy ujawnią, że inny gracz ma zdominowaną strategię, która nie była zdominowana w oryginalnej grze. I tak dalej. Podajmy formalną definicję.
Proces sekwencyjne wykluczanie strategii silnie zdominowanych jest ustawiony w następujący sposób. Wykluczmy z rozważań wszystkie ściśle zdominowane strategie graczy, tj. rozważmy nową grę, w której wszystkie strategie zdominowane są wykluczone ze zbioru możliwych strategii graczy. Potem w tym Nowa gra eliminujemy wszystkie strategie ściśle zdominowane i tak dalej.
Możliwe, że taki proces zakończy się, gdy graczom zostanie kilka strategii, ale możliwe, że każdy gracz będzie miał tylko jedną niewykluczoną strategię, wtedy logiczne jest rozważenie zestawu tych strategii jako rozwiązania gry .
Definicja 2.6. Jeżeli w wyniku sekwencyjnej eliminacji strategii silnie zdominowanych każdy gracz zostaje z jedną strategią, to profil tych strategii nazywa się równowaga dominacji.
W Przykładzie 1.1 uzyskaliśmy właśnie taką równowagę. Rozważmy jeszcze jeden przykład.
Profil strategii (N, P) jest jedyną równowagą Nasha w tej grze. Należy jednak zauważyć, że aby wybrać P, drugi gracz musi być pewien, że pierwszy gracz nie wybierze B. Ale wypłata pierwszego gracza jest taka sama, jeśli drugi gracz wybierze II. Dodatkowo, wybierając B, pierwszy gracz może nie obawiać się, że drugi gracz wybierze L. Być może racjonalny drugi gracz zastanowi się nad wyborem strategii C.
Drugie pytanie, na które nie znaleziono jeszcze jednoznacznej odpowiedzi: w jaki sposób gracze dochodzą do równowagi Nasha?
Idealny scenariusz teoretyczny jest następujący. Gracze niezależnie formułują oczekiwania dotyczące działań innych graczy, a następnie wybierają działania, które maksymalizują ich wypłatę przy danych oczekiwaniach. Jeżeli w tym przypadku oczekiwania odpowiadają działaniom faktycznie wybranym przez graczy, to otrzymujemy równowagę Nasha. Ten tok rozumowania pozwala nam nazwać równowagę Nasha sytuacją z samospełniające się oczekiwania. Skąd jednak biorą się oczekiwania? A która z równowag Nasha, jeśli jest ich kilka, zostanie wybrana w wyniku opisanego procesu? W ramach rozważanego scenariusza pytania te pozostają bez odpowiedzi.
Inne podejście obejmuje obecność szkolenia graczy. Gracze albo teoretycznie uczą się grać w daną grę (wyobraźcie sobie studentów Wydział Ekonomii) lub mają doświadczenie w podobnych interakcjach (np Nowa drużyna), co pozwala im na prawidłowe sformułowanie oczekiwań i wybór optymalnego zachowania. Ten scenariusz pomaga wyjaśnić powstawanie oczekiwań, ale po pierwsze ogranicza zakres modele gier tylko do standardowych, zbadanych i często występujących sytuacji interakcji, a po drugie, może to prowadzić do tego, że nie rozróżnia się sytuacji interakcji pojedynczej i powtarzalnej, a te ostatnie znacznie różnią się pod względem strategii i metod rozwiązywania w ramach teorii gier , które zostaną omówione bardziej szczegółowo, powiedział w rozdz. cztery.
Trzeci scenariusz polega na tym, że istnieje uprzednia umowa między graczami, zwyczaje, prawa lub instrukcje stron trzecich, które regulują interakcję graczy. W takim przypadku umowy lub instrukcje mogą nie być wiążące, ale jeśli zaleca się grę w równowagę Nasha, to żaden z graczy nie ma ochoty (sam) odstąpić od zalecanego zachowania. Wiadomo, że taki scenariusz nie jest możliwy w każdej sytuacji. Ponadto sam proces tworzenia umowy lub angażowania osób trzecich może stać się częścią gry.
Wreszcie, trzecie naturalne pytanie, które pojawia się podczas badania koncepcji równowagi Nasha, jest następujące: czy istnieją jakieś empiryczne dowody na to, że prawdziwi gracze zazwyczaj wybierają strategie równowagi? Tutaj znowu niezwykle trudno jest udzielić krótkiej i jednoznacznej odpowiedzi. Jednocześnie charakter pojawiających się problemów jest bardziej zgodny z tematyką ekonomii eksperymentalnej. Dlatego ograniczamy się do zalecenia, aby sięgnąć do literatury specjalistycznej, na przykład książki, w której doskonale przeanalizowano zagadnienia metodologii eksperymentalnej i przedstawiono szereg wyników.
Istnieją gry, które nie mają równowagi w czystych strategiach (patrz przykład 3.1), więc powstaje pytanie: jakie warunki są wystarczające, aby taka równowaga zaistniała? Sformułujmy i udowodnijmy twierdzenie o istnieniu równowagi Nasha w czystych strategiach w grach, które nie są skończone.
Oświadczenie 2.3. Jeśli zestawy strategii dla każdego z graczy Św są niepustymi wypukłymi kompaktami w przestrzeni euklidesowej oraz funkcją wypłaty każdego gracza oraz- ciągły w s i quasi-wklęsły w 5, to gra ma równowagę Nasha w czystych strategiach.
Dowód. Przypomnij sobie formułę Twierdzenia Kakutaia, którego użyjemy w dowodzie. Pozwalać X- niepusty wypukły zbiór zwarty R n , X* jest zbiorem jego podzbiorów i/ jest takim górnym półciągłym odwzorowaniem z X w x*, to dla każdego punktu x e x pęczek f(x) niepuste, zamknięte i wypukłe. Następnie mapowanie / ma stały punkt.
Ideą udowodnienia naszego twierdzenia jest skonstruowanie odwzorowania spełniającego warunki twierdzenia Kakutaniego. Aby to zrobić, nieco przedefiniowaliśmy wyświetlanie najlepszej odpowiedzi. Założymy czysto technicznie, że najlepsza odpowiedź zależy nie tylko od strategii innych graczy, ale także od własnej strategii gracza. Wraz ze zmianą własnej strategii gracza, przy ustalonych strategiach innych graczy, najlepsza odpowiedź oczywiście się nie zmieni. Wprowadźmy teraz notację wyświetlającą najlepszą odpowiedź dla wszystkich graczy jako iloczyn kartezjański SS) = s, (s) x s 2 (s) x... x s n (s). To mapowanie do każdego profilu przypisuje zestaw profili, w których każdy gracz Najlepszym sposobem reaguje na strategie innych graczy. Stały punkt odwzorowania S, tj. profil s takie że s e s > jest z definicji równowagą Nasha. Pokażmy, że odwzorowanie 5 spełnia warunki twierdzenia Kakutaniego. Weryfikacja każdego warunku będzie stanowiła odrębny punkt dowodowy.
- 1. Pokażmy, że zbiór S wszystkie profile - wypukła zwarta. Ponieważ, pod warunkiem stwierdzenia zbioru strategii każdego z graczy S, są niepustymi wypukłymi zbiorami zwartymi, to iloczyn kartezjański S = Św X S2 X...x S n jest zwartością wypukłą.
- 2. Wyświetlacz s ma niepuste obrazy. Z twierdzenia Weierstrassa funkcja ciągła oraz- sięga na domkniętym ograniczonym zbiorze 5, swoim własnym maksymalna wartość. W konsekwencji, s ma niepuste obrazy.
- 3. Wyświetl obrazy s zamknięte i wypukłe. Ponieważ funkcja wypłaty każdego gracza ty t quasi-wklęsły jeśli następnie, na podstawie własności funkcji quasi-wklęsłej, zbiór $. = (s. | u t (s i9 s .) > k) na stałe s i k jest domknięty, gdy dziedzina definicji jest domknięta, i wypukły, gdy nie jest pusty. Ponieważ jest to prawdziwe dla każdego k, to prawdą jest również, że zbiór 5. = (5/1 ty t(s", 5 ,) > maxw.(s., s .)}
wypukły. Ale wtedy iloczyn kartezjański 5(5) = s x (s) X s2(S) x... x s rz CS) jest zamknięta i wypukła.
4. Pokażmy, że mapowanie § półciągły od góry. Korzystamy z warunku ciągłości funkcji oraz, przez s. Udowodnimy przez sprzeczność. Załóżmy, że wyświetlacz § ns jest półciągły górny. Następnie są sekwencje profili strategii s m oraz s m , gdzie t - numer elementu sekwencji, taki, że dla any t s"" e S, s m e s(s""), lim s"" = s° e S, ale lim s"" = s° g lim s(s""). Oznacza to, że istnieje
t~* oo t->/oraz -? oo
skała, dla której strategia s f ° nie jest najlepszą odpowiedzią na s 0 , tj. istnieje strategia s" takie że i,(s", s 0 ,) > nas] s°;). Wtedy można znaleźć e > 0 takie, że m,(s/, s 0 ,) > m,(s ; °, s 0 ,) + Ze, skąd
Ponieważ z założenia funkcja m jest ciągła, lim s m = s°, granica s"” = s°,
m* oo m-*oo
z wystarczająco dużym m prawidłowy
Łącząc nierówności (2.8)-(2.10) w jeden łańcuch otrzymujemy
Z zależności (2.11) wynika, że u,(s", s"") > m,(s/", s"") + s, ale to jest sprzeczne z warunkiem s"" e s(s""), ponieważ s" daje ściśle większą wypłatę niż s/", w odpowiedzi na s"". Doszli do sprzeczności. Dlatego nasze pierwotne założenie, że s nie jest górno-półciągłe, było błędne.
Pokazaliśmy, że mapowanie S spełnia wszystkie warunki twierdzenia Kakutaniego, a zatem ma punkt stały. Ten stały punkt to równowaga Nasha. Twierdzenie 2.3 zostało udowodnione. ?
W szczególności stwierdzenie 2.3 gwarantuje istnienie równowagi Nasha w przykładzie 2.7, ale nie w przykładzie 2.8, gdzie funkcje wypłat graczy są nieciągłe.
„Przykład z pracy.
Wybór akcji przez gracza nazywa się ruszaj się. Są ruchy osobisty(gracz świadomie podejmuje decyzję) i losowy(wynik gry nie zależy od woli gracza). Zestaw reguł określających, który ruch musi wykonać gracz, nazywa się strategia. Istnieją strategie czysty(nielosowe decyzje gracza) i mieszany(strategię można uznać za zmienną losową).
punkt siodłowy
W teoria gry S. t. ( element siodła) - to jest największy element kolumna matryce gier, który jest również najmniejszym elementem odpowiedniego wiersza (w dwuosobowa gra o sumie zerowej). Dlatego w tym momencie maksim jednego gracza jest równy minimaksowi drugiego; S. t. jest sedno równowaga.
Twierdzenie o minimaksie
Nazywa się strategia minimax strategia minimaksu.
Zasada, która dyktuje graczom wybór najbardziej „ostrożnych” strategii maximin i minimax to tzw zasada minimaksu. Zasada ta wynika z rozsądnego założenia, że każdy gracz dąży do osiągnięcia przeciwnego celu przeciwnika.
Gracz wybiera swoje działania, zakładając, że przeciwnik będzie działał na niekorzyść, tj. spróbuje zaszkodzić.
Funkcja straty
Funkcja straty jest funkcją, która w teorii decyzji statystycznych charakteryzuje straty wynikające z błędnego podejmowania decyzji na podstawie zaobserwowanych danych. Jeżeli rozwiązuje się problem estymacji parametru sygnału na tle zakłóceń, to funkcja strat jest miarą rozbieżności między prawdziwa wartość oszacowany parametr i oszacowanie parametru
Optymalna strategia mieszana gracza to kompletny zestaw zastosowań jego czystych strategii w wielokrotnych powtórzeniach gry w tych samych warunkach z zadanymi prawdopodobieństwami.
Strategia mieszana gracza to komplet zastosowań jego czystych strategii w przypadku wielokrotnych powtórzeń gry w tych samych warunkach z zadanymi prawdopodobieństwami.
1. Jeśli wszystkie elementy wiersza nie są większe niż odpowiadające im elementy innego wiersza, wówczas pierwotny wiersz można usunąć z macierzy wypłat. Podobnie dla kolumn.
2. Cena gry jest wyjątkowa.
Dokumentacja: powiedzmy, że są 2 ceny gier w i , które są osiągane na parze i odpowiednio wtedy
3. Jeśli do wszystkich elementów macierzy wypłat dodamy tę samą liczbę, to optymalne strategie mieszane nie ulegną zmianie, a cena gry wzrośnie o tę liczbę.
Dokumentacja:
, gdzie 
4. Jeżeli wszystkie elementy macierzy wypłat pomnożymy przez tę samą liczbę różną od zera, cena gry zostanie pomnożona przez tę liczbę, a optymalne strategie nie ulegną zmianie.
