Paul Cockshott's Blog

Comments on economics and politics

Returning to Kantorovich

In this post I focus on recovering the work of Kantorovich the only Soviet Economic Nobelist, and on showing that his work provided a fundamental theoretical response to the Austrian school economist von Mises. Kantorovich was an eminent mathematician, whose work went well beyond economics, but in this article we focus only on his economic contributions. In explaining these I reproduce in section some of his original numerical examples drawn from his experience in Soviet heavy industry. I give what is essentially a tutorial introduction to using the lp-solve package to solve planning problems. I summarise what these mathematical techniques mean in practical terms. What type of economic problem do they allow us to solve?

As illustrations I show how Kantorovich allows us to pose problems of national or continental environmental trade-offs.

In Section 3 and beyond I provide a detailed commented source listing of a programme I have written that applies Kantorovich’s method to economic planning problems specified as spreadsheets in csv format. The programme is available in source and in Linux binary format from the folder at the following link. 

Documentation of the programme is provided in the full version of this post, linked to at the end.

With this programme you can experiment with macroeconomic planning problems. You need an input output matrix for an economy and a set of initial resources and a vector of plan objectives – what Kantorovich called a planray. It will then print Kantrovich’s objective valuations and the achievable gross output given the available resources.

The illustrations I give in the course of the post rely on the open source linear programming package lp-solve which is available for all Linux systems. I also provide my own programme in order to show the technique used by Kantorovich and to provide the Objective Valuations that he suggested be used in socialist calculation.

In the process of developing this programme I found that there were certain limitations to the Kantorovich’s own technique for deriving ODVs when you applied them to data in input output table format. I have therefore introduced some changes to his technique which are described in section .

1  Kantorovich’s method

In the early 30s, no algorithmic techniques were known which would solve the general problem of socialist calculation where there can be joint production and multiple possible techniques to produce individual products. But in 1939 ] the Soviet mathematician V Kantorovich came up with a method which later came to be known as linear programming or linear optimisation, for which he was later awarded both Stalin and Nobel prizes. Describing his discovery he wrote:

I discovered that a whole range of problems of the most diverse character relating to the scientific organization of production (questions of the optimum distribution of the work of machines and mechanisms, the minimization of scrap, the best utilization of raw materials and local materials, fuel, transportation, and so on) lead to the formulation of a single group of mathematical problems (extremal problems). These problems are not directly comparable to problems considered in mathematical analysis. It is more correct to say that they are formally similar, and even turn out to be formally very simple, but the process of solving them with which one is faced [i.e., by mathematical analysis] is practically completely unusable, since it requires the solution of tens of thousands or even millions of systems of equations for completion.

I have succeeded in finding a comparatively simple general method of solving this group of problems which is applicable to all the problems I have mentioned, and is sufficiently simple and effective for their solution to be made completely achievable under practical conditions. (], p. 368)

 

Table 1: Kantorovich’s first example.
Type of machine # machines output per machine Total output
As Bs As Bs
Milling machines 3 10 20 30 60
Turret lathes 3 20 30 60 90
Automatic turret lathes 1 30 80 30 80
Max total 120 230

What was significant about Kantorovich’s work was that he showed that it was possible, starting out from a description in purely physical terms of the various production techniques available, to use a determinate mathematical procedure to determine which combination of techniques will best meet plan targets. He indirectly challenged von Mises1, both by proving that in-natura calculation is possible, and by showing that there can be a non monetary scalar objective function : the degree to which plan targets are met.

The practical problems with which he was concerned came up whilst working in the plywood industry. He wanted to determine the most effective way of utilising a set of machines to maximise output. Suppose we are making a final product that requires two components, an A and a B. Altogether these must be supplied in equal numbers. We also have three types of machines whose productivities are shown in the Table 1.

Suppose we set each machine to produce equal numbers of As and Bs. The three milling machines can produce 30 As per hour or 60 Bs per hour. If the three machines produce As for 40 mins in the hour and Bs for 20 mins then they can produce 20 of each. Applying similar divisions of time we can produce 36 As and Bs on the Turret lathes and 21 As and Bs on the automatic turret lathe (Table ).

But Kantorovich goes on to show that this assignment of machines is not the best. If we assign the automatic lathe to producing only Bs, the turret lathe to producing only As and split the time of the milling machines so that they spend 6 mins per hour producing Bs and the rest producing As, the total output per hour rises from 77 As and Bs to 86 As and Bs.

