TEORIA_GIER.pdf

TEORIAGIER-notatki

PawełPo«sko

4marca2010

Notatki pomy±lane s¡ jako ±ci¡gawka dla studentów i maj¡ za zadanie ewo-

luowa¢ wraz z wykładem.

1Wprowadzenie

Deﬁnicja 1 Gra strategiczna : sytuacja, gdzie dwie lub wi¦cej osób podejmuje

decyzje, które wpływaj¡ na sytuacj¦ innych.

Deﬁnicja 2 Strategiczna współzale»no±¢ : decyzje i akcje podejmowane przez

osoby maj¡ wpływ na decyzje innych i w zwi¡zku z tym s¡ od siebie zale»ne.

Deﬁnicja 3 Gracze : Uczestnicy gry strategicznej, których celem jest maksy-

malizacja wypłat za pomoc¡ racjonalnego wyboru akcji.

To oznacza, »e mamy niepusty, sko«czony zbiór graczy N h 1 , 2 ,...,n i

(zawieraj¡cy n elementów (graczy)). Je»eli gracz i bierze udział w grze,

powiemy, »e i 2 N.

Deﬁnicja 4 Natura : Pseudo uczestnik gry strategicznej, który, we wskazanych

momentach gry, losowo wybiera akcje oparte na znanym rozkładzie prawdopo-

dobie«stwa.

Deﬁnicja 5 Akcja : Akcj¡ a i dla gracza i jest wybór, którego mo»e dokona¢ w

czasie gry.

SzkołaGłównaHandlowa, Katedra Ekonomii Matematycznej; email: Pa-

wel.Ponsko@sgh.waw.pl

To oznacza, »e deﬁniujemy zbiór akcji A i = h a i i dla gracza i zawieraj¡cy

wszystkie jego akcje dost¦pne w grze.

Ponadto, deﬁniujemy proﬁl akcji , który jest list¡ a = h a i i , gdzie ( i =

1 ,...,n ) , zawieraj¡c¡ po jednej akcji dla ka»dego z n graczy w grze.

Deﬁnicja 6 Zbiór informacji : wiedza gracza na temat zmiennych w grze w

danym momencie gry. (zbiór informacji zmienia si¦ wraz z wydarzeniami w

grze)

Deﬁnicja 7 Strategia(1) : kompletny plan akcji dla całej gry.

Strategia(2) : Strategia s i dla gracza i jest reguł¡, która mówi mu, któr¡

akcj¦ wybra¢ w ka»dym momencie gry (bior¡c pod uwag¦ jego zbiór informacji).

To oznacza, »e deﬁniujemy zbiór strategii S i = h s i i dla gracza i zawiera-

j¡cy wszystkie jego strategie dost¦pne w grze.

Ponadto, deﬁniujemy proﬁl strategii , który jest list¡ s = h s i i , gdzie ( i =

1 ,...,n ) , zawieraj¡c¡ po jednej strategii dla ka»dego z n graczy w grze.

Uwaga: Nale»y pami¦ta¢, »e strategia to jest kompletny plan akcji dla gracza.

Je»eli np. gracz uzna, »e nale»y popełni¢ samobójstwo w połowie gry, strategia

zawiera akcje, które wybrałby w nast¦pnych ruchach, mimo, »e ju» ﬁzycznie w

grze nie uczestniczy. Dlatego czasem mówi si¦, »e akcja jest realn¡ cz¦±ci¡ gry

(faktycznie j¡ si¦ gra) natomiast strategia jest tylko wyobra»ana. Szkopuł w tym,

»e to wła±nie strategie s¡ nam potrzebne do odnalezienia równowagi.

Deﬁnicja 8 Wynik gry to zbiór strategii, które zostały u»yte w grze.

Uwaga: Równowaga Nasha jest szczególnym wynikiem gry, takim gdzie gracze

skorzystali ze swoich najlepszych odpowiedzi .

