  We provide a near-optimal, computationally efficient algorithm for the
unit-demand pricing problem, where a seller wants to price n items to optimize
revenue against a unit-demand buyer whose values for the items are
independently drawn from known distributions. For any chosen accuracy eps>0 and
item values bounded in [0,1], our algorithm achieves revenue that is optimal up
to an additive error of at most eps, in polynomial time. For values sampled
from Monotone Hazard Rate (MHR) distributions, we achieve a (1-eps)-fraction of
the optimal revenue in polynomial time, while for values sampled from regular
distributions the same revenue guarantees are achieved in quasi-polynomial
time.
  Our algorithm for bounded distributions applies probabilistic techniques to
understand the statistical properties of revenue distributions, obtaining a
reduction in the search space of the algorithm via dynamic programming.
Adapting this approach to MHR and regular distributions requires the proof of
novel extreme value theorems for such distributions.
  As a byproduct, our techniques establish structural properties of
approximately-optimal and near-optimal solutions. We show that, for values
independently distributed according to MHR distributions, pricing all items at
the same price achieves a constant fraction of the optimal revenue. Moreover,
for all eps >0, g(1/eps) distinct prices suffice to obtain a (1-eps)-fraction
of the optimal revenue, where g(1/eps) is quadratic in 1/eps and independent of
n. Similarly, for all eps>0 and n>0, at most g(1/(eps log n)) distinct prices
suffice if the values are independently distributed according to regular
distributions, where g() is a polynomial function. Finally, when the values are
i.i.d. from some MHR distribution, we show that, if n is a sufficiently large
function of 1/eps, a single price suffices to achieve a (1-eps)-fraction of the
optimal revenue.
