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=〈N,H,P,(⪰i)i∈N〉:

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

a) jeżeli ciąg akk=1K∈H (K≤∞) oraz L<K to akk=1L∈H

b) jeżeli ciąg akk=1∞ spełnia akk=1L∈H ∀L>0 to akk=1∞∈H

Dodatkowo H zawiera pewien element, ∅∈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=akk=1K jest zakończona (terminal) jeśli jest ciągiem nieskończonym (mówimy: jest nieskończona), lub jeśli nie istnieje akcja aK+1 t. że akk=1K+1∈H. Zbiór historii zakończonych oznaczamy Z.
P:H\Z→N - indykator gracza, funkcja gracza (player function). P⁢h zwraca numer gracza który podejmuje decyzję (wykonuje ruch) po historii h.
{⪯i}i∈N - zbiór relacji preferencji na zbiorze Z. ⪯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): ui:Z→ℜ.

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∉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∈H ciąg h,a∈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∈A:h,a∈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 ∅. Liczba P⁢∅ jest numerem gracza który pierwszy wykonuje ruch - wybiera akcję a0 ze zbioru A⁢∅, która wyznacza historię ∅,a0.

Uwaga 9.5

W dalszym ciagu będziemy w historiach niepustych pomijać symbol ∅, czyli np. historię ∅,a0 oznaczamy a0, lub jeszcze krócej, symbolem a0.

Jeśli historia a0∈Z to gra się kończy, wpp. znajdujemy P⁢a0. Gracz P⁢a0 wybiera akcję ze zbioru A⁢a0. Ten wybór wyznacza następnego gracza. Ogólnie: Niech h - historia o długości k. Jeśli h∈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=∅,∅,E⁢n⁢t⁢e⁢r,∅,O⁢u⁢t,∅,E⁢n⁢t⁢e⁢r,A⁢g⁢r⁢e⁢e,∅,E⁢n⁢t⁢e⁢r,F⁢i⁢g⁢h⁢t

Przebieg gry:

P⁢∅=C (Firm, player 1)

A⁢∅=a:∅,a∈H=E⁢n⁢t⁢E⁢n⁢t⁢e⁢r,O⁢u⁢t

Z tego zbioru gracz C wybiera akcję a0 która wyznacza historię ∅,a0≡a0. Jeśli a0=O⁢u⁢t∈Z to gra się kończy (indykator gracza nie jest określony na O⁢u⁢t). Jeśli a0=E⁢n⁢t⁢e⁢r to obliczamy P⁢E⁢n⁢t⁢e⁢r=M, oraz

A⁢E⁢n⁢t⁢e⁢r=a:E⁢n⁢t⁢e⁢r,a∈H=A⁢g⁢r⁢e⁢e,F⁢i⁢g⁢h⁢t.

Z={Out≡h1,(Enter,Agree)≡h2,(Enter,Fight)≡h3}.

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

h2⪰1h1⪰1h3,h1⪰2h2⪰2h3.

Wprowadzamy funkcje wypłat zgodne z tymi preferencjami:

uC⁢O⁢u⁢t=1,⁢⁢uC⁢E⁢n⁢t⁢e⁢r,A⁢g⁢r⁢e⁢e=2,⁢⁢uC⁢E⁢n⁢t⁢e⁢r,F⁢i⁢g⁢h⁢t=0,

uM⁢O⁢u⁢t=2,⁢⁢uM⁢E⁢n⁢t⁢e⁢r,A⁢g⁢r⁢e⁢e=1,⁢⁢uM⁢E⁢n⁢t⁢e⁢r,F⁢i⁢g⁢h⁢t=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 a1,a2,a3,⁢ai∈C,N, a1 jest akcją jeśli R, a2 - jeśli Ż, a3 - jeśli Z. Pieszy ma 23 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 2020 strategii. W ”jednoruchowej” grze w GO (bez handicapów) białe mają 361, a czarne 361360 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 89 strategii. Jeżeli po 2-im ruchu gracza 1 to w takiej grze gracz 1 ma 9×78=518832209 strategii.

Do formalnej definicji strategii będzie nam potrzebna

Definicja 9.5 (Ai - zbiór (wszystkich) akcji gracza i)

Ai:=a∈A:∃h∈H\Z⁢⁢⁢P⁢h=i⁢∧⁢h,a∈H

Uwaga 9.6

W powyższej definicji zamiast ∃h∈H\Z można napisać ∃h∈H.

Dla h∈H\Z:P⁢h=i definiujemy

Definicja 9.6 (Ai⁢h - zbiór akcji gracza i po historii h)

Ai⁢h:=a∈Ai:⁢h,a∈H

Definicja (ważna) 9.7

Strategia gracza i w GE jest to funkcja

