heim › Getriebe (Getriebe) › Dualität in der linearen Programmierung. Arten von Gleichgewichten: Nash-Gleichgewicht, Stekelberg, Pareto-optimales Gleichgewicht, Gleichgewicht dominanter Strategien. Was ist der optimale Mechanismus, um eine Lösung für das Gleichgewicht zu finden?

Dualität in der linearen Programmierung. Arten von Gleichgewichten: Nash-Gleichgewicht, Stekelberg, Pareto-optimales Gleichgewicht, Gleichgewicht dominanter Strategien. Was ist der optimale Mechanismus, um eine Lösung für das Gleichgewicht zu finden?

Grundlegende Definitionen der Dualitätstheorie.

Jedes lineare Programmierproblem kann mit einem anderen linearen Programmierproblem verknüpft werden. Wenn eines davon gelöst ist, wird das andere Problem automatisch gelöst. Solche Aufgaben werden als gegenseitig dual bezeichnet. Lassen Sie uns zeigen, wie wir für ein gegebenes Problem (wir nennen es das ursprüngliche Problem) sein Duales konstruieren können.

Betrachten Sie das Problem der geplanten Ausgabe.

F=3 X 1 + 5X 2 + 4X 3 + 5X 4 → max.
5x 1 +0,4x 2 +2x 3 +0,5x 4 ≤400
5x2 +x3 +x4 ≤300
x 1 + x 3 + x 4 ≤100
x 1 ≥0, x 2 ≥0, x 3 ≥0, x 4 ≥0

Allgemeine Regeln zum Kompilieren eines dualen Problems:

Gerade	Dual
Zielfunktion (max)	Rechte Seite der Einschränkungen
Rechte Seite der Einschränkungen	Zielfunktion (min)
A – Einschränkungsmatrix	Eine T – Einschränkungsmatrix
i-te Einschränkung: ≤ 0, (≥ 0)	Variable y i ≥ 0, (≤ 0)
i-te Einschränkung: = 0	Variable y i ≠ 0
Variable x j ≥ 0 (≤ 0)
Variable x j ≠ 0	j-te Einschränkung: = 0

max → min

Gerade	Dual
Zielfunktion (min)	Rechte Seite der Einschränkungen
Rechte Seite der Einschränkungen	Zielfunktion (max)
A – Einschränkungsmatrix	Eine T – Einschränkungsmatrix
i-te Einschränkung: ≥ 0, (≤ 0)	Variable y i ≥ 0, (≤ 0)
i-te Einschränkung: = 0	Variable y i ≠ 0
Variable x j ≥ 0 (≤ 0)	j-te Einschränkung: ≤ 0 (≥ 0)
Variable x j ≠ 0	j-te Einschränkung: = 0

Konstruieren wir sein duales Problem gemäß den folgenden Regeln.

Die Anzahl der Variablen im dualen Problem ist gleich der Anzahl der Ungleichungen im ursprünglichen Problem.
Die Koeffizientenmatrix des dualen Problems wird auf die Koeffizientenmatrix des ursprünglichen Problems übertragen.
Die Spalte der freien Terme des ursprünglichen Problems ist eine Reihe von Koeffizienten für die duale Zielfunktion. Die Zielfunktion ist bei einem Problem maximiert, bei dem anderen minimiert.
Die Bedingungen für die Nichtnegativität der Variablen des ursprünglichen Problems entsprechen den in die andere Richtung gerichteten Ungleichungen-Einschränkungen des dualen Problems. Und umgekehrt entsprechen Ungleichungen-Einschränkungen im Original den Bedingungen der Nichtnegativität im Dualen.

Beachten Sie, dass die Zeilen der Matrix von Aufgabe I die Spalten der Matrix von Aufgabe II sind. Daher sind die Koeffizienten für die Variablen y i in Problem II jeweils die Koeffizienten der i-ten Ungleichung in Problem I.
Das resultierende Modell ist das ökonomische und mathematische Modell des Problems, das dual zum direkten Problem ist.

Die durch Pfeile verbundenen Ungleichungen werden sein Konjugat nennen.
Sinnvolle Formulierung des dualen Problems: Finden Sie einen solchen Satz von Preisen (Schätzungen) für Ressourcen Y = (y 1 , y 2 ..., y m), bei dem die Gesamtkosten der Ressourcen minimal sind, vorausgesetzt, dass die Ressourcenkosten bei der Produktion jedes Typs betragen des Produkts wird nicht geringer sein als der Gewinn (Erlös aus dem Verkauf dieser Produkte).
Ressourcenpreise y 1 , y 2 ..., y m in der Wirtschaftsliteratur erhalten verschiedene Titel: Buchhaltung, implizit, Schatten. Die Bedeutung dieser Namen liegt darin, dass es sich um bedingte, „falsche“ Preise handelt. Im Gegensatz zu den „externen“ Preisen von 1 , von 2 ..., von n für Produkte, die in der Regel vor Produktionsbeginn bekannt sind, sind die Preise der Ressourcen y 1 , y 2 ..., y m intern Da sie nicht von außen festgelegt werden, sondern direkt als Ergebnis der Lösung des Problems ermittelt werden, werden sie häufig als Ressourcenschätzungen bezeichnet.
Der Zusammenhang zwischen dem direkten und dem dualen Problem besteht insbesondere darin, dass die Lösung des einen direkt aus der Lösung des anderen gewonnen werden kann.

Dualitätssätze

Dualität ist ein grundlegendes Konzept in der linearen Programmiertheorie. Die Hauptergebnisse der Dualitätstheorie sind in zwei Theoremen enthalten, die Dualitätstheoreme genannt werden.

Erster Dualitätssatz.

Wenn eines der beiden dualen Probleme I und II lösbar ist, dann ist das andere lösbar und die Werte der Zielfunktionen auf den optimalen Plänen sind gleich. F(X*) = G(j*), wobei x *, y * - optimale Lösungen der Probleme I und II

Zweiter Dualitätssatz.

Die Pläne x* und y* sind in den Problemen I und II genau dann optimal, wenn, wenn sie in das System der Nebenbedingungen der Probleme I bzw. II eingesetzt werden, mindestens eines eines beliebigen Paares konjugierter Ungleichungen eine Gleichheit wird.
Das fundamentaler Dualitätssatz. Mit anderen Worten: Wenn x * und y * zulässige Lösungen für das Primär- und Dualproblem sind und wenn c T x*=b T y*, dann sind x * und y * optimale Lösungen für ein Paar dualer Probleme.

