Spil systemet

Du og en medskyldig i et større røveri er blevet fanget af politiet og bliver afhørt i separate rum. Hvis I begge tier om forbrydelsen, får I hver et års fængsel på en mindre anklage. Hvis I begge hviner, får I hver fem år. Men hvis bare en af ​​jer hviner, går den ene fri, mens den anden får 10 år. Hvis du ikke ved, hvad din medskyldige vil gøre, hvad er den rationelle beslutning?

Asuman Ozdaglar

Denne gåde, kendt som fangens dilemma, er det mest velkendte eksempel på et spil, i teknisk forstand brugt af spilteoretikere. Spilteori er en matematisk måde at beskrive strategisk ræsonnement på, og fangens dilemma illustrerer de tre grundlæggende krav til de situationer, det omfatter: spillet skal involvere flere agenter (her de to medskyldige); hver skal træffe en beslutning (hvin eller ikke hvin); og hver beslutning skal have en kvantificerbar gevinst (fængselsstraffene), der varierer i henhold til de andre agenters beslutninger.

Spilteori har været en fast bestanddel af økonomisk forskning siden 1950, hvor John Nash, der underviste på MIT fra 1951 til 1959 og er emnet for filmen Et smukt sind , udgivet banebrydende papir det ville give ham Nobelprisen i økonomi. Efterhånden som spilteorien er blevet modnet, er den blevet endnu mere central på det felt. På blot de sidste otte år er Nobelprisen gået til spilteoretikere tre gange, for blandt andet at kaste lys over logikken bag nuklear afskrækkelse, de omstændigheder, hvorunder frie markeder kan og ikke kan maksimere den offentlige velfærd, og de bedste løsninger. til matchende problemer - organer og patienter, læger og hospitaler og lignende.

Men for nylig har spilteori også trukket opmærksomhed inden for teknik og datalogi. Forskere bruger det til at analysere vanskelige problemer såsom at optimere trafikstrømmen eller forhindre strømafbrydelser.

Asuman Ozdaglar, SM '98, PhD '03, professor i elektroteknik og datalogi, siger, at internettets fremkomst har gjort dette nødvendigt. Historisk set måtte ingeniørerne af kommunikationsnetværk kæmpe med en lang række tekniske spørgsmål - såsom magtbegrænsninger og de relative fordele ved centralisering eller decentralisering. Men med internettet skulle de pludselig også beskæftige sig med menneskelig handlefrihed.

Hvis en Comcast-abonnent i Boston og en EarthLink-abonnent i San Francisco udveksler data, kører deres transmissioner over netværk, der vedligeholdes af flere forskellige udbydere: Comcast, EarthLink og andre imellem. Hele operationen er afhængig af både samarbejde og konkurrence mellem disse forskellige parter, siger Ozdaglar. Hvordan designer du protokoller, der rent faktisk vil give de rigtige incitamenter for folk til at samarbejde? Med andre ord: hvorfor fungerer internettet, selvom det består af individuelle netværk? Spilteori giver en måde at besvare den slags spørgsmål på.

Da ingeniører begyndte at bringe spilteori til at påvirke spørgsmål inden for deres felt, indså de også, at værktøjerne i deres fag var anvendelige til udestående spørgsmål om spilteori. Faktisk har af den håndfuld forskere i Institut for Elektroteknik og Datalogi (EECS), som arbejder meget med spilteori, alle brugt betydelig tid på spørgsmål, som mere typisk behandles af samfundsvidenskaberne.

Går en gang
EECS-professor Constantinos Daskalakis er et godt eksempel. I 2008 vandt han Association for Computing Machinerys afhandlingspris ved at vise, hvordan teknikker hentet fra teoretisk datalogi kunne kaste nyt lys over et af spilteoriens centrale begreber: ligevægt.

Constantinos Daskalakis

Ligevægt er ideen, der vandt Nash hans Nobel, og Nash-ligevægten er den type ligevægt, der oftest studeres. Den beskriver en balance mellem strategier, som ingen spiller i et spil har et motiv til at ændre ensidigt. Det mest grundlæggende eksempel på en Nash-ligevægt involverer det såkaldte straffesparksspil. I fodbold giver et straffespark en offensiv spiller et frit skud på mål, hvor kun målmanden forsvarer. Bolden rejser så hurtigt, at målmanden skal gætte, hvilken vej han skal dykke, før den bliver ramt. I den spilteoretiske version, hvis begge spillere vælger den samme halvdel af målet, vinder målmanden; hvis de vælger forskellige halvdele, vinder skytten.

