CAREER: Algorithms, Incentives, and Information in Strategic Settings

University Of Southern California, Los Angeles CA

Investigators

Abstract

Much of today's economic activity and resource allocation takes place on systems with many strategic actors. Examples include auctions and exchanges for advertising space, matching markets for labor and capital, and congestion-aware GPS navigation systems. These systems have grown larger than ever before in today's networked world, and their behavior is necessarily a confluence of the preferences, beliefs, and strategic behaviors of many, rather than a system designer's intent. Nevertheless, there are two main "knobs" that a designer of such a system can turn in order to influence the equilibrium behavior of its participants: the incentives provided to players in the game, and the information available to them. This proposal adopts the perspective of a designer looking to influence equilibrium outcomes in such systems. The proposed work will separately consider both modes of intervention, namely structuring the incentives provided and carefully revealing information. In each case, the PI will examine the associated algorithmic question: Given the designer's objective, can a near-optimal intervention be computed efficiently? On the incentives front, the focus will be on refining existing theoretical models and algorithmic techniques with the goal of broadening their impact, in particular to settings where heuristic mechanisms and auctions have seen success in practice. On the information front, the proposed work will lay the foundations of an algorithmic theory of information in games, and begin a systematic examination of the computational complexity of intervention through information revelation.