Spille systemet

Du og en medskyldig i et større rov er blitt pågrepet av politiet og blir avhørt i separate rom. Hvis dere begge tier om forbrytelsen, får dere et års fengsel hver på en mindre siktelse. Hvis dere begge skriker, får dere fem år hver. Men hvis bare en av dere hviner, vil den ene gå fri mens den andre får 10 år. Hvis du ikke vet hva din medskyldige vil gjøre, hva er den rasjonelle avgjørelsen?





Asuman Ozdaglar

Asuman Ozdaglar

Denne gåten, kjent som fangens dilemma, er det mest kjente eksemplet på et spill, i teknisk forstand brukt av spilleteoretikere. Spillteori er en matematisk måte å beskrive strategisk resonnement på, og fangens dilemma illustrerer de tre grunnleggende kravene til situasjonene den omfatter: spillet må involvere flere agenter (her de to medskyldige); hver må ta en avgjørelse (hvin eller ikke squeal); og hver avgjørelse må ha en kvantifiserbar utbetaling (fengselsstraffene) som varierer i henhold til de andre agentenes avgjørelser.

Spillteori har vært en stift i økonomisk forskning siden 1950, da John Nash, som underviste ved MIT fra 1951 til 1959 og er tema for filmen Et vakkert sinn , publiserte banebrytende papir som ville gi ham Nobelprisen i økonomi. Etter hvert som spillteorien har modnet, har den blitt enda mer sentral i det feltet. Bare de siste åtte årene har Nobelprisen gått til spilleteoretikere tre ganger, for å ha belyst blant annet logikken i kjernefysisk avskrekking, omstendighetene der frie markeder kan og ikke kan maksimere offentlig velferd, og de beste løsningene. til matchende problemer – organer og pasienter, medisinske beboere og sykehus og lignende.



Men nylig har spillteori også trukket oppmerksomhet innen ingeniørvitenskap og informatikk. Forskere bruker den til å analysere vanskelige problemer som å optimalisere trafikkflyten eller forhindre strømbrudd.

Asuman Ozdaglar, SM ’98, PhD ’03, professor i elektroteknikk og informatikk, sier fremveksten av Internett har gjort dette nødvendig. Historisk sett måtte ingeniørene av kommunikasjonsnettverk kjempe med et bredt spekter av tekniske spørsmål - som maktbegrensninger og de relative fordelene ved sentralisering eller desentralisering. Men med Internett måtte de plutselig forholde seg til menneskelig handlefrihet også.

Hvis en Comcast-abonnent i Boston og en EarthLink-abonnent i San Francisco utveksler data, går overføringene deres over nettverk som vedlikeholdes av flere forskjellige leverandører: Comcast, EarthLink og andre i mellom. Hele operasjonen er avhengig av både samarbeid og konkurranse fra disse ulike partene, sier Ozdaglar. Hvordan designer du protokoller som faktisk vil gi de riktige insentivene for folk til å samarbeide? Med andre ord: hvorfor fungerer Internett selv om det består av individuelle nettverk? Spillteori gir en måte å svare på den slags spørsmål.



Etter hvert som ingeniører begynte å bringe spilleteori til å ta stilling til spørsmål innen deres felt, innså de også at verktøyene i deres fag var anvendelige på utestående spørsmål innen spillteori. Faktisk, av de håndfulle forskere ved Institutt for elektroteknikk og informatikk (EECS) som jobber mye med spillteori, har alle brukt mye tid på spørsmål som er mer typisk behandlet av samfunnsvitenskapene.

Går en gang
EECS-professor Constantinos Daskalakis er et godt eksempel. I 2008 vant han Association for Computing Machinerys avhandlingspris ved å vise hvordan teknikker hentet fra teoretisk informatikk kunne kaste nytt lys over et av de sentrale konseptene i spillteorien: likevekt.

Constantinos Daskalakis

Constantinos Daskalakis



Likevekt er ideen som vant Nash sin Nobel, og Nash-likevekten er den typen likevekt som oftest studeres. Den beskriver en balanse av strategier som ingen spiller i et spill har et motiv til å endre ensidig. Det mest grunnleggende eksemplet på en Nash-likevekt involverer det såkalte straffesparkspillet. I fotball gir et straffespark en offensiv spiller et friskudd på mål med kun keeperen som forsvarer. Ballen går så raskt at målvakten må gjette hvilken vei han skal dykke før den blir truffet. I den spilleteoretiske versjonen, hvis begge spillerne velger samme halvdel av målet, vinner målvakten; hvis de velger forskjellige halvdeler, vinner skytteren.

