Is there a simple algorithm for computing mixed strategy Nash equilibria? For 2-player games < 20x20 say? Smells NP complete to me.
-
-
Replying to @vgr
let me see if I can sketch simplest algorithm in a set of tweets, perhaps number of tweets to describe is good measure of simplicity
1 reply 0 retweets 1 like -
The pure strategies in the support of the mixed strategy equilibria have maximal, and hence equal, expected payoff, for a player
1 reply 0 retweets 1 like -
This defines a se of linear equations and inequalities for the mixed strategy probabilities of the other player.
1 reply 0 retweets 1 like -
This is “best response polyhedron”. An equilibrium strategy of a player is a vertex (or convex comb.) of his best response polyhedron,.
1 reply 0 retweets 1 like -
Enumerate all pairs of vertices of the two best response polyhedra, check equilibrium property. This gives extreme equilibria of game.
1 reply 0 retweets 1 like -
It is still unknown if it is possible to do this efficiently in general, i.e., in time polynomial in both the input and output size.
1 reply 0 retweets 1 like -
for a 20x20 player game, you looking at ~ 40^10 vertices, which order of 1e16 checks you need to do.
2 replies 0 retweets 2 likes
Wow, thanks, an actual neat answer :D
-
-
Replying to @vgr
no problem, it was an interesting question, you make procrastinating on my thesis too easy.
0 replies 0 retweets 1 likeThanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.