Power of Second Opportunity: Dynamic Pricing with Second Chance

In this paper, we consider the following dynamic pricing problem. Suppose the market price $v_t$ of an item arriving at time $t$ is determined by $v_t={\mathit{\theta }}^{\mathrm{T}}{\mathit{x}}_t$, where ${\mathit{x}}_t$ is the feature vector of that item and $\mathit{\theta }$ is an unknown vector parameter. The seller has to post prices without knowing $\mathit{\theta }$ such that the total regret in time span $T$ is minimized. Considering real-world scenarios in which people may negotiate prices, we propose a model called Second Chance Pricing, in which a seller has a second opportunity to post a price after the first offer is declined. Theoretical analysis shows that a second chance of pricing results in a total regret between $O\left({\displaystyle \frac{\ln T}{n\ln n}+{\displaystyle \frac{1}{n}}}\right)$ and $O(n^2\ln T)$, where $n$ is the dimension of the feature space. Experiments on both synthetic data and real data demonstrate significant benefits brought about by the second chance where the regret is only $13\text{\%}$ of that of one chance.