Add is_degenerate for bimatrix games

[ameliekleber]

This feature request is for...

Other

Requested enahancement or feature

Add a is_degenerate check for 2-player games, similar to SageMath's implementation:

is_degenerate(certificate=False)[source]
A function to check whether the game is degenerate or not.

Will return a boolean.

A two-player game is called nondegenerate if no mixed strategy of support size
has more than
pure best responses [NN2007]. In a degenerate game, this definition is violated, for example if there is a pure strategy that has two pure best responses.

The implementation here transforms the search over mixed strategies to a search over supports which is a discrete search. A full explanation of this is given in [CK2015]. This problem is known to be NP-Hard [Du2009]. Another possible implementation is via best response polytopes, see Issue #18958.

[UveysAlsalehi]

Hello, sorry for the delay, and thank you for your patience. I've finished a draft implementation. I did it in a similar way to SageMath.

The problem is NP-hard. Basically I check every pair of supports (S, T) to see whether there exists a mixed strategy whose support is S and for which the opponent's best responses are exactly T. The size of S is k and T is k+1 — so the opponent having k+1 best responses to a size-k support is what makes the game degenerate. To check each pair I solve a linear feasibility problem (an LP) using scipy.optimize.linprog.

Before opening a pull request I wanted to check a few things:

1. Would it be acceptable to use a scipy function? (It would add scipy as a dependency.)
2. Should I define a custom error instead of ValueError for non-two-player games? (SageMath raises NotImplementedError.)

[rahulsavani]

Hi Uveys: Thanks for your patience -- we've been busy getting Gambit 17 ready. It's not in beta in case you want to check it out.

1. Yes, the problem is NP-hard and your approach is sensible. However, scipy.optimize.linprog is floating point only. For Gambit, we need this in exact arithmetic as we need always correct answers. We are happy with a new python dependency and for exact LP solving via a python wrapper we have used: https://pypi.org/project/pycddlib/. Feel free to use that or suggest an alternative. BTW, we have a Gambit-own solver in C++ but it is slow and doing this all in python for now is a good idea.

2. A NotImplementedError would be good here, just as in SageMath. We certainly have one at the C++ level, so let's go with this at the pygambit level too.

[rahulsavani]

P.S. doing this all in python would allow us to create a good test suite of both degenerate and non-degenerate games and perhaps later convert is_degenerate to a C++ based method, with that test suite already in place.