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=θ^Tx_t, where x_t is the feature vector of that item and θ is an unknown vector parameter. The seller has to post prices without knowing θ 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 (Formula presented), 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% of that of one chance.