Spela systemet

Du och en medbrottsling i ett stort rån har blivit gripna av polisen och förhörs i separata rum. Om ni båda håller tyst om brottet får ni vardera ett års fängelse på en mindre anklagelse. Om ni båda skriker får ni vardera fem år. Men om bara en av er skriker, kommer den ena att gå fri medan den andra får 10 år. Om du inte vet vad din medbrottsling kommer att göra, vad är det rationella beslutet?

Asuman Ozdaglar

Denna gåta, känd som fångens dilemma, är det mest välbekanta exemplet på ett spel, i teknisk mening som används av spelteoretiker. Spelteori är ett matematiskt sätt att beskriva strategiska resonemang, och fångens dilemma illustrerar de tre grundläggande kraven för de situationer som det omfattar: spelet måste involvera flera agenter (här, de två medbrottslingarna); var och en måste fatta ett beslut (skrika eller skrika inte); och varje beslut måste ha en kvantifierbar utdelning (fängelsevillkoren) som varierar beroende på de andra agenternas beslut.

Spelteori har varit en bas i ekonomiforskningen sedan 1950, då John Nash, som undervisade vid MIT från 1951 till 1959 och är föremål för filmen Ett vackert sinne , publicerade seminal papper som skulle ge honom Nobelpriset i ekonomi. Allt eftersom spelteorin har mognat, har den blivit ännu mer central för det området. Bara under de senaste åtta åren har Nobelpriset gått till spelteoretiker tre gånger, för att de bland annat belyst logiken i kärnvapenavskräckning, omständigheterna under vilka fria marknader kan och inte kan maximera den offentliga välfärden och de bästa lösningarna till matchningsproblem – organ och patienter, vårdpersonal och sjukhus och liknande.

Men nyligen har spelteori också uppmärksammats inom teknik och datavetenskap. Forskare använder den för att analysera svåra problem som att optimera trafikflödet eller förhindra strömavbrott.

Asuman Ozdaglar, SM ’98, PhD ’03, professor i elektroteknik och datavetenskap, säger att internets framväxt har gjort detta nödvändigt. Historiskt sett hade ingenjörerna av kommunikationsnätverk att kämpa med ett brett spektrum av tekniska frågor – såsom maktbegränsningar och de relativa fördelarna med centralisering eller decentralisering. Men med Internet fick de plötsligt ta itu med mänsklig handlingskraft också.

Om en Comcast-abonnent i Boston och en EarthLink-abonnent i San Francisco utbyter data, går deras överföringar över nätverk som underhålls av flera olika leverantörer: Comcast, EarthLink och andra däremellan. Hela verksamheten är beroende av både samarbete och konkurrens från dessa olika parter, säger Ozdaglar. Hur utformar du protokoll som faktiskt kommer att ge rätt incitament för människor att samarbeta? Med andra ord: varför fungerar Internet trots att det är uppbyggt av enskilda nätverk? Spelteorin ger ett sätt att besvara den typen av frågor.

När ingenjörer började använda spelteori i frågor inom deras område, insåg de också att verktygen för deras bransch var tillämpliga på utestående frågor om spelteori. Faktum är att av den handfull forskare vid institutionen för elektroteknik och datavetenskap (EECS) som arbetar mycket med spelteori, har alla lagt ner mycket tid på frågor som mer typiskt behandlas av samhällsvetenskaperna.

Går en gång
EECS-professorn Constantinos Daskalakis är ett bra exempel. 2008 vann han Association for Computing Machinerys avhandlingspris genom att visa hur tekniker hämtade från teoretisk datavetenskap kunde kasta nytt ljus över ett av de centrala begreppen inom spelteorin: jämvikt.

Constantinos Daskalakis

Jämvikt är idén som vann Nash sin Nobel, och Nash-jämvikten är den typ av jämvikt som oftast studeras. Den beskriver en balans av strategier som ingen spelare i ett spel har ett motiv att ändra ensidigt. Det mest grundläggande exemplet på en Nash-jämvikt involverar det så kallade straffsparksspelet. I fotboll ger en straffspark en offensiv spelare ett fritt skott på mål med endast målvakten som försvarar. Bollen går så snabbt att målvakten måste gissa åt vilket håll han ska dyka innan den träffas. I den spelteoretiska versionen, om båda spelarna väljer samma halva av målet, vinner målvakten; om de väljer olika halvor vinner skytten.

