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

Drexel University, Philadelphia PA

Investigators

Abstract

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.