Teoria gier. Podstawy matematyczne - ebook

WSTĘP

Streszczenie

Teoria gier jest dziedziną matematyki zajmującą się decyzjami interaktywnymi. Z jednej strony tworzy modele reprezentujące sytuacje, w których kilka podmiotów, zwanych graczami, dokonuje wyborów, zaś zbiór wszystkich tych indywidualnych zachowań determinuje pewien wynik, mający z kolei wpływ na każdego z nich. Z drugiej strony, skoro gracze mogą dokonywać w różny sposób oceny możliwych wyników, teoria gier bada również racjonalne zachowanie w tak wytyczonych ramach. Najlepiej ugruntowany paradygmat zdefiniowany jest przez zakres, zarysowany jako rozdźwięk między konfliktem a współpracą.

Pierwsza analiza matematyczna prowadząca w tym kierunku pochodzi z XVIII wieku, dotyczy prawdopodobieństwa wygranej w grze w karty, w miarę rozwoju gry (Montmort ). Podstawy teorii gier pojawiły się jednak dopiero na początku XX wieku wraz z pracami: Zermelo , który analizował gry skończone o pełnej informacji; Borela , który badał strategie i informacje oraz von Neumanna , który opracował regułę minimaksu. Pracą przełomową okazała się książka „Theory of Games and Economic Behavior” (1944), której współautorami byli matematyk von Neumann i ekonomista Morgenstern. Zawiera ona formalne opisy kilkunastu rodzajów gier wraz z podstawowymi zasadami samej teorii gier. Kolejny krok w rozwoju teorii gier został osiągnięty około 1950 r. dzięki pracom Johna Nasha dotyczącym definicji i istnienia „równowagi strategicznej” (zwanej równowagą Nasha) – stanowiło to między innymi uogólnienie prac Cournota .

Od tego czasu teoria gier rozwinęła się w wielu kierunkach, między innymi w zakresie badania gier z nieskończonym zbiorem strategii, gier z kontinuum graczy, dynamicznych, różniczkowch, o niepełnej informacji i stochastycznych. Poczyniono liczne postępy koncepcyjne: doskonalenie / selekcja równowag, pojawiły się nowe koncepcje rozwiązań, takie jak: równowagi skorelowane, jednolite własności interakcji powtarzanych, procedury uczenia i in. Zastosowano w tym celu liczne narzędzia matematyczne, takie jak analiza wypukła i funkcjonalna, optymalizacja, procesy stochastyczne, rzeczywista geometria algebraiczna, topologia algebraiczna, teoria punktu stałego, systemy dynamiczne. Teoria gier jest stosowana z powodzeniem w wielu dyscyplinach nauki, przede wszystkim w ekonomii, biologii i informatyce, ale również w badaniach operacyjnych, naukach politycznych, a także w innych obszarach matematyki (logika, opisowa teoria mnogości, gry kombinatoryczne etc.).

Teoria gier miała ogromny wpływ na ekonomię, a kilku teoretyków gier otrzymało nagrodę Nobla z dziedziny ekonomii: Harsanyi, Nash i Stelten w 1994 r.; Aumann i Schelling w 2005 r., w 2007 r. Hurwicz, Maskin i Myerson, a Roth i Shapley w roku 2012. Można tu również wspomnieć Tirole (2014), a także Harta i Holmstroma (2016), którzy używali narzędzi z zakresu teorii gier i przyczynili się do ich rozwoju. Zasadniczo wiele kwestii dotyczących organizacji przemysłu i teorii aukcji zawiera aspekty z dziedziny teorii gier. Celem jest zazwyczaj analiza zachowań racjonalnego podmiotu działającego w środowisku podobnych sobie uczestników tak, by wziął pod uwagę idiosynkratyczne aspekty informacji .

Zastosowanie teorii gier w biologii, zapoczątkowane przez Maynarda Smitha , przyczyniło się do wielu przełomowych odkryć – zarówno koncepcji np. „ESS” (strategie stabilne ewolucyjnie, ang. evolutionary stable strategies), jak i narzędzi matematycznych, w szczególności wykorzystanie systemów dynamicznych. Fascynującym wyzwaniem badawczym jest zrozumienie podobieństw między rezultatami wygenerowanymi przez mechanizmy krótkowzroczne (np. oparte na sprawności organizmu i nieczyniące żadnych założeń co do właściwości środowiska) oraz przez racjonalne wnioskowanie przeprowadzone przez inteligentnych i wysublimowanych graczy.

Niedawno opracowanym i prężnie rozwijającym się obszarem badań są interakcje między teorią gier a informatyką. Dziedzina ta wypracowała nawet nową terminologię „algorytmicznej teorii gier”. Za to osiągnięcie Daskalakis otrzymał Nagrodę Nevanlinny (ICM 2018). Bardzo ciekawe pytania powstają w związku ze złożonością konstrukcji wydajnych ram dla interakcji strategicznych (algorytmiczne projektowanie mechanizmów), złożoności obliczeniowej problemu znalezienia równowagi lub też złożoności samej równowagi (jako implementowanej przez automat).

Od czasu prac von Neumanna i Morgensterna gry klasyfikowano według dwóch kategorii: strategiczne (lub niekooperacyjne) oraz koalicyjne (albo kooperacyjne). W tej książce będziemy się zajmowali tymi pierwszymi, dzięki czemu możemy zaoferować jednolitą ich reprezentację z użyciem różnorakich narzędzi matematycznych. Najprostszym sposobem reprezentacji modelu jest wyjaśnienie explicite „reguł gry”, tak jak ma to miejsce w pokerze czy w szachach: który gracz zagrywa i kiedy, jakie informacje otrzymuje on w czasie rozgrywki, jakim dysponuje zbiorem wyborów i jakie są konsekwencje zagrań aż do ostatecznego wyniku. To odpowiada tak zwanej „postaci ekstensywnej” gry, która pozwala na wprowadzenie pojęcia strategii dla każdego z graczy jako specyfikacji zachowania gracza w każdym momencie, w którym może i musi dokonać wyboru. Strategia jest zatem programem komputerowym lub algorytmem, tj. zbiorem instrukcji pozwalającym na rozgrywanie gry w każdym możliwym scenariuszu. W sposób oczywisty na mocy tej konstrukcji, jeśli każdy z graczy wybierze tak pojętą strategię, powstanie rozgrywka i w rezultacie otrzymamy określony wynik.

Na powyższą sytuację można spojrzeć bardziej abstrakcyjnie, poprzez wprowadzenie zbioru strategii każdego gracza oraz odwzorowania, które by powiązało każdy profil strategii (po jednym dla gracza) z wynikiem odpowiadającym wytworzonej rozgrywce. Wynik ten determinuje wreszcie wypłatę odpowiadającą ewaluacji danego gracza. To odpowiada „postaci normalnej” gry. Zarówno postać ekstensywna, jak i normalna modelują strategiczne zachowanie agentów. Postać ekstensywna jest łatwiejsza w opracowaniu i zazwyczaj prowadzi do mniej złożonych obliczeń. Zaletą postaci normalnej jest to, że prezentuje ona prostą i jednolitą konstrukcję matematyczną: gra n-osobowa jest zasadniczo reprezentowana jako odwzorowanie z iloczynu n przestrzeni do ℝn.