Dritter Dualitätssatz. Die Werte der Variablen y i in der optimalen Lösung des dualen Problems sind Schätzungen des Einflusses freier Mitglieder b i des Zwangsbedingungssystems – Ungleichungen des direkten Problems auf den Wert der Zielfunktion dieses Problems:
Δf(x) = b i y i

Indem wir das LLP mit der Simplex-Methode lösen, lösen wir gleichzeitig das duale LLP. Die Werte der Variablen des dualen Problems y i im optimalen Plan werden als objektiv bestimmte oder duale Schätzungen bezeichnet. Bei angewandten Problemen werden duale Schätzungen y i oft als versteckte Schätzungen, Schattenpreise oder Grenzressourcenschätzungen bezeichnet.

Eigenschaft gegenseitig dualer Probleme

Bei der einen Aufgabe wird das Maximum einer linearen Funktion gesucht, bei der anderen das Minimum.
Die Koeffizienten für Variablen in einer linearen Funktion eines Problems sind freie Mitglieder des Randbedingungssystems eines anderen.
Jedes der Probleme ist in der Standardform gegeben, und beim Maximierungsproblem sind alle Ungleichungen der Form ≤ und beim Minimierungsproblem alle Ungleichungen der Form ≥ .
Die Koeffizientenmatrizen für die Variablen in den Zwangssystemen beider Probleme werden zueinander transponiert:
Die Anzahl der Ungleichungen im Zwangssystem eines Problems ist dieselbe wie die Anzahl der Variablen im anderen Problem.
In beiden Problemen liegen Bedingungen für die Nichtnegativität von Variablen vor.

Gleichgewichtssatz

Aufgabe 2
Verfassen Sie ein duales Problem für Problem 1. Finden Sie es Lösung nach dem Gleichgewichtssatz.
3x1 +x2 ≥12
x1 +2x2 ≥14
4x1 +11x2 ≥68

Gleichgewichtssatz . Seien X*=(x 1 *,...,x n *) und Y*=(y 1 *,...,y n *) zulässige Entwürfe eines Paares dualer Probleme in symmetrischer Form. Diese Pläne sind genau dann optimal, wenn die folgenden ergänzenden Slackness-Bedingungen erfüllt sind:

Satz 4 ermöglicht es uns, die optimale Lösung für eines von zwei dualen Problemen zu bestimmen, indem wir das andere lösen. Wenn sich die Einschränkung eines Problems beim Ersetzen durch die optimale Lösung in eine strikte Ungleichung verwandelt, dann ist die entsprechende duale Variable in der optimalen Lösung des dualen Problems gleich 0. Wenn eine Variable im optimalen Plan eines Problems positiv ist, dann Die entsprechende Nebenbedingung des dualen Problems ist eine Gleichung.
Lassen Sie uns eine ökonomische Interpretation der Bedingungen der komplementären Flaute geben. Wenn in der optimalen Lösung ein Rohstoff einen anderen Wert als 0 hat, ist er vollständig aufgebraucht (die Ressource ist knapp). Wenn der Rohstoff nicht vollständig verbraucht wird (im Übermaß vorhanden ist), ist seine Bewertung gleich 0. Somit erhalten wir, dass Doppelbewertungen ein Maß für die Rohstoffknappheit sind. Die Schätzung zeigt, um wie viel der Wert der Zielfunktion bei einer Erhöhung des Lagerbestands des entsprechenden Rohstoffs um 1 Einheit zunimmt. Wenn ein bestimmter Produkttyp im Produktionsplan enthalten ist, stimmen die Produktionskosten mit den Kosten des hergestellten Produkts überein. Wenn die Herstellungskosten eines Produkts höher sind als die Kosten des Produkts, wird das Produkt nicht hergestellt.
Wenn eines der Paare dualer Probleme zwei Variablen enthält, kann es grafisch gelöst werden und dann mithilfe der Sätze 3 und 4 eine Lösung für das duale Problem gefunden werden. In diesem Fall können drei Fälle auftreten: Für beide Probleme gibt es nur zulässige Lösungen Es gibt ein Problem mit zulässigen Lösungen, beide Probleme haben keine zulässigen Lösungen.

Beispiel 2
Stellen Sie ein duales Problem zusammen und finden Sie seine Lösung mithilfe des Gleichgewichtssatzes
x 2 -2x 3 +2x 4 -2x 5 ≤4
-2x 1 -2x 2 +2x 3 +2x 4 +x 5 ≥2
x i ≥0, i=1,5
Z=10x 1 -9x 2 -19x 3 -13x 4 -11x 5 → max, wenn die Lösung des ursprünglichen Problems bekannt ist: Zmax=(3;4;0;0;0).
Konstruieren wir ein duales Problem. Wir stimmen die Zeichen der Ungleichungen mit dem Ziel des ursprünglichen Problems überein.

Z=10x 1 -9x 2 -19x 3 -13x 4 -11x 5 → max
Doppelaufgabe:

W=4J 1 -2J 2 → min
Finden wir die optimale Lösung des dualen Problems mithilfe des Gleichgewichtssatzes. Schreiben wir die Bedingungen der komplementären Slackness auf.
y 1 (4-(x 2 -2x 3 +2x 4 -2x 5))=0
y 2 (-2-(2x 1 -2x 2 -2x 3 -2x 4 -x 5))=0
x 1 (-2y 2 -10)=0
x 2 (y 1 -2y 2 +9)=0
x 3 (-2y 1 -2y 2 +19)=0
x 4 (2y 1 -2y 2 +13)=0
x 5 (-2y 1 -y 2 +11)=0
Ersetzen wir die optimale Lösung des ursprünglichen Problems in das kompilierte System: x 1 =3, x 2 =4, x 3 =0, x 4 =0, x 5 =0.
y 1 (4-(4-2 0+2 0-2 0))=0
y 2 (-2-(2 3-2 4-2 0-2 0-0))=0 W(y 1 , y 2 , y 3)=12y 1 +31y 2 +18y 3 → max . Nach Satz 3 Zmax=Wmin=100000.
Schließlich ist Wmin=W(0; 4000/7; 32000/21) = 100000

In einem antagonistischen Spiel ist es selbstverständlich, das optimale Ergebnis als eines zu betrachten, bei dem es für keinen der Spieler unrentabel ist, davon abzuweichen. Ein solches Ergebnis (x*,y*) wird als Gleichgewichtssituation bezeichnet, und das Optimalitätsprinzip, das auf der Suche nach einer Gleichgewichtssituation basiert, wird als Gleichgewichtsprinzip bezeichnet.

Definition. In einem Matrixspiel mit einer Dimensionsmatrix ist das Ergebnis Gleichgewichtssituation oder ein Sattelpunkt, wenn

An einem Sattelpunkt ist ein Matrixelement sowohl das Minimum in seiner Zeile als auch das Maximum in seiner Spalte. Im Spiel aus dem Beispiel, Element 2 ein 33 ist ein Sattelpunkt. Die optimalen Strategien in diesem Spiel sind die dritten Strategien für beide Spieler. Wenn der erste Spieler von der dritten Strategie abweicht, beginnt er weniger als zu gewinnen ein 33. Weicht der zweite Spieler von der dritten Strategie ab, beginnt er mehr als zu verlieren ein 33. Daher gibt es für beide Spieler nichts Besseres, als konsequent an der dritten Strategie festzuhalten.

Das Prinzip des optimalen Verhaltens: Wenn es in einem Matrixspiel einen Sattelpunkt gibt, dann ist die optimale Strategie die Wahl, die dem Sattelpunkt entspricht. Was passiert, wenn es mehr als einen Sattelpunkt im Spiel gibt?

Satz. Lassen zwei beliebige Sattelpunkte in einem Matrixspiel. Dann:

Nachweisen. Aus der Definition der Gleichgewichtssituation ergibt sich:

Ersetzen wir in die linke Seite der Ungleichung (2.8) und in die rechte Seite - , in die linke Seite der Ungleichung (2.9) - , in die rechte Seite - . Dann erhalten wir:

Woher kommt die Gleichheit:

Aus dem Satz folgt, dass die Auszahlungsfunktion in allen Gleichgewichtssituationen den gleichen Wert annimmt. Deshalb wird die Nummer angerufen auf Kosten des Spiels. Und die Strategien, die einem der Sattelpunkte entsprechen, werden aufgerufen optimale Strategien Spieler 1 bzw. 2. Aufgrund von (2.7) sind alle optimalen Strategien des Spielers austauschbar.

Die Optimalität des Spielerverhaltens ändert sich nicht, wenn die Strategien im Spiel gleich bleiben und die Auszahlungsfunktion mit einer positiven Konstante multipliziert (oder eine konstante Zahl dazu addiert) wird.

Satz. Damit im Matrixspiel ein Sattelpunkt (i*,j*) existiert, ist es notwendig und ausreichend, dass das Maximin gleich dem Minimax ist:

(2.10)

Nachweisen. Notwendigkeit. Wenn (i*,j*) ein Sattelpunkt ist, dann gilt nach (2.6):

(2.11)

Wir haben jedoch:

(2.12)

Aus (2.11) und (2.12) erhalten wir:

(2.13)

Wenn wir ähnlich argumentieren, kommen wir zu den Gleichheiten:

Auf diese Weise,

Andererseits ist die umgekehrte Ungleichung (2.5) immer erfüllt, also ist (2.10) wahr.

Angemessenheit. Sei (2.10) wahr. Beweisen wir die Existenz eines Sattelpunkts. Wir haben:

Gemäß Gleichheit (2.10) werden Ungleichungen (2.15) und (2.16) zu Gleichheiten. Danach haben wir:

Der Satz ist bewiesen. Das ist auch bewiesen allgemeine Bedeutung Maximin und Minimax entsprechen dem Preis des Spiels.

Gemischte Spielerweiterung

Betrachten Sie ein Matrixspiel G. Wenn darin eine Gleichgewichtssituation vorliegt, dann ist das Minimax gleich dem Maximin. Darüber hinaus kann jeder Spieler dem anderen Spieler Informationen über seine optimale Strategie mitteilen. Sein Gegner wird aus dieser Information keinen zusätzlichen Nutzen ziehen können. Nehmen wir nun an, dass es im Spiel G keine Gleichgewichtssituation gibt. Dann:

In diesem Fall sind die Minimax- und Maximin-Strategien nicht stabil. Spieler können Anreize haben, von ihren umsichtigen Strategien abzuweichen, und zwar in Bezug auf die Möglichkeit einer höheren Auszahlung, aber auch auf das Risiko eines Verlusts, d. h. einer geringeren Auszahlung als bei der Anwendung einer umsichtigen Strategie. Bei riskanten Strategien hat die Weitergabe von Informationen über diese an den Gegner nachteilige Folgen: Der Spieler erhält automatisch eine geringere Auszahlung als bei einer vorsichtigen Strategie.

Beispiel 3. Lassen Sie die Spielmatrix wie folgt aussehen:

Für eine solche Matrix, d.h. Gleichgewicht existiert nicht. Die vorsichtigen Strategien der Spieler sind i*=1, j*=2. Lassen Sie Spieler 2 der Strategie j*=2 folgen und Spieler 1 wählt die Strategie i=2. dann erhält dieser eine Auszahlung von 3, also zwei Einheiten mehr als das Maximin. Wenn jedoch Spieler 2 die Pläne von Spieler 1 errät, ändert er seine Strategie auf j=1, und dann erhält der erste Spieler eine Auszahlung von 0, also weniger als sein Maximin. Ähnliche Überlegungen lassen sich auch für den zweiten Spieler anstellen. Im Allgemeinen können wir den Schluss ziehen, dass der Einsatz einer abenteuerlichen Strategie in einem separaten Spielabschnitt zu einem über dem garantierten Ergebnis liegenden Ergebnis führen kann, sein Einsatz jedoch mit Risiken verbunden ist. Es stellt sich die Frage: Ist es möglich, eine zuverlässige, vorsichtige Strategie mit einer abenteuerlichen zu kombinieren, um die durchschnittliche Auszahlung zu steigern? Im Wesentlichen geht es um die Frage, wie die Auszahlung (2,17) zwischen den Spielern aufgeteilt werden soll.

Es stellt sich heraus, dass eine vernünftige Lösung darin besteht, eine gemischte Strategie zu verwenden, also eine zufällige Auswahl reiner Strategien. Erinnere dich daran Die Strategie von Spieler 1 heißt gemischt, wenn die Wahl der i-ten Reihe von ihm mit einer gewissen Wahrscheinlichkeit getroffen wird p ich . Eine solche Strategie lässt sich anhand der Wahrscheinlichkeitsverteilung identifizieren auf mehreren Zeilen. Angenommen, der erste Spieler hat m reine Strategien und der zweite Spieler hat n reine Strategien. Dann sind ihre gemischten Strategien Wahrscheinlichkeitsvektoren:

(2.18)

Betrachten Sie zwei mögliche gemischte Strategien für den ersten Spieler in Beispiel 3: . Diese Strategien unterscheiden sich in der Wahrscheinlichkeitsverteilung zwischen reinen Strategien. Wenn im ersten Fall die Zeilen der Matrix vom Spieler mit gleichen Wahrscheinlichkeiten ausgewählt werden, dann im zweiten Fall mit unterschiedlichen Wahrscheinlichkeiten. Wenn wir von gemischter Strategie sprechen, meinen wir zufällige Wahl keine „zufällige“ Wahl, sondern eine Wahl, die auf der Arbeit eines Zufallsmechanismus basiert, der die von uns benötigte Wahrscheinlichkeitsverteilung liefert. Für die Umsetzung der ersten der gemischten Strategien eignet sich also ein Münzwurf gut. Der Spieler wählt die erste oder die zweite Reihe, je nachdem, wie die Münze herausfällt. Im Durchschnitt wählt der Spieler gleich oft sowohl die erste als auch die zweite Reihe, aber die Wahl in einer bestimmten Iteration des Spiels unterliegt keiner festen Regel und unterliegt dem größtmöglichen Grad an Geheimhaltung: vor der Implementierung des Zufallsmechanismus , es ist selbst dem allerersten Spieler unbekannt. Zur Umsetzung der zweiten gemischten Strategie eignet sich der Draw-Mechanismus gut. Der Spieler nimmt sieben identische Zettel, markiert drei davon mit einem Kreuz und wirft sie in den Hut. Dann holt er zufällig eines davon heraus. Nach der klassischen Wahrscheinlichkeitstheorie wird er mit einer Wahrscheinlichkeit von 3/7 ein Blatt Papier mit einem Kreuz und mit einer Wahrscheinlichkeit von 4/7 ein leeres Blatt Papier herausziehen. Ein solcher Ziehmechanismus ist in der Lage, beliebige rationale Wahrscheinlichkeiten zu realisieren.

Lassen Sie die Spieler gemischte Strategien anwenden (2.18). Dann ist die Auszahlung des ersten Spielers bei einer einzelnen Iteration des Spiels eine Zufallsvariable: v(X,Y). Da die Spieler ihre Strategien unabhängig voneinander wählen, ist nach dem Wahrscdie Wahrscheinlichkeit, ein Ergebnis (i, j) mit einem Sieg zu wählen, gleich dem Produkt der Wahrscheinlichkeiten. Dann das Verteilungsgesetz der Zufallsvariablen v(X,Y) ergibt sich aus der folgenden Tabelle

Lassen Sie das Spiel nun auf unbestimmte Zeit laufen. Dann entspricht die durchschnittliche Auszahlung in einem solchen Spiel der mathematischen Erwartung des Wertes v(X,Y).

(2.19)

Wenn endgültig, aber genug große Zahlen Bei mehreren Iterationen des Spiels weicht die durchschnittliche Auszahlung geringfügig vom Wert (2,19) ab.

Beispiel 4. Berechnen Sie die durchschnittliche Auszahlung (2,19) für das Spiel aus Beispiel 3, wenn die Spieler die folgenden Strategien anwenden: . Die Auszahlungsmatrix und die Wahrscheinlichkeitsmatrix lauten wie folgt:

Finden wir den Durchschnitt:

Somit liegt die durchschnittliche Auszahlung (2,20) zwischen Maximin und Minimax.

Da für jedes Paar gemischter Strategien X und Y der Durchschnittswert des Spiels berechnet werden kann, stellt sich das Problem, die optimale Strategie zu finden. Es ist selbstverständlich, zunächst vorsichtige Strategien auszuloten. Die vorsichtige Strategie des ersten Spielers verschafft ihm ein Maximum. Die vorsichtige Strategie des zweiten Spielers erlaubt dem ersten nicht, mehr als das Minimax zu gewinnen. Als bedeutendstes Ergebnis der Theorie der Spiele mit gegensätzlichen Interessen kann folgendes angesehen werden:

Satz. In jedem Matrixspiel gibt es eine Gleichgewichtssituation in gemischten Strategien. Der Beweis dieses Theorems ist nicht einfach. Darauf wird in diesem Kurs verzichtet.

Folgen: Die Existenz einer Gleichgewichtssituation bedeutet, dass das Maximin gleich dem Minimax ist und daher jedes Matrixspiel einen Preis hat. Die optimale Strategie für den ersten Spieler ist die Maximin-Strategie. Die optimale Strategie der zweiten ist Minimax. Da das Problem, optimale Strategien zu finden, gelöst ist, sagen wir, dass es sich um ein beliebiges Matrixspiel handelt lösbar auf einer Reihe gemischter Strategien.

Lösung des Spiels 2x2

Beispiel 5. Lösen Sie das Spiel. Es ist nicht schwer zu überprüfen, dass kein Sattelpunkt vorhanden ist. Bezeichnen Sie die optimale Strategie des ersten Spielers (x, 1-x) ist ein Spaltenvektor, aber der Einfachheit halber schreiben wir ihn als Zeichenfolge. Bezeichnen Sie die optimale Strategie des zweiten Spielers (y,1-y).

Die Auszahlung des Startspielers ist eine Zufallsvariable mit folgender Verteilung:

v(x,y)	2	-1	-4	7
P	xy	x(1-y)	(1x)y	(1-x)(1-y)

