Hraní systému

Vy a spolupachatel velké loupeže byli dopadeni policisty a jste vyslýcháni v oddělených místnostech. Pokud budete oba o zločinu mlčet, každý dostanete rok vězení za nižší obvinění. Pokud budete oba kňučet, dostanete každý pět let. Ale pokud jen jeden z vás zakňučí, ten bude volný, zatímco druhý dostane 10 let. Pokud nevíte, co váš komplic udělá, jaké je racionální rozhodnutí?

Asuman Ozdaglar

Tento hlavolam, známý jako vězeňovo dilema, je nejznámějším příkladem hry v technickém smyslu používaném teoretiky her. Teorie her je matematický způsob, jak popsat strategické uvažování, a vězeňovo dilema ilustruje tři základní požadavky situací, které zahrnuje: hra musí zahrnovat více agentů (zde dva spolupachatele); každý se musí rozhodnout (pískat nebo nekřičet); a každé rozhodnutí musí nést kvantifikovatelnou odměnu (vězeňské podmínky), která se liší podle rozhodnutí ostatních agentů.

Teorie her je základem ekonomického výzkumu od roku 1950, kdy John Nash, který učil na MIT v letech 1951 až 1959 a je předmětem filmu Nádherná mysl , zveřejnila klíčový papír to by mu vyneslo Nobelovu cenu za ekonomii. Jak teorie her dozrála, stala se v této oblasti ještě důležitější. Jen za posledních osm let byla Nobelova cena udělena herním teoretikům třikrát za to, že osvětlila mimo jiné logiku jaderného odstrašování, okolnosti, za nichž volné trhy mohou a nemohou maximalizovat veřejný blahobyt, a nejlepší řešení. k odpovídajícím problémům – orgánům a pacientům, lékařům a nemocnicím a podobně.

Teorie her však v poslední době přitahuje pozornost také ve strojírenství a informatice. Výzkumníci jej využívají k analýze ožehavých problémů, jako je optimalizace dopravního proudu nebo prevence výpadků proudu.

Asuman Ozdaglar, SM '98, PhD '03, profesor elektrotechniky a informatiky, říká, že vzestup internetu si to vynutil. Historicky se inženýři komunikačních sítí museli potýkat s širokou škálou technických otázek – jako jsou omezení výkonu a relativní přednosti centralizace nebo decentralizace. Ale s internetem se najednou museli vypořádat i s lidským jednáním.

Pokud si předplatitel Comcast v Bostonu a předplatitel EarthLink v San Franciscu vyměňují data, jejich přenosy putují po sítích spravovaných několika různými poskytovateli: Comcast, EarthLink a další mezi nimi. Celá operace závisí jak na spolupráci, tak na konkurenci těchto různých stran, říká Ozdaglar. Jak navrhujete protokoly, které skutečně poskytnou lidem ty správné pobídky ke spolupráci? Jinými slovy: proč internet funguje, i když je tvořen jednotlivými sítěmi? Teorie her poskytuje způsob, jak odpovědět na takovou otázku.

Když inženýři začali uplatňovat teorii her v otázkách ve svém oboru, uvědomili si také, že nástroje jejich obchodu lze použít i na nevyřešené otázky teorie her. Opravdu, z hrstky výzkumníků na katedře elektrotechniky a informatiky (EECS), kteří se intenzivně zabývají teorií her, všichni strávili značný čas otázkami, které jsou typicky řešeny společenskými vědami.

Jdu jednou
Profesor EECS Constantinos Daskalakis je dobrým příkladem. V roce 2008 získal cenu Asociace pro výpočetní techniku ​​za dizertační práci za to, že ukázal, jak by techniky získané z teoretické informatiky mohly vrhnout nové světlo na jeden z ústředních konceptů teorie her: rovnováhu.

Constantinos Daskalakis

Rovnováha je myšlenka, která Nashovi vynesla Nobelovu cenu, a Nashova rovnováha je typ rovnováhy, který se nejčastěji studuje. Popisuje rovnováhu strategií, kterou žádný hráč hry nemá motiv jednostranně měnit. Nejzákladnějším příkladem Nashovy rovnováhy je takzvaná hra na pokutové kopy. Ve fotbale poskytuje pokutový kop ofenzivnímu hráči volnou střelu na branku, přičemž brání pouze brankář. Míč cestuje tak rychle, že brankář musí uhodnout, kterým směrem se má ponořit, než bude zasažen. V teoretické verzi, pokud oba hráči vyberou stejnou polovinu branky, vyhrává brankář; pokud vyberou různé poloviny, vyhrává střelec.