si:{h:P(h)=i}→Ai:si(h)∈Ai(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=∅,C,D,C,E,C,F,D,G,D,H,

H\Z=∅,C,D, gdzie C,⁢D - ciągi jednowyrazowe.

Strategie gracza 2 to funkcje s2:h:P⁢h=2→A2, takie że

s2⁢h∈A2⁢h:=a∈A2:h,a∈H∧P⁢h=2,

gdzie

h:P⁢h=2=C,D,

A2=E,F,G,H,

A2⁢C=a∈A2:C,a∈H=E,F,

A2⁢D=a∈A2:D,a∈H=G,H,

Tak więc s2⁢C∈E,F,⁢⁢s2⁢D∈G,H, a zatem gracz 2 ma 4 strategie:

s21⁢C=E,⁢⁢s21⁢D=G⁢⁢≡E⁢G,

s22⁢C=E,⁢⁢s22⁢D=H⁢⁢≡E⁢H,

s23⁢C=F,⁢⁢s23⁢D=G⁢⁢≡F⁢G,

s24⁢C=F,⁢⁢s24⁢D=H⁢⁢≡F⁢H.

Strategie gracza 1 to funkcje s1:h:P⁢h=1→A1, takie że

s1⁢h∈A1⁢h:=a∈A1:h,a∈H∧P⁢h=1,

gdzie

h:P⁢h=1=∅,

A1⁢∅=C,D.

Ma być s1⁢h∈A1⁢∅, a zatem gracz 1 ma dwie strategie: s11,⁢s12:

s11⁢∅=C,⁢s12⁢∅=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⁢∅=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 h1=∅ i po h2=C,E (pomijamy w oznaczeniach historii niepustych symbol ∅).

Każda strategia gracza 1 to funkcja:

s1:{h1,h2}→A1={C,D,G,H}:s1(h)∈Ai(h),

czyli, pamiętając że h1=∅,⁢h2=C,E,

s1⁢∅∈A1⁢∅=C,D,⁢s1⁢C,E∈A1⁢C,E=G,H.

Takich funkcji jest 4, więc gracz 1 ma 4 strategie s1i,⁢⁢i=1,…⁢4, oznaczane kolejno C⁢G,C⁢H,D⁢G,D⁢H:

CG: wybierz C po historii ∅ i G po (C,E)

CH: wybierz C po historii ∅ i H po (C,E)

DG: wybierz D po historii ∅ i G po (C,E)

DH: wybierz D po historii ∅ i H po (C,E).

Gracz 2 ma dwie strategie, s21,s22:s21⁢C=E,s22⁢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:=s1,…⁢sn, gdzie si - strategia gracza i.

Definicja 9.9

Wynik O⁢s GE z profilu s jest to zakończona historia h∈Z skonstruowana nastepujący sposób.

Gracz P⁢∅ stosuje strategię sP⁢∅ z profilu s, grając akcję

a1:=sP⁢∅⁢∅⁢a1∈A⁢∅,

która definiuje historię a1. Jeżeli a1∈Z to oznaczamy ją O⁢s i nazywamy wynikiem O⁢s GE z profilu s (outcome of the profile s). Jeżeli a1∉Z to gracz P⁢a1 stosując swoją strategię sP⁢a1 z profilu s gra akcję

a2:=sP⁢a1⁢a1∈A⁢a1.

Jeśli historia a1,a2∉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=akk=1K∈Z,⁢⁢⁢K≤∞,

taka że

a1=sP⁢∅⁢∅,

ak+1=sP⁢a1,…,ak⁢a1,…,ak⁢⁢⁢d⁢l⁢a⁢ 1≤k<K.

Zapis ten oznacza że po ”podhistorii” a1,…,ak historii ajj=1K jest grana akcja ak+1=si⁢a1,…,ak przez gracza i=P⁢a1,…,ak który stosuje strategię si z profilu s. Akcja ak+1 jest wyznaczona jednoznacznie przez strategię si 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⁢C⁢H,E=C,E,H∈Z,⁢O⁢C⁢H,F=C,F∈Z,

O⁢D⁢G,E=D∈Z,⁢O⁢D⁢H,E=D∈Z.

9.4. Postać Strategiczna GE

Rozważmy G⁢E=N,H,P,uii∈N,⁢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,(ui)i∈N> jest to GS: <N,(Si)i∈N,(u¯i)i∈N> w której

N - zbiór graczy GE; N=n.
Si - zbiór akcji gracza i,⁢i∈N, jest to zbiór jego strategii w GE.
u¯i - funkcja wypłat gracza i,⁢i∈N. Wypłata u¯i z danego profilu akcji s=s1,…,sn jest równa wypłacie ui gracza i z wyniku O⁢s GE generowanego przez profil s w GE. Formalnie

u¯i⁢s:=ui⁢O⁢s

Uwaga 9.7

Uwaga: W dalszym ciągu będziemy dla uproszczenia utożsamiali u¯i≡ui.

Przykład 9.10