AF: Small: New Directions in Algorithmic Mechanism Design

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

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.