Sistemos žaidimai

Jūs ir stambios vagystės bendrininkas buvo sučiupti policininkų ir apklausiami atskiruose kambariuose. Jei abu tylėsite apie nusikaltimą, kiekvienas gausite po metus kalėjimo už mažesnį kaltinimą. Jei abu cypsite, kiekvienas gausite penkerius metus. Bet jei tik vienas iš jūsų šaukia, tas vienas išeis į laisvę, o kitas gaus 10 metų. Jei nežinote, ką darys jūsų bendrininkas, koks yra racionalus sprendimas?





Asumanas Ozdaglaras

Asumanas Ozdaglaras

Šis galvosūkis, žinomas kaip kalinio dilema, yra labiausiai žinomas žaidimo pavyzdys technine žaidimo teoretikų prasme. Žaidimo teorija yra matematinis būdas apibūdinti strateginius samprotavimus, o kalinio dilema iliustruoja tris pagrindinius jos apimamų situacijų reikalavimus: žaidime turi dalyvauti keli agentai (čia du bendrininkai); kiekvienas turi apsispręsti (čirškėti ar nečirškėti); ir kiekvienas sprendimas turi turėti kiekybiškai įvertinamą atlygį (kalėjimo terminus), kuris skiriasi priklausomai nuo kitų agentų sprendimų.

Žaidimų teorija buvo pagrindinė ekonomikos tyrimų dalis nuo 1950 m., kai Johnas Nashas, ​​kuris dėstė MIT nuo 1951 iki 1959 m. ir yra filmo objektas. Gražus protas , paskelbė sėklinis popierius kad jam būtų suteikta Nobelio ekonomikos premija. Žaidimų teorijai subrendus, ji tapo dar svarbesnė toje srityje. Vos per pastaruosius aštuonerius metus Nobelio premija tris kartus buvo skirta žaidimų teoretikams už tai, kad, be kita ko, atskleidė branduolinio atgrasymo logiką, aplinkybes, kuriomis laisvoji rinka gali ir negali padidinti visuomenės gerovės, ir geriausius sprendimus. problemų – organų ir pacientų, gydytojų rezidentų ir ligoninių ir panašiai.



Tačiau pastaruoju metu žaidimų teorija atkreipė dėmesį ir į inžineriją bei kompiuterių mokslą. Tyrėjai jį naudoja analizuodami sudėtingas problemas, tokias kaip eismo srauto optimizavimas arba elektros energijos tiekimo nutraukimų prevencija.

Asumanas Ozdaglaras, SM '98, PhD '03, elektros inžinerijos ir informatikos profesorius, sako, kad dėl interneto atsiradimo tai tapo būtina. Istoriškai ryšių tinklų inžinieriai turėjo kovoti su daugybe techninių klausimų, tokių kaip galios apribojimai ir santykiniai centralizacijos ar decentralizacijos pranašumai. Tačiau su internetu jiems staiga teko susidurti ir su žmogiškąja agentūra.

Jei „Comcast“ abonentas Bostone ir „EarthLink“ abonentas San Fransiske keičiasi duomenimis, jų perdavimas vyksta tinklais, kuriuos prižiūri keli skirtingi teikėjai: „Comcast“, „EarthLink“ ir kiti. Visa operacija priklauso nuo šių skirtingų šalių bendradarbiavimo ir konkurencijos, sako Ozdaglar. Kaip kuriate protokolus, kurie iš tikrųjų suteiktų tinkamų paskatų žmonėms bendradarbiauti? Kitaip tariant: kodėl internetas veikia, nors ir sudarytas iš atskirų tinklų? Žaidimo teorija suteikia atsakymą į tokį klausimą.



Kai inžinieriai pradėjo diegti žaidimų teoriją savo srities klausimais, jie taip pat suprato, kad jų amato įrankiai gali būti pritaikyti sprendžiant neišspręstus žaidimų teorijos klausimus. Iš tiesų, iš kelių Elektros inžinerijos ir informatikos katedros (EECS) mokslininkų, kurie daug dirba žaidimų teorijos srityje, visi daug laiko skyrė klausimams, kuriuos dažniausiai sprendžia socialiniai mokslai.

Eina vieną kartą
EECS profesorius Constantinos Daskalakis yra geras pavyzdys. 2008 m. jis laimėjo Kompiuterinių mašinų asociacijos disertacijos prizą, parodydamas, kaip teorinės informatikos metodai gali atskleisti vieną iš pagrindinių žaidimų teorijos sąvokų – pusiausvyrą.

Konstantinas Daskalakis

Konstantinas Daskalakis



Pusiausvyra yra idėja, kuri laimėjo Nashą Nobeliu, o Nash pusiausvyra yra dažniausiai tiriama pusiausvyros rūšis. Tai apibūdina strategijų balansą, kurio nė vienas žaidimo žaidėjas neturi motyvo vienašališkai pakeisti. Pagrindinis Nash pusiausvyros pavyzdys yra vadinamasis baudos smūgio žaidimas. Futbole baudos smūgis suteikia įžaidėjui laisvą smūgį į vartus, kai ginasi tik vartininkas. Kamuolys skrieja taip greitai, kad vartininkas turi atspėti, kuriuo keliu pasinerti, kol jis smūgiuojamas. Žaidimo teorinėje versijoje, jei abu žaidėjai pasirenka tą pačią pusę įvarčio, ​​vartininkas laimi; jei jie pasirenka skirtingas puses, šaulys laimi.

Pusiausvyros būsena šiame žaidime yra tokia, kad abu žaidėjai atsitiktinai pasirenka kryptį bet kuriam spyriui, tačiau turi užtikrinti, kad apskritai jie pasirinktų abi kryptis vienodai dažnai. Tokiu atveju kiekvienas iš jų laimės pusę laiko ir nei vienas, nei kitas negali pagerinti savo šansų, nukrypdamas nuo šios strategijos. Pavyzdžiui, jei vartininkas kiekvieną kartą staiga pradėtų eiti ta pačia kryptimi ir šaulys laikytųsi pradinės strategijos, vartininko laimėjimo procentas tiesiog išliktų toks pat. Tačiau pamainą pastebėjęs šaulys galėjo laimėti kiekvieną smūgį, kiekvieną kartą eidamas priešinga kryptimi, todėl vartininkas neturi paskatų atlikti šį pakeitimą.

Tačiau baudos metimų žaidimas yra vienas iš paprasčiausių žaidimų. Gali būti nepaprastai sunku rasti pusiausvyrą net šiek tiek sudėtingesniems žaidimams. Savo disertacijoje Daskalakis įrodė, kad kai kuriose situacijose, kurias galima apibūdinti žaidimų teorija, Nash pusiausvyrą taip sunku apskaičiuoti, kad visi pasaulio kompiuteriai negalėjo jos rasti per visatos gyvavimo laikotarpį. Tokiais atvejais, teigia Daskalakis, žmonės tikriausiai taip pat nerado bandymų ir klaidų būdu. Tai reiškia, kad žaidimų teoretikams reikia kitų analitinių įrankių nei Nash pusiausvyra, jei jie nori apibūdinti realų pasaulį.



Laimei, lygiai taip pat, kaip kompiuterių mokslas sukūrė daugybę metodų, skirtų skaičiavimo sudėtingumui nustatyti, pavyzdžiui, tų, kurie sukuria Nešo pusiausvyrą, taip pat sukūrė daugybę metodų, leidžiančių nustatyti apytikslius kitaip sunkiai išsprendžiamų problemų sprendimus. Pavyzdžiui, Daskalakis ir jo mokiniai sugebėjo rasti tokį, kuris išspręstų 30 metų trukusią ekonomikos problemą.

