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

AF：小：论最优定价和机制设计的复杂性

• 批准号: 1423100
• 负责人: Mihalis Yannakakis
• 金额: $ 45万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423100&HistoricalAwards=false
• 关键词: AF; Small; Complexity; Optimal; Pricing

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.

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