AF: Small: New Directions in Algorithmic Mechanism Design

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

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.