Optimal online markdown and markup pricing policies with demand uncertainty

• We study the dynamic pricing problem with demand uncertainty from the perspective of online algorithms and competitive analysis.
• We prove the upper bound and propose an optimal online markdown pricing policy for the HBL problem.
• For the general LBH problem, we prove that there is no competitive deterministic online policy.
• For a special LBH problem with enough potential demand, we propose an optimal online markup policy.

In this paper, we study the dynamic pricing problem with demand uncertainty from the perspective of online algorithms and competitive analysis which eliminate the need for both the functional relationship between price and demand and the customer arrival rate. Assuming customer's reservation price falls in a closed interval, we prove the upper bound of any online policy for the HBL problem where the reservation price of a customer showing up later is always no more than the reservation price of a customer showing up earlier. And an optimal online markdown pricing policy whose competitive ratio matches the upper bound is proposed. For the symmetrical problem with LBH manner, we prove that there is no deterministic online policy whose competitive ratio is larger than the ratio of the lowest reservation price and the highest reservation price. For a special LBH problem with enough potential demand, we propose an optimal online markup policy dealing with not only how to price but also how much item to limit for each price.