Static And Dynamic Games

The

linear complementarity problem has been successfully applied to option pricing. The

problem has undergone several name changes, from composite problem, to fundamental

problem, to complementary pivot problem. The current name linear complementarity

problem was proposed by Cottle [15, p. 37]. The linear complementarity problems are

found in the first-order optimality conditions of quadratic programming. Probably the

earliest publication containing an explicitly stated linear complementarity problem is

one by Du Val (1940)[24] in algebraic geometry.

The algorithm presented by Lemke and Howson [72] to compute an equilibrium

pair 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 complementarity

problem and in some instances of the problem may terminate inconclusively without

either 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 and

iterative. 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 possible

as it depends on the problem data, mostly on the matrix class to which the matrix

M belongs. Iterative method is used in case of a large scale linear complementarity

problem 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 a

linear complementarity problem and it has attracted lots of attention to game theory

community. Another pivoting algorithm called pincipal pivoting method(PPM) for

LCPs can be found in Cottle and Dantzig