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