[Bug]: enumpoly returns a profile with undefined probabilities that may not be a Nash eq

[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?

This was spotted when working on issue #636, which is about using UndefinedToCentroid rather than leaving probabilities at certain infosets as 0 in pygambit, or *s in the GUI. In making that change I noticed the following case (currently incorrectly included as a test case in test_enumpoly_ordered_behavior in test_nash.py).

The game in question is the "one-shot trust game", created in tests/games.py::create_one_shot_trust_efg, with the following efg file:

EFG 2 R "One-shot trust game, after Kreps (1990)" { "Buyer" "Seller" }
""

p "" 1 1 "" { "Trust" "Not trust" } 0
p "" 2 1 "" { "Honor" "Abuse" } 0
t "" 1 "Trustworthy" { 1, 1 }
t "" 2 "Untrustworthy" { -1, 2 }
t "" 3 "Opt-out" { 0, 0 }

The issue is that the second "equilibrium" found by enum_poly in mixed behaviors is not always an equilibrium:

import pygambit as gbt
g = gbt.read_efg('one_shot_trust.efg')
result = gbt.nash.enumpoly_solve(g)
print(result.equilibria[0])
print(result.equilibria[1])

giving

In [14]: print(result.equilibria[0])
[[[0.0, 1.0]], [[0.5, 0.5]]]

In [15]: print(result.equilibria[1])
[[[0.0, 1.0]], [[0.0, 0.0]]]

The second once should have [0.0, 1.0] for player 2, but is instead returned as "undefined", i.e. [0.0, 0.0] in pygambit, and wildcards * in the GUI:

However, if player 2 puts more than 0.5 probability on "Honor" then "No Trust" is no longer a best response for player 1.

Player 2's info set is only one deviation from the equilibrium path (i.e. "Not Trust"), and so actually should have specified probabilities and not be undefined (which should occur only for info sets that would only be reached with deviations of more than one player).

[rahulsavani]

Once we deal with issue #636 we will no longer have fully zero probs at an info set.

Still, we should consider what if anything we want to do about the fact that max_regret (which is currently the agent version for behavior profiles, but that is somewhat separate) is being computed as zero on result.equilibria[1].

[rahulsavani]

Here's the trace with supports:

./gambit-enumpoly -V one_shot_trust.efg
Compute Nash equilibria by solving polynomial systems
Gambit version 16.4.0, Copyright (C) 1994-2025, The Gambit Project
This is free software, distributed under the GNU GPL

candidate,11,11
NE,0.000000,1.000000,0.500000,0.500000
candidate,11,10
candidate,11,01
candidate,10,11
candidate,10,10
candidate,10,01
candidate,01,00
NE,0.000000,1.000000,0.000000,0.000000

Notes:

• We enumerate action supports -- we very possibly want to be enumerating sequence supports, but this needs thought.
• With the current approach what is happening is that for the player 1 "01" support, we never reach player'2 info set and then player 2 has no equations for what they do.
• To fix this current approach, we would need an "extend to Nash" step, which would look at pure distributions over action at unreachable infosets and try to fill them in and create a Nash.
• We had a "extend to Nash" in an older version of the code that was not being called. It was very possibly intended to solve this issue.

[rahulsavani]

@tturocy: One thing that is not completely clear is why "candidate,11,01" doesn't return anything (namely [[0,1],[0,1]]), given that "candidate,11,11' return [0,1] for player 1.

[tturocy]

[[0, 1], [0, 1]] doesn't solve the indifference equation for player 1. If player 2 plays [0, 1], player 1 is not indifferent between his actions. For 11,11 player 1 is indifferent because player 2 randomises [.5, .5].

[rahulsavani]

Yes, clear, bit of a silly question really. Clearly indifference among everything the full support is required by the equations and it would make not sense to allow indifference only over a subset of things in the support. That the returned action probabilities need not use the full support is also natural enough (with them presumably encoded by weak inequalities), and is required for true indifference for player 2 in the 11,11 case.

In this 11,11 case, indifference is enough for being best responses too. Since we don't have extensive tests for this method, I looked at some variants of the game above with an extra option of player 1 at the root with various payoffs to player 1. Everything seemed fine in terms of not getting back erroneous equilibria when player 1 has 3 actions at the root, the candidate support for player 1 is over two actions, player 1 can be made indifferent over these two, but the 3rd action not in the support gives a better payoff. From the examples I have looked at, I believe the notes in the comment above capture well the full issue as we currently understand it.