Kann man die Algorithmen für Nullsummenspiele(Payoff A + Payoff B=0) auch für nicht Nichtnullsummenspiele anwenden?

...komplette Frage anzeigen Beide Algorithmen - (Mathematik, Algebra, Spieltheorie)

1 Antwort

Ja durchaus. Statt einer einzigen Gewinn-Matrix arbeitet man mit zwei Gewinnmatrizen, π⁽¹⁾ für Spieler 1 und π⁽²⁾ für Spieler 2. Es seien am Anfang X⁽¹⁾ bzw. X⁽²⁾ die Mengen der Strategien für Spieler 1 bzw. 2. Hierbei wird definiert:

R ∋ π⁽¹⁾[x,y] = der Gewinn für Spieler 1
R ∋ π⁽²⁾[x,y] = der Gewinn für Spieler 2

gegeben Spieler 1 die reine Strategie x ∈ X⁽¹⁾ wählt und Spieler 2 die reine Strategie y ∈ X⁽²⁾ wählt.


Die beiden Verfahren laufen genauso ab, aber Achtung, man arbeitet anhand einer der beiden Gewinn-Matrizen/Funktionen und eliminiert gleichzeitig eine Zeile bzw. Spalte (Angabe, wenn als Funktionen betrachtet) von beiden π⁽ᵏ⁾s. Beachte folgende Definitionen:


Definition 0. Ein Spiel mit einer Menge S von Spielern sei betrachtet. Eine reine Gesamtstrategie sei ein Tupel a ∈ ∏ X⁽ᵏ⁾ =: Ω, wobei das Produkt über alle k ∈ S läuft. Die Mengen X⁽ᵏ⁾ dürfen unendliche topologische Räume sein. Und S darf abzählbar unendlich sein. Das ganze Spiel sei G=(Ω,π) bezeichnet.


Definition 1. Wenn Spieler k* Strategie x* ∈ X⁽ᵏ*⁾ eliminiert, ändert sich das Spiel wie folgt: Ω wird durch Ω´ := ∏X⁽ᵏ⁾´ ersetzt, wobei X⁽ᵏ⁾´ = X⁽ᵏ⁾ für k≠k* und X⁽ᵏ*⁾´ = X⁽ᵏ*⁾ \ {x*}. Entsprechend werden die Gewinn-Funktionen (Matrizen) von π⁽ᵏ⁾ auf π⁽ᵏ⁾´ = π⁽ᵏ⁾ | Ω´ reduziert. Also (Ω,π) ~> (Ω´,π´).
Beachte, im Falle einer Matrixdarstellung ist dies äquivalent zu der gleichzeitigen Eliminierung bei allen Matrizen von derselben Zeile bzw. Spalte.
Definition 1´. Wenn gleichzeitig eine Teilmenge von den Spieler S* ⊆ S jeweils eine Teilmenge deren Strategien A⁽ᵏ⁾ ⊆ X⁽ᵏ⁾ für k ∈ S reduzieren, ist die Reduktion ähnlich. (Ω,π) ~> (Ω´,π´), wobei π⁽ᵏ⁾´ = π⁽ᵏ⁾ | Ω´ für alle k ∈ S und Ω´ = ∏X⁽ᵏ⁾´ mit X⁽ᵏ⁾´ = X⁽ᵏ⁾ für k ∈ S\S* und X⁽ᵏ⁾´ = X⁽ᵏ⁾ \ A⁽ᵏ⁾ für k ∈ S*.
Im Falle einer Matrixdarstellung ist dies äquivalent zu der gleichzeitigen Eliminierung bei allen Matrizen von denselben Zeilen und Spalten.

Definition 2. Fixiere ein Spieler k ∈ S und x, x´ ∈ X⁽ᵏ⁾. Dann ist x genau dann durch x´ streng dominiert für Spieler k, wenn π⁽ᵏ⁾(a) < π⁽ᵏ⁾(a´) für alle a, a´ Gesamtstrategien mit a[k] = x und a´[k] = x´.

Definition 3. Fixiere ein Spieler k ∈ S und x ∈ X⁽ᵏ⁾. Das schlimmste Ergebnis für x ist π⁽ᵏ⁾_min[x] := INF{π⁽ᵏ⁾[a] : a ∈ Ω, a[k]=x}. Die reine Strategie x ist dann eine Maxmin-Strategie für Spieler k, wenn für alle x´ ∈ X⁽ᵏ⁾ gilt π⁽ᵏ⁾_min[x´] ≤ π⁽ᵏ⁾_min[x].


Jetzt sind die Verfahren genauso zu beschreiben.

Eliminierung von dominierenden Strategien. Durch alle Spiele durchlaufen. Bei jedem Spieler k nach allen streng dominierenden Strategie suchen und diese vom Spiel eliminieren. Wiederholen bis es keine zu eliminierenden Strategien bei keinem Spieler mehr gibt.

Minmax. Für jeden Spieler die Maxmin-Strategien finden. Führe eine gleichzeitige Eliminierung durch von allen nicht-Maxmin-Strategien aus. Wiederhole wenn nötig, bis das Ergebnis stabilisiert.

Ein Nullsummenspiel ist einfach ein Sonderfall dieser allgemeinen Definition eines Spiels, wo es gilt

∑ π⁽ᵏ⁾[a] = 0 für alle a ∈ Ω,

wobei die Summe über alle Spieler k läuft. Das heißt, man kann auch Nullsummenspielen zwischen 2 Spielern durch 2 Gewinnmatrizen darstellen und genauso wie oben die Verfahren durchführen.

0

Was möchtest Du wissen?