You are currently browsing the monthly archive for April 2014.

In 1937, representatives of the Plywood trust called upon Comrade Professor Leonid Vitalievich Kantorovich with a problem. The trust produced 5 varieties of plywood using 8 different machines. How, they asked, should they allocate their limited supply of raw materials to the various machines so as to produce the maximum output of plywood in the required proportions? As problems go, it was, from this remove unremarkable. Remarkable is that the Comrade Professor agreed to take it on. The so called representatives might have been NKVD. Why? Uncle Joe’s first act upon taking power in 1929 was to purge the economists, or more precisely the Jewish ones. This was well before the purge of the communist party in 1936. Why the economists? They complained about waste in a planned economy dizzy with success.’ Yet, here were the apparatchiks of the Trust asking the Comrade Professor to reduce waste.

Kantorovich writes, that at the time he was burnt out by pure mathematics. Combined with a concern at the rise of Hitler, he felt compelled to do something practical. And, so he turned his mind to the problem of the Plywood Trust. Frances Spufford, in his delightful work of faction’ called Red Plenty, imagines what Kantorovich might have been thinking.

He had thought about ways to distinguish between better answers and worse answers to questions which had no right answer. He had seen a method which could do what the detective work of conventional algebra could not, in situations like the one the Plywood Trust described, and would trick impossibility into disclosing useful knowledge. The method depended on measuring each machine’s output of one plywood in terms of all the other plywoods it could have made.

If he was right — and he was sure he was, in essentials — then anyone applying the new method to any production situation in the huge family of situations resembling the one at the Plywood Trust, should be able to count on a measureable percentage improvement in the quantity of product they got from a given amount of raw materials. Or you could put that the other way around: they would make a measureable percentage saving on the raw materials they needed to make a given amount of product.

He didn’t know yet what sort of percentage he was talking about, but just suppose it was 3%. It might not sound like much, only a marginal gain, an abstemious eking out of a little bit more from the production process, at a time when all the newspapers showed miners ripping into fat mountains of solid metal, and the output of plants booming 50%, 75%, 150%. But it was predictable. You could count on the extra 3% year after year. Above all it was free. It would come merely by organising a little differently the tasks people were doing already. It was 3% of extra order snatched out of the grasp of entropy. In the face of the patched and mended cosmos, always crumbling of its own accord, always trying to fall down, it built; it gained 3% more of what humanity wanted, free and clear, just as a reward for thought. Moreover, he thought, its applications did not stop with individual factories, with getting 3% more plywood, or 3% more gun barrels, or 3% more wardrobes. If you could maximise, minimise, optimise the collection of machines at the Plywood Trust, why couldn’t you optimise a collection of factories, treating each of them, one level further up, as an equation? You could tune a factory, then tune a group of factories, till they hummed, till they purred. And that meant —

An english description of Kantorovich’s appeared in the July 1960 issue of Management Science. The opening line of the paper is:

The immense tasks laid down in the plan for the third Five Year Plan period require that we achieve the highest possible production on the basis of the optimum utilization of the existing reserves of industry: materials, labor and equipment.

The paper contains a formulation of the Plywood Trust’s problem as a linear program. A recognition of the existence of an optimal solution at an extreme point as well as the hopelessness of enumerating extreme as a solution method. Kantorovich then goes on to propose his method, which he calls the method of resolving multipliers. Essentially, Kantorovich proposes that one solve the dual and then use complementary slackness to recover the primal. One might wonder how Kantorovich’s contribution differs from the contributions of Koopmans and Dantzig. That is another story and as fair a description of the issues as I know can be found in Roy Gardner’s 1990 piece in the Journal of Economic Literature. I reproduce one choice remark:

Thus, the situation of Kantorovich is rather like that of the discoverer Columbus. He really never touched the American mainland, and he didn’t give its name, but he was the first one in the area.

As an aside, David Gale is the one often forgotten in this discussion. If the Nobel committee has awarded the prize for Linear Programming, Dantzig and Gale would have been included. Had Gale lived long enough, he might have won it again for matching making him the third to have won the prize twice in the same subject. The others are John Bardeen and Frederick Sanger.

Continuing with Spufford’s imaginings:

— and that meant that you could surely apply the method to the entire Soviet economy, he thought. He could see that this would not be possible under capitalism, where all the factories had separate owners, locked in wasteful competition with one another. There, nobody was in a position to think systematically. The capitalists would not be willing to share information about their operations; what would be in it for them? That was why capitalism was blind, why it groped and blundered. It was like an organism without a brain. But here it was possible to plan for the whole system at once. The economy was a clean sheet of paper on which reason was writing. So why not optimise it? All he would have to do was to persuade the appropriate authorities to listen.

Implementation of Kantorovich’s solution at the Plywood trust led to success. Inspired, Kantorovich sent a letter to Gosplan urging adoption of his methods. Here the fact that Kantorovich solved the dual first rather than the primal is important. Kantorovich interpreted his resolving multipliers (shadow prices today) as objectively determined prices. Kantorovich’s letter to Gosplan urged a replacement of the price system in place by his resolving multipliers. Kantorovich intended to implement optimal production plans through appropriate pieces. Gosplan, responded that reform was unecessary. Kantorovich narrowly missed a trip to the Gulag and stopped practicing Economics, for a while. Readers wanting a fuller sense of what mathematical life was like in this period should consult this piece by G. G. Lorentz.

After the war, Kantorovich took up linear programming again. At Lenningrad, he headed a team to reduce scrap metal produced at the Egorov railroad-car plant. The resulting reduction in waste reduced the supply of scrap iron for steel mills disrupting their production! Kantorovich escaped punishment by the Leningrad regional party because of his work on atomic reactors.

Kantorovich’s interpretation of resolving multipliers which he renamed as objectively determined valuations put him at odds with the prevailing labor theory of value. In the post Stalin era, he was criticized for being under the sway of Bohm-Bawerk, author of the notion of subjective utility. Aron Katsenelinboigen, relates a joke played by one of these critics on Kantorovich. A production problem was presented to Kantorovich where the labor supply constraint would be slack at optimality. Its objectively determined valuation’ was therefore zero, contradicting the labor theory of value.

Nevertheless, Kantorovich survived. This last verse from the Ballard of L. V. Kantorvich authored by Josph Lakhman explains why:

Then came a big scholar with a solution.
Alas, too clever a solution.
Objectively determined valuations’-
That’s the panacea for each and every doubt!
Truth be told, the scholar got his knukcles rapped
Slightly rapped
That threatened to overturn the existing order.
After some thought, however, the conclusion was reached
That the valuations had been undervalued

This is the first of a series of posts about stability and equilibrium in trading networks. I will review and recall established results from network flows and point out how they immediately yield results about equilibria, stability and the core of matching markets with quasi-linear utility. It presumes familiarity with optimization and the recent spate of papers on matchings with contracts.

The simplest trading network one might imagine would involve buyers (${B}$) and sellers (${S}$) of a homogenous good and a set of edges ${E}$ between them. No edges between sellers and no edges between buyers. The absence of an edge in ${E}$ linking ${i \in B}$ and ${j \in S}$ means that ${i}$ and ${j}$ cannot trade directly. Suppose buyer ${i \in B}$ has a constant marginal value of ${v_i}$ upto some amount ${d_i}$ and zero thereafter. Seller ${j \in S}$ has a constant marginal cost of ${c_j}$ upto some capacity ${s_j}$ and infinity thereafter.

Under the quasi-linear assumption, the problem of finding the efficient set of trades to execute can be formulated as a linear program. Let ${x_{ij}}$ for ${(i,j) \in E}$ denote the amount of the good purchased by buyer ${i \in B}$ from seller ${j \in S}$. Then, the following program identifies the efficient allocation:

$\displaystyle \max \sum_{(i,j) \in E} (v_i - c_j)x_{ij}$

subject to

$\displaystyle \sum_{j \in S: (i,j) \in E}x_{ij} \leq d_i\,\, \forall i \in B$

$\displaystyle \sum_{i \in B:(i,j) \in E}x_{ij} \leq s_j\,\, \forall j \in S$

$\displaystyle x_{ij} \geq 0\,\, (i,j) \in E$

This is, of course, an instance of the (discrete) transportation problem. The general version of the transportation problem can be obtained by replacing each coefficient of the objective function by arbitrary numbers ${w_{ij}}$. This version of the transportation problem is credited to the mathematician F. J. Hitchcock and published in 1941. Hitchcock’s most famous student is Claude Shannon.

The continuous’ version of the transportation problem was formulated by Gaspard Monge and described in his 1781 paper on the subject. His problem was to split two equally large volumes (representing the initial location and the final location of the earth to be shipped) into infinitely many small particles and then match them with each other so that the sum of the products of the lengths of the paths used by the particles and the volume of the particles is minimized. The ${w_{ij}}$‘s in Monge’s problem have a property since called the Monge property, that is the same as submodularity/supermodularity. This paper describes the property and some of its algorithmic implications. Monge’s formulation was subsequently picked up by Kantorovich and the study of it blossomed into the specialty now called optimal transport with applications to PDEs and concentration of measure. That is not the thread I will follow here.

Returning to the Hitchcock, or rather discrete, formulation of the transportation problem let ${p_j}$ be the dual variables associated with the first set of constraints (the supply side) and ${\lambda_i}$ the dual variables associated with the second or demand set of constraints. The dual is

$\displaystyle \min \sum_{j \in S} s_jp_j + \sum_{i \in B}d_i\lambda_i$

subject to

$\displaystyle p_j + \lambda_i \geq [v_i-c_j]\,\, \forall (i,j) \in E$

$\displaystyle p_j, \lambda_i \geq 0\,\, \forall j \in S, i \in B$

We can interpret ${p_j}$ as the unit price of the good sourced from seller ${j}$ and ${\lambda_i}$ as the surplus that buyer ${i}$ will enjoy at prices ${\{p_j\}_{j \in S}}$. Three things are immediate from the duality theorem, complementary slackness and dual feasibility.

1. If ${x^*}$ is a solution to the primal and ${(p^*, \lambda^*)}$ an optimal solution to the dual, then, the pair ${(x^*, p^*)}$ form a Walrasian equilibrium.
2. The set of optimal dual prices, i.e., Walrasian prices live in a lattice.
3. The dual is a (compact) representation of the TU (transferable utility) core of the co-operative game associated with this economy.
4. Suppose the only bilateral contracts we allow between buyer ${i}$ and seller ${j}$ are when ${(i,j) \in E}$. Furthermore, a contract can specify only a quantity to be shipped and price to be paid. Then, we can interpret the set of optimal primal and dual solutions to be the set of contracts that cannot be blocked (suitably defined) by any buyer seller pair ${(i,j) \in E}$.
5. Because the constraint matrix of the transportation problem is totally unimodular, the previous statements hold even if the goods are indivisible.

As these are standard, I will not reprove them here. Note also, that none of these conclusions depend upon the particular form of the coefficients in the objective function of the primal. We could replace ${[v_i - c_j]}$ by ${w_{ij}}$ where we interpret ${w_{ij}}$ to be the joint gain gains from trade (per unit) to be shared by buyer ${i}$ and seller ${j}$.

Now, suppose we replace constant marginal values by increasing concave utility functions, ${\{U_i(\cdot)\}_{i \in B}}$ and constant marginal costs by ${\{C_j (\cdot)\}_{j \in S}}$? The problem of finding the efficient allocation becomes:

$\displaystyle \max \sum_{i \in B}U_i(\sum_{j: (i,j) \in E}x_{ij}) - \sum_{j \in S}C_j(\sum_{i: (i,j) \in E}x_{ij})$

subject to

$\displaystyle \sum_{j \in S: (i,j) \in E}x_{ij} \leq d_i\,\, \forall i \in B$

$\displaystyle \sum_{i \in B:(i,j) \in E}x_{ij} \leq s_j\,\, \forall j \in S$

$\displaystyle x_{ij} \geq 0\,\, (i,j) \in E$

This is an instance of a concave flow problem. The Kuhn-Tucker-Karush conditions yield the following:

1. If ${x^*}$ is a solution to the primal and ${(p^*, \lambda^*)}$ an optimal Lagrangean, then, the pair ${(x^*, p^*)}$ form a Walrasian equilibrium.
2. The set of optimal Lagrange prices, i.e., Walrasian prices live in a lattice.
3. Suppose the only bilateral contracts we allow between buyer ${i}$ and seller ${j}$ are when ${(i,j) \in E}$. Furthermore, a contract can specify only a quantity to be shipped and price to be paid. Then, we can interpret the set of optimal primal and dual solutions to be the set of contracts that cannot be blocked (suitably defined) by any buyer seller pair ${(i,j) \in E}$.

Notice, we lose the extension to indivisibility. As the objective function in the primal is now concave, an optimal solution to the primal may occur in the interior of the feasible region rather than at an extreme point. To recover integrality’ we need to impose a stronger condition on ${\{U_i\}_{i \in B}}$ and ${\{C_j\}_{j \in S}}$, specifically, they be ${M}$-concave and convex respectively. This is a condition tied closely to the gross substitutes condition. More on this in a subsequent post.

Ezra Klein, one among the chattering classes recently posted a summary of graduation speech given by Thomas Sargent to Berkeley economics undergraduates in 2007. Sargent prefaced his remarks with these words:

I will economize on words.

Lets see how well he succeeded:

Economics is organized common sense. Here is a short list of valuable lessons that our beautiful subject teaches.

1. Many things that are desirable are not feasible.

2. Individuals and communities face trade-offs.

3. Other people have more information about their abilities, their efforts, and their preferences than you do.

4. Everyone responds to incentives, including people you want to help. That is why social safety nets don’t always end up working as intended.

Everything after the comma is superfluous. Why emphasize the bit about people you want to help? Why choose to emphasize the business of safety nets? He could just as well have said: That is why markets don’t always end up working as intended.

5. There are tradeoffs between equality and efficiency.

Redundant given items 1 and 2 above. It also implies a commonly accepted definition of equality and efficiency.

6. In an equilibrium of a game or an economy, people are satisfied with their choices. That is why it is difficult for well meaning outsiders to change things for better or worse.

Wrong. Within the constraints of the game they may be satisfied with the outcome. It does not follow they are satisfied with the game they were obliged to play.

7. In the future, you too will respond to incentives. That is why there are some promises that you’d like to make but can’t. No one will believe those promises because they know that later it will not be in your interest to deliver. The lesson here is this: before you make a promise, think about whether you will want to keep it if and when your circumstances change.
This is how you earn a reputation.

He garbled this one by confusing the desire to make promises and whether they are credible. Here is an edit with fewer words.

Promises about tomorrow are easy to make, but because you will respond to incentives in the future they are hard to keep. Its even harder to convince others that you will keep them. Before you make a promise, think about whether you will want to keep it if and when your circumstances change. This is how you earn a reputation.

8. Governments and voters respond to incentives too. That is why governments sometimes default on loans and other promises that they have made.

Redundant given item 4 above.

9. It is feasible for one generation to shift costs to subsequent ones. That is what national government debts and the U.S. social security system do (but not the social security system of Singapore).

Item in brackets clearly redundant, but what is a bully pulpit for unless one get one’s licks in!

10. When a government spends, its citizens eventually pay, either today or tomorrow, either through explicit taxes or implicit ones like inflation.

11. Most people want other people to pay for public goods and government transfers (especially transfers to themselves).

12. Because market prices aggregate traders’ information, it is difficult to forecast stock prices and interest rates and exchange rates.

Rests on a supposition that some might find arguable. Conclusion might still follow. Perhaps, a simple you can’t beat the market without an unfair advantage’ might suffice.

Now compare with Yoram Baumann’s translation of Mankiw’s ten principles of economics:

#3. People are stupid.
#4. People aren’t that stupid.
#5. Trade can make everyone worse off.
#6. Governments are stupid.
#7. Governments aren’t that stupid.
#8. Blah blah blah.
#9. Blah blah blah.
#10. Blah blah blah.