The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers
Patrick Briest
Abstract:
We study an extension of the unit-demand pricing problem in which the seller may offer bundles of items. If a customer buys such a bundle she is guaranteed to receive one item out of it, but the seller does not make any promises as to how this item is selected. This is motivated by the sales model of retailers like hotwire.com , which offers bundles of hotel rooms based on location and rating, and only identifies the booked hotel after the purchase has been made. As the selected item is known only in hindsight, the buying decision necessarily depends on the customer's belief about the allocation mechanism. We study strictly pessimistic and optimistic customers who always assume the worst-case or best-case allocation mechanism relative to their personal valuations, respectively. While the latter model turns out to be equivalent to the pure item pricing problem, the former is fundamentally different. In particular,
(1) a revenue-maximizing bundle-pricing can be computed efficiently in the uniform version of the problem, in which every customer has identical values for some subset of the items and values all other items at 0, and
(2) for non-uniform customers computing a revenue-maximizing pricing is APX-hard and allows for a constant factor approximation when valuations satisfy some appropriate coarseness condition.
This is joint work with Heiko Röglin.