CRII: RI: Analysis and Applications of Multi-Level Games

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). With artificial intelligence (AI) becoming progressively more competent and ubiquitous, an AI entity is more likely to find itself operating in a complex, dynamic environment along with other intelligent entities all with different goals and disparate information or beliefs about their environment and each other. Examples include bidders in an online ad auction, algorithmic trading agents in a financial market, (cyber)attackers and defenders in a network, a hierarchy of policymakers formulating a decentralized epidemic response plan in a decentralized manner, and so on. As such, game theory, the systematic study of such multi-agent strategic interactions (or, games as they are called), is becoming increasingly fundamental to AI research and practice. Empirical game-theoretic analysis (EGTA) is a principled framework for (approximately) reasoning about games that are beyond the scope of traditional, analytical game-theoretic methods either because the games are too complex or because obtaining information about possible plays of the game is too expensive. This project seeks to make fundamental methodological improvements to the EGTA framework by constructing finer- grained models (i.e., more accurate approximations) of the game under consideration than those prevalent in the state of the art. Specifically, the aim of the project is to adapt EGTA to multi-level game model forms: strategic interactions that can be represented in the form of a directed, rooted tree. Extensive-form games (EFGs) are a classic example of this class of games that capture temporal patterns in agent activity, information revelation, and possible stochastic events (acts of Nature). Current EGTA practice abstracts all such temporal patterns away in a simulator (e.g., an agent-based model) that is queried to obtain payoff data for strategy combinations over players but induces a coarser game model that is essentially normal-form and does not reflect such patterns. This project will take the next step in EGTA design by explicitly incorporating features of the underlying game tree into the empirical game model itself and tackling the resulting conceptual and computational design challenges such as striking a balance between model granularity (which leads to better approximation) and per-iteration computational burden. The second phase of the project will seek to transfer knowledge gained from development of EGTA for EFGs to similar treatments of other tree-based game model forms. Advances in this project can significantly improve our understanding of systems that comprise interacting AI agents employing highly sophisticated strategies (such as deep reinforcement learning algorithms), and in turn inform robust design of such agents. 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.