Rovnovážný stav pro tuto hru spočívá v tom, že oba hráči si náhodně vyberou směr při jakémkoli daném kopu, ale aby se zajistilo, že celkově zvolí oba směry se stejnou frekvencí. V takovém případě vyhraje každý polovinu času a žádný z nich nemůže zlepšit své šance tím, že se od této strategie odchýlí. Pokud by například brankář najednou začal jít pokaždé stejným směrem a střelec by se držel původní strategie, procento výher brankáře by zůstalo stejné. Střelec, který si všiml posunu, však mohl vyhrát každý kop tím, že by šel pokaždé opačným směrem, takže brankář nemá žádnou motivaci k této změně.

Ale pokutové kopy jsou jednou z nejjednodušších her. Najít rovnováhu pro i trochu složitější hry může být nesmírně obtížné. Daskalakis ve své dizertační práci dokázal, že pro některé situace, které lze popsat pomocí teorie her, je Nashova rovnováha tak těžko vypočítatelná, že ji všechny počítače na světě za dobu existence vesmíru nenajdou. V těchto případech, tvrdí Daskalakis, to lidé pravděpodobně také nenašli metodou pokusů a omylů. To znamená, že herní teoretici potřebují jiné analytické nástroje než Nashovu rovnováhu, pokud chtějí nějakou naději popsat skutečný svět.

Naštěstí stejným způsobem, jakým počítačová věda vyvinula sadu technik pro určování složitosti výpočtů, jako jsou ty, které vytvářejí Nashovy rovnováhy, vyvinula také sadu technik pro identifikaci přibližných řešení jinak neřešitelných problémů. Daskalakis a jeho studenti například dokázali najít jeden pro ekonomický problém, který trval 30 let.

