Normalformspiel

In der Spieltheorie beschreibt die Normalform ein Spiel . Anders als die extensive Form sind Normalformdarstellungen nicht grafisch , sondern stellen das Spiel mittels einer Matrix dar . Obwohl dieser Ansatz besonders nützlich ist, um strikt dominierte Strategien und Nash-Gleichgewichte zu identifizieren , geht im Vergleich zu extensiven Formen ein Teil der Information verloren. Die Normalformdarstellung eines Spiels umfasst alle wahrnehmbaren und denkbaren Strategien sowie deren entsprechende Auszahlungen für jeden Spieler.

In statischen Spielen mit vollständiger Information beschreibt die Normalform eines Spiels die Strategieräume und Auszahlungsfunktionen der Spieler. Der Strategieraum eines Spielers umfasst alle ihm zur Verfügung stehenden Strategien, während eine Strategie einen vollständigen Handlungsplan für jede Spielphase darstellt, unabhängig davon, ob diese Phase tatsächlich eintritt. Die Auszahlungsfunktion eines Spielers bildet das Kreuzprodukt der Strategieräume der Spieler auf die Auszahlungsmenge dieses Spielers ab (üblicherweise die Menge der reellen Zahlen, wobei die Zahl einen kardinalen oder ordinalen Nutzenwert repräsentiert – in der Normalform oft kardinal). Die Auszahlungsfunktion eines Spielers erhält also als Eingabe ein Strategieprofil (eine Spezifikation der Strategien aller Spieler) und liefert als Ausgabe eine Darstellung der Auszahlung.

Die bereitgestellte Matrix stellt eine Normalformdarstellung eines Spiels dar, in dem die Spieler gleichzeitig ziehen (oder zumindest den Zug des anderen Spielers nicht beobachten, bevor sie ihren eigenen ausführen) und die für die gespielten Aktionskombinationen festgelegten Auszahlungen erhalten. Spielt beispielsweise Spieler 1 oben und Spieler 2 links, erhält Spieler 1 4 und Spieler 2 3. In jeder Zelle repräsentiert die erste Zahl die Auszahlung für den Zeilenspieler (in diesem Fall Spieler 1) und die zweite Zahl die Auszahlung für den Spaltenspieler (in diesem Fall Spieler 2).

Symmetrische Spiele (bei denen die Auszahlungen nicht davon abhängen, welcher Spieler welche Aktion wählt) werden oft mit nur einer Auszahlung dargestellt. Dies ist die Auszahlung für den Zeilenspieler. Beispielsweise repräsentieren die Auszahlungsmatrizen rechts und links unten dasselbe Spiel.

Der topologische Raum von Spielen mit verwandten Auszahlungsmatrizen lässt sich ebenfalls abbilden, wobei benachbarte Spiele die ähnlichsten Matrizen aufweisen. Dies verdeutlicht, wie inkrementelle Anreizänderungen das Spiel verändern können.

Die Auszahlungsmatrix erleichtert die Eliminierung dominierter Strategien und wird üblicherweise zur Veranschaulichung dieses Konzepts verwendet. Im Gefangenendilemma beispielsweise kann jeder Gefangene entweder kooperieren oder abtrünnig werden. Wenn genau ein Gefangener abtrünnig wird, kommt er ungeschoren davon, während der andere lange eingesperrt wird. Wenn jedoch beide abtrünnig werden, verkürzt sich ihre Haftzeit. Man kann feststellen, dass Kooperieren strikt von Abtrünnigkeit dominiert wird . Dazu vergleicht man die ersten Zahlen in jeder Spalte, in diesem Fall 0 > −1 und −2 > −5. Dies zeigt, dass der Zeilenspieler unabhängig von der Entscheidung des Spaltenspielers mit Abtrünnigkeit besser fährt . Analog vergleicht man die zweiten Auszahlungen in jeder Zeile; auch hier gilt 0 > −1 und −2 > −5. Dies zeigt, dass der Zeilenspieler unabhängig von der Entscheidung der Zeile mit Abtrünnigkeit besser fährt . Dies beweist, dass das eindeutige Nash-Gleichgewicht dieses Spiels ( Defekt , Defekt ) ist.

