tturocy
commented
11 months ago Based on some other issues we have recently dealt with, I got to wondering whether it was the presence of zero-probability chance actions that was the problem. I experimented with the game below, which is the same game with the zero-probability action deleted. gambit-lp still returns non-Nash output, but importantly (1) it's different non-Nash output than the original game and (2) the output doesn't enforce sum-to-one at least information set.
These observations lead me to believe very circumstantially that the problem may be in the construction of the sequence form tableau.
At this point, it is worth observing that there is very similar code in both LCP and LP for constructing the sequence form tableau, as well as a Sfg class in solvers/enumpoly which is used to construct the systems of polynomials. It would be useful to unify these, as, in essence, the same logic appears in all three places, and further useful to expose the sequence form as a concept in its own right rather than having it embedded implicitly inside algorithms.
The above would be a good idea even if the problem here is not per se with the sequence form implementation, although it seems somehow less plausible that there would be some unknown bug in the LP solver, in particular that it would return incorrect output even in rational precision. Not impossible, but the behaviour described above seems to point the finger at the inputs.
EFG 2 R "Untitled Extensive Game" { "Villain" "Hero" }
""
c "Villain's card" 1 "" { "Flush" 0.01 "Air" 0.99 } 0
p "Turn" 1 1 "" { "Bet Turn with Flush" "Check Turn wish Flush" } 0
p "" 2 1 "" { "Call Turn" "Fold Turn" } 0
c "River Card" 2 "" { "Blank" 1/2 "Straight or Boat" 1/2 } 0
p "River" 1 2 "" { "Bet River with Flush" "Check River with Flush" } 0
p "" 2 2 "" { "Call River" "Fold River" } 0
t "" 1 "" { 5, -4 }
t "" 2 "" { 2, -1 }
t "" 3 "" { 2, -1 }
t "" 4 "" { 0.5, 0.5 }
t "" 6 "" { 1, 0 }
t "" 7 "" { 0.75, 0.25 }
p "Turn" 1 3 "" { "Bluff Turn" "Doesn't Bluff Turn" } 0
p "" 2 1 "" { "Call Turn" "Fold Turn" } 0
c "River Card" 3 "" { "Blank" 1/2 "Straight or Boat" 1/2 } 0
p "River" 1 4 "" { "Bluff River" "Doesn't Bluff River" } 0
p "" 2 2 "" { "Call River" "Fold River" } 0
t "" 8 "" { -4, 5 }
t "" 9 "" { 2, -1 }
t "" 10 "" { -1, 2 }
t "" 11 "" { 0.5, 0.5 }
t "" 13 "" { 1, 0 }
t "" 14 "" { 0.25, 0.75 }
On the following game, the output of gambit-lp on the extensive game is not Nash. This error has been in place at least since revision f21b0a00 in September 2010; I cannot reliably compile earlier versions although the git blame for the relevant files indicates no changes since before 2006; this error has probably been around quite a long time. Other methods return the correct equilibrium (which is unique). At the moment, I have no leads on where this may be going wrong