Sistēmas spēlēšana

Policisti aizturēja jūs un līdzdalībnieci lielā laupīšanā un tiek pratināti atsevišķās telpās. Ja jūs abi klusēsit par noziegumu, jūs katrs saņemsiet gadu cietumā par mazāku apsūdzību. Ja jūs abi čīkstat, jūs katrs saņemsiet piecus gadus. Bet, ja tikai viens no jums čīkst, viņš tiks atbrīvots, bet otrs saņems 10 gadus. Ja jūs nezināt, ko darīs jūsu līdzdalībnieks, kāds ir racionāls lēmums?





Asumans Ozdaglars

Asumans Ozdaglars

Šī mīkla, kas pazīstama kā ieslodzīto dilemma, ir vispazīstamākais spēles piemērs tehniskajā nozīmē, ko izmanto spēļu teorētiķi. Spēles teorija ir matemātisks veids, kā aprakstīt stratēģisko spriešanu, un ieslodzītā dilemma ilustrē trīs pamatprasības tajā ietvertajām situācijām: spēlē ir jāiesaista vairāki aģenti (šeit, divi līdzdalībnieki); katram jāpieņem lēmums (čīkst vai nečīkst); un katram lēmumam ir jāsniedz izmērāma atlīdzība (ieslodzījuma termiņi), kas mainās atkarībā no citu aģentu lēmumiem.

Spēļu teorija ir bijusi ekonomikas izpētes pamats kopš 1950. gada, kad Džons Nešs, kurš mācīja MIT no 1951. līdz 1959. gadam un ir filmas priekšmets. Brīnišķīgais prāts , publicēja sēklas papīrs kas viņam piešķirtu Nobela prēmiju ekonomikā. Spēļu teorijai attīstoties, tā ir kļuvusi vēl svarīgāka šajā jomā. Tikai pēdējo astoņu gadu laikā Nobela prēmija trīs reizes ir saņēmusi spēļu teorētiķus, cita starpā par to, ka viņi ir izgaismojuši kodolieroču atturēšanas loģiku, apstākļus, kādos brīvie tirgi var un nevar palielināt sabiedrības labklājību, un labākos risinājumus. saskaņošanas problēmas — orgāni un pacienti, medicīnas rezidenti un slimnīcas un tamlīdzīgi.



Taču pēdējā laikā spēļu teorija ir pievērsusi uzmanību arī inženierzinātnēs un datorzinātnēs. Pētnieki to izmanto, lai analizētu sarežģītas problēmas, piemēram, satiksmes plūsmas optimizēšanu vai elektroenerģijas padeves pārtraukumu novēršanu.

Asumans Ozdaglars, SM '98, PhD '03, elektrotehnikas un datorzinātņu profesors, saka, ka interneta attīstība ir radījusi to nepieciešamību. Vēsturiski sakaru tīklu inženieriem bija jācīnās ar plašu tehnisko jautājumu loku, piemēram, jaudas ierobežojumiem un centralizācijas vai decentralizācijas relatīvajiem ieguvumiem. Bet, izmantojot internetu, viņiem pēkšņi bija jārisina arī cilvēku spēja.

Ja Comcast abonents Bostonā un EarthLink abonents Sanfrancisko apmainās ar datiem, viņu pārraide tiek pārraidīta pa tīkliem, ko uztur vairāki dažādi pakalpojumu sniedzēji: Comcast, EarthLink un citi. Visa darbība ir atkarīga gan no šo dažādo pušu sadarbības, gan konkurences, saka Ozdaglar. Kā jūs izstrādājat protokolus, kas patiešām dos pareizos stimulus cilvēkiem sadarboties? Citiem vārdiem sakot: kāpēc internets darbojas, lai gan to veido atsevišķi tīkli? Spēļu teorija sniedz veidu, kā atbildēt uz šāda veida jautājumiem.



Kad inženieri sāka izmantot spēļu teoriju, lai risinātu jautājumus savā jomā, viņi arī saprata, ka viņu aroda instrumenti ir piemērojami neatrisinātiem spēļu teorijas jautājumiem. Patiešām, no nedaudzajiem Elektrotehnikas un datorzinātņu departamenta (EECS) pētniekiem, kuri plaši strādā pie spēļu teorijas, visi ir pavadījuši daudz laika, lai risinātu jautājumus, kurus parasti risina sociālās zinātnes.

