Zagadnienia

9.1 Wprowadzenie
9.2 Definicja GE z Doskonałą Informacją
9.3 Strategie w GE
9.4 Postać Strategiczna GE

9. Gry Ekstensywne I

9.1. Wprowadzenie

Inne używane nazwy: Gry w postaci ekstensywnej, Gry w postaci rozwiniętej, Gry Dynamiczne. (EG: Extensive Games, Games in Extensive Form, Sequential Move(s) Game). Będziemy używać skrótu GE.

W GS gracze podejmują decyzje jednocześnie, lub nie znając decyzji przeciwników. W GE gracze podejmują decyzje sekwencyjnie, następstwo czasowe odgrywa kluczową rolę.

Wiele sytuacji politycznych, ekonomicznych, społecznych, (np. aukcje, wspołzawodnictwo firm wprowadzających nowe technologie, negocjacje cenowe, jak równiez wiele gier towarzyskich można opisać jako gry ekstensywne.

Jeżeli nie będzie powiedziane inaczej, będziemy zakładać że gracze są w pełni racjonalni, tzn. jedynym kryterium wyboru ich strategii są wypłaty (ogólniej - preferencje) - gracze maksymalizują swoje wypłaty i nie popełniają błędów przy wyborze strategii.

Wpierw zajmiemy się GE z pełną (kompletną) informacja (EG of (with) Complete Information, EG of (with) Perfect Information), tzn. GE w których:

1: w każdej chwili (w każdym kroku czasowym) dokładnie jeden gracz podejmuje decyzję (jaką akcję wybiera),

2: każdy gracz zna cały dotychczasowy przebieg gry (wie który gracz jaką decyzję podjął w poprzednich chwilach w których podejmował decyzję).

3. powyższa informacja jest wspólną wiedzą (common knowledge).

Przykład 9.1

Ultimatum, Gra w Stonogę patrz Wykład I.

Przykład 9.2

Firma F może wynająć (W) lub nie (N) robotnika (R). Jeśli N to F i P mają wypłaty 0. Jeżeli W, to R może pracować (P) (i wtedy obaj gracze dostaja po 1), lub nie (L), co daje -1 dla F i 2 dla R.

Przykład 9.3 (Gra na Wejście (Odstraszanie) Entry Deterrence Game)

Firma F (pretendent, intruz) ma podjąć decyzję czy wejść (In) czy nie (Out) na rynek monopolisty M incumbent (broniacy, właściciel). F ma wartość 1, M ma wartość 2. Jeśli F wybierze Out to wypłaty graczy są równe ich wartościom. Jeśli F wybierze In to M ma do wyboru dwie akcje: Agree, z wypłatą 2 dla F i 1 dla M, lub Fight, z wypłatą 0 dla F i 0 dla M.

Podstawowe elementy GE to zbiór graczy, kolejność ich ruchów, zbiory akcji każdego gracza gdy jest jego ruch, wyniki gry, preferencje graczy na wynikach. Wszystkie te elementy GE opisuje drzewo (wykres, diagram, graf) gry (game tree). Drzewo gry składa się z

węzłów (wierzchołków).
gałęzi
zbiorów informacyjnych.
indykatorów graczy
indykatorow akcji
wypłat

Definicja 9.1

GE w których wszystkie zbiory informacyjne są singletonami i w których gracze znają wszystkie poprzednie grane akcje i graczy którzy je wykonywali nazywamy GE z doskonałą (zupełną, pełną, kompletną) informacją.

Uwaga 9.1

Jeśli gracze znają wszystkie poprzednie grane akcje i graczy którzy je wykonywali to mówimy że mają doskonałą pamięć (perfect recall). Na ogół zakłada się że to zachodzi (wpp. trudno o rozsądną koncepcję równowagi, czy też rozwiązania gry–trudno pogodzić racjonalność graczy i ich niedoskonałą pamięć…).

9.2. Definicja GE z Doskonałą Informacją

Pełna nazwa gier omawianych w tym rozdziale: Gry Ekstensywne z Doskonałą Informacją . Bedziemy używali w tym rozdziale skrótu: Gry Ekstensywne. Później omówimy krótko GE z Niedoskonałą Informacją.

Definicja 9.2

Gra Ekstensywna jest to czwórka ([18])

$GE=\left\langle N,H,P,(\succeq _{i})_{{i\in N}}\right\rangle:$

$I$ - zbiór graczy
$H$ - zbiór historii – zbiór ciagów (skończonych lub nieskończonych) t. że

a) jeżeli ciąg $(a^{k})_{{k=1}}^{K}\in H$ ( $K\le\infty$ ) oraz $L<K$ to $(a^{k})_{{k=1}}^{L}\in H$

