Nikhil Bansal,
Ning Chen, Neva
Cherniavsky, Atri Rudra, Baruch Schieber and Maxim Sviridenko

**Dynamic Pricing for Impatient Bidders**

**Abstract :**
Consider a typical scenario of a buyer buying a ticket from Priceline.
The buyer "arrives" at a certain time and tells Priceline the maximum
amount of money she is willing to pay for a ticket for a particular flight.
Priceline
looks for airfares and the moment the buyer finds a price lower than the
maximum amount she is willing to pay, she buys a ticket (this of course
is a simplification of what actually happen in practice but the scenario
captures portions of reality fairly well). We look at the problem
from the
perspective of the airline or a middleman like Priceline. Many buyers come
in at different times and are willing to pay different amounts of money
for a ticket on the same flight. The job of the airline or Priceline is to set
a *single* price for tickets on the same flight at any given time.
If the price is low then
a lot of buyers would buy tickets but it might mean a low revenue for
Priceline. On the other hand if the price is high then Priceline might get
a high revenue but it runs the danger of scaring away buyers. Obviously
the airline or Priceline wants to maximize their revenue. Thus, the task at
hand for them is to set prices (which can vary over time) for tickets so as
to generate as much revenue as possible.
We present an abstract model that captures the scenario above and study
pricing algorithms (both deterministic and randomized) for the model.
For the (unrealistic) scenario where
Priceline knows about all the buyers in advance, we show efficient
algorithms that can generate the optimal revenue. For the more realistic
scenario where Priceline only knows about buyers that are already
``in the system", we use *competitive analysis* to evaluate the
performance of the algorithms. On the positive side, we present
algorithms that in the worst case generate revenue that is guaranteed
to be withing some (well-defined) factor of the best revenue that could have been
generated in hindsight. On the negative side, we show that no algorithm
can generate revenue significantly better what our algorithms can achieve.

** Versions**