Conversation

Is there a simple algorithm for computing mixed strategy Nash equilibria? For 2-player games < 20x20 say? Smells NP complete to me.
3
3
Replying to
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
1
Replying to and
The pure strategies in the support of the mixed strategy equilibria have maximal, and hence equal, expected payoff, for a player
1
1
Replying to and
This is “best response polyhedron”. An equilibrium strategy of a player is a vertex (or convex comb.) of his best response polyhedron,.
1
1
Replying to and
Enumerate all pairs of vertices of the two best response polyhedra, check equilibrium property. This gives extreme equilibria of game.
1
1
Replying to and
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
1