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