Gdy sytuacja interakcji decyzyjnej zostanie już opisana jako gra (identyfikacja graczy, specyfikacja strategii, określenie wyników, obliczenie wypłat), rozważyć należy to, co składa się na „racjonalne” zachowanie w tak określonych ramach. Analiza ta składa się z dwóch części:

– pierwsza część jest konceptualna i polega na definiowaniu obiektów matematycznych lub pomysłów rozwiązań biorących pod uwagę fakt, że gracze dokonują wyborów, posiadają określone preferencje oraz dysponują pewną wiedzą albo obserwacjami na temat gry lub preferencji czy wyborów innych graczy. Ma to na celu rozszerzenie zachowania pojedynczego agenta maksymalizującego swoją użyteczność do sytuacji interaktywnych. Podstawowymi przykładami są pojęcia wartości gry dwuosobowej o sumie zerowej i równowagi gier n-osobowych, a także analizy powstawania przekonań i procedury uczenia się;

– druga część polega na studiowaniu własności tak zdefiniowanych obiektów pod względem istnienia i zależności poszczególnych parametrów, algorytmów je obliczających lub procedur uczenia się dążących do nich, alternatywnych reprezentacji, rozszerzeń do ram bardziej ogólnych itd. Stanowić to będzie zadanie przewodnie tego tomu. Główne wyniki dotyczące wartości i równowag uzyskane zostaną poprzez analizę postaci normalnych gier. Postaci ekstensywnej będziemy używać do analiz gier wieloetapowych oraz do ulepszeń równowag.

Podsumowując, celem tej książki jest dostarczenie krótkiej, lecz wszechstronnej prezentacji najistotniejszych aspektów matematycznych gier strategicznych. Oznacza to zarówno prezentację ogólnych ram i pojęć podstawowych, jak i dostarczenie kompletnych dowodów głównych wyników.

Pozwoli to początkującym na ogólne rozeznanie w podstawowych osiągnięciach dziedziny. Czytelnicy wyposażeni zostaną w wiedzę i narzędzia potrzebne do kontynuacji badań: zarówno w zakresie zastosowań w ekonomii, biologii czy informatyce, jak i w obszarze zaawansowanych zagadnień teorii gier, takich jak: gry dynamiczne, gry średniego pola, uczenie strategiczne i powiązania tegoż z algorytmami sieciowymi.

Podsumowanie książki

Rozdział 1. jest poświęcony ogólnemu wprowadzeniu do interakcji strategicznych. Na kilku przykładach (dopasowanie, targowanie się, aukcje, głosowanie, ewolucja, powtarzanie itd.) pokazujemy różnorodność analizowanych sytuacji i rodzaje napotykanych w czasie analizy problemów. Wprowadzamy formalną definicję gry, notację i podstawowe pojęcia.

Następnie rozważamy gry o sumie zerowej w postaci normalnej (rozdziały 2. i 3.). Modelują one czystą konkurencję między dwoma graczami o przeciwstawnych interesach w sposób następujący: przy danej funkcji o wartościach rzeczywistych g zdefiniowanej na iloczynie zbiorów strategii S × T, gracz 1. kontroluje pierwszą zmienną i dąży do maksymalizacji g, podczas gdy gracz 2. kontroluje drugą zmienną i dąży do minimalizacji g. Właściwe koncepcje rozwiązań to pojęcia wartości oraz strategii optymalnych.

W rozdziale 2. analizujemy skończone gry o sumie zerowej, gdzie zbiór strategii jest skończony. Dowodzimy twierdzenia o minimaksie (regułę minimaksu) von Neumanna głoszące, że jeśli gra rozgrywa się ze strategiami mieszanymi (rozkładem prawdopodobieństwa na strategiach), to jej wartość istnieje, jak również istnieje optymalna strategia mieszana dla każdego z graczy. Następnie rozważamy rozszerzenia reguły, takie jak twierdzenie Loomisa czy twierdzenie Ville’a. Na końcu przestawiamy studium zbieżności procesu „gry fikcyjnej”, gdzie gra początkowa jest powtarzana, zaś na każdym etapie gracze zagrywają najlepszą odpowiedź na średnią strategii granych przez ich przeciwników w przeszłości.

W rozdziale 3. jest rozważany przypadek ogólny gier o sumie zerowej. Dowodzimy w nim różnych twierdzeń o minimaksie. Punktem wyjścia jest twierdzenie Siona z geometrycznymi i topologicznymi założeniami na temat gry: zwarte i wypukłe zbiory strategii oraz funkcje wypłat quasi-wklęsłe półciągłe z góry na pierwszej zmiennej oraz quasi-wypukłe półciągłe z dołu na drugiej zmiennej. Następnie dowodzimy standardowych twierdzeń o minimaksie dla mieszanych strategii dla mierzalnych i ograniczonych funkcji wypłat. Rozszerzamy twierdzenie von Neumanna pod warunkami topologicznymi: strategie tworzące zwarte zbiory Hausdorffa oraz funkcje wypłat półciągłe z góry na pierwszej zmiennej i półciągłe z dołu na drugiej zmiennej. Rozdział zakończymy wprowadzając operator wartości oraz pojęcie gry pochodnej, odgrywające kluczową rolę w podejściu operatorowym do gier powtarzanych.

Rozdział 4. traktuje o grach N-osobowych (o sumie ogólnej). Każdy z graczy i = 1, …, N posiada własną funkcję wypłat g i zdefiniowaną na iloczynie zbiorów strategii S = S¹ × … × Sn oraz kontroluje i-tą zmienną w Si. Wprowadzamy standardowe pojęcia najlepszej odpowiedzi, słabej i ścisłej dominacji. Następnie definiujemy pojęcie strategii racjonalizowalnych i dowodzimy twierdzenia o istnieniu (Bernheim i Pearce). W dalszej kolejności wprowadzamy centralne pojęcie (ε-)równowagi Nasha. Istnienie równowagi Nasha w strategiach mieszanych w grach skończonych dowodzimy przy użyciu twierdzenia Brouwera o punkcie stałym. Podrozdział 4.7. traktuje o uogólnieniach gier ciągłych. Istnienie równowagi dowiedzione zostaje pod pewnymi topologicznymi i geometrycznymi warunkami dla gier zwartych, ciągłych i quasi-wklęsłych, zaś istnienie równowagi mieszanej wykazujemy pod warunkami topologicznymi. Następnie prezentujemy charakterystykę i jedyność równowagi Nasha dla gier regularnych, gdzie zbiory strategii są wypukłymi podzbiorami przestrzeni Hilberta. Podrozdział 4.8. traktuje o równowagach Nasha i przybliżonych w grach nieciągłych, przede wszystkim zaś prezentuje analizę Reny’ego bezpieczeństwa lepszej odpowiedzi. W podrozdz. 4.9. wyjaśniamy, że zbiór mieszanych równowag Nasha gier skończonych jest semi-algebraiczny i definiujemy składowe Nasha dla danej gry. Na końcu, w podrozdz. 4.10. omawiamy kilka dalszych pojęć (wypłaty wykonalne, poziom kary, punkt groźby, punkt centralny, zachowanie Nasha kontra zachowanie ostrożne, wiedza ogólnie dostępna danej gry), zaś w podrozdz. 4.11. dowodzimy standardowych twierdzeń o punktach stałych Brouwera (poprzez lemat Spernera) oraz Kakutani (dla wielowartościowych odwzorowań ze zwartego wypukłego podzbioru znormalizowanej przestrzeni wektorowej w siebie samą).

W rozdziale 5. są opisane gry wklęsłe, gry potencjalne, gry populacyjne i równowagi Nasha / Wardropa. Wprowadzamy również charakterystykę równowag poprzez nierówności wariacyjne. Następnie przedstawiamy analizę rozmaitości równowag, gdzie zbiory strategii są ustalone, zaś funkcje wypłat są zmienne. Udowodnimy twierdzenie Kohlberga i Mertensa, a następnie wykażemy, że każda gra posiada istotne składowe równowag Nasha i że dla generycznych wypłat zbiór mieszanych równowag jest skończony, zaś jego liczba kardynalna – nieparzysta. Wprowadzamy również pola wektorowe Nasha i dynamiki gier, takie jak dynamiki replikatora, dynamika Smitha, dynamika najlepszej odpowiedzi oraz dynamiki Browna-von Neumanna-Nasha. Rozdział 5. jest zakończony analizą strategii stabilnych ewolucyjnie i ich powiązań z dynamikami replikatora.

Rozdział 6. traktuje o grach w postaci ekstensywnej. Jest w nim przedstawiony explicite rozwój interakcji poprzez precyzyjny opis tego, który gracz kiedy zagrywa, jakie są wykonalne akcje i jakie informacje dostępne są każdemu z graczy w czasie podejmowania decyzji. Na początku omawiamy gry o pełnej informacji (takie jak szachy) i dowodzimy twierdzenie Zermela dla gier skończonych. Rozważamy później gry nieskończone w duchu Gale-Stewarda: wykazujemy, że gry otwarte są zdeterminowane i że przy użyciu aksjomatu wyboru istnieje gra niezdeterminowana. Następnie wprowadzamy gry z informacją niepełną i dowodzimy twierdzenie Kuhna mówiące, że mieszane i behawioralne strategie są dla gier z pamięcią doskonałą równoważne sobie. Prezentujemy standardową charakterystykę równowag Nasha w strategiach behawioralnych i wprowadzamy podstawowe ulepszenia równowag Nasha w grach w postaci ekstensywnej: doskonałość w podgrach, równowagi doskonałe w sensie Bayesa oraz sekwencyjne, narzucające racjonalne zachowanie nie tylko na ścieżce równowagi, ale i poza nią. Dowodzimy również istnienia równowagi sekwencyjnej (Kreps i Wilson). Dla gier w postaci normalnej, tak jak w rozdziale 4., wprowadzamy standardowe ulepszenia równowag Nasha: równowagę doskonałą (Selten) oraz równowagę właściwą (Myerson). Dowodzimy, że równowaga właściwa gry w postaci normalnej G wywołuje równowagę sekwencyjną w każdej grze w postaci ekstensywnej z pamięcią doskonałą, która ma G jako swoją postać normalną. Na końcu omawiamy indukcję w przód i stabilność (Kohlberg i Mertens).

Rozdział 7. rozpoczynamy wprowadzeniem pojęcia równowagi skorelowanej, które zawdzięczamy Aumannowi. Jest to rozszerzenie równowagi Nasha o własnościach interesujących z punktu widzenia strategicznego, geometrycznego i dynamicznego. W ramach pojęciowych procedur uczących się wprowadzamy procedury pozbawione żalu (ang. no-regret procedures) oraz strategie skalibrowane, dowodzimy również odpowiednio ich istnienia. Następnie wykazujemy, że w grach powtarzanych: (1) jeśli gracz i podąża za strategią pozbawioną żalu zewnętrznego, empiryczny rozkład ruchów jest zbieżny niemal z pewnością do odpowiadającego zbioru Hannana dla i oraz że (2) jeśli każdy z graczy podąża za procedurą pozbawioną żalu wewnętrznego, następuje zbieżność do zbioru rozkładów równowag skorelowanych. Kończymy rozdział 7. grami z informacją niepełną (grami bayesowskimi), gdzie gracze dysponują różną informacją na temat gry, w którą grają i wprowadzamy odpowiednie rozszerzenia równowag.

Na końcu, w rozdziale 8. przyglądamy się grom powtarzanym. Najpierw analizujemy najprostszy model (z ruchami obserwowanymi), z którego wprowadzamy: gry skończenie powtarzane, gdzie wypłata jest średnią wypłat z poszczególnych etapów (skończenie wielu), gry dyskontowe, gdzie wypłata jest (nieskończoną) sumą dyskontową wypłat na poszczególnych etapach oraz gry jednorodne, gdzie gracze rozważają wypłaty w każdej grze dostatecznie długiej (lub w każdej grze dyskontowej z odpowiednio niskim współczynnikiem dyskontowym). Przedstawiamy twierdzenie ludowe mówiące, że wypłaty w równowagach dowolnej gry jednolitej są dokładnie tymi wypłatami, które są zarazem wykonalne (osiągalne) i indywidualnie racjonalne (powyżej poziomu kary każdego z graczy). Przekaz jest prosty: jeśli gracze są dostatecznie cierpliwi, każda rozsądna wypłata może zostać osiągnięta w równowadze. Przytaczamy i dowodzimy również twierdzenia ludowe dla gier dyskontowych i skończenie powtarzalnych. Ostatnia sekcja prezentuje rozszerzenia modelu w trzech kierunkach: gier powtarzanych z sygnałami (niedoskonała obserwacja ruchów graczy), gier stochastycznych, gdzie przyglądamy się „Wielkiemu Dopasowaniu” (ang. Big Match) oraz w kierunku gier powtarzanych z informacją niepełną, gdzie dowodzimy twierdzenia cav u Aumanna i Maschlera.

Na zakończenie każdego rozdziału prezentujemy ćwiczenia często zawierające wyniki uzupełniające główny nurt książki. Podpowiedzi rozwiązań znaleźć można w ostatnim rozdziale. Poruszane tematy to m.in. stabilne dopasowania, aukcje Vickreya, osiągalność Blackwella, lemat Ferkasa, dualność w programowaniu liniowym, pojedynki, konkurencja Cournota, gry supermodularne oraz Tarskiego twierdzenie o punkcie stałym, gry wypukłe, gry potencjalne, gry rozpraszające, gra fikcyjna i trójkąt Shapleya, gra w Chomp, poker, targowanie się, podwójna aukcja, możliwa ujemna wartość informacji, strategiczny przekaz informacji, rozkład równowag skorelowanych poprzez minimaks, porównanie równowag skorelowanych i równowag Nasha, dylemat więźnia z niewidomym graczem, wojna płci w ciemności, wspólnie racjonalne wypłaty, wypłaty w równowagach doskonałych w podgrach dla gier dyskontowych i gry w odchodzenie.

Wymagania wstępne

Książka została napisana z myślą o doktorantach i pracownikach naukowych. Bierze swój początek z notatek z wykładów kursorycznych wygłaszanych na wydziałach matematyki kilku uniwersytetów (włączając w to UPMC-Paris 6 oraz Ecole Polytechnique), dostarcza formalnej prezentacji matematycznych podstaw teorii gier i jest zasadniczo samowystarczalna, jako że wiele dowodów używa narzędzi i pojęć zdefiniowanych w tekście. Niezbędna będzie znajomość matematyki na poziomie studiów wyższych, zwłaszcza podstawowych pojęć analizy (ciągłość, zwartość) czy algebry liniowej i geometrii (macierze, iloczyn skalarny, wypukłość) oraz dyskretnego rachunku prawdopodobieństwa (wartość oczekiwana, niezależność). Połączenie zainteresowania strategicznym myśleniem z umiłowaniem formalizmów, będzie wystarczające do przeczytania, zrozumienia i – miejmy nadzieję – znajdowania przyjemności z czytania tej książki.

Niektóre dowody zawierają materiał stosunkowo bardziej zaawansowany. Przykładowo, w rozdziale 2. włączenie różniczkowe używane jest do zilustrowania zbieżności procesu „gry fikcyjnej”. W rozdziale 3. używamy twierdzenia o separacji Hahna–Banacha dla zbiorów wypukłych. Prawdopodobieństwa borelowskie na zwartych przestrzeniach Hausdorffa oraz słaba* topologia na zbiorze takich prawdopodobieństw używana jest w podrozdz. 3.3. podczas prezentacji ogólnych twierdzeń o minimaksie w strategiach mieszanych. W podrozdz. 5.4. (Nasha pola wektorów i dynamiki) oraz 5.5. (równowagi i ewolucja) pojawiają się zwyczajne równania różniczkowe. Twierdzenie Kołmogorowa o rozszerzeniu zostaje zastosowane w rozdziale 8., zaś w ostatnim podrozdziale tego rozdziału pojawiają się martyngały (gry powtarzane z informacją niepełną).

Lektura uzupełniająca

Prezentujemy tutaj kilka publikacji, które uzupełnią nasze raczej zwięzłe wprowadzenie do matematycznych podstaw teorii gier strategicznych.

Niemożliwą do pominięcia encyklopedią, w której w każdym rozdziale omówiona jest konkretna dziedzina to:

• Aumann R.J., Hart S., (red.), Handbook of Game Theory I, II, III, North ­Holland, 1992, 1994, 2002.

• Young P., Zamir S., (red.), Handbook of Game Theory IV, North Holland, 2015

Prosta w lekturze klasyka:

• Owen G., Game Theory (3rd Edition), Academic Press, 1995.

Dość ogólna prezentacja dziedziny zawarta jest w pozycji:

• Maschler M., Solan E., Zamir S., Game Theory, Cambridge University Press, 2013.

Trzy podstawowe lektury traktujące raczej o ekonomii:

• Myerson R., Game Theory, Analysis of Conflict, Harvard University Press, 1991.

• Fudenberg D., Tirole J., Game Theory, M.I.T. Press, 1992.

• Osborne M., Rubinstein A., A Course in Game Theory, M.I.T. Press, 1994.

Równowagi i selekcja analizowane są w pozycji:

• van Damme E., Stability and Perfection of Nash Equilibria, Springer, 1991.

oraz nieco bardziej współcześnie:

• Ritzberger K., Foundations of Non-Cooperative Game Theory, Oxford University Press, 2002.

Następne dwie pozycje prezentują bardziej matematyczne podejście:

• Barron E.N., Game Theory, An Introduction, Wiley, 2008.

• Gonzalez-Diaz J., Garcia-Jurado I., Gloria Fiestras-Janeiro M., An Introductory Course on Mathematical Game Theory, GSM 115, AMS, 2010.

Źródłem na temat gier ewolucyjnych jest:

• Hofbauer J., Sigmund K., Evolutionary Games and Population Dynamics, Cambridge U.P., 1998.

Ładną prezentację powiązań z ekonomią i ewolucją znaleźć można w:

• Weibull J., Evolutionary Game Theory, MIT Press, 1995.

Nieco współcześniej:

• Sandholm W., Population Games and Evolutionary Dynamics, M.I.T. Press, 2010.

Najnowsze osiągnięcia w algorytmicznej teorii gier prezentowane są w:

• Nizan N., Roughgarden T., Tardos E., Vazirani V., (red.) Algorithmic Game Theory, Cambridge University Press, 2007.

• Karlin A., Peres Y., Game Theory, Alive, AMS, 2017.

Krótkie i szybkie wprowadzenie do strategicznych i powtarzanych gier (w języku francuskim):

• Laraki R., Renault J., Tomala T., Théorie des Jeux, X-UPS 2006, Editions de l’Ecole Polytechnique.

Wprowadzenie do gier powtarzanych o sumie zerowej:

• Sorin S., A First Course on Zero-Sum Repeated Games, Springer, 2002.

Zaś ogólne matematyczne analizy z dziedziny prezentowane są w pozycji:

• Mertens J.F., Sorin S., Zamir S., Repeated Games, Cambridge University Press, 2015.

Podziękowania

Autorzy pragną podziękować następującym osobom: Miquel Oliu-Barton, Tristan Tomala, Cheng Wan, a także Vianney Perchet, Giullaume Vigeral i Yannick Viossat za uważną lekturę i trafne uwagi.

Paryż, Francja / Liverpool, Wielka BrytaniaRida Laraki

[email protected]

Tuluza, FrancjaJérÔme Renault

[email protected]

Paryż, FrancjaSylvain Sorin

[email protected]Ł 1
WPROWADZENIE

1.1. Interakcja strategiczna

Celem teorii gier jest analiza sytuacji obejmujących interakcje strategiczne, w których kilka podmiotów (graczy, populacji, firm, automatów, komórek itp.) o określonych właściwościach (działania, ceny, kody, geny itp.) wchodzi w interakcje. Matematyczna analogia wykracza tu poza optymalizację, ponieważ agent nie kontroluje wszystkich zmiennych, które go dotyczą. Ponadto, wybranie przez agenta własnej zmiennej kontrolowanej będzie miało wpływ na innych agentów.

Interakcje te modelowane są w literaturze przedmiotu na kilka sposobów i na kilku poziomach. Przyjrzyjmy się im pokrótce.

1.1.1. Gry strategiczne

To podejście odpowiada głównemu tematowi analiz omawianych w ramach tego kursu. Zidentyfikowane autonomiczne struktury, między którymi zachodzi interakcja nazwane są graczami. Poprzez „autonomiczne” rozumiemy to, że ich charakterystyki, ich parametryzacja wyborów, którą nazywamy strategią są determinowane (wybierane, obierane przez graczy) niezależnie od siebie nawzajem.

Profil strategii (po jednym dla każdego gracza) powoduje jakiś wynik, a każdy z graczy używa rzeczywistej funkcji użyteczności zdefiniowanej na tej przestrzeni wyników. Głównym zadaniem staje się wtedy definicja i analiza zachowania racjonalnego w tak określonych ramach (patrz podrozdział 1.3.)

1.1.2. Gry koalicyjne

W ramach tego podejścia dane początkowe nadal dostarczane są przez zbiór graczy I, ale bierze się pod uwagę wszystkie możliwe podzbiory C ⊂ I, nazywane koalicjami, zaś funkcja efektywności wiąże każdy C z podzbiorem wyników, jaki może ono osiągnąć. Problemem staje się wtedy określenie konkretnego wyniku dla zbioru wszystkich graczy.

Odpowiada to normatywnemu lub aksjomatycznemu punktowi widzenia, w ramach którego w zależności od wymagań początkowych dotyczących równości, władzy czy wydajności sugeruje się rozwiązanie. Między innymi ważnymi koncepcjami wymieńmy: rozwiązania von Neumanna-Morgensterna, wartość Shapley’a, rdzeń, targowanie się, jądro negocjacji itp. Modele koalicyjne i strategiczne są powiązane ze sobą w obu kierunkach:

– przejście od gier strategicznych do koalicyjnych: analiza na poziomie strategicznym dotycząca wyboru strategii przez koalicję pozwala na zdefiniowanie funkcji charakterystycznej (lub efektywności), a następnie zastosowanie programu gier koalicyjnych;

– przejście od gier koalicyjnych do strategicznych: tzw. „program Nasha” . Wychodząc od funkcji efektywności i rozwiązania, definiuje się strategie i funkcje użyteczności w ten sposób, że racjonalne zachowanie graczy w odpowiedniej grze strategicznej wywołuje wybrane rozwiązanie.

1.1.3. Wybór społeczny i projektowanie mechanizmów

Ten obszar bada, w ramach paradygmatu gier strategicznych rozgrywanych przez zbiór graczy, wpływ reguł gry na wynik końcowy. Zamiast koncentrować się na strategicznych zachowaniach graczy, koncentrujemy się głównie na analizie wpływu procedur na przebieg gry. Powiązanymi obszarami są teorie podżegania i kontraktów.

1.2. Przykłady

Następujące przykłady ilustrują poszczególne rodzaje pytań, narzędzi i zastosowań spotykanych w teorii gier.

1.2.1. Stabilne dopasowania

Weźmy dwie skończone rodziny I i J (mężczyźni i kobiety, pracownicy i firmy itp.) o tej samej liczebności takie, że każdy element i ∈ I (wzgl. j ∈ J) posiada ścisłe preferencje w J (wzgl. I). Rozpatrywanym problemem jest istnienie i charakterystyka stabilnych dopasowań (lub małżeństw), a dokładniej odwzorowań bijektywnych π prowadzących z I do J takich, że nie istnieją żadne pary (i, π (i) = j), (i', π (i' ) = j' ), w których zarówno j' preferowałby i nad j, jak również i preferowałby i' nad j'. Przykładowo, jeśli problem dotyczy kojarzenia mężczyzn z kobietami, dopasowanie jest stabilne, jeśli żadna niedopasowana para nie woli bardziej być dopasowana razem niż pozostać ze swoimi dopasowanymi partnerami. (patrz ćwiczenie 1.)

1.2.2. Problem targowania się

Poprzez odcinek będziemy reprezentować zbiór, który ma zostać podzielony pomiędzy dwóch graczy. Każdy z graczy posiada pewne preferencje dotyczące jego części zbioru. Gra toczy się w czasie ciągłym pomiędzy momentami 0 i 1, zaś gracz, który zatrzyma się jako pierwszy (w momencie t) wygrywa część zbioru , a jego przeciwnik otrzymuje dopełnienie. Zakładamy, że a₁(t) (wzgl. a₂(t)) jest funkcją ciągłą rosnącą od 0 do 1 opisującą oszacowanie wartości części przez gracza 1, względnie gracza 2 (1 – ai(t) stanowi oszacowanie dopełnienia, (t, 1]). Każdy z graczy może otrzymać 1/2 poprzez celowanie w czas ti z ai(ti) = 1/2 (jeśli przeciwnik zatrzyma się wcześniej, to tym lepiej). Jeśli jednak ti < tj i gracz i o tym wie, może on przewidzieć, że gracz j nie zatrzyma się przed tj i będzie czekał aż do jakiegoś tj – ε. Problemy pojawiają się w związku z informacją na temat charakterystyki przeciwnika, z przewidywaniem jego zachowania (racjonalnością) i z wpływem procedury na wynik (jeśli ti < tj, to gracz j będzie wolał, żeby granica przesuwała się od 1 do 0). (patrz ćwiczenie 2.)

1.2.3. Równowaga transportu

Poprzez odcinek reprezentujemy bardzo liczny zbiór małych graczy, z których każdy używa albo samochodu albo metra. Zakładamy, że każdy z nich w ten sam sposób oszacowuje ruch na drodze, co reprezentujemy funkcją rosnącą υ (wzgl. m) od do siebie, przy czym υ(t) (wzgl. m(t)) reprezentuje użyteczność w przypadku użycia samochodu (wzgl. metra) w przypadku, gdy część t ∈ pojedzie metrem. Jeśli υ > m, jedyną równowagą jest t = 0, nawet jeśli wynik υ(0) mógłby być gorszy niż inny możliwy wynik m(1). Jeśli krzywe m i υ się przecinają, to punkty ich przecięcia stanowią również punkty równowagi, z których każdy może być stabilny lub nie. (patrz ćwiczenie 3.)

1.2.4. Aukcje

Na aukcji został wystawiony pewien niepodzielny przedmiot i n graczy dysponuje na jego temat wycenami υi, i = 1, …, n. Rozpatrywać można albo licytacje malejące, gdzie proponowana cena spada aż do zaakceptowania, albo licytacje rosnące, w których gracze przedstawiają następujące po sobie, rosnące oferty. Inny model odpowiada sytuacji, w której gracze przedstawiają jednocześnie ukryte oferty bi, zaś przedmiot zostaje sprzedany temu, kto przedstawił najwyższą ofertę. Jeśli następnie trzeba zapłacić tyle, ile się zaoferowało, gracze zainteresowani są znajomością wycen swoich przeciwników. Jeśli zapłacić trzeba tyle, ile wynosiła druga co do wysokości oferta, strategia bi = υi (oferowanie dokładnie tyle, na ile się wycenia według własnej ewaluacji) jest strategią dominującą dla wszystkich graczy. (patrz podrozdział 1.3.2 i ćwiczenie 4.)

1.2.5. Paradoks Condorceta

Troje graczy, a, b i c ma ścisłe preferencje na temat trojga kandydatów A, B i C. Jeśli a uszereguje kandydatów A > B > C, b uszereguje ich B > C > A, zaś c: C > A > B, wtedy A jest preferowany przez większość w stosunku do B, B jest preferowany przez większość w stosunku do C, zaś C jest preferowany przez większość w stosunku do A. Wynika z tego, że reguła większości nie zawsze jest przechodnia i w pewnych przypadkach może nie być kandydatów, którzy wygrywają ze wszystkimi innymi na zasadzie reguły większości.

Poniżej dostarczamy kilka modeli interakcji dynamicznych.

1.2.6. Gra ewolucyjna

Rozpatrujemy konkurencję między trzema rodzajami komórek: a wytwarza wirus i antywirus, b wytwarza antywirus, a c nie wytwarza nic. Produkcja ma swój koszt, więc b wygrywa z a (jeśli chodzi o sprawność lub tempo reprodukcji), a c wygrywa z b, jednak a zabija c. Mamy więc do czynienia z cyklem. Odpowiadająca temu dynamika wykreślona na sympleksie proporcji między poszczególnymi typami populacji ma wewnętrzny punkt spoczynku (gdy wszystkie trzy typy są obecne naraz), może być on jednak przyciągający lub odpychający. (patrz rozdział 5.)

1.2.7. Gra stochastyczna

Rozpatrujemy sytuację, w której dwóch rybaków łowi ryby gatunku, który może występować w dużej ilości (a), małej ilości (b) lub znajdować się na granicy wyginięcia (c). Gracze mogą mieć intensywną (I) lub zredukowaną (R) aktywność, zaś wynik ich działań zależy od stanu łowionego gatunku (a, b lub c) i jest wyrażony w ilości złowionych ryb i rozkładzie prawdopodobieństwa na stan w następnym okresie. W ten sposób zdefiniowaliśmy grę stochastyczną.

W stanie a opis interakcji strategicznej podany jest następująco:

zaś ewolucja stanu zdefiniowana jest przez:

Dla przykładu, jeśli w stanie a gracz 1 (którego strategie podane są przez wiersze macierzy) łowi dużo ryb (I), zaś gracz 2 (reprezentowany przez kolumny) ma zredukowaną aktywność (R), ewaluacja (wypłata, użyteczność) wyniku dla gracza 1. wynosi 120, dla gracza 2. zaś 60, zaś stan następnego dnia wynosić będzie a z prawdopodobieństwem 0,5 – odpowiednio (b ; 0,4) i (c ; 0,1).

W stanie (b) dane dla użyteczności wynoszą:

zaś dla prawdopodobieństw przejścia:

zaś w stanie (c) wyniki łowów wynoszą zawsze 0, a stan jest pochłaniający, tzn. stan utrzymuje się na c niezależnie od przyszłych wyborów graczy.

Gdy gracze dokonują wyboru rodzaju aktywności, istnieje wyraźny konflikt między natychmiastowym wynikiem (dzisiejsza wypłata) a konsekwencjami w postaci przyszłych stanów (a więc i przyszłych wypłat). Tak więc ewaluacja dzisiejszego zachowania zależy od czasu trwania interakcji. (patrz podrozdział 8.5.)

1.2.8. Gra powtarzana

Rozpatrujemy grę powtarzaną między dwoma graczami, w której stan interakcji opisany jest z pomocą macierzy wypłat:

(Gracz 1 wybiera wiersz a lub b, gracz 2 wybiera kolumnę α lub β, zaś odpowiadający tym wyborom element macierzy wskazuje użyteczności obu graczy i wynikający stąd wynik.) Na każdym etapie obaj gracze dokonują wyborów (niezależnie od siebie) i są informowani o obu wyborach przed następnym etapem. Jeśli graczom nie zależy na przyszłości, zawsze powtarza się profil (a, β) (jako że a jest zawsze lepsze niż b, zaś β jest lepsze niż α w przypadku a), jednak można wprowadzić do gry groźbę (ang. threat) w stylu „będę grać β w nieskończoność w przyszłości” w przypadku zmiany z b do a – w ten sposób można ustabilizować wynik (b, α). Użycie planu i groźby jest kwestią podstawową w badaniach gier z powtarzanych. (patrz rozdział 8.)

1.3. Notacje i podstawowe pojęcia

Wprowadzamy tu główne pojęcia potrzebne do analizy gier.

1.3.1. Gry strategiczne

Gra strategiczna w postaci normalnej G zdefiniowana jest przez:

– skończony zbiór graczy I (o liczebności |I| = n ≥ 1);

– niepusty zbiór strategii Si dla każdego gracza i ∈ I;

– odwzorowanie g = (g ¹, …, g n) z S = Πni=1 S i w ℝn.

To modeluje wybory dokonywane niezależnie od siebie przez każdego z graczy (każde i ∈ I może wybrać strategię s i ∈ S i) oraz globalny wpływ na gracza j w sytuacji, gdy wybrany zostanie profil s = (s¹, …, sn) mierzony przez g j(s) = g j(s¹, …, sn), co nazywamy wypłatą gracza j, zaś g j nazywamy funkcją wypłaty dla j.

Będziemy również używać alternatywnej notacji s = (si, s–i), gdzie s–i oznacza wektor strategii (s j)j∈I \{i} graczy innych niż i, zaś S –i = Πj≠i S j.

Bardziej ogólnie, postać gry jest odwzorowaniem F z S do przestrzeni wyników R. Każdy z graczy i ∈ I posiada pewną preferencję (np. całkowity praporządek i) na R. Jeśli zaprezentujemy to jako funkcja użyteczności ui z R do ℝ, to wtedy złożenie ui ◦ F daje nam g i, ewaluację wypłaty dla danego wyniku dla gracza i. (Sprowadza się to do wzięcia zbioru S profilów strategii jako przestrzeni wyników).

Zauważmy, że g i(s) nie stanowi fizycznej wielkości (np. pieniędzy), tylko użyteczności wyniku wywołanego profilem s dla gracza i. Z definicji gracz i ściśle preferuje s nad t wtedy i tylko wtedy, gdy g i(s) > g i(t), zaś w przypadku loterii na profilach zakładamy, że ewaluacją loterii jest spodziewane g i. Tak więc w tej książce zakładamy, że preferencje graczy dotyczące loterii spełniają aksjomaty von Neumanna-Morgensterna.

1.3.2. Dominacja

Dla danego zbioru L oraz x, y należących do ℝL piszemy:

W grze strategicznej, si w Si jest strategią ściśle dominującą (wzgl. dominującą) gracza i jeśli

względnie

si jest ściśle zdominowana (wzgl. słabo zdominowana), jeśli w Si istnieje jakieś t i takie, że

względnie

1.3.3. Iterowana eliminacja

Ściśle zdominowaną strategię uważa się za zły wybór dla gracza. Przypuśćmy, że zaczynając od danej gry strategicznej usuwamy z niej wszystkie ściśle zdominowane strategie. Taka eliminacja definiuje nowy zbiór strategii, a więc i nowe możliwe ściśle zdominowane strategie, więc możemy iterować ten proces poprzez eliminację nowych ściśle zdominowanych strategii itd. Gra jest rozwiązywalna, jeśli iterowana eliminacja strategii ściśle zdominowanych dąży do zbioru jednoelementowego (w szczególności, jeśli każdy z graczy dysponuje ściśle dominującą strategią – patrz rozdział 4. oraz przykład w podrozdziale 1.4.1.).

1.3.4. Najlepsza odpowiedź

Korespondencja ε-najlepszej odpowiedzi (ε ≥ 0), oznaczana BRie z S –i do S i definiujemy jako:

Równowaga Nasha jest profilem s strategii takim, że żadna jednostronna zmiana nie jest korzystna: dla każdego gracza i wybór alternatywny t i nie dałby mu większej wypłaty: g i(t i, s–i) ≤ gi(s). To oznacza: si ∈ BRi₀ (s–i), Ɐi ∈ I (patrz rozdział 4.)

1.3.5. Mieszane rozwinięcia

W przypadku mierzalnych przestrzeni strategii S i (z σ-algebrą S i), mieszane rozwinięcie gry G jest zdefiniowane przez przestrzeń mieszanych strategii M i, dla każdego i ∈ I – co stanowi podzbiór zbioru prawdopodobieństw na (S i, S i), wypukły i zawierający Si (elementy Si są identyfikowane masami Diraca i nazywane są czystymi strategiami).

Zakładamy, że twierdzenie Fubiniego stosuje się do całki na g, gdzie M = Πni=1 Mi. To pozwala nam zdefiniować rozszerzoną wypłatę jako oczekiwaną z uwzględnieniem produktu rozkładu prawdopodobieństwa wygenerowanego przez mieszane strategie graczy:

Explicite, w przypadku skończonym, jeśli Δ(Si) jest sympleksem (otoczką wypukłą) na Si, Δ = ΠNi=1 Δ(Si) oznacza zbiór mieszanych profilów strategii. Dla danego profilu σ = (σ¹, …, σN) ∈ Δ, wypłata dla gracza i w mieszanym rozwinięciu gry jest podana w następujący sposób:

i odpowiada wieloliniowemu rozszerzeniu g i.

1.4. Informacja i racjonalność

Poniżej prezentujemy kilka przykładów ilustrujących różnice między grami jednoosobowymi (zwanymi inaczej problemami optymalizacyjnymi) a strategiczną interakcją.

1.4.1. Strategia dominująca i wynik zdominowany

Jak zwykle w przypadku reprezentacji macierzowej, wedle konwencji gracz 1 wybiera wiersz, a gracz 2 kolumnę, zaś pierwszą (wzgl. drugą) wartością każdego elementu macierzy jest wypłata gracza 1 (wzgl. 2). Tutaj I = {1, 2}, S¹ = {a, b}, zaś S² = {α, β}.

W tej grze a ściśle dominuje b, a β jest optymalną strategią dla a, tak więc wynikiem jest (1, 1) na mocy iterowanej eliminacji strategii ściśle zdominowanych. Zauważmy, że jeśli a nie jest dostępne dla gracza 1, wynikiem staje się (5, 5), co jest lepsze dla obu graczy.

1.4.2. Dominacja i optimum w sensie Pareto

Dla danego zbioru możliwych wyników S ⊂ ℝn, element x należący do S jest nazwany optimum w sensie Pareto, jeśli nie istnieje żaden inny element y ≠ x w S taki, że yi ≥ xi dla każdego i = 1, …, n.

Rozważmy następującą grę dwuosobową z trzema możliwymi strategiami dla każdego gracza:

W zbiorze możliwych wypłat {(1, 0), (0, 1), (1, 1)}, (1, 1) jest jedynym optimum w sensie Pareto i jest wyeliminowane przez słabą dominację, co prowadzi do:

gdzie jedynym racjonalnym wynikiem jest (1/2, 1/2).

1.4.3. Kolejność eliminacji

Wynik (2, 2) jest wyeliminowany na mocy słabej dominacji, jeśli gra zaczyna się od gracza 2, ale nie jeśli gra zaczyna się od gracza 1. Nie ma jednak żadnej niejednoznaczności w procesie eliminacji na mocy ścisłej dominacji.

1.4.4. Hipotezy wiedzy

Podczas analizy procesu dedukcyjnego kluczowym jest rozróżnienie między:

– wiedzą na temat stanu gry i wiedzą faktyczną. Dotyczy ona informacji na temat parametrów gry: strategii, wypłat (procedurami autonomicznymi są w tym paradygmacie takie procedury, które zależą od strategii danego gracza i od funkcji wypłat) oraz

– wiedzą na temat świata i wiedzą epistemiczną, co oznacza dodatkowo wiedzę na temat informacji posiadanych przez przeciwnika oraz na temat ich racjonalności (i stopnia tejże).

Napotykamy tutaj na paradoks błędnego koła: aby zdefiniować racjonalność danego gracza, musimy określić posiadane przez niego informacje, a te zawierają, między innymi, jego własne informacje na temat racjonalności jego przeciwników (patrz np. Sorin ).

1.4.5. Dominacja a strategie mieszane

Pojęcie dominacji zależy od ram, w jakich ją rozpatrujemy:

Strategia b nie jest zdominowana przez czyste strategie a ani c, ale jest ściśle zdominowana przez mieszaną strategię a + c.

1.4.6. Gry dynamiczne a przewidywania

W dynamicznych sytuacjach interaktywnych główną różnicą między grami z powtórzeniami a grami ewolucyjnymi w zakresie ich modelowania jest to, czy każdy z graczy bierze pod uwagę konsekwencje, jakie jego zachowanie wywiera na innych uczestników. Pierwszy model analizuje strategiczne interakcje zawierające racjonalne przewidywania. Drugi model opisuje globalne konsekwencje poszczególnych indywidualnych, krótkowzrocznych procedur adaptacyjnych.

1.5. Ćwiczenia

Ćwiczenie 1. Stabilne dopasowania

Rozpatrzmy zbiór M, n mężczyzn (oznaczanych a, b, c…) oraz zbiór K, n kobiet (oznaczanych A, B, C … ). Mężczyźni posiadają ścisłe preferencje dotyczące kobiet, a kobiety – ścisłe preferencje dotyczące mężczyzn. Dla przykładu, dla n = 3 mężczyzna b może preferować najpierw kobietę C, potem A, a potem B, podczas gdy kobieta C może preferować najpierw mężczyznę a, potem c, potem b. Dopasowanie to podzbiór iloczynu kartezjańskiego M × K taki, że każdy mężczyzna jest dopasowany z dokładnie jedną kobietą, a każda kobieta jest dopasowana z dokładnie jednym mężczyzną (można to rozpatrywać jako odwzorowanie bijekcyjne z M na K).

Dopasowanie μ jest stabilne, jeśli nie istnieje para (x, Y) nie zawarta w μ taka, że zarówno x, jak i Y odpowiednio preferują Y i x w stosunku do ich partnera w μ (tak, że x i Y woleliby „rozwieść się” z partnerem z dopasowania μ tak, aby być razem).

Model ten został skonstruowany przez Gale i Shapleya , którzy wykazali istnienie stabilnego dopasowania wyznaczonego przez następujący algorytm:

Kobiety zostają w domach, a mężczyźni odwiedzają kobiety (inny algorytm otrzymamy, jeśli zamienimy M i K rolami).

Dzień 1: Każdy mężczyzna oświadcza się kobiecie, którą preferuje; jeśli kobieta otrzymuje kilka propozycji, zatrzymuje ona w domu tego mężczyznę, którego preferuje najbardziej i odrzuca wszystkie inne oferty. Jeśli każda kobieta otrzyma dokładnie jedną propozycję, każda oferta zostaje zaakceptowana i algorytm zatrzymuje się. W przeciwnym przypadku:

Dzień 2: Każdy mężczyzna, którego oświadczyny zostały odrzucone 1. dnia oświadcza się następnej (a więc drugiej) kobiecie, którą preferuje. Następnie każda kobieta porównuje nowe propozycje (o ile dostała jakąś) z tą, którą przyjęła 1. dnia (o ile takowa istnieje) i zatrzymuje w domu tego mężczyznę, którego preferuje z nich najbardziej. Jeśli każda kobieta zatrzyma mężczyznę, algorytm zatrzymuje się. W przeciwnym przypadku, indukcyjnie:

Dzień k: Każdy mężczyzna, który został odrzucony dnia k – 1 oświadcza się następnej kobiecie na swej liście. Następnie każda kobieta porównuje swoją nową ofertę (jeśli takową dostała) do oferty, którą przyjęła dnia k – 1 (o ile takowa istnieje) i zatrzymuje w domu tego mężczyznę, który jest wyżej na jej liście preferencji. Jeśli każda kobieta zatrzymała mężczyznę, algorytm się zatrzymuje. W przeciwnym przypadku przynajmniej jedna kobieta i przynajmniej jeden mężczyzna na koniec dnia są samotni i algorytm jest kontynuowany.

(1) Wykazać, że algorytm jest dobrze zdefiniowany i że zatrzyma się po co najwyżej n² dniach.

(2) Obliczyć stabilne dopasowanie dla każdej z następujących dwóch preferencji:

Dla przykładu, element macierzy (1,3) na pozycji (a, A) oznacza, że mężczyzna a posiada kobietę A na swojej liście preferencji na miejscu 1., zaś kobieta A posiada mężczyznę a na swojej liście preferencji na miejscu 3.

(3) Wykazać, że ostateczny wynik algorytmu jest z konieczności dopasowaniem stabilnym.

(4) Wykazać, że stabilne dopasowanie może nie istnieć w następującym wariancie: rozpatrujemy wspólnotę ludzi, w której mamy 2n studentów oraz n pokoi dla dwóch osób i każdy student posiada ścisłą listę preferencji na temat swoich 2n – 1 potencjalnych współlokatorów.

(5) Zdefiniować stabilne dopasowania i zbadać ich istnienie w społeczeństwie poligamicznym: rozpatrzmy n studentów i m szkół, gdzie każdy student posiada preferencje na temat szkół, zaś każda szkoła dysponuje rankingiem studentów i maksymalną objętością (numerus clausus).

Ćwiczenie 2. Procedura dzielenia tortu

Sędzia tnie tort, utożsamiany z odcinkiem , między dwóch graczy tak, jak następuje. Przesuwa on nóż w sposób ciągły od 0 do 1. Pierwszy gracz, który zatrzyma nóż w jakimś x ∈ otrzyma część tortu na lewo od noża, tzn. . Drugi gracz otrzyma pozostałą część tortu, na prawo od noża. Jeśli obaj gracze zatrzymają nóż w tym samym momencie, na mocy konwencji gracz 1 dostanie część lewą, a gracz 2 – część prawą. Całość tortu jest oceniana na 1 przez obu graczy. Gracz 1 (wzgl. gracz 2) ocenia lewą część tortu do x jako f(x) (wzgl. g(x)), zaś prawą część jako 1 – f(x) (wzgl. 1 – g(x)), gdzie f i g są ciągłe, ściśle rosnące i przechodzą z na .

(1) Wykazać, że każdy gracz może zagwarantować sobie wynik przynajmniej 1/2.

(2) Co powinno się zrobić, gdy jest się graczem 1 i zna się f i g?

(3) Rozważyć przypadek, gdy jest się graczem 1 (wzgl. 2) i nie zna się g (wzgl. f).

(4) Sędzia zmienia reguły gry i porusza nożem w sposób ciągły z prawa na lewo (od x = 1 do x = 0). Czy zmiana ta ma jakiś wpływ na zachowanie graczy?

Ćwiczenie 3. Autobus czy samochód?

Weźmy bardzo duże miasto o populacji modelowanej jako odcinek . Każdy mieszkaniec ma wybór pomiędzy publicznym autobusem lub prywatnym samochodem i każdy z nich ma takie same preferencje: u(B, x) (wzgl. u(V, x)) to użyteczność tego, że ktoś wybierze autobus (wzgl. swój samochód) w sytuacji, w której x jest odsetkiem populacji, która zadecydowała się na autobus. Czynimy tu następujące naturalne założenia: u(V, x) jest wprost proporcjonalna do x (wysoka wartość x oznacza mniejsze korki) oraz u(B, ·) i u(V, ·) są ciągłe. Dana jest proporcja początkowa x₀ ∈ (0, 1), zakładamy zaś, że proporcja xt pasażerów autobusu w danym czasie t ∈ zachowuje się zgodnie z dynamiką równania replikatora:

gdzie υ(xt) = xtu(B, xt) + (1 – xt)u(V, xt)

Zbadajmy stacjonarne punkty tej dynamiki na funkcji użyteczności.

(1) Zbadać, co się stanie, jeśli u(V, x) > u(B, x) dla wszystkich x.

(2) Podać przykład, gdy „opieka społeczna” υ(xt) ściśle maleje wraz z czasem.

(3) Co jeśli u(V, x) = 2 + 3x, a u(B, x) = 3 dla każdego x?

(4) Załóżmy, że u(B, 0) > u(V, 0), zaś u(B, 1) < u(V, 1). Wykazać, że ogólnie liczba m punktów stacjonarnych dynamiki (które stanowią granice trajektorii zaczynających się od (0, 1)) jest nieparzysta oraz że (m+1)/2 z nich jest atraktorami lokalnymi dynamiki.

(5) Rozpatrzeć (4) dla przypadku ogólnego.

Ćwiczenie 4. Aukcja Vickreya

Zorganizowano następującą aukcję w celu sprzedaży obrazu:

(a) każdy gracz i przedstawia swoją ofertę pi w zaklejonej kopercie;

(b) ten gracz (nazwijmy go k), który przedstawi najwyższą ofertę (pk = maxi pi) wygrywa aukcję i otrzymuje obraz;

(c) jeśli kilku graczy przedstawi tę samą najwyższą ofertę, wyłania się zwycięzcę zgodnie z zadanym porządkiem liniowym (dokładny porządek, czy też reguła rozstrzygająca remis, nie odegra żadnej roli jeśli chodzi o wynik; można dzięki niej założyć, że zwycięzca zawsze zostanie wyłoniony spośród graczy, którzy przedstawili najwyższe oferty);

(d) zwycięzca k płaci za obraz tyle, ile wynosiła druga najwyższa oferta p, zdefiniowana jako p = maxi≠k pi.

Zakładamy, że każdy gracz i wycenia obraz na υi (υi jest maksymalną sumą, jaką jest on gotów zapłacić w celu zakupu obrazu), zaś jego użyteczność wynosi 0 jeśli nie jest zwycięzcą, a υi – p jeśli wygrywa on aukcję i płaci p.

Wykazać, że dla każdego gracza i oferowanie oferty pi = υi jest strategią dominującą.