Spieltheorie

aus Wikipedia, der freien Enzyklopädie

Die Spieltheorie (engl. game theory) ist ein Teilgebiet der Mathematik, das sich mit der Modellierung und Untersuchung von Gesellschaftsspielen, von im weitesten Sinn gesellschaftsspielähnlichen Interaktionssystemen sowie mit den in diesen eingesetzten Spielstrategien beschäftigt. Die Spieltheorie ist dabei weniger eine zusammenhängende Theorie als mehr ein Satz von Analyseinstrumenten. Anwendungen findet die Spieltheorie vor allem im Operations Research, in den Wirtschaftswissenschaften, in den Politikwissenschaften, in der Soziologie, in der Psychologie und seit den 1980ern auch in der Biologie. Gelegentlich werden auch außermathematische Arten der theoretischen Behandlung des Spiels als Spieltheorie bezeichnet; vergleiche etwa Homo ludens, Spielpädagogik und Ludologie.

Inhaltsverzeichnis 1 Geschichte 2 Methodik der Spieltheorie 2.1 Interaktion als Spiel modellieren 2.2 Lösungskonzepte 2.3 Gemischte vs. reine Strategien 2.4 Darstellungen eines Spiels 2.5 Einmalige vs. wiederholte Spiele 2.6 Kooperative vs. Nichtkooperative Spieltheorie 3 Spieltheorie im Mechanism Design 4 Beispiele 5 Siehe auch 6 Literatur 7 Weblinks

[Bearbeiten] Geschichte

Historischer Ausgangspunkt der Spieltheorie ist die Analyse von Gesellschaftsspielen durch John von Neumann (ungarisch: Neumann János Lajos) im Jahre 1928. Schnell erkannte John von Neumann die Anwendbarkeit des von ihm entwickelten Ansatzes zur Analyse wirtschaftlicher Fragestellungen, so dass 1944 im Buch "Spieltheorie und wirtschaftliches Verhalten" (Theory of Games and Economic Behavior), das er zusammen mit Oskar Morgenstern verfasste, bereits eine Verquickung zwischen der mathematischen Theorie und der wirtschaftswissenschaftlichen Anwendung erfolgte. Das Erscheinen dieses Buches wird im Allgemeinen als Startpunkt der modernen Spieltheorie angesehen. Erwähnenswert ist, dass es bereits vor und parallel zu John von Neumann spieltheoretische Analysen gab, insbesondere durch Bernoulli, Bertrand, Cournot, Edgeworth, Zeuthen und von Stackelberg. Diese spieltheoretischen Analysen waren jedoch immer Antworten auf spezifische Fragestellungen, ohne dass eine allgemeinere Theorie zur Analyse strategischer Interaktion daraus entwickelt worden wäre.

Für spieltheoretische Arbeiten wurden bisher fünf Wirtschaftsnobelpreise vergeben: 1994 an John Forbes Nash Jr., John Harsanyi und Reinhard Selten, 1996 an William Vickrey und 2005 an Robert Aumann und Thomas Schelling. Auch die Nobelpreise für die Erforschung begrenzter Rationalität an Herbert Simon 1978 und Daniel Kahneman 2002 stehen in engem Zusammenhang zu spieltheoretischen Fragestellungen.

[Bearbeiten] Methodik der Spieltheorie

[Bearbeiten] Interaktion als Spiel modellieren

Die Spieltheorie modelliert die verschiedensten Situationen als ein Spiel. Dabei ist der Begriff Spiel durchaus wörtlich zu nehmen: In der mathematisch-formalen Beschreibung wird festgelegt, welche Spieler es gibt, welchen sequentiellen Ablauf das Spiel hat und welche Handlungsoptionen jeder Spieler in den einzelnen Stufen der Sequenz hat. (Bei-)Spiele: Im Spiel Cournot-Duopol sind die Spieler die Firmen und ihre jeweilige Handlungsoption ist ihre Angebotsmenge. Im Bertrand-Duopol sind die Spieler wieder die Duopolisten, ihre Handlungsoptionen sind aber hier die Angebotspreise. Im Spiel Gefangenendilemma sind die Spieler die beiden Gefangenen und ihre Aktionsmengen sind aussagen und schweigen. In Anwendungen der Politikwissenschaft sind die Spieler oft Parteien oder Lobbyverbände, während in der Biologie die Spieler meistens Gene oder Spezies sind.

