CAREER: Strategic Interactions, Learning, and Dynamics in Large-Scale Multi-Agent Systems: Achieving Tractability via Graph Limits

Multi-agent systems are characterized by the presence of a large number of users interacting in complex ways. Examples include sellers competing in online markets, autonomous systems exchanging data packages, and people interacting over social networks. Rigorous theoretical analysis of such network interactions is fundamental to support planners and policy makers in designing better socio-technical infrastructure and regulations, improving for example security, efficiency and welfare.

The increasing size of modern multi-agent systems and their dynamic nature, however, introduces novel challenges for analysis and control. This project seeks to overcome these challenges by developing a theoretical framework that can tractably and robustly capture heterogeneous interactions in large network systems via the use of graph limits. Such framework will result in the development of certifiable algorithms for analysis, learning and control of large multi-agent systems, addressing main challenges such as the presence of dynamic populations, dynamic interconnections and issues of computational tractability.

The novel perspective introduced in this project will enable both theoretical and practical advances in application areas including online markets, decision-dependent learning, robotics, and security of network systems. Research activities will be complemented with teaching and outreach efforts, providing exposure to exciting challenges in the area of complex network systems to elementary, high school and undergraduate students.

The key innovation of this project will be to show how the theory of graph limits can be used in combination with game theory, dynamical systems theory and network optimization to devise a novel framework for tractable analysis of large but finite multi-agent dynamical processes in time-varying network settings. This result will be achieved via two main steps.

First, graph limits will be used to define tractable infinite population models of network systems while maintaining agents’ heterogeneity. Second, insights and control policies derived for such infinite population models will be applied to large but finite networks, with formal performance guarantees in terms of the network size. This project will illustrate the benefit of this graph limit approach for broad classes of network processes including: i) strategic interactions, ii) multi-agent learning and iii) nonlinear pairwise interaction dynamics.

In all these settings the use of low-dimensional graph limit representations instead of unstructured finite networks will result in solutions that are guaranteed to be computationally tractable, asymptotically optimal, and robust in the presence of fast-changing and growing networks. Theoretical results will be validated over real world networks, as well as lab experiments involving swarms of robots.

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.