It’s a classic dilemma for air travelers in today’s world of wildly varying ticket prices: Buy now, or wait for a better deal and take the risk that the price will go up?
Researchers at the University of Southern California and University of Washington appear to have taken out some of the uncertainty with a new computer program that approaches a 90 percent score in saving money by predicting air fares.The researchers hope to follow up soon with a web-agent shopper that will actually be able to accept assignments to find tickets at the best price.
“If you’re on an airplane and look around at your fellow passengers, probably every single person on that plane has paid a different price,” said Oren Etzioni, associate professor in the Department of Computer Science & Engineering in the UW’s College of Engineering. On one flight studied, the ticket price varied by more than $2,000, depending on when the purchase was made.
“It’s the same product, but people are paying radically different prices,” he said. “So ‘to buy or not to buy’ is the question — that’s why we named our program ‘Hamlet.'”
Initial testing indicates that Hamlet does a good job of edging things toward the consumer’s side of the equation.
That fare! Should I snatch up a ticket now?
Or postpone the purchase in the hope of a lower price?
But what if the fare goes up instead of down?
Aye, there’s the rub…
During a 41-day pilot run, the algorithm saved 607 simulated passengers a total of $283,904 on airline fares by advising when to buy and when to postpone purchases. If one could predict the future and had perfect knowledge of how the ticket prices would vary, the greatest possible savings was $320,572. That means Hamlet’s savings were 88.6 percent of optimal.
Put another way, the algorithm saved an average of 27.1 percent per simulated passenger in cases where savings were possible. In a number of cases, savings were not possible because the virtual passenger tried to buy a ticket too close to the departure date.
Etzioni, co-resarcher Craig Knoblock of the USC Information Sciences Institute, and their colleagues have filed for a patent on the algorithm and the approach. A paper on the work, “To buy or not to buy: Mining airline fare data to minimize ticket purchase price,” appeared in the Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003.
Knoblock, an ISI senior project leader and research associate professor in the USC School of Engineering department of computer science, explained that the work of gathering the continually shifting airfare information was done by data-mining software agents that prowled the World Wide Web. “They would wake up every three hours, do the queries, and put the information they found in a database,” he said.
The agent search technology used was originally developed at ISI and subsequently turned into a commercial product, AgentBuilder, by an ISI spinoff, Fetch Technologies. The Hamlet project licensed AgentBuilder to do its datamining.
The agents had to extract information from a volatile market. Airlines are famous for “dynamic pricing” — frequently changing fares in an attempt to maximize revenue, using algorithms that are closely guarded trade secrets. That leaves the traveler at a disadvantage, Etzioni said.
“The airlines have a bunch of high-powered consultants who work with them to figure out the algorithm in the back room,” he said. “We’re looking at this from the consumer’s point of view. Can we help consumers save money?”
To do so, the project had to design an algorithm that could accurately predict what the airlines’ algorithms would do, without having access to the information the airlines use to drive their pricing.
The key was the World Wide Web. “That’s really what makes this possible,” Knoblock said. “All of the prices are now available online.”
Hamlet uses a combination of techniques to find patterns in the variation of prices over time.
For the purposes of the study, the researchers restricted themselves to two non-stop flights — Los Angeles to Boston and Seattle to Washington, D.C. The sleepless software agents observed six airlines on those routes, patiently gathering fares around the clock.
The agents reports showed that the price of particular flights changed as often as seven times a day. Over time, the range in prices could be extreme — for one flight on the LA to Boston route, for example, the high was $2,524 for a round trip ticket, compared to a brief low of $275. The high from Seattle to Washington, D.C., was $1,668 compared to a low of $281.
“Look how big those jumps are,” Etzioni said. “If you were going from Los Angeles to Boston and could buy in that window when the price dropped, you could save more than $2,000 on the ticket price. The potential savings are huge.”
While the airlines aren’t likely to welcome Hamlet, Etzioni believes their options for retaliation will be somewhat limited.
“We’re looking at prices that are available to people,” Etzioni said. “If the airlines start playing with the prices to trick us, they also have the potential of shooting themselves in the foot.”
In other words, the prices are juggled to maximize profits, and if airlines manipulate them to obfuscate things for algorithms like Hamlet, they are also changing their chance of selling a ticket.
“I would never underestimate the cleverness of another party,” Etzioni added. “But their hands are somewhat tied.”
Hamlet doesn’t buy tickets, but the group is hard at work on a follow-on agent program, a “travel agent agent” if you will, who will not just gather information but use it to get the best possible fare for its human clients.
This work builds directly on another ISI project called “Electric Elves,” which already uses software agents to facilitate travel by monitoring the Web for any problems that might affect existing reservations.
“Something like Hamlet fits in very nicely by providing the capability to create agents that learn patterns from online data sources.”said Knoblock.
Might thousands, or tens of thousands of Hamlet agents shopping for the best fares on the Web create their own price artifacts? “We’ll cross that bridge when we come to it,” said Knoblock.
Also participating in the research were graduate students Alexander Yates from UW and Rattapoom Tuchinda from USC, who are co-authors, with Etzioni and Knoblock, of the paper on the algorithm.
UW contact: Rob Harrill rharrill@u.washington.edu.
Published on April 4th, 2003
Last updated on August 10th, 2021
