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的法定任务，并使用基金会的知识分子优点和更广泛的影响评估审查标准，被视为通过评估而被视为珍贵的支持。