The fields of Algorithmic Game Theory and Mechanism Design study the strategic interaction of multiple agents. The growth of available data and computational power enable these fields to make a real impact in understanding the agents' incentives and improving their decisions and the resulting social outcomes. A grand challenge is the presence of uncertainty and risk, which calls for new game theoretic models and algorithmic techniques. As a brief example, consider going to the airport to catch a flight. In uncertain traffic and a deadline, risk considerations are critical and a less risky, albeit longer, route might be preferable over one that minimizes expected delay. But the fundamental questions do not depend merely on one individual's preferences, but on a broader social model that captures many individuals and their interactions. For instance, how does strategic risk-aware routing by multiple users affect route selection and the overall congestion in the network? And how different is the individually optimal (equilibrium) route selection of multiple risk-averse users from a socially optimal traffic allocation?
This research program outlines an agenda for investigating how uncertainty and risk aversion transform traditional models and methodologies employed by Algorithmic Game Theory and Mechanism Design. It will import models and tools from areas with a rich tradition in studying risk, such as Financial Engineering, and adapt them to multi-user computational environments. Ultimately, the goal is to develop new game theoretic models and analysis, as well as new algorithms for solving the computational questions in these models.
The program focuses on problems that arise in complex multi-user systems in the real world and has the potential to improve a variety of applications that involve uncertainty and risk-averse users, for example, reduce congestion in transportation and telecommunication networks, enhance the quality of streaming applications over the Internet, increase the safety and security in military operations, autonomous and robot navigation, etc. From a research standpoint, the transformative potential of the proposed research is to fundamentally shift thinking about uncertain multi-user environments away from optimizing simple expected performance and instead towards a systematic treatment of contingencies and risk.
