Teoria gier: czym jest, kto ją stworzył i gdzie się ją stosuje
W skrócie: teoria gier to dział matematyki, który bada decyzje zależne od tego, co postanowią inni. „Gra” to każda sytuacja, w której kilku graczy wybiera strategie, a wypłata każdego z nich zależy od wyborów wszystkich. Dziedzinę zapoczątkował John von Neumann (twierdzenie minimaksowe, 1928) i jego książka z Oskarem Morgensternem Theory of Games and Economic Behavior (1944); John Nash dodał w 1950 roku równowagę Nasha. Dziś teorię gier stosuje się w ekonomii, aukcjach, polityce, biologii, bezpieczeństwie i sztucznej inteligencji.
Mało która decyzja zapada w próżni. Cena w sklepie zależy od cen konkurencji po drugiej stronie ulicy, najlepszy róg bramki dla strzelającego karnego zależy od tego, w którą stronę rzuci się bramkarz, a budżet obronny państwa od budżetów sąsiadów. Za każdym razem trafny wybór zależy od przewidywania cudzego wyboru, a druga strona przewiduje w ten sam sposób nasz. Teoria gier to narzędzie do myślenia właśnie o tej pętli i dlatego słowo „gra” obejmuje tu zarówno szachy, jak i wojny cenowe czy rokowania pokojowe.
Czym jest teoria gier? Definicja
Teoria gier zajmuje się interakcjami strategicznymi, czyli sytuacjami, w których wynik każdego uczestnika zależy nie tylko od jego decyzji, ale też od decyzji innych. Żeby taką sytuację przeanalizować, opisuje się ją czterema elementami:
- Gracze: ci, którzy podejmują decyzje. Mogą to być ludzie, firmy, państwa, zwierzęta albo programy komputerowe.
- Strategie: opcje do wyboru albo kompletny plan postępowania na każdą sytuację, w jakiej gracz może się znaleźć.
- Wypłaty: to, co każdy gracz dostaje przy każdej kombinacji strategii, zapisane liczbami (pieniądze, lata więzienia, punkty, liczba potomstwa).
- Informacja: co gracz wie w chwili wyboru. W szachach widać całą planszę, w pokerze nie widać kart przeciwnika.
Gdy sytuacja jest tak opisana, pytanie brzmi: co powinien zrobić każdy gracz i co się stanie, jeśli wszyscy będą rozumować starannie? Odpowiedzi często zaskakują, bo wybór najlepszy dla każdego z osobna potrafi prowadzić do wyniku gorszego dla wszystkich.
Najważniejsze pojęcia teorii gier
Gry o sumie zerowej i niezerowej
W grze o sumie zerowej zysk jednego gracza jest dokładnie stratą drugiego: wypłaty zawsze sumują się do zera. Szachy, poker we dwóch czy rzut karny to gry o sumie zerowej. W grze o sumie niezerowej obie strony mogą zyskać albo obie stracić. Handel, negocjacje i większość życia gospodarczego to gry o sumie niezerowej, dlatego teoria gier dotyczy czegoś więcej niż samego wygrywania.
Strategia dominująca
Strategia jest dominująca, jeśli jest najlepsza bez względu na to, co zrobią pozostali gracze. Gdy gracz ma strategię dominującą, analiza jest prosta: powinien ją wybrać. Wiele słynnych gier jest ciekawych właśnie dlatego, że strategie dominujące wszystkich graczy razem dają marny wynik.
Równowaga Nasha
Równowaga Nasha to zestaw strategii, po jednej dla każdego gracza, w którym nikt nie może poprawić swojego wyniku, zmieniając wyłącznie własną decyzję. To punkt stabilny: gdy gracze już w nim są, nikt nie ma powodu, by samodzielnie z niego wyjść. Dwa samochody na drodze są w równowadze, gdy oba jadą prawą stroną, ale także wtedy, gdy oba jadą lewą; dlatego kraj musi się umówić tylko na jedną z nich. Pojęcie nosi imię Johna Nasha, który w 1950 roku udowodnił, że każda gra ze skończoną liczbą graczy i strategii ma co najmniej jedną równowagę.
Strategie mieszane
Czasem każdy przewidywalny wybór da się wykorzystać. W „papier, kamień, nożyce” ktoś, kto zawsze pokazuje kamień, zawsze przegra z papierem. Równowagą jest losowanie każdej z trzech opcji z prawdopodobieństwem jednej trzeciej. Losowanie według ustalonych prawdopodobieństw to strategia mieszana, i właśnie dopuszczenie takich strategii sprawia, że twierdzenie Nasha działa dla każdej skończonej gry. Podobnie zachowują się strzelcy karnych i bramkarze: kto zawsze strzela w ten sam róg, jest łatwy do rozszyfrowania.
Gry jednoczesne i sekwencyjne
W grze jednoczesnej gracze wybierają w tym samym momencie, nie znając wyboru drugiej strony (aukcja z zamkniętymi ofertami, papier-kamień-nożyce). W grze sekwencyjnej wykonują ruchy po kolei i mogą reagować na wcześniejsze (szachy, negocjacje z ofertą i kontrofertą). Gry sekwencyjne rysuje się jako drzewo gry i rozwiązuje indukcją wsteczną: zaczyna się od końca, ustala najlepszy ostatni ruch, potem najlepszy ruch przed nim i tak dalej aż do początku.
Gry kooperacyjne i niekooperacyjne
Niekooperacyjna teoria gier bada graczy, którzy decydują każdy za siebie; tu należy równowaga Nasha. Kooperacyjna teoria gier pyta, co mogą osiągnąć grupy graczy (koalicje) i jak sprawiedliwie podzielić wspólny wynik. Najbardziej znaną odpowiedzią na pytanie o podział jest wartość Shapleya, zaproponowana przez Lloyda Shapleya w 1953 roku; dziś używa się jej również do wyjaśniania, które dane wejściowe zdecydowały o odpowiedzi modelu uczenia maszynowego.
Dylemat więźnia: najsłynniejsza gra
Policja zatrzymuje dwóch podejrzanych i przesłuchuje ich w osobnych pokojach. Każdy może milczeć albo obciążyć wspólnika. Jeśli obaj milczą, każdy dostaje rok więzienia. Jeśli jeden zdradza, a drugi milczy, zdrajca wychodzi na wolność, a milczący dostaje trzy lata. Jeśli zdradzają obaj, każdy dostaje dwa lata.
| B milczy | B zdradza | |
|---|---|---|
| A milczy | po 1 roku | A: 3 lata, B: wolność |
| A zdradza | A: wolność, B: 3 lata | po 2 lata |
Spójrzmy z perspektywy A. Jeśli B milczy, zdrada daje A wolność zamiast roku. Jeśli B zdradza, zdrada daje A dwa lata zamiast trzech. Cokolwiek zrobi B, zdrada jest dla A lepsza: to strategia dominująca. Tak samo jest dla B. Obaj więc zdradzają i siedzą po dwa lata, choć gdyby obaj milczeli, dostaliby po roku. Jedyna równowaga Nasha jest gorsza dla obu graczy niż wynik, który osiągnęliby, ufając sobie nawzajem.
Grę wymyślili w 1950 roku Merrill Flood i Melvin Dresher z RAND Corporation; matematyk Albert Tucker dopisał do niej historię z więźniami i nadał nazwę. Ta sama struktura pojawia się w wojnach cenowych, wyścigu zbrojeń, przełowieniu łowisk i porozumieniach klimatycznych: każdej stronie opłaca się wyłamać, a gdy wyłamią się wszyscy, tracą wszyscy.
Co się zmienia, gdy gra się powtarza
Rozegrany raz, dylemat więźnia nagradza zdradę. Rozgrywany wiele razy z tym samym partnerem wygląda inaczej, bo dzisiejszą zdradę można jutro ukarać. Około 1980 roku politolog Robert Axelrod zaprosił badaczy do nadsyłania programów, które grały ze sobą w powtarzany dylemat więźnia. Wygrał jeden z najprostszych, wet za wet (ang. tit for tat) autorstwa Anatola Rapoporta: w pierwszej rundzie współpracuj, potem powtarzaj to, co przeciwnik zrobił poprzednio. Axelrod opisał wyniki w książce The Evolution of Cooperation (1984). Jego wniosek: dobrze radzą sobie strategie uprzejme (nigdy nie zdradzają pierwsze), odpowiadające ciosem na cios, wybaczające i łatwe do zrozumienia.
Inne klasyczne gry
- Gra w cykora (jastrząb i gołąb): dwóch kierowców pędzi naprzeciw siebie; kto skręci, traci twarz, ale jeśli nie skręci żaden, obaj się rozbiją. Są dwie równowagi, w każdej ustępuje jeden z graczy, a cała gra polega na przekonaniu drugiej strony, że to nie my ustąpimy.
- Polowanie na jelenia: dwóch myśliwych może razem upolować jelenia (duża zdobycz, wymaga obu) albo w pojedynkę zająca (mała, ale pewna). Równowagą jest zarówno wspólne polowanie na jelenia, jak i polowanie każdego na zające; o tym, która nastąpi, decyduje zaufanie.
- Orzeł i reszka (matching pennies): jeden gracz wygrywa, gdy monety pokażą to samo, drugi, gdy pokażą co innego. Nie ma tu stabilnego wyboru, jest tylko strategia mieszana: orzeł lub reszka z prawdopodobieństwem jednej drugiej. To najprostsza gra o sumie zerowej.
Kiedy powstała teoria gier? Krótka historia
Ludzie myśleli strategicznie na długo przed pierwszymi wzorami, ale teoria gier jako dziedzina matematyki ma mniej więcej sto lat. Najważniejsze etapy:
| Rok | Wydarzenie |
|---|---|
| 1838 | Antoine Augustin Cournot opisuje dwie firmy decydujące, ile produkować; jego rozwiązanie to wczesny przykład tego, co dziś nazywamy równowagą Nasha. |
| 1913 | Ernst Zermelo pokazuje, że w szachach albo białe mogą wymusić wygraną, albo czarne, albo obie strony mogą wymusić co najmniej remis. |
| 1921 | Emile Borel publikuje prace o strategiach mieszanych. |
| 1928 | John von Neumann dowodzi twierdzenia minimaksowego dla dwuosobowych gier o sumie zerowej. |
| 1944 | Von Neumann i Oskar Morgenstern wydają Theory of Games and Economic Behavior; ten rok uznaje się zwykle za narodziny dziedziny. |
| 1950 | John Nash definiuje równowagę Nasha; Flood i Dresher tworzą w RAND dylemat więźnia. |
| 1953 | Lloyd Shapley wprowadza wartość Shapleya do podziału zysków w koalicji. |
| 1962 | David Gale i Lloyd Shapley publikują algorytm odroczonej akceptacji do stabilnego przydziału par. |
| 1973 | John Maynard Smith i George Price wprowadzają strategię ewolucyjnie stabilną i przenoszą teorię gier do biologii. |
| 1984 | The Evolution of Cooperation Roberta Axelroda opisuje turnieje powtarzanego dylematu więźnia. |
| 1994 | John Nash, John Harsanyi i Reinhard Selten otrzymują Nagrodę Banku Szwecji im. Alfreda Nobla w dziedzinie ekonomii. |
| 2005 | Nagrodę dostają Robert Aumann i Thomas Schelling za analizę konfliktu i współpracy. |
| 2012 | Nagrodę dostają Alvin Roth i Lloyd Shapley za teorię stabilnych przydziałów i projektowanie rynków. |
| 2020 | Nagrodę dostają Paul Milgrom i Robert Wilson za rozwój teorii aukcji i nowe formaty aukcji. |
Jeśli potrzebna jest jedna data, to 1944, rok wydania książki von Neumanna i Morgensterna; jeśli pierwsze twierdzenie, to twierdzenie minimaksowe von Neumanna z 1928 roku. Życie Nasha stało się później tematem filmu Piękny umysł (2001).
Twierdzenie minimaksowe
Wynik von Neumanna z 1928 roku mówi, że w każdej dwuosobowej grze o sumie zerowej ze skończoną liczbą strategii istnieje wartość v i (być może mieszana) strategia dla każdego gracza, taka że pierwszy gracz może zagwarantować sobie średnio co najmniej v, a drugi może go ograniczyć do co najwyżej v. Innymi słowy, „maksymalizuj swój najgorszy wynik” i „minimalizuj najlepszy wynik rywala” spotykają się w tej samej liczbie. Dlatego gra o sumie zerowej ma dobrze określony „poprawny” sposób gry, a ta sama idea, stosowana ruch po ruchu, to sposób myślenia programów szachowych.
Gdzie stosuje się teorię gier?
Ekonomia i biznes
Teoria gier należy dziś do podstawowych narzędzi ekonomii. Modeluje się nią konkurencję kilku dużych firm (oligopol), ustalanie cen i wchodzenie na rynek, negocjacje związków zawodowych z pracodawcami oraz umowy zawierane wtedy, gdy jedna strona wie więcej niż druga. Pokrewna dziedzina, projektowanie mechanizmów (Nobel 2007 dla Leonida Hurwicza, Erica Maskina i Rogera Myersona), działa od końca: zaczyna od pożądanego wyniku i tak ustala reguły gry, by gracze dochodzili do niego, kierując się własnym interesem.
Aukcje
Aukcja to gra, a jej reguły zmieniają sposób licytowania. Rządy sprzedają operatorom komórkowym częstotliwości radiowe w aukcjach zaprojektowanych z pomocą teorii gier: jednoczesną aukcję wielorundową, przy której projektowaniu pomagali Milgrom i Wilson, amerykańska Federalna Komisja Łączności (FCC) zastosowała po raz pierwszy w 1994 roku. Także o tym, jaka reklama wyświetli się na stronie, zwykle decyduje błyskawiczna automatyczna aukcja między reklamodawcami.
Rynki przydziału: lekarze i nerki
Na niektórych rynkach nie da się użyć cen: nie można kupić miejsca w szkole ani nerki. Algorytm Gale'a-Shapleya znajduje przydział stabilny, czyli taki, w którym żadne dwie strony nie wolałyby siebie nawzajem od partnerów, których dostały. Jego wersja, przeprojektowana przez Alvina Rotha w latach 90., przydziela w Stanach Zjednoczonych absolwentów medycyny do programów rezydenckich w szpitalach. Roth pomógł też zbudować programy wymiany nerek, w których niezgodne pary dawca-biorca zamieniają się dawcami, dzięki czemu możliwych jest więcej przeszczepów.
Polityka i stosunki międzynarodowe
W czasie zimnej wojny teorię gier stosowano do analizy odstraszania nuklearnego: jak sprawić, by groźba była wiarygodna, i dlaczego zdolność do drugiego uderzenia czyni pierwsze uderzenie bezcelowym. Thomas Schelling w The Strategy of Conflict (1960) pokazał, jak zobowiązania, wiarygodne groźby i „punkty skupienia” (rozwiązania, które ludzie wybierają bez porozumiewania się, jak spotkanie w południe pod zegarem na dworcu) kształtują negocjacje. Tymi samymi narzędziami analizuje się głosowania, budowanie koalicji i porozumienia klimatyczne.
Biologia i ewolucja
Zwierzęta nie liczą wypłat, ale robi to za nie dobór naturalny: strategie dające więcej potomstwa się rozprzestrzeniają. Praca Maynarda Smitha i Price'a z 1973 roku wykorzystała grę w jastrzębia i gołębia, by wyjaśnić, dlaczego większość walk między zwierzętami tego samego gatunku to rytualne pokazy, a nie walki na śmierć i życie. Strategia ewolucyjnie stabilna to taka, której raz rozpowszechnionej w populacji nie może wyprzeć rzadka alternatywa. Te same idee pomagają badać współpracę, proporcję płci i rywalizację bakterii czy wirusów.
Informatyka, sztuczna inteligencja i bezpieczeństwo
Programy grające przeszukują drzewo gry według zasady minimaks: zakładają, że przeciwnik zawsze odpowie najlepszym ruchem, i wybierają ruch, którego najgorszy możliwy skutek jest najlepszy. W 2017 roku program Libratus z Carnegie Mellon University pokonał czołowych zawodowców w pokera heads-up no-limit Texas hold'em, a w 2019 roku jego następca Pluribus wygrał w pokera sześcioosobowego; oba wyliczały strategie bliskie równowadze, zamiast naśladować ludzi. Teoria gier pomaga też planować ochronę: od 2007 roku policja na lotnisku w Los Angeles korzysta z oprogramowania opartego na grach Stackelberga, które losowo rozmieszcza punkty kontrolne i patrole, by nie dało się ich przewidzieć.
Życie codzienne
Żeby korzystać z głównych lekcji, nie trzeba wzorów. Przed decyzją, która dotyczy innych, zapytaj, jak oni na nią odpowiedzą. Poszukaj strategii dominującej. Zauważ, kiedy działanie każdego we własnym interesie prowadzi do gorszego wyniku dla wszystkich (dylemat więźnia), i wtedy szukaj sposobów, by współpraca się utrzymała: powtarzane kontakty, reputacja, egzekwowane umowy. Dzielenie rachunku, wybór kolejki do kasy i decyzja, czy się targować, to małe gry.
Teoria gier a gry na tej stronie
Teoria gier i gry rekreacyjne spotykają się najwyraźniej w dwuosobowych grach czysto umiejętnościowych, takich jak kółko i krzyżyk, Cztery w rzędzie czy warcaby. Nie ma w nich kości ani ukrytych kart, więc, jak Zermelo pokazał dla szachów, każda ma z góry ustalony wynik przy idealnej grze obu stron. Artykuł o rozwiązanych grach (po angielsku) wyjaśnia, które z nich komputery już rozgryzły: kółko i krzyżyk kończy się remisem, w Czwórkach (Connect Four) wygrywa zaczynający, a warcaby kończą się remisem.
Komputerowi przeciwnicy w naszych grach używają dokładnie idei minimaks z twierdzenia von Neumanna, przerwanej na ograniczonej głębokości. W Czterech w rzędzie komputer na poziomie trudnym patrzy cztery ruchy do przodu (licząc ruchy obu graczy), używając minimaksu z cięciami alfa-beta, które pomijają ruchy niemogące zmienić wyniku. W Warcabach na poziomie trudnym liczy osiem ruchów w głąb, w Reversi pięć, a w Mancali dziewięć. Ponieważ przeszukiwanie kończy się wcześnie, komputer nie gra idealnie i dlatego da się go pokonać: zastaw pułapkę, która zadziała dopiero za jego horyzontem.
Osobna gałąź, kombinatoryczna teoria gier, bada właśnie takie gry z pełną informacją i bez losowości, jak Nim, końcówki w go czy Hex. Zaczęła się od rozwiązania gry Nim przez Charlesa Boutona w 1901 roku i jest innym przedmiotem niż opisana wyżej ekonomiczna teoria gier, choć obie łączy rozumowanie od końca gry.
Częste nieporozumienia
- „Teoria gier zakłada, że wszyscy są samolubni”. Zakłada, że gracze dążą do swoich wypłat, ale wypłaty mogą obejmować troskę o innych, poczucie sprawiedliwości czy reputację. Teoria mówi, jak działać przy danych wartościach, a nie, co należy cenić.
- „Równowaga to najlepszy wynik”. Niekoniecznie. Dylemat więźnia pokazuje równowagę gorszą dla wszystkich niż inny możliwy wynik.
- „Ludzie grają tak, jak przewiduje teoria”. Często nie. W eksperymentach takich jak gra w ultimatum ludzie odrzucają niesprawiedliwe oferty, choć odrzucenie kosztuje ich pieniądze. Te różnice bada behawioralna teoria gier.
- „To tylko dla matematyków”. Główne idee (gracze, strategie, wypłaty, myślenie o odpowiedzi drugiej strony) nie wymagają żadnej matematyki i pasują do każdej decyzji, w której biorą udział inni ludzie.
Najczęściej zadawane pytania
Czym jest teoria gier w prostych słowach?
Teoria gier to matematyka decyzji, których skutek zależy od decyzji innych. Opisuje sytuację jako graczy, strategie, które każdy może wybrać, i wypłaty dla każdej kombinacji wyborów, a potem pyta, co rozsądny gracz powinien zrobić i jakiego wyniku się spodziewać.
Kto wymyślił teorię gier?
Za twórcę uważa się matematyka Johna von Neumanna. W 1928 roku udowodnił twierdzenie minimaksowe, a jego książka Theory of Games and Economic Behavior z 1944 roku, napisana z ekonomistą Oskarem Morgensternem, uczyniła z teorii gier osobną dziedzinę. Wcześniejsze ważne prace napisali Ernst Zermelo (1913) i Emile Borel (1921).
Co to jest równowaga Nasha?
Równowaga Nasha to taki zestaw strategii, w którym żaden gracz nie może poprawić swojego wyniku, zmieniając tylko własny wybór, gdy pozostali trzymają się swoich. John Nash udowodnił w 1950 roku, że każda skończona gra ma co najmniej jedną taką równowagę, jeśli gracze mogą losować swoje wybory.
Do czego służy teoria gier?
Stosuje się ją przy projektowaniu aukcji i systemów przydziału (np. lekarzy rezydentów do szpitali i wymiany nerek), w analizie konkurencji firm, wyścigu zbrojeń i negocjacji, w biologii do wyjaśniania współpracy i konfliktów zwierząt, przy planowaniu patroli ochrony oraz w sztucznej inteligencji grającej w szachy czy pokera.
Czy teoria gier dotyczy gier komputerowych?
Nie. Grą w teorii gier jest każda sytuacja, w której kilku decydentów wpływa na swoje wyniki, na przykład wojna cenowa albo negocjacje. Gry planszowe i komputerowe to tylko mały przykład, choć to właśnie zasada minimaks z teorii gier pozwala komputerowi wybierać ruchy w grach takich jak Cztery w rzędzie czy warcaby.
