Granie w system

Ty i wspólnik w dużym napadzie zostałeś złapany przez gliny i jesteście przesłuchiwani w osobnych pokojach. Jeśli oboje będziecie milczeć o przestępstwie, dostaniecie rok więzienia za mniejszą opłatą. Jeśli oboje piszczycie, każdy dostanie pięć lat. Ale jeśli tylko jedno z was pisnie, to jedno wyjdzie na wolność, podczas gdy drugie dostanie 10 lat. Jeśli nie wiesz, co zrobi twój wspólnik, jaka jest racjonalna decyzja?

Asuman Ozdaglar

Ta zagadka, znana jako dylemat więźnia, jest najbardziej znanym przykładem gry w sensie technicznym stosowanym przez teoretyków gier. Teoria gier to matematyczny sposób opisu rozumowania strategicznego, a dylemat więźnia ilustruje trzy podstawowe wymagania dotyczące sytuacji, które obejmuje: gra musi obejmować wielu agentów (tutaj dwóch wspólników); każdy musi podjąć decyzję (pisz lub nie pisz); a każda decyzja musi wiązać się z wymierną wypłatą (warunki więzienia), która różni się w zależności od decyzji innych agentów.

Teoria gier jest podstawą badań ekonomicznych od 1950 roku, kiedy John Nash, który wykładał na MIT w latach 1951-1959 i jest bohaterem filmu Piękny umysł , opublikowała nasienny papieru to zapewniłoby mu Nagrodę Nobla w dziedzinie ekonomii. Gdy teoria gier dojrzała, stała się jeszcze bardziej centralna w tej dziedzinie. Tylko w ciągu ostatnich ośmiu lat Nagroda Nobla trafiła trzykrotnie do teoretyków gier za rzucenie światła między innymi na logikę odstraszania nuklearnego, okoliczności, w których wolny rynek może i nie może maksymalizować dobrobyt publiczny oraz najlepsze rozwiązania dopasowanych problemów — narządy i pacjenci, rezydenci medyczni i szpitale i tym podobne.

Ale ostatnio teoria gier przyciąga uwagę także w inżynierii i informatyce. Naukowcy używają go do analizowania drażliwych problemów, takich jak optymalizacja przepływu ruchu lub zapobieganie przerwom w dostawie prądu.

Asuman Ozdaglar, SM ’98, PhD ’03, profesor elektrotechniki i informatyki, mówi, że rozwój Internetu uczynił to koniecznym. Historycznie inżynierowie sieci komunikacyjnych musieli zmagać się z szerokim zakresem pytań technicznych, takich jak ograniczenia mocy i względne zalety centralizacji lub decentralizacji. Ale z Internetem nagle musieli zmierzyć się również z ludzką agencją.

Jeśli subskrybent Comcast w Bostonie i subskrybent EarthLink w San Francisco wymieniają dane, ich transmisje są przesyłane przez sieci obsługiwane przez kilku różnych dostawców: Comcast, EarthLink i innych pomiędzy. Cała operacja opiera się zarówno na współpracy, jak i rywalizacji tych różnych stron, mówi Ozdaglar. Jak zaprojektować protokoły, które faktycznie zapewnią odpowiednią zachętę ludziom do współpracy? Innymi słowy: dlaczego Internet działa, mimo że składa się z pojedynczych sieci? Teoria gier dostarcza sposobu na odpowiedź na tego rodzaju pytania.

Gdy inżynierowie zaczęli wprowadzać teorię gier w odpowiedzi na pytania z ich dziedziny, zdali sobie jednak również sprawę, że narzędzia ich rzemiosła mają zastosowanie do nierozstrzygniętych kwestii teorii gier. Rzeczywiście, z garstki badaczy z Wydziału Inżynierii Elektrycznej i Informatyki (EECS), którzy intensywnie zajmują się teorią gier, wszyscy spędzili dużo czasu na pytaniach, które są bardziej typowe dla nauk społecznych.

Idę raz
Dobrym przykładem jest profesor EECS Constantinos Daskalakis. W 2008 roku zdobył nagrodę rozprawy Association for Computing Machinery, pokazując, w jaki sposób techniki zaczerpnięte z teoretycznej informatyki mogą rzucić nowe światło na jedno z głównych pojęć w teorii gier: równowagę.

Constantinos Daskalakis

Równowaga to idea, dzięki której Nash otrzymał Nobla, a równowaga Nasha jest najczęściej badanym typem równowagi. Opisuje równowagę strategii, której żaden gracz w grze nie ma motywacji do jednostronnej zmiany. Najbardziej podstawowy przykład równowagi Nasha obejmuje tak zwaną grę rzutów karnych. W piłce nożnej rzut karny daje ofensywnemu graczowi rzut wolny na bramkę, gdy tylko bramkarz broni. Piłka leci tak szybko, że bramkarz musi odgadnąć, w którą stronę skoczyć, zanim zostanie uderzona. W wersji gry teoretycznej, jeśli obaj gracze wybiorą tę samą połowę bramki, bramkarz wygrywa; jeśli wybiorą różne połówki, strzelec wygrywa.

