Unexpected behavior - no equilibrium for a simple game

[omerbp]

Hi,

I discovered that support_enumeration fails to find a mixed NE for the following game (the list is empty). Is it a well known issue?
`
import nash
import numpy as np
M = [[ 0., 1., -0., -1.],
[-1., 0., 1., 1.],
[ 0., -1., 0., 1.],
[ 1., -1., -1., 0.]]

rps = nash.Game(M)
print(rps)
eqs = list(rps.support_enumeration())
print(eqs)
`

[drvinceknight]

Hi @omerbp yup, that's expected behaviour, the game you've got there is degenerate: the row player's 2nd and 3rd strategies are both best responses to the final strategy (final column). The support enumeration algorithm implemented here is specifically for non degenerate games so it only considers supports of the same size: https://nashpy.readthedocs.io/en/stable/reference/support-enumeration.html?highlight=degenerate

This is to reduce inefficiency of checking all potential supports.

[omerbp]

Great, makes sense. As a user, I would expect to get a message/warning notifying me that the game is degenerate and is therefore left untreated.

Thanks a lot!

[drvinceknight]

As a user, I would expect to get a message/warning notifying me that the game is degenerate and is therefore left untreated.

A test for degeneracy itself is not a trivial thing to do (it's essentially as "hard" as computing the equilibria but I've got an issue up to think about adding such a test: #20), another option would be to allow a user to pass a flag to support_enumeration to allow it to consider supports of unequal length. I'll think about that :)

I'm guessing you found this already but if you use vertex_enumeration you get a set of equilibria.

Thanks for the issue and I hope you find the library useful (if you use it I'd love to know about it 👍).

[drvinceknight]

@omerbp for your information I have updated the library (the latest release is version 0.0.16) and it now support enumeration handles degeneracy in a hopefully more understandable way. This is the behaviour with your game:

>>> import nashpy as nash
>>> import numpy as np
>>> M = [[ 0., 1., -0., -1.],
...            [-1., 0., 1., 1.],
...            [ 0., -1., 0., 1.],
...            [ 1., -1., -1., 0.]]
>>> game = nash.Game(M)
>>> list(game.support_enumeration())
[(array([  3.33333333e-01,   3.33333333e-01,   2.77555756e-17,
           3.33333333e-01]),
  array([  3.33333333e-01,   3.33333333e-01,   2.77555756e-17,
           3.33333333e-01]))]

There is some information about this here: https://nashpy.readthedocs.io/en/v0.0.15/reference/degenerate-games.html