Feature request: Nash equilibrium with maximal entropy

[WenjieZ]

Nash equilibria are not unique. Currently, the package returns a list of equilibria to handle this problem. However, this becomes troublesome when the game is degenerate.

It would be better if the package provides an option to return the one with maximal entropy, which is unique and has a better interpretability.

PS. Thanks for this easy-to-use package!

[drvinceknight]

PS. Thanks for this easy-to-use package!

My pleasure and thanks for the suggestion!

It would be better if the package provides an option to return the one with maximal entropy, which is unique and has a better interpretability.

Would this be equivalent to maximising the entropy over the set of all equilibria? In which case perhaps there's no need to implement anything as it would correspond to:

>>> def entropy(eq):
... # code to compute entropy
>>> eqs = list(game.support_enumeration())
>>> max(eqs, key=entropy)

I'm not overly familiar with this though so please do correct me if my assumption is incorrect (and links to references would be great).

[WenjieZ]

Would this be equivalent to maximising the entropy over the set of all equilibria?

No, not as simple. When the payoff matrix is degenerate (e.g., there are two rows or columns identical), there exists an infinite number of equilibria, and anything between two equilibria is also an equilibrium. See Example 1 in this paper (Page 6) for an example.

Currently your solution gives only the extremities, which has the least entropy, while the maximal entropy sits at the middle of all extremities. Indeed, each extremity has a preference on one strategy, whereas the maximal entropy one is indifferent to any equally well strategy.

Concerning the usefulness, please see Proposition 4 (Page 6) of the above paper for a discussion.

[WenjieZ]

By the way, I am running your package on a 200x200 payoff matrix. Do you have any idea how long it will take?

[WenjieZ]

Also see this: Maximum entropy correlated equilibrium

[drvinceknight]

Thanks for the update, the library really doesn't handle degeneracy at all so I'll read through those papers with interest.

By the way, I am running your package on a 200x200 payoff matrix. Do you have any idea how long it will take?

Depending on the algorithm that would almost certainly take too long. If a single equilibria is sufficient I'd suggest you use the Lemke-Howson algorithm. https://nashpy.readthedocs.io/en/stable/how-to/solve-with-lemke-howson.html

[WenjieZ]

Thanks for the suggestion! The Lemke-Howson algorithm finished instantly on my 200x200 matrix and produced the same result as my hand-coded solver. I suspect that my problem has a single equilibrium, so this works for me. Thanks again :)

[drvinceknight]

Fantastic to hear that :)