Zagadnienia

1.1 Uwagi ogólne
1.2 Przykłady Gier

1. Wprowadzenie. Przykłady Gier

1.1. Uwagi ogólne

Teorię gier (TG) można scharakteryzować jako naukę o strategicznym działaniu w warunkach konfliktu i kooperacji.

Jest zbiorem rozważań stosowalnych przez podmioty w sytuacjach strategicznych.

Jest narzędziem ułatwiającym zrozumienie zjawisk i interakcji zachodzących między ludźmi i innymi podmiotami. Jest formalnym, uniwersalnym językiem unifikacji nauk behawioralnych.

Opisuje formalnie sytuacje w których podmioty współzawodniczą lub współpracują.

Jest nauką o powstawaniu, przemianach, dyfuzji (tj. rozprzestrzenianiu się) i ewentualnej stabilizacji różnych form behawioralnych ludzi i innych podmiotów.

W biologii pewne idee i metody TG stały się ważnym teoretycznym narzędziem teorii ewolucji.

W ostatnich dziesięcioleciach obserwujemy sprzężenie zwrotne między teorią gier a biologią, antropologią, socjologią, ekonomią, psychologią, naukami politycznymi, informatyką i innymi gałęziami nauki. Matematyczny aparat i formalizm teorii gier jest stosowany do opisu teorii ewolucji populacji, opisu konkurencji i kooperacji między indywidualnymi osobnikami i grupami, do opisu konfliktów politycznych i społecznych, funkcjonowania rynków finansowych, powstawania i ewolucji instytucji i norm społecznych, do opisu przebiegu procesów ekonomicznych, przekazu informacji w internecie itd.

Podstawowym obiektem w nieformalnym opisie TG jest (podejmujacy decyzje) gracz. W zależności od dziedziny badawczej i/lub kontekstu używamy nazw: agent, osobnik, podmiot, osoba, indywiduum, obiekt etc. Graczem może być grupa, jednostka ekonomiczna czy administracyjna, zwierzę, program komputerowy itp.

W przypadku jednego gracza mamy do czynienia z problemem decyzyjnym.

Interakcja jest to sytuacja (strategiczna sytuacja) w której rezultat decyzji każdego gracza zależy od decyzji (akcji) conajmniej jednego innego gracza (wpp. mielibyśmy zbiór niezależnych problemów decyzyjnych). Jako prosty przykład rozważmy dwie osoby w restauracji. Gdy każda zamawia tylko dla siebie i płaci tylko za siebie, mamy 2 niezależne problemy decyzyjne. Gdy każda zamawia tylko dla siebie a płaci połowę całego rachunku, mamy interakcję którą można sformalizować w postaci gry (tu rezultatem, wynikiem decyzji, akcji obu graczy jest kwota którą każdy gracz płaci).

Istotną rolę będzie odgrywało pojęcie gracz racjonalny. Gracz racjonalny to taki który zna szczegóły interakcji (kto, z kim i w jaką grę gra) i wie że inni też znają szczegóły interakcji i wie że inni wiedzą że on wie że…itd., oraz podejmuje najlepszą (z punktu widzenia preferencji na wynikach) dla siebie decyzję (inaczej - wybiera akcję), i wie ze inni gracze też podejmują takie decyzje (wybieraja takie akcje).

W zależności od kontekstu używa się terminów: zagrać, zagrać (wybrać) akcję, strategię, podjąć decyzję, mieć ruch, wykonać posunięcie, etc.

W ogólności istnieje różnica między pojęciami akcja i strategia, o czym będzie mowa w odpowiednich wykładach. Akcja to decyzja jednorazowa; strategia to plan akcji, który precyzuje jaką decyzje podjąć w każdej możliwej sytuacji w grze.

TG została po raz pierwszy sformalizowana matematycznie w monografii J. von Neumanna, O. Morgensterna, [16]. Literatura w języku angielskim jest bardzo bogata, patrz np. [1, 6, 5, 7, 8, 9, 10, 11, 18, 19, 40, 31, 37, 39]. W języku polskim przykładowe pozycje to [13, 14, 20, 36].

Początkowo zasadniczym żródłem inspiracji dla formalizowania TG była ekonomia. Do około I p. XIX ekonomia była nauka opisową. Pierwsze modele matematyczne to modele duopolu Cournota i Bertranda. W modelach tych zajmowano się problemami równowagi rynkowej (np. podaż - popyt, liczba rąk do pracy - liczba miejsc pracy). Obecnie TG jest stosowana w wielu dyscyplinach nauki, od biologii po nauki polityczne.

Ze względu na specyficzne własności i charakterystyki wyróżniamy wiele typów gier i istnieją różne sposoby ich klasyfikacji. Poniżej przykładowe typy kier i ich klasyfikację ze wzgledu na rózne ich cechy (nie są to wyczerpujące i spójne charakterystyki i klasyfikacje, lecz raczej informacje jakie nazwy, określenia i typy gier spotyka się w bogatej literaturze przedmiotu). Gry można podzielić:

Ze względu na czas (kolejność) podejmowania decyzji:

1. Gry w postaci strategicznej (normalnej)

Opisują sytuacje w których gracze podejmują decyzje jednocześnie, bez wiedzy o decyzjach innych uczestników gry.

2. Gry w postaci ekstensywnej (rozwinętej)

Opisują sytuacje w których gracze podejmują decyzje sekwencyjnie, w kolejnych chwilach czasu, mając określone informacje o decyzjach innych graczy (i swoich) w poprzednich chwilach czasu.
Ze względu na posiadana wiedzę:

1. Gry z kompletną informacją

Są to gry w których gracze mają pełną informację o możliwych wynikach gry (znają funkcje wypłat swoją i innych graczy) i o zbiorach możliwych strategii graczy. W przypadku gier ekstensywnych, gdy gracze oprócz tego w każdej chwili mają pełną informację o poprzednich decyzjach innych graczy i o ewentualnych ich posunięciach losowych, mówimy o grach z pełną informacją.

2. Gry z niekompletną informacją
Ze względu na możliwość tworzenia koalicji

1. Gry kooperacyjne (koalicyjne) - gdy akcje są przypisywane grupom (koalicjom) graczy

2. Gry niekooperacyjne - gdy akcje są przypisywane pojedynczym graczom
Ze względu na liczbę graczy:

Gry dwuosobowe, wieloosobowe nieskończone (w szczególności tzw. ”duże gry”, tzn. gry z continuum graczy).
Ze względu na zbiory dostępnych akcji, strategii:

Gry skończone - gdy zbiór akcji czy strategii każdego gracza jest skończony.

Gry nieskończone. W szczególności wyodrebniamy tu gry z continuum akcji (strategii).
Ze względu na liczbę wykonywalnych akcji

Gry ze skończonym i z nieskończonym horyzontem czasowym.
Ze względu na powtarzalność:

Gry jednokrotne i wielokrotne (iterowane)
Ze względu na ”rolę” czasu:

Gry statyczne i gry ewolucyjne
Inne charakterystyki gier: Gry stochastyczne, gry różniczkowe, gry dynamiczne, gry przeciwko naturze, gry na sieciach.

Nagrody Banku Szwecji im. A. Nobla z ekonomii, związane z teorią gier:

1975 L. Kantorowicz, T. C. Koopmans

1972: K.J. Arrow

1983: G. Debreu

1994: J. Nash, J. Harsanyi, R. Selten

2005: R. Aumann, T. Schelling

2007: L. Hurwicz, E. Maskin, R. Myerson

1.2. Przykłady Gier

Przykład 1.1

Polowanie na Jelenia (Stag Hunt)

2 myśliwych może polować na jelenia lub na zające. Ich decyzje zapadają jednocześnie i niezależnie, tzn. bez wiedzy o decyzji drugiego. Jeleń ma wartość 4, zające po 1. Każdy ma 2 akcje do wyboru: J, Z. Jesli obaj zapolują na jelenia (akcje J) to upoluja go, otrzymujac po 2. Jeśli jeden wybierze J, drugi Z, to pierwszy nic nie upoluje (otrzymuje 0), drugi upoluje zająca (otrzymuje 1). Jeśli obaj wybiora Z, to otrzymuja po 1. Przedstawimy możliwe rezultaty polowania w postaci macierzy wypłat graczy:

i=1:	J	Z
J	2	0
Z	1	1

i=2:	J	Z
J	2	1
Z	0	1

gdzie pierwsza macierz reprezentuje wypłaty gracza nazwanego graczem wierszowym, druga - gracza kolumnowego. Przykładowo: zero w pierwszej macierzy oznacza wypłatę gracza (wierszowego) grającego J, gdy przeciwnik (gracz kolumnowy) gra Z. Jedynka w pierwszym wierszu drugiej macierzy w oznacza wypłate gracza kolumnowego grającego Z gdy przeciwnik (gracz wierszowy) gra J. Nierozróżnialność myśliwych implikuje że jedna macierz jest transponowana do drugiej. Zapis w postaci jednej macierzy:

	J	Z
J	2,2	0,1
Z	1,0	1,1

Zauważmy że gdyby gracze podjęli decyzje (J,J) lub (Z,Z) to żadnemu z nich nie opłaca się JEDNOSTRONNIE (tj. gdy drugi nie zmienia decyzji) zmienić swojej decyzji. Mówimy, na razie nieformalnie, że takie pary akcji, decyzji, strategii czystych ”są w równowadze”, ”tworzą równowagę” (równowagę Nasha w strategiach czystych, patrz następny wykład).

Uwaga: J. J. Rousseau 1712-1779, pisarz, filozof Oświecenia, w traktacie o początku i zasadach nierówności między ludżmi” (1755) opisał nieformalnie tę grę [5].

Oto wolny przekład odpowiedniego fragmentu traktatu:

”…Jeżeli grupa myśliwych poluje na jelenia, to każdy z nich musi być na stanowisku by polowanie zakończyło się sukcesem. je,zeli jednak zając przemknie koło jednego z nich to [nie ma wątpliwości że] ten myśliwy zacznie go gonić nie zważając na to że w ten sposób może dramatycznie obniżyć szanse innych na upolowanie jelenia…”

Więcej o grze Polowanie na Jelenia można przeczytać np. w książce [34].

Przykład 1.2

Gra Dylemat Więźnia (Prisoner's Dilemma)

2 podejrzanych o dokonanie przestępstwa siedzi w areszcie, nie komunikując się między sobą. Śledczy nie ma dostatecznych dowodów by skazać obu, Proponuje każdemu by obciążył drugiego, uzyskując w zamian zwolnienie. Podejrzani mają do wyboru dwie akcje (strategie): C: milczeć, czyli nie obciążać drugiego (kooperacja, Cooperation), i D: obciążyć drugiego (defekcja, Defection), i wybierają jedną z nich jednocześnie i bez komunikacji między sobą. Wybierajac:

(C,C) $\Rightarrow$ każdy dostaje rok więzienia: wynik akcji to po -1 dla każdego

(C,D) i (D, C) $\Rightarrow$ C dostaje 5 lat (wynik -5), D jest zwolniony (wynik 0)

(D,D) $\Rightarrow$ każdy dostaje 3 lata: wynik akcji to po -1 dla każdego

Macierz gry:

	C	D
C	-1,-1	-5,0
D	0,-5	-3,-3

Uwaga: nawet gdyby więżniowie mogli się kontaktować, a nawet uzgodnić przedtem swoje akcje, a nawet gdyby decydowali sekwencyjnie, wynik (D,D) jest jedynym ”racjonalnym” z punktu widzenia indywidualnych interesów każdego z podejrzanych!

Jeżeli za wynik gry (wypłatę) przyjmiemy liczbę lat spędzonych na wolności w czasie 5 lat po zapadnięciu wyroku, to macierz gry ma postać

	C	D
C	4,4	0,5
D	5,0	2,2

Dylemat Więźnia w postaci ogólnej:

	C	D
C	R,R	S,T
D	T,S	P, P

$T>R>P>S.$ T: Temptation, R: Reward, P: Punishment, S: Sucker. Para (D, D) jest (jedyną) równowagą Nasha.

Oto inne przykłady ”tego typu” gry.

* Wspólny projekt.

$s_{i}\in\{ 0,1\},i=1,2$ indykator gracza $i$ : udaje pracę: $s_{i}=0$ , pracuje: $s_{i}=1$ . Jeśli gracz pracował - ponosi koszt 3, nie - 0. Wynik pracy: $2(s_{1}+s_{2})$ dla każdego uczestnika, niezależnie od tego czy pracował czy udawał.

	C	D
C	1, 1	-1, 2
D	2, -1	0, 0

* Dylemat Współpracy

2 mocarstwa A, B muszą niezależnie, bez wiedzy o decyzji drugiego, podjąć decyzję: C - włożyć (zainwestować) $2c>0$ , lub D - nie inwestować. $2c>0$ - koszt wyjścia świata z kryzysu. Jeśli A i B włożyły po $2c>0$ to korzyść (wypłata) każdego: $-2c+c+b=b-c$ . Jeśli A włożyłoby $2c$ a B nic, to A otrzymuje $b-2c$ , B $b$ ; nalogicznie (symetrycznie) B. Jeśli A i B nic nie włożą, to będą miały po $a$ , $0<b-2c<a<b-c<b$ . Macierz gry:

	C	D
C	b-c,b-c	b-2c,b
D	b,b-2c	a,a

Przykład 1.3

Gra Zamieć Śnieżna (Snowdrift)

2 kierowców stoi przed drogą zasypaną przez lawinę. $c>0$ - całkowity nakład energii potrzebny do odśnieżenia drogi , $b>c$ - korzyść każdego gracza z dojechania do domu, $a$ - energia (wypłata) każdego gracza gdy nic nie robią, $b-c>a$ by opłacało sie wracać.

	C	D
C	b-c/2,b-c/2	b-c,b
D	b, b-c	a,a

Na ogół przyjmuje się $a=0$ . Przykład ogólniejszy: $b=5,c=2,a=1$ . W tej grze żaden gracz nie ma tzw. strategii dominującej. Są dwie (”asymetryczne”) równowagi Nasha w strategiach czystych: $(C,D),(D,C)$ .

Oto inny przykłady ”tego typu” gry:

* Dylemat Współpracy II

2 mocarstwa: A, B mają do wyboru akcje: C: włożyć (zainwestować), D - nie inwestować. A musi ”na początku” włożyć $c$ by wyjść z kryzysu (niezależnie od tego co będzie grał B; ”finalna” wypłata B zależy od akcji B!) B: analogicznie (symetrycznie). Jeśli A i B włożą po $c>0$ to dostaną zwrot $c/2$ + zysk $b$ . Jeśli A włoży $c$ a B włoży $0$ , to A otrzymuje $b-c>0$ , B $b$ . Analogicznie B. Jeśli A i B włożą 0, będą miały po kryzysie $a$ , $b-c>a$ . Macierz gry:

	C	D
C	b-c/2,b-c/2	b-c,b
D	b,b-c	a,a

W powyższych przykładach macierz wypłat jednego gracza była transponowaną macierzą wypłat drugiego (symetryczne gry dwuosobowe; ogólna definicja dla szerszej klasy gier będzie podana później). Poniższa gra nie ma już tej własności.

Przykład 1.4

Gra W Monety (Gra Orzeł-Reszka, Matching Pennies)

Dwaj gracze pokazują jednocześnie stronę monety (O lub R). Macierz wypłat:

	O	R
O	1,-1	-1,1
R	-1,1	1,-1

Gry nie mają RN w strategiach czystych (”brak koordynacji”). Są to gry o sumie stałej (w pierwszym przypadku - o sumie zerowej). Intuicyjnie: w przypadku wielokrotnego powtarzania gry, średnia wypłata każdego gracza ze strategii mieszanej polegającej na odkrywaniu każdej ze stron monety z prawdopodobieństwem $1/2$ wynosi 0 dla pierwszej, 0.5 dla drugiej macierzy.

Podobny przykład, w którym brak symetrii gry (formalna definicja będzie podana w nastepnym wykładzie) jest ”bardziej widoczny”:

Przykład 1.5

(Gra W Kota i Myszkę)

Kot goni Myszkę. Każde zwierze ma 2 opcje: skręcić w lewo (L) lub w prawo (P). Macierz wypłat:

	L	P
L	0,2	1,0
P	1,0	0,2

gdzie M jest graczem wierszowym, K - kolumnowym: pierwszy element każdej pary wypłat daje wypłatę M, drugi - K. Gra nie ma RN w strategiach czystych. W przeciwieństwie do poprzedniego przypadku gracze są ”rozróżnialni”.

Przykład 1.6

Gra Walka Płci (Battle of the Sexes)

Kobieta (gracz wierszowy, K) woli boks (Bo), mężczyzna (gracz kolumnowy, M) balet (Ba). Z drugiej strony chcą oglądać wybrane widowisko razem. Macierz wypłat:

	Bo	Ba
Bo	3,2	0,0
Ba	1,1	2,3

Przykład 1.7

Gra Walka Płci - wersja ekstensywna:

Załóżmy że K wybrała Bo i nie może już zmienić decyzji, i dzwoni do M z tymi informacjami. Racjonalny M wybierze Bo. Można narysować postać rozwiniętą tej gry. Uwzględniamy wszystkie scenariusze, np. wybór Ba przez K (np. gdy nie jest pewna pełnej racjonalności M lub gdy jest szansa że M się pomyli).

Przykład 1.8

Gra Kamień-Papier-Nożyczki (Rock-Paper-Scissors)

2 graczy, każdy ma 3 strategie: K, P, N. Macierz wypłat:

	K	P	N
K	0,0	-1,1	1,-1
P	1,-1	0,0	-1,1
N	-1,1	1,-1	0,0

Przykład 1.9

Gra Dobra Publiczne (Public Goods Game, PG)

N graczy. Każdy dostaje po $c(=1)$ do dyspozycji i wkłada tę kwotę (akcja C) lub nie (akcja D) do wspólnej puli. Jeśli zagra D to zatrzymuje $c$ . Gracze nie znają decyzji innych graczy. Pula zostaje zwielokrotniona $r$ razy. Niech $n$ oznacza liczbę graczy którzy zagrali C. KAŻDY z N graczy dostaje $rn/N$ z puli. Niech $P_{C}(n),\ P_{D}(n)$ - finalne stany posiadanie gracza grającego odpowiednio $C,D:$ $P_{C}(n)=nrc/N,\ P_{D}(n)=nrc/N+c.$ Zauważmy że $r<N\Leftrightarrow P_{C}(n)<P_{D}(n-1)$ ; dla $r<N$ zawsze lepiej grać D. PG to gra opisana powyższym scenariuszem, dla której $r<N$ i dodatkowo $P_{C}(N)>P_{D}(0)$ , czyli dla której $1<r<N.$

W szczególności, im większa liczba graczy $N$ tym mniej każdy gracz musi dostać z puli by opisany scenariusz definiował PG.

Przykład 1.11

Gra ”Dylemat Wspólnych Zasobów” (Tragedy of Commons)

N graczy. Jeżeli jest nie więcej niż $M<N$ defektorów to każdy gracz dostaje bonus B. Wypłata defektorów jest zawsze wyższa niż kooperatorów: $T>R$ . Każdy gracz ma lepiej jeśli wszyscy kooperują niż gdy wszyscy zdradzają: $R+B>T$

	$<M$ innych gra D	M innych gra D	$>M$ innych gra D
C	R+B	R + B	R
D	T + B	T	T

W tej grze jest wiele RN w strategiach czystych: totalna defekcja i takie profile gry w których jest dokładnie M defektorów (minimalna efektywna kooperacja). Minimalna efektywna kooperacja jest jedynym profilem Pareto - optymalnym, patr Wykład 3.

Przykład 1.17

Gra Ultimatum (Ultimatum Game)

Jest do podziału 100 PLN między graczy A i B. A proponuje B podział: $x$ dla B, $100-x$ dla A, gdzie $x\in\{ 1,2,...100\}$ są akcjami gracza A. Dla gracza A jego strategie utożsamiamy z akcjami. Gracz B ma dwie akcje : TAK, NIE. Wypłaty: (100 - x, x) lub (0,0). Strategie B (czyli plany jaką akcję podjąć w każdej możliwej sytuacji): wektory 100 elementowe o wyrazach TAK, NIE. Równowaga Nasha: Para strategii: (1, (TAK, TAK, …,TAK)).

Przykład 1.19

Gra Wejście–Odstraszanie (Entry - Deterrence Game)

Posiadasz warsztat o dochodach 2. Obok jest sklep spożywczy o dochodach 5. Jeśli przekształcisz warsztat w drugi sklep to:

a. jeśli pierwszy sklep zareaguje agresywnie (wojna cen) to dochody obu będa po 1.

b. jeśli pokojowo (podział rynku) to dochody obu będa po 3.

Jeśli nie przekształcisz warsztatu w sklep to wasze dochody nie ulegną zmianie.

Przykład 1.20

Gra Stonoga (Centipede Game)

2 graczy A i B, mają na kontach po 0 PLN. A otrzymuje ofertę przyjęcia 1 PLN. Jeśli przyjmie (akcja T), to gra się kończy i A ma 1, B 0, użyjemy notacji (1,0) na oznaczenie wyniku.

Jeśli nie (akcja N), to B otrzymuje ofertę $10^{1}$ PLN. Jeśli B zagra T to gra się kończy z wynikiem (0,10).

Jeśli N to A otrzymuje oferte $10^{2}$ PLN. Jeśli A zagra T to gra się kończy z wynikiem $(10^{2},0)$ .

Jeśli N to B otrzymuje oferte $10^{3}$ PLN. Jeśli B zagra T to gra się kończy z wynikiem $(0,10^{3})$ .

Jeśli N to A otrzymuje oferte $10^{4}$ PLN. Jeśli A zagra T to gra się kończy z wynikiem $(10^{4},0)$ .

Jeśli N to B otrzymuje oferte $10^{5}$ PLN. Jeśli B zagra T to gra się kończy z wynikiem $(0,10^{5})$ .

Jeśli N to gra się kończy i nikt nic nie dostaje.

Przykład 1.21

Gra Podział Dolara.

Do podziału jest 1 $. N=3 gracze moga tworzyć koalicje (niepuste podzbiory zbioru graczy) proponując partnerom koalicji pewien podział 1 $. Podział następuje (gra się kończy) gdy conajmniej 2 graczy go zaakceptuje i żaden z 3 graczy nie zaproponuje innego podziału, który by zmienił decyzję conajmniej jednego z tych 2 graczy, którzy zaakceptowali podział. Każdy chce dostać jak największą część z 1 $ i nie jest związany w żaden sposób z pozostałymi graczy.

Ćwiczenie 1.4

Gra W Tchórza (Chicken Game)

2 osoby stoją po przeciwnej stronie kładki przez rzekę. Przez kładkę może przejść tylko jedna osoba. Mają do wyboru 2 strategie: A(gresywna) - wejść na kładkę, P(okojowa) - nie wejść (czekając aż druga przejdzie). Jeśli obie wejdą (grają A) to żadna nie przejdzie, obie ucierpią w wyniku zderzenia oraz spóźnią się do pracy - wypłaty po -1, jeśli wybiorą przeciwne strategie to wybierający A dostaje 2, a P dostaje 1 (A będzie wcześniej w pracy), jeśli obie grają P, to spóżnią się do pracy - dostają po 0. Macierz gry:

	A	P
A	-1,-1	2,1
P	1,2	0,0

Czyste RN: (A,P), (P,A). Ogólna postać tej gry:

	A	P
A	a,a	b,c
P	c,b	d,d

$b>a,c>a,d<b$ . Czyste RN: (A,P), (P,A).

Ćwiczenie 1.5

3-osobowy PD: każdy z 3 graczy ma 2 akcje: C lub D.

$(C,C,C)\Rightarrow(R,R,R)$ , $(D,D,D)\Rightarrow(P,P,P),$

$(C,D,D)\Rightarrow(S,P^{{\prime}},P^{{\prime}}),(C,C,D)\Rightarrow(R^{{\prime}},R^{{\prime}},T),\ T>R>P>S,\ T>P^{{\prime}}>P,\ R>R^{{\prime}}.$ Jedyna równowaga Nasha to (D, D, D).

Ćwiczenie 1.6

3-osobowa Gra Zamieć Śnieżna

Praca wymagana do odśnieżenia: c. Wypłaty: $(CCC):(b-c/3,b-c/3,b-c/3),(CCD):(b-c/2,b-c/2,b)$ , $(CDD):(b-c,b,b),(DDD):(c/3,c/3,c/3)$ (defektorzy zachowują energię). Jedyna czysta RN: $(DDD)$ . Rozważyć modyfikację: $(DDD)-(0,0,0)$ . Są wtedy 3 RN czyste.

Ćwiczenie 1.7

3-osobowa Gra na Mniejszość (Minority Game)

3 graczy wybiera jednocześnie jedną z opcji: A lub B. Wygrywa gracz który jest w mniejszości.

Macierz gry - 3 ”kostki gry”. Można zróżnicować wyniki (wypłaty) w zależności czy się wybrało opcję tę samą co 1 czy 2 pozostali gracze. Uogólnienie - $2k+1$ - osobowa gra na mniejszość.

Ćwiczenie 1.8

Dylemat podróżnika (Traveller's Dilemma)

Linia lotnicza zgubiła 2 identyczne walizki, należące do 2 podróżnych. Linia oferuje odszkodowanie, ale nie większe niż $K$ $. Podróżni proszeni są niezależnie od siebie o napisanie kwoty jakiej oczekują jako odszkodowanie, nie mniejszej niż $2$ $ i nie większej niż $K$ $. Jeśli napiszą taką samą kwotę, obaj otrzymają odszkodowanie tej wysokości, jeśli różne, to zostanie uznana niższa kwota i ten kto napisze niższą kwotę, dostanie dodatkowo $2$ $, a drugi straci $2$ $ ze swojego odszkodowania.

Dla $K=3$ $ gra jest dylematem więźnia. Dylemat podróżnika jest uogólnieniem DW.

Jeśli przewidujemy że przeciwnik napisze wartość K $, najbardziej opłaca nam się napisać $K-1$ $. Nasza nagroda wyniesie wtedy $K+1$ $. Jeśli jednak przeciwnik przewidzi, że będziemy chcieli napisać $K-1$ $, sam napisze $K-2$ $ (jego nagroda wyniesie wtedy $K$ $, a nasza $K-4$ $ itd. Napisanie kwoty $2$ $ jest więc strategią dominującą. Jedyna RN to para $(2,2)$ $.

Ćwiczenie 1.9

Gra Banacha (Stanisław Mazur, 1935)

2 graczy, $A\subseteq[0,1]$ -ustalony. Gracz 1-y wybiera cyfrę $a_{1}$ , 2-i $a_{2}$ , 1-y $a_{3}$ itd w nieskończoność. Powstaje rozwinięcie dziesiętne $x=0.a_{1}a_{2}a_{3}...$ . jeśli $x\in A$ to wygrywa 1-y, wpp 2-i. Podaj przykłady strategii wygrywających dla różnych $A$ .

Nazwijmy $A\subseteq[0,1]$ zbiorem zdeterminowanym jeżeli 1-y lub 2-i gracz ma strategię wygrywającą. Wiele ”spotykanych na codzień” podzbiorów $[0,1]$ jest zdeterminowanych. Pewnik wyboru implikuje istnienie zbiorów niezdeterminowanych. Jest to gra ekstensywna z nieskończonym horyzontem czasowym. Szerzej o pewnych związkach pomiędzy teorią mnogości a TG - patrz np. rozdz. 40 w [14].

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Wstęp do Teorii Gier