2-Player

In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy. As an algorithmic problem, given the payoff matrices for a bimatrix game, determine a Nash equilibrium.

Parameters

$m,n$ : dimensions of payoff matrices

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 2 of 2 algorithms

				See more
Lipton; Mehta	2003	$O(n^{O(\log n/\epsilon^2)}$	$O(\log^2(n)/\epsilon^2)$
Lemke–Howson algorithm	1964	$2^{O(n+m)}$	$O(mn)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms