  Algorithmic pricing is the computational problem that sellers (e.g., in
supermarkets) face when trying to set prices for their items to maximize their
profit in the presence of a known demand. Guruswami et al. (2005) propose this
problem and give logarithmic approximations (in the number of consumers) when
each consumer's values for bundles are known precisely. Subsequently several
versions of the problem have been shown to have poly-logarithmic
inapproximability. This problem has direct ties to the important open question
of better understanding the Bayesian optimal mechanism in multi-parameter
settings; however, logarithmic approximations are inadequate for this purpose.
It is therefore of vital interest to consider special cases where constant
approximations are possible. We consider the unit-demand variant of this
problem. Here a consumer has a valuation for each different item and their
value for a set of items is simply the maximum value they have for any item in
the set. We assume that the preferences of the consumers are drawn from a
distribution, the standard assumption in economics; furthermore, the setting of
a specific set of customers with known preferences, which is employed in all
prior work in algorithmic pricing, is a special case of this general problem,
where there is a discrete Bayesian distribution for preferences specified by
picking one consumer uniformly from the given set of consumers. Our work
complements these existing works by considering the case where the consumer's
valuations for the different items are independent random variables. Our main
result is a constant approximation that makes use of an interesting connection
between this problem and the concept of virtual valuations from the
single-parameter Bayesian optimal mechanism design literature.
