Online Pricing with Strategic and Patient Buyers
We consider a seller with an unlimited supply of a single good, who is faced with a stream of T buyers. Each buyer has a window of time in which she would like to purchase, and would buy at the lowest price in that window, provided that this price is lower than her private value (and otherwise, would not buy at all). In this setting, we give an algorithm that attains O(T 2/3 ) regret over any sequence of T buyers with respect to the best fixed price in hindsight, and prove that no algorithm can perform better in the worst case.
This paper considers an online pricing problem when the seller faces a steam of incoming strategic and patient buyers. The patience of buyers is modeled by a time window, beyond which buyer will leave. The arrival of buyers types are assumed to be adversarial. A EXP3 based learning algorithm is proposed. The basic idea of the algorithm is to bundle time steps are into epochs, and a fixed price (given by EXP3) will be announced for each epoch. Then the algorithm uses the feedback from the entire epoch to update EXP3. Upper bound on learner’s regret can thus be easily established via using the results from EXP3. Then the problem is shown to be reducible from a MAB problem with switching cost; a matching lower bound is developed nicely following the reduction.   This paper considered a different worker patience model for online pricing. The techniques for proving the lower bound (relate the strategic buyer model to a MAB with switching cost) are interesting, and may find applications in other problem settings. The results are presented clearly.   I read the authors' rebuttal.
While the problem is well formulated, and both upper and matching lower bound are nicely presented, the reviewer has the following concerns.  On modeling: The algorithm requires knowing workers’ patience. It is mentioned in the paper that such information can be gathered through buyers’ reports; but when such information is elicited from workers, would strategic manipulation and reporting complicate the algorithm design?   On the lower bound: Based on the reviewer’s reading, the lower bound is established over a learning space that the learning algorithm always posts price forehand for tau+1 time window sizes. So if this is the case, the proved lower bound is not quite the true lower bound, as the learner can be strategic about price posting, and so can the workers respond correspondingly. Also a relevant note: before presenting Algorithm 1, it is mentioned that the intuition is to minimize the number of times it changes prices, as the buyer would select the lower of the two prices for example when the window size is 2. But this argument is again based on the fact prices are pre-posted? If the learner can adjust the prices accordingly, forgoing the current price the buyer may risk missing a lower price in hindsight.   Other comments:  -The authors mention that modeling patient workers using time window is an important aspect of this work, while considering a discounted buyer will make the problem less trackable. But it looks like the discount model has already been considered in existing results, e.g., in [1],   -Just want to clarify the window size = tau (patience) + 1? so the claim that [11] is a special case of the current paper is not precise: [11] has tau = 0, while the set of results developed in this paper are for tau >= 1; as otherwise a sort{T} lower bound can immediately be established based on the results in [11].