Equilibrium tracing in strategic-form games

Balthasar, Anne
January 2010
Economic Theory;Jan2010, Vol. 42 Issue 1, p39
Academic Journal
We analyze the relationships of the van den Elzen–Talman algorithm, the Lemke–Howson algorithm and the global Newton method for equilibrium computation by Govindan and Wilson. For two-player games, all three can be implemented as complementary pivoting algorithms. The algorithms by Lemke and Howson and by van den Elzen and Talman start at a pair of strategies: the first method at a pure strategy and its best reply, the latter anywhere in the strategy space. However, we show that even with the same starting point they may find different equilibria. Our second result is that the van den Elzen–Talman algorithm is a special case of the global Newton method, which was known only for the Lemke–Howson algorithm. More generally, the global Newton method implements the linear tracing procedure for any number of players. All three algorithms find generically only equilibria of positive index. Even though the van den Elzen–Talman algorithm is extremely flexible in the choice of starting point, we show that there are generic coordination games where the completely mixed equilibrium, which has positive index, is generically not found by the algorithm.


Related Articles

  • APPLICATION OF TAYLOR-NEWTON HOMOTOPY METHOD FOR SOLVING ELECTRICAL ENGINEERING DESIGN PROBLEM. Hashim Hasan, Talib; Azram, Mohammed; Ibrahim Daoua, Jamal // AIP Conference Proceedings;8/18/2009, Vol. 1159 Issue 1, p92 

    We describe simple implementations of homotopy (also called continuation) algorithm for determining the proper resistor to dissipate energy at a specified rate of an electric circuit. Homotopy algorithm can be considered as a developing of the classical methods in numerical computing such as...

  • The Application of Homotopy Method In Solving Electrical Circuit Design Problem. Hasan, Talib Hashim // Proceedings of World Academy of Science: Engineering & Technolog; 

    This paper describes simple implementation of homotopy (also called continuation) algorithm for determining the proper resistance of the resistor to dissipate energy at a specified rate of an electric circuit. Homotopy algorithm can be considered as a developing of the classical methods in...

  • GETTING TO REAL-TIME LOAD-FLOW. Llopis-Rivas, Regina // Electric Perspectives;Jan/Feb2003, Vol. 28 Issue 1, p73 

    Discusses the application of non-linear equations solving algorithms based on the Newton-Raphson method to analyze the behavior of electrical power system. Definition of Newton-Raphson method; History of the method; Forecast of the North American Electrical Reliability Council on transmission...

  • An efficient power flow algorithm for distribution systems with polynomial load. Jianwei Liu; Salama, M.M.A.; Mansour, R.R. // International Journal of Electrical Engineering Education;Oct2002, Vol. 39 Issue 4, p371 

    A new, efficient power flow algorithm for complex distribution systems is presented. Voltage ratio is used for convergence control. This method has fast convergence ability for the polynomial load model for which the traditional Newton-Raphson method is usually not adaptable. Test results show...

  • A NEWTON-TYPE ALGORITHM FOR THE SOLUTION OF THE IMPLICIT PROGRAMMING PROBLEM. Feinstein, C.D.; Loren, S.S. // Mathematics of Operations Research;Feb84, Vol. 9 Issue 1, p75 

    A second-order algorithm is presented for the solution of the implicit programming problem. The implicit programming problem is a mathematical programming problem that has as its solution the optimal steady-states of an optimal control problem defined on an infinite horizon. The algorithm is...

  • Global Convergence of a Class of Collinear Scaling Algorithms with Inexact Line Searches on Convex Functions. Ariyawansa, K. A.; Begashaw, N. // Computing;1999, Vol. 63 Issue 2, p145 

    Ariyawansa [2] has presented a class of collinear scaling algorithms for unconstrained minimization. A certain family of algorithms contained in this class may be considered as an extension of quasi-Newton methods with the Broyden family [11] of approximants of the objective function Hessian....

  • ON THE EFFICIENCY OF NEWTON'S METHOD IN APPROXIMATING ALL ZEROS OF A SYSTEM OF COMPLEX POLYNOMIALS. Renegar, J. // Mathematics of Operations Research;Feb87, Vol. 12 Issue 1, p121 

    This paper studies the efficiency of an algorithm based on Newton's method is approximating all zeros of a system of polynomials f = (f[sub 1], f[sub 2],..., f[sub n]): C[sup n] → C[sup n]. The criteria for a successful approximation y of a zero w of f include the following: given ε >...

  • Forward Kinematics Analysis of a 3-PRS Parallel Manipulator. Abbasnejad, Ghasem; Zarkandi, Soheil; Imani, Misagh // World Academy of Science, Engineering & Technology;Jan2010, Issue 37, p329 

    In this article the homotopy continuation method (HCM) to solve the forward kinematic problem of the 3-PRS parallel manipulator is used. Since there are many difficulties in solving the system of nonlinear equations in kinematics of manipulators, the numerical solutions like Newton-Raphson are...

  • HOMOTOPY CURVE TRACKING FOR TOTAL VARIATION IMAGE RESTORATION. Fenlin Yang; Ke Chen; Bo Yu // Journal of Computational Mathematics;Mar2012, Vol. 30 Issue 2, p177 

    The total variation (TV) minimization problem is widely studied in image restoration. Although many alternative methods have been proposed for its solution, the Newton method remains not usable for the primal formulation due to no convergence. A previous study by Chan, Zhou and Chan [15]...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics