You are currently browsing the category archive for the ‘market design’ category.
Fox News and CNN have been in knots recently about how to allocate scarce debate slots to the many Republican pretenders to the oval office. Should Poll numbers be the criteria? What about gender, race, state office etc. etc. There is a simple and transparent way to allocate the slots: an auction. Neither CNN or Fox are charities. If the debates are a public good, there is no reason why Fox and CNN alone should forgo profits to host them. They should, instead auction off the rights to participate in the debates.
What design questions would have to be answered? First, how much time to allocate to the debate, i.e., what is the supply of the resource to be allocated? Second, should one auction slots or time. For example, should it be 10 slots of equal time lengths in a 2 hour time period? Or, should one allow the bidders to bid on the actual amount of time they would get in the 2 hour period? Are candidates the only ones allowed to bid, or can anyone submit bids on their behalf? Can one bid to deny time to the candidates? Actually, as these are not debates at all, but parallel news conference, perhaps one should auction off the right to answer questions. In real time. That would be entertainment!
Having caught your eye, I direct you to an article in the April 9, 2015 edition of the Grey Lady. It discusses attempts by various countries to boost domestic birthrates. The same issue had been considered earlier by Noah Smith. There are two questions lurking here. First, what is the optimal population size for a country? If the goal was to shrink the population then a declining birth rate is not a bad thing. Suppose the goal is keep the population fixed, because, say of pension obligations. Then, one wants a replacement birth rate of roughly 2 per couple.
If the birth rate is below the target, what should one do? Interestingly, I cannot recall anyone I have asked or read who does not turn to Government interventions of various kinds. Noah Smith, for example, only discusses Government interventions before concluding one should imitate the French. If the birth rate is below what is optimal for society, why doesn’t the market take care of it? Do we have a missing market? Is this a public goods problem? (If so, then, Mankiw who is often castigated for being a selfish beast, is, in this case, an unstinting provider of public goods, see here.)
Analogies are sometimes helpful (if biology is the study of bios, life; geology is the study of geos, earth, what does that make analogy?). Farmers plant crops and after a period, the fruits of their labor are harvested and sent to market. The Farmer must anticipate what will be demanded in the future to decide what to plant now. What if she plants turnips when what is desired are parsnips? This problem is solved with a futures market for parsnips (or turnips or pork etc). Why not a futures market for babies? Those who want warm bodies in the future to support them in their dotage pay for babies now. Swiftian, I know, but interesting to consider. Once one thinks about how to implement the idea, difficulties emerge. One might, for example, be concerned with moral hazard on the part of parents. However, these same difficulties are present even with various Government subsidies.
General equilibrium! Crown jewel of micro-economic theory. Arrow and Hahn give the best justification:
“There is by now a long and fairly imposing line of economists from Adam Smith to the present who have sought to show that a decentralized economy motivated by self-interest and guided by price signals would be compatible with a coherent disposition of economic resources that could be regarded, in a well defined sense, as superior to a large class of possible alternative dispositions. Moreover the price signals would operate in a way to establish this degree of coherence. It is important to understand how surprising this claim must be to anyone not exposed to the tradition. The immediate `common sense’ answer to the question `What will an economy motivated by individual greed and controlled by a very large number of different agents look like?’ is probably: There will be chaos. That quite a different answer has long been claimed true and has permeated the economic thinking of a large number of people who are in no way economists is itself sufficient ground for investigating it seriously. The proposition having been put forward and very seriously
entertained, it is important to know not only whether it is true, but whether it could be true.”
But how to make it come alive for my students? When first I came to this subject it was in furious debates over central planning vs. the market. Gosplan, the commanding heights, indicative planning were as familiar in our mouths as Harry the King, Bedford and Exeter, Warwick and Talbot, Salisbury and Gloucester….England, on the eve of a general election was poised to leave all this behind. The question, as posed by Arrow and Hahn, captured the essence of the matter.
Those times have passed, and I chose instead to motivate the simple exchange economy by posing the question of how a sharing economy might work. Starting with two agents endowed with a positive quantity of each of two goods, and given their utility functions, I asked for trades that would leave each of them better off. Not only did such trades exist, there were more than one. Which one to pick? What if there were many agents and many goods? Would bilateral trades suffice to find mutually beneficial trading opportunities? Tri-lateral? The point of this thought experiment was to show how in the absence of prices, mutually improving trades might be very hard to find.
Next, introduce prices, and compute demands. Observed that demands in this world could increase with prices and offered an explanation. Suggested that this put existence of market clearing prices in doubt. Somehow, in the context of example this all works out. Hand waved about intermediate value theorem before asserting existence in general.
On to the so what. Why should one prefer the outcomes obtained under a Walrasian equilibrium to other outcomes? Notion of Pareto optimality and first welfare theorem. Highlighted weakness of Pareto notion, but emphasized how little information each agent needed other than price, own preferences and endowment to determine what they would sell and consume. Amazingly, prices coordinate everyone’s actions. Yes, but how do we arrive at them? Noted and swept under the rug, why spoil a good story just yet?
Gasp! Did not cover Edgeworth boxes.
Went on to introduce production. Spent some time explaining why the factories had to be owned by the consumers. Owners must eat as well. However it also sets up an interesting circularity in that in small models, the employee of the factory is also the major consumer of its output! Its not often that a firm’s employers are also a major fraction of their consumers.
Closed with, how in Walrasian equilibrium, output is produced at minimum total cost. Snuck in the central planner, who solves the problem of finding the minimum cost production levels to meet a specified demand. Point out that we can implement the same solution using prices that come from the Lagrange multiplier of the central planners demand constraint. Ended by coming back full circle, why bother with prices, why not just let the central planner have his way?
It states that the Minkowski sum of a large number of sets is approximately convex. The clearest statement as well as the nicest proof I am familiar with is due to J. W. S. Cassels. Cassels is a distinguished number theorist who for many years taught the mathematical economics course in the Tripos. The lecture notes are available in a slender book now published by Cambridge University Press.
This central limit like quality of the lemma is well beyond the capacity of a hewer of wood like myself. I prefer the more prosaic version.
Let be a collection of sets in with . Denote by the Minkowski sum of the collection . Then, every can be expressed as where for all and .
How might this be useful? Let be an 0-1 matrix and with . Consider the problem
Let be a solution to the linear relaxation of this problem. Then, the lemma yields the existence of a 0-1 vector such that and . One can get a bound in terms of Euclidean distance as well.
How does one do this? Denote each column of the matrix by and let . Let . Because and it follows that . Thus, by the Lemma,
where each and . In words, has at most fractional components. Now construct a 0-1 vector from as follows. If , set . If is fractional, round upto 1 with probability and down to zero otherwise. Observe that and the . Hence, there must exist a 0-1 vector with the claimed properties.
The error bound of is to large for many applications. This is a consequence of the generality of the lemma. It makes no use of any structure encoded in the matrix. For example, suppose were an extreme point and a totally unimodular matrix. Then, the number of fractional components of $x^*$ are zero. The rounding methods of Kiralyi, Lau and Singh as well as of Kumar, Marathe, Parthasarthy and Srinivasan exploit the structure of the matrix. In fact both use an idea that one can find in Cassel’s paper. I’ll follow the treatment in Kumar et. al.
As before we start with . For convenience suppose for all . As as has more columns then rows, there must be a non-zero vector in the kernel of , i.e., . Consider and . For and sufficiently small, for all . Increase and until the first time at least one component of and is in . Next select the vector with probability or the vector with probability . Call the vector selected .
Now . Furthermore, has at least one more integer component than . Let . Let be the matrix consisting only of the columns in and consist only of the components of in . Consider the system . As long as has more columns then rows we can repeat the same argument as above. This iterative procedure gives us the same rounding result as the Lemma. However, one can do better, because it may be that even when the number of columns of the matrix is less than the number of rows, the system may be under-determined and therefore the null space is non-empty.
In a sequel, I’ll describe an optimization version of the Lemma that was implicit in Starr’s 1969 Econometrica paper on equilibria in economies with non-convexities.
Something funny happened when I started watching Al Roth’s lecture and looked at the paper: I realized that what I always assumed is the meaning of `repugnant transactions’ is not exactly the phenomena that Roth talks about. What I thought `repugnant transaction’ means is a situation of `two rights makes a wrong': it’s totally awesome that Xanders is willing to donate his extra kidney to Zordiac, and it’s really nice of Zordiac to donate money to Xanders, but these two nobles acts done together in exchange for each other is imoral and should be outlawed. Roth however defines `repugnant transaction’ more broadly as any transaction that some people want to engage in and others don’t think they should.
Consider the opening example of his paper: laws against selling horse meat in restaurants. Here what is repugnant is not the exchange but the good itself. It’s not two rights makes wrong. It’s just wrong. We outlaw the exchange simply because of constitutional reasons or because it’s impossible to enforce a ban on eating — people will simply order take away and perform the crime of eating at their homes.
So let me offer a distinction between `repugnant exchanges’, where the good itself is fine but buying and selling it is repugnant and `repugnant good/services’ where the good or service are what is repugnant, even if for whatever reason what we actually outlaw is the transaction. Most of the examples that Roth gives fall into the `repugnant good/service’ category rather than `repugnant exchange’. Such is the case of buying and selling recreational drugs, endangered species, imported cultural property.
Are there any examples for `repugnant exchanges’ in addition to selling human organs ? Well, there is `renting’ organs, as in surrogate motherhood. Anything else ? An interesting example is lending money with interest, which used to be repugnant in the West (we got over it already): The very idea of lending money was never considered repugnant. What was repugnant is doing it for payment in terms of interest.
Finally, there is prostitution, which is illegal in the US. Repugnant service or repugnant exchange ? depends on your reasoning. Anti-prostitution laws have an unlikely coalition of supporters. There are the religious moralists, for whom the service (extra-marriage sexual intercourse) is what makes the transaction repugnant. They go for prostitution just because that’s what they can outlaw in the US. (They go further in Iran.) But there are also feminists and liberals who view prostitution as exploitation, as I view selling human organs. They find the exchange repugnant even if they have no problem with the service itself.
Note that the example of prostitution shows the difficulty in the distinction I make between `repugnant good/service’ and `repugnant exchange': It relies on unobservable reasoning. Just by knowing the laws and customs of a society you don’t know to which category a forbidden transaction belongs. Moreover, since different people may have different reasoning, the category is sometimes not uniquely defined. But I still think it’s a useful distinction.
In my salad days, school masters would assign boys returning from the summer hols an essay: `What I did during the summer’. Yes, masters and boys. I served a portion of my youth in a `misbegotten penal colony upon a wind blasted heath’. The only females present were master’s wives, matrons and the French mistress. No, not that kind, the kind that offers instruction in French. As you can see, to the lascivious minds of boys, there was no end to the double entendres. However, I digress.
The National Resident Matching program strives for a stable matching of medical students to teaching hospitals. With the presence of couples, stable matchings need not exist. For any student preferences, we show that each instance of a stable matching problem has a `nearby’ instance with a stable matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Specifically, given a reported capacity for each hospital , we find a redistribution of the slot capacities satisfying for all hospitals and , such that a stable matching exists with respect to . Our approach is general and applies to other type of complementarities, as well as matchings with side constraints and contracts.
In other words, with the addition of at most 9 additional slots, one can guarantee the existence of a stable matchings. This is independent of the size of the market or doctors preferences (it does assume responsive preferences on the part of hospitals). The key tool is Scarf’s lemma which is a wonderful device for converting results about cardinal matching problems into results about ordinal matching problems. For more on this, consult the paper by Kiralyi and Pap, who should be credited with a formulation of Scarf’s lemma that makes its usefulness evident.
Here is Al Roth’s talk in the Lindau Meeting on Economic Sciences about repugnant transactions, which I guess is the technical term for the discomfort I feel at the idea of people donating their extra kidney to those who need it in return to, you know, money.
Before he was a Nobel Laureate Roth was a Nancy L. Schwartz Memorial Lecturer. His talk was about kidney exchanges — these are exchanges between several pairs of donor+recipient involving no money but only kidneys — and he started with a survey of the audience: who is in favor of allowing selling and buying of kidneys in the free market ? (I am glad I didn’t raise my hand. The next question was about selling and buying of living hearts.) I remember noticing that there was a correlation between raised hands and seniority: For whatever reason, seniors were more likely to be in favor of the free market than juniors.
In the dinner after the talk I ended up in a table of juniors & spouses and we got to discuss our objection to the idea of letting Bob sell his Kidney to Alice, so that Bob can afford to send his daughter to college, and in doing so save Alice’s small child from orphanhood. Turned out we agreed on the policy but for different reasons. I don’t remember which was my reason. I still find both of them convincing, though less so simultaneously.
Reason I: The market price would be too low. Hungry people will compete selling their organs for a bowl of red pottage out of desperation. The slippery slope leads to poor people being harvested for their body parts.
Reason II: The market price would be too high. Only the 0.01 % will be able to afford it. The slippery slope leads to a small aristocracy who live forever by regenerating their bodies.
As I said, both (somewhat) convincing. And please don’t ask me what would be the fair price, that is neither too low nor too high.
Over a lunch of burgers and envy, Mallesh Pai and discussed an odd feature of medical reidencies. This post is a summary of that discussion. It began with this question: Who should pay for the apprenticeship portion of a Doctor’s training? In the US, the apprenticeship, residency, is covered by Medicare. This was `enshrined’ in the 1965 act that established Medicare:
Educational activities enhance the quality of care in an institution, and it is intended, until the community undertakes to bear such education costs in some other way, that a part of the net cost of such activities (including stipends of trainees, as well as compensation of teachers and other costs) should be borne to an appropriate extent by the hospital insurance program .
House Report, Number 213, 89th Congress, 1st session 32 (1965) and Senate Report, Number 404 Pt. 1 89th Congress 1 Session 36 (1965)).
Each year about $9.5 billion in medicare funds and another $2 billion in medicaid dollars go towards residency programs. There is also state government support (multiplied by Federal matching funds). At 100K residents a year, this translates into about about $100 K per resident. The actual amounts each program receives per resident can vary (we’ve seen figures in the range of $50K to $150K) because of the formula used to compute the subsidy. In 1997, Congress capped the amount that Medicare would provide, which results in about 30K medical school graduates competing for about 22.5K slots.
Why should the costs of apprenticeship be borne by the government? Lawyers, also undertake 7 years of studies before they apprentice. The cost of their apprenticeship is borne by the organization that hires them out of law school. What makes Physicians different?
Two arguments we are aware of. First, were one to rely on the market to supply physicians, it is possible that we might get to few (think of booms and busts) in some periods. Assuming sufficient risk aversion on the part of society, there will be an interest in ensuring a sufficient supply of physicians. Note similar arguments are also used to justify farm subsidies. In other words, insurance against shortfalls. Interestingly, we know of no Lawyer with the `dershowitz’ to make such a claim. Perhaps, Dick the butcher (Henry VI, Part 2 Act 4) has cowed them.
The second is summarized in the following from Gbadebo and Reinhardt:
“Thus, it might be argued … that the complete self-financing of medical education with interest-bearing debt … would so commercialize the medical profession as to rob it of its traditional ethos to always put the interest of patients above its own. Indeed, it can be argued that even the current extent of partial financing of their education by medical students has so indebted them as to place the profession’s traditional ethos in peril.”
Note, the Scottish master said as much:
“We trust our health to the physician: our fortune and sometimes our life and reputation to the lawyer and attorney. Such confidence could not safely be reposed in people of a very mean or low condition. Their reward must be such, therefore, as may give them that rank in the society which so important a trust requires. The long time and the great expense which must be laid out in their education, when combined with this circumstance, necessarily enhance still further the price of their labour.”
Interestingly, he includes Lawyers.
If we turn the clock back to before WWII, Hospitals paid for trainees (since internships were based in hospitals, not medical schools) and recovered the costs from patient charges. Interns were inexpensive and provided cheap labor. After WWII, the GI Bill provides subsidies for graduate medical education, residency slots increased and institutions were able to pass along the costs to insurers. Medicare opened up the spigot and residencies become firmly ensconced in the system. Not only do they provide training but they allow hospitals to perform a variety of other functions such as care for the indigent at lower cost than otherwise.
Ignoring the complications associated with the complementary activities that surround residency programs, who should pay for the residency? Three obvious candidates: insurers, hospitals and the doctors themselves. From Coase we know that in a world without frictions, it does not matter. With frictions, who knows?
Having medicare pay makes residency slots an endowment to the institution. The slots assign to a hospital will not reflect what’s best for the intern or the healthcare system. Indeed a recent report by from the Institute of Medicine summarizes some of these distortions. However, their response to is urge for better rules governing the distribution of monies.
If hospitals themselves pay, its unclear what the effect might be. For example, as residents costs less than doctors, large hospitals my bulk up of residents and reduce their reliance of doctors. However, assuming no increases in the supply of residents, wages for residents will rise etc etc. If insurers pay there might be overprovision of residents.
What about doctors? To practice, a doctor must have a license. The renewal fee on a medical license is, at the top end (California), around $450 a year. In Florida it is about half that amount. There are currently about 800K active physicians in the US. To recover $10 billion (current cost of residency programs) one would have to raise the fee by a $1000 a year at least. The average annual salary for the least remunerative specialties is around $150K. At the high end about $400K. From these summary statistics, it does not appear that an extra $1K a year will break the bank, or corrupt physicians, particularly if it is pegged as a percentage rather than flat amount. The monies collected can be funneled to the program in which the physician completed his or her residency.
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
For such an unusual advice
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 () and sellers () of a homogenous good and a set of edges between them. No edges between sellers and no edges between buyers. The absence of an edge in linking and means that and cannot trade directly. Suppose buyer has a constant marginal value of upto some amount and zero thereafter. Seller has a constant marginal cost of upto some capacity 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 for denote the amount of the good purchased by buyer from seller . Then, the following program identifies the efficient allocation:
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 . 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 ‘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 be the dual variables associated with the first set of constraints (the supply side) and the dual variables associated with the second or demand set of constraints. The dual is
We can interpret as the unit price of the good sourced from seller and as the surplus that buyer will enjoy at prices . Three things are immediate from the duality theorem, complementary slackness and dual feasibility.
- If is a solution to the primal and an optimal solution to the dual, then, the pair form a Walrasian equilibrium.
- The set of optimal dual prices, i.e., Walrasian prices live in a lattice.
- The dual is a (compact) representation of the TU (transferable utility) core of the co-operative game associated with this economy.
- Suppose the only bilateral contracts we allow between buyer and seller are when . 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 .
- 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 by where we interpret to be the joint gain gains from trade (per unit) to be shared by buyer and seller .
Now, suppose we replace constant marginal values by increasing concave utility functions, and constant marginal costs by ? The problem of finding the efficient allocation becomes:
This is an instance of a concave flow problem. The Kuhn-Tucker-Karush conditions yield the following:
- If is a solution to the primal and an optimal Lagrangean, then, the pair form a Walrasian equilibrium.
- The set of optimal Lagrange prices, i.e., Walrasian prices live in a lattice.
- Suppose the only bilateral contracts we allow between buyer and seller are when . 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 .
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 and , specifically, they be -concave and convex respectively. This is a condition tied closely to the gross substitutes condition. More on this in a subsequent post.