# The crazy math of airline ticket pricing

Earlier this year, I was scheduled to fly from California to Germany to give
some lectures at an international conference. When I came to book my flights, almost a month before the trip, the cheapest
round trip economy class tickets from San Francisco to Frankfurt on any major airline was $5,750. (That's right, almost six
thousand dollars; in economy class.) Needless to say, the conference organizers could not cover this outrageous fare, so I
pulled out and stayed at home.
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 *SIAM News,* published by the Society for Industrial and Applied Mathematics.

Mathematician Keith Devlin ( devlin@csli.stanford.edu) is the Executive Director of the Center for the Study of Language and Information at Stanford University and "The Math Guy"
on NPR's Weekend Edition. His latest book is The Math Gene: How Mathematical Thinking Evolved and Why Numbers Are Like Gossip, published by Basic Books.