In a 2 person, constant sum game, all NE strategies have identical payoff, the 'value' of the game. Typically this is calculated by first calculating one NE strategy.
In many algorithms for enumerating NE of a bimatrix game, we assume that the game is nondegenerate. For example, the simplest algorithm I know of, support enumeration, requires this hypothesis.
What is the simplest algorithm to calculate the payoff that discards this hypothesis?
Best Answer
Yes we can using a modification to the Lemke-Howson algorithm. Normally when running the Lemke-Howson algorithm in tableau form on a non degenerate game, in each iteration there is a unique variable that wins the minimum-ratio test. In the degenerate game we will be faced with the problem of breaking ties and if we have a bad tie-breaking rule the program can end up running forever. The approach used, instead of the basic minimum-ratio test, is called the lexicographic minimum ratio test. In the article Equilibrium points of bimatrix games by Lemke and Howson they describe this under lexicographic method. There is also a description of this in chapter three of the book Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vaziran.
The simplest algorithm for any game though would be given a tie during the solving procedure. To break it, choose randomly and if we later come back to the same case, then break the tie in a different way.