Title: Solutions to optimization problems with a continuum of variables/constraints in auction settings
Speaker: Dr. D. Thirumalanathan
Time and Date: 10 am-11 am, 21st November 2019 (Thursday)
Venue: IEOR Teaching lab (Ground floor, IEOR Building)
Abstract:
We consider the problem of designing auction mechanisms that optimize revenue. We optimize revenue in two settings: (i) Maximize revenue while selling two heterogeneous items to a single buyer; (ii) Minimize the surplus with the central entity while allocating a divisible resource efficiently to many users.
Revenue maximization problem: The design of a revenue optimal mechanism to sell one item was solved by Myerson in 1981, but the same problem in the two-item setting remains unsolved as yet, even when only one buyer is present. 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. We consider the case when the buyer's valuation is uniformly distributed over an arbitrary rectangle in the positive quadrant, and show that the optimal mechanism is to sell according to one of eight simple structures. We model the problem into a functional optimization problem, and discover that its dual is a relaxed version of the optimal transport problem in the functional domain. We then provide a general solution to the dual functional optimization problem, when the support set is any arbitrary rectangle in the positive quadrant.
Surplus minimization problem: Consider the problem of designing a mechanism satisfying incentive compatibility, allocative efficiency, and budget balance, to allocate a divisible good. But by Green-Laffont theorem, no mechanism satisfies all three properties simultaneously. So, we relax the budget balance (zero surplus) constraint to near budget balance (minimal surplus). We model this problem as an optimization problem with a continuum of constraints (called an Uncertain Convex Program), and propose a solution method via constraint sampling. We also identify the number of samples sufficient for a good approximation.
Speaker Bio: 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, using functional optimization. His work has resulted in two papers being published in a core economics journal: Journal of Mathematical Economics. His research interests include game theory, mechanism design, optimization, and data analytics.