The Choice Of Technique As A Linear Complementarity Problem

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

x_i ≥ 0, for i = 1, 2, ..., k

z_i ≥ 0, for i = 1, 2, ..., k

x_i z_i = 0, for i = 1, 2, ..., k

The last condition can be specified as the condition that the vector dot product x^T z must be equal to zero. (x^T 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.

q_i ≥ 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) A^T p + a₀^T ≥ B^T 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:

p_i ≥ 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:

p^T [(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:

[p^T(B - (1 + r) A) - a₀] 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 x^T 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.