Carlton Lemke's paper "Bimatrix Equilibrium Points and Mathematical Programming" presents a constructive proof of the existence of solutions for systems of the form $ Mz - w = q $, $ z \geq 0 $, $ w \geq 0 $, and $ z^T w = 0 $, which includes quadratic programming and bimatrix game equilibrium problems. The paper introduces a general algorithm for these problems by generating an adjacent extreme-point path that leads to a solution under non-degeneracy assumptions. This path is not based on successive approximation and terminates at an equilibrium point when one exists.
The paper discusses the existence of equilibrium points in bimatrix games and quadratic programming problems, showing that the set of equilibrium points is the set of endpoints of adjacency paths. It also extends the class of problems for which an adjacent extreme-point path scheme leads to a solution. The paper provides a theorem showing that if a set Z is non-degenerate and has exactly one ray, it has an odd number of equilibrium points. Another theorem states that if Z is non-degenerate and M is non-negative definite, there is at most one equilibrium point.
The paper also discusses the computational aspects of these results, noting that adjacent extreme-point algorithms are well-known and that details of computation may be omitted. It compares its formulation with that of Dantzig and Cottle, showing that the results extend previous findings. The paper concludes with a theorem stating that if Z is non-empty and non-degenerate, and M is non-negative definite, then Z has at least n rays. This result is illustrated with an example from linear programming.Carlton Lemke's paper "Bimatrix Equilibrium Points and Mathematical Programming" presents a constructive proof of the existence of solutions for systems of the form $ Mz - w = q $, $ z \geq 0 $, $ w \geq 0 $, and $ z^T w = 0 $, which includes quadratic programming and bimatrix game equilibrium problems. The paper introduces a general algorithm for these problems by generating an adjacent extreme-point path that leads to a solution under non-degeneracy assumptions. This path is not based on successive approximation and terminates at an equilibrium point when one exists.
The paper discusses the existence of equilibrium points in bimatrix games and quadratic programming problems, showing that the set of equilibrium points is the set of endpoints of adjacency paths. It also extends the class of problems for which an adjacent extreme-point path scheme leads to a solution. The paper provides a theorem showing that if a set Z is non-degenerate and has exactly one ray, it has an odd number of equilibrium points. Another theorem states that if Z is non-degenerate and M is non-negative definite, there is at most one equilibrium point.
The paper also discusses the computational aspects of these results, noting that adjacent extreme-point algorithms are well-known and that details of computation may be omitted. It compares its formulation with that of Dantzig and Cottle, showing that the results extend previous findings. The paper concludes with a theorem stating that if Z is non-empty and non-degenerate, and M is non-negative definite, then Z has at least n rays. This result is illustrated with an example from linear programming.