AF: Small: On the Complexity of Optimal Pricing and Mechanism Design

点击翻译按钮获取中文摘要

In this project, the PIs plan to investigate fundamental questions in algorithmic pricing, and improve the current understanding in this area. Consider the setting where a buyer is interested in multiple heterogeneous items offered by a seller. While values of items to the buyer are private, the seller can exploit stochastic information on the preferences of a typical buyer to maximize her expected revenue. Optimal pricing problems under various settings have received considerable attention in the computer science literature during the past decade, and have been studied from both the algorithmic and complexity-theoretic perspectives, yet many basic questions remain open. The motivation of studying these problems also stems from their strong connection to the general framework of optimal (Bayesian) multidimensional mechanism design, an area that has been investigated intensively in both mathematical economics and computer science.The main goal of the project is to develop novel ideas and techniques that can help resolve some of the fundamental open problems in the area of algorithmic pricing, focusing on the case in which the buyer's values are independent. During the next three years, the PIs will work to develop new efficient (approximation) algorithms for optimal pricing problems under various settings, and to understand computational difficulties inherent within them. In addition to the computational aspect, the PIs will also seek to identify better structures of (approximately) optimal pricing schemes. The PIs are particularly interested in characterizing classes of distributions and buyer preferences for which there exist simple, easy-to-implement pricing schemes that can extract most of the optimal revenue, or providing counterexamples that exhibit large gaps between revenues obtained from complex and simple pricing schemes.Results obtained in the proposed research would complement the already extensive economics literature on optimal pricing and multidimensional mechanism design, by offering perspectives through the lens of algorithms, approximation, and complexity. The PIs will broadly disseminate results obtained in the proposed research. The PIs will mentor PhD students and promote undergraduate research by involving them in accessible research projects related to this project.