[PYTHON] Spieltheorie mit Kombinationsoptimierung lösen

Was ist das

In Spieltheorie Im Fall des Nullsummenspiels kann die optimale Mischstrategie durch lineare Optimierung (LP) erhalten werden [^ 1]. Versuchen wir es mit Python am Beispiel des arrangierten Janken.

Informationen zur linearen Optimierung finden Sie unter Kombinationsoptimierung verwenden.

[^ 1]: Aus dem Seminar "ODER beginnend mit Excel Solver"

Janken gewinnt Tabelle

Bestimmen Sie die Verstärkungstabelle (Translokation) wie folgt. Wenn Sie die Goo (G) gewinnen, wird Ihre Punktzahl vervierfacht.

Formulierung

―― Nehmen wir an, dass das Verhältnis von Goo, Choki und Par $ x, y, z $ beträgt. (Gemischte Strategie)

• Zu diesem Zeitpunkt ist $ x + y + z = 1 $.
• Der erwartete Wert ist $ -y + z $, wenn der Gegner goo ist, $ 4x --z $, wenn der Gegner choki ist, und $ -x + y $, wenn der Gegner par ist.
• Maximieren wir den Mindestwert ($ w $) dieser drei erwarteten Werte. Auf diese Weise liegt der erwartete Wert über $ w $, unabhängig davon, was die andere Partei tut.

Löse mit Python

python

from pulp import *
from ortoolpy import addvar, addvars

a = [[0, -1, 1], [4, 0, -1], [-1, 1, 0]]
m = LpProblem(sense=LpMaximize) #Mathematisches Modell
xyz = addvars(3) #Variable x,y,z
w = addvar(lowBound=None) #Variable w
m += w #Zielfunktion
m += lpSum(xyz) == 1 #Einschränkungen
for i in range(3):
    m += lpDot(a[i], xyz) >= w #Einschränkungen
m.solve() #Lösung
print(value(w), [value(v) for v in xyz])
>>>
0.16666667 [0.16666667, 0.33333333, 0.5]

Wenn Sie Goo, Choki und Par in einem Verhältnis von [1/6, 1/3, 1/2] ausgeben, können Sie sehen, dass der erwartete Wert auf 1/6 reduziert werden kann, unabhängig davon, welche Art von Bewegung der Gegner ausführt.

In nicht kooperativen Spielen ist das interessante Ergebnis, dass je höher der erwartete Wert ist, desto geringer der Prozentsatz der Hände (goo) ist, die für Sie von Vorteil sind.

das ist alles