lemke howson algorithm result

Question

Qian Li 2022-5-2

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1709615-lemke-howson-algorithm-result

回答： Yash 2024-1-10

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?

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Yash 2024-1-10

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1709615-lemke-howson-algorithm-result#answer_1387241

在 MATLAB Online 中打开

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!