Stan równowagi w tej grze polega na tym, aby obaj gracze losowo wybierali kierunek przy każdym kopnięciu, ale aby upewnić się, że ogólnie wybierają oba kierunki z taką samą częstotliwością. W takim przypadku każdy z nich wygra połowę czasu i żaden z nich nie może poprawić swoich szans, odchodząc od tej strategii. Na przykład, gdyby bramkarz za każdym razem zaczął jechać w tym samym kierunku, a strzelec trzymał się oryginalnej strategii, procent wygranych bramkarza po prostu pozostałby taki sam. Jednak strzelec, który zauważył zmianę, może wygrać każdy kopnięcie, idąc za każdym razem w przeciwnym kierunku, więc bramkarz nie ma motywacji do dokonania tej zmiany.

Ale gra w rzuty karne jest jedną z najprostszych gier. Znalezienie równowagi dla nawet nieco bardziej złożonych gier może być niezwykle trudne. W swojej rozprawie Daskalakis udowodnił, że w niektórych sytuacjach, które można opisać za pomocą teorii gier, równowaga Nasha jest tak trudna do obliczenia, że ​​wszystkie komputery na świecie nie mogły jej znaleźć w ciągu życia wszechświata. W takich przypadkach, przekonuje Daskalakis, ludzie prawdopodobnie również nie znaleźli tego metodą prób i błędów. Oznacza to, że teoretycy gier potrzebują narzędzi analitycznych innych niż równowaga Nasha, jeśli chcą mieć nadzieję na opisanie rzeczywistego świata.

Na szczęście w ten sam sposób, w jaki informatyka opracowała zestaw technik określania złożoności obliczeń, takich jak te, które tworzą równowagę Nasha, opracowała również zestaw technik do identyfikacji przybliżonych rozwiązań problemów, które w przeciwnym razie byłyby trudne do rozwiązania. Na przykład Daskalakis i jego uczniowie byli w stanie znaleźć rozwiązanie dla problemu ekonomicznego, który trwał od 30 lat.

