211service.com
Het systeem gamen
Jij en een handlanger bij een grote overval zijn gepakt door de politie en worden ondervraagd in aparte kamers. Als jullie allebei zwijgen over de misdaad, krijgen jullie elk een jaar gevangenisstraf tegen een lagere aanklacht. Als jullie allebei gillen, krijgen jullie elk vijf jaar. Maar als slechts één van jullie gilt, gaat die vrijuit terwijl de ander 10 jaar krijgt. Als u niet weet wat uw handlanger zal doen, wat is dan de rationele beslissing?
Asuman Ozdaglar
Dit raadsel, bekend als het prisoner's dilemma, is het meest bekende voorbeeld van een spel, in de technische zin van speltheoretici. Speltheorie is een wiskundige manier om strategisch redeneren te beschrijven, en het prisoner's dilemma illustreert de drie basisvereisten van de situaties die het omvat: bij het spel moeten meerdere agenten betrokken zijn (hier de twee handlangers); iedereen moet een beslissing nemen (piepen of niet piepen); en elke beslissing moet een kwantificeerbare uitbetaling (de gevangenisstraffen) bevatten die varieert naargelang de beslissingen van de andere agenten.
Speltheorie is een hoofdbestanddeel van economisch onderzoek sinds 1950, toen John Nash, die van 1951 tot 1959 aan het MIT doceerde en het onderwerp is van de film Een mooie geest , publiceerde de baanbrekend papier dat zou hem de Nobelprijs voor economie opleveren. Naarmate de speltheorie volwassener is geworden, is het nog centraler geworden op dat gebied. In de afgelopen acht jaar is de Nobelprijs drie keer naar gametheoretici gegaan, onder meer omdat ze licht werpen op de logica van nucleaire afschrikking, de omstandigheden waarin vrije markten het algemeen welzijn wel en niet kunnen maximaliseren, en de beste oplossingen op het afstemmen van problemen - organen en patiënten, medische bewoners en ziekenhuizen, en dergelijke.
Maar de laatste tijd trekt speltheorie ook de aandacht in techniek en informatica. Onderzoekers gebruiken het om netelige problemen te analyseren, zoals het optimaliseren van de verkeersstroom of het voorkomen van black-outs.
Asuman Ozdaglar, SM '98, PhD '03, hoogleraar elektrotechniek en informatica, zegt dat de opkomst van internet dit noodzakelijk heeft gemaakt. Historisch gezien hadden de ingenieurs van communicatienetwerken te maken met een breed scala aan technische vragen, zoals stroombeperkingen en de relatieve voordelen van centralisatie of decentralisatie. Maar met internet kregen ze ineens ook te maken met menselijke macht.
Als een Comcast-abonnee in Boston en een EarthLink-abonnee in San Francisco gegevens uitwisselen, gaan hun uitzendingen over netwerken die worden onderhouden door verschillende providers: Comcast, EarthLink en andere daartussenin. De hele operatie is afhankelijk van zowel de samenwerking als de concurrentie van deze verschillende partijen, zegt Ozdaglar. Hoe ontwerp je protocollen die daadwerkelijk de juiste prikkels opleveren voor mensen om samen te werken? Met andere woorden: waarom werkt internet ook al bestaat het uit losse netwerken? Speltheorie biedt een manier om dat soort vragen te beantwoorden.
Toen ingenieurs de speltheorie begonnen toe te passen op vragen binnen hun vakgebied, realiseerden ze zich echter ook dat de instrumenten van hun vak van toepassing waren op openstaande vragen van de speltheorie. Van het handjevol onderzoekers van de afdeling Elektrotechniek en Computerwetenschappen (EECS) die zich uitgebreid bezighouden met speltheorie, hebben ze allemaal veel tijd besteed aan vragen die doorgaans in de sociale wetenschappen aan de orde komen.
Een keer gaan
EECS-hoogleraar Constantinos Daskalakis is een goed voorbeeld. In 2008 won hij de proefschriftprijs van de Association for Computing Machinery door te laten zien hoe technieken uit de theoretische informatica nieuw licht konden werpen op een van de centrale concepten in de speltheorie: evenwicht.
Constantinos Daskalakis
Evenwicht is het idee dat Nash zijn Nobelprijs heeft opgeleverd, en het Nash-evenwicht is het type evenwicht dat het meest wordt bestudeerd. Het beschrijft een balans van strategieën die geen enkele speler van een spel een motief heeft om eenzijdig te veranderen. Het meest elementaire voorbeeld van een Nash-evenwicht is het zogenaamde penalty-kick-spel. In voetbal geeft een strafschop een aanvallende speler een vrij schot op doel waarbij alleen de keeper verdedigt. De bal gaat zo snel dat de keeper moet raden naar welke kant hij moet duiken voordat hij wordt geraakt. In de speltheoretische versie, als beide spelers dezelfde helft van het doel kiezen, wint de keeper; als ze verschillende helften kiezen, wint de schutter.
De evenwichtstoestand voor dit spel is dat beide spelers willekeurig een richting kiezen bij een gegeven trap, maar om ervoor te zorgen dat ze over het algemeen beide richtingen met gelijke frequentie kiezen. In dat geval zullen ze elk de helft van de tijd winnen en geen van beide kan zijn of haar kansen verbeteren door van die strategie af te wijken. Als de keeper bijvoorbeeld plotseling elke keer dezelfde kant op zou gaan en de schutter vasthield aan de oorspronkelijke strategie, zou het winstpercentage van de keeper hetzelfde blijven. Een schutter die de verschuiving opmerkte, kon echter elke schop winnen door elke keer de tegenovergestelde richting op te gaan, dus de keeper heeft geen reden om deze verandering aan te brengen.
Maar het strafschopspel is een van de eenvoudigste spellen. Het vinden van evenwichten voor zelfs iets complexere spellen kan enorm moeilijk zijn. In zijn proefschrift bewees Daskalakis dat voor sommige situaties die met speltheorie kunnen worden beschreven, het Nash-evenwicht zo moeilijk te berekenen is dat alle computers ter wereld het tijdens de levensduur van het universum niet konden vinden. In die gevallen, betoogt Daskalakis, hebben mensen het waarschijnlijk ook niet met vallen en opstaan gevonden. Dat betekent dat speltheoretici andere analytische instrumenten nodig hebben dan het Nash-evenwicht als ze enige hoop willen hebben om de echte wereld te beschrijven.
Gelukkig heeft de computerwetenschap, net zoals de computerwetenschap een reeks technieken heeft ontwikkeld voor het bepalen van de complexiteit van berekeningen, zoals die welke Nash-evenwichten produceren, ook een reeks technieken ontwikkeld voor het identificeren van benaderende oplossingen voor anders hardnekkige problemen. Daskalakis en zijn studenten wisten er bijvoorbeeld een te vinden voor een economisch probleem dat al 30 jaar bestond.
In 1981 liet Roger Myerson van de Universiteit van Chicago zien hoe een veiling voor een enkel item zo kon worden gestructureerd dat als alle bieders de biedstrategieën in hun eigen belang zouden toepassen, de verkoper de grootste winst zou behalen. Dat werk heeft hem de Nobelprijs 2007 opgeleverd. Het riep ook een verwante vraag op: wat is de beste manier om een veiling voor meer dan één item te structureren? (In het jargon van economen telt elke markt met een enkele verkoper en meerdere kopers als een veiling; een Christie's-veiling is er een, maar dat geldt ook voor verkopen in een winkel.) Het is een vraag met zo'n grote complexiteit dat er geen beknopte beschrijving is voor de veiling die u de optimale winst oplevert, zegt Daskalakis. Om de inkomsten voor meerdere items te maximaliseren, moet de verkoper waarschijnlijk elk item verkopen tegen minder dan de hoogste prijs die iemand zou willen betalen. Maar de korting varieert afhankelijk van factoren zoals de mix van items die worden verkocht en de populaties waaruit de kopers worden getrokken.
Informatica biedt een frisse kijk op het probleem - wat Daskalakis het benaderingsperspectief noemt. Misschien kun je de optimale veiling niet vinden, zegt hij, maar een veiling die 99 procent van de beste opbrengst garandeert, is ook een goede veiling. Daskalakis en zijn studenten toonden aan dat voor elke markt met meerdere artikelen de ideale veiling - een die de inkomsten van de verkoper maximaliseert - kan worden benaderd door een combinatie van de resultaten van eenvoudigere veilingen.
Een enigszins andere benadering van veilingproblemen kenmerkt het werk van professor techniek Silvio Micali. Hij en EECS-professor Shafi Goldwasser zijn de meest recente ontvangers van de Turing Award, de hoogste onderscheiding in de informatica. De prijs eert voor een groot deel hun werk aan zogenaamde interactieve bewijzen, waarbij een vraagsteller met beperkte rekenkracht het resultaat van een berekening probeert te ontlokken aan een onbetrouwbare gesprekspartner met onbeperkte rekenkracht. Een voorbeeld is een zero-knowledge proof, waarbij een van de deelnemers het bezit van een stukje informatie, zoals een cryptografische sleutel, vaststelt zonder te onthullen wat het is. Nul-kennisbewijzen worden gebruikt om transacties tussen financiële instellingen te beveiligen, en er zijn verschillende startups opgericht om ze te commercialiseren.
Micali voert verschillende game-theoretische onderzoeksprojecten uit, maar een ervan komt heel dicht in de buurt van zero-knowledge proofs. Bij veel openbare veilingen – zoals bijvoorbeeld wanneer de federale overheid ongebruikt radiospectrum veilt aan telecombedrijven – is de veilingmeester verplicht om de biedingen van alle deelnemers openbaar te maken omwille van de transparantie. Voor een bedrijf dat deelneemt aan zo'n veiling en verliest, is dit echt de slechtste van alle mogelijke uitkomsten, zegt Micali. Uw concurrenten weten nu hoeveel u dit ding waardeert, waaruit ze kunnen afleiden hoe groot een klantenkring u bedient of welke technologie u beschikbaar heeft.
Daarom ontwikkelt de groep van Micali veilingen waarin deelnemers voldoende informatie over hun biedingen openbaar kunnen maken om een winnaar te bepalen, zonder de biedingen zelf bekend te maken. Ik denk dat dit uiteindelijk mainstream zal worden in de speltheorie, zegt Micali. Je kunt niet echt een zinvolle wetenschap van menselijk gedrag hebben terwijl je privacy negeert.
Wie heeft de touwtjes in handen?
Voor veel situaties die als spelletjes kunnen worden uitgedrukt, kan het Nash-evenwicht, zoals Daskalakis aantoonde, bijna onmogelijk te berekenen zijn. Maar dat betekent niet dat het gedrag van de spelers willekeurig is. Denk aan een raster van stadsstraten waar automobilisten talloze beslissingen nemen op tientallen kruispunten. Zelfs als de chauffeurs niet alle mogelijke gevolgen van alternatieve beslissingen evalueren, passen ze nog steeds enkele eenvoudige strategieën toe, bijvoorbeeld als je te lang stil hebt gezeten, sla dan een zijstraat in. Volgens Munther Dahleh, het associate hoofd van EECS, brengt het analyseren van dergelijke systemen de speltheorie heel dicht bij zijn eigen vakgebied, de controletheorie, die strategieën onderzoekt voor het besturen van dynamische systemen zoals de ledematen van robots en de vleugels van vliegtuigen. Wij hebben een andere kijk op deze problemen, zegt Dahleh. In plaats van het idee van evenwicht op te leggen en te zeggen 'Welke strategieën zouden mensen spelen onder dat evenwicht?', kijken we naar het gecontroleerde dynamische gedrag en stellen de vraag 'Welke notie van evenwicht ontstaat?'
Dahleh heeft inderdaad de instrumenten van de speltheorie toegepast op de analyse van verkeersstromen, waarbij hij heeft onderzocht welke soorten weginrichtingen het best geschikt zijn voor het sluiten van bepaalde routes. Zijn aanpak geldt ook voor andere grootschalige dynamische systemen, zoals het elektriciteitsnet.
Elke dag bieden stroomproducenten - exploitanten van kerncentrales, kolencentrales, windmolenparken en dergelijke - nieuwe schema's aan van hoeveel elektriciteit ze willen produceren, tegen welke prijs, op welk tijdstip van de dag. De nutsbedrijven die elektriciteit leveren, hebben ook beheerders die, op basis van de verwachte vraag van de consument, beslissen hoeveel stroom ze van elke provider afnemen. Stroomproductie en verbruik moeten exact op elkaar aansluiten, anders zijn de gevolgen desastreus.
Dahleh en Mardavij Roozbehani, PhD '08, een hoofdonderzoeker in het Laboratorium voor Informatie en Beslissingssystemen, toonden met behulp van de instrumenten van de speltheorie om de prikkels van zowel energieleveranciers als consumenten te analyseren, dat slimme meters in huis, die kunnen zorgen voor informatie over spotprijzen op de elektriciteitsmarkt en consumenten energie-intensieve huishoudelijke taken laten uitstellen tot ze het meest betaalbaar zijn, zou in feite pieken in de vraag kunnen veroorzaken die het hele net zouden neerhalen.
Dahleh heeft ook samengewerkt met Ozdaglar en haar man, de MIT-econoom Daron Acemoglu, om te analyseren hoe informatie zich door populaties verspreidt. Het spel in dit geval is er een waarin mensen de waarheid of onwaarheid van informatie die hen bereikt afwegen, terwijl ze ernaar streven de nauwkeurigheid van hun eigen overtuigingen te maximaliseren.
Dit zijn vragen die zowel in de sociologie als in de economie zijn bestudeerd, zegt Ozdaglar. Traditioneel gingen deze onderzoeken er echter van uit dat elke persoon in een bepaalde populatie informatie rechtstreeks van een andere kan ontvangen. Wat ingenieurs bieden, stelt Ozdaglar, zijn goed geslepen tools voor het analyseren van de onderliggende netwerkstructuur van de bevolking. De meeste mensen ontvangen bijvoorbeeld in feite de meeste van hun informatie van slechts een paar directe buren in het netwerk - en ze wijzen verschillende kansen toe aan de juistheid van de beweringen van verschillende buren.
Ik denk dat sociale wetenschappen en economie in het verleden anders met problemen omgingen dan ingenieurs, zegt Dahleh. Nu hebben we het allemaal over sociale netwerken - beslissingen in sociale netwerken, dynamiek op netwerken - dus ik denk dat de twee velden samenkomen.