AF: Small: New Directions in Algorithmic Mechanism Design

AF：小：算法机制设计的新方向

• 批准号: 1617505
• 负责人: Shuchi Chawla
• 金额: $ 45万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1617505&HistoricalAwards=false
• 关键词: AF; Small; New; Directions; Algorithmic

This project employs mechanism design theory to address resource allocation problems arising in the context of large computational systems with many participants. Mechanism design deals with economic systems from the viewpoint of an optimizing designer: the designer would like to design a system or protocol whereby the selfish optimization of individual participants leads to a desirable aggregate behavior. In the context of resource allocation, for example, mechanism design theory specifies how a seller or owner of resources should allocate these resources to buyers so as to achieve the maximum possible revenue or economic efficiency. However, optimal mechanisms prescribed by the theory are often hard to compute, complex to implement, and over-sensitive to fine details of the input. These challenges are exacerbated in settings that are combinatorial, dynamic or online (as opposed to one-shot), or involve informational dependencies among different buyers. The PI will investigate solution concepts that are simultaneously near-optimal as well as practical; this would bring the theory of mechanism design closer to practice. Over the last decade new electronic marketplaces-for example, cloud platforms, platforms for a sharing economy, and digital goods stores-have arisen in a largely ad hoc manner. This project aims to establish strong theoretical underpinnings for the design of such marketplaces, thereby guiding the next wave of development in this area.The project will address applications such as allocation of cloud services, as well as resource allocation in dynamic settings where buyers repeatedly request resources (e.g. digital goods such as music, apps, and games), and their value for a resource varies stochastically over time. One challenge in these contexts is that buyers may strategize about how their current actions affect their future payoffs and the mechanism designer must take such strategizing into account. Another challenge is in dealing with the combinatorial nature of resource requests owing to the multiple kinds of resources available (e.g., CPU, storage). This project will employ pricing-based mechanisms as a solution concept that simultaneously achieves near-optimality, simplicity, detail-freeness, and robustness to noise in the input.

这个项目使用机制设计理论来解决在有许多参与者的大型计算系统的背景下出现的资源分配问题。机制设计从优化设计者的角度来处理经济系统：设计者想要设计一个系统或协议，在这个系统或协议中，个体参与者的自私优化会导致理想的聚合行为。例如，在资源分配的背景下，机制设计理论规定了资源的卖方或所有者应如何将这些资源分配给买方，以实现最大可能的收入或经济效率。然而，该理论规定的最优机制往往难以计算、难以实施，并且对输入的细节过于敏感。这些挑战在组合、动态或在线(而不是一次性)的环境中加剧，或者涉及不同买家之间的信息依赖。PI将研究既接近最优又实用的解决方案概念；这将使机构设计理论更接近实践。在过去的十年里，新的电子市场--例如云平台、共享经济平台和数字商品商店--基本上是以一种临时的方式出现的。该项目旨在为此类市场的设计建立坚实的理论基础，从而指导该领域的下一波发展。该项目将解决云服务分配等应用，以及在买家重复请求资源(例如，音乐、应用程序和游戏等数字产品)且其资源价值随时间随机变化的动态环境中的资源分配。在这些情况下的一个挑战是，买家可能会对他们当前的行为如何影响他们未来的收益进行战略规划，机制设计者必须考虑这种战略规划。另一个挑战是处理由于可用的多种资源(例如，CPU、存储)而导致的资源请求的组合性质。该项目将采用基于定价的机制作为解决方案概念，同时实现近乎最优、简单、无细节和对输入中的噪声的稳健性。