Table 2: Kantorovich’s examples of output assignments.
Type of machine Simple solution Best solution
As Bs As Bs
Milling machines 20 20 26 6
Turret lathes 36 36 60 0
Automatic turret lathes 21 21 0 80
Total 77 77 86 86

The key concept here is that each machine should be preferentially assigned to producing the part for which it is relatively most efficient. The relative efficiency of producing As/Bs of the three machines was milling machine =[1/2], turret lathes =[2/3] , and automatic lathe =[3/8]. Clearly the turret lathe is relatively most efficient at producing As, the automatic lathe is relatively most efficient at producing Bs and the milling machine stands in between. Thus the automatic lathe is set to produce only Bs, the turret lathes to make only As and the time of the milling machines is split so as to ensure that an equal number of each product is turned out.

 kantor1

 

#1Kantorovich’s example as a diagram . The plan ray is the locus all points where the output of As equals the output of Bs. The production possibility frontier is made of straight line segments whose slopes represent the relative productivities of the various machines for the two products. As a whole these make a polygon. The plan objective is best met where the plan ray intersects the boundary of this polygon.

The decision process is shown diagrammatically in Figure 1. The key to the construction of the diagram, and to the decision algorithm is to rank the machines in order of their relative productivities. If one does this, one obtains a convex polygon whose line segments represent the different machines. The slopes of the line segments are the relative productivities of the machines. One starts out on the left with the machine that is relatively best at producing Bs, then move through the machines in descending order of relative productivity. Because relative productivity is monotonically decreasing one is guaranteed that the boundary will be convex. One then computes the intersection of the 45 degree line representing equal output of As and Bs with the boundary of this polygon. This intersection point is the optimal way of meeting the plan. The term linear programming stems from the fact that the production functions are represented by straight lines in the case of 2 products, planes for 3 products, and for the general higher dimensional case by linear functions. That is to say, functions in which variables only appear raised to the power 1.

The slope of the boundary where the plan ray intersects was called by Kantorovich the resolving ratio. Any machine whose slope is less than this should be assigned to produce Bs any machine whose slope is greater, should be assigned to produce As.

When there are only two products being considered, the method is easy and lends itself to diagrammatic representation. But it can handle problems of higher dimensions, involving 3 or more products. In these cases we can not use graphical solutions, but Kantorovich provided an algorithmic by which the resolving ratios for different pairs of outputs could be arrived at by successive approximations. Kantorovich’s work was unknown outside of the USSR until the late 50s and prior to that Dantzig had independently developed a similar algorithm for solving linear programming problems, the so called simplex method ]. This has subsequently been incorporated into freely available software tools2. These packages allow you to enter the problem as a set of linear equations or linear inequalities which they then solve.

In the West, linear programming was used to optimise the use of production facilities operating within a capitalist market. This meant that the objective function that was maximised was not a fixed mix of outputs, in Kantorovich’s first example equal numbers of parts A and B, but the money that would be obtained from selling the output: price A ×number of As + price B ×number of Bs. Manuals and textbooks produced in association with Western linear programming software assumes this sort of objective. However, as we shall see, one can readily formulate Kantorovich’s problem using this sort of software by adding additional equations. We shall now show how you can use the package lp_solve to reproduce Kantorovich’s solution to his problem.

A;

m1<=3;

m2<=3;

m3<=1;

A-B=0;

m1-0.1 x1a - 0.05 x1b=0;

m2-0.05 x2a - 0.033333 x2b=0;

m3- 0.033333 x3a - 0.0125 x3b=0;

x1a+x2a+x3a - A=0;

x1b+x2b+x3b -B =0;

int A;
 

#1Kantorovich’s example as equations input to lp_solve. .

The program requires that you input an expression to be maximised or minimised followed by a sequence of equations or inequalities. In Algorithm 1 we give Kantorovich’s problem in the format that lp_solve requires. In this example we use the following variables:

variable meaning
A number of units of A produced
B number of units of B produced
m1 number of milling machines used
m2 number of turret lathes used
m3 number of automatic turret lathes used
xij number of units of j produced on machine i

Thus x1a means the output of As on milling machines.

The first line of input is the objective function to be maximised. We give this as A, meaning maximise the output of A’s. The following lines give the constraints to which the maximisation process is to be subjected.

