// (C) Jörg Bewersdorff 07-2003

// ====== MatrixSpiel =======================================================

// Eine Instanz des Objekts MatrixSpiel entspricht einem endlichen Zwei-
// Personen-Nullsummen-Spiel, d.h. einem Matrix-Spiel. Zur Bestimmung einer
// Minimax-Lösung für das Spiel
//          (x,y)  -> xAy
// (unter den Nebenbedingungen xe = ey = 1)
// wird für den Fall eines negativen Minimax-Wertes, der bei lauter positiven
// Koeffizienten der Matrix A auf jeden Fall gesichert ist, das Linear-Pro-
// gramm
//            Ay <= ve  mit ey = 1 und minimalem v
// d.h.
//        A(y/v) <= e
//        e(y/v)  = 1/v = Max!
//         (y/v) >= 0
//             
// Das entspricht dem Starttableau
//
//                1   y1/v  y2/v    ...  
//  Zmax          0     1     1    ... 
//  Schlupf(X1)   1  -a11  -a12    ... 
//  Schlupf(X2)   1  -a21  -a22    ... 
//               ...  
//
// Set A = new MatrixSpiel()
// A.Set_a("Name von x1", "Name von y1", 1.0);
// A.Set_a("Name von x2", "Name von y3", 2.0);
// ...
// ...
// A.Optimiere();

// Output:
// A.Minimax(), A.Wert("Name von x1"), A.Wert("Schlupf(Name von b2)")

// Der mathemtische Hintergrund wird u.a erläutert in
// Jörg Bewersdorff, "Glück, Logik und Bluff: Mathematik im Spiel -
// Methoden, Ergebnisse und Grenzen", Kapitel 3.5


function MatrixSpiel()
{
  // Eigenschaften:
  this.fastnull=0.000000001;            // Const (überschreibbar)
  this.unendlich=1E20;                  // Const (überschreibbar)
  this.Status=0;                        // Status der Instanz (0:unbearbeitet, 1:Daten gesetzt, ...)
  this.Shift=0;                         // sichert positiven Wert
  this.xNamen = new Set();              // Variablenname von x
  this.yNamen = new Set();              // Variablenname von y
  this.LP = new SimplexTableau();       // zugehöriges Linear-Programm

  // Methoden:
  this.Set_a = MatrixSpielSet_a;
  this.Optimiere = MatrixSpielOptimiere;
  this.Minimax = MatrixSpielMinimax;
  this.Wert = MatrixSpielWert;
}

// ==========================================================================


function MatrixSpielSet_a(xName, yName, Wert)
// Ein Koeffizient des Matrix-Spiels wird gesetzt:
{
  if (this.Status>1)
  {
    alert("Matrix des Spiels kann nicht mehr verändert werden");
    return ;
  } 
  this.Status=1
  this.LP.Set_a(yName+"/v",xName,Wert);
  this.xNamen.AddElement(xName);
  this.yNamen.AddElement(yName+"/v");
}


function MatrixSpielOptimiere()
// Die Minimax-Optimierung erfolgt mittels einer Lösung des entsprechenden
// Linear-Programmes:
{
  var aMin,r,xi, yj;

  if (this.Status==0)
  {
    alert("Matrix des Spiels wurde nicht definiert");
    return ;
  } 
  if (this.Status>1)
  {
    alert("Optimierung kann pro Instanz nur einmal durchgeführt werden");
    return ;
  } 
  this.Status=2;

  this.LP.fastnull = this.fastnull;
  this.LP.unendlich = this.unendlich;

  // stelle mittels eines Shifts sicher, dass der Minimax-Wert positiv ist:
  aMin=this.unendlich;
  for (r in this.LP.a.List())
    aMin = Math.min(aMin,-this.LP.a.BildLfd(r));
  if (aMin<this.fastnull) 
  // führe Shift durch (andernfalls keine Veränderung und this.Shift==0):
  {
    this.Shift = -aMin+1;                  
    for (r in this.LP.a.List())
      this.LP.a.DefBild(this.LP.a.UrbildLfd(r),-(-this.LP.a.BildLfd(r)+this.Shift));
  }

  for (xi in this.xNamen.List())
    this.LP.Set_b(xi,1);
  for (yj in this.yNamen.List())
    this.LP.Set_c(yj,1);  

  this.LP.Optimiere();
}


function MatrixSpielMinimax()
// Ermittelt den Minimax-Wert des Matrix-Spiels:
{
  if (this.Status==0)
  {
    alert("Matrix des Spiels wurde nicht definiert");
    return ;
  } 
  if (this.Status==1)
    this.Optimiere();

  return 1/this.LP.Max() - this.Shift;
}


function MatrixSpielWert(VariablenName)
// Ermittelt die Wahrscheinlichkeit zu einer reinen Strategie, wie sie
// für die berechnete Minimax-Strategie zu verwenden ist:
{
  if (this.Status==0)
  {
    alert("Matrix des Spiels wurde nicht definiert");
    return ;
  } 
  if (this.Status==1)
    this.Optimiere();

  if (this.yNamen.Member(VariablenName+"/v"))
    return this.LP.Wert(VariablenName+"/v")/this.LP.Max();

  if (this.xNamen.Member(VariablenName))
    return -this.LP.Schattenpreis("Schlupf("+VariablenName+")")/this.LP.Max();

  alert("Die Variable '"+VariablenName +"' gibt es nicht");
  return ;
}