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).
Ultimatum, Gra w Stonogę patrz Wykład I.
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.
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
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ą.
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ęć…).
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ą.
Gra Ekstensywna jest to czwórka ([18])
![]() |
- zbiór graczy
- zbiór historii – zbiór ciagów (skończonych lub nieskończonych) t. że
a) jeżeli ciąg (
) oraz
to
b) jeżeli ciąg spełnia
to
Dodatkowo zawiera pewien element,
, nazywany ”ciągiem pustym”
. Jest on potrzebny by zdefiniować ”poczatek gry”, patrz niżej.
Elementy zbioru oznaczamy
i nazywamy historiami. Wyrazy każdego (niepustego) ciągu
(niepustej historii) są elementami pewnego zbioru
, nazywanego zbiorem akcji. Nazywamy je akcjami (graczy).
Potocznie mówimy: Historia jest ciągiem akcji (lub jest pusta).
Historia jest zakończona (terminal) jeśli jest ciągiem nieskończonym (mówimy: jest nieskończona),
lub jeśli nie istnieje akcja
t. że
.
Zbiór historii zakończonych oznaczamy
.
- indykator gracza, funkcja gracza (player function).
zwraca numer gracza który podejmuje decyzję (wykonuje ruch) po historii
.
- zbiór relacji preferencji na zbiorze
.
jest relacją preferencji gracza
na zbiorze
.
Na zakończonych historiach definiujemy preferencje graczy przez podanie funkcji wypłat które opisują te preferencje
(zgodnych z tymi preferencjami): .
GE jest skończona jeżeli zbiór 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.
Gra która nie jest skończona może mieć skończony horyzont. Przykład - Gra Ultimatum z przeliczalną (lub continuum) liczba ofert.
Definicja GE nie precyzuje zbioru akcji gracza gdy jest jego ruch (po historii ). Zbiór ten można odtworzyć ze zbioru
zakończonych historii i funkcji gracza
w następujący sposób.
Jeśli dla ciąg
(tzn. jest historią), to akcja
jest jedną z akcji którą może grać gracz
po historii
. Zbiór takich akcji oznaczamy
. Formalnie:
:
![]() |
gdzie oznacza zbiór wszystkich wyrazów ciągów występujących w
, identyfikowany ze zbiorem wszystkich akcji wszystkich
graczy .
Opis przebiegu gry:
Gra zaczyna sie od historii pustej . Liczba
jest numerem gracza który pierwszy wykonuje ruch -
wybiera akcję
ze zbioru
, która wyznacza historię
.
W dalszym ciagu będziemy w historiach niepustych pomijać symbol , czyli np. historię
oznaczamy
, lub jeszcze krócej, symbolem
.
Jeśli historia to gra się kończy,
wpp. znajdujemy
. Gracz
wybiera akcję ze zbioru
. Ten wybór wyznacza następnego gracza. Ogólnie:
Niech
- historia o długości
. Jeśli
to gra się kończy. Wpp. gracz
wybiera akcję ze zbioru
,
aż uzyskamy historię zakończoną. .
W Grze na Wejście:
Przebieg gry:
(Firm, player 1)
Z tego zbioru gracz wybiera akcję
która wyznacza historię
.
Jeśli
to gra się kończy (indykator gracza nie jest określony na
).
Jeśli
to obliczamy
, oraz
![]() |
![]() |
Preferencje graczy na zakończonych historiach ustalamy w następujący sposób :
![]() |
Wprowadzamy funkcje wypłat zgodne z tymi preferencjami:
![]() |
![]() |
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.
.
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 ,
jest akcją jeśli R,
- jeśli Ż,
- jeśli Z. Pieszy ma
strategii. Na przykład
- nieuważanie,
- pasywna,
- postępuj zgodnie z prawem,
- szalona1,
- szalona2 itd.
Jeżeli partia szachów kończyłaby się po pierwszym ruchu czarnych to białe miałyby strategii, a czarne
strategii.
W ”jednoruchowej” grze w GO (bez handicapów) białe mają
, a czarne
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 strategii. Jeżeli po 2-im ruchu gracza 1 to w takiej grze gracz 1 ma
strategii.
Do formalnej definicji strategii będzie nam potrzebna
![]() |
W powyższej definicji zamiast można napisać
.
Dla definiujemy
![]() |
Strategia gracza w GE jest to funkcja
![]() |
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.
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:
gdzie
- ciągi jednowyrazowe.
Strategie gracza 2 to funkcje , takie że
![]() |
gdzie
![]() |
![]() |
![]() |
![]() |
Tak więc a zatem gracz 2 ma 4 strategie:
![]() |
![]() |
![]() |
![]() |
Strategie gracza 1 to funkcje , takie że
![]() |
gdzie
![]() |
![]() |
Ma być a zatem gracz 1 ma dwie strategie:
:
![]() |
Oznaczamy je , w odróżnieniu od niezakończonych historii
.
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.
. Niech
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
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ą
, z
, 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 i po
(pomijamy w oznaczeniach historii niepustych symbol
).
Każda strategia gracza 1 to funkcja:
![]() |
czyli, pamiętając że ,
![]() |
Takich funkcji jest 4, więc gracz 1 ma 4 strategie , oznaczane kolejno
:
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, , 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.
Profil strategii w GE jest to wektor , gdzie
- strategia gracza
.
Wynik GE z profilu
jest to zakończona
historia
skonstruowana nastepujący sposób.
Gracz stosuje strategię
z profilu
, grając akcję
![]() |
która definiuje historię . Jeżeli
to oznaczamy ją
i nazywamy wynikiem
GE
z profilu
(outcome of the profile
). Jeżeli
to gracz
stosując swoją strategię
z profilu
gra akcję
![]() |
Jeśli historia , to proces kontynuujemy aż do otrzymania historii zakończonej.
Oznaczamy ją
i nazywamy wynikiem GE z profilu
. Formalnie:
Wynik GE z profilu strategii
jest to zakończona historia
![]() |
taka że
![]() |
![]() |
Zapis ten oznacza że po ”podhistorii” historii
jest grana akcja
przez gracza
który stosuje strategię
z profilu
. Akcja
jest wyznaczona jednoznacznie przez strategię
z profilu
. Zauważmy że
jest, z konstrukcji, jednoznacznie wyznaczony przez
.
Rozważmy .
Każda GE indukuje pewną GS, którą będziemy nazywać Postacią Strategiczną GE
(strategic form, normal form representation of EG).
Postać Strategiczna GE jest to GS:
w której
- zbiór graczy GE;
.
- zbiór akcji gracza
, jest to zbiór jego strategii w GE.
- funkcja wypłat gracza
. Wypłata
z danego profilu akcji
jest równa wypłacie
gracza
z wyniku
GE generowanego przez profil
w GE. Formalnie
![]() |
Uwaga: W dalszym ciągu będziemy dla uproszczenia utożsamiali .
W Grze na Wejście:
F ma strategie In, Out, M ma strategie Agree, Fight. Postać strategiczna tej GE to GS o macierzy wypłat:
Agree | Fight | |
---|---|---|
In | 2,1 | 0,0 |
Out | 1,2 | 1,2 |
Macierz wypłat Postaci Strategicznej GE ”Targ” z przykładu 9.7:
EG | EH | FG | FH | |
---|---|---|---|---|
C | 500,50 | 500,50 | 0,0 | 0,0 |
D | 100,450 | 0,0 | 100,450 | 0,0 |
Macierz wypłat Postaci Strategicznej GE z przykładu 9.8:
E | F | ||||
---|---|---|---|---|---|
CG | 1,2 | 3,1 | |||
CH | 0,0 | 3,1 | |||
DG | 2,0 | 2,0 | |||
DH | 2,0 | 2,0 |
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.