Das System spielen

Sie und ein Komplize bei einem großen Raubüberfall wurden von der Polizei geschnappt und werden in getrennten Räumen verhört. Wenn Sie beide über das Verbrechen schweigen, bekommen Sie gegen eine geringere Anklage jeweils ein Jahr Gefängnis. Wenn ihr beide quietscht, bekommt ihr jeweils fünf Jahre. Aber wenn nur einer von euch quietscht, wird der eine frei, während der andere 10 Jahre bekommt. Wenn Sie nicht wissen, was Ihr Komplize tun wird, was ist die rationale Entscheidung?

Asuman Özdaglar

Asuman Özdaglar

Dieses Rätsel, das als Gefangenendilemma bekannt ist, ist das bekannteste Beispiel für ein Spiel im technischen Sinne der Spieltheoretiker. Die Spieltheorie ist ein mathematischer Weg, um strategisches Denken zu beschreiben, und das Dilemma des Gefangenen veranschaulicht die drei Grundvoraussetzungen der Situationen, die es umfasst: Das Spiel muss mehrere Agenten (hier die beiden Komplizen) involvieren; jeder muss eine Entscheidung treffen (quietschen oder nicht quietschen); und jede Entscheidung muss eine quantifizierbare Auszahlung (die Gefängnisstrafen) beinhalten, die je nach den Entscheidungen der anderen Agenten variiert.



Die Spieltheorie ist seit 1950 ein fester Bestandteil der Wirtschaftsforschung, als John Nash, der von 1951 bis 1959 am MIT lehrte und Gegenstand des Films ist Ein schöner Geist , veröffentlichte die Samenpapier das würde ihm den Nobelpreis für Wirtschaftswissenschaften einbringen. Mit der Reife der Spieltheorie ist sie für dieses Feld noch wichtiger geworden. Allein in den letzten acht Jahren ging der Nobelpreis dreimal an Spieltheoretiker, um unter anderem die Logik der nuklearen Abschreckung zu beleuchten, die Umstände, unter denen freie Märkte das öffentliche Wohl maximieren können und die nicht, und die besten Lösungen zu passenden Problemen – Organe und Patienten, medizinische Bewohner und Krankenhäuser und dergleichen.

Aber auch in den Ingenieurwissenschaften und der Informatik hat die Spieltheorie in letzter Zeit Aufmerksamkeit erregt. Forscher analysieren damit heikle Probleme wie die Optimierung des Verkehrsflusses oder die Vermeidung von Stromausfällen.

Asuman Ozdaglar, SM ’98, PhD ’03, Professor für Elektrotechnik und Informatik, sagt, der Aufstieg des Internets habe dies notwendig gemacht. Historisch gesehen mussten sich die Ingenieure von Kommunikationsnetzen mit einer Vielzahl technischer Fragen auseinandersetzen – wie etwa Machtbeschränkungen und den relativen Vorzügen der Zentralisierung oder Dezentralisierung. Aber mit dem Internet hatten sie plötzlich auch mit menschlicher Handlungsfähigkeit zu tun.

Wenn ein Comcast-Abonnent in Boston und ein EarthLink-Abonnent in San Francisco Daten austauschen, laufen ihre Übertragungen über Netzwerke, die von mehreren verschiedenen Anbietern unterhalten werden: Comcast, EarthLink und andere dazwischen. Die gesamte Operation beruht sowohl auf der Zusammenarbeit als auch auf dem Wettbewerb dieser verschiedenen Parteien, sagt Ozdaglar. Wie entwerfen Sie Protokolle, die tatsächlich die richtigen Anreize für die Zusammenarbeit bieten? Mit anderen Worten: Warum funktioniert das Internet, obwohl es aus einzelnen Netzen besteht? Die Spieltheorie bietet eine Möglichkeit, diese Art von Frage zu beantworten.

Als Ingenieure begannen, die Spieltheorie auf Fragen innerhalb ihres Fachgebiets einzubringen, erkannten sie jedoch auch, dass ihr Handwerkszeug auf offene Fragen der Spieltheorie anwendbar war. Tatsächlich haben von den wenigen Forschern am Department of Electrical Engineering and Computer Science (EECS), die sich intensiv mit Spieltheorie beschäftigen, alle viel Zeit mit Fragen verbracht, die typischerweise von den Sozialwissenschaften behandelt werden.

Einmal gehen
EECS-Professor Constantinos Daskalakis ist ein gutes Beispiel. 2008 gewann er den Dissertationspreis der Association for Computing Machinery, indem er zeigte, wie Techniken aus der theoretischen Informatik ein zentrales Konzept der Spieltheorie neu beleuchten können: das Gleichgewicht.

Constantinos Daskalakis

Constantinos Daskalakis

Gleichgewicht ist die Idee, die Nash seinen Nobelpreis einbrachte, und das Nash-Gleichgewicht ist die am häufigsten untersuchte Art von Gleichgewicht. Es beschreibt ein Gleichgewicht von Strategien, die kein Spieler eines Spiels ein Motiv hat, einseitig zu ändern. Das einfachste Beispiel für ein Nash-Gleichgewicht ist das sogenannte Penalty-Kick-Spiel. Im Fußball gibt ein Elfmeter einem Offensivspieler einen Freistoß auf das Tor, wobei nur der Torwart verteidigt. Der Ball bewegt sich so schnell, dass der Torwart erraten muss, in welche Richtung er tauchen muss, bevor er getroffen wird. In der spieltheoretischen Version gewinnt der Torwart, wenn beide Spieler die gleiche Torhälfte wählen; wählen sie unterschiedliche Hälften, gewinnt der Schütze.

Der Gleichgewichtszustand für dieses Spiel besteht darin, dass beide Spieler bei jedem Tritt zufällig eine Richtung wählen, aber sicherstellen, dass sie beide Richtungen insgesamt gleich häufig wählen. In diesem Fall gewinnt jeder die Hälfte der Zeit und keiner kann seine Gewinnchancen verbessern, indem er von dieser Strategie abweicht. Wenn beispielsweise der Torwart jedes Mal plötzlich in die gleiche Richtung geht und der Schütze an der ursprünglichen Strategie festhält, bleibt die Gewinnquote des Torwarts nur gleich. Ein Schütze, der die Verschiebung bemerkt, könnte jedoch jeden Schuss gewinnen, indem er jedes Mal in die entgegengesetzte Richtung geht, sodass der Torwart keinen Anreiz hat, diese Änderung vorzunehmen.

Aber das Elfmeter-Spiel ist eines der einfachsten Spiele. Gleichgewichte auch für etwas komplexere Spiele zu finden, kann enorm schwierig sein. Daskalakis hat in seiner Dissertation bewiesen, dass das Nash-Gleichgewicht für einige spieltheoretisch beschreibbare Situationen so schwer zu berechnen ist, dass alle Computer der Welt es während der Lebensdauer des Universums nicht finden könnten. In diesen Fällen, argumentiert Daskalakis, haben die Menschen es wahrscheinlich auch nicht durch Versuch und Irrtum gefunden. Das bedeutet, dass Spieltheoretiker andere Analysewerkzeuge als das Nash-Gleichgewicht brauchen, wenn sie hoffen wollen, die reale Welt zu beschreiben.

Glücklicherweise hat die Informatik eine Reihe von Techniken zur Bestimmung der Komplexität von Berechnungen entwickelt, die beispielsweise Nash-Gleichgewichte erzeugen, aber auch eine Reihe von Techniken zur Identifizierung ungefährer Lösungen für ansonsten unlösbare Probleme. Daskalakis und seine Studenten konnten beispielsweise einen für ein seit 30 Jahren bestehendes wirtschaftswissenschaftliches Problem finden.

1981 zeigte Roger Myerson von der University of Chicago, wie man eine Auktion für einen einzelnen Artikel so strukturiert, dass der Verkäufer den größten Gewinn erzielen würde, wenn alle Bieter die Gebotsstrategien in ihrem besten Interesse anwenden würden. Diese Arbeit verhalf ihm 2007 zum Nobelpreis. Es stellte sich auch die damit verbundene Frage: Wie kann eine Auktion für mehr als einen Artikel am besten strukturiert werden? (Im Jargon der Ökonomen gilt jeder Markt mit einem einzigen Verkäufer und mehreren Käufern als Auktion; eine Christie's-Auktion ist eine, aber auch Verkäufe im Einzelhandel.) Diese Frage ist so komplex, dass es keine prägnante Beschreibung für die Auktion, die Ihnen den optimalen Gewinn bringt, sagt Daskalakis. Um den Umsatz über mehrere Artikel zu maximieren, muss der Verkäufer wahrscheinlich jeden Artikel zu weniger als dem Höchstpreis verkaufen, den jemand zu zahlen bereit wäre. Der Rabatt variiert jedoch je nach Faktoren wie der Mischung der verkauften Artikel und der Bevölkerung, aus der die Käufer stammen.

Die Informatik bietet eine neue Perspektive auf das Problem – was Daskalakis als Approximationsperspektive bezeichnet. Vielleicht findet man nicht die optimale Auktion, sagt er, aber auch eine Auktion, die 99 Prozent der besten Einnahmen garantiert, ist eine gute Auktion. Daskalakis und seine Studenten zeigten, dass die ideale Auktion – eine, die den Umsatz des Verkäufers maximiert – für jeden Multi-Item-Markt durch eine Kombination der Ergebnisse einfacherer Auktionen angenähert werden kann.

Eine etwas andere Herangehensweise an Auktionsprobleme kennzeichnet die Arbeit des Ingenieurprofessors Silvio Micali. Er und EECS-Professor Shafi Goldwasser sind die jüngsten Preisträger des Turing Award, der höchsten Auszeichnung in der Informatik. Der Preis würdigt zum großen Teil ihre Arbeit an sogenannten interaktiven Beweisen, bei denen ein Fragesteller mit begrenzten Rechenressourcen versucht, einem unzuverlässigen Gesprächspartner mit unbegrenzten Rechenressourcen das Ergebnis einer Berechnung zu entlocken. Ein Beispiel ist ein Zero-Knowledge-Proof, bei dem einer der Teilnehmer den Besitz einer Information, wie eines kryptografischen Schlüssels, feststellt, ohne diese preiszugeben. Zero-Knowledge-Beweise werden verwendet, um Transaktionen zwischen Finanzinstituten abzusichern, und mehrere Startups wurden gegründet, um sie zu kommerzialisieren.

Micali verfolgt mehrere spieltheoretische Forschungsprojekte, aber eines davon ist im Geiste sehr nahe an Zero-Knowledge-Beweisen. Bei vielen öffentlichen Auktionen – etwa wenn die Bundesregierung ungenutzte Funkfrequenzen an Telekommunikationsunternehmen versteigert – ist der Auktionator aus Gründen der Transparenz verpflichtet, alle Gebote aller Teilnehmer offenzulegen. Für ein Unternehmen, das an einer solchen Auktion teilnimmt und verliert, ist das wirklich das schlechteste aller möglichen Ergebnisse, sagt Micali. Ihre Wettbewerber wissen jetzt, wie sehr Sie diese Sache schätzen, woraus sie schließen können, wie groß Ihr Kundenkreis ist oder welche Technologie Ihnen zur Verfügung steht.

Daher entwickelt die Gruppe von Micali Auktionen, bei denen die Teilnehmer genügend Informationen über ihre Gebote veröffentlichen können, um einen Gewinner zu ermitteln, ohne die Gebote selbst preiszugeben. Ich glaube, dass dies irgendwann zum Mainstream in der Spieltheorie werden wird, sagt Micali. Sie können keine wirklich sinnvolle Wissenschaft des menschlichen Verhaltens betreiben, während Sie die Privatsphäre missachten.

Wer hat die Kontrolle?
Für viele Situationen, die als Spiele ausgedrückt werden können, kann das Nash-Gleichgewicht, wie Daskalakis gezeigt hat, fast unmöglich zu berechnen sein. Das bedeutet jedoch nicht, dass das Verhalten der Spieler zufällig ist. Stellen Sie sich ein Straßennetz vor, in dem die Fahrer an Dutzenden von Kreuzungen unzählige Entscheidungen treffen. Auch wenn die Fahrer nicht alle möglichen Konsequenzen alternativer Entscheidungen abwägen, verfolgen sie dennoch einige einfache Strategien – wenn Sie beispielsweise zu lange still sitzen, biegen Sie in eine Seitenstraße ab. Laut Munther Dahleh, dem stellvertretenden Leiter von EECS, bringt die Analyse solcher Systeme die Spieltheorie sehr nahe an sein eigenes Gebiet, die Kontrolltheorie, die Strategien zur Kontrolle dynamischer Systeme wie Roboterglieder und Flugzeugflügel untersucht. Wir haben eine andere Sicht auf diese Probleme, sagt Dahleh. Anstatt den Begriff des Gleichgewichts aufzuzwingen und zu fragen: „Welche Strategien würden die Leute unter diesem Gleichgewicht spielen?“ betrachten wir das kontrollierte dynamische Verhalten und stellen die Frage „Welcher Begriff von Gleichgewicht entsteht?“

Dahleh hat in der Tat die Werkzeuge der Spieltheorie auf die Analyse des Verkehrsflusses angewendet und untersucht, welche Arten von Straßenlayouts am besten geeignet sind, die Sperrung bestimmter Routen zu berücksichtigen. Sein Ansatz gilt auch für andere dynamische Großsysteme wie das Stromnetz.

Jeden Tag bieten Stromproduzenten – Betreiber von Kernkraftwerken, Kohlekraftwerken, Windparks und dergleichen – neue Fahrpläne an, wie viel Strom sie zu welchem ​​Preis und zu welcher Tageszeit zu produzieren bereit sind. Die Stromlieferanten haben auch Administratoren, die auf der Grundlage der erwarteten Verbrauchernachfrage entscheiden, wie viel Strom sie von jedem Anbieter beziehen. Stromproduktion und -verbrauch müssen exakt zusammenpassen, sonst sind die Folgen katastrophal.

Dahleh und Mardavij Roozbehani, PhD '08, ein leitender Wissenschaftler am Labor für Informations- und Entscheidungssysteme, zeigten, dass intelligente Zähler im Haushalt mit den Werkzeugen der Spieltheorie die Anreize sowohl von Stromanbietern als auch von Verbrauchern analysieren können Informationen über Spotpreise auf dem Strommarkt und die Möglichkeit, energieintensive Haushaltsaufgaben bis zum günstigsten Preis zu verschieben, könnten tatsächlich zu Nachfragespitzen führen, die das gesamte Stromnetz zum Einsturz bringen würden.

Stromstoßdiagramm


Dahleh hat auch mit Ozdaglar und ihrem Mann, dem MIT-Ökonomen Daron Acemoglu, zusammengearbeitet, um zu analysieren, wie sich Informationen in der Bevölkerung verbreiten. Das Spiel in diesem Fall ist eines, bei dem Menschen die Wahrheit oder Falschheit von Informationen abwägen, die sie erreichen, während sie sich bemühen, die Genauigkeit ihrer eigenen Überzeugungen zu maximieren.

Dies sind Fragen, die sowohl in der Soziologie als auch in den Wirtschaftswissenschaften untersucht wurden, sagt Ozdaglar. Traditionell gingen diese Untersuchungen jedoch davon aus, dass jede Person in einer bestimmten Population Informationen direkt von jeder anderen erhalten kann. Was Ingenieure anbieten, argumentiert Ozdaglar, sind ausgereifte Werkzeuge zur Analyse der zugrunde liegenden Netzwerkstruktur der Bevölkerung. Die meisten Menschen erhalten beispielsweise die meisten ihrer Informationen von nur wenigen unmittelbaren Nachbarn im Netzwerk – und ordnen der Richtigkeit der Behauptungen der verschiedenen Nachbarn unterschiedliche Wahrscheinlichkeiten zu.

Ich glaube, dass die Sozial- und Wirtschaftswissenschaften früher anders mit Problemen umgegangen sind als Ingenieure, sagt Dahleh. Jetzt reden wir alle über soziale Netzwerke – Entscheidungen in sozialen Netzwerken, Dynamiken in Netzwerken – also denke ich, dass die beiden Bereiche konvergieren.

verbergen