Diese Matrizen stellen nur Spiele dar, in denen die Züge simultan erfolgen (oder allgemeiner: die Information unvollständig ist ). Die obige Matrix repräsentiert nicht das Spiel, in dem Spieler 1 zuerst zieht, Spieler 2 dies beobachtet und anschließend Spieler 2 zieht, da sie in diesem Fall nicht alle Strategien von Spieler 2 spezifiziert. Um dieses sequentielle Spiel darzustellen , müssen wir alle Aktionen von Spieler 2 spezifizieren, selbst solche, die im Spielverlauf niemals eintreten können. In diesem Spiel hat Spieler 2 wie zuvor die Aktionen „ Links“ und „Rechts“ . Anders als zuvor verfügt er über vier Strategien, die von den Aktionen von Spieler 1 abhängen. Die Strategien sind:

1. Links, wenn Spieler 1 oben spielt, und ansonsten links.
2. Links, wenn Spieler 1 oben spielt, und ansonsten rechts.
3. Rechts, wenn Spieler 1 oben spielt, und ansonsten links.
4. Rechts, wenn Spieler 1 oben spielt, und ansonsten rechts.

Rechts ist die Normalformdarstellung dieses Spiels abgebildet.

Damit ein Spiel in Normalform vorliegt, werden uns folgende Daten zur Verfügung gestellt:

Es gibt eine endliche Menge I von Spielern, wobei jeder Spieler mit i bezeichnet wird . Jeder Spieler i besitzt endlich k reine Strategien .

${\displaystyle S_{i}=\{1,2,\ldots ,k\}.}$

ADas reine Strategieprofil ist eine Zuordnung von Strategien zu Spielern, also einI-Tupel.

${\displaystyle {\vec {s}}=(s_{1},s_{2},\ldots ,s_{I})}$

so dass

${\displaystyle s_{1}\in S_{1},s_{2}\in S_{2},\ldots ,s_{I}\in S_{I}}$

ADie Auszahlungsfunktion ist eine Funktion

${\displaystyle u_{i}:S_{1}\times S_{2}\times \ldots \times S_{I}\rightarrow \mathbb {R} .}$

Die beabsichtigte Interpretation ist die Auszahlung, die einem einzelnen Spieler am Ende des Spiels zugesprochen wird. Um ein Spiel vollständig zu spezifizieren, muss daher die Auszahlungsfunktion für jeden Spieler der Spielermenge I = {1, 2, ..., I } angegeben werden.

Definition : Ein Spiel in Normalform ist eine Struktur

${\displaystyle \mathrm {T} =\langle I,\mathbf {S} ,\mathbf {u} \rangle }$

Wo:

${\displaystyle I=\{1,2,\ldots ,I\}}$

ist eine Gruppe von Spielern,

${\displaystyle \mathbf {S} =\{S_{1},S_{2},\ldots ,S_{I}\}}$

ist ein I- Tupel von reinen Strategiemengen, eine für jeden Spieler, und

${\displaystyle \mathbf {u} =\{u_{1},u_{2},\ldots ,u_{I}\}}$

ist ein I -Tupel von Auszahlungsfunktionen.

• Fudenberg, D. ; Tirole, J. (1991). Spieltheorie . MIT Press. ISBN 0-262-06141-4Die
• Leyton-Brown, Kevin; Shoham, Yoav (2008). Grundlagen der Spieltheorie: Eine prägnante, multidisziplinäre Einführung . San Rafael, CA: Morgan & Claypool Publishers. ISBN 978-1-59829-593-1DieEine 88-seitige mathematische Einführung; kostenlos online an vielen Universitäten verfügbar.
• Luce, R. D .; Raiffa, H. (1989). Spiele und Entscheidungen . Dover Publications. ISBN 0-486-65943-7Die
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagentensysteme: Algorithmische, spieltheoretische und logische Grundlagen . New York: Cambridge University Press . ISBN 978-0-521-89943-7DieEine umfassende Referenz aus rechnerischer Sicht; siehe Kapitel 3. Kostenlos online herunterladbar .
• Weibull, J. (1996). Evolutionäre Spieltheorie . MIT Press. ISBN 0-262-23181-6Die
• J. von Neumann und O. Morgenstern , Theorie der Spiele und des ökonomischen Verhaltens , John Wiley Science Editions, 1964. Ursprünglich 1944 von Princeton University Press veröffentlicht.