b) jeżeli ciąg $(a^{k})_{{k=1}}^{{\infty}}$ spełnia $(a^{k})_{{k=1}}^{L}\in H$ $\forall L>0$ to $(a^{k})_{{k=1}}^{{\infty}}\in H$

Dodatkowo $H$ zawiera pewien element, $\emptyset\in H$ , nazywany ”ciągiem pustym” . Jest on potrzebny by zdefiniować ”poczatek gry”, patrz niżej.

Elementy zbioru $H$ oznaczamy $h$ i nazywamy historiami. Wyrazy każdego (niepustego) ciągu (niepustej historii) są elementami pewnego zbioru $A$ , nazywanego zbiorem akcji. Nazywamy je akcjami (graczy).

Potocznie mówimy: Historia jest ciągiem akcji (lub jest pusta).

Historia $h=(a^{k})_{{k=1}}^{K}$ jest zakończona (terminal) jeśli jest ciągiem nieskończonym (mówimy: jest nieskończona), lub jeśli nie istnieje akcja $a^{{K+1}}$ t. że $(a^{k})_{{k=1}}^{{K+1}}\in H$ . Zbiór historii zakończonych oznaczamy $Z$ .
$P:H\backslash Z\rightarrow N$ - indykator gracza, funkcja gracza (player function). $P(h)$ zwraca numer gracza który podejmuje decyzję (wykonuje ruch) po historii $h$ .
$\{\preceq _{i}\} _{{i\in N}}$ - zbiór relacji preferencji na zbiorze $Z$ . $\preceq _{i}$ jest relacją preferencji gracza $i$ na zbiorze $Z$ .

Na zakończonych historiach definiujemy preferencje graczy przez podanie funkcji wypłat które opisują te preferencje (zgodnych z tymi preferencjami): $u_{i}:Z\rightarrow\Re$ .

Uwaga 9.2

Ścisłą definicję GE można też podać używając formalizmu teorii grafów, patrz np. [6, 38].

Definicja 9.3

GE jest skończona jeżeli zbiór $H$ jest skończony. GE ma skończony horyzont jeżeli najdłuższa historia jest skończona. Niekiedy warunek skończoności horyzontu jest częścią definicji gry skończonej.

Uwaga 9.3

Gra która nie jest skończona może mieć skończony horyzont. Przykład - Gra Ultimatum z przeliczalną (lub continuum) liczba ofert.

Uwaga 9.4

Definicja GE nie precyzuje zbioru akcji gracza gdy jest jego ruch (po historii $h\notin Z$ ). Zbiór ten można odtworzyć ze zbioru $Z$ zakończonych historii i funkcji gracza $P$ w następujący sposób.

Jeśli dla $h\in H$ ciąg $(h,a)\in H$ (tzn. jest historią), to akcja $a$ jest jedną z akcji którą może grać gracz $P(h)$ po historii $h$ . Zbiór takich akcji oznaczamy $A(h)$ . Formalnie:

Definicja 9.4 ( $A(h)$ –zbiór akcji gracza $P(h)$ po historii $h$ )

$A(h)=\{ a\in A:(h,a)\in H\},$

gdzie $A$ oznacza zbiór wszystkich wyrazów ciągów występujących w $H$ , identyfikowany ze zbiorem wszystkich akcji wszystkich graczy .

Opis przebiegu gry:

