Traffic Lights: Regulation vs. free-markets

In the aftermath of the Sandy Hurricane, many parts of the NY/NJ area have sustained power outages, and as a result, traffic lights in these areas are not functional. This requires drivers to approach a traffic junction as a multi-way stop-sign. This got me thinking: What if, in place of traffic lights, we had just stop signs everywhere, and the rule was: the next car to go should be the car at the head of the longest queue. I believe this is an optimal scheduling policy in a certain sense (it provides an optimal throughput x delay product -- that is for a given average delay at the intersection, it would provide the highest rate number of cars going through [1] ). In this policy, each driver is trusted to follow the scheduling policy faithfully. For argument sake, I am ignoring (1) the time spent by each driver having to figure out which queue is the longest at each step, (2) how the driver at the head of each queue gets information about the length of each queue, and (3) the loss in efficiency incurred by slowing down and starting. Compared to this self-enforced scheduling policy, traffic lights can be very suboptimal. You know this if you have ever stood on a red light waiting to turn green while the street with the green signal has no traffic. Why then do we have traffic lights? The problem is that in the self-enforcing scheduling policy, there will be some drivers who will free-load, i.e. they will not obey the rule and simply take the turn for themselves, even if the turn belongs to someone else according to the scheduling rule. Further, when this happens, it will often result in collisions between the free loader and the rightful owner of the turn. This is why traffic lights are necessary, even though they come at the expense of reduced overall efficiency.

There is a nice lesson embedded here that speaks to the need for government regulation by way of analogy: Regulation is necessary to enforce fairness and safety by preventing freeloaders and accidents, even though a free market might provide higher overall benefit if everyone was guaranteed to behave properly. Therefore regulation is the price we must pay, in the form of reduced overall benefit, to counter the fact that all market participants do not behave as per the rules if left to themselves.

EDIT 1: The loss in overall utility when all participants are allowed to act selfishly, compared to the state where each participant acts for the overall good of the set of all participants, is called the price-of-anarchy. This is different from (but related to) the loss in overall utility from the imposition of regulations. A simple 2-player prisoner's dilemma can exhibit the price of anarchy when all participants are worse off if allowed at act selfishly, compared to the overall optimal for the 2 players. In the traffic light example, when players act selfishly, they create unfairness and also end up endangering everyone (including themselves, but perhaps they don't realize this bit). Hence the utility derived by each participant is lower, compared to if they all cooperated perfectly.

EDIT 2: Regulation can be thought of simply as a mechanism designed to improve the utility received by players beyond what it would be in anarchy, by changing the (rules of the) game a little. Regulation typically doesn't take the system to the overall optimal (which corresponds to perfectly cooperating players in the original game) of the original game. The 'price of regulation' ( = utility of overall optimum - that achieved by regulation) should be less than the price of anarchy (= overall optimum - state achieved by anarchy). Modern day regulators need to be really good at mechanism design!

EDIT 3: Perfect cooperation can be unstable against defection by free loaders [2] because the utility a player derives by unilaterally defecting is greater than that obtained by cooperating. If everyone is well aware of the risk of an accident upon defecting, then this can serve as a disincentive to defecting because the utility from defecting, after factoring in the probability of an accident may no longer make defecting worthwhile. This suggests that simply increasing awareness of the risks posed by misbehavior upon the misbehaving player, might improve the overall equilibrium a bit. Of course, this requires that the defector bear extra personal risk.


[1] I know this because it holds true for scheduling packets transmissions in a class of communication networks [citation required].

[2] I experienced free loaders first hand during the last few days after Sandy in 2 different contexts: people going out of turn at road intersections, and people trying to break into the long line at a gas station.

Compressive sensing of vacant parking spaces with mobile sensors

My work on mobile sensing for automotive parking applications has just been accepted to ACM Mobisys 2010 and I will br presenting this work at Mobisys in San Francisco in June 2010. The paper is about the design, implementation and evaluation of a mobile sensing system called ParkNet, for the purpose of harvesting in as close to real time as possible, information about the availability street-parking spaces in urban areas. ParkNet was recently featured in the MIT Technology review. It has just been covered by Rutgers Today, an organization within Rutgers University that produces news articles about promising research efforts within Rutgers. ParkNet proposes that sensors for sensing vacant street side parking spaces be made mobile (see this project trial that uses stationary sensors installed in the asphalt road, one sensor per spot, presumably at a huge cost) by exploiting vehicles that regularly comb city environment, such as taxicabs. ParkNet can be thought of as a compressive sensing system because it drastically reduces the number of sensors needed [with a corresponding dramatic decrease in overall cost], with a very small loss in spatio-temporal accuracy.

Naturally, one of the things I needed to figure out was: how well can a fleet of N taxicabs cover a given geographical area, in terms of mean time between successive cabs visiting a given street? How does this number vary with N. The San Francisco Taxicab dataset came in handy. The visualization on the right is made with good old Matlab©. It shows GPS coordinates of a single taxicab in the San Francisco area, measured about once per minute, over a period of 30 days. When I plotted this, I immediately realized that taxicabs would be great for ParkNet because most taxicabs tend to spend most of their time in the crowded downtown area of the city (dense, upper right corner in the plot), and this is where the parking problem is most serious.

Update: My ParkNet paper received the best paper award at ACM's annual Mobile Systems and Applications Conference [ACM Mobisys]!