Behavioral computing and airline loading...

Can distributed and local computing really be more efficient than centralized planning ? In economics of course, we know the answer, but in computing ?

Consider the problem: how to sequence passenger loading on an airplane so as to minimize completion time. In a Wired article by Dave Demerjian (pointer via Virginia Postrel), researchers proposed a "reverse pyramid" method (rear windows and middles before front aisles, roughly speaking) for loading passengers. The article also mentions "WILMA", or "Window-Middle-Aisle" order, and rotating zones (last 5 rows, first 5 rows, and so on), all of which are in use on different airlines.

Southwest however uses a different method, one that many of you are probably familiar with. Passengers are partitioned into three zones. Passengers enter by zone, and they sit wherever they want. According to the article,

...while Southwest's open seating might seem like an invitation for chaos, it actually illustrates a tendency among passengers to self-organize when left to their own devices. "Passengers who are free to sit anywhere usually do a good job staying out of each other's way," he explains. "Without having studied it in detail, I would imagine that an open boarding model is faster than assigned seating."

What we have here, ladies and gentleman, is an example of "Behavioral Computing". Michael Kearns at UPenn is one of the people investigating this space, and as he puts it,

Perhaps the computer science view of this fascinating line of thought can be best summarized as follows: Using relatively local information, distributed human organizations can compute good approximations to the all-pairs shortest paths problem. What other sorts of distributed optimization problems can humans networks solve?

Now this is not computing in the algorithmic sense: no n^2 time algorithms or NP-hardness results. But it reflects a growing interest in the "wisdom of crowds", social networks, and emergence phenomena (heck, even Charlie Eppes is working on 'cognitive emergence'). Kearns, and his students Nick Montfort and Siddharth Suri have some initial behavioral studies on graph coloring problems: there isn't a paper yet as far as I can tell, but I've heard about the results informally.

For those who might be wondering, this is not warmed-over distributed computing. Distributed computing indeed involved local computations, but the entities were slaves, devices that ran specific protocols that led to the desired outcome (leader election is a classic problem of this kind). There is a notion of malicious machines (a device that may have been compromised), and Byzantine agreement is a famous example of the kinds of problems one considers.

But the fundamental difference is that in this notion of behavioral computing, the local agents are not running pre-specified programs. They are often acting in their own interest, or working under some incentive model, ("I want to find the best seat quickly"), and may execute different procedures towards this goal. The key idea is to set up "a system that controls network structure, information conditions, incentives, and a variety of other variables of interest".

Thus, behavioral computing is more like distributed game theory, and fits nicely into the rapidly growing area of computational game theory.

Categories:

• models