Monday, June 23, 2008

Traffic, game theory, and efficient markets

One of the perks of working for Microsoft and living in Seattle is getting to sit in traffic for a couple hours a day (I'm working on something greener, honest). So, I have a lot of time to think. Often, my thoughts turn to why exactly there is so much traffic. (There is a lot of scholarly work on traffic, and you can write code to model different things, but I'm speaking from a more theoretical perspective).

I take State Route 520 to and from work. There are no traffic lights, so on the surface, I thought traffic couldn't get too bad. I don't see much reason why the ratio of total trip time to the number of cars on the road shouldn't remain fairly constant or at least scale gracefully. But, it does not. At some point, there is enough traffic that you spend most of the time stopped, and getting home takes an hour plus, instead of 15 minutes.

So, there must be other factors affecting traffic patterns besides the road itself. There are two important other factors: surrounding road topology, and people. Traffic is worst coming home (Westbound), and it's bad from about 4-7 every day. That's what I'm going to look at here.

520 runs through Redmond, to a bridge across Lake Washington, and ends at I-5 in Seattle. During rush hour, there's traffic along the whole way. The strange thing is, it's not uniform. Not even close. It tends to be wide open until you hit the I-405 intersection, and then be solid all the way to the lake, where it opens up until it ends at I-5. The area of interest is this map.

In terms of topology, the road is two normal westbound lanes, with a carpool lane on the right. The carpool lane ends right before the bridge across Lake Washington, and two lanes go west across the bridge. There are 3 entrances to 520 that are near the traffic: I-405, 108th Ave, and 84th Ave (see map above). You can get on or off 520 there, and some people use them as shortcuts to skip 520 traffic.

People getting on at these shortcuts cause a large delay due to merging. At each intersection, you are effectively merging another lane or two of cars into 520's two lanes. On top of that, merging occurs through the carpool lane, slowing it greatly. Merging forms the primary source of delay because it is essentially a funnel for cars. In total, with the 3 entrances, and additional 5 lanes (plus the carpool lane) of cars have to be merged into 520's 2 lanes to go across the bridge.

That got me thinking, why doesn't everyone just not take shortcuts? I am almost positive the average time to get across 520 would be greatly reduced.

The answer comes from game theory. Unfortunately, this is a classic example of the Prisoner's Dilemma. Suppose that I did convince everyone not to take the shortcuts for a day. Then, one unscrupulous (or logical) person could bypass all the remaining traffic by taking a shortcut. From a game theoretical perspective, that person is doing the correct action if his goal is to maximize his own happiness (a fundamental tenet of economies and societies... true selflessness is so rare as to almost always have no impact on their courses). Game theory and the Prisoner's Dilemma make it clear why there will always be people trying to take these shortcuts to skip 520 traffic: everyone wants to maximize his or her own personal utility. In this particular case, this greedy algorithm creates a global suboptimal solution relative to the better solution of no shortcuts, as measured by average trip time. It is extremely unlikely that this will change without topological changes to the road system.

Once I arrived at this conclusion in late 2007, I was satisfied in my analysis of the patterns and decided to just sit in the traffic in the left lane to minimize my impact and involvement in negative traffic behaviors. Then, about a month ago, I was in a rush and had to run an errand near one of the shortcut entrances. So, I tried a shortcut for the first time. I discovered it took just as long as simply sitting in the traffic.

This seemed strange to me. I mean, I knew that game theory projected there would always be people taking the shortcuts, and that at equilibrium all the routes would take around the same time, but it got me thinking about the decision process behind those people who choose to take the shortcuts, especially those who did it all the time. What did they think they were getting, and why are they choosing a particular route?

This led me to the efficient market hypothesis. Sure, there are psychological factors to it related specifically to driving, like preferring moving along a longer route vs. sitting still on a shorter one, but I saw another parallel to economics.

The (controversial) efficient market hypothesis (EMH) says that at all times, the prices of objects in the market (stocks, bonds, commodities, etc.) reflect an accurate value incorporating the sum of all public information about that object. These fair market prices arise naturally out of buying and selling those objects on the open market, and are kept in check globally and across all markets by arbitrage.

For example, suppose there were 100 tons of gold that we knew about and had mined from the earth, and that gold was $1000 an ounce. Then, suppose I get lucky and find a 2 ton vein in my back yard. The EMH says that, as soon as my find is public knowledge, and given that the demand for gold is fixed, that the value of an amount of golf will drop 1.96% to make an ounce of gold worth $980.39. Arbitrageurs make sure that prices of gold across the planet, in all currencies, are the same by exploiting small differences for profit until the difference disappears.

So, what does this mean to traffic? It's more of a leap to EMH than Prisoners Dilemma, but EMH can be applied to traffic in some ways, only with time instead of money as the "gold".

There are 4 ways to get onto the bridge on 520: sitting in traffic, or taking one of three shortcuts. All of these routes are public knowledge, and everyone who does this commute knows about them. Everyone can also look up traffic data on the Internet, providing an approximation of how long it will take to get to the bridge. So, the EMH s says all routes should take about the same amount of time. If any particular route did let one "beat the traffic," more and more people would take it as the information became public, until it no longer beat the traffic.

In practice, the times on all the shortcuts are fairly close. But, the differences in the times highlight some of the problems with applying the EMH to traffic (and the market in general, in my opinion). First, the EMH depends on the market having perfect information. Inaccurate, incomplete traffic data, people who don't know about the shortcuts, and other factors cause the information in this system to be imperfect. Second, once you're in your car, by and large you won't get any more information (unless you have something like GPS or Internet phone that can get it for you). Finally, you can't change routes at will. In the market, you can buy or sell almost anything at any time (if the market is open). In traffic, you only have a few chances to change, namely by finding some intersection between one of the 4 paths and changing routes. There are only a handful of times in your journey home you can make this decision. The application of EMH therefore isn't entirely correct, but it still provides some insight.

So, there is a small amount of inefficiency in the traffic system. There's a chance that you could get home faster by taking one route over the others. This chance is what people on shortcuts are chasing. Sometimes they make it, sometimes they don't. But, they are always acting as a sort of arbitrageur (except they, unlike a good arbitrageur, can lose). They are providing stability to the system by decreasing the impact of random events (like accidents), and decrease the variance of my trip time. For that, I decided, I am thankful. I'd rather spend an hour in traffic everyday, that 3 hours every once in a while.

The moral of the story: as long as there are shortcuts, people will take them, even if they don't help (which they shouldn't in the aggregate). And while you're yelling at them for skipping traffic in front of you, remember that they aren't getting there any faster in the long run, but they are helping you get there more consistently.

A better moral: take the bus. You'll get to spend time thinking about things other than traffic.

1 comment:

lancea12 said...

Shawn, you need a bike, then you can really start thinking about things other than traffic. Nice analysis though.