Revenue Maximization for Buyers with Outside Options

We study mechanisms for selling a single item when buyers have private values for their outside options, which they forego by participating in the mechanism. This substantially changes the revenue maximization problem, which becomes non-convex in the presence of outside options. For example, even when there is just a single buyer, the seller can strictly benefit from selling lotteries. For multiple buyers with private outside options, we show how to construct a $(2+\epsilon)$-approximately revenue-optimal mechanism in polynomial time. Our approach makes use of a many-buyers-to-single-buyer reduction, and in the single-buyer case our mechanism improves to an FPTAS. We also bound the menu size and the sample complexity for the optimal single-buyer mechanism. Moreover, we show that posting a single price in the single-buyer case is in fact optimal under the assumption that either (1) the outside-option value is independent of the item value, and the item value distribution has decreasing marginal revenue or monotone hazard rate; or (2) the outside-option value is a concave function of the item value. When there are multiple buyers, we show that sequential posted pricing guarantees a large fraction of the optimal revenue under similar conditions.