Optimal selection of customers for a last-minute offer

We analyze a short-term revenue optimization problem that involves the optimal targeting of customers for a promotion in which a finite number of perishable items are sold on a last-minute offer. The goal is to select the subset of customers to whom the offer will be made available in order to maximize the expected return. Each client replies with a certain probability and reports a specific value that may depend on the customer type, so that the selected subset has to balance the risk of not selling all the items with the risk of assigning an item to a low value customer. We show that {\em threshold strategies}, which select all those clients with values above a certain optimal threshold, may fail to achieve the maximal revenue. However, using a linear programming relaxation, we prove that they attain a constant factor of the optimal value. Specifically, the achieved factor is ${1\over 2}$ when a single item is to be sold, and approaches 1 as the number of available items grows to infinity. Furthermore, for the single item case, we propose an upper bound based on an exponential size linear program that allows us to obtain a threshold strategy achieving at least ${2\over 3}$ of the optimal revenue. Additionally, although the complexity status of the problem is open, we provide a polynomial time approximation scheme for the single item case, which leads to policies that might have very little structure. Finally we perform a brief computational study of the proposed policies and observe that their performance on randomly generated instances is significantly better than the theoretical predictions.