Sunday, August 16, 2009

Markets, regulation, MaxEnt, and the Braess paradox

I recently ran across Braess's paradox (again). (Christsos Papadimitriou mentions it in his wonderful talk on "The Algorithmic Lens.") It's an old result, 1968, one that I'd seen at least a decade and a half ago—and a number of times since. But it's so interesting that I decided to write up a little discussion.

The figure to the right shows a simple route map—for automobiles, let's assume. The goal is to get from A to D in the least time. The times are shown on each link. The time shown as T means that the time along that segment equals the number of cars on the road at the time.

One can imagine this map as representing a small network of roadways and ferries. The ferries carry cars over the river. The ferries are assumed to have an unlimited capacity. But they are not fast. The roadways are fast when uncrowded, but they slow down with congestion. We'll assume that usage information is generally available to all drivers, e.g., on the Internet or on radio "traffic condition" broadcasts.

Without the dashed line in the middle, traffic will divide itself between the two possible routes: A-B-D and A-C-D. The time for a trip will range from a minimum of T/2 + 12 to T + 12. If there are 10 cars, as we are assuming, the most efficient division is 5 on each route: 5 on A-B-D, and the other 5 on A-C-D. Each car will have a trip whose time is 5 + 12 = 17.

The paradox arises if one adds a "free link" from B to C. (Think of it as an unlimited capacity bridge.) All the traffic will go A-B-C-D. But then the total time is 10 + 0 + 10 = 20, worse than without the free link!

Why won't the cars divide up 5 and 5 as before? The A-C-D drivers will notice that it's faster to get from A to C by going first to B and then to C. That's true even if the route from A to B is 10 because it has all the cars. That's still faster than the direct A to C route, which is 12. So no matter how a car plans to finish the trip, the best first leg is A to B. By the same reasoning, once at B the best way to get to D is first to go to C.

The problem is that by eliminating the need for the ferry ride the free bridge essentially forces the cars onto the roadways, doubling the congestion (and doubling the time) on each. In other words, by forcing all the traffic to take both A-B and C-D the bridge doubled the travel time on each from 5 to 10. The previous routes of 17 time units each were no longer available.

How might that happen incrementally?
Imagine that after the creation of the free B-C route the drivers all agreed to go back to the earlier arrangement: 5 on A-B-D and 5 on A-C-D. One of the drivers on A-B-D would notice that if he did A-B-C-D instead his time would be reduced from 17 to 11. Such a saving would be hard to resist.

Then a second driver on the A-B-D route would notice that he could reduce his time from 17 to 12 by switching. The third driver would switch to reduce his time from 17 to 13. The last two drivers on the A-B-D route would also switch reducing their times from 17 to 14 and 15 respectively. At this point A-B is still 5 but C-D is now 10. All the drivers on A-B-C-D have times of 15.

But now the drivers who are still doing A-C-D notice that their times have increased from 17 to 22 because of the switches of the A-B-D drivers. So they start switching to A-B-C-D as well. The first switch reduces that driver's time from 22 to 16. The second switch reduces that driver's time from 22 to 17. The third, fourth, and fifth drivers also switch to reduce their times from 22 to 18, 19, and 20 respectively. At this point all the drivers have trips of 20 units, and they can't do any better by switching.

Although I tend to favor markets, here's a case in which what seems like a free-market solution—let each car make its own choice about route—is worse than a regulated system—force cars to take what seems to be a worse route.

A free-market solution
When the first driver switched from A-B-D to A-B-C-D, he reduced his time from 17 to 11. But he raised the times of each of the 5 drivers on the A-C-D route from 17 to 18. Considering all drivers, the net was a savings of 1: -6 +5 = -1.

In some sense that's ok; the total drive time was reduced and society worked slightly better. But the next driver to switch would have had a net effect of -5 +6 = +1. That is, he would have saved himself 5 units (from 17 to 12), but he would have cost the other 6 drivers who are already on C-D 1 unit each. Society as a whole would be less efficient by 1 unit. So the first switch reduced the overall travel time for all drivers by 1 unit. But any subsequent switch would have raised the total travel time.

So it seems that a 1/4/5 division is optimal: 6 + 5 = 11 units for the 1 driver on A-B-C-D; 12 + 5 = 17 for 4 drivers on (say) A-B-D; and 12 + 6 = 18 for 5 drivers on (say) A-C-D. The total drive time is 1 unit less than an even 5/5 division between A-B-D and A-C-D.

Gobal mechanisms
Let's assume we wanted to implement this optimum solution. Which driver should get the 11 route? Which should suffer the 18 route? And which should get the nominally normal 17? We could let the first driver to make the switch (since he is the innovator) get the benefit. But then he would have raised the travel time of 5 other drivers. That doesn't seem appropriate. But if you let the drivers make their own decisions, this arrangement would not be stable either, as we saw above.

