AF: Small: New Directions for Simplicity versus Optimality in Mechanism Design

该项目旨在开发新的算法技术，用于设计忠实地模拟消费者行为和其他现实世界约束的市场机制。这项工作属于算法机制设计的范围，它涉及经济系统的优化，其中许多具有冲突目标的各方竞争占有资源。该领域的见解适用于各种市场的设计，无论大小、实体或电子，并在新兴电子市场（如在线广告、云市场、拼车行业、众包市场等）的兴起中发挥着越来越重要的作用。该项目关注的目标是最大化卖方的收入或分配的经济效率。对于这些目标中的每一个，目标都是开发易于实现、广泛适用且接近最优的解决方案。这个项目的第一部分将集中在所谓的买多约束下的收益最大化目标。这种自然约束要求卖方不能限制买方与该机制交互的次数，并且在大多数现实环境中都得到满足。施加这一约束为最优机制提供了一个良好的结构，因此在没有任何比以前已知的进一步假设的情况下，应该允许更好的近似。该项目的第二部分将开发在线环境下有效资源分配的算法，在这种情况下，买家随着时间的推移到达市场，必须在不知道未来需求的情况下做出分配决策。目标是开发简单的基于定价的分配机制，但却能实现近乎最佳的性能。该项目的第三部分将考虑买家不确定其当前或未来价值的设置，并将研究诸如退款，免费试用和过度使用费用等定价策略的有效性，以减少买家面临的风险。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project aims to develop new algorithmic techniques for designing market mechanisms that faithfully model consumer behavior and other real-world constraints. This work lies within the purview of algorithmic mechanism design, which deals with the optimization of economic systems wherein many parties with conflicting objectives compete for possession of resources. Insights from this area apply to the design of all kinds of markets – big or small, brick-and-mortar or electronic – and play an increasingly important role in the rise of new electronic marketplaces such as online advertising, the cloud market, the rideshare industry, crowdsourcing marketplaces, etc. The project focuses on the objectives of maximizing the seller's revenue or the economic efficiency of the allocation. For each of these objectives, the goal is to develop solutions that are simple to implement, broadly applicable, and near optimal.The first part of this project will focus on the revenue-maximization objective under a so-called buy-many constraint. This natural constraint requires that the seller cannot limit the number of times a buyer can interact with the mechanism, and is satisfied in most real-world contexts. Imposing this constraint imparts a nice structure to the optimal mechanism, and should thereby allow for much better approximations in the absence of any further assumptions than previously known. The second part of this project will develop algorithms for efficient resource allocation in online settings where buyers arrive in the market over time and allocation decisions must be made without knowing future demand. The goal is to develop simple pricing-based allocation mechanisms that nevertheless achieve near-optimal performance. The third part of this project will consider settings where buyers are uncertain about their current or future values, and will study the effectiveness of pricing strategies such as refunds, free trials, and overuse fees as vehicles for lessening the risk faced by the buyer.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.