W 1981 roku Roger Myerson z University of Chicago pokazał, jak zorganizować aukcję pojedynczego przedmiotu, tak aby jeśli wszyscy licytujący przyjęli strategie licytacji w ich najlepszym interesie, sprzedający osiągnąłby największy zysk. Ta praca pomogła mu zdobyć Nagrodę Nobla w 2007 roku. Pojawiło się również powiązane pytanie: jaki jest najlepszy sposób na zorganizowanie aukcji dla więcej niż jednego przedmiotu? (W żargonie ekonomistów każdy rynek z jednym sprzedawcą i wieloma kupującymi liczy się jako aukcja; aukcja Christie's to jedna, ale też sprzedaż w sklepie detalicznym). To pytanie o tak dużej złożoności, że nie ma zwięzłego opisu aukcja, która daje optymalny zysk, mówi Daskalakis. Aby zmaksymalizować przychody z wielu przedmiotów, sprzedawca prawdopodobnie musi sprzedać każdy przedmiot po cenie niższej niż najwyższa, jaką ktoś byłby w stanie zapłacić. Ale zniżka różni się w zależności od czynników, takich jak mieszanka sprzedawanych przedmiotów i populacja, z której pochodzą kupujący.

Informatyka oferuje świeże spojrzenie na problem — to, co Daskalakis nazywa perspektywą aproksymacji. Może nie jesteś w stanie znaleźć optymalnej aukcji, mówi, ale aukcja, która gwarantuje 99 procent najlepszych przychodów, jest również dobrą aukcją. Daskalakis i jego uczniowie wykazali, że dla każdego rynku składającego się z wielu przedmiotów, idealną aukcję — taką, która maksymalizuje dochód sprzedającego — można by przybliżyć przez kombinację wyników prostszych aukcji.

Nieco inne podejście do problemów aukcyjnych charakteryzuje praca profesora inżynierii Silvio Micali. On i profesor EECS Shafi Goldwasser są ostatnimi laureatami nagrody Turinga, najwyższej nagrody w dziedzinie informatyki. W dużej mierze nagroda honoruje ich pracę nad tzw. dowodami interaktywnymi, w których pytający o ograniczonych zasobach obliczeniowych próbuje uzyskać wynik obliczenia od niewiarygodnego rozmówcy o nieograniczonych zasobach obliczeniowych. Jednym z przykładów jest dowód z wiedzą zerową, w którym jeden z uczestników ustala posiadanie informacji, takiej jak klucz kryptograficzny, nie ujawniając, co to jest. Dowody z wiedzą zerową służą do zabezpieczania transakcji między instytucjami finansowymi, a kilka startupów powstało w celu ich komercjalizacji.

Micali prowadzi kilka projektów badawczych w zakresie teorii gier, ale jeden z nich jest bardzo zbliżony duchem do dowodów z wiedzą zerową. W wielu aukcjach publicznych – jak na przykład, gdy rząd federalny sprzedaje niewykorzystane widmo radiowe firmom telekomunikacyjnym – licytator jest zobowiązany do ujawnienia ofert wszystkich uczestników ze względu na przejrzystość. Dla firmy, która bierze udział w takiej aukcji i przegrywa, to naprawdę najgorszy ze wszystkich możliwych wyników, mówi Micali. Twoi konkurenci wiedzą teraz, jak bardzo cenisz tę rzecz, z czego mogą wywnioskować, jak dużą klientelę obsługujesz lub jaką technologię masz dostępną.

Dlatego grupa Micali opracowuje aukcje, w których uczestnicy mogą publicznie ujawnić wystarczającą ilość informacji o swoich ofertach, aby wyłonić zwycięzcę, bez ujawniania samych ofert. Wierzę, że w końcu stanie się to głównym nurtem teorii gier, mówi Micali. Nie można naprawdę mieć sensownej nauki o ludzkim zachowaniu, lekceważąc prywatność.

Kto rządzi?
W wielu sytuacjach, które można wyrazić jako gry, równowaga Nasha może być, jak pokazał Daskalakis, prawie niemożliwa do obliczenia. Ale to nie znaczy, że zachowanie graczy jest przypadkowe. Rozważ siatkę ulic miasta, gdzie kierowcy podejmują niezliczone decyzje na dziesiątkach skrzyżowań. Nawet jeśli kierowcy nie oceniają wszystkich możliwych konsekwencji alternatywnych decyzji, nadal stosują proste strategie — powiedzmy, jeśli zbyt długo siedzisz w bezruchu, skręć w boczną uliczkę. Według Munthera Dahleha, zastępcy szefa EECS, analiza takich systemów bardzo zbliża teorię gier do jego własnej dziedziny, teorii sterowania, która bada strategie kontrolowania dynamicznych systemów, takich jak kończyny robotów i skrzydła samolotów. Mamy inne spojrzenie na te problemy, mówi Dahleh. W przeciwieństwie do narzucania pojęcia równowagi i mówienia „Jakie strategie graliby ludzie przy tej równowadze?”, przyglądamy się kontrolowanemu zachowaniu dynamicznemu i zadajemy pytanie „Jakie pojęcie równowagi się pojawia?”

Dahleh rzeczywiście zastosował narzędzia teorii gier do analizy przepływu ruchu, badając typy układów dróg, które najlepiej uwzględniają zamykanie poszczególnych tras. Jego podejście odnosi się również do innych wielkoskalowych systemów dynamicznych, takich jak sieć energetyczna.

Każdego dnia producenci energii – operatorzy elektrowni jądrowych, węglowych, wiatrowych i tym podobnych – oferują nowe harmonogramy dotyczące tego, ile energii elektrycznej są w stanie wyprodukować, za jaką cenę i o jakich porach dnia. Przedsiębiorstwa dostarczające energię elektryczną mają również administratorów, którzy na podstawie oczekiwanego zapotrzebowania konsumentów decydują, ile energii kupić od każdego dostawcy. Produkcja i zużycie energii muszą dokładnie odpowiadać, w przeciwnym razie konsekwencje będą katastrofalne.

Wykorzystując narzędzia teorii gier do analizy motywacji zarówno dostawców energii, jak i konsumentów, dr Dahleh i Mardavij Roozbehani, główny naukowiec w Laboratorium Systemów Informacyjnych i Decyzyjnych, wykazali, że inteligentne liczniki w domu, które mogą zapewnić informacje o cenach spot na rynku energii elektrycznej i umożliwienie konsumentom odkładania energochłonnych zadań domowych do czasu, gdy będą one najbardziej przystępne, może w rzeczywistości spowodować skoki popytu, które spowodują awarię całej sieci.

Dahleh współpracowała również z Ozdaglar i jej mężem, ekonomistą MIT Daronem Acemoglu, aby przeanalizować, w jaki sposób informacje rozprzestrzeniają się w populacjach. Gra w tym przypadku to taka, w której ludzie ważą prawdę lub fałsz informacji, które do nich docierają, dążąc do maksymalizacji trafności własnych przekonań.

Są to pytania, które badano zarówno w socjologii, jak i ekonomii, mówi Ozdaglar. Tradycyjnie jednak badania te zakładały, że każda osoba w danej populacji może otrzymywać informacje bezpośrednio od dowolnej innej. To, co inżynierowie oferują, twierdzi Ozdaglar, to dobrze dopracowane narzędzia do analizy podstawowej struktury sieciowej populacji. Na przykład większość ludzi w rzeczywistości otrzymuje większość swoich informacji od zaledwie kilku bezpośrednich sąsiadów w sieci — i przypisują różne prawdopodobieństwa trafności twierdzeń różnych sąsiadów.

Myślę, że w przeszłości nauki społeczne i ekonomia zajmowały się problemami inaczej niż inżynierowie, mówi Dahleh. Teraz wszyscy mówimy o sieciach społecznościowych – decyzje w sieciach społecznościowych, dynamika w sieciach – więc myślę, że te dwie dziedziny się zbiegają.

ukryć