## Devlin's Angle |

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^{12}, or around 10^{36},
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.

Devlin's Angle is updated at the beginning of each month. This article was based on a longer story by Sara Robinson in the July/August issue of