Zur Beschreibung eines Spiels gehört zudem eine Auszahlungsfunktion: Diese Funktion ordnet jedem möglichen Spielausgang einen Auszahlungsvektor zu, d.h. durch sie wird festgelegt, welchen Gewinn ein Spieler macht, wenn ein bestimmter Spielausgang eintritt. Bei Anwendungen der Wirtschaftswissenschaft ist die Auszahlung meistens als monetäre Größe zu verstehen, bei politikwissenschaftlichen Anwendungen kann es sich hingegen um Wählerstimmen handeln, während bei biologischen Anwendungen meistens die Auszahlung aus Reproduktionsfähigkeit oder Überlebensfähigkeit besteht.

Man kann in der Spieltheorie zwei bedeutende Aspekte erkennen:

• Formalisierung: Ein bedeutender Schritt ist, ein Spiel im Sinne der Spieltheorie zu formalisieren. Die Spieltheorie hat hierfür eine reichhaltige Sprache entwickelt. Siehe unter: Spieldarstellung
• Lösung: Abhängig vom Kontext kann man in einem weiteren Schritt eine Vorhersage des Spielausganges versuchen. Siehe hierfür: Lösungskonzepte (Spieltheorie).

Eine wichtige Technik beim Finden von Gleichgewichten in der Spieltheorie ist das Betrachten von Fixpunkten.

In der Informatik versucht man, mit Hilfe von Suchstrategien und Heuristiken (allgemein: Techniken der Kombinatorischen Optimierung und Künstlichen Intelligenz) bestimmte Spiele, wie Schach, SameGame, Awari, Go zu lösen oder z.B. zu beweisen, dass derjenige, der anfängt, bei richtiger Strategie immer gewinnt (das ist z.B. der Fall für Vier gewinnt, Qubic und Fünf in eine Reihe) oder z.B. derjenige, der den 2. Zug hat, immer wenigstens ein Unentschieden erzielen kann (Beispiel Mühle).

[Bearbeiten] Lösungskonzepte

Sobald ein Spiel definiert ist, kann man sodann das Analyseinstrumentarium der Spieltheorie anwenden, um beispielsweise zu ermitteln, welche die optimalen Strategien für alle Spieler sind und welches Ergebnis das Spiel haben wird, falls diese Strategien zur Anwendung kommen.

Um Fragestellungen spieltheoretisch zu analysieren, werden sogenannte Lösungskonzepte verwendet. Das weitaus prominenteste derartige Lösungskonzept, das Nash-Gleichgewicht, stammt von John Forbes Nash Jr. (1951). Die obige Fragestellung - welche möglichen Ausgänge ein Spiel hat, wenn sich alle Spieler individuell optimal verhalten - kann durch die Ermittlung der Nash-Gleichgewichte eines Spiels beantwortet werden: Die Menge der Nashgleichgewichte eines Spiels enthält per Definition diejenigen Strategieprofile, in denen sich ein einzelner Spieler durch Austausch seiner Strategie durch eine andere Strategie bei gegebenen Strategien der anderen Spieler nicht verbessern könnte.

Für andere Fragestellungen gibt es andere Lösungskonzepte. Wichtige sind das Minimax-Gleichgewicht, das wiederholte Streichen dominierter Strategien sowie Teilspielperfektion und in der kooperativen Spieltheorie der Core, der Nucleolus, die Verhandlungsmenge und die Imputationsmenge.

[Bearbeiten] Gemischte vs. reine Strategien

