On the Computational Complexity of Optimal Simple Mechanisms
On the Computational Complexity of Optimal Simple Mechanisms
We consider a monopolist seller facing a single buyer with additive valuations over n heterogeneous, independent items. It is known that in this important setting optimal mechanisms may require randomization [12], use menus of infinite size [9], and may be computationally intractable [8]. This has sparked recent interest in finding …