Deﬁnicja 9 Wypłaty(1) : U»yteczno±¢ (zysk, etc.), któr¡ otrzymuje gracz w

mo»liwym wyniku gry.

Wypłaty(2) : Poprzez wypłat¦ i ( s i ,...,s n ) rozumiemy:

U»yteczno±¢ (zysk, etc.), któr¡ otrzymuje gracz i po tym jak wszyscy gracze

(wł¡czaj¡c w to Natur¦, je±li bierze udział w grze) wybrali swoje strategie

i gra została zako«czona. lub:

Oczekiwan¡ u»yteczno±¢ (zysk, etc.) jak¡ otrzymuje gracz i jako funkcj¦

strategii wybranych przez gracza i oraz innych graczy − i w grze.

Uwaga: W deﬁnicji (2) oba punkty nie oznaczaj¡ dokładnie tego samego. Za-

zwyczaj jednak funkcji wypłat u»ywa sie do oznaczenia obu wy»ej wymienionych

rzeczy. Rozwi¡zuj¡c gry b¦dzie oczywiste, z której deﬁnicji wypłat korzystamy.

Deﬁnicja 10 Racjonalno±¢ : gracze wybieraj¡ strategie tak, by zmaksymalizo-

wa¢ swoj¡ wypłat¦ na ko«cu gry.

Deﬁnicja 11 Strategia równowagi = Najlepsza odpowied¹ : Strategia wy-

brana przez racjonalnego gracza, czyli taka, która daje graczowi najwy»sz¡ wy-

płat¦ bior¡c pod uwag¦ strategie grane przez innych graczy.

Deﬁnicja 12 Równowaga strategiczna(1) : kombinacja strategii, które s¡

najlepszymi odpowiedziami dla wszystkich graczy.

Równowaga strategiczna(2) : Równowag¡ s = ( s 1 ,...,s n ) jest proﬁl stra-

tegii zawieraj¡cy najlepsze odpowiedzi dla ka»dego z n graczy w grze.

Czasami w grach deﬁniujemy poj¦cie rozwi¡zania gry. Zamieszam je tutaj,

aby pami¦ta¢, »e równowaga Nasha to nie to samo co wypłaty, które otrzymuj¡

gracze w równowadze Nasha.

Deﬁnicja 13 Rozwi¡zanie gry : to reguła F : h S 1 ,...,S n , 1 ,..., n i ! s ,

która deﬁniuje równowag¦ na podstawie mo»liwych kombinacji strategii i funkcji

wypłat.

Potrzebujemy rozszerzy¢ notacj¦ graczy. Dla gracza i 2 N , istnieje zawsze

gracz (b¡d¹ gracze) − i 2 N równie» bior¡cy udział w grze, którzy nie s¡ graczem

i . Innymi słowy za pomoc¡ − i oznaczamy wszystkich innych graczy w grze poza

i .

Deﬁnicja 14 Strategia równowagi = Najlepsza odpowied¹ (2) : Najlepsza

odpowied¹ gracza i wzgl¦dem strategii s − i wybranych przez innych graczy, jest

strategia s i , która daje mu najwy»sze wypłaty, to znaczy:

i ( s i ,s − i ) i ( s 0 i ,s − i ) , 8 s 0 i 6 = s − i

2Dominuj¡ceizdominowanestrategie

Deﬁnicja 15 Strategia dominuj¡ca (1) : W grze, gdzie mamy dwóch gra-

czy, wypłaty dla gracza, który korzysta ze ±ci±le dominuj¡cej strategii s¡ wy»sze

ni» wypłaty z ka»dej innej strategii dost¦pnej dla tego gracza, w odpowiedzi na

jak¡kolwiek strategi¦ drugiego gracza.

Strategia dominuj¡ca (2) : Strategia s i jest strategi¡ dominuj¡c¡ dla gra-

cza i je±li jest jego najlepsz¡ odpowiedzi¡ na jak¡kolwiek strategi¦ drugiego gra-