A-B=0
 
 
This is another way of writing that A=B, or that equal quantities of A and B must be produced.
m1<=3
 
 
This means that the number of milling machines used must be less than or equal to 3. The characters ‘<‘ ‘=’ are used because ≤ is not available on computer keyboards. Similar constraints are provided for the other machines.
m1-0.1x1a-0.05x1b=0
 
 
This specifies m1=0.1x1a+0.05x1b=[1/10]x1a+[1/20]x1b or in words, that allocating a milling machine to produce an A uses [1/10] of a milling machine hour, and that allocating a milling machine to produce a unit of B uses [1/20] of a milling machine hour. We provide similar production equations for the other machines.
x1a+x2a+x3a
- A=0
 
This says that the total output of A is equal to the sum of the outputs of A from each of the machines. We provide a similar equation defining the output of B.

Note that all equations have to be provided with variables and constants on the left and a constant on the right. One can readily re-arrange the equations in this form. The last line specifies that the number of units of A produced should be an integer. When the equations are input to lp_solve it produces the answer:

Value~of~objective~function:~86

Actual~values~of~the~variables:

A          86

B          86

x1a         26

x1b         6

x2a         60

x2b         0

x3a         0

x3b         80

m1          2.9

m2          3

m3          1 

which exactly reproduces Kantorovich’s own solution (Table 2) arrived at using his algorithm.

1.1  Generalising Kantorovich’s approach

In his first example Kantorovich deals with a very simple problem, producing two goods in equal proportions using a small set of machines. He was aware, even in 1939 that the potential applications of mathematical planning were much wider. We will look at two issues that he considered which are important for the more general application of the method.

  1. Producing outputs in a definite ratio rather than in strictly equal quantities.
  2. Taking into account consumption of raw materials and other inputs.

Suppose that instead of wanting to produce one unit of A for every unit of B, as might be the case if we were matching car engines to car bodies, we want to produce 4 units of A for every unit of B, as would be the case if we were matching wheels to car engines ( and ignoring spare wheels). Can Kantorovich’s method deal with this as well. Consider Figure 1 again. In that the plan ray is shown at an angle of 45° a slope of 1 to 1. If we drew the plan ray at a slope of 4 to 1, the intersection with the production frontier would provide the solution. Since this geometric approach only works for two products, let us consider the algebraic implications.

You should now be convinced that it is possible to solve Kantorovich’s original problem3 by algebraic means. In Algorithm 1 we specified that A−B=0 or in other words A=B , if one wanted 4 units of A for every B we would have to specify A=4B or, expressing it in the standard form used in linear optimisation, A−4B=0 . Suppose A stands for engines, B stands for wheels. If we now say wheels come in packs of 4, then we can repose the problem in terms of producing equal numbers of packs of wheels and engines. Introduce a new variable β = 4B to stand for packs of wheels, and rewrite the equations in terms of β and we can return to an equation specifying the output mix in the form A−β = 0, which we know to be soluble.

How do we deal with consumption of raw materials or intermediate products?

In our previous example we had variables like x1b which stood for the output of product B on machine 1. This was always a positive quantity. Suppose that there is a third good to be considered – electricity, and that each machine consumes electricity at different rate depending on what it is turning out. Call electricity C and introduce new variables x1ac, x1bc etc referring to how much electricity is consumed by machine 1 producing outputs A and B. Then add equations specifying how much electricity is consumed by each machine doing each task, and the model will specify the total amount of electricity consumed.

We now know how to :

  1. Use Kantorovich’s approach to specify that outputs must be produced in a definite ratios.
  2. Use it to take into account consumption of raw materials and other inputs.

If we can do these two tasks, we can in principle perform in-natura calculations for an entire planned economy. Given a final output bundle of consumer and investment goods to maximise and given our current resources, a system of linear equations and inequalities can be solved to yield the structure of the plan. From simple beginnings, optimising the output of plywood on different machines, Kantorovich had come up with a mathematical approach which could be extended to the problem of optimising the operation of the economy as a whole.

1.2  A second example

Let us consider a more complicated example, where we have to draw up a plan for a simple economy. We imagine an economy that produces three outputs : energy, food, and machines. The production uses labour, wind and river power, and two types of land: fertile valley land, and poorer highlands. If we build dams to tap hydro power, some fertile land is flooded. Wind power on the other hand, can be produced on hilly land without compromising its use for agriculture. We want to draw up a plan that will make the most rational use of our scarce resources of people, rivers and land.

