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

在这个项目中，PI计划研究算法定价中的基本问题，并提高对该领域的理解。考虑买方对卖方提供的多个异构项目感兴趣的设置。虽然物品对买方的价值是私人的，但卖方可以利用典型买方偏好的随机信息来最大化其预期收入。在过去的十年中，各种设置下的最优定价问题在计算机科学文献中受到了相当大的关注，并从算法和复杂性理论的角度进行了研究，但许多基本问题仍然是开放的。研究这些问题的动机也来自于它们与最优规划的一般框架的紧密联系。（贝叶斯）多维机制设计，一个在数理经济学和计算机科学中都得到深入研究的领域。该项目的主要目标是开发新的想法和技术，以帮助解决算法定价领域的一些基本开放问题，重点放在买方价值独立的情况下。在接下来的三年里，PI将致力于开发新的有效（近似）算法，用于各种设置下的最优定价问题，并了解其中固有的计算困难。除了计算方面，PI还将寻求确定（近似）最优定价方案的更好结构。PI特别感兴趣的是描述分布和买方偏好的类别，对于这些类别，存在简单，易于实施的定价方案，可以提取大部分最佳收入，或提供反例，显示从复杂和简单的定价方案获得的收入之间的巨大差距。在拟议的研究中获得的结果将补充已经广泛的最优定价和多维机制的经济学文献设计，通过算法、近似和复杂性的透镜提供视角。主要研究员将广泛传播拟议研究中取得的成果。PI将指导博士生，并通过让他们参与与本项目相关的无障碍研究项目来促进本科生研究。

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.