lemke howson algorithm result

5 views (last 30 days)
Qian Li
Qian Li on 2 May 2022
Answered: Yash on 10 Jan 2024
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?

Answers (1)

Yash
Yash on 10 Jan 2024
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!

Categories

Find more on Strategy & Logic in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!