[Bug]: adding a "all zero payoff" outcome at a non-terminal node breaks lp_solve and lcp_solve

[rahulsavani]

Where did you find this bug?

PyGambit

What operating system are you using?

macOS

What version of Gambit are you using?

16.4.0

What happened?

In the following example, which is "matching pennies" as a EFG, we get the wrong answers from lp_solve and lcp_solve by adding an outcome with payoffs [0,0] at a non-terminal node.

def create_MP(with_neutral_outcome=False) -> gbt.Game:
    g = gbt.Game.new_tree(
        players=["Alice", "Bob"], title="Matching pennies")
    g.append_move(g.root, "Alice", ["H", "T"])
    g.append_move(g.root.children, "Bob", ["h", "t"])
    alice_lose = g.add_outcome([-1, 1], label="Alice lose")
    alice_win = g.add_outcome([1, -1], label="Alice win")
    if with_neutral_outcome:
        neutral = g.add_outcome([0, 0], label="neutral")
        g.set_outcome(g.root.children["H"], neutral)
    g.set_outcome(g.root.children["H"].children["h"], alice_win)
    g.set_outcome(g.root.children["T"].children["t"], alice_win)
    g.set_outcome(g.root.children["H"].children["t"], alice_lose)
    g.set_outcome(g.root.children["T"].children["h"], alice_lose)
    return g

g1 = create_MP()
g2 = create_MP(with_neutral_outcome=True)

for i in [0,1]:
    assert (g1.to_arrays()[i] == g2.to_arrays()[i]).all() 

print(gbt.nash.lp_solve(g1))
print(gbt.nash.lp_solve(g2))

print(gbt.nash.lcp_solve(g1))
print(gbt.nash.lcp_solve(g2))

From those solver calls we get for lp_solve:

NashComputationResult(method='lp', rational=True, use_strategic=False, equilibria=[[[[Rational(1, 2), Rational(1, 2)]], [[Rational(1, 2), Rational(1, 2)]]]], parameters={})

NashComputationResult(method='lp', rational=True, use_strategic=False, equilibria=[[[[Rational(1, 2), Rational(1, 2)]], [[Rational(1, 4), Rational(3, 4)]]]], parameters={})

and for lcp_solve:

NashComputationResult(method='lcp', rational=True, use_strategic=False, equilibria=[[[[Rational(1, 2), Rational(1, 2)]], [[Rational(1, 2), Rational(1, 2)]]]], parameters={'stop_after': 0, 'max_depth': 0})

NashComputationResult(method='lcp', rational=True, use_strategic=False, equilibria=[[[[Rational(0, 1), Rational(1, 1)]], [[Rational(1, 1), Rational(0, 1)]]]], parameters={'stop_after': 0, 'max_depth': 0})

The following more complicated example has the same problem (compared to tests/test_games/strippped_down_poker):

EFG 2 R "Stripped-Down Poker: a simple game of one-card poker from Reiley et al (2008)." { "Alice" "Bob" }
""

c "" 1 "" { "King" 1/2 "Queen" 1/2 } 1 "Ante" { -1, -1 }
p "" 1 1 "" { "Bet" "Fold" } 0
p "" 2 1 "" { "Call" "Fold" } 3 "Alice Bets" { -1, 0 }
t "" 6 "Bob Calls and Loses" { 4, -1 }
t "" 4 "Bob Folds" { 3, 0 }
t "" 2 "Alice Folds" { 0, 2 }
p "" 1 2 "" { "Bet" "Fold" } 0
p "" 2 1 "" { "Call" "Fold" } 3 "Alice Bets" { -1, 0 }
t "" 5 "Bob Calls and Wins" { 0, 3 }
t "" 4 "Bob Folds" { 3, 0 }
t "" 2 "Alice Folds" { 0, 2 }

However, note that the non-terminal outcomes have non-zero payoffs, so issue #498 is potentially relevant.