The crazy math of airline ticket pricing

This month, I have to fly from San Francisco to Boston to film a TV program. The cost of the round trip is $2,350, again in economy class. A few weeks later, I fly all the way to Japan and back, half way round the globe, for a mere $795 in economy.

Clearly, the price attached to an airline ticket has got nothing to do with the length of the journey. It has everything to do with supply and demand. The airlines employ some complicated computer programs to try to meet a number of goals, the main two being to avoid flying with any seats empty and to maximize the total net revenue to the airline.

A third goal is to attract customers from other airlines and a fourth is to create customer loyalty among regular flyers. These goals are what lie behind all those promotional packages and those loyalty membership programs like United's Mileage Plus or American Airlines' AA Advantage. These programs create additional complexities to the pricing system. For example, as a 100,000+ miles a year member of United's Mileage Plus, I was able to buy a round trip ticket from San Francisco to Milan for later this month for a bargain basement price of $1000 and upgrade it to business class at no cost, but a colleague who will be travelling with me, who bought the same ticket at the same time, and who is only a regular Mileage Plus member, was unable to upgrade.

Additional rules are designed to encourage flyers to book two weeks in advance, to fly on particular days of the week or at unpopular times, to include a Saturday night stay, to take along a companion, and to use less congested airports.

Also, many airlines offer incentives to passengers who make their own bookings on the Internet. And the savvy traveler who can stay awake long enough to make an Internet booking after midnight will occasionally come across so-called "Internet specials", super cheap deals that disappear when the rest of the nation wakes up and starts booking their airline travel.

Further complexity arises from the sale of blocks of seats by the airlines to third parties, often called "bucket shops", who then sell them at discount prices (or "consolidated fares").

The result of trying to meet all these different goals, in a highly volatile market, is a ticket pricing system that has grown increasingly complex over the years, to the point where on some flights, no two passengers will have paid the same price, and where it may be cheaper to fly from Boston to New York via London, England, than to take the direct shuttle flight. (Yes, this one has actually occurred.)

Faced with all this confusion, with computers constantly monitoring sales and adjusting fares as often as ten times a day, the only real option for the fare conscious air traveler is to use a Web service to try to locate the best deal. A number of such services have sprung into being in recent years, among them Expedia, Travelocity, and CheapTickets. These services trawl the Web looking for the cheapest fare for any given destination and dates of travel.

But just how well do those search engines do? Not very, is the answer. And with good reason. Airline pricing has grown so complex that it is now practically impossible to design an algorithm that will find the cheapest fare. In mathematical terms, the (idealized) problem of finding the cheapest airfare between two given locations is actually unsolvable, and even if you specify the actual route or the flights, the (idealized) problem of finding the lowest fare is NP hard, which means it could take the fastest computers billions of years to solve. This is the perhaps surprising result obtained recently by mathematician Carl de Marcken.

The story began a few years ago, when Jeremy Wertheimer, then a graduate student in computer science at MIT, and a group of fellow graduate students set out to develop an airline pricing search engine. When what looked like being a few months work failed to yield the expected results, the group began to examine the nature of the airline pricing system. Their study did lead them to develop a powerful price-searching system, which the company they formed, ITA software, markets to both Orbitz (a fare searching site owned by five of the major US airlines) and Delta Airlines, who use it to drive their search utilities. But it also led to the discovery, by research team member de Marcken, that they were chasing the end of a rainbow.

The problem was that all the different pricing rules interact in ways that not even those who designed the pricing systems could begin to fully understand. Mathematically, this made the (idealized) problem of finding an optimal fare between two given locations undecidable, which means that it is impossible to write a computer program to solve the problem. For the same reason, the more specific (idealized) problem of finding an optimal fare for a particular route, while theoretically solvable, turns out to very similar to a classical mathematical problem known as boolean satisfiability, which has long been known to be NP-complete -- which means it could take the fastest computer longer than the lifetime of the universe to find the solution.

Admittedly, in order to study the airline pricing problem mathematically and obtain these results, de Marcken had to make some simplifying assumptions that don't apply to real airline travel, such as allowing an unlimited number of destinations, flights of unlimited length, or arbitrarily long lists of rules. But the implications for real airline pricing are unavoidable.

You can get a sense of just how complicated the real situation is when you consider that with airlines offering thousands of different fares, with different sets of rules governing the different legs on each trip, if two people take a round trip together, with three flights in each direction, there can be as many as 1,000¹², or around 10³⁶, fare combinations. If you printed out a ticket for each possible fare, the pile would stretch all the way to the nearest star, Proxima Centauri, four light years way.