V roce 1981 Roger Myerson z Chicagské univerzity ukázal, jak strukturovat aukci pro jednu položku tak, že pokud všichni dražitelé přijmou nabídkové strategie ve svém nejlepším zájmu, prodávající dosáhne největšího zisku. Tato práce mu pomohla získat Nobelovu cenu za rok 2007. Také vyvolal související otázku: jaký je nejlepší způsob, jak strukturovat aukci pro více než jednu položku? (Ve žargonu ekonomů se jako aukce počítá každý trh s jedním prodávajícím a více kupujícími; aukce Christie's je jednou z nich, ale také prodeje v maloobchodě.) Je to otázka s tak velkou složitostí, že pro ni neexistuje žádný stručný popis aukce, která vám poskytne optimální zisk, říká Daskalakis. Chcete-li maximalizovat výnosy z více položek, prodejce pravděpodobně musí prodat každou položku za nižší cenu, než je nejvyšší cena, kterou by byl někdo ochoten zaplatit. Sleva se však liší v závislosti na faktorech, jako je mix prodávaných položek a populace, ze kterých jsou kupující čerpáni.

Počítačová věda nabízí nový pohled na problém – to, co Daskalakis nazývá perspektivou aproximace. Možná nemůžete najít optimální aukci, říká, ale aukce, která zaručuje 99 procent nejlepších výnosů, je také dobrá aukce. Daskalakis a jeho studenti ukázali, že pro jakýkoli trh s více položkami by ideální aukce – ta, která maximalizovala tržby prodejce – mohla být aproximována kombinací výsledků jednodušších aukcí.

Poněkud odlišný přístup k aukčním problémům charakterizuje práci profesora inženýrství Silvia Micaliho. On a profesor EECS Shafi Goldwasser jsou nejnovějšími držiteli Turingovy ceny, nejvyššího ocenění v oblasti informatiky. Ocenění z velké části oceňuje jejich práci na tzv. interaktivních důkazech, kdy se tazatel s omezenými výpočetními zdroji snaží vymámit výsledek výpočtu od nespolehlivého partnera s neomezenými výpočetními zdroji. Jedním z příkladů je důkaz s nulovými znalostmi, ve kterém jeden z účastníků prokáže, že má určitou informaci, jako je kryptografický klíč, aniž by prozradil, co to je. Důkazy s nulovými znalostmi se používají k zabezpečení transakcí mezi finančními institucemi a bylo založeno několik startupů, které je komercializovaly.

Micali se věnuje několika herně-teoretickým výzkumným projektům, ale jeden z nich je duchem velmi blízký důkazům o nulových znalostech. V mnoha veřejných aukcích – jako například když federální vláda draží nevyužité rádiové spektrum telekomunikačním společnostem – je dražitel povinen z důvodu transparentnosti zveřejnit nabídky všech účastníků. Pro společnost, která se účastní takové aukce a prohraje, je to opravdu nejhorší ze všech možných výsledků, říká Micali. Vaši konkurenti nyní vědí, jak moc si této věci ceníte, z čehož mohou odvodit, jak velké klientele obsluhujete nebo jakou technologii máte k dispozici.

Skupina Micali tedy vyvíjí aukce, ve kterých mohou účastníci zveřejnit dostatek informací o svých nabídkách, aby mohli rozhodnout o vítězi, aniž by odhalovali samotné nabídky. Věřím, že se to nakonec stane hlavním proudem v teorii her, říká Micali. Nemůžete skutečně mít smysluplnou vědu o lidském chování a ignorovat soukromí.

kdo to řídí?
Pro mnoho situací, které lze vyjádřit jako hry, může být Nashova rovnováha, jak ukázal Daskalakis, téměř nemožné vypočítat. To ale neznamená, že chování hráčů je náhodné. Vezměme si síť městských ulic, kde řidiči dělají nespočet rozhodnutí na desítkách křižovatek. I když řidiči nevyhodnocují všechny možné důsledky alternativních rozhodnutí, stále si osvojují několik jednoduchých strategií – řekněme, pokud sedíte příliš dlouho na místě, odbočte do vedlejší ulice. Podle Munthera Dahleha, zástupce vedoucího EECS, analýza takových systémů přibližuje teorii her velmi blízko jeho vlastnímu oboru, teorii řízení, která zkoumá strategie pro ovládání dynamických systémů, jako jsou končetiny robotů a křídla letadel. Máme na tyto problémy jiný pohled, říká Dahleh. Na rozdíl od vnucování pojmu rovnováhy a tvrzení ‚Jaké strategie by lidé v této rovnováze hráli?‘ se podíváme na řízené dynamické chování a položíme otázku ‚Jaký pojem rovnováhy vzniká?‘

Dahleh skutečně aplikoval nástroje teorie her na analýzu dopravního proudu a zkoumal typy rozvržení silnic, které mohou nejlépe vyhovět uzavření konkrétních tras. Jeho přístup platí i pro další rozsáhlé dynamické systémy, jako je elektrická síť.

Každý den výrobci elektřiny – provozovatelé jaderných elektráren, uhelných elektráren, větrných elektráren a podobně – nabízejí nové plány, kolik elektřiny jsou ochotni vyrobit, za jakou cenu a v kterou denní dobu. Energetické společnosti, které dodávají elektřinu, mají také své administrátory, kteří na základě očekávané poptávky spotřebitelů rozhodují o tom, kolik energie od jednotlivých poskytovatelů nakoupí. Výroba a spotřeba energie se musí přesně shodovat, jinak budou následky katastrofální.

Dahleh a Mardavij Roozbehani, PhD '08, hlavní výzkumní pracovníci v Laboratoři pro informační a rozhodovací systémy, použili nástroje teorie her k analýze pobídek jak poskytovatelů energie, tak spotřebitelů, ukázali, že inteligentní měřiče v domácnosti, které mohou poskytnout informace o spotových cenách na trhu s elektřinou a umožnit spotřebitelům odložit energeticky náročné úkoly v domácnosti, dokud nebudou cenově nejdostupnější, by ve skutečnosti mohly způsobit skoky v poptávce, které by srazily celou síť.

Dahleh také spolupracovala s Ozdaglarem a jejím manželem, ekonomem MIT Daronem Acemoglu, na analýze toho, jak se informace šíří mezi populacemi. Hra je v tomto případě hra, ve které lidé zvažují pravdivost nebo nepravdivost informací, které se k nim dostanou, když se snaží maximalizovat přesnost svých vlastních přesvědčení.

To jsou otázky, které byly studovány jak v sociologii, tak v ekonomii, říká Ozdaglar. Tradičně však tato vyšetřování předpokládala, že kterákoli osoba v dané populaci může přijímat informace přímo od jakékoli jiné. To, co inženýři nabízejí, tvrdí Ozdaglar, jsou dobře vypilované nástroje pro analýzu základní síťové struktury populace. Většina lidí například ve skutečnosti přijímá většinu svých informací od několika bezprostředních sousedů v síti – a přesnosti tvrzení různých sousedů přiřazují různé pravděpodobnosti.

V minulosti si myslím, že společenské vědy a ekonomie řešily problémy jinak než inženýři, říká Dahleh. Teď všichni mluvíme o sociálních sítích – rozhodnutí v sociálních sítích, dynamika na sítích – takže si myslím, že se tyto dvě oblasti sbližují.

skrýt