Spieltheorie: Matrixspiele. Ein Beispiel für die Lösung eines spieltheoretischen Problems in gemischten Strategien durch unseren Service

27.09.2019 | Konstruktion

Es wird ein Zwei-Personen-Nullsummenspiel genannt, bei dem jeder von ihnen einen endlichen Satz von Strategien hat. Die Regeln des Matrixspiels werden durch die Auszahlungsmatrix bestimmt, deren Elemente die Auszahlungen des ersten Spielers sind, die auch die Verluste des zweiten Spielers sind.

Matrix-Spiel ist ein antagonistisches Spiel. Der erste Spieler erhält die maximal garantierte (unabhängig vom Verhalten des zweiten Spielers) Auszahlung in Höhe des Spielpreises, ebenso erzielt der zweite Spieler den garantierten Mindestverlust.

Unter Strategie wird als Regelwerk (Prinzipien) verstanden, das die Wahl einer Handlungsvariante für jeden persönlichen Zug eines Spielers in Abhängigkeit von der aktuellen Situation bestimmt.

Jetzt über alles in Ordnung und im Detail.

Auszahlungsmatrix, reine Strategien, Spielpreis

IN Matrix-Spiel seine Regeln sind bestimmt Auszahlungsmatrix .

Stellen Sie sich ein Spiel vor, bei dem es zwei Teilnehmer gibt: den ersten Spieler und den zweiten Spieler. Lassen Sie den ersten Spieler haben M reine Strategien und zur Verfügung des zweiten Spielers - N reine Strategien. Da ein Spiel betrachtet wird, ist es natürlich, dass es in diesem Spiel Gewinne und Verluste gibt.

IN Zahlungsmatrix Die Elemente sind Zahlen, die die Gewinne und Verluste der Spieler ausdrücken. Gewinne und Verluste können in Punkten, Geld oder anderen Einheiten ausgedrückt werden.

Lassen Sie uns eine Auszahlungsmatrix erstellen:

Wenn der erste Spieler wählt ich-th reine Strategie, und der zweite Spieler J-te reine Strategie, dann ist die Auszahlung des ersten Spielers Aij Einheiten, und der Verlust des zweiten Spielers ist auch Aij Einheiten.

Als Aij + (- A ij) = 0, dann ist das beschriebene Spiel ein Nullsummen-Matrixspiel.

Das einfachste Beispiel für ein Matrixspiel ist das Werfen einer Münze. Die Spielregeln sind wie folgt. Der erste und der zweite Spieler werfen eine Münze und das Ergebnis ist Kopf oder Zahl. Wenn gleichzeitig Kopf und Kopf oder Zahl oder Zahl gewürfelt werden, gewinnt der erste Spieler eine Einheit, und in anderen Fällen verliert er eine Einheit (der zweite Spieler gewinnt eine Einheit). Dem zweiten Spieler stehen die gleichen zwei Strategien zur Verfügung. Die entsprechende Auszahlungsmatrix wäre:

Die Aufgabe der Spieltheorie besteht darin, die Wahl der Strategie des ersten Spielers zu bestimmen, die ihm den maximalen durchschnittlichen Gewinn garantieren würde, sowie die Wahl der Strategie des zweiten Spielers, die ihm den maximalen durchschnittlichen Verlust garantieren würde.

Wie wird eine Strategie in einem Matrixspiel gewählt?

Schauen wir uns noch einmal die Auszahlungsmatrix an:

Zuerst bestimmen wir die Auszahlung des ersten Spielers, wenn er verwendet ich Reine Strategie. Wenn der erste Spieler verwendet ich-te reine Strategie, dann ist es logisch anzunehmen, dass der zweite Spieler eine solche reine Strategie verwenden wird, aufgrund derer die Auszahlung des ersten Spielers minimal wäre. Der erste Spieler wird wiederum eine solche reine Strategie anwenden, die ihm die maximale Auszahlung bringen würde. Basierend auf diesen Bedingungen, die Auszahlung des ersten Spielers, die wir als bezeichnen v1 , wird genannt maximaler Gewinn oder geringerer Spielpreis .

Bei Für diese Werte sollte der erste Spieler wie folgt vorgehen. Schreiben Sie aus jeder Zeile den Wert des minimalen Elements aus und wählen Sie das Maximum aus ihnen aus. Somit ist die Auszahlung des ersten Spielers das Maximum des Minimums. Daher der Name - maximin win. Die Zeilennummer dieses Elements ist die Nummer der reinen Strategie, die der erste Spieler gewählt hat.

Lassen Sie uns jetzt den Verlust des zweiten Spielers bestimmen, wenn er verwendet J-te Strategie. In diesem Fall verwendet der erste Spieler seine eigene reine Strategie, bei der der Verlust des zweiten Spielers maximal wäre. Der zweite Spieler muss eine solche reine Strategie wählen, bei der sein Verlust minimal wäre. Der Verlust des zweiten Spielers, den wir so bezeichnen v2 , wird genannt minimaler Verlust oder Top Spielpreis .

Bei Lösen von Problemen zum Preis des Spiels und Bestimmen der Strategie Um diese Werte für den zweiten Spieler zu ermitteln, gehen Sie wie folgt vor. Schreiben Sie aus jeder Spalte den Wert des maximalen Elements aus und wählen Sie das Minimum aus. Somit ist der Verlust des zweiten Spielers das Minimum des Maximums. Daher der Name - Minimax-Gewinn. Die Spaltennummer dieses Elements ist die Nummer der reinen Strategie, die der zweite Spieler gewählt hat. Wenn der zweite Spieler "Minimax" verwendet, verliert er unabhängig von der Strategiewahl des ersten Spielers höchstens v2 Einheiten.

Beispiel 1

Das größte der kleinsten Elemente der Reihen ist 2, dies ist der niedrigere Preis des Spiels, die erste Reihe entspricht ihm, daher ist die Maximin-Strategie des ersten Spielers die erste. Das kleinste der größten Elemente der Spalten ist 5, dies ist der obere Preis des Spiels, die zweite Spalte entspricht ihm, daher ist die Minimax-Strategie des zweiten Spielers die zweite.

Nachdem wir nun gelernt haben, wie man den unteren und oberen Preis des Spiels, die Maximin- und Minimax-Strategien findet, ist es an der Zeit zu lernen, wie man diese Konzepte formal bezeichnet.

Die garantierte Auszahlung des ersten Spielers ist also:

Der erste Spieler muss eine reine Strategie wählen, die ihm das Maximum der minimalen Auszahlungen bringt. Dieser Gewinn (Maximin) wird wie folgt bezeichnet:

Der erste Spieler setzt seine reine Strategie so ein, dass der Verlust des zweiten Spielers maximal ist. Dieser Verlust ist wie folgt definiert:

Der zweite Spieler muss seine reine Strategie so wählen, dass sein Verlust minimal ist. Dieser Verlust (Minimax) wird wie folgt bezeichnet:

Ein weiteres Beispiel aus der gleichen Serie.

Beispiel 2 Gegeben sei ein Matrixspiel mit einer Auszahlungsmatrix

Bestimmen Sie die Maximin-Strategie des ersten Spielers, die Minimax-Strategie des zweiten Spielers, den unteren und oberen Preis des Spiels.

Lösung. Rechts von der Auszahlungsmatrix schreiben wir die kleinsten Elemente in ihren Zeilen aus und markieren das Maximum von ihnen und am unteren Rand der Matrix - die größten Elemente in den Spalten und wählen das Minimum von ihnen aus:

Das größte der kleinsten Elemente der Reihen ist 3, dies ist der niedrigere Preis des Spiels, die zweite Reihe entspricht ihm, daher ist die Maximin-Strategie des ersten Spielers die zweite. Das kleinste der größten Elemente der Spalten ist 5, dies ist der obere Preis des Spiels, die erste Spalte entspricht ihm, daher ist die Minimax-Strategie des zweiten Spielers die erste.

Sattelpunkt in Matrixspielen

Wenn der obere und der untere Preis des Spiels gleich sind, wird das Matrixspiel als Sattelpunkt angesehen. Das Gegenteil gilt auch: Wenn ein Matrixspiel einen Sattelpunkt hat, dann sind die oberen und unteren Preise des Matrixspiels gleich. Das entsprechende Element ist sowohl das kleinste in der Reihe als auch das größte in der Spalte und entspricht dem Preis des Spiels.

Wenn also , dann ist die optimale reine Strategie des ersten Spielers und die optimale reine Strategie des zweiten Spielers. Das heißt, gleiche untere und obere Preise des Spiels werden mit demselben Strategiepaar erzielt.

In diesem Fall das Matrixspiel hat eine Lösung in reinen Strategien .

Beispiel 3 Gegeben sei ein Matrixspiel mit einer Auszahlungsmatrix

Der niedrigere Preis des Spiels ist derselbe wie der obere Preis des Spiels. Somit beträgt der Preis des Spiels 5. Das heißt . Der Preis des Spiels entspricht dem Wert des Sattelpunktes. Die Maximin-Strategie des ersten Spielers ist die zweite reine Strategie, und die Minimax-Strategie des zweiten Spielers ist die dritte reine Strategie. Dieses Matrixspiel hat eine Lösung in reinen Strategien.

Lösen Sie das Matrixspielproblem selbst und sehen Sie sich dann die Lösung an

Beispiel 4 Gegeben sei ein Matrixspiel mit einer Auszahlungsmatrix

Finden Sie den unteren und oberen Preis des Spiels. Hat dieses Matrixspiel einen Sattelpunkt?

Matrixspiele mit optimal gemischter Strategie

In den meisten Fällen hat das Matrixspiel keinen Sattelpunkt, das entsprechende Matrixspiel hat also keine reinen Strategielösungen.

Aber es hat eine Lösung in optimal gemischten Strategien. Um sie zu finden, muss davon ausgegangen werden, dass das Spiel so oft wiederholt wird, dass man aufgrund der Erfahrung erraten kann, welche Strategie vorzuziehen ist. Daher ist die Entscheidung mit dem Konzept der Wahrscheinlichkeit und des Durchschnitts (Erwartung) verbunden. In der endgültigen Lösung gibt es sowohl ein Analogon des Sattelpunkts (dh die Gleichheit der unteren und oberen Preise des Spiels) als auch ein Analogon der ihnen entsprechenden Strategien.

Damit also der erste Spieler den maximalen durchschnittlichen Gewinn und der zweite Spieler den minimalen durchschnittlichen Verlust erzielt, sollten mit einer gewissen Wahrscheinlichkeit reine Strategien zum Einsatz kommen.

Wenn der erste Spieler reine Strategien mit Wahrscheinlichkeiten verwendet , dann der Vektor wird die gemischte Strategie des ersten Spielers genannt. Mit anderen Worten, es handelt sich um eine „Mischung“ aus reinen Strategien. Die Summe dieser Wahrscheinlichkeiten ist gleich eins:

Wenn der zweite Spieler reine Strategien mit Wahrscheinlichkeiten verwendet , dann der Vektor wird die gemischte Strategie des zweiten Spielers genannt. Die Summe dieser Wahrscheinlichkeiten ist gleich eins:

Wenn der erste Spieler eine gemischte Strategie verwendet P, und der zweite Spieler - eine gemischte Strategie Q, dann macht es Sinn erwarteter Wert der erste Spieler gewinnt (der zweite Spieler verliert). Um es zu finden, müssen Sie den gemischten Strategievektor des ersten Spielers (der eine einzeilige Matrix sein wird), die Auszahlungsmatrix und den gemischten Strategievektor des zweiten Spielers (der eine einspaltige Matrix sein wird) multiplizieren:

Beispiel 5 Gegeben sei ein Matrixspiel mit einer Auszahlungsmatrix

Bestimmen Sie die mathematische Erwartung für den Gewinn des ersten Spielers (den Verlust des zweiten Spielers), wenn die gemischte Strategie des ersten Spielers ist und die gemischte Strategie des zweiten Spielers ist.

Lösung. Gemäß der Formel für die mathematische Erwartung des Gewinns des ersten Spielers (Verlust des zweiten Spielers) ist sie gleich dem Produkt aus dem gemischten Strategievektor des ersten Spielers, der Auszahlungsmatrix und dem gemischten Strategievektor des zweiten Spielers:

Der erste Spieler wird eine solche gemischte Strategie genannt, die ihm die maximale durchschnittliche Auszahlung bringen würde, wenn das Spiel ausreichend oft wiederholt wird.

Optimale gemischte Strategie Der zweite Spieler wird eine solche gemischte Strategie genannt, die ihm den minimalen durchschnittlichen Verlust verschaffen würde, wenn das Spiel ausreichend oft wiederholt wird.

In Analogie zur Notation von Maximin und Minimax bei reinen Strategien werden optimale gemischte Strategien wie folgt bezeichnet (und zugeordnet mathematische Erwartung, also der Durchschnitt aus dem Gewinn des ersten Spielers und dem Verlust des zweiten Spielers):

In diesem Fall für die Funktion E Es gibt einen Sattelpunkt , was Gleichheit bedeutet.

Um die optimalen gemischten Strategien und Sattelpunkte zu finden, d.h. Lösen Sie das Matrixspiel in gemischten Strategien , müssen wir das Matrixspiel auf das Problem reduzieren Lineares Programmieren, also auf das Optimierungsproblem, und lösen Sie das entsprechende Problem der linearen Programmierung.

Reduktion eines Matrixspiels auf ein lineares Programmierproblem

Um ein Matrixspiel in gemischten Strategien zu lösen, müssen Sie eine gerade Linie bilden Problem der linearen Programmierung Und seine Doppelaufgabe. Beim dualen Problem wird die erweiterte Matrix, die die Koeffizienten von Variablen im Beschränkungssystem, konstante Terme und Koeffizienten von Variablen in der Zielfunktion speichert, transponiert. In diesem Fall ist das Minimum der Zielfunktion des ursprünglichen Problems dem Maximum des dualen Problems zugeordnet.

Zielfunktion im Problem der direkten linearen Programmierung:

Das Nebenbedingungssystem im direkten Problem der linearen Programmierung:

Zielfunktion im dualen Problem:

Das Nebenbedingungssystem im dualen Problem:

Bezeichnen Sie den optimalen Plan des Problems der direkten linearen Programmierung

und der optimale Plan des dualen Problems ist mit bezeichnet

Lineare Formen für die entsprechenden optimalen Designs werden mit und bezeichnet.

und Sie müssen sie als Summe der entsprechenden Koordinaten der optimalen Pläne finden.

In Übereinstimmung mit den Definitionen des vorherigen Abschnitts und den Koordinaten optimaler Pläne gelten die folgenden gemischten Strategien des ersten und zweiten Spielers:

Mathematiker haben das bewiesen Spielpreis wird in Form von linearen Formen optimaler Pläne wie folgt ausgedrückt:

das heißt, es ist der Kehrwert der Summen der Koordinaten der optimalen Pläne.

Wir Praktiker können diese Formel nur anwenden, um Matrixspiele in gemischten Strategien zu lösen. Wie Formeln zum Finden optimaler gemischter Strategien jeweils der erste und zweite Spieler:

wobei die zweiten Faktoren Vektoren sind. Optimale gemischte Strategien sind auch Vektoren, wie wir bereits im vorherigen Absatz definiert haben. Wenn wir also die Zahl (den Preis des Spiels) mit dem Vektor (mit den Koordinaten der optimalen Pläne) multiplizieren, erhalten wir auch einen Vektor.

Beispiel 6 Gegeben sei ein Matrixspiel mit einer Auszahlungsmatrix

Finden Sie den Preis eines Spiels v und optimale gemischte Strategien und .

Lösung. Wir stellen das diesem Matrixspiel entsprechende lineare Programmierproblem zusammen:

Wir erhalten die Lösung des direkten Problems:

Wir finden die lineare Form optimaler Pläne als Summe der gefundenen Koordinaten.

Inhalt 1 allgemeine Informationen 2 1.1 Spiele. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Bewegungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Strategien. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Matrixspiel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Spurpunkt. Reine Strategien 7 2.1 Beispiele. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Beispiel 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Beispiel 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Gemischte Strategien 9 3.1 Spiel 2×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Beispiele. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Beispiel 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Beispiel 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Geometrische Interpretation. . . . . . . . . . . . . . . . . . . . 12 3.2 Spiele 2×n und m×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Beispiel 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Allgemeines aus der Spieltheorie 1.1. Spiele Spieltheorie ist mathematische Theorie Konfliktsituationen, d.h. solche Situationen, in denen die Interessen zweier oder mehrerer Parteien mit unterschiedlichen Zielen kollidieren. Ein Spiel ist eine durch bestimmte Regeln geregelte Konfliktsituation, die Folgendes angeben soll: mögliche Optionen für die Aktionen der Teilnehmer, das quantitative Ergebnis des Spiels oder die Zahlung (Gewinn, Verlust), zu der eine bestimmte Reihe von Zügen führt, in Höhe von Informationen jeder Seite über das Verhalten der anderen. Paarspiel – ein Spiel, an dem nur zwei Parteien (zwei Spieler) teilnehmen. Nullsummen-Paarspiel – ein Paarspiel, bei dem der Zahlungsbetrag Null ist, d.h. Der Verlust des einen Spielers entspricht dem Gewinn des anderen. Abhängig von der Einstellung jedes Spielers zum Wert der Auszahlungsfunktion werden Paarspiele unterteilt: Der Verlust des einen Spielers entspricht dem Gewinn des anderen. Ein nicht-antagonistisches Spiel ist ein Paarspiel, bei dem die Spieler unterschiedliche, aber nicht direkt gegensätzliche Ziele verfolgen. 2 1.2. Moves Move - die Wahl einer der in den Spielregeln vorgesehenen Aktionen, die Umsetzung dieser Wahl Es gibt zwei Arten von Moves: Persönlicher Zug - + bewusste Wahl einer der in den Spielregeln vorgesehenen Aktionen + Implementierung dieser Wahl Zufallszug - Ein Zufallszug ist eine Auswahl aus einer Reihe von Möglichkeiten, die nicht durch die Entscheidung des Spielers, sondern durch einen zufälligen Auswahlmechanismus durchgeführt wird. Im Folgenden betrachten wir paarweise Nullsummenspiele, die nur persönliche Züge enthalten. Jede Seite hat keine Informationen über das Verhalten der anderen. 3 1.3. Strategien Die Strategie eines Spielers ist eine Reihe von Regeln, die die Wahl der Aktionen für jeden persönlichen Zug dieses Spielers bestimmen, abhängig von der Situation, die sich während des Spiels entwickelt hat. Abhängig von der Anzahl möglicher Strategien werden Spiele in endlich und unendlich unterteilt. Ein unendliches Spiel ist ein Spiel, bei dem mindestens einer der Spieler unendlich viele Strategien hat. Ein endliches Spiel ist ein Spiel, bei dem jeder Spieler nur eine endliche Anzahl von Strategien hat. Die Anzahl der aufeinanderfolgenden Züge für einen der Spieler bestimmt die Aufteilung der Spiele in Ein-Zug- und Mehrfach-Zug- oder Positionsspiele. + In einem One-Move-Spiel trifft jeder Spieler nur eine Wahl aus den möglichen Optionen und legt dann den Ausgang des Spiels fest. + Ein Multi-Move- oder Positionsspiel entwickelt sich im Laufe der Zeit und stellt eine Reihe aufeinanderfolgender Phasen dar, von denen jede nach dem Zug eines der Spieler und der entsprechenden Änderung der Situation erfolgt. Bei einem One-Move-Spiel trifft jeder Spieler nur eine Wahl aus den möglichen Optionen und legt dann das Ergebnis des Spiels fest. Die optimale Strategie eines Spielers ist eine Strategie, die dem gegebenen Spieler bei vielen Wiederholungen des Spiels den maximal möglichen durchschnittlichen Gewinn (oder äquivalent den minimal möglichen durchschnittlichen Verlust) verschafft. In der Spieltheorie basieren alle Empfehlungen auf der Annahme vernünftigen Verhaltens der Spieler. Die in jeder Konfliktsituation unvermeidlichen Fehlkalkulationen und Fehler der Spieler sowie die spieltheoretischen Elemente Spannung und Risiko bleiben unberücksichtigt. 4 1.4. Matrixspiel Ein Matrixspiel ist ein endliches Nullsummenspiel mit einem Zug. mögliche Wege Maßnahmen: Entsprechend den gewählten Handlungsmethoden (Strategien) wird das erzielte Ergebnis ermittelt. Schauen wir uns ein Beispiel an. Lassen Sie es zwei Spieler A und B geben, von denen einer wählen kann i-te Strategie aus m möglichen Strategien A1 , A2 , ...Am , und die zweite wählt j-te Strategie ihrer möglichen Strategien B1, B2, ... Bm. Dadurch gewinnt der erste Spieler aij und der zweite Spieler verliert diesen Wert. Aus den Zahlen aij bilden wir die Matrix   a11 a11 · · · a1n  a21 a22 · · · a2n    A = (aij) =  .. .. .. ..   . . . .  am1 am2 · · · amn Die Matrix A = (aij), i = 1, m, j = 1, n heißt Auszahlungsmatrix oder Matrix des m × n-Spiels. In dieser Matrix stehen die Zeilen immer für die Strategien des gewinnenden (maximierenden) Spielers A, also des Spielers, der versucht, seine Auszahlung zu maximieren. Die Spalten sind für die Strategien des verlierenden Spielers B reserviert, dh des Spielers, der versucht, das Effizienzkriterium zu minimieren. Spielnormalisierung ist der Prozess der Reduzierung eines Positionsspiels auf ein Matrixspiel. Ein Spiel in Normalform ist ein auf ein Matrixspiel reduziertes Positionsspiel Situation. Spiellösung - Finden der optimalen Strategien beider Spieler und Bestimmung des Spielwerts Der Spielwert ist der erwartete Gewinn (Verlust) der Spieler. Die Lösung des Spiels kann entweder in reinen Strategien gefunden werden - wenn der Spieler einer einzigen Strategie folgen muss, oder in gemischten Strategien, wenn der Spieler zwei oder mehr reine Strategien mit bestimmten Wahrscheinlichkeiten verwenden muss. Letztere werden in diesem Fall als aktiv bezeichnet. 5 Die gemischte Strategie eines Spielers ist ein Vektor, dessen jede Komponente die Häufigkeit der Nutzung der entsprechenden reinen Strategie durch den Spieler zeigt. Maximin oder niedrigerer Preis des Spiels - Zahl α = max min aij i j Maximin-Strategie (String) - die vom Spieler gewählte Strategie, um seine Mindestauszahlung zu maximieren. Offensichtlich verschafft sich Spieler A bei der Wahl der vorsichtigsten Maximin-Strategie (unabhängig vom Verhalten des Gegners) eine garantierte Auszahlung von mindestens α. Maximin oder die oberen Kosten des Spiels - die Zahl β = min max aij j i Minimax-Strategie (Spalte) - die vom Spieler gewählte Strategie, um seinen maximalen Verlust zu minimieren. Bei der Wahl der vorsichtigsten Minimax-Strategie lässt Spieler B offensichtlich Spieler A unter keinen Umständen mehr als β gewinnen. Der niedrigere Preis des Spiels übersteigt immer nicht den oberen Preis des Spiels α = max min aij 6 min max aij = β i j j i Satz 1 (der Hauptsatz der Theorie der Matrixspiele). Jedes endliche Spiel hat mindestens eine Lösung, vielleicht im Bereich gemischter Strategien. 6 2. Spiele mit Sattelspitze. Lösung in reinen Strategien Ein Spiel mit Sattelpunkt ist ein Spiel, für das α = max min aij = min max aij = β i j j i Bei Spielen mit Sattelpunkt besteht das Finden einer Lösung darin, optimale Maximin- und Minimax-Strategien zu wählen. allgemeine Bedeutung untere und obere Preise des Spiels α=β=ν 2.1. Beispiele Beispiel 1 Finden Sie eine Lösung in reinen Strategien des Spiels, gegeben durch die Matrix   8 4 7 A= 6 5 9  7 7 8 Lösung: Bestimmen Sie den oberen und unteren Preis des Spiels. Dazu finden wir das Minimum der Zahlen aij in i-te Zeileαi = min aij j und das Maximum der Zahlen aij in j-te Spalte βj = max aij i Wir schreiben die Zahlen αi (Zeilenminima) rechts neben die Auszahlungsmatrix als zusätzliche Spalte. Wir schreiben die Zahlen βi (Spaltenmaxima) als zusätzliche Zeile unter die Matrix: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Finde das Maximum der Zahlen αi α = max αi = 7 i und das Minimum der Zahlen βj β = min βj = 7 j α = β - das Spiel hat einen Sattelpunkt. Die optimale Strategie für den Spieler ist die Strategie A3 , und für den Spieler B - die Strategie B2 , die Nettokosten des Spiels ν = 7 Beispiel 2 Die Auszahlungsmatrix ist gegeben: 1 1 2   1 2 1 1 2 Finden Sie die Lösung des Spiels in reinen Strategien. Lösung: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Das Spiel hat sechs Sattelpunkte. Die optimalen Strategien sind: A1 und B3 oder B4 A3 und B3 oder B4 A4 und B3 oder B4 8 3. Lösung des Spiels in gemischten Strategien Für α ̸= β. Für den Fall, dass beide Spieler bei der Auswahl ihrer Strategien keine Informationen über die Wahl des anderen haben, bietet das Spiel eine Lösung in gemischten Strategien. SA = (p1 , p2 , ..., pm) ist die gemischte Strategie von Spieler A, bei der die Strategien A1 , A2 , ..., Am mit Wahrscheinlichkeiten ∑ m p1 , p2 , ..., pm , pi angewendet werden = 1, pi > 0, i = 1, m i=1 SB = (q1 , q2 , ..., qn) ist eine gemischte Strategie von Spieler B, bei der die Strategien B1 , B2 , ..., Bm mit Wahrscheinlichkeiten angewendet werden ∑ n q1 , q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 = aij p∗i qi∗ j=1 i=1 2 × n, m × 2). Wenn einer der Spieler eine optimale gemischte Strategie verwendet, dann ist seine Auszahlung gleich dem Preis des Spiels ν, unabhängig von den Wahrscheinlichkeiten, mit denen der zweite Spieler die Strategien verwenden wird, die in der optimalen enthalten sind (einschließlich reiner Strategien). 9 3.1. 2 × 2-Spiel Betrachten Sie ein 2 × 2-Spiel mit der Matrix: () a11 a21 a21 a22 Lassen Sie das Spiel keine Lösung in reinen Strategien haben. Finden wir die optimalen Strategien SA∗ und SB∗ . Zuerst definieren wir die Strategie SA∗ = (p∗1 , p∗2). Wenn Partei A an Strategie ν festhält, bleibt die Auszahlung nach dem Theorem unabhängig von der Vorgehensweise von Partei B gleich dem Preis des Spiels ν. Wenn also Partei A an der optimalen Strategie SA∗ = (p∗1 , p∗2) festhält, kann Partei B jede ihrer Strategien anwenden, ohne die Auszahlung zu ändern. Wenn Spieler B dann eine reine Strategie B1 oder B2 anwendet, erhält der Spieler eine durchschnittliche Auszahlung in Höhe des Spielpreises: a11 p∗1 + a21 p∗2 = ν ← für Strategie B1 beachten Sie, dass p∗1 + p ∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Spielwert: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 Ebenso wird die optimale Strategie von Spieler B gefunden: SB∗ = (q1∗ , q2∗). Unter Berücksichtigung von q1∗ + q2∗ = 1: q1∗ = a2 2 − a1 2 a11 + a22 − a12 − a21 q2∗ = a1 1 − a2 1 a11 + a22 − a12 − a21 3.1.1. Beispiele Beispiel 3 Finde eine Lösung für das Spiel mit Matrix () −1 1 A= 1 −1 10 Lösung: Das Spiel hat keinen Sattelpunkt, da α= -1, β = 1, α ̸= β. Wir suchen eine Lösung in gemischten Strategien. Mit den Formeln für p∗ und q ∗ erhalten wir p∗1 = p∗2 = 0,5 und q1∗ = q2∗ = 0,5, ν = 0 Somit ist SA∗ = (0,5, 0,5) SB∗ = (0,5, 0,5) Beispiel 4 Finden Sie eine Lösung für das Spiel mit Matrix () 2 5 A= 6 4 Lösung: Das Spiel hat keinen Sattelpunkt, da α= 4, β = 5, α ̸= β. Wir suchen eine Lösung in gemischten Strategien. Durch Formeln für p∗ und q 0.8) 11 3.1.2. Geometrische Interpretation Dem 2×2-Spiel kann eine einfache geometrische Interpretation gegeben werden. Nehmen wir einen Einheitsschnitt der Abszissenachse, jedem Punkt verbinden wir eine gemischte Strategie S = (p1 , p2) = (p1 , 1 − p1) p2 , Strategien A2 - der Abstand zum linken Ende. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ das rechte Ende des Abschnitts (x = 1) - Strategie A2 An den Enden des Abschnitts werden zwei Senkrechte zur Abszissenachse wiederhergestellt: Achse I - I - die Auszahlung wird mit der Strategie A1 verschoben Achse II - II - die Auszahlung wird mit der Strategie A2 verschoben Lassen Sie Spieler B die Strategie B1 anwenden; sie gibt auf den Achsen I − I bzw. II − II die Punkte mit den Ordinaten a11 und a21 an. Wir ziehen die Linie B1 − B1′ durch diese Punkte. Für jede gemischte Strategie SA = (p1 , p2) wird die Auszahlung des Spielers durch den Punkt N auf der Linie B1 − B1′ bestimmt, der dem Punkt SA auf der x-Achse entspricht, der das Segment in Bezug auf p2 teilt: p1 . Offensichtlich lässt sich die Gerade B2 − B2′, die die Auszahlung für die Strategie B2 bestimmt, genauso konstruieren. 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Es gilt die optimale Strategie SA∗ zu finden, d.h. so dass die minimale Auszahlung von Spieler A (mit dem schlechtesten Verhalten von Spieler B für ihn) zu einem Maximum werden würde. Dazu wird für die Strategien B1, B2 eine Untergrenze für die Auszahlung von Spieler A konstruiert, d.h. gestrichelte Linie B1 N B2′ ;. Auf dieser Grenze liegt die minimale Auszahlung von Spieler A für jede seiner gemischten Strategien, der Punkt N, an dem diese Auszahlung ein Maximum erreicht und die Lösung und den Preis des Spiels bestimmt. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗S . 1∗ P Die Ordinate des Punktes N ist nichts als der Wert des Spiels ν, seine Abszisse ist gleich ∗2 , und der Abstand zum rechten Ende des Segments ist gleich ∗1 , d.h. die Entfernung vom Punkt SA∗ zu den Enden des Segments sind gleich den Wahrscheinlichkeiten ∗2 und ∗1 der Strategien A2 und A1 der optimalen gemischten Strategie von Spieler A. In diesem Fall wurde die Lösung des Spiels durch die bestimmt Schnittpunkt der Strategien B1 und B2 . Unten ist der Fall gezeigt, wenn die optimale Strategie des Spielers die reine Strategie A2 ist. Hier ist Strategie A2 (für jede Strategie des Gegners) profitabler als Strategie A1 , 13 .y .y .I .I I .I I. I .B2′ . 1′B .B1′B . 2 .B2′ B . 2 .B1 .v = a21 .B1 .v = a21 I. I I. I .I . .x .ich . .X 2∗P. A∗ S = A2 . 2∗P. A∗ S = A2 Rechts ist der Fall dargestellt, dass Spieler B eine absichtlich unrentable Strategie hat Die geometrische Interpretation macht es möglich, auch den niedrigeren Preis des Spiels α und den oberen β .y .I .I I .B2 zu visualisieren .B1′ .N .B1 .B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗S . 1∗ P Auf dem gleichen Graphen kann man auch die optimalen Strategien von Spieler B geometrisch interpretieren. Man sieht leicht, dass der Anteil q1∗ der Strategie B1 der optimalen gemischten Strategie SB∗ = (q1∗ , q2∗) gleich dem Verhältnis der Länge des Segments KB2 zur Summe der Längen der Segmente ist KB1 und KB2 auf der Achse I − I: .y .I .I I .B2 .B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗S . 1∗ P 14 KB2 q1∗ = KB2 + KB1 oder LB2′ q1∗ = LB2′ + LB1′ das Maximum der unteren Grenze der Auszahlung berücksichtige das Minimum der oberen Grenze. .y .I .I I .A2 .A'1 .N .A1 .A'2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. 2 × n- und m × 2-Spiele Die Lösung von 2 × n- und m × 2-Spielen basiert auf dem folgenden Satz. Satz 3. Jedes endliche Spiel m × n hat eine Lösung, bei der die Anzahl der aktiven Strategien jeder Seite die kleinste von m und n nicht überschreitet. Nach diesem Satz hat ein 2 × n-Spiel immer eine Lösung, bei der jeder Spieler höchstens zwei aktive Strategien hat. Man muss diese Strategien nur finden, und aus dem 2 × n-Spiel wird ein 2 × 2-Spiel, das elementar gelöst wird. Das Finden aktiver Strategien kann grafisch erfolgen: 1) eine grafische Interpretation wird erstellt; 2) die untere Grenze der Verstärkung wird bestimmt; 3) An der unteren Auszahlungsgrenze werden zwei Strategien des zweiten Spielers unterschieden, die zwei Linien entsprechen, die sich am Punkt mit der maximalen Ordinate schneiden (wenn sich mehr als zwei Linien dort schneiden, wird ein beliebiges Paar genommen) - diese Strategien sind aktiv Strategien von Spieler B. Somit reduziert sich das 2 × n-Spiel auf das 2 × 2-Spiel.Das m × 2-Spiel kann ebenfalls gelöst werden, mit dem Unterschied, dass die obere Auszahlungsgrenze nicht konstruiert wird und nicht das Maximum, sondern das Minimum darauf gesucht wird . Beispiel 5 Finden Sie eine Lösung für das Spiel () 7 9 8 A= 10 6 9 Lösung: Mit der geometrischen Methode wählen wir aktive Strategien aus. Die Linien B1 − B1′ , B2 − B2′ und B3 − B3′ entsprechen den Strategien B1 , B2 , B3 . Die unterbrochene Linie B1 N B2 ist die untere Grenze der Auszahlung des Spielers. Das Spiel hat eine Lösung S∗A = (23 , 31); S∗B = (0,5; 0,5; 0); v = 8,16 .y .I .I I . 1' B B . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .X 2∗P. A∗S . 1∗ P 17 Indexspiel, 2 Zug, 3 2 × 2, 10 persönlich, 3 2 × 2, 9 zufällig, 3 Geometrie, 12 reiner Spielwert, 7 Beispiele, 10 2 × n, 9, 16 m × 2, 9 , 16 unendlich, 4 Normalform, 5 endlich, 4 Mehrweg, 4 Einweg, 4 Matrix, 5 Doppel, 2 Nullsumme, 2 Antagonistisch, 2 Nicht-Antagonistisch, 2 Lösung, 5 Gemischte Strategien, 5, 9 reine Strategien 5 Spieltheorie, 2 18

Wenn es mehrere Konfliktparteien (Personen) gibt, von denen jede eine Entscheidung trifft, die durch ein bestimmtes Regelwerk bestimmt wird, und jede der Parteien den Endzustand der Konfliktsituation mit Zahlungen kennt, die für jede der Parteien vorbestimmt sind, dann sagen wir das Es gibt ein Spiel.

Die Aufgabe der Spieltheorie besteht darin, für einen gegebenen Spieler eine solche Verhaltensweise zu wählen, von der eine Abweichung seine Auszahlung nur schmälern kann.

Einige Definitionen des Spiels

Die quantitative Bewertung der Ergebnisse des Spiels wird als Zahlung bezeichnet.

Doppel (zwei Personen) heißt Nullsummenspiel, wenn die Summe der Zahlungen Null ist, d.h. wenn der Verlust des einen Spielers gleich dem Gewinn des anderen ist.

Eine eindeutige Beschreibung der Wahl des Spielers in jeder der möglichen Situationen, in denen er einen persönlichen Zug machen muss, wird genannt Spieler Strategie .

Die Strategie eines Spielers wird als optimal bezeichnet, wenn sie dem Spieler bei vielen Wiederholungen des Spiels die maximal mögliche durchschnittliche Auszahlung (oder, was dasselbe ist, die minimal mögliche durchschnittliche Auszahlung) bietet.

Matrixdefiniertes Spiel A, was hat M Linien u N Spalten wird als Finite-Pair-Spiel der Dimension bezeichnet M* N;

Wo ich=
ist die Strategie des ersten Spielers mit m Strategien; J=ist die Strategie des zweiten Spielers mit n Strategien; ij ist die Auszahlung des ersten Spielers ich-te Strategie, wenn sie von der zweiten verwendet wird J-ten Strategie (oder, was dasselbe ist, Verlieren der zweiten J te Strategie, wenn sie zuerst verwendet wird ich Mai);

A =   ij ist die Auszahlungsmatrix des Spiels.

1.1 Spielen mit reinen Strategien

Niedrigerer Preis des Spiels (für den ersten Spieler)

 = max (Mindest ij). (1.2)

ich J

Oberer Spielpreis (für den zweiten Spieler):

= Mindest (max ij) . (1.3)

J ich

Wenn  =  , heißt das Spiel mit Sattelpunkt (1.4), oder ein Spiel mit reinen Strategien. Dabei v =  =  genannt das wertvolle Spiel ( v- der Preis des Spiels).

Beispiel. Gegeben sei eine Auszahlungsmatrix für ein 2-Personen-Spiel A. Bestimmen Sie die optimalen Strategien für jeden der Spieler und den Preis des Spiels:

(1.4)

max 10 9 12 6

ich

Mindest 6

ist die Strategie des ersten Spielers (Reihe).

Strategie des zweiten Spielers (Spalten).

- der Preis des Spiels.

Somit hat das Spiel einen Sattelpunkt. Strategie J = 4 ist die optimale Strategie für den zweiten Spieler ich=2 - für den ersten. Wir haben ein Spiel mit reinen Strategien.

1.2 Gemischte Strategiespiele

Wenn die Auszahlungsmatrix keinen Sattelpunkt hat, d.h.
, und keiner der Spielteilnehmer einen Plan als optimale Strategie auswählen kann, wechseln die Spieler zu "gemischten Strategien". In diesem Fall verwendet jeder der Spieler jede seiner Strategien mehrmals während des Spiels.

Der Vektor, von dem jede Komponente die relative Häufigkeit zeigt, mit der der Spieler die entsprechende reine Strategie verwendet, wird die gemischte Strategie des Spielers genannt.

X= (X 1 …X ich …X M) ist die gemischte Strategie des ersten Spielers.

Bei= (bei 1 ...bei J ...bei N) ist die gemischte Strategie des zweiten Spielers.

Xich , j J– relative Häufigkeiten (Wahrscheinlichkeiten) von Spielern, die ihre Strategien anwenden.

Bedingungen für die Verwendung gemischter Strategien

. (1.5)

Wenn X* = (X 1 * ….X ich * ... X M*) ist die vom ersten Spieler gewählte optimale Strategie; Y* = (bei 1 * …bei J * ... bei N*) ist die vom zweiten Spieler gewählte optimale Strategie, dann ist die Zahl der Preis des Spiels.

(1.6)

Zur Nummernordnung v war der Preis des Spiels, und X* Und bei* - Optimale Strategien, es ist notwendig und ausreichend, dass die Ungleichheiten

(1.7)

Wenn einer der Spieler eine optimal gemischte Strategie verwendet, entspricht seine Auszahlung dem Preis des Spiels v unabhängig von der Häufigkeit, mit der der zweite Spieler die Strategien anwenden wird, die in der optimalen enthalten sind, einschließlich reiner Strategien.

Reduktion spieltheoretischer Probleme auf Probleme der linearen Programmierung.

Beispiel. Finden Sie eine Lösung für das durch die Auszahlungsmatrix definierte Spiel A.

A = (1.8)

j 1 j 2 j 3

Lösung:

Lassen Sie uns ein duales Paar von Problemen der linearen Programmierung zusammenstellen.

Für den ersten Spieler

(1.9)

bei 1 +bei 2 +bei 3 = 1 (1.10)

Sich von der Variable befreien v(der Preis des Spiels) dividieren wir die linke und rechte Seite der Ausdrücke (1.9), (1.10) durch v. Akzeptiert haben bei J /v für eine neue Variable z ich, wir bekommen neues System Beschränkungen (1.11) und Zielfunktion (1.12)

(1.11)

. (1.12)

Analog erhalten wir das Spielmodell für den zweiten Spieler:

(1.13)

X 1 +X 2 +X 3 = 1 . (1.14)

Reduktionsmodell (1.13), (1.14) auf die Form ohne Variable v, wir bekommen

(1.15)

, (1.16)

Wo
.

Wenn wir die Verhaltensstrategie des ersten Spielers bestimmen müssen, d.h. die relative Häufigkeit der Anwendung seiner Strategien ( X 1 ….X ich …X M), verwenden wir das Modell des zweiten Spielers, weil diese Variablen sind in seinem Auszahlungsmodell (1.13), (1.14).

Wir führen (1.15), (1.16) auf die kanonische Form zurück

(1.17)

Spieltheorie - Aggregat mathematische Methoden Lösung von Konfliktsituationen (Interessenkonflikte). In der Spieltheorie ist ein Spiel mathematisches Modell einer Konfliktsituation. Ein Gegenstand von besonderem Interesse in der Spieltheorie ist die Untersuchung von Entscheidungsstrategien von Spielteilnehmern unter Unsicherheitsbedingungen. Unsicherheit ergibt sich aus der Tatsache, dass zwei oder mehr Seiten gegensätzliche Ziele verfolgen und die Ergebnisse jeder Aktion jeder der Parteien von den Bewegungen des Partners abhängen. Gleichzeitig strebt jede der Parteien danach, optimale Entscheidungen zu treffen, die die gesetzten Ziele weitestgehend realisieren.

Am konsequentesten wird die Spieltheorie in der Wirtschaft angewendet, wo Konfliktsituationen beispielsweise in Beziehungen zwischen einem Lieferanten und einem Verbraucher, einem Käufer und einem Verkäufer, einer Bank und einem Kunden entstehen. Die Anwendung der Spieltheorie findet sich auch in Politik, Soziologie, Biologie und Militärkunst.

Aus der Geschichte der Spieltheorie

Geschichte der Spieltheorie als eigenständige Disziplin beginnt 1944, als John von Neumann und Oscar Morgenstern das Buch „Theory of Games and Economic Behavior“ („Theory of Games and Economic Behavior“) veröffentlichten. Obwohl Beispiele der Spieltheorie schon früher begegnet sind: die babylonische Talmud-Abhandlung über die Aufteilung des Vermögens eines verstorbenen Mannes zwischen seinen Frauen, Kartenspiele im 18. Jahrhundert, die Entwicklung der Schachtheorie im frühen 20. Jahrhundert, der Beweis des Minimax-Theorems desselben John von Neumann im Jahr 1928, ohne den es keine Spieltheorie gäbe.

In den 1950er Jahren traten Melvin Drescher und Meryl Flood auf Rand Corporation Der erste, der das Gefangenendilemma experimentell anwandte, John Nash, entwickelte in seiner Arbeit über den Gleichgewichtszustand in Zwei-Personen-Spielen das Konzept des Nash-Gleichgewichts.

Reinhard Salten veröffentlichte 1965 das Buch „Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit“, mit dem die Anwendung der Spieltheorie in der Volkswirtschaftslehre einen neuen Antrieb erhielt. Ein Schritt vorwärts in der Evolution der Spieltheorie ist mit der Arbeit von John Maynard Smith "Evolutionary Stable Strategy" ("Evolutionary Stable Strategy", 1974) verbunden. Das Gefangenendilemma wurde in Robert Axelrods Buch The Evolution of Cooperation, das 1984 veröffentlicht wurde, populär gemacht. 1994 wurden John Nash, John Harsanyi und Reinhard Salten mit dem Nobelpreis für Spieltheorie ausgezeichnet.

Spieltheorie in Leben und Wirtschaft

Gehen wir näher auf das Wesen einer Konfliktsituation (Interessenkonflikt) in dem Sinne ein, wie sie in der Spieltheorie zur weiteren Modellierung verschiedener Lebens- und Geschäftssituationen verstanden wird. Lassen Sie das Individuum in einer Position sein, die zu einem von mehreren möglichen Ergebnissen führt, und das Individuum hat einige persönliche Präferenzen in Bezug auf diese Ergebnisse. Aber obwohl er die variablen Faktoren, die das Ergebnis bestimmen, bis zu einem gewissen Grad kontrollieren kann, hat er keine vollständige Kontrolle über sie. Manchmal liegt die Kontrolle in den Händen einiger weniger Personen, die wie er eine gewisse Vorliebe für mögliche Ergebnisse haben, aber in Allgemeiner Fall die Interessen dieser Personen stimmen nicht überein. In anderen Fällen kann das Endergebnis sowohl von Unfällen (in den Rechtswissenschaften manchmal als Naturkatastrophen bezeichnet) als auch von anderen Personen abhängen. Die Spieltheorie systematisiert Beobachtungen solcher Situationen und formuliert sie allgemeine Grundsätze um in solchen Situationen angemessene Maßnahmen zu ergreifen.

In gewisser Hinsicht ist der Name „Spieltheorie“ unglücklich, da er suggeriert, dass sich die Spieltheorie nur mit ihr befasst sozialen Wert Zusammenstöße, die in Gesellschaftsspielen auftreten, aber diese Theorie hat dennoch eine viel umfassendere Bedeutung.

Die folgende wirtschaftliche Situation kann eine Vorstellung von der Anwendung der Spieltheorie geben. Angenommen, es gibt mehrere Unternehmer, von denen jeder versucht, den Gewinn zu maximieren, während er nur begrenzte Macht über die Variablen hat, die diesen Gewinn bestimmen. Der Unternehmer hat keine Kontrolle über Variablen, die von einem anderen Unternehmer kontrolliert werden, die aber das Einkommen des ersten stark beeinflussen können. Die Interpretation dieser Situation als Spiel kann zu folgendem Einwand Anlass geben. Das Spielmodell geht davon aus, dass jeder Unternehmer eine Wahl aus dem Bereich der möglichen Entscheidungen trifft und die Gewinne durch diese einzelnen Entscheidungen bestimmt werden. Dass dies in der Realität nahezu unmöglich ist, liegt auf der Hand, da in diesem Fall in der Industrie keine aufwendigen Verwaltungsapparate benötigt würden. Es ist nur so, dass es eine Reihe von Entscheidungen und Modifikationen dieser Entscheidungen gibt, die von den Entscheidungen anderer Teilnehmer abhängen. Wirtschaftssystem(Spieler). Aber im Prinzip kann man sich vorstellen, dass jeder Administrator alle möglichen Eventualitäten antizipiert und detailliert beschreibt, was im Einzelfall zu tun ist, anstatt jede Aufgabe so zu lösen, wie sie entsteht.

Ein militärischer Konflikt ist per Definition ein Interessenkonflikt, bei dem keine Seite die volle Kontrolle über die Variablen hat, die das Ergebnis bestimmen, das durch eine Reihe von Schlachten entschieden wird. Sie können das Ergebnis einfach als Sieg oder Niederlage betrachten und ihnen die Zahlenwerte 1 und 0 zuweisen.

Eine der einfachsten Konfliktsituationen, die in der Spieltheorie niedergeschrieben und gelöst werden können, ist ein Duell, bei dem es sich um einen Konflikt zwischen zwei Spielern 1 und 2 handelt P Und Q Schüsse. Für jeden Spieler gibt es eine Funktion, die die Wahrscheinlichkeit angibt, dass der Spieler geschossen hat ich damals T wird einen Treffer geben, der sich als tödlich erweisen wird.

Im Ergebnis kommt die Spieltheorie zu folgender Formulierung einer bestimmten Klasse von Interessenkonflikten: Es gibt N Spieler, und jeder Spieler muss eine Möglichkeit aus einem bestimmten Satz von 100 auswählen, und wenn er eine Wahl trifft, hat der Spieler keine Informationen über die Entscheidungen anderer Spieler. Der Auswahlbereich des Spielers kann Elemente wie „Pik-Ass bewegen“, „Panzer statt Autos produzieren“ oder „in“ enthalten Allgemeinsinn, eine Strategie, die alle Maßnahmen definiert, die unter allen möglichen Umständen zu ergreifen sind. Jeder Spieler steht vor der Aufgabe: Welche Wahl soll er treffen, damit ihm sein privater Einfluss auf das Ergebnis den größtmöglichen Gewinn bringt?

Mathematisches Modell in der Spieltheorie und Problemformalisierung

Wie wir bereits festgestellt haben, Spiel ist mathematisches Modell Konfliktsituation und benötigt folgende Komponenten:

interessierte Parteien;
mögliche Aktionen auf jeder Seite;
die Interessen der Parteien.

Die am Spiel Interessierten werden Spieler genannt. , jeder von ihnen kann mindestens zwei Aktionen ausführen (wenn der Spieler nur eine Aktion hat, nimmt er eigentlich nicht am Spiel teil, da im Voraus bekannt ist, was er tun wird). Das Ergebnis des Spiels wird als Gewinn bezeichnet. .

Eine echte Konfliktsituation liegt nicht immer vor, aber das Spiel (im Sinne der Spieltheorie) geht – immer – weiter bestimmte Regeln , die genau definieren:

Spieleroptionen;
die Menge an Informationen, die jeder Spieler über das Verhalten des Partners hat;
die Auszahlung, zu der jede Reihe von Aktionen führt.

Beispiele für formalisierte Spiele sind Fußball, Kartenspiel, Schach.

Aber in der Ökonomie entsteht ein Modell des Spielerverhaltens, wenn zum Beispiel mehrere Firmen versuchen, einen vorteilhafteren Platz auf dem Markt einzunehmen, mehrere Einzelpersonen versuchen, etwas Gutes (Ressourcen, Finanzen) untereinander aufzuteilen, damit alle so viel wie möglich bekommen . Die als Spiel modellierbaren Akteure in Konfliktsituationen in der Wirtschaft sind Unternehmen, Banken, Einzelpersonen und andere Wirtschaftssubjekte. Unter Kriegsbedingungen wiederum wird das Spielmodell beispielsweise bei der Auswahl von mehr verwendet beste Waffe(aus dem verfügbaren oder potenziell möglichen) um den Feind zu besiegen oder vor Angriffen zu schützen.

Das Spiel ist geprägt von der Ungewissheit des Ergebnisses . Die Ursachen der Unsicherheit lassen sich in folgende Gruppen einteilen:

kombinatorisch (wie beim Schach);
der Einfluss zufälliger Faktoren (wie im Spiel "Kopf oder Zahl", Würfel, Kartenspiele);
strategisch (der Spieler weiß nicht, was der Gegner tun wird).

Spielerstrategie ist eine Reihe von Regeln, die seine Aktionen bei jedem Zug abhängig von der Situation bestimmen.

Das Ziel der Spieltheorie ist es, die optimale Strategie für jeden Spieler zu bestimmen. Eine solche Strategie zu bestimmen heißt, das Spiel zu lösen. Strategie Optimalität ist erreicht, wenn einer der Spieler die maximale Auszahlung erzielen muss, während der zweite an seiner Strategie festhält. Und der zweite Spieler sollte einen minimalen Verlust haben, wenn der erste bei seiner Strategie bleibt.

Spielklassifizierung

Klassifizierung nach Anzahl der Spieler (Spiel von zwei oder mehr Personen). Zwei-Personen-Spiele sind zentral für die gesamte Spieltheorie. Das Grundkonzept der Spieltheorie für Zwei-Personen-Spiele ist eine Verallgemeinerung der sehr wesentlichen Idee des Gleichgewichts, die natürlicherweise in Zwei-Personen-Spielen vorkommt. Was die Spiele angeht N Personen, dann widmet sich ein Teil der Spieltheorie Spielen, bei denen die Zusammenarbeit zwischen Spielern verboten ist. In einem anderen Teil der Spieltheorie N Personen wird davon ausgegangen, dass die Spieler zum gegenseitigen Nutzen zusammenarbeiten können (siehe weiter unten in diesem Abschnitt über nicht kooperative und kooperative Spiele).
Klassifizierung nach Anzahl der Spieler und deren Strategien (die Anzahl der Strategien beträgt mindestens zwei, kann unendlich sein).
Klassifizierung nach Informationsmenge zu vergangenen Zügen: Partien mit vollständigen Informationen und unvollständigen Informationen. Es gibt Spieler 1 - den Käufer und Spieler 2 - den Verkäufer. Wenn Spieler 1 keine vollständigen Informationen über die Aktionen von Spieler 2 hat, dann darf Spieler 1 nicht zwischen zwei Alternativen unterscheiden, zwischen denen er sich entscheiden muss. Zum Beispiel zwischen zwei Arten eines bestimmten Produkts zu wählen und nicht zu wissen, dass das Produkt einige Eigenschaften aufweist A schlimmer als Ware B, sieht Spieler 1 den Unterschied zwischen den Alternativen möglicherweise nicht.
Einstufung nach den Grundsätzen der Gewinnteilung : einerseits kooperativ, Koalition und andererseits nicht kooperativ, nicht kooperativ. IN nicht kooperatives Spiel , oder andernfalls - nicht kooperatives Spiel , wählen die Spieler gleichzeitig Strategien, ohne zu wissen, welche Strategie der zweite Spieler wählen wird. Eine Kommunikation zwischen den Spielern ist nicht möglich. IN kooperatives Spiel , oder andernfalls - Koalitionsspiel können Spieler Koalitionen bilden und gemeinsam handeln, um ihre Gewinne zu erhöhen.
Endliches Nullsummenspiel für zwei Personen oder antagonistisches Spiel ist Strategiespiel mit vollständigen Informationen, an denen Parteien mit gegensätzlichen Interessen beteiligt sind. Antagonistische Spiele sind Matrixspiele .

Ein klassisches Beispiel aus der Spieltheorie ist das Gefangenendilemma.

Die beiden Verdächtigen werden in Gewahrsam genommen und voneinander isoliert. Der Staatsanwalt ist überzeugt, dass sie ein schweres Verbrechen begangen haben, hat aber nicht genügend Beweise, um sie vor Gericht anzuklagen. Er sagt jedem der Gefangenen, dass er zwei Alternativen hat: das Verbrechen gestehen, von dem die Polizei glaubt, dass er es begangen hat, oder nicht gestehen. Wenn beide nicht gestehen, wird der Bezirksstaatsanwalt sie wegen eines geringfügigen Verbrechens wie geringfügigen Diebstahls oder illegalen Waffenbesitzes anklagen, und sie werden beide eine kleine Strafe erhalten. Wenn sie beide gestehen, werden sie strafrechtlich verfolgt, aber es wird nicht die härteste Strafe erfordern. Gesteht der eine und der andere nicht, dann bekommt der Geständige eine abgewandelte Strafe für die Auslieferung eines Komplizen, während der Hartnäckige "in vollen Zügen" kassiert.

Wenn diese strategische Aufgabe im Sinne des Fazits formuliert wird, dann läuft es auf Folgendes hinaus:

Wenn also beide Gefangenen kein Geständnis ablegen, erhalten sie jeweils 1 Jahr. Wenn beide gestehen, erhält jeder 8 Jahre. Und wenn einer gesteht, der andere nicht, dann kommt derjenige, der gesteht, mit drei Monaten Gefängnis davon, und derjenige, der nicht gesteht, bekommt 10 Jahre. Die obige Matrix gibt das Gefangenendilemma richtig wieder: Jeder steht vor der Frage Geständnis oder Nichtgeständnis. Das Spiel, das der Bezirksstaatsanwalt den Gefangenen anbietet, ist nicht kooperatives Spiel oder andernfalls - Nicht-Koalitionsspiel . Wenn beide Gefangene kooperieren könnten (d.h. Das Spiel wäre kooperativ oder andernfalls Koalitionsspiel ), dann wollten beide nicht gestehen und bekamen jeweils ein Jahr Gefängnis.

Beispiele für den Einsatz mathematischer Mittel der Spieltheorie

Wir wenden uns nun der Betrachtung von Lösungen zu Beispielen gängiger Klassen von Spielen zu, für die es spieltheoretische Untersuchungs- und Lösungsmethoden gibt.

Ein Beispiel für die Formalisierung eines nicht kooperativen (nicht kooperativen) Spiels von zwei Personen

Im vorherigen Absatz haben wir bereits ein Beispiel für ein nicht kooperatives (nicht kooperatives) Spiel (Gefangenendilemma) betrachtet. Lassen Sie uns unsere Fähigkeiten festigen. Dazu eignet sich auch ein klassischer Plot, der von Arthur Conan Doyles Die Abenteuer des Sherlock Holmes inspiriert ist. Man kann natürlich einwenden: Das Beispiel stammt nicht aus dem Leben, sondern aus der Literatur, aber Conan Doyle hat sich nicht als Science-Fiction-Autor etabliert! Klassisch auch deshalb, weil die Aufgabe, wie wir bereits festgestellt haben, von Oscar Morgenstern erledigt wurde – einem der Begründer der Spieltheorie.

Beispiel 1 Es wird ein gekürzter Auszug aus einem der Abenteuer von Sherlock Holmes gegeben. Erstellen Sie nach den bekannten Konzepten der Spieltheorie ein Modell einer Konfliktsituation und schreiben Sie das Spiel formal auf.

Sherlock Holmes beabsichtigt, von London nach Dover zu gehen, mit dem weiteren Ziel, auf den (europäischen) Kontinent zu gelangen, um Professor Moriarty zu entkommen, der ihn verfolgt. Als er in den Zug einstieg, sah er Professor Moriarty auf dem Bahnsteig. Sherlock Holmes gibt zu, dass Moriarty einen Sonderzug auswählen und überholen kann. Sherlock Holmes hat zwei Alternativen: Weiter nach Dover oder an der Station Canterbury aussteigen, die die einzige Zwischenstation auf seiner Route ist. Wir gehen davon aus, dass sein Gegner intelligent genug ist, Holmes Optionen zu bestimmen, also hat er die gleichen zwei Alternativen. Beide Kontrahenten müssen einen Bahnhof auswählen, an dem sie aus dem Zug aussteigen, ohne zu wissen, welche Entscheidung jeder von ihnen treffen wird. Wenn beide aufgrund der Entscheidung auf derselben Station landen, können wir definitiv davon ausgehen, dass Sherlock Holmes von Professor Moriarty getötet wird. Wenn Sherlock Holmes sicher nach Dover kommt, wird er gerettet.

Lösung. Die Helden von Conan Doyle können als Teilnehmer des Spiels betrachtet werden, dh als Spieler. Zur Verfügung jedes Spielers ich (ich=1,2) zwei reine Strategien:

steigen Sie in Dover aus (Strategie Si1 ( ich=1,2) );
an einer Zwischenstation aussteigen (Strategie Si2 ( ich=1,2) )

Je nachdem, welche der beiden Strategien jeder der beiden Spieler wählt, entsteht eine spezielle Kombination von Strategien als Paar S = (S1 , S 2 ) .

Jede Kombination kann mit einem Ereignis in Verbindung gebracht werden – dem Ergebnis eines Versuchs, Sherlock Holmes von Professor Moriarty zu töten. Wir erstellen eine Matrix dieses Spiels mit möglichen Ereignissen.

Unter jedem der Ereignisse ist ein Index angegeben, der die Übernahme von Professor Moriarty bedeutet und abhängig von der Rettung von Holmes berechnet wird. Beide Helden wählen gleichzeitig eine Strategie, ohne zu wissen, was der Gegner wählen wird. Das Spiel ist also nicht kooperativ, weil die Spieler erstens in unterschiedlichen Zügen sitzen und zweitens gegensätzliche Interessen haben.

Ein Beispiel für Formalisierung und Lösung eines kooperativen (Koalitions-)Spiels N Personen

An dieser Stelle wird dem praktischen Teil, also dem Ablauf der Lösung eines Beispielproblems, ein theoretischer Teil vorangestellt, in dem wir uns mit den Konzepten der Spieltheorie zur Lösung kooperativer (nicht kooperativer) Spiele vertraut machen. Für diese Aufgabe schlägt die Spieltheorie vor:

die charakteristische Funktion (vereinfacht gesagt spiegelt sie den Wert der Vorteile wider, die der Zusammenschluss der Spieler zu einer Koalition mit sich bringt);
das Konzept der Additivität (Eigenschaft von Mengen, die darin besteht, dass der Wert der Menge, die dem gesamten Objekt entspricht, gleich der Summe der Werte der Mengen ist, die seinen Teilen entsprechen, in einer bestimmten Klasse der Aufteilung des Objekts in Teile) und Superadditivität (der Wert der Größe, die dem gesamten Objekt entspricht, ist größer als die Summe der Werte der Größen, die seinen Teilen entsprechen) der charakteristischen Funktion.

Die Superadditivität der charakteristischen Funktion weist darauf hin, dass Koalitionen für die Spieler vorteilhaft sind, da in diesem Fall die Auszahlung der Koalition mit der Anzahl der Spieler steigt.

Um das Spiel zu formalisieren, müssen wir eine formale Notation für die obigen Konzepte einführen.

Für Spiel N bezeichne die Menge aller seiner Spieler als N= (1,2,...,n) Jede nicht leere Teilmenge der Menge N bezeichnet als T(einschließlich selbst N und alle Teilmengen, die aus einem Element bestehen). Es gibt eine Aktivität auf der Website Mengen und Operationen auf Mengen, die sich in einem neuen Fenster öffnet, wenn Sie auf den Link klicken.

Die charakteristische Funktion wird als bezeichnet v und sein Definitionsbereich besteht aus möglichen Teilmengen der Menge N. v(T) - der Wert der charakteristischen Funktion für eine bestimmte Teilmenge, zum Beispiel das Einkommen einer Koalition, die möglicherweise aus einem Spieler besteht. Dies ist wichtig, da die Spieltheorie für die Werte der charakteristischen Funktion aller nicht überlappenden Koalitionen das Vorhandensein von Superadditivität überprüfen muss.

Für zwei nicht leere Koalitionen von Teilmengen T1 Und T2 die Additivität der charakteristischen Funktion eines kooperativen (Koalitions-)Spiels wird wie folgt geschrieben:

Und Superadditivität ist wie folgt:

Beispiel 2 Drei Schüler einer Musikschule verdienen sich in verschiedenen Clubs nebenbei Geld, ihre Einnahmen erhalten sie von Clubbesuchern. Stellen Sie fest, ob es für sie rentabel ist, sich zusammenzuschließen (wenn ja, unter welchen Bedingungen), indem sie die Konzepte der Spieltheorie verwenden, um kooperative Spiele zu lösen N Personen, mit folgenden Anfangsdaten.

Im Durchschnitt betrug ihr Umsatz pro Abend:

der Geiger hat 600 Einheiten;
der Gitarrist hat 700 Einheiten;
der Sänger hat 900 Einheiten.

Um die Einnahmen zu steigern, gründeten die Studenten mehrere Monate lang verschiedene Gruppen. Die Ergebnisse zeigten, dass sie durch die Zusammenarbeit ihre Abendeinnahmen wie folgt steigern konnten:

Geiger + Gitarrist verdient 1500 Einheiten;
Geiger + Sänger verdient 1800 Einheiten;
Gitarrist + Sänger verdient 1900 Einheiten;
Geiger + Gitarrist + Sänger verdienten 3000 Einheiten.

Lösung. In diesem Beispiel die Anzahl der Teilnehmer am Spiel N= 3 , also besteht der Definitionsbereich der charakteristischen Funktion des Spiels aus 2³ = 8 möglichen Teilmengen der Menge aller Spieler. Lassen Sie uns alle möglichen Koalitionen auflisten T:

Koalitionen eines Elements, die jeweils aus einem Spieler bestehen - einem Musiker: T{1} , T{2} , T{3} ;
Koalitionen aus zwei Elementen: T{1,2} , T{1,3} , T{2,3} ;
Koalition aus drei Elemente: T{1,2,3} .

Wir weisen jedem Spieler eine Seriennummer zu:

Geiger - 1. Spieler;
Gitarrist - 2. Spieler;
der Sänger ist der 3. Spieler.

Anhand der Problemdaten bestimmen wir die charakteristische Funktion des Spiels v:

v(T(1)) = 600 ; v(T(2)) = 700 ; v(T(3)) = 900 ; diese Werte der charakteristischen Funktion werden auf der Grundlage der Auszahlungen des ersten, zweiten und dritten Spielers bestimmt, wenn sie nicht in Koalitionen vereint sind;

v(T(1,2)) = 1500 ; v(T(1,3)) = 1800 ; v(T(2,3)) = 1900 ; diese Werte der charakteristischen Funktion werden durch die Einnahmen jedes in Koalitionen vereinten Spielerpaares bestimmt;

v(T(1,2,3)) = 3000 ; Dieser Wert der charakteristischen Funktion wird durch den durchschnittlichen Umsatz in dem Fall bestimmt, in dem die Spieler in Drillingen vereint waren.

Wir haben also alle möglichen Koalitionen von Spielern aufgelistet, acht davon gibt es, wie es sein sollte, da der Definitionsbereich der charakteristischen Funktion des Spiels aus genau acht möglichen Teilmengen der Menge aller Spieler besteht. Das fordert die Spieltheorie, da wir für die Werte der charakteristischen Funktion aller nicht überlappenden Koalitionen das Vorhandensein von Superadditivität prüfen müssen.

Wie werden in diesem Beispiel die Bedingungen der Superadditivität erfüllt? Lassen Sie uns definieren, wie die Spieler nicht überlappende Koalitionen bilden T1 Und T2 . Wenn einige der Spieler in einer Koalition sind T1 , dann sind alle anderen Spieler in der Koalition T2 und per definitionem wird diese Koalition als die Differenz zwischen der Gesamtmenge der Spieler und der Menge gebildet T1 . Dann wenn T1 - eine Koalition von einem Spieler, dann in einer Koalition T2 es wird den zweiten und dritten Spieler geben, falls in der Koalition T1 wird der erste und dritte Spieler sein, dann die Koalition T2 besteht nur aus dem zweiten Spieler und so weiter.