Title: On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer,
Abstract: We show that the Revenue-Optimal Deterministic Mechanism Design problem for a
single additive buyer is #P-hard, even when the distributions have support size
2 for each item and, more importantly, even when the optimal solution is
guaranteed to be of a very simple kind: the seller picks a price for each
individual item and a price for the grand bundle of all the items; the buyer
can purchase either the grand bundle at its given price or any subset of items
at their total individual prices. The following problems are also #P-hard, as
immediate corollaries of the proof:
1. determining if individual item pricing is optimal for a given instance,
2. determining if grand bundle pricing is optimal, and
3. computing the optimal (deterministic) revenue.
On the positive side, we show that when the distributions are i.i.d. with
support size 2, the optimal revenue obtainable by any mechanism, even a
randomized one, can be achieved by a simple solution of the above kind
(individual item pricing with a discounted price for the grand bundle) and
furthermore, it can be computed in polynomial time. The problem can be solved
in polynomial time too when the number of items is constant.