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

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

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.