To Buy or Not to Buy: Mining Airfare Data to Minimize

Ticket Purchase Price

Oren Etzioni

Dept. Computer Science

University of Washington

Seattle, Washington 98195

[email protected]ashington.edu

Craig A. Knoblock

Information Sciences Institute

University of Southern California

Marina del Rey, CA 90292

knobloc[email protected]

Rattapoom Tuchinda

Dept. of Computer Science

corporations vary these prices over time. However, corpora-

tions change prices based on proprietary algorithms and hid-

den variables (e.g., the number of unsold seats on a flight).

Is it possible to develop data mining techniques that will

enable consumers to predict price changes under these con-

ditions?

This paper reports on a pilot study in the domain of air-

line ticket prices where we recorded over 12,000 price obser-

vations over a 41 day period. When trained on this data,

Hamlet — our multi-strategy data mining algorithm — gen-

represents an average savings of 23.8% for the 341 passen-

gers for whom savings are possible. Overall, Hamlet saved

4.4% of the ticket price averaged over the entire set of 4,488

simulated passengers. Our pilot study suggests that mining

of price data available over the web has the potential to save

consumers substantial sums of money per annum.

Categories and Subject Descriptors

I.2.6 [Artificial Intelligence]: Learning

Permission to make digital or hard copies of all or part of this work for

personal or classroom use is granted without fee provided that copies are

1. INTRODUCTION AND MOTIVATION

Corporations often use complex policies to vary product

prices over time. The airline industry is one of the most

sophisticated in its use of dynamic pricing strategies in an

attempt to maximize its revenue. Airlines have many fare

classes for seats on the same flight, use different sales chan-

nels (e.g., travel agents, priceline.com, consolidators), and

frequently vary the price per seat over time based on a slew

of factors including seasonality, availability of seats, compet-

itive moves by other airlines, and more. The airlines are said

World Wide Web, consumers have the opportunity to be-

come more sophisticated shoppers. They are able to com-

parison shop efficiently and to track prices over time; they

can attempt to identify pricing patterns and rush or delay

purchases based on anticipated price changes (e.g., “I’ll wait

to buy because they always have a big sale in the spring...”).

In this paper we describe the use of data mining methods to

help consumers with this task. We report on a pilot study

in the domain of airfares where an automatically learned

model, based on price information available on the Web,

tend to go up or down over time? Our pilot study en-

ables us to begin to characterize the complex behavior

of airfares.

• What data mining methods are able to detect

patterns in price data? In this paper we consider

reinforcement learning, rule learning, time series meth-

ods, and combinations of the above.

• Can Web price tracking coupled with data min-

access to the airline’s model or to the number of avail-

able seats on the flights. Thus, a priori, price changes

could appear to be unpredictable to a consumer track-

ing prices over the Web. In fact, we have found price

changes to be surprisingly predictable in some cases.

The remainder of this paper is organized as follows. Sec-

tion 2 describes our data collection mechanism and analyzes

the basic characteristics of airline pricing in our data. Sec-

tion 3 considers related work in the areas of computational

finance and time series analysis. Section 4 introduces our

ports on a sensitivity analysis to assess the robustness of

our results to changes in the simulation. We conclude with

a discussion of future work and a summary of the paper’s

contributions.

2. DATA COLLECTION

We collected airfare data directly from a major travel web

site. In order to extract the large amount of data required

for our machine learning algorithms, we built a flight data

collection agent that runs at a scheduled interval, extracts

the pricing data, and stores the result in a database.

on web pages into XML. Once the system has learned the

extraction rules, AgentBuilder compiles this into a Theseus

plan. Theseus is a streaming dataflow execution system that

supports highly optimized execution of a plan in a network

environment. The system maximizes the parallelism across

different operators and streams data between operations to

support the efficient execution of plans with complex navi-

gation paths and extraction from multiple pages.

For the purpose of our pilot study, we restricted our-

selves to collecting data on non-stop, round-trip flights for

3. RELATED WORK

line.com). Whereas we gathered actual flight price data from

the web, TAC simulates flight prices using a stochastic pro-

cess that follows a random walk with an increasingly upward

bias. Also, the TAC auction of airline tickets assumes that

tion including historical averaging, neural nets, and boost-

ing. It is difficult to know how these methods would perform

if reconfigured for our price mining task.

There has been some recent interest in temporal data min-

ing (see [23] for a survey). However, the problems studied

under this heading are often quite different from our own

(e.g., [1]). There has also been algorithmic work on time se-

ries methods within the data mining community (e.g., [4]).

We discuss time series methods below.

Problems that are closely related to price prediction over

niques with rule learning techniques to improve their per-

formance.

Computational finance is concerned with predicting prices

and making buying decisions in markets for stock, options,

and commodities. Prices in such markets are not determined

by a hidden algorithm, as in the product pricing case, but

rather by supply and demand as determined by the actions

of a large number of buyers and sellers. Thus, for example,

stock prices tend to move in small incremental steps rather

than in the large, tiered jumps observed in the airline data.

there may be a time before the expiration of an option at

which its exercise is optimal. Reinforcement learning meth-

ods have been applied to both problems, and that is one

reason we consider reinforcement learning for our problem.

Time series analysis is a large body of statistical tech-

