Zero Sum Game - Several Solutions

[sano98]

Hi there,

is there a way to get all possible solutions from a zero sum game problem?
To illustrate what I mean, I altered the example from the tutorial:

from pymprog import *
#####Solve this 2-player 0-sum game:
##
##     Gain for player 1 
##    (Loss for player 2)
##   
##            ||  Player  2
##   Player 1 ||  B1     B2    B3
##      A1    ||  -1      1    0
##      A2    ||  1      -1    0
##      A3    ||  0       0    0
##
##############################
beginModel('game')
# the gain of player 1
v = var(name='game_value', 
      bounds=(None,None)) #free
# mixed strategy of player 2
p = var([1,2,3], 'prob') 
# player 2 wants to minimize v
minimize(v) 
# probability sums to 1
st(p[1]+p[2]+p[3] == 1)
# player 1 plays the best strat.
r1=st(v >= -1*p[1] + 1*p[2] + 0*p[3])
r2=st(v >= 1*p[1] + -1*p[2] + 0*p[3])
r3=st(v >= 0*p[1] + -0*p[2] + 0*p[3])
solve()
print v
print "Player 1's mixed Strategy:" 
print "A1:", r1.dual, "A2:", r2.dual, "A3:", r3.dual
print "Player 2's mixed strategy:" 
print p
endModel()

The result is:

game_value=0.000000
Player 1's mixed Strategy:
A1: 0.5 A2: 0.5 A3: 0.0
Player 2's mixed strategy:
{1: prob=0.500000, 2: prob=0.500000, 3: prob=0.000000}

But obviously, this is not the only solution. The strategy  {A1: 0.0 A2: 0.0 A3: 1.0} has the same expectation value, as well as for example  {A1: 0.25 A2: 0.25 A3: 0.5}  or any other strategy where A1 and A2 are chosen in the same proportion and in the rest of the cases A3 is played.

Now, since there are infinite many solutions, the simple answer to my question must obviously be: "No, you can't list all possible solutions to such a problem."
But it is most unsatisfying that there seems to be no feedback that additional solutions exist.
If maybe at least the extrema could be suggested as solutions? (in this case, {A1: 0.0 A2: 0.0 A3: 1.0} and {A1: 0.5 A2: 0.5 A3: 0.0} are the extrema of the solution space.)

Would be glad to get feedback.

Thanks,
Bye
Sano

[Yingjie Lan]

Hi Sano, this is an interesting question, in the way that it can be framed as a general question of obtaining/describing the whole set of optimal solutions to a LP. And you are correct that when the solution is not unique, then there are infinite many. Another thing is: it is a convex set, which can be described by a set of linear constraints. In fact, you can exactly describe them all by using the original constraints + one additional constraint: the objective function == the optimal value.

Cheers,
Lan