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

职业：大规模多智能体系统中的战略交互、学习和动态：通过图限制实现可处理性

• 批准号: 2340289
• 负责人: Francesca Parise
• 金额: $ 55万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-02-01 至 2029-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2340289&HistoricalAwards=false
• 关键词: CAREER; Strategic; Interactions; Learning; Dynamics

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.

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