niques that apply to a sequence of values of a variable that

varies over time due to some underlying process or structure

[7, 13, 9]. The observations of product prices over time are

naturally viewed as time series data. Standard data mining

techniques are “trained” on a set of data to produce a pre-

There is also significant interest in bidding and pricing

strategies for online auctions. For example, in [24] Harshit et

al. use cluster analysis techniques to categorize the bidding

strategies being used by the bidders. And in [17], Lucking-

Reiley et al. explore the various factors that determine the

final price paid in an online auction, such as the length of

the auction, whether there is a reserve price, and the reputa-

tion of the seller. However, these techniques are not readily

applicable to our price mining problem.

Comparison shopping “bots” gather price data available

on the web for a wide range of products.

These are de-

scendants of the Shopbot [11] which automatically learned

to extract product and price information from online mer-

the data mining methods in this paper complement the body

of work on shopbots.

of stacked generalization [26, 28].

Our data consists of price observations recorded every 3

hours over a 41 day period. Our goal is to learn whether to

buy a ticket or wait at a particular time point, for a particu-

lar flight, given the price history that we have recorded. All

of our experiments enforce the following essential temporal

constraint: all the information used to make a decision at

particular time point was recorded before that time point.

In this way, we ensure that we rely on the past to predict

the future, but not vice versa.

• Number of hours until departure (denoted as hours-

before-takeoff).

• Current price.

• Airline.

• Route (LAX-BOS or SEA-IAD).

The class labels on each training instance were ‘buy’ or

‘wait’.

We considered a host of additional features derived from

the data, but they did not improve Ripper’s performance.

We did not represent key variables like the number of unsold

by s ∼ s

.

Thus, our revised Q-learning formula is:

(R(s

(Q(a

, s

)))

The reason for choosing -300,000 is now more apparent:

flight in the tenth example sells out in the next state. The Q

value for waiting in any state in this equivalence class will be

(−300, 000− 2, 000∗ 9)/10 = −31, 800, or still much less then

the Q value for any equivalence class where no flight sells

out in the next state. Thus the choice of reward for a flight

that sells out will determine how willing the Q-Learning al-

gorithm will be to risk waiting when there’s a chance a flight

may sell out. Using a hill climbing search in the space of

penalties, we found -300,000 to be locally optimal.

Q-learning can be very slow, but we were able to ex-

value of Q(w, s) depends only on the Q values of exactly

one other state: the state containing the same flight num-

ber and departure date but with three hours less time left

until departure. Applying dynamic programming is thus

straightforward, and the initial training step requires only

a single pass over the data. In order to compute averages

over states in the same equivalence class, we keep a running

total and a count of the Q values in each equivalence class.

Thus, the reinforcement learning algorithm just makes a sin-

gle pass over the training data, which bodes well for scaling

action with the lowest learned cost.

future, p

, based on a weighted average of prices already

seen. Thus, whereas Q-learning and Ripper attempt to gen-

eralize from the behavior of a set of flights in the training

data to the behavior of future flights, the moving average

model attempts to predict the price behavior of a flight in

the test data based on its own history.

At time t, we predict the next price using a fixed window

of price observations, p

, . . . , p

. (In Hamlet, we found

t+1

t

tested such rules for K ranging from 1 to 22, but none of

these rules resulted in savings and some resulted in sub-

stantial losses.

% of Optimal

$320,572

$173,002

21.8%

3.96%

-39.90%

2.48%

2.60%

Table 6: Sensitivity of Methods to Distribution of Passengers’ Earliest Purchase Points. The numbers

reported are the savings, as a percentage of total ticket price, achieved by each algorithm under each distri-

bution. We see that Hamlet outperforms Q-learning, time series, and Ripper on all distributions.

to collect data for multiple flights, but the amount of data

would be much smaller. This type of agent would fit well

within the Electric Elves system [6, 2], which deploys a set

of personalized agents to monitor various aspects of a trip.

many of the same pricing strategies as the airlines and it

would be interesting to see how much Hamlet can save in

these product categories. Similarly, online shopping sites

such as Amazon and Wal-mart are beginning to explore

more sophisticated pricing strategies and Hamlet will al-

low consumers to make more informed decisions. Finally,

reverse auction sites, such as half.com, also provide an op-

portunity for Hamlet to learn about pricing over time and

make recommendations about purchasing an item right away

or waiting to buy it. In general, price mining over time pro-

While we have not studied this question in depth, the ob-

vious problem is that changing fares on a flight in order to

fool a price miner would impact all consumers considering

buying tickets on that flight. If the price of a ticket moves

up substantially, then consumers are likely to buy tickets

on different flights resulting in a revenue loss for the airline.

Similarly, if the price moves down substantially, consumers

will be buying tickets at a discount resulting in a revenue

loss again. Thus, to avoid these distortions, the airlines are

forced to show the prices that they actually want to charge

This paper reported on a pilot study in “price mining”

over the web. We gathered airfare data from the web and

showed that it is feasible to predict price changes for flights

based on historical fare data. Despite the complex algo-

rithms used by the airlines, and the absence of informa-

tion on key variables such as the number of seats available

on a flight, our data mining algorithms performed surpris-

ingly well. Most notably, our Hamlet data mining method

achieved 61.8% of the possible savings by appropriately tim-