Eju vienreiz
Labs piemērs ir EECS profesors Constantinos Daskalakis. 2008. gadā viņš ieguva Datortehnikas asociācijas disertācijas balvu, parādot, kā teorētiskās datorzinātnes metodes var radīt jaunu gaismu vienam no spēļu teorijas galvenajiem jēdzieniem: līdzsvaram.

Konstantīns Daskalakis

Konstantīns Daskalakis



Līdzsvars ir ideja, kas Nešam ieguva savu Nobelu, un Neša līdzsvars ir visbiežāk pētītais līdzsvara veids. Tas apraksta stratēģiju līdzsvaru, kuru nevienam spēles spēlētājam nav motīva vienpusēji mainīt. Visvienkāršākais Neša līdzsvara piemērs ir tā sauktā soda sitienu spēle. Futbolā soda sitiens dod uzbrūkošam spēlētājam brīvu metienu pa vārtiem, tikai vārtsargam aizsargājoties. Bumbiņa pārvietojas tik ātri, ka vārtsargam ir jāuzmin, kurā virzienā jānirst, pirms tā tiek sitiena. Spēles teorētiskajā versijā, ja abi spēlētāji izvēlas vienu un to pašu vārtu pusi, uzvar vārtsargs; ja viņi izvēlas dažādas pusītes, uzvar šāvējs.

Šīs spēles līdzsvara stāvoklis ir tāds, ka abi spēlētāji nejauši izvēlas virzienu jebkuram konkrētajam sitienam, bet lai nodrošinātu, ka kopumā viņi izvēlas abus virzienus ar vienādu biežumu. Tādā gadījumā viņi katrs uzvarēs pusi laika, un neviens nevarēs uzlabot savas izredzes, atkāpjoties no šīs stratēģijas. Piemēram, ja vārtsargs pēkšņi katru reizi sāktu iet vienā virzienā un šāvējs pieturas pie sākotnējās stratēģijas, vārtsarga uzvaras procents paliktu nemainīgs. Tomēr šāvējs, kurš pamanīja maiņu, varēja uzvarēt katru sitienu, katru reizi ejot pretējā virzienā, tāpēc vārtsargam nav stimula veikt šīs izmaiņas.

Taču soda sitienu spēle ir viena no vienkāršākajām spēlēm. Līdzsvara atrašana pat nedaudz sarežģītākām spēlēm var būt ārkārtīgi sarežģīta. Savā disertācijā Daskalakis pierādīja, ka dažām situācijām, kuras var aprakstīt ar spēļu teorijas palīdzību, Neša līdzsvaru ir tik grūti aprēķināt, ka visi pasaules datori to nevarēja atrast Visuma dzīves laikā. Šajos gadījumos, apgalvo Daskalakis, cilvēki, iespējams, to nav atraduši arī izmēģinājumu un kļūdu ceļā. Tas nozīmē, ka spēļu teorētiķiem ir nepieciešami citi analītiskie rīki, nevis Neša līdzsvars, ja viņi vēlas kādu cerību aprakstīt reālo pasauli.



Par laimi, tāpat kā datorzinātne ir izstrādājusi virkni metožu, lai noteiktu aprēķinu sarežģītību, piemēram, tādus, kas rada Neša līdzsvaru, tā ir izstrādājusi arī metožu kopumu, lai identificētu aptuvenus risinājumus citādi neatrisināmām problēmām. Daskalakis un viņa studenti, piemēram, spēja atrast vienu ekonomikas problēmai, kas bija pastāvējusi 30 gadus.