In order to plan rationally, we must know what the composition of the final output is to be – Kantorovich’s ray. For simplicity we will assume that final consumption is to be made up of food and energy, and that we want to consume these in the ratio 3 units of food per unit of energy. We also need to provide equations relating to the productivities of our various technologies and the total resources available to us.

Valleys are more fertile. When we grow food in a valleys, each valley requires 10,000 workers and 1000 machines and 20,000 units of energy to produce 50,000 units of food. If we grow food on high land, then each area of high land produces only 20,000 units of food using 10,000 workers, 800 machines and 10,000 units of energy.

Electricity can be produced in two ways. A dam produces 60000 units of energy, using one valley and 100 workers and 80 machines. A windmill produces 500 units of electricity, using 4 workers and 6 machines, but the land on which it is sited can still be used for farming.

We will assume that machine production uses 20 units of electricity and 10 workers per machine produced.

Finally we are constrained by the total workforce, which we shall assume to be 104,000 people.

Table 3: Variables in the example economy
e total energy output
ec household energy consumption
f food
v valleys
w windmills
m machines
d dams
u undammed valleys
h highland
fh food produced on high land
fv food produced in valleys
Table 4: Resource constraints and productivities in our example economy
final output mix f=3ec
number of valleys v=4
dams use valleys v−u=d
valley food output fv=50000u
valley farm labour lv=10000u
valley energy use ev=20000u
valley farm machines mv=1000u
highland food prod fh=20000h
highland farm labour lh=10000h
highland energy use eh=10000h
highland farm machines mh=800h
energy production e=500w+60000d
energy workers le=100d+4w
machines in energy prod me=80d+6w
workers making machines lm=10m
energy used to make machines em=20m
energy consumption em+ev+eh+ec ≤ e
machine use me+mh+mv ≤ m
total food prod f=fh+fv
workforce lm+le+lv+lh ≤ 104000

Tables 3 and 4 show how to express the constraints on the economy and the plan in equational form. If we feed these into lp_solve we obtain the plan shown in Table . The equation solver shows that the plan targets can best be met by building no dams, generating all electricity using 541 windmills, and devoting the river valleys to agriculture.

It also shows how labour should be best allocated between activities: 40000 people should be employed in agriculture in the valleys, 109 people should work as farmers in the highlands, 2164 people should work on energy production, and 61727 people should work building machines.

Table 5: Economic plan for the example economy using lp_solve
d (dams)       0
e         270500
f         200218
h        0.0108889
m        6172.71
u        4
v        4
w (windmills)        541
ec        66739.3
eh        108.889
em        123454
ev       80000
fh        217.778
fv        200000
le        2164
lh        108.889
lm        61727.1
lv        40000
me         2164
mh        8.71111
mv        4000

The results that we have obtained were by no means obvious at the outset. It was not initially clear that it would be better to use all the river valleys for agriculture rather than building dams on some of them. In fact, whether dams or windmills are preferred turns out to depend on the whole system, not just on their individual rates of producing electricity. We can illustrate this by considering what happens if we cut the labour supply in half to 52000 people?

If we feed this constraint in to the system of equations we find the optimal use of resources has changed. The plan now involves 1 dam and 159 windmills. Cut the working population slightly further, down to 50000 people and the optimal plan involves flooding two valleys with dams and building only 23 windmills. Why?

As the population is reduced, there are no longer enough people available to both farm the valleys and produce agricultural machinery. Under these circumstances the higher fertility of lowland valleys is of no importance, it is better to use one or more of them to generate electricity. By applying Kantorovich’s approach it becomes possible for a socialist plan to do two things that von Mises had believed impossible:

  1. It allows the plan to take into account natural resource constraints – in this case the shortage of land in river valleys which can be put to alternative uses.
  2. It allows rational choices to be made between different technologies – in this case between windmills and hydro power and between lowland and highland agriculture.

Contrary to what von Mises claimed, the whole calculation can be done in physical units without any recourse to money or to prices.

2  Valuation

The core of Mises’s argument relates to the use of prices to arrive at a rational use of intermediate or capital goods. Mises argues that, in practice, only money prices will do for this, but concedes that, in principle, other systems of valuation, such as labour values would also be applicable. Kantorovich too, was very concerned with the problem of relative valuation], and developed what he called objectively determined valuations (ODV). These valuations differed from prices, since a price involves an exchange of commodities for money between two owners. In the USSR all factories and all products were owned by the state. When products moved from one factory to another, there was no sale or purchase involved. The ODVs were purely notional numbers, used in economic calculations, not selling prices.

