Czyste gry strategiczne. Teoria gier i decyzje statystyczne

Opis gry bimatrix. Wszystkie gry, które zostały zrecenzowane, należały do ​​tej klasy gry o sumie zerowej. Jednak szereg sytuacji konfliktowych powstających w toku działań charakteryzuje się tym, że zysk jednej strony nie jest dokładnie równy stracie drugiej. Modele teorii gier Takie sytuacje to niekooperacyjne gry o sumie niezerowej. Takie gry nazywane są bimatrixami, ponieważ zadanie każdej takiej gry sprowadza się do zadania dwóch macierzy tej samej postaci: .

Proces gra bimatrixowa polega na samodzielnym wyborze przez gracza I numeru i przez gracza II numeru, po czym gracz I otrzymuje zwycięstwo, a gracz II otrzymuje zwycięstwo.

Nazywa się numery wierszy macierzy czyste strategie gracza I i numery kolumn tych macierzy to czyste strategie gracza II. Wówczas pary postaci będą sytuacjami w strategiach czystych gra bimatrixowa, a liczby i oznaczają wypłaty graczy I i II w danej sytuacji. Odpowiednio rozkład prawdopodobieństwa zastosowania czystych strategii gracza I wynosi i gracz II - zadzwonimy strategie mieszane. Następnie pary postaci reprezentują sytuacje gra bimatrixowa V strategie mieszane i liczby I są matematycznymi oczekiwaniami wygranej dla graczy I i II.

Sytuacja równowagi gry dwumacierzowej w strategiach mieszanych nazwiemy taką parę, dla której:

(8.2)

,

Gdzie - wartość oczekiwana wygrane gracza I;

Matematyczne oczekiwanie wygranej dla gracza II;

Optymalnie mieszane strategia gracza I;

Optymalnie mieszane strategia gracza II.

Zadanie

Budowa i rozwiązanie gry bimatrix. Załóżmy, że krajowy okręt podwodny przeciw okrętom podwodnym poszukuje swojego rakietowego okrętu podwodnego, który manewruje w ściśle określonej części obszaru patrolu bojowego. Pozostałą część obszaru obsługuje okręt podwodny przeciw okrętom podwodnym, który prowadzi działania poszukiwawcze przeciw okrętom podwodnym. Niech każda łódź przeciw okrętom podwodnym korzysta z własnej stacji hydroakustycznej do wykrywania wroga albo w trybie aktywnym, włączając go okresowo, albo tylko w trybie pasywnym, wykonując ciągłe poszukiwania.

Zarówno okręt podwodny przeciw okrętom podwodnym, jak i okręt podwodny rakietowy z wykrywaniem sonaru mogą uniknąć wroga. Jednak częstotliwość aktywacji sonaru umożliwia wykrywanie, ale jest zawodne.

W podobnym sytuacja konfliktowa jeden z graczy jest okrętem podwodnym do zwalczania okrętów podwodnych, a drugi do zwalczania okrętów podwodnych.Oczywiście rakietowy okręt podwodny nie może być graczem, ponieważ ma tylko jeden sposób działania, którym jest ukradkowe manewrowanie i wykonywanie uników podczas wykrywanie sygnałów sonaru.

Cechą charakterystyczną jest to, że każdy z graczy realizuje inne, choć nie przeciwstawne sobie cele. Rzeczywiście, celem okrętu podwodnego przeciw okrętom podwodnym jest wykrycie okrętu podwodnego rakietowego, a celem okrętu podwodnego przeciw okrętom podwodnym jest wykrycie okrętu podwodnego przeciw okrętom podwodnym. Aby zatem ocenić osiągnięcie celu przez każdego gracza, w zależności od wybranych metod działania (strategii), konieczne jest posiadanie dwóch kryteriów efektywności i odpowiednio dwóch funkcji wypłaty. Wówczas modelem takiej sytuacji konfliktowej będzie gra skończona o sumie niezerowej, opisana dwiema macierzami o tym samym kształcie I , zwany bimatrycą.

Przyjmijmy to jako kryterium wydajności okręt podwodny przeciw okrętom podwodnym (gracz I) prawdopodobieństwo wykrycia okrętu podwodnego rakietowego oraz dla kryterium wydajności okręt podwodny przeciw okrętom podwodnym (gracz II) – prawdopodobieństwo wykrycia okrętu podwodnego przeciw okrętom podwodnym. Wtedy grę bimacierzową dana będzie macierz (rysunek 9.a) i macierz (rysunek 9.b).

Ryż. 9.a.

Ryż. 9.b.

Gdzie - użycie trybu aktywnego;

Korzystanie z trybu pasywnego.

Dwuosobową grę macierzową o sumie zerowej można traktować jako następującą abstrakcyjną grę dla dwóch graczy.

Pierwszy gracz ma M strategie I = 1,2,...,M, drugie ma N strategie J= 1,2,...,N. Każda para strategii ( I, J) dopasowany numer A ja , wyrażający zysk gracza 1 kosztem gracza 2, jeśli pierwszy gracz zaakceptuje jego zysk I- Twoja strategia, a 2 – jego własna J strategia.

Każdy gracz wykonuje jeden ruch: gracz 1 wybiera swój I strategia ( I= ), 2 – Twoje J strategia ( J=
), po czym gracz 1 otrzymuje wygraną A ja kosztem gracza 2 (jeśli A ja < 0, oznacza to, że gracz 1 płaci drugą kwotę | A ja|). W tym miejscu gra się kończy.

Strategia każdego gracza I=
; J =
często nazywana czystą strategią.

Jeśli weźmiemy pod uwagę macierz

A=

następnie prowadzenie każdej gry w grę matrix z matrixem A zależy od wyboru gracza 1 I rząd i gracz 2 J kolumnie i gracz 1 (kosztem gracza 2) otrzymuje wygraną a ij .

Najważniejszą rzeczą w badaniu gier jest koncepcja optymalnych strategii graczy. Koncepcja ta intuicyjnie ma następujące znaczenie: strategia gracza jest optymalna, jeśli zastosowanie tej strategii zapewnia mu największą gwarantowaną wygraną ze wszystkich możliwych strategii drugiego gracza. Na podstawie tych pozycji gracz 1 sprawdza macierz wypłat A w następujący sposób: dla każdej wartości I (I =
) minimalna wartość wygranej ustalana jest w zależności od strategii zastosowanej przez gracza 2

A ja (I=
)

te. określony minimalne wygrane dla gracza 1, pod warunkiem, że zaakceptuje swoje I czystej strategii, to z tych minimalnych wypłat zostanie znaleziona taka strategia I = I O, przy którym to minimalne wzmocnienie będzie maksymalne, tj. usytuowany

A ja =
=(1)

Definicja . Numer , określony wzorem (1), nazywa się niższa cena netto Gry i pokazuje, jakie minimalne wygrane gracz 1 może sobie zagwarantować, stosując swoje czyste strategie do wszystkich możliwych działań gracza 2.

Gracz 2, zachowując się optymalnie, powinien, jeśli to możliwe, poprzez swoje strategie dążyć do zminimalizowania wypłaty gracza 1. Zatem dla gracza 2 znajdujemy

A ja

te. ustalana jest maksymalna wygrana gracza 1, pod warunkiem, że gracz 2 wykorzysta swoją J czystej strategii, następnie gracz 2 szuka swojej własnej J = J 1 strategia, w której gracz 1 otrzyma minimalną wygraną, tj. znajdzie

A ja =
=(2).

Definicja . Numer , określone wzorem (2), nazywa się najwyższa cena netto Gry i pokazuje, jakie maksymalne wygrane gracz 1 może sobie zagwarantować dzięki swoim strategiom.

Innymi słowy, stosując swoje czyste strategie, gracz 1 może zapewnić sobie wygraną nie mniejszą niż , a gracz 2, poprzez zastosowanie swoich czystych strategii, może uniemożliwić graczowi 1 wygranie więcej niż .

Definicja . Jeśli w grze z macierzą A =potem mówią, że ta gra tak siodło punkt w czystych strategiach i Cena netto Gry

 = =.

Punkt siodłowy to para czystych strategii (I O , J O ) odpowiednio gracze 1 i 2, przy czym równość zostaje osiągnięta =. Koncepcja ta ma następujące znaczenie: jeśli jeden z graczy trzyma się strategii odpowiadającej punktowi siodłowemu, wówczas drugi gracz nie może zrobić nic lepszego, jak tylko trzymać się strategii odpowiadającej punktowi siodłowemu. Matematycznie można to zapisać w inny sposób:

Gdzie I, J– dowolne czyste strategie odpowiednio graczy 1 i 2; (I O , J O ) – strategie tworzące punkt siodłowy.

Zatem na podstawie (3) element siodłowy
jest minimalna w i -tym wierszu i maksymalna w jo -tej kolumnie macierzy A. Znalezienie punktu siodłowego macierzy A przebiega następująco: w macierzy A kolejno w każdym linia znajdź element minimalny i sprawdź, czy ten element jest maksymalny w swoim kolumna. Jeśli tak, to jest to element siodłowy, a odpowiadająca mu para strategii tworzy punkt siodłowy. Kilka czystych strategii (I O , J O ) gracze 1 i 2, tworząc punkt siodłowy i element siodłowy
, zwany rozwiązanie gry . W której I O I J O są nazywane optymalnie czyste strategie odpowiednio gracze 1 i 2.

Przykład 1

Punkt siodłowy to para ( I O = 3;J O= 1), przy czym = == 2.

Zauważ, że chociaż wypłata w sytuacji (3;3) jest również równa 2 = =, to nie jest punkt siodłowy, ponieważ ta wygrana nie jest maksymalna wśród wygranych trzeciej kolumny.

Przykład 2

Z analizy macierzy wypłat jasno wynika, że
, tj. ta macierz nie ma punktu siodłowego. Jeśli gracz 1 wybierze swoją czystą strategię maximin I = 2, następnie gracz 2, wybierając swój minimax J= 2, przegra tylko 20. W tym przypadku graczowi 1 opłaca się wybrać strategię i = 1, tj. odejdzie od swojej czystej strategii maximin i wygra 30. Wtedy graczowi 2 będzie opłacało się wybrać strategię j = 1, tj. odejdzie od swojej czystej strategii minimax i straci 10. Z kolei gracz 1 musi wybrać swoją drugą strategię, aby wygrać 40, a gracz 2 w odpowiedzi wybierze swoją drugą strategię itd.

Spójrzmy na przykład. Niech będzie dana macierz gry (4):

Musimy znaleźć niższą cenę gry α, górną cenę gry β oraz strategie minimax i sprawdzić, czy są one stabilne. Rozwiązanie. Z analizy dodatkowej kolumny i wiersza otrzymujemy: α = 5, β = 5. Maksymin jest równy minimaxowi! To jest szczególny przypadek. Co z tego wynika? Weźmy kilka strategii minimax: K 2 i C 3. Jeśli obaj będą trzymać się tych strategii, wypłata wyniesie 5. Załóżmy teraz, że dowiedzieliśmy się o zachowaniu wroga. Co robimy? Nic! Będziemy nadal trzymać się strategii K2, bo jakiekolwiek odstępstwa od niej są dla nas nieopłacalne. Niezależnie od tego, czy wiemy, czy nie wiemy o zachowaniu wroga, nadal będziemy trzymać się strategii K 2! To samo tyczy się „niebieskich” – nie ma sensu, żeby zmieniali strategię C3. W tym przykładzie para strategii K 2 i C 3 jest stabilna, to znaczy reprezentuje pozycję równowagi i zapewnia rozwiązanie gry. Dlaczego się to stało? Ponieważ w macierzy znajduje się specjalny element 5; jest minimalna w swoim rzędzie i jednocześnie maksymalna w swojej kolumnie. Taki element nazywa się punkt siodłowy. Jeżeli macierz ma punkt siodłowy (czyli dolna cena gry jest równa wyższej), to gra ma rozwiązanie w strategiach czystych: jest to para strategii przecinających się w punkcie siodłowym. Sam punkt siodłowy określa cenę gry – w naszym przykładzie jest ona równa 5. Klasa gier posiadających punkt siodłowy ma ogromne znaczenie w teorii gier. W szczególności udowodniono, że jeśli zgodnie z regułami gry każdy z graczy zna wynik wszystkich poprzednich posunięć, zarówno swoich, jak i przeciwnika (tzw. gra z pełną informacją), to gra ma punkt siodłowy i dlatego ma rozwiązanie w czystych strategiach. Przykładami gier z pełną informacją są: szachy, warcaby, kółko i krzyżyk itp. Podajmy przykład gry z pełną informacją, której rozwiązanie jest łatwe do znalezienia. Dwóch graczy – K i C – na przemian kładzie identyczne monety na okrągłym stole. Pozycja każdej monety jest wybierana dowolnie, o ile nie nakłada się na inne. Wygrywa gracz, który jako ostatni umieści monetę (jeśli nie ma już miejsca dla innych). Warto się chwilę zastanowić, aby wynik tej gry był zawsze z góry przesądzony i aby istniała dobrze określona strategia, która gwarantuje wygraną temu graczowi, który jako pierwszy wrzuci monetę (niech będzie to K). Mianowicie K musi umieścić pierwszą monetę na środku stołu, a następnie na każdy ruch C musi odpowiedzieć ruchem dokładnie symetrycznym względem środka stołu! Biedny S może zachowywać się, jak mu się podoba, ale i tak nie ma dla niego ucieczki... Oczywiście taka gra ma sens tylko dla tych, którzy nie znają rozwiązania. Ciekawe, że sytuacja jest dokładnie taka sama z takimi popularna gra jak szachy! Ta gra ma sens tylko do momentu znalezienia rozwiązania. Teoretycznie udowodniono, że istnieje rozwiązanie, a wynik gry w szachy jest w zasadzie z góry ustalony: jeśli każda ze stron zastosuje własną optymalną strategię, wówczas partia albo zawsze zakończy się zwycięstwem białych, albo zawsze wygraną czarnych, lub zawsze z remisem! Ale co dokładnie? Tego jeszcze nie wiemy, gdyż liczba możliwych strategii jest zbyt duża, aby móc skonstruować macierz partii szachowej i znaleźć w niej punkt siodłowy... Zapewne miłośników szachów interesuje fakt, że szachy gra nie zostanie rozwiązana w najbliższym czasie. Na zakończenie zauważmy, że w macierzy może znajdować się nie jeden, ale kilka punktów siodłowych; wówczas istnieje tyle rozwiązań gry w czystych strategiach, ile jest punktów siodłowych. Każdy z nich daje zwycięstwo, równa cenie Gry.

Czysta strategia gracz I ma wybrać jeden z n wierszy macierzy wypłat A, a czystą strategią gracza II jest wybranie jednej z kolumn tej samej macierzy.

Optymalne strategie czystego gracza różnią się od mieszanych obecnością obowiązkowej jednostki p i = 1, q i = 1. Na przykład: P(1,0), Q(1,0). Tutaj p 1 = 1, q 1 = 1.

Problem 1
Korzystając z macierzy płatności, znajdź optymalne strategie czyste, stosując zasadę ścisłej dominacji. Jako odpowiedź zapisz wektory P*, Q*.

	R1	R2	R3	R4
S1	3	1	2	5
S2	2	0	0	3
S3	-3	-5	-5	-2
S4	0	-2	-2	1

Rozwiązanie:

Wszystkie problemy rozwiązujemy za pomocą kalkulatora gry Matrix.

Zakładamy, że gracz I wybiera swoją strategię w taki sposób, aby zmaksymalizować swoją wypłatę, a gracz II wybiera swoją strategię w taki sposób, aby zminimalizować wypłatę gracza I.

Gracze	B 1	B 2	B 3	B 4	a = min(A i)
1	3	1	2	5	1
2	2	0	0	3	0
3	-3	-5	-5	-2	-5
4	0	-2	-2	1	-2
b = maks. (B i)	3	1	2	5

Znajdujemy gwarantowaną wypłatę, zdefiniowaną przez Niższa cena gra a = max(a i) = 1, co oznacza maksymalną czystą strategię A 1 .
Górna cena gry b = min(b j) = 1.
Punkt siodłowy (1, 2) wskazuje rozwiązanie pary alternatyw (A1, B2). Cena gry to 1.
2. Sprawdź macierz płatności pod kątem dominujących wierszy i dominujących kolumn.
Czasami na podstawie prostego badania macierzy gry można stwierdzić, że niektóre strategie czyste można zaliczyć do optymalnej strategii mieszanej jedynie z zerowym prawdopodobieństwem.
Mówią, że i-t Strategia Gracza 1 dominuje nad nim kth strategia, jeśli a ij ≥ a kj dla wszystkich j E N i przynajmniej dla jednego J a ij > a kj . W tym przypadku również tak się mówi i-t strategia (lub linia) – dominująca, k-ty– zdominowany.
Mówią, że j-ja Strategia drugiego gracza dominuje nad nim l-te strategia, jeśli jest dla wszystkich j E M a ij ≤ a il oraz dla co najmniej jednego i a ij< a il . В этом случае j-t strategia (kolumna) nazywana jest dominującą, l-te– zdominowany.
Strategia A 1 dominuje nad strategią A 2 (wszystkie elementy wiersza 1 są większe lub równe wartościom wiersza 2), dlatego wykluczamy wiersz 2 macierzy. Prawdopodobieństwo p 2 = 0.
Strategia A 1 dominuje nad strategią A 3 (wszystkie elementy wiersza 1 są większe lub równe wartościom wiersza 3), dlatego wykluczamy wiersz 3 macierzy. Prawdopodobieństwo p 3 = 0.

3	1	2	5
0	-2	-2	1

Z punktu widzenia strat gracza B strategia B 1 dominuje nad strategią B 2 (wszystkie elementy kolumny 1 są większe od elementów kolumny 2), dlatego pomijamy pierwszą kolumnę macierzy. Prawdopodobieństwo q 1 = 0.
Z punktu widzenia strat gracza B strategia B 4 dominuje nad strategią B 1 (wszystkie elementy kolumny 4 są większe od elementów kolumny 1), dlatego też wykluczamy 4 kolumnę macierzy. Prawdopodobieństwo q 4 = 0.

1	2
-2	-2

Zredukowaliśmy grę 4 x 4 do gry 2 x 2.



Rozwiązanie gry ( 2 x rz

p 1 = 1
p2 = 0
Cena gry, y = 1
Teraz możemy znaleźć strategię minimax gracza B, pisząc odpowiedni układ równań
q 1 = 1
q 1 + q 2 = 1
Rozwiązując ten układ znajdujemy:
q 1 = 1.
Odpowiedź:
Cena gry: y = 1, wektory strategii gracza:
Q(1, 0), P(1, 0)

∑a ij q jot ≤ v
∑a ij p ja ≥ v
M(P 1 ;Q) = (1 1) + (2 0) = 1 = v
M(P 2 ;Q) = (-2 1) + (-2 0) = -2 ≤ v
M(P;Q 1) = (1 1) + (-2 0) = 1 = v
M(P;Q 2) = (2 1) + (-2 0) = 2 ≥ v

Ponieważ z oryginalnej macierzy usunięto wiersze i kolumny, znalezione wektory prawdopodobieństwa można zapisać jako:
P(1,0,0,0)
Q(0,1,0,0)

Problem 2
Korzystając z macierzy płatności, znajdź dolną i górną cenę gry. Jeżeli istnieje punkt siodłowy, zapisz wektory optymalnych strategii czystych P*, Q*.

	R1	R2	R3
S1	-6	-5	0
S2	-8	-3	-2
S3	-3	-2	3

Rozwiązanie:
1. Sprawdź, czy matryca płatności ma punkt siodłowy. Jeśli tak, to zapisujemy rozwiązanie gry w czystych strategiach.

Gracze	B 1	B 2	B 3	a = min(A i)
1	-6	-5	0	-6
2	-8	-3	-2	-8
3	-3	-2	3	-3
b = maks. (B i)	-3	-2	3

Znajdujemy gwarantowaną wypłatę wyznaczoną przez niższą cenę gry a = max(a i) = -3, co wskazuje na maksymalną czystą strategię A 3 .
Górna cena gry b = min(b j) = -3.
Punkt siodłowy (3, 1) wskazuje rozwiązanie pary alternatyw (A3, B1). Koszt gry wynosi -3.
Odpowiedź: P(0,0,1), Q(1,0,0)

Problem 3
Korzystając z macierzy płatności, znajdź wektory optymalnych strategii P*, Q* i ceny gry. Który gracz wygrywa?

	R1	R2	R3	R4
S1	-6	-6	2	4
S2	2	-2	7	-1

Rozwiązanie:
1. Sprawdź, czy matryca płatności ma punkt siodłowy. Jeśli tak, to zapisujemy rozwiązanie gry w czystych strategiach.
Zakładamy, że gracz I wybiera swoją strategię w taki sposób, aby zmaksymalizować swoją wypłatę, a gracz II wybiera swoją strategię w taki sposób, aby zminimalizować wypłatę gracza I.

Gracze	B 1	B 2	B 3	B 4	a = min(A i)
1	-6	-6	2	4	-6
2	2	-2	7	-1	-2
b = maks. (B i)	2	-2	7	4

Znajdujemy gwarantowaną wypłatę wyznaczoną przez niższą cenę gry a = max(a i) = -2, co wskazuje na maksymalną czystą strategię A 2 .
Górna cena gry b = min(b j) = -2.
Punkt siodłowy (2, 2) wskazuje rozwiązanie pary alternatyw (A2, B2). Koszt gry wynosi -2.
3. Znajdź rozwiązanie gry w strategiach mieszanych.
Rozwiążmy problem metodą geometryczną, która obejmuje następujące kroki:
1. W kartezjańskim układzie współrzędnych wzdłuż osi odciętych wykreślany jest odcinek, którego długość jest równa 1. Lewy koniec odcinka (punkt x = 0) odpowiada strategii A 1, prawy koniec odpowiada strategii A 2 (x = 1). Punkty pośrednie x odpowiadają prawdopodobieństwom niektórych strategii mieszanych S 1 = (p 1 , p 2).
2. Wypłaty strategii A 1 są wykreślone na lewej rzędnej. Na linii równoległej do rzędnej, od punktu 1, wykreślone są wygrane strategii A 2.
Rozwiązanie gry ( 2 x rz) wykonujemy z pozycji gracza A, trzymając się strategii maximin. Żaden z graczy nie ma strategii dominującej ani powielającej.

Maksymalna optymalna strategia gracza A odpowiada punktowi N, dla którego możemy pisać następujący system równania:
p 1 = 0
p 2 = 1
Cena gry, y = -2
Teraz możemy znaleźć strategię minimax gracza B, pisząc odpowiedni układ równań, wykluczając strategię B 1, B 3, B 4, która wyraźnie daje większą stratę graczowi B, a zatem q 1 = 0,q 3 = 0,q 4 = 0 .
-2q 2 = -2
q 2 = 1
Rozwiązując ten układ znajdujemy:
q 2 = 1.
Odpowiedź:
Cena gry: y = -2, wektory strategii gracza:
Q(0, 1, 0, 0), P(0, 1)
4. Sprawdźmy poprawność rozwiązania gry wykorzystując kryterium optymalności strategii.
∑a ij q jot ≤ v
∑a ij p ja ≥ v
M(P 1 ;Q) = (-6 0) + (-6 1) + (2 0) + (4 0) = -6 ≤ v
M(P 2 ;Q) = (2 0) + (-2 1) + (7 0) + (-1 0) = -2 = v
M(P;Q 1) = (-6 0) + (2 1) = 2 ≥ v
M(P;Q 2) = (-6 0) + (-2 1) = -2 = v
M(P;Q 3) = (2 0) + (7 1) = 7 ≥ v
M(P;Q 4) = (4 0) + (-1 1) = -1 ≥ v
Wszystkie nierówności są spełnione jako równości lub ścisłe nierówności, dlatego rozwiązanie gry jest znalezione poprawnie.

Problem 4
Podaj szczegółową odpowiedź na pytanie

Czysta strategia- deterministyczny (wyłączają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, jeśli nie zaznaczono inaczej, przez strategię zawsze rozumiemy strategię czystą.

Bardzo często podczas prezentacji będziemy ilustrować koncepcje rozwiązań przykładami gier bimatrixowych, dlatego będziemy podawać odpowiednie definicje.

Definicja 2.1. Najlepsza gra to gra, w której zbiór graczy i zbiór strategii każdego gracza zawierają skończoną liczbę elementów. Nazywa się skończoną grą dwóch osób gra bimatrixowa.

Nazwisko pochodzi od wygodnej formy zapisywania wygranej w takiej grze – za pomocą podwójnej matrycy.

Do późniejszej analizy wygodnie jest podzielić strategie w dowolnym profilu strategii s na strategię jakiegoś i-tego gracza i strategie wszystkich pozostałych graczy s_ (. Formalnie s = (.у, s,). Nie chodzi tutaj o zamianę współrzędnych profilu strategii, po prostu wprowadzamy inny sposób jego wyznaczania.

Pierwszą koncepcją rozwiązania gry, której się przyjrzymy, jest równowaga w strategiach dominujących.

Definicja 2.2. Strategia /tego gracza ściśle dominuje jego strategia to „jeśli”. Uj(s jt s ,) > h,(s", s ,) dla dowolnego zestawu s, strategii pozostałych graczy. W tym przypadku strategia s" nazywana jest ściśle zdominowany.

W istocie oznacza to, że dla każdego naprawił w zestawie strategii pozostałych graczy, i-ty gracz, wybierając strategie, otrzymuje ś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*) nazywa się zrównoważyć (strategie ściśle) dominujące, jeśli dla dowolnego i-tego gracza strategia „s” ściśle dominuje nad którąkolwiek z jego pozostałych strategii.

Wydawać by się mogło, że taka koncepcja rozwiązania może prowadzić jedynie do banalnych wniosków. Każdy gracz ma w swojej strategii taką, która zapewni mu więcej wygranych niż jakakolwiek inna, niezależnie od tego, jak zachowają się jego przeciwnicy. Wtedy zastosuje dokładnie tę strategię w równowadze. To wszystko jest dość oczywiste. Ale to właśnie jest sytuacja typowa dla być może najsłynniejszej i bardzo ważnej gry służącej do analizy szeregu sytuacji praktycznych, „dylematu więźnia”.

Przykład 2.1 (dylemat więźnia). Obaj przestępcy przebywają w areszcie w oddzielnych celach i nie mogą się porozumiewać. Śledztwo zgromadziło wystarczający materiał dowodowy, aby skazać każdego z nich na rok za drobne przestępstwo. Jednak 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 oferują każdemu z przestępców układ: przestępca otrzyma wyrok

o rok krócej, jeśli złoży zeznania przeciwko swojemu partnerowi, które wystarczą do postawienia mu zarzutu poważnego przestępstwa. Zakładając, że przestępców interesuje tylko liczba lat spędzonych w więzieniu, każdy dodatkowy rok generuje minus jedną użyteczność. Wówczas wygrane przestępców można przedstawić za pomocą następującej podwójnej macierzy:

W przypadku, gdy uczestnicy gry nie są wymienieni, założymy, że różnym strategiom pierwszego uczestnika odpowiadają wiersze podwójnej macierzy, a strategie drugiego uczestnika odpowiadają kolumnom. Jeśli w naszym przykładzie pierwszy więzień złoży zeznania, a drugi nie, wówczas pierwszy zostanie zwolniony, a drugi otrzyma dziesięć lat więzienia.

Łatwo zauważyć, że niezależnie od tego, jak zachowuje się drugi więzień, zapłata jest większa (kara więzienia jest krótsza), jeśli złożysz zeznania (dla pierwszego gracza pierwsze współrzędne w pierwszym wierszu podwójnej macierzy są ściśle większe niż w drugim rzędzie, dla drugiego gracza drugie współrzędne znajdują się w pierwszej kolumnie, podwójna macierz jest ściśle większa niż w drugiej kolumnie). Wówczas równowagą w strategiach dominujących będzie profil strategii (daj świadectwo, daj świadectwo).

Interesującą rzeczą w tym przykładzie jest to, że gracze, wybierając zachowanie, które zwiększa ich wygraną, kończą w sytuacji, w której ich wypłaty są niskie w porównaniu z sytuacją odwrotną – kiedy obaj decydują się milczeć. Wyjaśnienie leży w obecności silnego efektu zewnętrznego, tj. silny wpływ działań jednego gracza na wygrane innego gracza. W rezultacie profil równowagi strategii okazuje się jedynym profilem nieefektywnym w sensie Pareto w tej grze. Należy pamiętać, ż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.

Przy analizie sytuacji gospodarczych często pojawiają się sytuacje typu dylemat więźnia. Rozważmy na przykład konkurencję pomiędzy dwoma sklepami sprzedającymi podobny zestaw produktów. Dla uproszczenia załóżmy, że sklepy mogą pobierać tylko dwa poziomy cenowe – wysoki lub niski. Konsumenci w naturalny sposób wolą kupować w sklepie, w którym ceny są niższe. Wtedy wygrane sklepów, charakteryzujące się zyskiem, mogą wyglądać np. następująco:

Z punktu widzenia równowagi sytuacja przypomina dylemat więźnia – równowaga w strategiach dominujących (niskie ceny, niskie ceny) to jedyny profil nieefektywny w sensie Pareto (a także pożądany ze społecznego punktu widzenia).

Wspomniana już duża popularność dylematu więźnia spowodowała, że ​​na jego przykładzie próbowano eksperymentalnie sprawdzić poprawność przewidywań teorii gier. Na rachunku było to dwa nieznajomi oferował grę na pieniądze z nagrodami (na przykład w dolarach) zbliżonymi do tych wskazanych w grze obu sklepów. Każdy uczestnik podejmował decyzję osobno (często anonimowo) i nie znał decyzji drugiego gracza, dopóki nie otrzymał on 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 prawidłowo ocenić swoje wygrane. Oczywiście z wyników tych eksperymentów nie wynika, że ​​przewidywania teorii gier są błędne, a jedynie, że oceniając swoje wygrane, gracze brali pod uwagę czynniki pozapieniężne – względy altruizmu, sprawiedliwości itp. Jeśli wypłaty graczy zostaną oszacowane prawidłowo, to gracze powinni preferować strategię dominującą i dlatego ją wybierają (w duchu preferencji ujawnionych w mikroekonomii). Dlatego wartość tego rodzaju eksperymentów nie polega na sprawdzaniu przewidywań teorii gier, ale na ocenie roli motywacji niematerialnej w działaniach jednostek.

W teorii gier używa się koncepcji słabej dominacji w znacznie mniejszym stopniu niż koncepcja ścisłej dominacji.

Definicja 2.4. Strategia i-tego gracza, słabo dominuje jego strategia to „jeśli”. m, (s, s ,) > m ; (sJ, s,) dla dowolnego zestawu strategii pozostałych graczy s_j, Co więcej, dla przynajmniej jednego zestawu strategii innych graczy nierówność jest ściśle spełniona. Następnie nazywana jest strategia s”. słabo zdominowany.

W przypadku nierówności nieścisłych nie można już powiedzieć, ż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, podobna do przypadku ścisłej dominacji.

Definicja 2.5. Nazywa się profil strategii s* = (s*, Sj,..., s*). równowaga w strategiach słabo dominujących, jeśli dla dowolnego i-tego gracza strategia „s” słabo dominuje nad którąkolwiek z jego pozostałych strategii.

Przykład 2.2 (zamknięta aukcja drugiej ceny). Zamknięta aukcja drugiej ceny odbywa się pomiędzy dwiema osobami. Struktura aukcji jest następująca. Każdy uczestnik wskazuje ofertę nieujemną, nie znając ofert pozostałych uczestników (w kopercie). Uczestnik, który dokonał najwyższa oferta, płaci maksymalną kwotę spośród zakładów innych uczestników (tj. kwotę drugiego, ale wielkość zakładu) i otrzymuje jakiś przedmiot. Jeśli na przykład oferty graczy wynosiły 100 i 90, uczestnik, który zaoferował 100, wygrywa aukcję i kupuje przedmiot za 90 – czyli tyle, ile wynosi druga oferta. Niech każdy uczestnik będzie miał ocenę przedmiotu, wyrażoną w jednostki monetarne, v 2> 0. Szacunki te są znane wszystkim uczestnikom. Załóżmy, że dla uproszczenia opisu gry, jeśli obaj uczestnicy wskażą ten sam zakład, to przedmiot trafia do pierwszego uczestnika.

W tej grze strategią pierwszego gracza będzie wielkość jego zakładu. Ponieważ zakład nie jest ujemny, zestaw wszystkich jego możliwych strategii

5, = spełnione 0 = u,(o, s 2) > w,(s, s 2) = = q, - s 2 v x słabo dominuje strategia s,.

Pokazaliśmy, że w przypadku pierwszego gracza strategia sprawdzania jego szacunków w formie zakładu słabo dominuje nad każdą inną strategią. Łatwo sprawdzić, że podobne stwierdzenie jest prawdziwe w przypadku drugiego gracza. Należy zwrócić uwagę, że w naszym rozumowaniu nigdy nie korzystaliśmy z faktu, że gracz zna ocenę drugiego gracza, a zatem w przypadku gry z niepełną informacją w zamknięta aukcja drugiej cenie, sprawdzenie szacunkowych wyników będzie nie mniej zyskowne niż postawienie jakiegokolwiek innego zakładu.

Może się wydawać, że sprzedającemu nie opłaca się urządzać aukcji drugiej ceny, skoro może zorganizować aukcję pierwszej ceny i otrzymać wartość nie drugiej, ale pierwszej oferty. Jednak wartość ofert w przypadku aukcji pierwszej ceny w równowadze będzie niższa. O opłacalności aukcji napiszemy więcej w rozdziale. 5. Na razie zauważmy, że aukcja drugiej ceny cieszy się dużą popularnością i jest szeroko wykorzystywana np. przez firmy Google i „Yandex” przy sprzedaży reklam kontekstowych w Internecie.

Równowaga w strategiach dominujących istnieje tylko w mała klasa Gry. Zazwyczaj gracze nie mają jednej strategii, która dominuje nad wszystkimi innymi. Ale koncepcja dominacji pozwala nam 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ść, że przeciwnik wybierze taką strategię. Być może ta analiza ujawni, że drugi gracz ma strategię dominującą, która nie była dominująca w oryginalnej grze. I tak dalej. Podajmy formalną definicję.

Proces konsekwentne wykluczanie strategii ściśle zdominowanych podaje się następująco. Wykluczmy z rozważań wszystkie strategie graczy ściśle zdominowanych, tj. Rozważmy nową grę, w której wszystkie zdominowane strategie są wykluczone ze zbioru możliwych strategii gracza. Potem w tym Nowa gra wykluczmy wszystkie strategie ściśle zdominowane itp.

Jest możliwe, że taki proces zakończy się, gdy graczom pozostanie kilka strategii, ale jest też możliwe, że każdy gracz będzie miał tylko jedną niewykluczoną strategię, wówczas logiczne jest uznanie zestawu tych strategii za rozwiązanie problemu gra.

Definicja 2.6. Jeżeli w wyniku sekwencyjnej eliminacji strategii ściśle zdominowanych każdemu graczowi pozostanie z jedną strategią, wówczas profil tych strategii nazywa się równowaga dominacji.

W przykładzie 1.1 uzyskaliśmy właśnie taką równowagę. Spójrzmy na inny przykład.

Profil strategii (N, P) stanowi jedyną równowagę Nasha w tej grze. Ale uwaga: aby wybrać P, drugi gracz musi mieć pewność, że pierwszy gracz nie wybierze B. Jednak wypłata pierwszego gracza jest taka sama, jeśli drugi gracz wybierze II. Co więcej, wybierając B, pierwszy gracz nie musi się obawiać, że drugi gracz wybierze A. Być może racjonalny drugi gracz pomyśli o wyborze 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 co do działań innych graczy, a następnie wybierają działania, które maksymalizują ich wypłatę, biorąc pod uwagę ich oczekiwania. Jeśli oczekiwania odpowiadają faktycznie wybranym przez graczy działaniom, wówczas otrzymujemy równowagę Nasha. Ten sposób rozumowania pozwala nam nazwać sytuację równowagą Nasha samospełniające się oczekiwania. Ale skąd biorą się same oczekiwania? A która z równowag Nasha, jeśli jest ich kilka, zostanie wybrana w wyniku opisanego procesu? W rozpatrywanym scenariuszu pytania te pozostają bez odpowiedzi.

Inne podejście polega na szkoleniu zawodników. Gracze albo teoretycznie uczą się, jak grać w daną grę (wyobraźmy sobie uczniów Wydział Ekonomii) lub mają doświadczenie w podobnych interakcjach (przykładowo przychodzi doświadczony pracownik Nowa drużyna), co pozwala im prawidłowo formułować oczekiwania i wybierać optymalne zachowania. Scenariusz ten pomaga wyjaśnić powstawanie oczekiwań, ale po pierwsze zawęża zakres zastosowania modele do gier tylko do standardowych, zbadanych i często występujących sytuacji interakcji, a po drugie, może to prowadzić do tego, że sytuacje interakcji jednorazowej i powtarzalnej nie są różnicowane, a te ostatnie różnią się istotnie z punktu widzenia strategii i sposobów rozwiązywania w ramach ramy teorii gier, które zostaną omówione bardziej szczegółowo w rozdz. 4.

Trzeci scenariusz zakłada, że ​​pomiędzy graczami istnieje wcześniejsza umowa, zwyczaje, przepisy lub instrukcje stron trzecich regulujące interakcję graczy. W takim przypadku ustalenia lub instrukcje mogą nie być obowiązkowe, ale jeśli zaleca się grę w równowadze Nasha, wówczas żaden z graczy nie ma ochoty (sam) odbiegać od przepisanego zachowania. Wiadomo, że nie w każdej sytuacji taki scenariusz jest możliwy. Dodatkowo częścią gry może stać się sam proces zawierania umowy czy angażowania osób trzecich.

Wreszcie trzecie naturalne pytanie, które pojawia się podczas badania koncepcji równowagi Nasha, jest następujące: czy istnieją dowody empiryczne 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 ograniczymy się do zalecenia sięgnięcia po literaturę specjalistyczną, na przykład książkę, w której doskonale omawiane są zagadnienia metodologii eksperymentów i przedstawiane są liczne wyniki.

Istnieją gry, w których nie występuje równowaga czysto strategiczna (patrz przykład 3.1), dlatego pojawia się pytanie: jakie warunki są wystarczające, aby taka równowaga zaistniała? Sformułujmy i udowodnijmy twierdzenie o istnieniu równowagi Nasha w strategiach czystych w grach, które nie są skończone.

Oświadczenie 2.3. Jeśli zestawy strategii dla każdego gracza St są niepustymi wypukłymi zbiorami zwartymi w przestrzeni euklidesowej i funkcją wypłaty każdego gracza I- ciągły w S i jest quasi-wklęsły w 5, to gra ma równowagę Nasha w czystych strategiach.

Dowód. Przypomnijmy sformułowanie Twierdzenia Kakutai'a, którego użyjemy w dowodzie. Pozwalać X- osadzony niepusty wypukły zwarty Rn, X* jest zbiorem jego podzbiorów i/jest górnym odwzorowaniem półciągłym X V X*, to dla każdego punktu x e X pęczek k(x) niepuste, zamknięte i wypukłe. Wtedy odwzorowanie / ma stały punkt.

Ideą udowodnienia naszego twierdzenia jest skonstruowanie odwzorowania spełniającego warunki twierdzenia Kakutaniego. Aby to zrobić, zdefiniujmy nieco sposób wyświetlania najlepszej odpowiedzi. Załóżmy, 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, biorąc pod uwagę ustalone strategie innych graczy, najlepsza odpowiedź oczywiście nie ulegnie zmianie. Teraz wprowadzimy notację wyświetlającą najlepszą odpowiedź dla wszystkich graczy jako iloczyn kartezjański SS) = s,(s)x s2 x... x s n (s). To mapowanie przypisuje do każdego profilu 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(a)> z definicji jest równowagą Nasha. Pokażmy, że odwzorowanie 5 spełnia warunki twierdzenia Kakutaniego. Weryfikacja każdego warunku będzie stanowić odrębny punkt dowodowy.

• 1. Pokażmy, że zbiór S wszystkie profile - wypukłe kompaktowe. Ponieważ zbiór strategii każdego z graczy S jest niepustym zbiorem zwartym wypukłym, to iloczyn kartezjański S = St X S2 X...x S n jest zwartą wypukłą.
• 2. Wyświetlacz S zawiera niepuste obrazy. Według twierdzenia Weierstrassa, funkcja ciągła I- osiąga swój cel na zbiorze zamkniętym ograniczonym 5 maksymalna wartość. Stąd, S zawiera niepuste obrazy.
• 3. Wyświetlaj obrazy S zamknięte i wypukłe. Ponieważ funkcja wypłaty każdego gracza wynosi ty quasi-wklęsły jeśli wówczas, zgodnie z właściwością funkcji quasi-wklęsłej, zbiór $. = (s. | u t (s i9 s .) > k) o stałej porze S .i k zamknięte, jeśli dziedzina definicji jest zamknięta i wypukłe, jeśli nie puste. Ponieważ dotyczy to każdego k, to prawdą jest również, że zbiór 5. = (5/1 ty(s", 5 ,) > maxw.(s., S .)}

wypukły. Ale wtedy iloczyn kartezjański 5(5) = s x (s) X s 2(S) x... X s n 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 I, przez s. Udowodnimy to przez zaprzeczenie. Załóżmy, że mapowanie § ns jest górnym półciągłym. Następnie są sekwencje profili strategii jest m I jest m Gdzie T - numer elementu sekwencji, taki że dla any T s"" tj S, m e s(s""), lim s"" = s° i S, ale lim s"" = s° g lim s(s""). Oznacza to, że istnieje gra

t~* oo t->/I -? oo

los, dla którego strategia s f° nie jest najlepszą odpowiedzią na s 0, tj. istnieje strategia S" takie, że i (y), s 0 ,) > nas] tak ;). Wtedy możemy znaleźć e > 0 takie, że m,(s/, s 0 ,) > m,(s ; °, s 0 ,) + Ze, skąd

Ponieważ pod warunkiem funkcja m jest ciągła, lim s m = s°, lim 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 relacji (2.11) wynika, że ​​u,(s", s"") > m,(s/", s"") + S, ale to jest sprzeczne z warunkiem s"" е s(s""), ponieważ s" daje ściśle większą wypłatę niż s/", w odpowiedzi na s"". Doszliśmy do sprzeczności. Dlatego nasze początkowe założenie, że mapa s nie jest górno-półciągła, było błędne.

Pokazaliśmy, że mapowanie S spełnia wszystkie warunki twierdzenia Kakutaniego, co oznacza, że ​​ma punkt stały. Ten punkt stały jest równowagą 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.

Metody matematyczne i modele w ekonomii

Gry matrixowe

Wstęp

W praktyce gospodarczej często zdarzają się sytuacje, w których różne strony dążą do różnych celów. Na przykład relacje między sprzedawcą a kupującym, dostawcą a konsumentem, bankiem a deponentem itp. Takie sytuacje konfliktowe powstają nie tylko w gospodarce, ale w innych rodzajach działalności. Na przykład podczas gry w szachy, warcaby, domino, lotto itp.

Gra jest matematycznym modelem sytuacji konfliktowej, w której biorą udział co najmniej dwie osoby korzystające z kilku na różne sposoby aby osiągnąć swoje cele. Gra nazywa się łaźnia parowa, jeśli bierze w nim udział dwóch graczy. Gra nazywa się antagonistyczny, jeśli zysk jednego gracza jest równy stracie drugiego. Dlatego, aby skonfigurować grę, wystarczy ustawić zwycięskie wartości jednego gracza w różnych sytuacjach.

Dowolny sposób działania gracza w zależności od aktualnej sytuacji nazywa się strategia. Każdy gracz ma określony zestaw strategii. Jeśli liczba strategii jest skończona, gra zostaje wywołana ostateczny, W przeciwnym razie - nieskończony . Strategie nazywane są czysty, jeśli każdy gracz wybiera tylko jedną strategię w specyficzny, a nie przypadkowy sposób.

Rozwiązanie gry jest wybór strategii, która daje satysfakcję warunek optymalności. Warunek ten jest taki, że otrzymuje je jeden gracz maksymalna wygrana, jeśli drugi będzie trzymał się swojej strategii. I odwrotnie, drugi gracz otrzymuje minimalna strata, jeśli pierwszy gracz będzie trzymał się swojej strategii. Takie strategie nazywane są optymalny . Zatem, Celem gry jest określenie optymalnej strategii dla każdego gracza.

Czysta gra strategiczna

Rozważmy grę z dwoma graczami A I W. Załóżmy, że gracz A To ma M strategie A 1, A 2, …, A m i odtwarzacz W To ma N strategie B 1, B 2, …, B n. Zakładamy, że jest to wybór gracza A strategie A ja, i gracz W strategie Bj jednoznacznie określa wynik gry, tj. wygrana ij gracz A i wygrane b ij gracz W. Tutaj i=1,2,…,m, j=1,2,…,n.

Najprostszą grą dla dwóch graczy jest gra o sumie zerowej. , te. gra, w której interesy graczy są bezpośrednio przeciwne. W tym przypadku wypłaty graczy są powiązane równością

b ij =-a ij

Ta równość oznacza, że ​​zysk jednego gracza jest równy stracie drugiego. W takim przypadku wystarczy wziąć pod uwagę tylko wygrane jednego z graczy, na przykład gracza A.

Każda para strategii A ja I Bj odpowiada wygranej ij gracz A. Wszystkie te wygrane wygodnie jest zapisywać w formie tzw matryca płatności

Wiersze tej macierzy odpowiadają strategiom gracza A, a kolumny – strategie gracza W. Ogólnie taka gra nazywa się (m×n)-gra.

Przykład 1. Dwóch graczy A I W Rzuć monetą. Jeśli strony monety się zgadzają, wygrywa A, tj. gracz W płaci graczowi A pewną kwotę równą 1, a jeśli się nie zgadzają, wygrywa gracz B, tj. wręcz przeciwnie, gracz A płaci graczowi W tę samą kwotę , równy 1. Utwórz matrycę płatności.

Rozwiązanie. Zgodnie z warunkami problemu