taramath: Zwei-Personen Nullsummenspiele

Beschreibung

In der Spieltheorie werden mathematische Modelle aufgestellt und analysiert, welche der Entscheidungsfindung dienen können. Als Spezialfall untersuchen wir Zwei-Personen Nullsummenspiele, wobei für beide Spieler jeweils gemischte Strategien zu berechnen sind. Ein sehr einfaches Beispiel eines Zwei-Personen Nullsummenspiels ist das bekannte Spiel Stein-Schere-Papier. Zur Lösung derartiger Problemen, d.h. zur Berechnung von gemischten Strategien, die zu einem stabilen Zustand oder Gleichgewicht führen, kommen lineare Programme zum Einsatz. Eine detaillierte Beschreibung dazu kann dem folgenden Dokument entnommen werden.

zerosumgames.pdf

Beispiel

Im folgenden Beispiel betrachten wir das Zwei-Personen Nullsummenspiel Stein-Schere-Papier. Es werden optimale gemischte Strategien für beide Spieler durch das Lösen eines linearen Programmes berechnet. Anschließend werden die Ergebnisse entsprechend ausgegeben.

Falls andere Zwei-Personen Nullsummenspiele gelöst werden sollen, muss lediglich die Spielmatrix angepasst werden.

<!DOCTYPE html>
<html>

<head>
  <script src="taramath.js"></script>
</head>

<body>

<textarea id="output"></textarea>

<script>

/*
Die Funktion solve_zero_sum_game (A) loest das lineare Programm zur Berechnung
einer optimalen gemischen Strategie eines Zwei-Personen Nullsummenspiels zur
Spielmatrix A aus Sicht von Spieler 2.
*/
function solve_zero_sum_game (A) {
  var m = A.length;
  var n = A[0].length;

  var T = LinearAlgebra.zero_matrix(m+1, n+1);
  for (var i = 0; i < m; i++) for (var j = 0; j < n; j++) T[i][j] = A[i][j];
  for (var i = 0; i < m; i++) T[i][n] = -1;
  for (var j = 0; j < n; j++) T[m][j] = 1;

  var b = new Array(m+1);
  for (var i = 0; i < m; i++) b[i] = 0;
  b[m] = 1;

  var s = new Array(m+1);
  for (var i = 0; i < m; i++) s[i] = -1;
  s[m] = 0;

  var c = new Array(n+1);
  for (var j = 0; j < n; j++) c[j] = 0;
  c[n] = 1;

  var z = new Array(n+1);
  for (var j = 0; j < n; j++) z[j] = 1;
  z[n] = 0;

  var S = LinearProgramming.interior_point(c, z, T, b, s);
  if (typeof(S) == "string") return S;
  return [S[0].slice(0,n), S[1]];
};


// Spielmatrix definieren (Stein-Schere-Papier)
var A = [
  [  0,  1, -1 ],
  [ -1,  0,  1 ],
  [  1, -1,  0 ]
];

// optimale gemischte Strategie fuer Spieler 2
var spieler2 = solve_zero_sum_game(A);

// optimale gemischte Strategie fuer Spieler 1
var B = LinearAlgebra.mult(-1, LinearAlgebra.transpose(A));
var spieler1 = solve_zero_sum_game(B);

// Ergebnisse ausgeben
Print.init("output");
if ((typeof(spieler1) == "string") || (typeof(spieler2) == "string")) {
  Print.object("Fehler beim Loesen der linearen Programme.");
} else {
  Print.object("Gemischte Strategie Spieler 1:");
  Print.object(spieler1[0]);
  Print.object("Gemischte Strategie Spieler 2:");
  Print.object(spieler2[0]);
  Print.object("Erwartete Auszahlung an Spieler 1:");
  Print.object(spieler2[1]);
};

</script>

</body>
</html>

Vorschau aktualisieren

Zwei-Personen Nullsummenspiele

formuliert als lineares Programm