CAREER: Towards a Predictive Theory of Algorithmic Mechanism Design

点击翻译按钮获取中文摘要

Traditional algorithms are designed to take a given input and produce the best achievable output. However, as modern algorithms increasingly influence ads we see, people we date, and many other aspects of our lives, their input is no longer directly given but instead is solicited from strategic agents. Importantly, these same agents care deeply about the output produced, and they will manipulate their input to achieve more desirable outcomes. These manipulations are not hypothetical, but well-documented in multi-billion-dollar industries like healthcare, cloud computing, and online dating. Modern algorithms can however benefit from utilizing tools from Game Theory to successfully interact with strategic agents. The field of Algorithmic Mechanism Design emerged at the intersection of Economics and Computer Science precisely to tackle this pressing challenge. This project will advance this rapidly-growing research agenda. The project also contains an educational plan to develop a graduate course to train future researchers and an undergraduate course to train future engineers who will deploy these algorithms.More specifically, the overarching focus of this proposal is to extend the vast existing theory from descriptive to prescriptive. For example, extensive prior work successfully describes why simple mechanisms are ubiquitous in daily interactions with unsophisticated designers, but does not yet prescribe novel mechanisms for a sophisticated designer with the data and means to finely optimize. The project will implement this agenda in three key directions: (a) the analysis of simple revenue-maximizing auctions beyond traditional approximation guarantees, (b) the design of novel revenue-maximizing auctions for buyers who learn how to bid strategically over time, and (c) the development of fundamental building blocks for incentive compatible cryptocurrencies. The research in all three directions will draw on broad toolkits from both Computer Science and Economics and continue forging new connections between these fields.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.