Static And Dynamic Games

Thelinear complementarity problem has been successfully applied to option pricing. Theproblem has undergone several name changes, from composite problem, to fundamentalproblem, to complementary pivot problem. The current name linear complementarityproblem was proposed by Cottle [15, p. 37]. The linear complementarity problems arefound in the first-order optimality conditions of quadratic programming. Probably theearliest publication containing an explicitly stated linear complementarity problem isone by Du Val (1940)[24] in algebraic geometry.The algorithm presented by Lemke and Howson [72] to compute an equilibriumpair of strategies to a bimatrix game, later extended by Lemke to solve an LCP(q, M)contributed significantly to the development of the linear complementarity theory.However, this algorithm does not solve every instance of the linear complementarityproblem and in some instances of the problem may terminate inconclusively withouteither computing a solution to it or showing that no solution to it exists.In fact there exists two major types of algorithms to solve LCPs: pivoting anditerative. The former one is of finite step algorithm where it transform the problem(q, M) into an equivalent form (q, M) in which q >= 0. But this is not always possibleas it depends on the problem data, mostly on the matrix class to which the matrixM belongs. Iterative method is used in case of a large scale linear complementarityproblem and the matrix is to be sparse(to have lesser number of nonzero elements)and structured. Lemke's algorithm [71] is a nice pivoting algorithm for solving alinear complementarity problem and it has attracted lots of attention to game theorycommunity. Another pivoting algorithm called pincipal pivoting method(PPM) forLCPs can be found in Cottle and Dantzig