Wir ermitteln die durchschnittliche Auszahlung für die Iteration des ersten Spielers – den mathematischen Erwartungswert einer Zufallsvariablen v(x,y):

Lassen Sie uns diesen Ausdruck umwandeln:

Diese mathematische Erwartung besteht aus einem konstanten (5/7) und einem variablen Teil: 14(x-11/14)(y-8/14). Wenn der Wert j Anders als am 14.08. kann der Startspieler immer wählen X so, dass der variable Teil positiv wird und sich Ihr Gewinn erhöht. Wenn der Wert X Anders als am 14.11. kann der zweite Spieler immer wählen j um den variablen Teil negativ zu machen, was die Auszahlung des ersten Spielers verringert. Somit wird der Sattelpunkt durch die Gleichungen definiert: x*=11/14, y*=8/14.

2.5 Lösen von Spielen

Ein Beispiel soll zeigen, wie man solche Spiele löst.

Beispiel 6. Lösen Sie das Spiel . Wir achten darauf, dass es keine Sattelspitze gibt. Bezeichnen Sie die gemischte Strategie des ersten Spielers X=(x, 1-x) ist ein Spaltenvektor, aber der Einfachheit halber schreiben wir ihn als Zeichenfolge.

Lassen Sie den ersten Spieler die Strategie X anwenden und der zweite seine j-th sauber Strategie. Bezeichnen wir die durchschnittliche Auszahlung des ersten Spielers in dieser Situation als . Wir haben:

Zeichnen wir die Funktionsgraphen (2.21) auf der Strecke .

Die Ordinate eines Punktes auf einem der Liniensegmente entspricht der Auszahlung des Startspielers in einer Situation, in der er eine gemischte Strategie anwendet (x,(1-x)), und der zweite Spieler die entsprechende reine Strategie. Das garantierte Ergebnis des ersten Spielers ist der untere Umschlag der Linienfamilie (unterbrochenes ABC). höchster Punkt Diese gestrichelte Linie (Punkt B) ist das maximal garantierte Ergebnis von Spieler 1. Die Abszisse von Punkt B entspricht der optimalen Strategie des ersten Spielers.

Da der gewünschte Punkt B der Schnittpunkt der Geraden und ist, kann seine Abszisse als Lösung der Gleichung gefunden werden:

Somit ist die optimale gemischte Strategie des ersten Spielers (5/9, 4/9). Die Ordinate von Punkt B ist der Preis des Spiels. Es ist gleich:

(2.22)

Beachten Sie, dass die Linie, die der zweiten Strategie des zweiten Spielers entspricht, über Punkt B verläuft. Das bedeutet, dass, wenn der erste Spieler seine optimale Strategie anwendet und Spieler 2 die zweite verwendet, der Verlust des zweiten Spielers im Vergleich zur Anwendung der Strategien zunimmt 1 oder 3. Somit darf die zweite Strategie nicht an der optimalen Strategie des zweiten Spielers teilnehmen. Die optimale Strategie für Spieler 2 sollte sein: . Üblicherweise werden die reinen Strategien 1 und 3 des zweiten Spielers aufgerufen, die in der optimalen Strategie Komponenten ungleich Null haben bedeutsam. Strategie 2 heißt unbedeutend. Aus der obigen Abbildung sowie aus Gleichung (2.22) ist ersichtlich, dass die Auszahlung des zweiten Spielers nicht davon abhängt, welche seiner wesentlichen Strategien er anwendet, wenn der erste Spieler seine optimale Strategie anwendet. Er kann auch jede beliebige gemischte Strategie bestehend aus wesentlichen (insbesondere optimalen) anwenden, die Auszahlung ändert sich auch in diesem Fall nicht. Eine völlig analoge Aussage gilt auch für den umgekehrten Fall. Wenn der zweite Spieler seine optimale Strategie verwendet, hängt die Auszahlung des ersten Spielers nicht davon ab, welche seiner wesentlichen Strategien er verwendet, und entspricht den Kosten des Spiels. Anhand dieser Aussage finden wir die optimale Strategie für den zweiten Spieler.

Optimale Strategien in der Konflikttheorie sind jene Strategien, die die Akteure zu stabilen Gleichgewichten führen, d.h. einige Situationen, die alle Spieler zufrieden stellen.

Die Optimalität einer Lösung in der Spieltheorie basiert auf dem Konzept Gleichgewichtssituation:

1) Es lohnt sich für keinen der Spieler, von der Gleichgewichtssituation abzuweichen, wenn alle anderen darin bleiben,

2) die Bedeutung des Gleichgewichts – bei wiederholter Wiederholung des Spiels erreichen die Spieler eine Gleichgewichtssituation und beginnen das Spiel in jeder strategischen Situation.

In jeder Wechselwirkung können die folgenden Arten von Gleichgewichten existieren:

1. Gleichgewicht in vorsichtigen Strategien . Bestimmt durch Strategien, die Spieler bieten garantiertes Ergebnis;

2. Gleichgewicht in dominanten Strategien .

Dominante Strategie ist ein solcher Aktionsplan, der dem Teilnehmer den maximalen Gewinn verschafft, unabhängig von den Handlungen des anderen Teilnehmers. Daher wird das Gleichgewicht der dominanten Strategien die Schnittmenge der dominanten Strategien beider Spielteilnehmer sein.

Wenn die optimalen Strategien der Spieler alle anderen Strategien dominieren, herrscht im Spiel ein Gleichgewicht der dominanten Strategien. Im Gefangenendilemma-Spiel lautet die Nash-Gleichgewichtsstrategie („zugeben – zugeben“). Darüber hinaus ist es wichtig zu beachten, dass sowohl für Spieler A als auch für Spieler B „Erkennen“ die vorherrschende Strategie ist, während „Nicht-Erkennen“ dominiert;

3. Gleichgewicht Nash . Nash-Gleichgewicht ist eine Art Entscheidung eines Spiels mit zwei oder mehr Spielern, bei dem kein Teilnehmer die Auszahlung erhöhen kann, indem er seine Entscheidung einseitig ändert, während andere Teilnehmer ihre Entscheidung nicht ändern.

Sagen wir das Spiel N Gesichter in Normalform, wobei die Menge der reinen Strategien und die Menge der Auszahlungen ist.

