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 的法定使命，并被认为是值得的。通过使用基金会的智力优势和更广泛的影响审查标准进行评估来提供支持。