Gra zaczyna sie od historii pustej $\emptyset$ . Liczba $P(\emptyset)$ jest numerem gracza który pierwszy wykonuje ruch - wybiera akcję $a^{0}$ ze zbioru $A(\emptyset)$ , która wyznacza historię $(\emptyset,a^{0})$ .

Uwaga 9.5

W dalszym ciagu będziemy w historiach niepustych pomijać symbol $\emptyset$ , czyli np. historię $(\emptyset,a^{0})$ oznaczamy $(a^{0})$ , lub jeszcze krócej, symbolem $a^{0}$ .

Jeśli historia $a^{0}\in Z$ to gra się kończy, wpp. znajdujemy $P(a^{0})$ . Gracz $P(a^{0})$ wybiera akcję ze zbioru $A(a^{0})$ . Ten wybór wyznacza następnego gracza. Ogólnie: Niech $h$ - historia o długości $k$ . Jeśli $h\in Z$ to gra się kończy. Wpp. gracz $P(h)$ wybiera akcję ze zbioru $A(h)$ , aż uzyskamy historię zakończoną. .

Przykład 9.4

W Grze na Wejście:

$H=\{\emptyset,(\emptyset,Enter),(\emptyset,Out),(\emptyset,Enter,Agree),(\emptyset,Enter,Fight)\}$

Przebieg gry:

$P(\emptyset)=C$ (Firm, player 1)

$A(\emptyset)=\{ a:(\emptyset,a)\in H\}=\{ EntEnter,Out\}$

Z tego zbioru gracz $C$ wybiera akcję $a^{0}$ która wyznacza historię $(\emptyset,a^{0})\equiv a^{0}$ . Jeśli $a^{0}=Out\in Z$ to gra się kończy (indykator gracza nie jest określony na $Out$ ). Jeśli $a^{0}=Enter$ to obliczamy $P(Enter)=M$ , oraz

$A(Enter)=\{ a:(Enter,a)\in H\}=\{ Agree,Fight\}.$

$Z=\{ Out\equiv h_{1},\ (Enter,Agree)\equiv h_{2},\ (Enter,Fight)\equiv h_{3}\}.$

Preferencje graczy na zakończonych historiach ustalamy w następujący sposób :

$h_{2}\succeq _{1}h_{1}\succeq _{1}h_{3},\quad\quad h_{1}\succeq _{2}h_{2}\succeq _{2}h_{3}.$

Wprowadzamy funkcje wypłat zgodne z tymi preferencjami:

$u_{C}(Out)=1,\ \ u_{C}(Enter,Agree)=2,\ \ u_{C}(Enter,Fight)=0,$

$u_{M}(Out)=2,\ \ u_{M}(Enter,Agree)=1,\ \ u_{M}(Enter,Fight)=0.$

9.3. Strategie w GE

W GE podstawową rolę będzie odgrywało pojęcie strategii. Strategia gracza to przepis, algorytm, którą akcję ma wybrać w każdej chwili w której w której przypada jego ruch, czyli kompletny plan akcji ”na całą grę”, na wszystkie możliwe sytuacje w grze. Akcja gracza (decyzja, wybór, ruch, posunięcie) to element ze zbioru akcji gracza. Strategia gracza w GE określa przede wszystkim akcję gracza po każdej historii po której jest jego ruch.

Formalne definicje będą podane niżej.

Przykład 9.5

Pieszy ma 2 akcje: może na światłach przejść przez jezdnię (P) lub nie (N), the światła mogą być C, Ż lub Z. Strategie pieszego to wektory $(a_{1},a_{2},a_{3}),\ a_{i}\in\{ C,N\}$ , $a_{1}$ jest akcją jeśli R, $a_{2}$ - jeśli Ż, $a_{3}$ - jeśli Z. Pieszy ma $2^{3}$ strategii. Na przykład $(P,P,P)$ - nieuważanie, $(N,N,N)$ - pasywna, $(N,N,P)$ - postępuj zgodnie z prawem, $(P,P,N)$ - szalona1, $(P,N,N)$ - szalona2 itd.