Während die reine Strategie eines Spielers eine Funktion ist, die jeder Spielstufe, in der die Aktionsmenge des Spielers nichtleer ist, eine Aktion zuordnet, ist eine gemischte Strategie eine Funktion, die jeder Spielstufe, in der die Aktionsmenge des Spielers nichtleer ist, eine Wahrscheinlichkeitsverteilung über der in dieser Spielstufe verfügbaren Aktionsmenge zuordnet. Damit ist eine reine Strategie der Spezialfall einer gemischten Strategie, in der immer dann, wenn die Aktionsmenge eine Spielers nichtleer ist, die gesamte Wahrscheinlichkeitsmasse auf eine einzige Aktion der Aktionsmenge gelegt wird. Man kann leicht zeigen, dass jedes Spiel, dessen Aktionsmengen endlich sind, ein Nash-Gleichgewicht in gemischten Strategien haben muss. In reinen Strategien ist die Existenz eines Nash-Gleichgewichtes hingegen für viele Spiele nicht gewährleistet. Die Analyse von Gleichgewichten in gemischten Strategien wurde wesentlich durch eine Reihe von Beiträgen John Harsanyis in den 70er und 80er Jahren vorangebracht.

[Bearbeiten] Darstellungen eines Spiels

Spiele werden entweder in strategischer (Normal-)Form oder in extensiver Form beschrieben. Die extensive Form kommt vor allem bei sequentiellen Spielen zum Einsatz, während die strategische Form bei den meisten einstufigen Spielen wie Gefangenendilemma, Ultimatumspiel, Spiel mit dem Untergang (chicken game) u.a. angewendet wird. Grundsätzlich kann aber jedes Spiel in beiden Formen beschrieben werden. Wird ein explizit mehrstufiges Spiel in der strategischen Form dargestellt, so spricht man von pseudo-strategischer Form, während die Darstellung eines einstufigen Spiels in extensiver Form als pseudo-extensive Form bezeichnet wird.

Spiele in strategischer Form kann man durch eine Auszahlungsmatrix veranschaulichen. In einer zweidimensionalen Auszahlungsmatrix entsprechen die Zeilen den Aktionen oder Strategien des ersten Spielers ("Zeilenspielers") und die Spalten den Aktionen oder Strategien des zweiten Spielers ("Spaltenspielers"). Die Felder der Matrix enthalten dann Informationen darüber, welche Auszahlungen die beiden Spieler erhalten, wenn die entsprechende Zeile und Spalte gespielt werden.

Unter einer Aktion eines Spielers versteht man die Handlung eines Spielers in einer Spielsituation, wohingegen man unter einer Strategie eine Funktion versteht, die jeder Spielsituation, in der ein Spieler eine nichtleere Aktionsmenge hat, eine Aktion aus dieser Menge zuordnet. Wenn ein Spiel aus einer einzigen Spielsituation besteht, so fallen Strategie und Aktion offensichtlich zusammen. Da Auszahlungsmatrizen vor allem zur Darstellung von einstufigen Spielen verwendet werden, sind es meistens Aktionen, für die die Zeilen und Spalten der Matrix stehen. Falls das Spiel mehrstufig ist und die Zeilen und Spalten der Matrix für Strategien aber nicht für Aktionen stehen, hat man es mit einer pseudo-strategischen Spieldarstellung zu tun.

Spiele in extensiver Form kann man durch gerichtete Graphen veranschaulichen. Dabei ist jeder Knoten, von dem Pfeile abgehen, eine Spielsituation, in der genau ein Spieler eine Aktion tätigen kann, während die von diesem Knoten abgehenden Pfeile die in dieser Spielsituation zur Auswahl stehenden Aktionen darstellen. Welcher Spieler es ist, der an einem Knoten ziehen darf, bestimmt die Spielerfunktion: Eine Spielerfunktion ist eine auf der Menge der Knoten des Spielbaums definierte Funktion, die jedem Knoten einen Spieler zuordnet, der dort ziehen darf. D.h. der von der Spielerfunktion einem Knoten y zugewiesene Spieler ist der einzige, der am Knoten y keine leere Aktionsmenge hat. Wenn zwei Knoten A und B durch einen Pfeil x von A nach B verbunden sind, so bedeutet dies, dass durch die Auswahl der Aktion x durch den Spieler, der in der Spielsituation A eine nichtleere Aktionsmenge hatte, der Punkt B erreicht wurde, wo eventuell ein anderer oder der gleiche Spieler wieder eine Aktion auswählen muss. Ein Knoten, von dem kein Pfeil abgeht, bezeichnet eine Spielsituation, in der kein Spieler mehr eine nichtleere Aktionsmenge hat - daher endet das Spiel. An diesem Knoten werden dann im allgemeinen die Auszahlungen verzeichnet, die alle Spieler erhalten, wenn dieser Spielausgang erreicht wird.