Wenn jeder Spieler im Strategieprofil eine Strategie auswählt, erhält der Spieler eine Auszahlung. Darüber hinaus hängt die Auszahlung vom gesamten Strategieprofil ab: nicht nur von der vom Spieler selbst gewählten Strategie, sondern auch von den Strategien anderer Leute. Das Strategieprofil ist ein Nash-Gleichgewicht, wenn eine Änderung seiner Strategie für keinen Spieler, also für keinen, von Vorteil ist

Ein Spiel kann sowohl in reinen als auch in gemischten Strategien ein Nash-Gleichgewicht aufweisen.

Nash hat das bewiesen, wenn es erlaubt ist gemischte Strategien, dann in jedem Spiel N Spieler werden mindestens ein Nash-Gleichgewicht haben.

In einer Nash-Gleichgewichtssituation bietet die Strategie jedes Spielers ihm die beste Reaktion auf die Strategien anderer Spieler;

4. Gleichgewicht Stackelberg. Stackelberg-Modell– spieltheoretisches Modell eines oligopolistischen Marktes bei Vorliegen einer Informationsasymmetrie. In diesem Modell wird das Verhalten von Unternehmen durch ein dynamisches Spiel mit vollständiger perfekter Information beschrieben, in dem das Verhalten von Unternehmen modelliert wird statisch Spiele mit alle Informationen. Hauptmerkmal Spiel ist die Anwesenheit eines führenden Unternehmens, das als erstes das Produktionsvolumen der Güter ermittelt, und die übrigen Unternehmen orientieren sich bei ihren Berechnungen daran. Grundvoraussetzungen des Spiels:

Die Branche produziert ein homogenes Produkt: Die Unterschiede in den Produkten verschiedener Firmen sind vernachlässigbar, was bedeutet, dass sich der Käufer bei der Auswahl des Unternehmens, bei dem er kauft, nur auf den Preis konzentriert;

Die Branche hat eine kleine Anzahl von Firmen.

Unternehmen legen die Menge der produzierten Produkte fest und der Preis dafür wird auf der Grundlage der Nachfrage bestimmt;

Es gibt ein sogenanntes Führungsunternehmen, an dessen Produktionsvolumen sich andere Unternehmen orientieren.

Somit wird das Stackelberg-Modell verwendet, um in dynamischen Spielen die optimale Lösung zu finden und entspricht der maximalen Auszahlung der Spieler, basierend auf den Bedingungen, die sich nach der bereits von einem oder mehreren Spielern getroffenen Wahl entwickelt haben. Stackelberg-Gleichgewicht.- eine Situation, in der keiner der Spieler seine Gewinne einseitig erhöhen kann und Entscheidungen zuerst von einem Spieler getroffen werden auf die Sekunde genau bekannt Spieler. Im Gefangenendilemma-Spiel wird das Stackelberg-Gleichgewicht im Quadrat (1; 1) erreicht – „Schuld eingestehen“ beider Kriminellen;

5. Pareto-Optimalität- ein Zustand des Systems, in dem der Wert jedes einzelnen Kriteriums, das den Zustand des Systems beschreibt, nicht verbessert werden kann, ohne die Position anderer Spieler zu verschlechtern.

Das Pareto-Prinzip besagt: „Jede Veränderung, die keinen Verlust verursacht, aber einigen Menschen (nach ihrer eigenen Einschätzung) zugute kommt, ist eine Verbesserung.“ Somit wird das Recht auf alle Änderungen anerkannt, die niemandem zusätzlichen Schaden zufügen.

Die Menge der Pareto-optimalen Systemzustände wird „Pareto-Menge“, „die Menge der im Sinne von Pareto optimalen Alternativen“ oder „Menge optimaler Alternativen“ genannt.

Eine Situation, in der die Pareto-Effizienz erreicht wurde, ist eine Situation, in der alle Vorteile des Austauschs ausgeschöpft sind.

Pareto-Effizienz ist eines der zentralen Konzepte der modernen Wirtschaftswissenschaften. Basierend auf diesem Konzept werden der erste und zweite grundlegende Wohlfahrtssatz konstruiert.

Eine der Anwendungen der Pareto-Optimalität ist die Pareto-Verteilung von Ressourcen (Arbeit und Kapital) in der internationalen Wirtschaftsintegration, d. h. Wirtschaftsunion zweier oder mehrerer Staaten. Interessanterweise wurde die Pareto-Verteilung vor und nach der internationalen Wirtschaftsintegration mathematisch angemessen beschrieben (Dalimov R.T., 2008). Die Analyse ergab, dass sich die Wertschöpfung der Sektoren und der Ertrag der Arbeitsressourcen gemäß der bekannten Wärmeleitungsgleichung, ähnlich einem Gas oder einer Flüssigkeit im Weltraum, gegenläufig bewegen, was die Anwendung der verwendeten Analysetechnik ermöglicht in der Physik in Bezug auf ökonomische Probleme der Migration ökonomischer Parameter.

Pareto-Optimum besagt, dass der Wohlstand der Gesellschaft sein Maximum erreicht und die Verteilung der Ressourcen dann optimal wird, wenn jede Änderung dieser Verteilung den Wohlstand mindestens eines Subjekts des Wirtschaftssystems verschlechtert.

Pareto-optimale Marktlage- eine Situation, in der es unmöglich ist, die Position eines Teilnehmers am Wirtschaftsprozess zu verbessern, ohne gleichzeitig das Wohlergehen mindestens eines anderen zu beeinträchtigen.

Nach dem Pareto-Kriterium (Kriterium für das Wachstum der sozialen Wohlfahrt) ist eine Bewegung in Richtung des Optimums nur mit einer solchen Ressourcenverteilung möglich, die das Wohlergehen mindestens einer Person erhöht, ohne anderen zu schaden.

Situation S* wird als Pareto-dominante Situation S bezeichnet, wenn:

für jeden Spieler seine Auszahlung in S<=S*

· Es gibt mindestens einen Spieler, für den seine Auszahlung in der Situation S*>S gilt

Im Problem des „Gefangenendilemmas“ entspricht das Pareto-Gleichgewicht, wenn es unmöglich ist, die Position eines der Spieler zu verbessern, ohne die Position des anderen zu verschlechtern, der Situation des Quadrats (2; 2).

