Gambit: Software Tools for Game Theory | ||
---|---|---|
<<< Previous | Reference: Algorithms to Compute Nash Equilibria | Next >>> |
Finds Nash equilibria via the Lyapunov function method described in [McK91]. Works on either the extensive or normal form. This algorithm casts the problem as a function minimization problem by use of a Lyapunov function for Nash equilibria. This is a continuously differentiable non negative function whose zeros coincide with the set of Nash equilibria of the game. A standard descent algorithm is used to find a constrained local minimum of the function from any given starting location. Since a local minimum need not be a global minimum (with value 0), the algorithm is not guaranteed to find a Nash equilibrium from any fixed starting point. The algorithm thus incorporates the capability of restarting. The algorithm starts from the initial starting point determined by the parameter start. If a Nash equilibrium is not found, it will keep searching from new randomly chosen starting points until a Nash equilibrium has been found or the maximum number of tries is exceeded, whichever comes first. For an extensive form game, if the algorithm converges, it converges to a sequential equilibrium [1]
![]() | The disadvantages of this method are that it is generally slower than any of the above methods, and also, there can be local minima to the Liapunov function which are not zeros of the function. Thus the algorithm can potentially converge to a non Nash point. However, inspection of the objective function can determine if this problem has occurred. If the objective function is zero, a Nash equilibrium has been found. If it is greater than zero, the point is not Nash. The algorithm will automatically check this. If the objective function is larger than the tolerance, then the point is discarded. |
The following parameters can be set; \begin{description} \item[nTries:] Sets the maximum number of attempts at finding each equilibrium. Note that a value of 0 means the algorithm will continue forever, or until the algorithm is terminated by the user, whichever comes first. \item[start:] Sets the starting profile for the descent algorithm. {\bf Default} is the centroid. \end{description}
[1] | Andrew Solnick, personal communication to Richard McKelvey |
<<< Previous | Home | Next >>> |
LcpSolve | Up | LpSolve |