cza, w takim sensie, »e jak¡kolwiek strategi¦ gracz − i by nie wybrał, s i daje

graczowi i najwy»sze wypłaty.

i ( s i ,s − i ) > i ( s 0 i ,s − i ) , 8 s − i , 8 s 0 i 6 = s i

Deﬁnicja 16 Strategia słabo dominuj¡ca (1) : W grze, gdzie mamy dwóch

graczy, wypłaty dla gracza, który korzysta ze słabo dominuj¡cej strategii s¡

(i) przynajmniej tak samo wysokie jak wypłaty z ka»dej innej strategii do-

st¦pnej dla tego gracza, w odpowiedzi na jak¡kolwiek strategi¦ wybran¡ przez

drugiego gracza.

(ii) wy»sze ni» wypłaty z innych dost¦pnych mu strategii w odpowiedzi na

przynajmniej jedn¡ strategi¦ drugiego gracza.

Strategia słabo dominuj¡ca (2) : Strategia s i jest strategi¡ słabo domi-

nuj¡c¡ dla gracza i je±li jest jego najlepsz¡ odpowiedzi¡ na jak¡kolwiek strategi¦

drugiego gracza, w takim sensie, »e jak¡kolwiek strategi¦ gracz − i by nie wybrał,

s i daje graczowi i co najmniej tak samo wysokie wypłaty jak ka»da inna jego

strategia oraz ostro wy»sze wypłaty w odpowiedzi na przynajmniej jedn¡ strategi¦

gracza − i.

i ( s i ,s − i ) i ( s 0 i ,s − i ) , 8 s − i , 8 s 0 i 6 = s i ,

gdzie przynajmniej w jednym przypadku ta nierówno±¢ jest ostra.

Deﬁnicja 17 Równowaga w strategiach dominuj¡cych (1) : Kombinacja

strategii dominuj¡cych (po jednej dla ka»dego gracza). W grze dwuosobowej:

para strategii (po jednej dla ka»dego gracza), które przynosz¡ najwy»sze wypłaty

w odpowiedzi na wszystkie strategie drugiego gracza.

Równowaga w strategiach dominuj¡cych (2) : Proﬁl strategii zawiera-

j¡cy dominuj¡c¡ strategi¦ dla ka»dego z graczy.

Deﬁnicja 18 Równowaga w strategiach słabo dominuj¡cych : Kombina-

cja strategii dominuj¡cych (po jednej dla ka»dego gracza), gdzie niektóre lub

wszystkie strategie s¡ tylko słabo dominuj¡ce.

Deﬁnicja 19 Strategia zdominowana : Strategia s d i jest strategi¡ zdomino-

wan¡ je±li jest ostro gorsza od jakiej± innej strategii niezale»nie od tego jakie

strategie zagraj¡ inni gracze, w takim sensie, »e niezale»nie jakie strategie za-

graj¡ gracze − i, wypłaty dla gracza i s¡ ni»sze, gdy gra s d i . Formalnie, s d i jest

zdominowana je±li istnieje przynajmniej jedna taka strategia s 0 i , »e:

i ( s d i ,s − i ) < i ( s 0 i ,s − i ) , 8 s − i

Deﬁnicja 20 Równowaga iteracyjna : Równowaga znaleziona poprzez usu-

wanie zdominowanych lub słabo zdominowanych strategii a» do momentu, gdy

pozostaje para strategii (po jednej dla ka»dego gracza).

Deﬁnicja 21 RÓWNOWAGA NASHA : Kombinacja strategii (po jednej

dla ka»dego gracza), które s¡ najlepszymi odpowiedziami dla siebie.

Deﬁnicja 22 RÓWNOWAGA NASHA : Sytuacja, w której ka»dy gracz robi

to, co najlepsze dla siebie bior¡c pod uwag¦ to, co robi¡ inni gracze.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: