Optimal selection of customers for a last-minute offer

We analyze a short-term revenue optimization problem involving the 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 might depend on the customer type, so that the selected subset has to balance the risk of not selling all items with the risk of assigning an item to a low value customer. We show that threshold strategies, which select all those clients with values above a certain optimal threshold, might 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/2 when a single item is to be sold and approaches 1 as the number of available items grows to infinity. Also, for the single item case, we propose an upper bound based on a sharper linear relaxation that allows us to obtain a threshold strategy achieving at least 2/3 of the optimal revenue. Moreover, although the complexity status of the problem is open, we provide a polynomial time approximation scheme for the single item case.