Multidimensional Mechanism Design: Revenue Maximization and the Multiple-Good Monopoly

The seller of N distinct objects is uncertain about the buyer's valuation for those objects. The seller's problem, to maximize expected revenue, consists of maximizing a linear functional over a convex set of mechanisms. A solution to the seller's problem can always be found in an extreme point of the feasible set. We identify the relevant extreme points and faces of the feasible set. With N = 1, the extreme points are easily described providing simple proofs of well-known results. The revenue-maximizing mechanism assigns the object with probability one or zero depending on the buyer's report. With N > 1, extreme points often involve randomization in the assignment of goods. Virtually any extreme point of the feasible set maximizes revenue for a well-behaved distribution of buyer's valuations. We provide a simple algebraic procedure to determine whether a mechanism is an extreme point.