Jämviktstillståndet för det här spelet är att båda spelarna väljer en riktning slumpmässigt på en given spark men för att säkerställa att de totalt sett väljer båda riktningarna med samma frekvens. I så fall kommer de att vinna halva tiden var och en, och ingen av dem kan förbättra sina odds genom att avvika från den strategin. Till exempel, om målvakten plötsligt började gå i samma riktning varje gång och skytten höll fast vid den ursprungliga strategin, skulle målvaktens vinstprocent bara förbli densamma. Men en skytt som märkte skiftet kunde vinna varje spark genom att gå åt motsatt håll varje gång, så målvakten har inget incitament att göra denna förändring.

Men straffsparksspelet är ett av de enklaste spelen. Att hitta jämvikt för ännu lite mer komplexa spel kan vara oerhört svårt. I sin avhandling bevisade Daskalakis att för vissa situationer som kan beskrivas genom spelteori är Nash-jämvikten så svår att beräkna att alla datorer i världen inte kunde hitta den under universums livstid. I dessa fall, hävdar Daskalakis, har människor förmodligen inte hittat det genom försök och misstag heller. Det betyder att spelteoretiker behöver andra analytiska verktyg än Nash-jämvikten om de vill ha något hopp om att beskriva den verkliga världen.

Lyckligtvis, på samma sätt som datavetenskap har utvecklat ett batteri av tekniker för att bestämma komplexiteten i beräkningar som de som producerar Nash-jämvikter, har den också utvecklat ett batteri av tekniker för att identifiera ungefärliga lösningar på annars svårlösta problem. Daskalakis och hans elever kunde till exempel hitta en för ett ekonomiskt problem som hade stått i 30 år.

