Online pricing with impatient bidders
Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang · Symposium on Discrete Algorithms · 2016
In this paper we consider the following online pricing problem. An auctioneer is selling identical items in unlimited supply, whereas each bidder from a given set is interested in purchasing a single copy of the item. Each bidder is characterized by a budget and a time interval, in which he is considering to buy the item. Bidders are willing to buy the item at the earliest time provided it is within their time intervals and the price at that time is within their budgets. We call such bidders impatient bidders. The problem is considered in the online setting, i.e., each bidder arrives at the start of his time interval, and only then an algorithm learns of his existence and his budget. The goal of the seller is to set the price of the item over time so that the total revenue is maximized.We study two versions of the impatient bidders problem: the one introduced by Bansal et al. [TALG'10], and a more restricted setting in which the deadline of each bidder remains unknown until it is hit. We give tight bounds for both settings. Rather surprisingly, in both cases the optimum competitive ratios are the same. In particular we prove that the competitive ratio of an optimum deterministic algorithm is Θ(log h/log log h), whereas for randomized algorithms it is Θ(log log h).