Ligevægtstilstanden for dette spil er, at begge spillere vælger en retning tilfældigt på et givet spark, men for at sikre, at de samlet set vælger begge retninger med samme frekvens. I så fald vil de hver især vinde halvdelen af ​​tiden, og ingen af ​​dem kan forbedre hans eller hendes odds ved at afvige fra denne strategi. For eksempel, hvis målmanden pludselig begyndte at gå i samme retning hver gang, og skytten holdt sig til den oprindelige strategi, ville målmandens vinderprocent blot forblive den samme. En skytte, der bemærkede skiftet, kunne dog vinde hvert spark ved at gå i den modsatte retning hver gang, så målmanden har intet incitament til at foretage denne ændring.

Men straffesparksspillet er et af de enkleste spil. At finde ligevægt for selv lidt mere komplekse spil kan være enormt svært. I sin afhandling beviste Daskalakis, at for nogle situationer, der kan beskrives gennem spilteori, er Nash-ligevægten så svær at beregne, at alle computere i verden ikke kunne finde den i universets levetid. I de tilfælde, hævder Daskalakis, har mennesker sandsynligvis heller ikke fundet det gennem forsøg og fejl. Det betyder, at spilteoretikere har brug for andre analytiske værktøjer end Nash-ligevægten, hvis de ønsker noget håb om at beskrive den virkelige verden.

Heldigvis, på samme måde som datalogi har udviklet et batteri af teknikker til at bestemme kompleksiteten af ​​beregninger som dem, der producerer Nash-ligevægte, har den også udviklet et batteri af teknikker til at identificere omtrentlige løsninger på ellers vanskelige problemer. Daskalakis og hans elever var for eksempel i stand til at finde en til et økonomisk problem, der havde stået på i 30 år.