Den so beschriebenen Graphen nennt man Spielbaum und diese Art der Darstellung eine Baumdarstellung. Eine Strategie eines Spielers kann dann als eine Funktion angesehen werden, die auf den Knoten definiert ist, denen dieser Spieler von der Spielerfunktion zugeordnet wird. Sie bildet jeden dieser Knoten auf ein Element der in diesem Knoten verfügbaren Aktionsmenge ab, ist also eine Abbildung von dieser Knotenmenge in die Vereinigungsmenge aller Aktionsmengen dieses Spielers. Ein Strategieprofil kann als eine auf allen Knoten des Spielbaums definierte Funktion angesehen werden, die jedem Knoten ein Element desjenigen Aktionsraumes zuordnet, den der von der Spielerfunktion diesem Knoten zugeordnete Spieler an diesem Knoten hat. Ein Strategieprofil ist dann eine Abbildung von der Menge der Knoten in die Vereinigungsmenge aller Aktionsräume aller Spieler.

Bei vielen Spielen in extensiver Form wird davon ausgegangen, dass Spieler in bestimmten Situationen nicht wissen, welche Historie das Spiel bisher hatte: Sie wissen daher nicht eindeutig, in welchem Knoten sie sich befinden. Will man dies in einem Spielbaum graphisch verdeutlichen, so zeichnet man eine zusammenhängende Linie um die Menge der Knoten, von denen der Spieler nicht weiß, in welchem er sich befindet. Er weiß lediglich, dass er sich in einem von diesen Knoten befindet. Der von dieser Linie eingekreiste Bereich wird Informationsraum genannt. Eine Spielerfunktion weist sodann jedem Informationsraum (und nicht jedem Knoten) einen Spieler zu. Dieser Spieler ist der einzige, der bei diesem Informationsraum eine nichtleere Aktionsmenge hat. Auch die Definitionen von Strategie und Strategieprofil lassen sich in natürlicher Weise auf Informationsräume übertragen. Wichtig ist, dass ein Informationsraum nur aus Knoten bestehen kann, bei denen der Spieler die gleichen Aktionsmengen hat: Ansonsten könnte er aus den unterschiedlichen Aktionsmengen ableiten, in welchem Knoten er sich befindet (falls der Baum als Ganzes dem Spieler bekannt ist), was dem Konzept des Informationsraumes widersprechen würde.

[Bearbeiten] Einmalige vs. wiederholte Spiele

Ein Spiel, das nach einmaliger Durchführung nicht wiederholt wird, wird als sog. One-Shot-Game bezeichnet. Wird ein One-Shot-Game mehrmals hintereinander durchgeführt, wobei sich im allgemeinen die Gesamtauszahlung für jeden Spieler durch die (eventuell aufdiskontierten) Auszahlungen jedes einzelnen One-Shot-Games ergibt, so spricht man von einem wiederholten Spiel. Hat ein wiederholtes Spiel unendlich viele Wiederholungen, so bezeichnet man es als Superspiel.

Die Analyse wiederholter Spiele wurde wesentlich von Robert J. Aumann vorangebracht.

Wichtiges Element vieler wiederholter Spiele ist der sogenannte Backward-Breakdown, der sich ergeben kann, wenn die Spieler wissen, wieviele Runden das wiederholte Spiel hat.

[Bearbeiten] Kooperative vs. Nichtkooperative Spieltheorie

Die Unterscheidung zwischen kooperativer und nichtkooperativer Spieltheorie ist sehr verschwommen. Oft wird folgende Definition verwendet: Können die Spieler bindende Verträge abschließen, so spricht man von kooperativer Spieltheorie. Sind hingegen alle Verhaltensweisen (also auch eine mögliche Kooperation zwischen Spielern) self-enforcing, d.h. sie ergeben sich aus dem egoistischen Verhalten der Spieler, ohne dass bindende Verträge abgeschlossen werden können, so spricht man von nichtkooperativer Spieltheorie.

Fast alle prominenten Beispiele, die auch Laien bekannt sind, wie beispielsweise das Gefangenendilemma, das Spiel Kampf der Geschlechter usw., entstammen der nichtkooperativen Spieltheorie. Die nichtkooperative Spieltheorie verdrängt seit einigen Jahrzehnten die kooperative Spieltheorie in zunehmendem Maße, insbesondere in der Lehre an Universitäten. Heutzutage erscheinen viele Lehrbücher zur Spieltheorie und es gibt an Universitäten viele Veranstaltungen mit dem Titel Spieltheorie, in denen die kooperative Spieltheorie gar nicht mehr oder nur noch am Rande behandelt wird. Obwohl die Nobelpreisträger Robert J. Aumann und John Forbes Nash Jr. beide entscheidende Beiträge zur kooperativen Spieltheorie geleistet haben, wurde der Preis vom Nobelpreiskommitee ausdrücklich für ihre Beiträge zur nichtkooperativen Spieltheorie vergeben.

Nichtsdestotrotz wird in der aktuellen Forschung weiterhin die kooperative Spieltheorie untersucht, und ein Großteil neuer spieltheoretischer wissenschaftlicher Artikel sind der kooperativen Spieltheorie zuzuordnen.

Die weiterhin große Bedeutung der kooperativen Spieltheorie in der Forschung ist auch daran abzulesen, dass in der wissenschaftlichen Diskussion sehr präsente Forschungsfelder wie die Verhandlungstheorie und die Matching Theorie zu einem großen Teil mit den Mitteln der kooperativen Spieltheorie analysiert werden.

Siehe auch: Nash-Gleichgewicht.

[Bearbeiten] Spieltheorie im Mechanism Design

Die Spieltheorie wird unter anderem auch angewandt, um den Ausgang bestimmter regelbezogener Prozesse zu bestimmen oder festzulegen. Dies geschieht im Zuge der Lösungen für ein Mechanism Design Problem. Dieses Vorgehen kann nicht nur für "reine" Spiele, sondern auch für das Verhalten von Gruppen in Wirtschaft und Gesellschaft genutzt werden.

[Bearbeiten] Beispiele

Berühmte Probleme der Spieltheorie:

• Gefangenendilemma
• Spiel mit dem Untergang (chicken game)
• Hirschjagd
• Kampf der Geschlechter
• Ultimatumspiel
• Eisverkäufer-am-Strand-Problem
• Beauty Contest
• Triell
• Braess-Paradoxon

[Bearbeiten] Siehe auch

• Adjusted-Winner-Methode
• Algorithmische Spieltheorie
• Beauty Contest
• Bertrand-Wettbewerb
• Entscheidungstheorie
• Evolutionär stabile Strategie
• Imputation
• Kombinatorische Spieltheorie
• Minmax-Algorithmus
• Negativ-Null-Summen-Spiel
• Quid pro quo
• Shapley-Wert
• game semantics/Dialogische Logik
• Spiel mit vollständiger Information
• Teilungsproblem
• Tit-for-tat
• Tragik der Allmende (engl. tragedy of the commons)
• Ziegenproblem

[Bearbeiten] Literatur

