AF:Small: The Efficiency of Clock Auctions

定价是一种基本工具，在日常生活中被广泛使用，在实现有效的资源分配结果方面发挥着至关重要的作用。对于那些非常稀缺和需求量很大的商品，给它们定一个高价格可以确保它们只会被那些高度重视它们的买家购买。因此，在适当的定价下，商品可以被有效地分配，卖方也可以获得最大的收益。然而，确定适当的价格需要对每种商品的需求有所了解，而这些信息通常是不公开的。拍卖通过与感兴趣的买家互动，并利用从这些互动中获得的信息来发现合适的价格，为这个问题提供了一个解决方案。机制设计（经济学中的一个领域）的文献提供了一系列著名的拍卖，这些拍卖以不同的方式与买家互动，旨在实现社会福利或收入等目标的最大化。从计算机科学家的角度来看，拍卖本质上是一种算法，它从买家那里获取信息作为输入，并返回定价和资源分配作为输出。因此，在过去的二十年里，计算机科学家利用他们在算法设计和分析方面的悠久传统来分析经典拍卖或设计新的拍卖。这个项目的重点是时钟拍卖，一类拍卖，最近被证明拥有一个非常吸引人的隐私和激励属性的列表，并为买家提供一个简单的界面和一个明确的主导战略。然而，对这些拍卖的算法潜力的理解仍然非常有限，这个项目的目标是通过从算法的角度研究时钟拍卖来解决这个问题。该项目将把时钟拍卖作为一种算法，以评估它们为充分研究的资源分配问题获得有效结果的能力。与经济学中通常采用的方法不同，该项目将考虑更苛刻的环境，在这些环境中，实现完全效率可能是不可能的，并使用最坏情况或平均情况近似因子，根据最优基准来衡量拍卖的表现。这项工作将为实际时钟拍卖的设计和分析奠定基础，并深入了解拍卖设计师可以使用时钟拍卖实现的性能保证。这项工作还将统一计算机科学和经济学文献中的理论工具，这些理论工具可用于设计此类拍卖。这项研究的结果将提供一套算法工具，拍卖设计师可以使用这些工具来生产具有令人信服的激励保证的高性能实际拍卖，为广泛要求的“拍卖的简单性”提供及时的贡献。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Pricing is a fundamental tool that is very widely used on a daily basis and plays a crucial role in reaching effective resource allocation outcomes. For goods that are very scarce and in high demand, assigning a high price to them ensures that they will be requested only by buyers who value them highly. As a result, given an appropriate pricing, the goods may be efficiently allocated, and the seller may also maximize her revenue. Assigning appropriate prices, however, requires some knowledge regarding the demand for each good, and this information is usually not publicly known. Auctions provide a solution to this problem by interacting with the interested buyers and using the information gained from these interactions to discover appropriate prices. The literature on mechanism design, a field in economics, has provided a list of celebrated auctions, which interact with the buyers in different ways aiming to maximize objectives such as social welfare or revenue. From the perspective of a computer scientist, auctions are, in essence, algorithms that take information from the buyers as input and return a pricing and a resource allocation as output. As a result, in the last two decades, computer scientists have leveraged their long tradition in algorithm design and analysis to analyze classic auctions or design new ones. The focus of this project is on clock auctions, a class of auctions which was recently shown to possess a list of very appealing privacy and incentive properties, and to provide the buyers with a simple interface and a clearly dominant strategy. However, understanding of the algorithmic potential of these auctions is still very limited, and the goal of this project is to address this issue by studying clock auctions from an algorithmic standpoint.This project will approach clock auctions as a class of algorithms in order to evaluate their ability to reach efficient outcomes for well-studied resource-allocation problems. Rather than focusing on the conditions under which these auctions can reach the optimal outcome, which is often the approach in economics, this project will instead consider more demanding settings, where achieving full efficiency may be impossible, and measure the performance of the auctions against the optimal benchmark using worst-case, or average-case, approximation factors. This work will lay the foundations for the design and analysis of practical clock auctions and develop a deeper understanding of the performance guarantees that an auction designer can achieve using clock auctions. This work will also unify the theoretical tools from both the computer-science and economics literature that can be used for designing such auctions. The results of this research will provide a set of algorithmic tools that an auction designer can use in order to produce high-performance practical auctions with compelling incentive guarantees, providing a timely contribution toward the widely-demanded "simplicity in auctions."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.