Venkatesh Rao@vgr·Jun 25, 2016Is there a simple algorithm for computing mixed strategy Nash equilibria? For 2-player games < 20x20 say? Smells NP complete to me.313
nikete@nikete·Jun 25, 2016Replying to @vgrlet me see if I can sketch simplest algorithm in a set of tweets, perhaps number of tweets to describe is good measure of simplicity11
nikete@nikete·Jun 25, 2016Replying to @nikete and @vgrThe pure strategies in the support of the mixed strategy equilibria have maximal, and hence equal, expected payoff, for a player11
nikete@nikete·Jun 25, 2016Replying to @nikete and @vgrThis defines a se of linear equations and inequalities for the mixed strategy probabilities of the other player.11
nikete@nikete·Jun 25, 2016Replying to @nikete and @vgrThis is “best response polyhedron”. An equilibrium strategy of a player is a vertex (or convex comb.) of his best response polyhedron,.11
nikete@nikete·Jun 25, 2016Replying to @nikete and @vgrEnumerate all pairs of vertices of the two best response polyhedra, check equilibrium property. This gives extreme equilibria of game.11
nikete@nikete·Jun 25, 2016Replying to @nikete and @vgrIt 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.11
nikete@nikete·Jun 25, 2016Replying to @nikete and @vgrfor a 20x20 player game, you looking at ~ 40^10 vertices, which order of 1e16 checks you need to do.22
Venkatesh Rao@vgrReplying to @niketeWow, thanks, an actual neat answer :D11:28 PM · Jun 25, 20161 Like
nikete@nikete·Jun 26, 2016Replying to @vgrno problem, it was an interesting question, you make procrastinating on my thesis too easy.1