Which Plane Lands Last?

Inclement weather is a big deal in the airline industry—it is responsible for nearly 40 percent of the total amount of time flights are delayed. Wind, fog, snow, and thunderstorms limit the rate at which planes can safely take off and land. That throws airlines’ and air traffic controllers’ carefully crafted schedules into disarray. The Federal Aviation Administration has to step in to make sure everyone gets a fair slot on the runways.

In the past, the FAA used a procedure called Grover-Jack. It assigned arrival slots during inclement weather based on feasible departure times, which were reported by the airlines themselves. Under Grover-Jack, if a plane had a mechanical problem, that delay was added to the weather delay, penalizing the airline twice. Airlines would deliberately withhold information about mechanical and other problems to avoid this double penalty. Sometimes they would be able to land a different flight in the open slot, but if none was ready the slot would go unused. That meant arrival slots—which were already limited—were being wasted, lengthening delays. This was bad for everyone.

Eventually the FAA developed a new scheme that assigns arrival slots based on their original schedule, not actual schedule. If a flight cannot use a weather-delayed slot, an algorithm called Compression steps in to reassign it. Compression works by first looking for flights by the same airline. If none exist, it moves on to other carriers to look for a trade. That trading is the fundamental advantage Compression has over Grover-Jack. When an airline decides a slot is useless, it trades it for a later one, usually owned by the carrier that took the heretofore useless slot. The airline that gave up the initial slot is rewarded because the one it accepts is typically earlier than it would have received otherwise.

Because of these incentives, the FAA says the Compression algorithm is immune to the sort of games that were played under Grover-Jack. And as far as anyone knew, that seemed to be the case. But no one ever sat down to make sure.

Enter James Schummer and Rakesh Vohra, associate professor and professor, respectively, of managerial economics and decision sciences at the Kellogg School of Management. They undertook the first rigorous investigation of the Compression algorithm. While they show that Compression is largely free from manipulation, they do reveal some potential problems.

Identifying the Problems

The first issue is that Compression merely discourages manipulation—it does not preclude it entirely. One trick would be if an airline could “destroy” a slot. “Destroying a slot means pretending there’s a flight in there and isn’t really in there. Basically that slot is not available,” Vohra says. That could give an airline an advantage by denying their competitors that slot. While Schummer and Vohra say that slot destruction is a shortcoming of Compression, it will not necessarily present a problem in the real world.

“An airline would actually have to run the computations to find the situation,” Schummer remarks, adding even that is only half the battle. “At some point the FAA realizes that the plane you were supposed to land there hasn’t taken off yet back at the other airport.” The slot would remain empty, but the ruse would be exposed and the airline likely punished. Such a brief gain would not be worth the trouble.

Still, there is nothing in the Compression algorithm that prevents slot destruction. As game theorists who prefer to tackle all shortcomings of a model, Schummer and Vohra are bothered by this issue, though they have not yet devised a way to address it mathematically.

The second problem with Compression that Schummer and Vohra identified is more tractable, and one for which they have a solution. Under Compression, it is possible that a subset of airlines could break off from the main group. Such a schism would occur if those airlines thought they could fare better trading slots among themselves rather than in the larger group.

Arrival slots technically belong to the federal government—airspace is a public good owned by everyone in the country—but airlines have claimed squatters rights because they have invested money in staffing and scheduling around those times. Schummer and Vohra say Compression does not go far enough to respect those rights, which could lead to splinter groups.

To see how a splinter group would affect the air traffic system, let’s say that of three carriers—Delta, American, and United—two of them—United and American—decide to trade slots with each other and exclude Delta. That would give United and American first choice from their collective pool of slots. But suppose a Delta flight would be a better fit for one of those slots, easing congestion more than a United or American flight. Because Delta is not in that group, United and American could effectively deny them that slot. United and American would gain the advantage, but the system as a whole would be worse off.

Such blocking coalitions would reduce the pool of slots for other airlines and harm the efficiency of the allocation process. Fortunately, these coalitions are not likely to form. “As a practical matter, given the amount of time in which airlines have to do these arrangements, it’s not clear that it’s feasible for them to do that,” Vohra says.

A Better System

So given that neither slot destruction nor splinter groups are likely under the Compression algorithm, why bother searching for such theoretical flaws? Because in the process Schummer and Vohra have found another algorithm—called Trade Cycle—that they say would both eliminate those theoretical problems and be better overall.

Trade Cycle is based on an old economic theory called the house trading model. In the house trading model, the fundamental question is, Vohra says, “Without money, is there a way to trade that in some sense is good?” To understand how that works, let’s pretend you ask three people to point to the owner of another house they would like to trade into. Any sequence of owners who form a cycle—person 1 points to person 2 who points to person 3 who points to person 1—can trade with each other and each receives their favorite house by giving up their current house. These three owners can then move into their new homes, and the process starts all over again. “No one has an incentive to lie about their favorite house at any time,” Vohra points out. “Why is that? At the beginning, I ask you to point to your favorite house. You wouldn’t have gained by pretending your favorite house was your number four choice.” The same goes for airlines—in pointing to their favorite slot, there is no incentive to lie.

When applying the house trading model to flight arrival slots, Vohra says, “there are a couple of wrinkles. In the house trading model, every agent owns a single house. Here agents are airlines and they own multiple homes.” That makes the mathematics a bit trickier, but not so onerous that the problems cannot be solved.

Eventually, all airlines receive slots that are better than the ones they started out with, or at least no worse. The key part about Trade Cycle—the part that makes it work—is that it respects the property rights of airlines and their slots. When trading, an airline may be giving up their right to that slot, but in return they are receiving one that is worth more to them. There is no need for shenanigans like slot destruction or slot-trading cartels. The result, Schummer and Vohra hope, would be a slot assignment system that would function even more smoothly, reducing the number of minutes flights are delayed.

Schummer and Vohra have yet to present their paper to the FAA, though they are open to the idea. But before they do, they want make sure they have worked through all the details. “One approach we sometimes take as game theorists is to first solve a problem in reduced form, before enriching it with details to see which details really matter.”

Related reading on Kellogg Insight

Cutting in Line: Flexible queuing systems may improve customer service

We Will Be Right with You: Managing customers with vague promises

Should I Bring an Umbrella? Rating forecasters is difficult, but not impossible