Optimal Mechanisms for Selling Two Heterogeneous Items

Abstract

We consider the problem of designing revenue-optimal mechanisms for selling two heterogeneous items to a single buyer. Designing a revenue-optimal mechanism for selling a single item is simple: Set a threshold price based on the distribution, and sell the item only when the buyer’s valuation exceeds the threshold. However, designing a revenue-optimal mechanism to sell two heterogeneous items is a harder problem. Even the simplest setting with two items and one buyer remains unsolved as yet. The partial characterizations available in the literature have succeeded in solving the problem largely for distributions that are bordered by the coordinate axes. We consider distributions that do not contain (0; 0) in their support sets. Specifically, we consider the buyer’s valuations to be distributed uniformly over arbitrary rectangles in the positive quadrant. We anticipate that the special cases we solve could be a guideline to un-derstand the methods to solve the general problem. We explore two different methods – the duality method and the virtual valuation method – and apply them to solve the problem for distributions that are not bordered by the coordinate axes. The thesis consists of two parts. In the first part, we consider the problem when the buyer has no demand constraints. We assume the buyer’s valuations to be uniformly distributed over an arbitrary rectangle [c1; c1 + b1] [c2; c2 + b2] in the positive quadrant. We first study the duality approach that solves the problem for the (c1; c2) = (0; 0) case. We then nontrivially extend this approach to provide an explicit solution for arbitrary nonnegative values of (c1; c2; b1; b2). We prove that the optimal mechanism is to sell the two items according to one of eight simple menus. The menus indicate that the items must be sold individually for certain values of (c1; c2), the items must be bundled for certain other values, and the auction is an interplay of individual sale and a bundled sale for the remaining values of (c1; c2). We conjecture that our method can be extended to a wider class of distributions. We provide some preliminary results to support the conjecture. In the second part, we consider the problem when the buyer has a unit-demand constraint. We assume the buyer’s valuations (z1; z2) to be uniformly distributed over an arbitrary rectangle [c; c + b1] [c; c + b2] in the positive quadrant, having its south-west corner on the line z1 = z2. We first show that the structure of the dual measure shows significant variations for different values of (c; b1; b2) which makes it hard to discover the correct dual measure, and hence to compute the solution. We then nontrivially extend the virtual valuation method to provide a complete, explicit solution for the problem considered. In particular, we prove that the optimal mechanism is structured into five simple menus. We then conjecture, with promising preliminary results, that the optimal mechanism when the valuations are uniformly distributed in an arbitrary rectangle [c1; c1 + b1] [c2; c2 + b2] is also structured according to similar menus.