Likevektstilstanden for dette spillet er for begge spillere å velge en retning tilfeldig på et gitt spark, men for å sikre at de totalt sett velger begge retninger med lik frekvens. I så fall vil de hver vinne halve tiden, og ingen av dem kan forbedre oddsen hans eller hennes ved å avvike fra den strategien. For eksempel, hvis keeperen plutselig begynte å gå i samme retning hver gang og skytteren holdt seg til den opprinnelige strategien, ville keeperens vinnerprosent bare forbli den samme. En skytter som la merke til skiftet kunne imidlertid vinne hvert spark ved å gå i motsatt retning hver gang, så keeperen har ikke noe insentiv til å gjøre denne endringen.

Men straffesparkspillet er et av de enkleste spillene. Å finne likevekter for enda litt mer komplekse spill kan være enormt vanskelig. I sin avhandling beviste Daskalakis at for noen situasjoner som kan beskrives gjennom spillteori, er Nash-likevekten så vanskelig å beregne at alle datamaskiner i verden ikke kunne finne den i universets levetid. I disse tilfellene, hevder Daskalakis, har mennesker sannsynligvis ikke funnet det gjennom prøving og feiling heller. Det betyr at spilleteoretikere trenger andre analytiske verktøy enn Nash-likevekten hvis de ønsker noe håp om å beskrive den virkelige verden.



Heldigvis, på samme måte som informatikk har utviklet et batteri av teknikker for å bestemme kompleksiteten til beregninger som de som produserer Nash-likevekter, har den også utviklet et batteri av teknikker for å identifisere omtrentlige løsninger på ellers vanskelige problemer. Daskalakis og studentene hans, for eksempel, var i stand til å finne en for et økonomisk problem som hadde stått i 30 år.