I 1981 viste University of Chicagos Roger Myerson, hvordan man strukturerer en auktion for en enkelt genstand, så hvis alle budgivere vedtog budstrategierne i deres bedste interesse, ville sælgeren realisere den største fortjeneste. Det arbejde var med til at give ham Nobelprisen i 2007. Det rejste også et relateret spørgsmål: hvad er den bedste måde at strukturere en auktion for mere end én genstand? (I økonomers jargon tæller ethvert marked med en enkelt sælger og flere købere som en auktion; en Christie's auktion er en, men det er salg i en detailbutik også.) Det er et spørgsmål med så stor kompleksitet, at der ikke er nogen kortfattet beskrivelse af auktion, der giver dig det optimale overskud, siger Daskalakis. For at maksimere omsætningen på tværs af flere varer er sælgeren sandsynligvis nødt til at sælge hver vare til mindre end den højeste pris, nogen ville være villig til at betale. Men rabatten varierer afhængigt af faktorer som blandingen af ​​varer, der sælges, og de populationer, som køberne er trukket fra.

Datalogi giver et nyt perspektiv på problemet - det, Daskalakis kalder tilnærmelsesperspektivet. Måske er man ikke i stand til at finde den optimale auktion, siger han, men en auktion, der garanterer 99 procent af den bedste omsætning, er også en god auktion. Daskalakis og hans elever viste, at for ethvert marked med flere varer kunne den ideelle auktion – en som maksimerede sælgerens omsætning – tilnærmes ved en kombination af resultaterne af enklere auktioner.

En noget anderledes tilgang til auktionsproblemer kendetegner ingeniørprofessor Silvio Micalis arbejde. Han og EECS-professor Shafi Goldwasser er de seneste modtagere af Turing-prisen, den højeste pris inden for datalogi. Prisen hædrer i høj grad deres arbejde med såkaldte interaktive beviser, hvor en spørger med begrænsede beregningsressourcer forsøger at fremkalde resultatet af en beregning fra en upålidelig samtalepartner med ubegrænsede beregningsressourcer. Et eksempel er et nulvidensbevis, hvor en af ​​deltagerne konstaterer besiddelse af en information, som en kryptografisk nøgle, uden at afsløre, hvad det er. Nulvidensbeviser bruges til at sikre transaktioner mellem finansielle institutioner, og flere startups er blevet grundlagt for at kommercialisere dem.

Micali forfølger adskillige spilteoretiske forskningsprojekter, men et af dem er i ånden meget tæt på nul-vidensbeviser. I mange offentlige auktioner - som for eksempel når den føderale regering auktionerer ubrugt radiospektrum til teleselskaber - er auktionsholderen forpligtet til at afsløre alle deltageres bud af hensyn til gennemsigtigheden. For en virksomhed, der deltager i sådan en auktion og taber, er det virkelig det værste af alle mulige udfald, siger Micali. Dine konkurrenter ved nu, hvor meget du værdsætter denne ting, hvorfra de kan udlede, hvor stor en kundekreds du betjener, eller hvilken teknologi du har tilgængelig.

Så Micalis gruppe udvikler auktioner, hvor deltagere offentligt kan offentliggøre nok information om deres bud til at afgøre en vinder, uden at afsløre buddene selv. Jeg tror på, at dette i sidste ende vil blive mainstream i spilteorien, siger Micali. Du kan ikke rigtig have en meningsfuld videnskab om menneskelig adfærd, mens du ser bort fra privatlivets fred.

Hvem har kontrol?
For mange situationer, der kan udtrykkes som spil, kan Nash-ligevægten være, som Daskalakis viste, næsten umulig at beregne. Men det betyder ikke, at spillernes adfærd er tilfældig. Overvej et gitter af bygader, hvor chauffører træffer utallige beslutninger ved snesevis af vejkryds. Selvom chaufførerne ikke vurderer alle mulige konsekvenser af alternative beslutninger, vedtager de stadig nogle simple strategier - for eksempel, hvis du har siddet stille for længe, ​​så drej ned ad en sidegade. Ifølge Munther Dahleh, associeret leder af EECS, bringer analyse af sådanne systemer spilteorien meget tæt på hans eget felt, kontrolteori, som undersøger strategier til styring af dynamiske systemer såsom robotters lemmer og flys vinger. Vi har et andet syn på disse problemer, siger Dahleh. I modsætning til at påtvinge forestillingen om ligevægt og sige 'Hvilke strategier ville folk spille under den ligevægt?' ser vi på den kontrollerede dynamiske adfærd og stiller spørgsmålet 'Hvilken begreb om ligevægt opstår?'

Dahleh har faktisk anvendt spilteoriens værktøjer til at analysere trafikstrømmen, idet han har undersøgt de typer vejlayout, der bedst kan rumme lukning af bestemte ruter. Hans tilgang gælder også andre dynamiske systemer i stor skala, såsom elnettet.

Hver dag tilbyder strømproducenter - operatører af atomkraftværker, kulfyrede værker, vindmølleparker og lignende - nye tidsplaner for, hvor meget elektricitet de er villige til at producere, til hvilken pris, på hvilke tidspunkter af dagen. De forsyningsselskaber, der leverer strøm, har også administratorer, der på baggrund af forventet forbrugerefterspørgsel bestemmer, hvor meget strøm der skal købes hos hver udbyder. Elproduktion og forbrug skal matche nøjagtigt, ellers bliver konsekvenserne katastrofale.

Ved at bruge spilteoriens værktøjer til at analysere incitamenterne fra både strømudbydere og forbrugere viste Dahleh og Mardavij Roozbehani, PhD '08, en hovedforsker i Laboratory for Information and Decision Systems, at smarte målere i hjemmet, som kan give information om spotpriser på elmarkedet og lade forbrugerne udsætte energikrævende husholdningsopgaver, indtil de er mest overkommelige, kunne faktisk forårsage stigninger i efterspørgslen, der ville bringe hele nettet ned.

Dahleh har også samarbejdet med Ozdaglar og hendes mand, MIT-økonomen Daron Acemoglu, for at analysere, hvordan information forplanter sig gennem befolkninger. Spillet i dette tilfælde er et, hvor folk afvejer sandheden eller falskheden af ​​information, der når dem, da de stræber efter at maksimere nøjagtigheden af ​​deres egne overbevisninger.

Det er spørgsmål, som er blevet undersøgt i både sociologi og økonomi, siger Ozdaglar. Traditionelt har disse undersøgelser dog antaget, at enhver person i en given population kan modtage information direkte fra enhver anden. Det, ingeniører tilbyder, hævder Ozdaglar, er veludviklede værktøjer til at analysere befolkningens underliggende netværksstruktur. De fleste mennesker modtager f.eks. faktisk det meste af deres information fra nogle få umiddelbare naboer i netværket - og de tildeler forskellige sandsynligheder til nøjagtigheden af ​​forskellige naboers påstande.

Tidligere tror jeg, at samfundsvidenskab og økonomi håndterede problemer anderledes end ingeniører, siger Dahleh. Nu taler vi alle om sociale netværk – beslutninger i sociale netværk, dynamik på netværk – så jeg tror, ​​at de to felter konvergerer.

skjule