CRII: AF: Practical Auction Design Using the Deferred-Acceptance Framework

CRII：AF：使用延期接受框架的实用拍卖设计

• 批准号: 1755955
• 负责人: Vasilis Gkatzelis
• 金额: $ 17.49万
• 依托单位: Drexel University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-02-01 至 2020-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1755955&HistoricalAwards=false
• 关键词: CRII; AF; Practical; Auction; Design

As the world grows increasingly interconnected, a more effective utilization of its scarce resources becomes possible through an unprecedented number of auctions. On a daily basis, human and software agents compete for an extremely diverse set of resources, ranging from the advertising space on web sites and the goods sold on online auction sites, to the electrical power supply that supports large cities and the landing slots of the world's busiest airports. Were it not for the auctions that regulate these resource allocation processes, massive amounts of social utility would be wasted; hence, it is imperative that these auctions are designed to the highest standard. Some of the optimization problems involved in designing such resource allocation mechanisms can be highly demanding from a computational standpoint. In reality, the design process is even more challenging, as the agents competing for these resources may be strategic and have their own interests at heart. This project approaches resource allocation problems from the perspective of the designer who chooses the rules of the auction aiming to maximize her own objectives, such as efficiency, revenue, or fairness, despite the strategic behavior of the participants. The long literature on game theory and mechanism design has produced several celebrated auctions that maximize these objectives while at the same time providing attractive theoretical guarantees regarding the incentives of the participating agents, but many of these auctions are rarely used in practice. Two important drawbacks that render these auctions impractical are that: i) it may be non-trivial for the participating bidders to verify these auctions' incentive guarantees, and ii) these auctions often require that the bidders reveal their private preferences to the auctioneer and trust the implementation of the auction.The long-term goal of this project is to develop a deeper understanding of the performance guarantees that an auction designer can achieve using practical auctions that avoid these drawbacks. Recent work by economists has proposed refined incentive properties that even non-experts can verify, as well as a framework for designing auctions that satisfy these incentive properties. This project aims to evaluate the performance of these auctions, and to extend the auction design framework to capture a much wider family of problem instances. As a result, it can lead to the design of novel and practical auctions that maximize the desired objectives, while contributing the algorithmic perspective of computer science to a line of research initiated by economists. The proposed research combines techniques from both approximation algorithms and mechanism design. Specifically, the auction design framework that this project aims to analyze and generalize crucially depends on the design of backward greedy algorithms for deciding how the available resources should be allocated. Unlike forward greedy algorithms, the approximation guarantees achievable by backward greedy algorithms are not well understood even within the computer science literature, so this project will also contribute toward a deeper understanding of this interesting class of algorithms.

随着世界日益相互联系，通过前所未有的拍卖数量，更有效地利用其稀缺资源成为可能。每天，人类和软件代理都在争夺各种各样的资源，从网站上的广告空间和在线拍卖网站上出售的商品，到支持大城市的电力供应和世界上最繁忙机场的着陆位置。如果没有拍卖来规范这些资源分配过程，大量的社会效用将被浪费;因此，这些拍卖的设计必须达到最高标准。从计算的角度来看，设计这种资源分配机制所涉及的一些优化问题可能要求很高。实际上，设计过程更具挑战性，因为竞争这些资源的代理可能具有战略意义，并且有自己的利益。本项目从设计师的角度来探讨资源分配问题，设计师选择拍卖规则的目的是最大化自己的目标，如效率，收入或公平，尽管参与者的战略行为。博弈论和机制设计的长期文献已经产生了几个著名的拍卖，最大限度地提高这些目标，同时提供有吸引力的理论保证参与代理人的激励，但这些拍卖很少在实践中使用。使这些拍卖不切实际的两个重要缺点是：i）对于参与的投标人来说，验证这些拍卖的激励保证可能是重要的，以及ii）这些拍卖通常要求出价人向拍卖师透露他们的私人偏好，并信任拍卖的实施。这个项目的长期目标是开发一个更深入的了解性能保证，拍卖设计师可以实现使用实际拍卖，避免这些缺点。经济学家最近的工作提出了细化的激励属性，即使是非专家也可以验证，以及设计满足这些激励属性的拍卖的框架。这个项目的目的是评估这些拍卖的性能，并扩展拍卖设计框架，以捕捉更广泛的家庭的问题的情况。因此，它可以导致设计新颖和实用的拍卖，最大限度地提高预期目标，同时为经济学家发起的一系列研究提供计算机科学的算法视角。所提出的研究结合了近似算法和机制设计的技术。具体来说，拍卖设计框架，本项目的目的是分析和推广至关重要的依赖于设计的向后贪婪算法，以决定如何分配可用的资源。与前向贪婪算法不同，后向贪婪算法实现的近似保证即使在计算机科学文献中也没有得到很好的理解，因此该项目也将有助于更深入地理解这类有趣的算法。

项目成果

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

Online Nash Social Welfare Maximization with Predictions

在线纳什社会福利最大化与预测

• 发表时间: 2022
• 期刊: Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
• 作者: Gorokh, Artur;Banerjee, Siddhartha;Jin, Billy;Gkatzelis, Vasilis
• 通讯作者: Gkatzelis, Vasilis

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

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

Fair and Efficient Memory Sharing: Confronting Free Riders

公平高效的内存共享：对抗搭便车者

• 发表时间: 2019
• 期刊: Proceedings of the ... AAAI Conference on Artificial Intelligence
• 作者: Friedman, Eric J.;Gkatzelis, Vasilis;Psomas, Christos-Alexandros;Shenker, Scott
• 通讯作者: Shenker, Scott