AF:Small: The Efficiency of Clock Auctions

AF:Small：时钟拍卖的效率

• 批准号: 2008280
• 负责人: Vasilis Gkatzelis
• 金额: $ 35.8万
• 依托单位: Drexel University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-08-01 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008280&HistoricalAwards=false
• 关键词: AF; Small; Efficiency; 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.

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

项目成果

Prior-Free Clock Auctions for Bidders with Interdependent Values

为具有相互依赖价值的投标人提供无优先权的时钟拍卖

• DOI: 10.1007/978-3-030-85947-3_5
• 发表时间: 2021
• 期刊: Symposium on Algorithmic Game Theory
• 作者: Gkatzelis, Vasilis;Patel, Rishi;Pountourakis, Emmanouil;Schoepflin, Daniel
• 通讯作者: Schoepflin, Daniel

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods

• DOI: 10.5555/3535850.3535875
• 发表时间: 2022-01
• 期刊: ArXiv
• 作者: I. Caragiannis;Vasilis Gkatzelis;Alexandros Psomas;Daniel Schoepflin

Deterministic Budget-Feasible Clock Auctions

确定性预算可行的时钟拍卖

• 发表时间: 2022
• 期刊: 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA22
• 作者: Balkanski, Eric;Garimidi, Pranav;Gkatzelis, Vasilis;Schoepflin, Daniel;Tan, Xizhi
• 通讯作者: Tan, Xizhi

Optimal Data Acquisition with Privacy-Aware Agents

通过具有隐私意识的代理实现最佳数据采集

• DOI: 10.1109/satml54575.2023.00023
• 发表时间: 2023
• 期刊: 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML
• 作者: Cummings, Rachel;Elzayn, Hadi;Pountourakis, Emmanouil;Gkatzelis, Vasilis;Ziani, Juba
• 通讯作者: Ziani, Juba

Achieving Proportionality up to the Maximin Item with Indivisible Goods

实现不可分割商品最大最小项目的比例

• 发表时间: 2021
• 期刊: 35th AAAI Conference on Artificial Intelligence (AAAI 2021
• 作者: Baklanov, Artem;Garimidi, Pranav;Gkatzelis, Vasilis;Schoepflin, Daniel
• 通讯作者: Schoepflin, Daniel