Przykład 9.6

Jeżeli partia szachów kończyłaby się po pierwszym ruchu czarnych to białe miałyby $20$ strategii, a czarne $20^{{20}}$ strategii. W ”jednoruchowej” grze w GO (bez handicapów) białe mają $361$ , a czarne $361^{{360}}$ strategii.

Gra Kółko i krzyżyk (noughts and crosses). Gracz 1 (np. ”kółkowy”) ma w 1-ym ruchu 9 akcji. Gracz 2 ma w swym 1-ym ruchu 8 akcji. Jeżeli gra kończyłaby się po 1-ym ruchu gracza 2 to ma on $8^{9}$ strategii. Jeżeli po 2-im ruchu gracza 1 to w takiej grze gracz 1 ma $9\times 7^{8}=518832209$ strategii.

Do formalnej definicji strategii będzie nam potrzebna

Definicja 9.5 ( $A_{i}$ - zbiór (wszystkich) akcji gracza $i$ )

$A_{i}:=\{ a\in A:\exists h\in H\backslash Z\ \ P(h)=i\ \wedge\ (h,a)\in H\}$

Uwaga 9.6

W powyższej definicji zamiast $\exists h\in H\backslash Z$ można napisać $\exists h\in H$ .

Dla $h\in H\backslash Z:P(h)=i$ definiujemy

Definicja 9.6 ( $A_{i}(h)$ - zbiór akcji gracza $i$ po historii $h$ )

$A_{i}(h):=\{ a\in A_{i}:\ (h,a)\in H\}$

Definicja (ważna) 9.7

Strategia gracza $i$ w GE jest to funkcja

$s_{i}:\{ h:P(h)=i\}\rightarrow A_{i}:\ \ s_{i}(h)\in A_{i}(h).$

W pewnym sensie definicja strategii jest ”nadokreślona” , może specyfikować akcje które nie będą grane jeżeli były grane wcześniej inne akcje determinowane przez daną strategie (Przykład 9.8 poniżej). Taka definicja jest potrzebna do sformułowania pojęcia równowagi (Nasha) w grach ekstensywnych, a następnie równowagi doskonałej ze względu na podgry.

Przykład 9.7

Targ (Bargaining Game) Gracz 1 (Klient) ocenia wartość przedmiotu sprzedawanego przez gracza 2 (Sprzedawca) na 600. Przedmiot ma dla gracza 2 wartość 50. Gracz 1 może złożyć dwie oferty: zapłaci 100 (C) lub 500 (D). Gracz 2 może w przypadku każdej z ofert zgodzić się na sprzedaż (E w przypadku oferty C, G w przypadku oferty D) lub nie (F w przypadku oferty C, H w przypadku oferty D). Akcja E implikuje wypłaty (”czyste zyski”) graczy: (500, 50), gdzie pierwszy element oznacza wypłatę gracza 1, oferta F implikuje wypłaty (0,0), G: (100, 450), H: (0,0). W tej GE:

$H=\{\emptyset,(C),(D),(C,E),(C,F),(D,G),(D,H)\},$

$H\backslash Z=\{\emptyset,(C),(D)\},$ gdzie $(C),\ (D)$ - ciągi jednowyrazowe.

Strategie gracza 2 to funkcje $s_{2}:\{ h:P(h)=2\}\rightarrow A_{2}$ , takie że

$s_{2}(h)\in A_{2}(h):=\{ a\in A_{2}:(h,a)\in H\wedge P(h)=2\},$

gdzie

$\{ h:P(h)=2\}=\{ C,D\},$

$A_{2}=\{ E,F,G,H\},$

$A_{2}(C)=\{ a\in A_{2}:(C,a)\in H\}=\{ E,F\},$

$A_{2}(D)=\{ a\in A_{2}:(D,a)\in H\}=\{ G,H\},$

Tak więc $s_{2}(C)\in\{ E,F\},\ \ s_{2}(D)\in\{ G,H\},$ a zatem gracz 2 ma 4 strategie:

$s_{2}^{1}(C)=E,\ \ s_{2}^{1}(D)=G\ \ \equiv EG,$

$s_{2}^{2}(C)=E,\ \ s_{2}^{2}(D)=H\ \ \equiv EH,$

$s_{2}^{3}(C)=F,\ \ s_{2}^{3}(D)=G\ \ \equiv FG,$

$s_{2}^{4}(C)=F,\ \ s_{2}^{4}(D)=H\ \ \equiv FH.$

Strategie gracza 1 to funkcje $s_{1}:\{ h:P(h)=1\}\rightarrow A_{1}$ , takie że

$s_{1}(h)\in A_{1}(h):=\{ a\in A_{1}:(h,a)\in H\wedge P(h)=1\},$

gdzie

$\{ h:P(h)=1\}=\{\emptyset\},$

$A_{1}(\emptyset)=\{ C,D\}.$

Ma być $s_{1}(h)\in A_{1}(\emptyset),$ a zatem gracz 1 ma dwie strategie: $s_{1}^{1},\ s_{1}^{2}$ :

$s_{1}^{1}(\emptyset)=C,\ s_{1}^{2}(\emptyset)=D.$

Oznaczamy je $C,D$ , w odróżnieniu od niezakończonych historii $(C),(D)$ .

W powyższym przykładzie strategia gracza może być opisana jako ”plan akcji na wszystkie sytuacje”. W ogólności strategia ma ogólniejsze znaczenie.

Przykład 9.8

$N=\{ 1,2\}$ . Niech $P(\emptyset)=1.$ Jeśli gracz 1 gra D to otrzymujemy historię zakończoną (”gra się kończy”), wypłaty graczy to (2,0), gdzie pierwszy element oznacza wypłatę gracza 1. Jeśli 1 gra C, to określamy $P(C)=2,$ czyli ma ruch gracz 2. Gracz 2-i ma do wyboru dwie akcje: E i F. Jeśli zagra F to gra się kończy i wypłaty są (3,1), jeśli zagra E to otrzymujemy historię niezakończoną $(C,E)\$ , z $P((C,E))=1$ , po której gracz 1-y ma do wyboru dwie akcje: G i H. Jeśli zagra G to wypłaty są (1,2), jeśli H to wypłaty są (0,0). W obu przypadkach gra się kończy.

Gracz 1 ma ruch po historii $h_{1}=\emptyset$ i po $h_{2}=(C,E)$ (pomijamy w oznaczeniach historii niepustych symbol $\emptyset$ ).

Każda strategia gracza 1 to funkcja:

$s_{1}:\{ h_{1},h_{2}\}\rightarrow A_{1}=\{ C,D,G,H\}:\quad s_{1}(h)\in A_{i}(h),$

czyli, pamiętając że $h_{1}=\emptyset,\ h_{2}=(C,E)$ ,

$s_{1}(\emptyset)\in A_{1}(\emptyset)=\{ C,D\},\quad s_{1}((C,E))\in A_{1}((C,E))=\{ G,H\}.$

Takich funkcji jest 4, więc gracz 1 ma 4 strategie $s_{1}^{i},\ \ i=1,...4$ , oznaczane kolejno $CG,CH,DG,DH$ :

CG: wybierz C po historii $\emptyset$ i G po (C,E)

CH: wybierz C po historii $\emptyset$ i H po (C,E)

DG: wybierz D po historii $\emptyset$ i G po (C,E)

DH: wybierz D po historii $\emptyset$ i H po (C,E).

Gracz 2 ma dwie strategie, $s_{2}^{1},s_{2}^{2}:s_{2}^{1}(C)=E,s_{2}^{2}(C)=F$ , które oznaczymy E, F – tak jak jego akcje.

Przedstawiona formalizacja będzie potrzebna do podanej niżej definicji postaci strategicznej gry ekstensywnej i do zdefiniowania, w nastepnym wykładzie, równowagi Nasha w GE.

Definicja 9.8

