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

多智能体系统的特点是存在大量的用户以复杂的方式进行交互。例子包括在线市场中的卖家竞争，交换数据包的自治系统，以及通过社交网络进行交互的人。对这种网络相互作用进行严格的理论分析，对于支持规划者和决策者设计更好的社会技术基础设施和法规，例如改善安全、效率和福利至关重要。然而，现代多智能体系统的规模越来越大，其动态性质，引入了新的挑战，分析和控制。该项目旨在通过开发一个理论框架来克服这些挑战，该框架可以通过使用图限制来跟踪和鲁棒地捕获大型网络系统中的异构交互。这样的框架将导致可认证的算法的发展，分析，学习和控制的大型多智能体系统，解决主要的挑战，如存在的动态人口，动态互连和计算的易处理性问题。该项目中引入的新视角将使在线市场，决策相关学习，机器人技术和网络系统安全等应用领域的理论和实践取得进展。研究活动将与教学和推广工作相结合，为小学，高中和本科生提供复杂网络系统领域令人兴奋的挑战。该项目的关键创新将是展示如何将图极限理论与博弈论结合使用，动力系统理论和网络优化，旨在设计一种新的框架，用于时变网络环境中大型但有限的多智能体动态过程的易于分析。这一结果将通过两个主要步骤实现。首先，图极限将被用来定义网络系统的易处理的无限人口模型，同时保持代理的异质性。其次，这种无限种群模型的见解和控制策略将应用于大型但有限的网络，并在网络规模方面提供正式的性能保证。该项目将说明这种图极限方法对广泛类别的网络过程的好处，包括：i）策略交互，ii）多智能体学习和iii）非线性成对交互动力学。在所有这些设置中，使用低维图极限表示而不是非结构化有限网络将导致解决方案，保证在快速变化和增长的网络中是计算上易于处理的，渐近最优的和鲁棒的。理论结果将在真实的世界网络以及涉及机器人群的实验室实验中得到验证。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.