• John von Neumann, Oscar Morgenstern: Theory of Games and Economic Behavior. University Press, Princeton NJ 1944, ⁶⁰2004. ISBN 0-691-11993-7
• Robert Axelrod: Die Evolution der Kooperation. Oldenbourg, München 2000. ISBN 3486539957
• Robert Axelrod: The Evolution of Cooperation. BasicBooks, New York 1984, 2003 (engl. Original). ISBN 0465021212
• Christian Rieck: Spieltheorie - eine Einführung. Rieck, Eschborn ⁵2006. ISBN 3-924043-91-4 (Sehr gute Einführung, didaktisch anschaulich geschrieben. Erklärt auch die Hintergründe zu den Konzepten)
• Avinash K. Dixit, Barry J. Nalebuff: Spieltheorie für Einsteiger. Strategisches Know-how für Gewinner. Schäffer-Poeschel, Stuttgart 1997. ISBN 3-7910-1239-8
• Avinash K. Dixit, Barry J. Nalebuff: Thinking Strategically. The Competitive Edge in Business, Politics, and Everyday Life. Norton, New York 1999 (Amerik. Original). ISBN 0393974219 (leicht lesbare Einführung in die Spieltheorie)
• Jörg Bewersdorff: Glück, Logik und Bluff. Mathematik im Spiel - Methoden, Ergebnisse und Grenzen. Vieweg, Wiesbaden 2003. ISBN 3528269979 (was die Spieltheorie über richtige Spiele aussagt - relativ elementar, viele historische Details, keine Ökonomie)
• Manfred Eigen, Ruthild Winkler: Das Spiel. Piper, München 1976, ⁷1987. ISBN 3492021514
• Morton D. Davis, Dietmar Rothermund: Spieltheorie für Nichtmathematiker. Oldenbourg, München 1972, 1999. ISBN 348656448X
• Drew Fudenberg, Jean Tirole: Game Theory. MIT Press, Cambridge Ma 1991, ⁸2002. ISBN 0-262-06141-4 (Zurzeit das Standard-Lehrbuch der Spieltheorie - zumindest für Wirtschaftswissenschaftler. Alle Grundlagen umfassend, sehr präzise, stark mathematisch formalisiert, für den Einstieg weniger geeignet)
• Shaun P. Hargreaves Heap, Yanis Varoufakis: Game Theory - A Critical Text. Routledge, New York 2004. ISBN 0415250951 (Theorien und ihre Bedeutung)
• Martin J. Osborne, Ariel Rubinstein: A Course in Game Theory, MIT Press 1994. Das Standardwerk an vielen Universitäten, vom didaktischen Wert her allerdings umstritten. Behandelt auch wesentliche Lösungskonzepte der kooperativen Spieltheorie. Mathematisch verhältnismäßig rigoros, allerdings werden die Beweise in äußerst kurzer Form präsentiert, was oft selbst bei mathematisch versierten Lesern ein Verständnis erschwert.
• Martin J. Osborne, Ariel Rubinstein: Bargaining and Markets, Academic Press 1990. Eine Darstellung der spieltheoretischen Verhandlungstheorie. Vorteil: Das Buch kann kostenlos und legal im Internet bezogen werden: http://ww2.economics.utoronto.ca/osborne/bm/
• Guillermo Owen: Game Theory, Academic Press 1995. Wahrscheinlich einer der mathematisch rigorostesten Texte, die in der Sekundärliteratur zu finden sind. Fast alle Aussagen werden bewiesen. Auch die kooperative Spieltheorie wird recht umfassend dargestellt. Die Beweise sind ausführlich und gut verständlich. Leider auch in der dritten Auflage des Buches viele Tippfehler!
• Bezalel Peleg, Peter Sudhölter: Introduction to the Theory of Cooperative Games, Kluwer Academic Publisher 2003. Eines der wenigen neueren Bücher, welche die kooperative Spieltheorie vorstellen.
• Walter Schlee: Einführung in die Spieltheorie. Vieweg, Wiesbaden 2004. ISBN 3528032146 (streng mathematisch)

[Bearbeiten] Weblinks

• Eintrag (englisch) in der Stanford Encyclopedia of Philosophy (inkl. Literaturangaben)
• Computer Games Group des Fachbereichs Informatik der Universität Maastricht
• Gametheory.net (englisch)
• Spieltheorie.de Grundbegriffe der Spieltheorie und nicht-mathematische, oft etwas provokante Anwendungsbeispiele
• Wikiludia
• Gambit - Software zur Analyse von endlichen, strategischen und extensiven Spielen