1981. gadā Čikāgas Universitātes Rodžers Maijersons parādīja, kā strukturēt izsoli vienai precei tā, lai, ja visi solītāji izvēlētos solīšanas stratēģijas savās interesēs, pārdevējs gūtu vislielāko peļņu. Šis darbs palīdzēja viņam nopelnīt 2007. gada Nobela prēmiju. Tas arī izvirzīja saistītu jautājumu: kāds ir labākais veids, kā strukturēt izsoli vairāk nekā vienai precei? (Ekonomistu žargonā runājot, jebkurš tirgus, kurā ir viens pārdevējs un vairāki pircēji, tiek uzskatīts par izsoli; Christie's izsole ir viena, taču tā ir arī pārdošana mazumtirdzniecības veikalā.) Tas ir tik sarežģīts jautājums, ka tam nav īsa apraksta. izsole, kas sniedz jums optimālu peļņu, saka Daskalakis. Lai palielinātu ieņēmumus no vairākām precēm, pārdevējam, iespējams, ir jāpārdod katra prece par zemāku cenu, nekā kāds būtu gatavs maksāt. Taču atlaide mainās atkarībā no tādiem faktoriem kā pārdoto preču kombinācija un pircēju grupas.

Datorzinātne piedāvā jaunu skatījumu uz problēmu — to, ko Daskalakis sauc par tuvināšanas perspektīvu. Varbūt jūs nevarat atrast optimālo izsoli, viņš saka, bet izsole, kas garantē 99 procentus no vislabākajiem ieņēmumiem, ir arī laba izsole. Daskalakis un viņa studenti parādīja, ka jebkuram vairāku preču tirgum ideālo izsoli — tādu, kas maksimāli palielināja pārdevēja ieņēmumus — var tuvināt, apvienojot vienkāršāku izsoļu rezultātus.

Nedaudz atšķirīga pieeja izsoļu problēmām raksturo inženierzinātņu profesora Silvio Mikali darbu. Viņš un EECS profesors Šafi Goldvasers ir jaunākie Tjūringa balvas, augstākās balvas datorzinātnēs, saņēmēji. Lielā mērā ar balvu tiek pagodināts viņu darbs pie tā sauktajiem interaktīvajiem pierādījumiem, kuros jautātājs ar ierobežotiem skaitļošanas resursiem mēģina iegūt aprēķina rezultātu no neuzticama sarunu biedra ar neierobežotiem skaitļošanas resursiem. Viens piemērs ir nulles zināšanu pierādījums, kurā viens no dalībniekiem konstatē informācijas daļas, piemēram, kriptogrāfiskās atslēgas, īpašumā, neatklājot, kas tas ir. Nulles zināšanu pierādījumi tiek izmantoti, lai nodrošinātu darījumus starp finanšu iestādēm, un ir dibināti vairāki jaunuzņēmumi, lai tos komercializētu.

Mikali īsteno vairākus spēļu teorētiskos pētniecības projektus, taču viens no tiem pēc būtības ir ļoti tuvs nulles zināšanu pierādījumiem. Daudzās publiskās izsolēs, piemēram, kad federālā valdība izsolē neizmantoto radiofrekvenču spektru telekomunikāciju uzņēmumiem, izsoles rīkotājam ir pienākums atklāt visus dalībnieku piedāvājumus, lai nodrošinātu pārredzamību. Uzņēmumam, kas piedalās šādā izsolē un zaudē, tas patiešām ir sliktākais no visiem iespējamajiem rezultātiem, saka Mikali. Jūsu konkurenti tagad zina, cik ļoti jūs vērtējat šo lietu, un no tā viņi var secināt, cik lielu klientu loku jūs apkalpojat vai kāda tehnoloģija jums ir pieejama.

Tāpēc Micali grupa izstrādā izsoles, kurās dalībnieki var publiski atklāt pietiekami daudz informācijas par saviem piedāvājumiem, lai noteiktu uzvarētāju, neatklājot pašus piedāvājumus. Es uzskatu, ka galu galā tas kļūs par galveno spēļu teorijas virzienu, saka Mikali. Nevar būt jēgpilnas zinātnes par cilvēku uzvedību, neievērojot privātumu.

Kurš kontrolē?
Daudzās situācijās, kuras var izteikt kā spēles, Neša līdzsvaru var būt gandrīz neiespējami aprēķināt, kā parādīja Daskalakis. Bet tas nenozīmē, ka spēlētāju uzvedība ir nejauša. Padomājiet par pilsētas ielu režģi, kurā autovadītāji pieņem neskaitāmus lēmumus desmitiem krustojumu. Pat ja autovadītāji neizvērtē visas iespējamās alternatīvu lēmumu sekas, viņi joprojām pieņem dažas vienkāršas stratēģijas — piemēram, ja esat pārāk ilgi sēdējis uz vietas, nogriezieties pa sānielu. Pēc EECS asociētā vadītāja Muntera Dahla teiktā, šādu sistēmu analīze pietuvina spēļu teoriju viņa paša jomai, vadības teorijai, kas pēta dinamisku sistēmu, piemēram, robotu ekstremitāšu un lidmašīnu spārnu, kontroles stratēģijas. Mums ir atšķirīgs skatījums uz šīm problēmām, saka Dahleh. Pretstatā līdzsvara jēdziena uzspiešanai un sakām: “Kādas stratēģijas cilvēki spēlētu tādā līdzsvarā?” mēs aplūkojam kontrolēto dinamisko uzvedību un uzdodam jautājumu: “Kāds līdzsvara jēdziens rodas?”

Dahleh patiešām ir izmantojis spēļu teorijas rīkus satiksmes plūsmas analīzei, pētot ceļu izkārtojumu veidus, kas vislabāk atbilst noteiktu maršrutu slēgšanai. Viņa pieeja attiecas arī uz citām liela mēroga dinamiskām sistēmām, piemēram, elektrotīklu.

Katru dienu elektroenerģijas ražotāji — atomelektrostaciju, ogļu spēkstaciju, vēja parku un tamlīdzīgu operatoru operatori — piedāvā jaunus grafikus, cik daudz elektroenerģijas viņi vēlas saražot, par kādu cenu un kurā diennakts laikā. Komunālajiem uzņēmumiem, kas piegādā elektroenerģiju, ir arī administratori, kuri, pamatojoties uz paredzamo patērētāju pieprasījumu, izlemj, cik daudz jaudas iegādāties no katra piegādātāja. Enerģijas ražošanai un patēriņam ir precīzi jāsakrīt, pretējā gadījumā sekas ir postošas.

Izmantojot spēļu teorijas rīkus, lai analizētu gan enerģijas piegādātāju, gan patērētāju stimulus, Dahleh un Mardavijs Roozbehani, PhD '08, galvenais pētnieks Informācijas un lēmumu sistēmu laboratorijā, parādīja, ka viedie skaitītāji mājās, kas var nodrošināt informācija par tūlītējo cenu noteikšanu elektroenerģijas tirgū un ļaut patērētājiem atlikt energoietilpīgus mājsaimniecības darbus, līdz tie ir vispieejamākie, faktiski var izraisīt pieprasījuma kāpumus, kas nojauktu visu tīklu.

jaudas pārsprieguma grafiks


Dahleh ir arī sadarbojies ar Ozdaglaru un viņas vīru, MIT ekonomistu Daronu Acemoglu, lai analizētu, kā informācija izplatās pa populācijām. Spēle šajā gadījumā ir tāda, kurā cilvēki izsver viņus nonākušās informācijas patiesumu vai nepatiesību, cenšoties maksimāli palielināt savu uzskatu precizitāti.

Tie ir jautājumi, kas pētīti gan socioloģijā, gan ekonomikā, saka Ozdaglars. Tomēr tradicionāli šajos pētījumos ir pieņemts, ka jebkura persona noteiktā populācijā var saņemt informāciju tieši no jebkura cita. Ozdaglar apgalvo, ka inženieru piedāvātie rīki ir labi izstrādāti rīki, lai analizētu iedzīvotāju pamata tīkla struktūru. Piemēram, lielākā daļa cilvēku lielāko daļu informācijas saņem tikai no dažiem tuvākajiem kaimiņiem tīklā, un viņi piešķir dažādas varbūtības dažādu kaimiņu apgalvojumu precizitātei.

Agrāk es domāju, ka sociālā zinātne un ekonomika risināja problēmas savādāk nekā inženieri, saka Dahleh. Tagad mēs visi runājam par sociālajiem tīkliem — lēmumiem sociālajos tīklos, dinamiku tīklos — tāpēc es domāju, ka abas jomas saplūst.

paslēpties