1.0 Introduction
Linear Complementarity Problems (LCPs) have well-known algorithms (as least known by others)
to solve them. Of particular interest to me is the Lemke algorithm. I think Christian
Bidard or Guido Erreygers was the first to point out that the Lemke algorithm applies
to economics in this way. But I do not know they ever specify the details in this post.
I often need to step through what others find obvious to understand something.
2.0 The Linear Complementarity Problem (LCP)
Table 1: Parameters and Variables for the LCP
| Symbol | Type | Definition |
| k | Parameter | Problem size, known as the order of the LCP. |
| M | Parameter | A k x k matrix. |
| u | Parameter | A k-element column vector. |
| x | Variable | A k-element non-negative column vector. |
| z | Variable | A k-element non-negative column vector. |
This section specifies the LCP. Let M be a given k x k matrix
and u a given k-element column vector (Table 1).
Find the
k-element column vectors x and z such that:
x - M z = u
xi ≥ 0, for i = 1, 2, ..., k
zi ≥ 0, for i = 1, 2, ..., k
xi zi = 0, for i = 1, 2, ..., k
The last condition can be specified as the condition that the vector
dot product xT z must be equal to zero.
(xT is the tranpose of x.)
3.0 The Problem Of The Choice of Technique
I now specify inequalities and equalities (for duality conditions) that
specify the problem of finding a cost-minizing solution in the analysis of the choice of technique.
Table 2 defines the given parameters for this problem.
Table 3 defines the vectors to be found.
Technology and final demand is taken as given.
Given the rate of profits, the level of operation of each process in the technology and the price of each produced commodity is determined
by the solution, when a solution exists and is unique.
Table 2: Parameters for a Cost-Minimizing Technique
| Symbol | Definition |
| n | The number of produced commodities. |
| m | The number of processes, m ≥ n. |
| A | The n x m input matrix. |
| a0 | The m-element row vector of direct labor coefficients. |
| B | The n x m output matrix. |
| y | The n-element column vector of net output, also known as final demand. |
| r | The rate of profits. |
Table 3: Variables for a Cost-Minimizing Technique
| Symbol | Definition |
| q | A m-element non-negative column vector. The level of operation of each process. |
| p | A n-element non-negative column vector. The price of each produced commodity. |
The net output must meet or exceed the specified final demand:
B q - A q ≥ y
A vector is greater than or equal to another if and only if each element of the first is
greater than or equal to another. Each process must be operated at a non-negative level.
qi ≥ 0, for i = 1, 2, ..., m
The above non-negativity conditions complete the specification of the quantity system.
The specification of the price system starts with the following system of inequalities:
(1 + r) AT p + a0T ≥ BT p
The cost of each process cannot fall below the revenues obtained by that process.
Labor is paid out of the surplus at the end of the production period.
Each price must be non-negative:
pi ≥ 0, for i = 1, 2, ..., n
In this specification, a person-year of labor is the numeraire.
I turn to duality conditions.
The law of free goods states that any commodity in excess supply has a price of zero.
It can be stated as the following equality:
pT [(B - A) q - y] = 0
The law of non-operated processes asserts that any process in which the cost exceeds revenues
is not operated. It is stated like so:
[pT(B - (1 + r) A) - a0] q = 0
A (cost-minimizing) solution of the above systems of equalities and inequalities is a long-period position.
The prices are prices of production.
4.0 Mapping the Choice of Technique to a LCP
The main inequality in the quantity system can be converted to equality by subtracting excess supplies from
the left hand side (LHS). Some manipulation yields the equation in Figure 1. Notice that the two vectors
on the LHS in Figure 1 are non-negative. The matrices and the vector on the RHS side are part of the
data when finding a cost-minimization system.
|
| Figure 1: Quantity System as an Equality |
The same approach can be adopted for the main inequality in the price system. Here I introduce a vector of extra costs for
each process. The result is shown in Figure 2.
|
| Figure 2: Price System as an Equality |
Two vectors are found in the solution of a LCP. The above suggests that k = n + m is the order
of the LCP in which I am interested. Figure 3 specifies the other vector in the solution for the LCP in terms of the
vectors to be found in finding a cost-minizing solution.
|
| Figure 3: One Solution Vector in the LCP as Price and Quantity Vectors for Cost-Minimization |
Figure 4 specifies the vector taken as a parameter in the LCP.
Figure 5 specifies the matrix.
|
| Figure 4: The Given Vector in the LCP for the Cost-Minimization Problem |
|
| Figure 5: The Given Matrix in the LCP for the Cost-Minimization Problem |
With the mapping shown, the problem of finding a cost-minimizing solution to the problem of the choice of technique
is now a LCP. The condition that xT z must be zero incorporates both the rule of free goods
and the law of non-operated processes.
5.0 Conclusion
Solving a LCP provides a solution to a linear program. In this formulation, duality considerations apprently enter.
I have seen and even published an article, in 2005, with a LP formulation of the analysis of the choice of technique.
Does the LCP formulation yield the same LP?
Above, the LCP is for a model of general joint production. I suppose that I could explicitly formulate the LCP to
consider the theory of rent. I do not think that any difficulties arise here, at least as far as setting up the
problem. Erreygers (1995) and Kurz and Salvadori (1995) provide an approach.
Can I find some way of illustrating a LCP by partitioning a low-dimensional parameter or solution space for
some small problem? Can I actually step through the Lemke algorithm for a small problem?
References
- Erreygers, Guido. 1995. On the uniqueness of cost-minimizing techniques. The Manchester School 63: 145-166.
- Murty, Katta G. 1997. Linear Complementarity Linear and Nonlinear Pogramming
- Lemke, Carlton. 1965. Bimatrix Equilibrium Points and Mathematical Programming. Management Science 11(7): 681-689.