1981 m. Čikagos universiteto Rogeris Myersonas parodė, kaip sudaryti vieno daikto aukcioną taip, kad jei visi konkurso dalyviai taikytų pasiūlymų strategijas, kurios geriausiai atitinka jų interesus, pardavėjas gautų didžiausią pelną. Šis darbas padėjo jam pelnyti 2007 m. Nobelio premiją. Taip pat iškilo susijęs klausimas: koks yra geriausias būdas organizuoti aukcioną daugiau nei vienam daiktui? (Ekonomistų žargonu kalbant, bet kuri rinka, kurioje yra vienas pardavėjas ir keli pirkėjai, laikoma aukcionu; Christie's aukcionas yra vienas, bet taip pat ir pardavimas mažmeninės prekybos parduotuvėje.) Tai toks sudėtingas klausimas, kad nėra glausto apibūdinimo. aukcione, kuris suteikia jums optimalų pelną, sako Daskalakis. Kad padidintų kelių prekių pajamas, pardavėjas tikriausiai turi parduoti kiekvieną prekę mažesne nei didžiausia kaina, kurią kas nors norėtų mokėti. Tačiau nuolaida skiriasi atsižvelgiant į tokius veiksnius kaip parduodamų prekių derinys ir pirkėjai.

Kompiuterių mokslas siūlo naują požiūrį į problemą – tai, ką Daskalakis vadina aproksimavimo perspektyva. Galbūt jūs negalite rasti optimalaus aukciono, sako jis, bet aukcionas, garantuojantis 99 procentus geriausių pajamų, taip pat yra geras aukcionas. Daskalakis ir jo mokiniai parodė, kad bet kurioje kelių prekių rinkoje idealų aukcioną, kuris padidintų pardavėjo pajamas, būtų galima apytiksliai nustatyti paprastesnių aukcionų rezultatų deriniu.

Kiek kitoks požiūris į aukciono problemas apibūdina inžinerijos profesoriaus Silvio Micali darbą. Jis ir EECS profesorius Shafi Goldwasseris yra paskutiniai apdovanoti Turingo apdovanojimu – aukščiausiu kompiuterių mokslo apdovanojimu. Daugeliu apdovanojimų pagerbiamas jų darbas, susijęs su vadinamaisiais interaktyviais įrodymais, kai klausėjas, turintis ribotus skaičiavimo išteklius, bando išgauti skaičiavimo rezultatą iš nepatikimo pašnekovo, turinčio neribotus skaičiavimo išteklius. Vienas iš pavyzdžių yra nulinių žinių įrodymas, kai vienas iš dalyvių nustato informacijos, pavyzdžiui, kriptografinio rakto, turėjimą, neatskleisdamas, kas tai yra. Nulinių žinių įrodymai naudojami siekiant užtikrinti sandorius tarp finansų įstaigų, o siekiant juos komercializuoti buvo įkurta keletas startuolių.

Micali vykdo keletą žaidimų teorinių tyrimų projektų, tačiau vienas iš jų savo dvasia labai artimas nulinių žinių įrodymams. Daugelyje viešų aukcionų, pavyzdžiui, kai federalinė vyriausybė aukcione parduoda nepanaudotą radijo spektrą telekomunikacijų bendrovėms, aukciono vedėjas privalo atskleisti visų dalyvių pasiūlymus, kad būtų skaidrumas. Įmonei, kuri dalyvauja tokiame aukcione ir pralaimi, tai iš tikrųjų yra blogiausia iš visų galimų rezultatų, sako Micali. Dabar jūsų konkurentai žino, kiek jūs vertinate šį daiktą, ir iš to gali spręsti, kiek klientų aptarnaujate arba kokias technologijas turite.

Taigi Micali grupė rengia aukcionus, kuriuose dalyviai gali viešai atskleisti pakankamai informacijos apie savo pasiūlymus, kad nuspręstų laimėtoją, neatskleisdami pačių pasiūlymų. Tikiu, kad galiausiai tai taps pagrindine žaidimų teorijos kryptimi, sako Micali. Jūs tikrai negalite turėti prasmingo mokslo apie žmogaus elgesį nepaisydami privatumo.

Kas valdo?
Daugeliui situacijų, kurias galima išreikšti žaidimais, Nash pusiausvyros, kaip parodė Daskalakis, beveik neįmanoma apskaičiuoti. Tačiau tai nereiškia, kad žaidėjų elgesys yra atsitiktinis. Apsvarstykite miesto gatvių tinklelį, kuriame vairuotojai priima daugybę sprendimų dešimtyse sankryžų. Net jei vairuotojai neįvertina visų galimų alternatyvių sprendimų pasekmių, jie vis tiek taiko keletą paprastų strategijų – tarkime, jei per ilgai sėdite vietoje, pasukite šalutine gatve. Pasak Muntherio Dahleho, asocijuoto EECS vadovo, analizuojant tokias sistemas, žaidimų teorija labai priartėja prie jo paties srities, valdymo teorijos, kuri tiria dinaminių sistemų, tokių kaip robotų galūnės ir lėktuvų sparnai, valdymo strategijas. Mes turime kitokį požiūrį į šias problemas, sako Dahleh. Priešingai nei primesti pusiausvyros sąvoką ir sakydamas „Kokias strategijas žmonės žaistų esant tokiai pusiausvyrai?“, mes žiūrime į kontroliuojamą dinaminį elgesį ir užduodame klausimą „Kokia atsiranda pusiausvyros sąvoka?

Dahlehas iš tiesų pritaikė žaidimų teorijos įrankius eismo srautų analizei, tirdamas kelių išdėstymo tipus, kurie gali geriausiai prisitaikyti prie tam tikrų maršrutų uždarymo. Jo požiūris taip pat taikomas kitoms didelės apimties dinaminėms sistemoms, tokioms kaip elektros tinklas.

Kiekvieną dieną energijos gamintojai – atominių elektrinių, anglimi kūrenamų elektrinių, vėjo jėgainių ir panašių dalykų operatoriai – siūlo naujus grafikus, kiek elektros jie nori pagaminti, už kokią kainą ir kokiu paros metu. Elektrą tiekiančios komunalinės įmonės taip pat turi administratorius, kurie, atsižvelgdami į numatomą vartotojų paklausą, nusprendžia, kiek energijos pirkti iš kiekvieno tiekėjo. Energijos gamyba ir suvartojimas turi tiksliai sutapti, kitaip pasekmės bus pražūtingos.

Naudodami žaidimų teorijos įrankius energijos tiekėjų ir vartotojų paskatoms analizuoti, Dahleh ir Mardavij Roozbehani, PhD '08, pagrindinis informacijos ir sprendimų sistemų laboratorijos mokslininkas, parodė, kad išmanieji skaitikliai namuose gali Informacija apie neatidėliotiną elektros energijos rinkos kainodarą ir leisti vartotojams atidėti daug energijos reikalaujančius namų ūkio darbus, kol jie bus įperkamiausi, iš tikrųjų gali sukelti paklausos šuolius, dėl kurių sumažės visas tinklas.

galios viršįtampių grafikas


Dahleh taip pat bendradarbiavo su Ozdaglar ir jos vyru, MIT ekonomistu Daronu Acemoglu, siekdama analizuoti, kaip informacija sklinda per populiacijas. Žaidimas šiuo atveju yra tas, kai žmonės pasveria juos pasiekiančios informacijos tiesą ar klaidingumą, siekdami maksimaliai padidinti savo įsitikinimų tikslumą.

Tai klausimai, kurie buvo tiriami tiek sociologijoje, tiek ekonomikoje, sako Ozdaglar. Tačiau tradiciškai šiuose tyrimuose buvo daroma prielaida, kad bet kuris asmuo tam tikroje populiacijoje gali gauti informaciją tiesiogiai iš bet kurios kitos. Ozdaglar teigia, kad tai, ką siūlo inžinieriai, yra gerai patobulinti įrankiai, skirti analizuoti pagrindinę gyventojų tinklo struktūrą. Pavyzdžiui, dauguma žmonių didžiąją dalį informacijos gauna tik iš kelių artimiausių kaimynų tinkle ir priskiria skirtingas tikimybes skirtingų kaimynų teiginių tikslumui.

Anksčiau aš manau, kad socialiniai mokslai ir ekonomika sprendė problemas kitaip nei inžinieriai, sako Dahleh. Dabar mes visi kalbame apie socialinius tinklus – sprendimus socialiniuose tinkluose, dinamiką tinkluose – todėl manau, kad šios dvi sritys susilieja.

paslėpti