In Betracht ziehen Beispiel 1.

Optimale Strategien in der Konflikttheorie sind jene Strategien, die die Akteure zu stabilen Gleichgewichten führen, d.h. einige Situationen, die alle Spieler zufrieden stellen.

Die Optimalität einer Lösung in der Spieltheorie basiert auf dem Konzept Gleichgewichtssituation:

1) Es lohnt sich für keinen der Spieler, von der Gleichgewichtssituation abzuweichen, wenn alle anderen darin bleiben,

2) die Bedeutung des Gleichgewichts – bei wiederholter Wiederholung des Spiels erreichen die Spieler eine Gleichgewichtssituation und beginnen das Spiel in jeder strategischen Situation.

In jeder Wechselwirkung können die folgenden Arten von Gleichgewichten existieren:

1. Gleichgewicht in vorsichtigen Strategien . Bestimmt durch Strategien, die den Spielern ein garantiertes Ergebnis bieten;

2. Gleichgewicht in dominanten Strategien .

Sagen wir das Spiel N Gesichter in Normalform, wobei die Menge der reinen Strategien und die Menge der Auszahlungen ist.

Ein Spiel kann sowohl in reinen als auch in gemischten Strategien ein Nash-Gleichgewicht aufweisen.

Nash hat das bewiesen, wenn es erlaubt ist gemischte Strategien, dann in jedem Spiel N Spieler werden mindestens ein Nash-Gleichgewicht haben.

In einer Nash-Gleichgewichtssituation bietet die Strategie jedes Spielers ihm die beste Reaktion auf die Strategien anderer Spieler;

4. Gleichgewicht Stackelberg. Stackelberg-Modell– spieltheoretisches Modell eines oligopolistischen Marktes bei Vorliegen einer Informationsasymmetrie. In diesem Modell wird das Verhalten von Unternehmen durch ein dynamisches Spiel mit vollständiger perfekter Information beschrieben, in dem das Verhalten von Unternehmen modelliert wird statisch Spiele mit vollständigen Informationen. Das Hauptmerkmal des Spiels ist die Anwesenheit eines führenden Unternehmens, das zunächst das Produktionsvolumen der Güter festlegt, und die übrigen Unternehmen orientieren sich bei ihren Berechnungen daran. Grundvoraussetzungen des Spiels:

Die Branche hat eine kleine Anzahl von Firmen.

Unternehmen legen die Menge der produzierten Produkte fest und der Preis dafür wird auf der Grundlage der Nachfrage bestimmt;

Es gibt ein sogenanntes Führungsunternehmen, an dessen Produktionsvolumen sich andere Unternehmen orientieren.

Somit wird das Stackelberg-Modell verwendet, um in dynamischen Spielen die optimale Lösung zu finden und entspricht der maximalen Auszahlung der Spieler, basierend auf den Bedingungen, die sich nach der bereits von einem oder mehreren Spielern getroffenen Wahl entwickelt haben. Stackelberg-Gleichgewicht.- eine Situation, in der keiner der Spieler seinen Gewinn einseitig erhöhen kann und Entscheidungen zuerst von einem Spieler getroffen werden und dem zweiten Spieler bekannt werden. Im Gefangenendilemma-Spiel wird das Stackelberg-Gleichgewicht im Quadrat (1; 1) erreicht – „Schuld eingestehen“ beider Kriminellen;

Die Menge der Pareto-optimalen Systemzustände wird „Pareto-Menge“, „die Menge der im Sinne von Pareto optimalen Alternativen“ oder „Menge optimaler Alternativen“ genannt.

Eine Situation, in der die Pareto-Effizienz erreicht wurde, ist eine Situation, in der alle Vorteile des Austauschs ausgeschöpft sind.

Pareto-Effizienz ist eines der zentralen Konzepte der modernen Wirtschaftswissenschaften. Basierend auf diesem Konzept werden der erste und zweite grundlegende Wohlfahrtssatz konstruiert.

Situation S* wird als Pareto-dominante Situation S bezeichnet, wenn:

für jeden Spieler seine Auszahlung in S<=S*

· Es gibt mindestens einen Spieler, für den seine Auszahlung in der Situation S*>S gilt

In Betracht ziehen Beispiel 1:

Gleichgewichte in dominanten Strategien Nein.

Nash-Gleichgewicht. (5.5) und (4.4). Da es für jeden Spieler unrentabel ist, individuell von der gewählten Strategie abzuweichen.

Pareto-Optimum. (5.5). Da die Auszahlung der Spieler bei der Wahl dieser Strategien mehr Siege bei der Wahl anderer Strategien.

Stackelberg-Gleichgewicht:

Spieler A macht den ersten Zug.

Wählt seine erste Strategie. B wählt die erste Strategie. A bekommt 5.

Wählt seine zweite Strategie. B wählt den zweiten. A bekommt 4.

5 > 4 =>

B macht den ersten Zug.

Wählt seine erste Strategie. A wählt die erste Strategie. B bekommt 5.

Wählt seine zweite Strategie. Und er wählt den zweiten. B bekommt 4.

5 > 4 => Stackelberg-Gleichgewicht (5, 5)

Beispiel 2Duopol-Modellierung.

Betrachten Sie die Essenz dieses Modells:

Angenommen, es gäbe eine Branche mit zwei Firmen, von denen eine die „Leader-Firma“ und die andere die „Follower-Firma“ ist. Sei der Produktpreis lineare Funktion Gesamtangebot Q:

P(Q) = A − bQ.

Nehmen wir außerdem an, dass die Kosten der Unternehmen pro Produktionseinheit konstant und gleich sind Mit 1 und Mit 2 bzw. Dann wird der Gewinn des ersten Unternehmens bestimmt Formel

Π 1 = P(Q 1 + Q 2) * Q 1 − C 1 Q 1 ,

und der Gewinn des zweiten

Π 2 = P(Q 1 + Q 2) * Q 2 − C 2 Q 2 .

Gemäß dem Stackelberg-Modell ordnet das erste Unternehmen – das führende Unternehmen – im ersten Schritt seinen Output zu Q 1 . Danach bestimmt das zweite Unternehmen – das Folgeunternehmen – durch Analyse der Aktionen des Führungsunternehmens seinen Output Q 2. Das Ziel beider Unternehmen ist die Maximierung ihrer Zahlungsfunktionen.

