  We show that computing the revenue-optimal deterministic auction in
unit-demand single-buyer Bayesian settings, i.e. the optimal item-pricing, is
computationally hard even in single-item settings where the buyer's value
distribution is a sum of independently distributed attributes, or multi-item
settings where the buyer's values for the items are independent. We also show
that it is intractable to optimally price the grand bundle of multiple items
for an additive bidder whose values for the items are independent. These
difficulties stem from implicit definitions of a value distribution. We provide
three instances of how different properties of implicit distributions can lead
to intractability: the first is a #P-hardness proof, while the remaining two
are reductions from the SQRT-SUM problem of Garey, Graham, and Johnson. While
simple pricing schemes can oftentimes approximate the best scheme in revenue,
they can have drastically different underlying structure. We argue therefore
that either the specification of the input distribution must be highly
restricted in format, or it is necessary for the goal to be mere approximation
to the optimal scheme's revenue instead of computing properties of the scheme
itself.