Profil strategii w GE jest to wektor $s:=(s_{1},...s_{n})$ , gdzie $s_{i}$ - strategia gracza $i$ .

Definicja 9.9

Wynik $O(s)$ GE z profilu $s$ jest to zakończona historia $h\in Z$ skonstruowana nastepujący sposób.

Gracz $P(\emptyset)$ stosuje strategię $s_{{P(\emptyset)}}$ z profilu $s$ , grając akcję

$a^{1}:=s_{{P(\emptyset)}}(\emptyset)\quad\big(a^{1}\in A(\emptyset)\big),$

która definiuje historię $(a^{1})$ . Jeżeli $(a^{1})\in Z$ to oznaczamy ją $O(s)$ i nazywamy wynikiem $O(s)$ GE z profilu $s$ (outcome of the profile $s$ ). Jeżeli $(a^{1})\notin Z$ to gracz $P((a^{1}))$ stosując swoją strategię $s_{{P((a^{1}))}}$ z profilu $s$ gra akcję

$a^{2}:=s_{{P((a^{1}))}}((a^{1}))\in A((a^{1})).$

Jeśli historia $(a^{1},a^{2})\notin Z$ , to proces kontynuujemy aż do otrzymania historii zakończonej. Oznaczamy ją $O(s)$ i nazywamy wynikiem GE z profilu $s$ . Formalnie:

Definicja 9.10

Wynik $O(s)$ GE z profilu strategii $s$ jest to zakończona historia

$O(s)=(a^{k})_{{k=1}}^{K}\in Z,\ \,\ K\le\infty,$

taka że

$a^{1}=s_{{P(\emptyset)}}(\emptyset),$

$a^{{k+1}}=s_{{P((a^{1},...,a^{k}))}}((a^{1},...,a^{k}))\ \ dla\ \ 1\le k<K.$

Zapis ten oznacza że po ”podhistorii” $(a^{1},...,a^{k})$ historii $(a^{j})_{{j=1}}^{K}$ jest grana akcja $a^{{k+1}}=s_{i}((a^{1},...,a^{k}))$ przez gracza $i=P((a^{1},...,a^{k}))$ który stosuje strategię $s_{i}$ z profilu $s$ . Akcja $a^{{k+1}}$ jest wyznaczona jednoznacznie przez strategię $s_{i}$ z profilu $s$ . Zauważmy że $O(s)$ jest, z konstrukcji, jednoznacznie wyznaczony przez $s$ .

Przykład 9.9

W Przykładzie 9.8

$O((CH,E))=(C,E,H)\in Z,\ O((CH,F))=(C,F)\in Z,$

$O((DG,E))=D\in Z,\ O((DH,E))=D\in Z.$

9.4. Postać Strategiczna GE

Rozważmy $GE=\left\langle N,H,P,(u_{i})_{{i\in N}}\right\rangle,\ N=\{ 1,...,n\}$ . Każda GE indukuje pewną GS, którą będziemy nazywać Postacią Strategiczną GE (strategic form, normal form representation of EG).

Definicja 9.11

Postać Strategiczna GE $<N,H,P,(u_{i})_{{i\in N}}>$ jest to GS: $<N,(S_{i})_{{i\in N}},(\bar{u}_{i})_{{i\in N}}>$ w której

$N$ - zbiór graczy GE; $|N|=n$ .
$S_{i}$ - zbiór akcji gracza $i,\ i\in N$ , jest to zbiór jego strategii w GE.
$\bar{u}_{i}$ - funkcja wypłat gracza $i,\ i\in N$ . Wypłata $\bar{u}_{i}$ z danego profilu akcji $s=(s_{1},...,s_{n})$ jest równa wypłacie $u_{i}$ gracza $i$ z wyniku $O(s)$ GE generowanego przez profil $s$ w GE. Formalnie

$\bar{u}_{i}(s):=u_{i}(O(s))$

Uwaga 9.7

Uwaga: W dalszym ciągu będziemy dla uproszczenia utożsamiali $\bar{u}_{i}\equiv u_{i}$ .

Przykład 9.10