1981 visade Roger Myerson från University of Chicago hur man strukturerar en auktion för ett enda föremål så att om alla budgivare antog budgivningsstrategierna i deras bästa intresse, skulle säljaren uppnå den största vinsten. Det arbetet bidrog till att ge honom Nobelpriset 2007. Det väckte också en relaterad fråga: vad är det bästa sättet att strukturera en auktion för mer än ett föremål? (I ekonomers jargong räknas varje marknad med en enda säljare och flera köpare som en auktion; en Christie's-auktion är en, men det är även försäljning i en butik.) Det är en fråga med så stor komplexitet att det inte finns någon kortfattad beskrivning av auktion som ger dig den optimala vinsten, säger Daskalakis. För att maximera intäkterna för flera varor måste säljaren förmodligen sälja varje vara till mindre än det högsta pris som någon skulle vara villig att betala. Men rabatten varierar beroende på faktorer som mixen av varor som säljs och populationerna från vilka köparna dras.

Datavetenskap erbjuder ett nytt perspektiv på problemet – vad Daskalakis kallar approximationsperspektivet. Kanske kan man inte hitta den optimala auktionen, säger han, men en auktion som garanterar 99 procent av de bästa intäkterna är en bra auktion också. Daskalakis och hans elever visade att för alla marknader med flera föremål, kunde den ideala auktionen – en som maximerade säljarens intäkter – uppskattas genom en kombination av resultaten från enklare auktioner.

En något annorlunda inställning till auktionsproblem kännetecknar ingenjörsprofessor Silvio Micalis arbete. Han och EECS-professor Shafi Goldwasser är de senaste mottagarna av Turing Award, det högsta priset inom datavetenskap. Till stor del hedrar priset deras arbete med så kallade interaktiva bevis, där en frågeställare med begränsade beräkningsresurser försöker få fram resultatet av en beräkning från en opålitlig samtalspartner med obegränsade beräkningsresurser. Ett exempel är ett nollkunskapsbevis, där en av deltagarna konstaterar innehav av en bit information, som en kryptografisk nyckel, utan att avslöja vad det är. Nollkunskapsbevis används för att säkra transaktioner mellan finansiella institutioner, och flera startups har grundats för att kommersialisera dem.

Micali driver flera spelteoretiska forskningsprojekt, men ett av dem ligger mycket nära noll-kunskapsbevis. I många offentliga auktioner – som till exempel när den federala regeringen auktionerar ut oanvänt radiospektrum till telekomföretag – är auktionsförrättaren skyldig att avslöja alla deltagares bud för öppenhetens skull. För ett företag som deltar i en sådan auktion och förlorar är det verkligen det värsta av alla möjliga resultat, säger Micali. Dina konkurrenter vet nu hur mycket du värdesätter den här saken, från vilket de kan härleda hur stor kundkrets du betjänar eller vilken teknik du har tillgänglig.

Så Micalis grupp utvecklar auktioner där deltagare offentligt kan avslöja tillräckligt med information om sina bud för att avgöra en vinnare, utan att själva avslöja buden. Jag tror att det här så småningom kommer att bli mainstream inom spelteorin, säger Micali. Du kan inte riktigt ha en meningsfull vetenskap om mänskligt beteende samtidigt som du bortser från privatlivet.

Vem har kontroll?
För många situationer som kan uttryckas som spel kan Nash-jämvikten vara, som Daskalakis visade, nästan omöjlig att beräkna. Men det betyder inte att spelarnas beteende är slumpmässigt. Tänk på ett rutnät av stadsgator där förare fattar otaliga beslut i dussintals korsningar. Även om förarna inte utvärderar alla möjliga konsekvenser av alternativa beslut, antar de fortfarande några enkla strategier - säg, om du har suttit stilla för länge, sväng ner för en sidogata. Enligt Munther Dahleh, biträdande chef för EECS, kommer analys av sådana system spelteorin mycket nära hans eget område, kontrollteorin, som undersöker strategier för att kontrollera dynamiska system som robotars lemmar och flygplans vingar. Vi har en annan syn på de här problemen, säger Dahleh. I motsats till att påtvinga begreppet jämvikt och säga 'Vilka strategier skulle människor spela under den jämvikten?' tittar vi på det kontrollerade dynamiska beteendet och ställer frågan 'Vilken begrepp om jämvikt dyker upp?'

Dahleh har verkligen tillämpat spelteorins verktyg för analys av trafikflödet, och undersökt vilka typer av väglayouter som bäst kan anpassas till stängning av särskilda rutter. Hans synsätt gäller även andra storskaliga dynamiska system, som till exempel elnätet.

Varje dag erbjuder kraftproducenter – operatörer av kärnkraftverk, koleldade anläggningar, vindkraftsparker och liknande – nya scheman för hur mycket el de är villiga att producera, till vilket pris, vid vilka tider på dygnet. De elbolag som levererar el har också administratörer som bestämmer, utifrån förväntad konsumentefterfrågan, hur mycket ström som ska köpas från varje leverantör. Kraftproduktion och förbrukning måste matcha exakt annars blir konsekvenserna katastrofala.

Med hjälp av spelteorins verktyg för att analysera incitamenten från både strömleverantörer och konsumenter visade Dahleh och Mardavij Roozbehani, PhD '08, en ledande forskare vid Laboratory for Information and Decision Systems, att smarta mätare i hemmet, som kan ge information om spotprissättning på elmarknaden och låta konsumenter skjuta upp energikrävande hushållsuppgifter tills de är mest prisvärda, skulle faktiskt kunna orsaka toppar i efterfrågan som skulle få ner hela nätet.

Dahleh har också samarbetat med Ozdaglar och hennes man, MIT-ekonomen Daron Acemoglu, för att analysera hur information sprids genom befolkningar. Spelet i det här fallet är ett där människor väger sanningen eller falskheten i information som når dem, eftersom de strävar efter att maximera noggrannheten i sina egna övertygelser.

Det är frågor som har studerats inom både sociologi och ekonomi, säger Ozdaglar. Traditionellt har dock dessa undersökningar antagit att vilken person som helst i en given population kan få information direkt från vilken annan som helst. Det ingenjörer erbjuder, hävdar Ozdaglar, är välslipade verktyg för att analysera befolkningens underliggande nätverksstruktur. De flesta människor, till exempel, får faktiskt det mesta av sin information från bara ett fåtal omedelbara grannar i nätverket - och de tilldelar olika sannolikheter till riktigheten av olika grannars påståenden.

Tidigare tror jag att samhällsvetenskap och ekonomi hanterade problem annorlunda än ingenjörer, säger Dahleh. Nu pratar vi alla om sociala nätverk – beslut i sociala nätverk, dynamik i nätverk – så jag tror att de två områdena konvergerar.

Dölj