A global planning structure would solve the problem. One solution is to have a random assignment of the specific optimal 1/4/5 route set to drivers each day. This would randomize the assignment of the good and bad routes. On average the expected drive time would be reduced from 17 to 16.9. Of course such a random assignment is not part of market mechanisms and must be implemented through some sort of global structure such as a government or a transportation user's group.

But any change from that 1/4/5 division of routes would make things worse overall. Because a switch of a driver assigned to, say, the A-B-D route to the A-B-C-D route would "foul the environment" for the other drivers, that switch should not be allowed. What this would mean in practice is that even if we had a random assignment of routes each day, there would have to be an enforcement mechanism so that each driver was prevented from taking a different route from that assigned. Again, this is not part of a pure market mechanism. The problem is that any driver making a switch that improved his own condition would be doing so at the expense of everyone else.

Taking the cost to "the environment" into account
So what was missing from the original analysis in which all the drivers eventually switched to A-B-C-D was an accounting of what could be considered the environmental or societal cost of the switch. Once that cost is included the system no longer moves to a worse equilibrium.

But to do so requires an extension of market mechanisms. The market generally does not charge for environmental or societal costs, and it does not impose forced solutions. To take those costs into consideration and to impose some global constraints, additional mechanisms must be added to a pure market structure. Those additional mechanisms would presumably be carried out by government or some other entity representing society as a whole.

One can ask whether the cost of adding those global mechanisms is worth the benefit of reducing each rider's average drive time from 17 to 16.9 In a large enough system with an efficient enough global mechanism it would be. Each driver should be happy to pay the taxes or user fees that are required to implement the global mechanism.

This is the sort of thing that living organisms, successful societies, and other far-from-equilibrium systems do. They find global mechanisms that are worth the cost of implementation.

Global constraints and MaxEnt
As I understand it, the Principle of MaxEnt says that systems that are subjected to a constant inflow of energy will configure themselves to dissipate that energy as quickly as possible. Does that principle apply in this case? Suppose we re-interpreted the example above to refer to energy flows or reductions in potential. The longer it takes energy to traverse a path from A to D, the more slowly the energy is dissipated.

Is that a fair way to re-interpret the example? If so, doesn't this violate the Principle of MaxEnt? Left to itself, the energy flow would all follow the A-B-C-D path, which results in slower dissipation than if the flow divided in half along the two perimeter paths. Furthermore, apparently the fastest overall configuration for energy dissipation is for 10% of the energy to follow A-B-C-D, with 40% following A-B-D (or A-C-D) and the remaining 50% following the other perimeter path. Yet without global constraints it appears that the system cannot configure itself to achieve that maximal rate of dissipation. Why is this not a violation of the Principle of MaxEnt? Or am I simply misunderstanding what MaxEnt is all about?


I.J.Swamy said...

The assumption that 5 cars go by ABD and 5 by ACD is wrong because cars and their numbers are known to blogger but not to car owners . Unlimited traffic bridge also is theoretical . Markets need to be free with very limited regulation. Diagramatic comparison between markets and traffic , confuses more than it clarifies. Cars in traffic and market trends in a country are two different modalities. The co efficient of correlation between the two is ZERO.

Blue said...

The cars will even themselves out as long as information about the relative congestion on the two routes is available. That's not an unreasonable assumption.

The bridge might be constructed under any number of circumstances. It could be a public service effort intended to reduce congestion. It could be a private development that makes money by other means, e.g., advertising of some sort.

More generally, whether you like this particular example, it's often the case that an apparent improvement to a system makes things worse rather than better. And once such an improvement is in place the mechanism by which things are made worse is typically local, e.g., market-like, whereas preventing that degradation is typically global, i.e., regulatory.

whenpigsfly said...

You're confusing MaxEnt which is an inference method developed by Jaynes which uses the word "entropy' but has nothing to do with efficiency of energy flows and the Law of Maximum Entropy Production which does and seems to be what you are referring to. Which is that a "system will select the path or assembly of paths that minimizes the potential (maximizes the entropy) at the fastest rate given the constraints" (e.g., see That is what you are wondering whether it is being violated (and is usually abbreviated MEP or LMEP). That would be the first point.

To your question, MEP or LMEP is not being violated because it is 'subject to contraints' and the way you've set up the problem as a rule-based system where the rules (as you give them) lead to the result you get then that's what you get. LMEP and the theory of nonequilibrium systems which it governs and explicates is subject to hysteresis even under situations that are not so artificially contrived as yours. Typically they do not for example function as maximally efficient steady states over time but 'develop' to senescence, e.g., look at any ecosyystem succession. If you want to have them rune 'efficiently' in your terms on a stable basis the way you describe it then you would have to put constraints into the system something of the kind you suggest to keep it going. Free markets in other words don't remain free (by some definition) unless you put constraints into the system to keep it from crashing at some point.