He considered a situation where planners have to deal with several different types of factories (A..E) each able to produce products 1 and 2, and where the intended ratio of output of product 1 and 2 are fixed in the plan. Each class of factory A..E has different relative productivities for the two products.

He next looked at the apparent profitability of producing products 1 and 2 under different relative valuations. Under some schemes of relative price, all factories would find product 1 to be unprofitable relative to product 2, under other the reverse would occur. Intermediate price schemes would allow both products to be produced, with some classes of factories specializing on 1 and others on 2. He gives the example of children’s clothing as something which, under the administratively determined valuations then used in the USSR, were unprofitable to produce, and unless factories were specifically instructed to ignore local profitability, too few children’s clothes would be made.

He asks if there exists a relative valuation structure which would allow factories to concentrate on the most valuable output, and at the same time meet the specified plan targets and arrives at certain conclusions:

  1. That among the very large number of possible plans there is always an optimal one which maximises output of plan goals with current resources.
  2. That in the optimal plan there exists a set objectively determined valuations (ODV) of goods which will ensure that each factory
    1. produces the output which will contribute most to maximising the plan goals
    2. each factory also finds that the output which contributes to maximising plan targets is also the output which is most profitable
  3. With arbitrary valuations which differ from ODV, these conditions can not be met, and profit maximising factories will not specialise in a way that meets plan goals optimally.

It is important to understand that his ODVs are valuations that apply only for a plan which optimally meets a specific plan target. Kantorovich’s procedure for arriving at an optimal plan involved successive adjustments to the ODVs and factory specialisation until both the appropriate mix of goods is reached, and at the same time each factory is producing its most profitable good. He actually gave several different mathematical procedures for arriving at such a plan and system of ODVs.

Although Kantorovich asserts that labour is ultimately the only source of value, his ODV’s are short term valuations and differ from the classical labour theory of value, which gave valuations in terms of the long term labour reproduction costs of goods – including the reproduction costs of capital goods. Kantorovich, in contrast, is concerned with valuations which should apply with the current stock of means of production and labour resources. For example, he considers the situation of giving a valuation to electric power relative to labour. Instead of valuing it in terms of the labour required to produce electricity, he first assumes that the total electrical power available is fixed – ie, power-stations operating at full capacity, and then works out how many person hours of labour is saved by using an additional kilowatt hour of electricity. The assumption is made that in order to arrive at this objective valuation of electricity in terms of labour

  1. The plan targets must be met
  2. The plan must be optimal

Kantorovich’s insistence on considering short term, very material constraints – so many megawatts of power, such and such a number of cutting machines, etc, gives his work an intensely practical and pragmatic character, quite different from that of most theoretical economists.

2.1  Alterations made to Kantorovich’s algorithm

Besides the alterations to the input data structures that I will describe in Section , I found that there were 3 other areas that needed improvement.

  1. Selection of a plan ray where the outputs produced are, unlike his soil example, unequal. This is easily dealt with by selecting units of measurement for the outputs so as to make all outputs equal. Thus if you were to need twice as much of soil A as soil B, you would express your volume of soil A in units of 2 cubic meters not 1 cubic meter. This can be effected by an appropriate predivision of the resource vector and the technology matrix.
  2. It was noticed that on certain problems the first phase of the algorithm to obtain resolving multipliers , fails to terminate. This turns out to be because all resources are allocated to the technique for which they are ‘best’ under the valuation given by the resolving multipliers. This greedy algorithm can result in the system never terminating under some circumstances. When a given technique uses multiple resources, as is typical with IO table examples, the system can get trapped in an oscillation in which all resources are allocated alternately to two disjoint set of techniques, leaving some goods un-produced. I altered this rule to one in which half of the available resources were allocated to the ‘best’ line of production, leaving some free for other techniques.
  3. Kantorovich’s optimisation procedure works very well for his own examples, but fails to converge for some input output table examples. I provide an option to use a different optimizer that also works on gradient descent, but with simulated annealing added. This proves more robust than Kantorovich’s method, albeit slower than his on the examples where his method works. You select which optimiser to use by setting the optimiser flag in the kantor library. For the programme objectiveValuation the flag is set to use my optimiser.

Since the rest of the post requires sophisticated typesetting I provide a link to a pdf version of the rest

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: