Skip to main content

IEOR seminar by Dr. D. Thirumalanathan

Title: Title: Optimal mechanisms for selling two heterogeneous items

Speaker: Dr. D. Thirumalanathan

Time and Date: 10.30am-11.30am, 28th February (Thursday)

Venue: IEOR Seminar room (2nd floor)

Abstract: Thirumulanathan is currently a senior engineer at Qualcomm, Bengaluru. He received his masters and Ph.D. from the Indian Institute of Science. His Ph.D. thesis was on designing optimal mechanisms for selling two items. His work has resulted in two papers being published on a core economics journal: Journal of Mathematical Economics. His research interests include game theory, mechanism design, optimization, and data analytics.

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 set-
ting 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 understand 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 talk 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 ex-
tend 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.

News Category
Date Posted