Lineare Optimierung mit Mathematica

Gesucht ist eine optimale Strategie für folgendes Spiel:

Gegeben sei eine reelle NxM-Matrix K (die Auszahlungstabelle)

In jedem Spielzug

• wählt Spieler A heimlich eine Zahl i aus {1,...,N}, Spieler B eine Zahl j aus {1,...,M},
• danach geben beide Spieler ihre Zahlen bekannt,
• worauf Spieler B den Betrag K_ij an Spieler A zahlen muß (negative Werte von K_ij bedeuten Zahlung von A an B).

Angenommen, die Spieler A und B wählen den entsprechenden Index zufällig mit den Wahrscheinlichkeiten p_i bzw. q_j. Wie lauten diese Wahrscheinlichkeiten in Abhängigkeit von K? Wieviel gewinnt Spieler A im Mittel?

Obiges Spiel beschreibt ein klassisches lineares Optimierungsproblem, das meist mit Hilfe des Simplex-Algorithmus (siehe Bronstein oder Numerical Recipes, § 10.8) gelöst wird. Mathematica besitzt eine entsprechende eingebaute Funktion.

spiel.nb