Transcript
Niepewno´sc´ w teorii gier Paweł Najgebauer 28-01-2008
1
Gra bayesowska W teorii gier spotykamy si˛e cz˛esto z mechanizmami, w których nieznane sa˛ do-
kładne informacje na temat preferencji graczy a takz˙ e macierzy wypłat. Takie mechanizmy nazywa si˛e grami bayesowskimi. Laureat nagrody Nobla w dziedzinie ekonomii z 1994 roku, John Harsanyi, zaproponował wprowadzenie Natury jako dodatkowego gracza w celu zamodelowania niepewno´sci. Natura losowo przypisuje kaz˙ demu z graczy pewien typ, który do pewnego stopnia determinuje jego zachowanie w grze (u´scis´lajac, ˛ determinuje jego funkcj˛e wypłat). Ów typ jest zmienna˛ losowa,˛ której rozkład jest dany. W grze bayesowskiej niekompletno´sc´ informacji oznacza, z˙ e przynajmniej jeden z graczy nie jest pewien jakiego typu sa˛ inni gracze. Gracze na poczatku ˛ gry maja˛ pewne wyobraz˙ enia na temat typów pozostałych uczestników, przy czym nie posiadajac ˛ z˙ adnych przesłanek, gracze musza˛ si˛e oprze´c o dany rozkład moz˙ liwych typów. W czasie gry, gdy zaobserwowane zostana˛ decyzje podj˛ete przez uczestników, owe wyobraz˙ enia moga˛ by´c uaktualniane za pomoca˛ twierdzenia Bayesa (stad ˛ nazwa tego typu gier).
1.1
Specyfikacja gry W grach niebayesowskich z pełna˛ informacja˛ mamy do dyspozycji przestrze´n do-
puszczalnych strategii i funkcje wypłat graczy. Wówczas strategia danego gracza jest kompletnym planem działa´n zabezpieczajacym ˛ kaz˙ da˛ ewentualno´sc´ . Funkcja wypłat jest funkcja˛ przekształcajac ˛ a˛ zbiór strategii na zbiór wypłat (np. typu rzeczywistego). W grach bayesowskich nalez˙ y zdefiniowa´c równiez˙ przestrze´n moz˙ liwych typów graczy i ich wyobraz˙ e´n na temat innych. W takiej sytuacji strategia˛ gracza jest zbiorem planów działa´n gracza dla kaz˙ dego typu, który moz˙ e go dotyczy´c. Macierz przekona´n
1
wzgl˛edem pozostałych graczy wyraz˙ a jego niepewno´sc´ wobec ich typów, pod warunkiem posiadania danego typu. Kaz˙ de takie przekonanie jest prawdopodobie´nstwem warunkowym, wyraz˙ ajacym ˛ si˛e wzorem: p(typyP ozostaychGraczy|typGracza). Funkcja wypłat jest funkcja˛ dwóch zmiennych U (x∗ , t), gdzie x∗ jest strategia˛ w danej grze a t jego typem.
1.2
Punkt równowagi Bayesa-Nasha W grach niebayesowskich profil strategii graczy (macierz strategii) jest punktem
równowagi Nasha, je´sli kaz˙ da strategia w tym profilu jest najlepsza˛ odpowiedzia˛ na dowolne działanie pozostałych graczy, tzn. nie ma takiej strategii, która przyniosłaby lepszy (w sensie Pareto) rezultat, majac ˛ dane strategie grane przez pozostałych graczy. W grach z niepełna˛ informacja,˛ gdzie modeluje si˛e uczestników jako neutralnych wzgl˛edem ryzyka, gracze maksymalizuja˛ oczekiwana˛ warto´sc´ wypłaty, majac ˛ dane wyobraz˙ enia nt. typów pozostałych graczy. W ogólnym przypadku, gdzie uczestnicy moga˛ by´c bardziej lub mniej skłonni do podejmowania ryzyka, zakłada si˛e, z˙ e gracze maksymalizuja˛ warto´sc´ oczekiwana˛ funkcji uz˙ yteczno´sci (´sredniej wypłaty waz˙ onej preferencjami). Punkt równowagi Bayesa-Nasha definiuje si˛e jako profil strategii i przekona´n odno´snie typów pozostałych graczy, który maksymalizuje warto´sc´ oczekiwana˛ wypłat kaz˙ dego z graczy, pod warunkiem ich przekona´n i profili strategii granych przez pozostałych. Takie rozwiazanie ˛ prowadzi do pojawienia si˛e wielu punktów równowagi, co uniemoz˙ liwia precyzyjna˛ analiz˛e gier z niepełna˛ informacja.˛
1.3
Doskonała równowaga Bayesa Koncepcja punktu równowagi Bayesa-Nasha daje mało prawdopodobne rezultaty
w przypadku gier sekwencyjnych, w których gracze podejmuja˛ decyzje naprzemiennie (w przeciwie´nstwie do symultanicznych, w których gracze podejmuja˛ decyzje jednocze´snie). Aby wybra´c odpowiednie punkty równowagi spo´sród znalezionych przez powyz˙ sza˛ metod˛e wprowadza si˛e poj˛ecie doskonałej równowagi Bayesa, które zakłada lokalna˛ optymalizacj˛e (w obr˛ebie, powiedzmy, jednej decyzji).
1.4
Przykład Informacja w grze (rysunek 1) jest niepełna je´sli gracz 2 nie wie jaka˛ decyzj˛e podjał ˛
gracz 1. Je´sli obydwaj gracze sa˛ racjonalni i wiedza˛ wzajemnie o tym (gracz 1 wie, z˙ e gracz 2 jest racjonalny i gracz 2 wie o tym, z˙ e gracz 1 to wie, itd.), gra przebiegnie
2
Rysunek 1: Drzewo decyzyjne nast˛epujaco: ˛ Gracz 1 wybierajac ˛ decyzj˛e U nie ma szans przegra´c, jednak bardziej kuszace ˛ dla niego moz˙ e by´c zaryzykowanie decyzji D i liczenie na decyzj˛e D’ gracza 2. W tym trywialnym przypadku oczywi´scie gracz 2 z duz˙ ym prawdopodobie´nstwem podejmie decyzj˛e U’, i wła´snie taki profil strategii jest punktem doskonałej równowagi Bayesa (w przypadku pełnej informacji ten punkt byłby punktem równowagi Nasha).
2
Gra stochastyczna Innym typem gier, w których modeluje si˛e niepewno´sc´ sa˛ tzw. gry stochastyczne.
Sa˛ to gry podzielone na etapy, w których definiuje si˛e przestrze´n stanów gry, od których zalez˙ a˛ funkcje wypłat graczy. Przej´scia pomi˛edzy stanami odbywaja˛ si˛e po kaz˙ dej sekwencji decyzji graczy. Stan wyj´sciowy jest zmienna˛ losowa,˛ której rozkład zalez˙ y od stanu wej´sciowego i decyzji podj˛etych przez graczy na danym etapie. Procedura powtarza si˛e pewna˛ ilo´sc´ razy (lub nigdy si˛e nie ko´nczy) a wypłata graczy jest suma˛ (lub s´rednia) ˛ wypłat z poszczególnych etapów gry. Je´sli ilo´sc´ graczy, przestrze´n decyzji i stanów sa˛ sko´nczone, gra stochastyczna posiada punkt równowagi Nasha. Gry stochastyczne maja˛ zastosowanie w ekonomii i w biologii (ewolucja).
3