I 1981 viste University of Chicagos Roger Myerson hvordan man strukturerer en auksjon for en enkelt gjenstand slik at hvis alle budgiverne vedtok budstrategiene i deres beste interesse, ville selgeren oppnå størst fortjeneste. Det arbeidet bidro til å gi ham Nobelprisen i 2007. Det reiste også et relatert spørsmål: hva er den beste måten å strukturere en auksjon for mer enn én gjenstand på? (I økonomers sjargong teller ethvert marked med en enkelt selger og flere kjøpere som en auksjon; en Christie's-auksjon er en, men det er også salg i en detaljhandel.) Det er et spørsmål med så stor kompleksitet at det ikke finnes noen kortfattet beskrivelse av auksjon som gir deg optimal fortjeneste, sier Daskalakis. For å maksimere inntektene på tvers av flere varer, må selgeren sannsynligvis selge hver vare til mindre enn den høyeste prisen noen ville være villig til å betale. Men rabatten varierer i henhold til faktorer som blandingen av varer som selges og populasjonene som kjøperne er trukket fra.

Datavitenskap tilbyr et nytt perspektiv på problemet – det Daskalakis kaller tilnærmingsperspektivet. Kanskje du ikke klarer å finne den optimale auksjonen, sier han, men en auksjon som garanterer 99 prosent av de beste inntektene er en god auksjon også. Daskalakis og hans studenter viste at for ethvert marked med flere varer, kunne den ideelle auksjonen – en som maksimerte selgerens inntekter – tilnærmes ved en kombinasjon av resultatene av enklere auksjoner.

En noe annerledes tilnærming til auksjonsproblematikk kjennetegner arbeidet til ingeniørprofessor Silvio Micali. Han og EECS-professor Shafi Goldwasser er de siste mottakerne av Turing-prisen, den høyeste utmerkelsen innen informatikk. I stor grad hedrer prisen deres arbeid med såkalte interaktive bevis, der en spørre med begrensede beregningsressurser prøver å få frem resultatet av en beregning fra en upålitelig samtalepartner med ubegrensede beregningsressurser. Et eksempel er et null-kunnskapsbevis, der en av deltakerne fastslår besittelse av en informasjon, som en kryptografisk nøkkel, uten å avsløre hva det er. Nullkunnskapsbevis brukes for å sikre transaksjoner mellom finansinstitusjoner, og flere startups har blitt grunnlagt for å kommersialisere dem.

Micali forfølger flere spillteoretiske forskningsprosjekter, men ett av dem er i ånden veldig nær null-kunnskapsbevis. I mange offentlige auksjoner – som for eksempel når den føderale regjeringen auksjonerer ubrukt radiospektrum til telekomselskaper – er auksjonarius forpliktet til å avsløre alle deltakernes bud for åpenhetens skyld. For et selskap som deltar i en slik auksjon og taper, er det egentlig det verste av alle mulige utfall, sier Micali. Konkurrentene dine vet nå hvor mye du verdsetter denne tingen, som de kan utlede hvor stor kundekrets du betjener eller hvilken teknologi du har tilgjengelig.

Så Micalis gruppe utvikler auksjoner der deltakerne kan offentliggjøre nok informasjon om budene sine til å avgjøre en vinner, uten å avsløre budene selv. Jeg tror at dette etter hvert vil bli mainstream innen spillteori, sier Micali. Du kan egentlig ikke ha en meningsfull vitenskap om menneskelig atferd mens du ser bort fra personvernet.

Hvem har kontroll?
For mange situasjoner som kan uttrykkes som spill, kan Nash-likevekten være, som Daskalakis viste, nesten umulig å beregne. Men det betyr ikke at spillernes oppførsel er tilfeldig. Tenk på et rutenett av bygater der sjåfører tar utallige avgjørelser i dusinvis av veikryss. Selv om sjåførene ikke vurderer alle mulige konsekvenser av alternative beslutninger, tar de fortsatt i bruk noen enkle strategier – for eksempel hvis du har sittet stille for lenge, sving ned en sidegate. Ifølge Munther Dahleh, assisterende sjef for EECS, bringer analyse av slike systemer spillteorien veldig nært hans eget felt, kontrollteori, som undersøker strategier for å kontrollere dynamiske systemer som roboters lemmer og flyvinger. Vi har et annet syn på disse problemene, sier Dahleh. I motsetning til å påtvinge forestillingen om likevekt og si 'Hvilke strategier ville folk spille under den likevekten?' ser vi på den kontrollerte dynamiske atferden og stiller spørsmålet 'Hvilken forestilling om likevekt dukker opp?'

Dahleh har faktisk brukt spillteoriens verktøy på analysen av trafikkflyt, og undersøkt hvilke typer veioppsett som best kan imøtekomme stenging av bestemte ruter. Hans tilnærming gjelder også andre storskala dynamiske systemer, som for eksempel strømnettet.

Hver dag tilbyr kraftprodusenter – operatører av kjernekraftverk, kullkraftverk, vindparker og lignende – nye tidsplaner for hvor mye strøm de er villige til å produsere, til hvilken pris, til hvilke tider på døgnet. Verkene som leverer strøm har også administratorer som bestemmer, ut fra forventet forbrukerbehov, hvor mye strøm som skal kjøpes fra hver leverandør. Kraftproduksjon og forbruk må samsvare nøyaktig, ellers blir konsekvensene katastrofale.

Ved å bruke spillteoriens verktøy for å analysere insentivene til både strømleverandører og forbrukere, viste Dahleh og Mardavij Roozbehani, PhD '08, en hovedforsker ved Laboratory for Information and Decision Systems, at smarte målere i hjemmet, som kan gi informasjon om spotprising i strømmarkedet og la forbrukere utsette energikrevende husholdningsoppgaver til de er mest rimelige, kan faktisk forårsake topper i etterspørselen som vil få hele nettet ned.

strømstøt graf


Dahleh har også samarbeidet med Ozdaglar og mannen hennes, MIT-økonomen Daron Acemoglu, for å analysere hvordan informasjon forplanter seg gjennom populasjoner. Spillet i dette tilfellet er et der folk veier sannheten eller usannheten i informasjonen som når dem, mens de streber etter å maksimere nøyaktigheten til sin egen tro.

Dette er spørsmål som er studert både i sosiologi og økonomi, sier Ozdaglar. Tradisjonelt har imidlertid disse undersøkelsene antatt at enhver person i en gitt populasjon kan motta informasjon direkte fra enhver annen. Det ingeniører tilbyr, hevder Ozdaglar, er velslipte verktøy for å analysere den underliggende nettverksstrukturen til befolkningen. De fleste, for eksempel, mottar faktisk mesteparten av informasjonen sin fra bare noen få umiddelbare naboer i nettverket – og de tildeler ulike sannsynligheter til nøyaktigheten av ulike naboers påstander.

Tidligere tror jeg at samfunnsvitenskap og økonomi behandlet problemer annerledes enn ingeniører, sier Dahleh. Nå snakker vi alle om sosiale nettverk – beslutninger i sosiale nettverk, dynamikk på nettverk – så jeg tror de to feltene konvergerer.

gjemme seg