Das Nash-Gleichgewicht in diesem Spiel wird durch Rückwärtsinduktion bestimmt. Betrachten Sie die vorletzte Phase des Spiels – den Zug der zweiten Firma. Zu diesem Zeitpunkt kennt Unternehmen 2 die optimale Leistung von Unternehmen 1 Q 1 * . Dann das Problem, die optimale Leistung zu ermitteln Q 2 * reduziert sich auf die Lösung des Problems, den Maximalpunkt der Auszahlungsfunktion des zweiten Unternehmens zu finden. Maximieren der Funktion Π 2 in Bezug auf die Variable Q 2 zählen Q 1 gegeben, finden wir den optimalen Output des zweiten Unternehmens

Dies ist die beste Reaktion der Folgefirma auf die Wahl der Veröffentlichung durch die Führungsfirma Q 1 * . Das führende Unternehmen kann seine Auszahlungsfunktion angesichts der Form der Funktion maximieren Q 2*. Der Maximalpunkt der Funktion Π 1 in der Variablen Q 1 beim Auswechseln Q 2 * wird

Ersetzen Sie dies in den Ausdruck for Q 2 * , wir bekommen

Im Gleichgewicht produziert das Spitzenunternehmen also doppelt so viel Output wie das Folgeunternehmen.

Wenn wir die Angebots- und Nachfragelinien in einem einzigen Diagramm kombinieren, erhalten wir grafisches Bild Gleichgewicht in Koordinaten P, Q(Abb. 2.6). Der Schnittpunkt der Linien hat Koordinaten (P * , Q*), Wo R* - Gleichgewichtspreis, Q*- Gleichgewichtsvolumen von Produktion und Verbrauch.

Marktgleichgewicht- Dabei handelt es sich um einen Marktzustand, bei dem bei einem gegebenen Preisniveau die nachgefragte Menge der angebotenen Menge entspricht.

Nur am Punkt des Gleichgewichts E Der Markt ist ausgeglichen, keiner der Marktakteure hat Anreize, die Situation zu ändern. Dies bedeutet, dass das Marktgleichgewicht die Eigenschaft hat Nachhaltigkeit - Im Falle eines Nichtgleichgewichtszustands sind Marktakteure motiviert, den Markt wieder ins Gleichgewicht zu bringen. Zum Nachweis der Stabilität wird üblicherweise die Logik von L. Walras oder A. Marshall verwendet.

Laut L. Walras gibt es bei zu hohen Preisen ein Überangebot – Überproduktion (Segment). A-B in Abb. 2.6i) nennt man einen solchen Markt Käufermarkt da der Käufer bei Geschäftsabschlüssen die Möglichkeit hat, eine Preisminderung zu verlangen. In einer solchen Situation ist zunächst einmal der Verkäufer nicht interessiert, der gezwungen ist, die Preise zu senken und die Produktionsmengen zu reduzieren. Wenn die Preise sinken, steigt die nachgefragte Menge A-B schrumpft, bis es einen Gleichgewichtspunkt erreicht E.

Bei niedrige Preise Es besteht ein Nachfrageüberschuss – es entsteht ein Mangel (Segment CFna Abb. 2.6a). Verkäufermarkt. Der Käufer wird gezwungen

Wenn ein Verbraucher seinen Konsum reduziert und für ein knappes Gut zu viel bezahlt, steigt mit steigendem Preis die angebotene Menge und die Knappheit nimmt ab, bis der Markt ausgeglichen ist.

Laut A. Marshall (Abb. 2.66), Bei kleinen Produktionsmengen übersteigt der Nachfragepreis den Verkäuferpreis, bei großen Produktionsmengen umgekehrt. In jedem Fall stimuliert die Ungleichgewichtssituation eine Verschiebung des Preises oder des Volumens von Angebot und Nachfrage in Richtung eines Gleichgewichts. Gleichgewicht (A) Laut Walras reguliert der Preis das Ungleichgewicht von Angebot und Nachfrage. (B) Laut Marshall werden die Preise des Käufers und des Verkäufers durch eine Änderung der Mengen ausgeglichen.

Reis. 2.6. Herstellung des Marktgleichgewichts: c) nach L. Walras; b) nach A. Marshall

Eine Änderung der Marktnachfrage oder des Marktangebots führt zu einer Gleichgewichtsänderung (Abb. 2.7). Steigt beispielsweise die Marktnachfrage, verschiebt sich die Nachfragelinie nach rechts, dann steigen Gleichgewichtspreis und -menge. Wenn das Marktangebot abnimmt, verschiebt sich die Angebotslinie nach links, was zu einem Preisanstieg und einem Rückgang des Volumens führt.

Dieses Model Der Markt ist statisch, da die Zeit darin nicht vorkommt.

Modell „Spinne“.

Als Beispiel für ein dynamisches Modell des Marktgleichgewichts stellen wir das einfachste „Spinnennetz“-Modell vor. Angenommen, die nachgefragte Menge hängt vom Preisniveau der aktuellen Periode ab T, und das Angebotsvolumen – aus den Preisen der Vorperiode t-1:

Q d i = Q d i (P t) , Q s i = Q s i (P t -1) ,

wobei t = 0,1….T der diskrete Wert des Zeitraums ist.

Reis. 2.7. Veränderung des Marktgleichgewichts:

a) aufgrund einer gestiegenen Nachfrage; B) aufgrund einer Abnahme

bietet an

Marktpreis P t entspricht möglicherweise nicht dem Gleichgewichtspreis R*, und es gibt drei mögliche Dynamiken P t(Abb. 2.8).

Die Variante des Entwicklungsverlaufs in diesem Modell hängt vom Verhältnis der Steigungen der Angebots- und Nachfragelinien ab.

Reis. 2.8. „Spider“-Modell des Marktgleichgewichts:

a) die Abweichung vom Gleichgewicht nimmt ab; 5) Abweichung

steigt aus dem Gleichgewicht (das „Katastrophen“-Modell); c) der Markt

schwingt zyklisch um den Gleichgewichtspunkt, aber das Gleichgewicht

Beliebt in der Kategorie: