NSF-BSF: AF: Small: Mechanisms for Auctions and Markets - The Interplay of Incentives and Optimization

Auctions are at the epicenter of algorithmic game theory. From a practical perspective, the importance of auctions stems from their numerous applications, in digital-commerce platforms such as eBay, in huge government-run endeavors like the spectrum auctions, and as the basis for the online advertisement industry. The emergence of such huge auctions has led to the necessity of designing auctions that can handle vast amounts of data.

From a mathematical point of view, which is the focus of this project, auctions present an elegant mathematical model that allows one to study the intersecting roles of various elements that are crucial for market design, such as optimization, incentives, and computational and information-theoretic limitations. Indeed, the rise of algorithmic mechanism design can be attributed to the demand for mechanisms which are computationally tractable and yet are powerful enough to properly handle the incentives of the players.

The rich toolbox of theoretical computer science for designing and analyzing large-scale systems is a perfect candidate for applying in the context of auctions.

This project addresses the clash of incentives and optimization objectives in combinatorial auctions. In some settings the underlying optimization problem is easy from a computational point of view, but it is impossible to incentivize the players properly. An example domain here is the classic bilateral trade problem introduced by Myerson and Satterthwaite.

The small size of the problem makes it computationally unchallenging. However, taking into account the incentives of agents limits the set of applicable algorithms. In contrast, combinatorial auctions involve a large number of players and multiple resources to be allocated.

In these settings, the optimization task of welfare maximization itself is challenging. This project addresses the difficulty of welfare maximization in several fundamental settings, as well as the difficulty of reconciling existing algorithmic techniques with the requirement of incentive-compatibility. Whether computationally efficient approximation algorithms are more powerful than their incentive-compatible counterparts has been the subject of extensive research.

Only very recently, the first gap between the power of the two families was demonstrated. The goal of this project is to prove a significant separation between the power of incentive-compatible mechanisms and algorithms without this requirement.

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.