lemke howson algorithm result

I am using the LemkeHowson package to compute mixed strategy equilibrium.

The payoff matrices are

A = [0,6;2,5;3,3];
B = [1,0;0,2;4,3];

Then I type this code to compute the equilibrium:

nashEqbm = LemkeHowson(A, B,1); 

(I change the 3rd argument from 1 to 5 according to the algorithm)

This game should have 3 equilibria: one pure strategy equilibrium ((0,0,1),(1,0)) and 2 mixed equilibria ((0,1/3,2/3),(2/3,1/3)), ((2/3,1/3,0),(1/3,2/3)).

But when I change the pivoting point from 1 to 5, I can only get 2 equilibria and always miss one mixed strategy equlibrium. I keep getting ((0,0,1),(1,0)) and ((2/3,1/3,0),(1/3,2/3)) but missing ((0,1/3,2/3),(2/3,1/3)).

Any idea on how to get all 3 equilibria of this game?

Answer 1

[Yash]

Hi Qian,

It seems that you are experiencing some issues with the Lemke-Howson algorithm when trying to compute all three equilibria for your game. One possible reason for this is that the algorithm might be getting stuck in a local minimum and not exploring all possible equilibria.

To overcome this issue, you can try running the algorithm multiple times with different initial pivoting points. By doing so, you increase the chances of finding all three equilibria. Here's an example of how you can modify your code to achieve this:

>> nashEqbm1 = LemkeHowson(A, B, 1);
>> nashEqbm2 = LemkeHowson(A, B, 5);
>> nashEqbm3 = LemkeHowson(A, B, 10);

By running the algorithm with different initial pivoting points (e.g., 1, 5, and 10), you increase the likelihood of finding all three equilibria.

Please note that the Lemke-Howson algorithm is not guaranteed to find all equilibria for every game. It is possible that for certain games, the algorithm may not converge to all equilibria. In such cases, you may need to consider alternative algorithms or approaches.

Hope this helps!