[pymprog] Several Solutions in Zero Sum Games

[Nico G. <nic...@gm...>]

Hi everyone,

 

I also posted this question in the pymprog Forum. Generally, a Forum seems
to be the more comfortable place for discussing and archiving solutions. 

But I messed up my post a little and can't seem to find an "edit"-button. 

So, here my question again on the mailing list:

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
<http://pymprog.sourceforge.net/tutorial.html#zero-sum-two-player-game>
tutorial:

#####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()
[/code]

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[1]=0.500000, 2: prob[2]=0.500000, 3: prob[3]=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