CAREER: Efficient Learning of Equilibria in Dynamic Bayesian Games with Nash, Bellman and Lyapunov

职业生涯：与纳什、贝尔曼和李亚普诺夫一起有效学习动态贝叶斯博弈中的均衡

• 批准号: 2238838
• 负责人: Lichun Li
• 金额: $ 50万
• 依托单位: Florida State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-05-01 至 2028-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2238838&HistoricalAwards=false
• 关键词: CAREER; Efficient; Learning; Equilibria; Dynamic

Dynamic Bayesian games characterize long-term interactions among multiple organizations or agents with private information that changes over time. The balance among the agents occurs when every agent has the best response to the others’ strategies. At this equilibrium, agents strategically exploit their private information to gain long-term benefits. Dynamic Bayesian games have broad applications in cyber, physical, economic, and social systems like cyber security, resource allocation, war field, market share, and governance of social media. The main difficulty in bringing the intelligence of the game into the society and the economy is the extremely high computational complexity of the equilibrium. Currently, only supercomputers can handle the computation. This project proposes an innovative method that integrates AI, control theory, and game theory to provide efficient computation algorithms such that the computation can be handled on typical PCs, which makes it possible to fight efficiently and intelligently against millions of cyber-attacks, to rapidly allocate resources in 6G ultra-dense networks in a near-optimal way, and to automate the governance of metaverse in real-time. The project will build an initial model of a support system for female engineers, including a freshman course to enhance female students’ interest in engineering and early research opportunities to encourage female students to pursue further engineering careers. Meanwhile, the project will regularly deliver the research results to the public using narratives in summer camps in cooperation with the Challenger Learning Center, STEM events, and open house events. This project aims at breaking the curse of time in Bayesian games and develop efficient algorithms to compute the perfect Bayesian equilibrium in long/infinite horizon stochastic Bayesian games with typical PCs. Computing equilibria in dynamic Bayesian games is extremely difficult. Current algorithms need to compute equilibrium for every possible information set. The total number of possible information sets grows exponentially with respect to time, and hence current algorithms soon exhaust computing resources. This project will break the curse of time through three innovative approaches. First, the Bellman equation in dynamic Bayesian games suggests that the current stage equilibrium can be computed based on the value function in the future, so evaluating the Nash equilibrium at all information sets is unnecessary. Second, Lyapunov-like energy functions established based on our prior work promise to solve the Bellman equation efficiently. Third, our proposed dual neural network structure has great potential for approximating the value function with time-insensitive structures without introducing the curse of dimensionality. This project will develop a video game to test the algorithms against humans in real-time. This algorithm has great potential to automate and intellectualize defense strategies in security problems, coordination strategies in multi-agent systems, resource allocation in 6G ultra-dense networks, governance of metaverse, and much more. As the algorithms can be run on typical PCs, it will allow many more scientists and researchers to investigate the complicated equilibrium behavior in general stochastic Bayesian games.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.

动态贝叶斯博弈描述了多个组织或代理之间的长期交互，这些组织或代理具有随时间变化的私人信息。当每个代理人对其他代理人的策略都有最佳反应时，代理人之间的平衡就会发生。在这个均衡中，代理商战略性地利用他们的私人信息来获得长期利益。动态贝叶斯博弈在网络、物理、经济和社会系统中有着广泛的应用，如网络安全、资源分配、战场、市场份额和社会媒体治理。将博弈的智能化引入社会和经济的主要困难在于均衡的极高计算复杂性。目前，只有超级计算机可以处理计算。该项目提出了一种创新的方法，将人工智能，控制理论和博弈论相结合，提供高效的计算算法，使计算可以在典型的PC上处理，这使得可以有效和智能地对抗数百万次网络攻击，以接近最佳的方式快速分配6 G超密集网络中的资源，并实时自动化Metaverse的治理。该项目将为女工程师建立一个支助系统的初步模式，包括一门提高女学生对工程学兴趣的大一课程，以及鼓励女学生进一步从事工程职业的早期研究机会。与此同时，该项目将与挑战者学习中心、STEM活动和开放日活动合作，在夏令营中使用叙事方式定期向公众提供研究成果。本项目旨在打破贝叶斯博弈中的时间诅咒，并开发有效的算法来计算长/无限时域随机贝叶斯博弈中的完美贝叶斯均衡。在动态贝叶斯博弈中计算均衡是非常困难的。目前的算法需要为每个可能的信息集计算均衡。可能的信息集的总数随时间呈指数增长，因此当前的算法很快就会耗尽计算资源。该项目将通过三种创新方法打破时间的诅咒。首先，动态贝叶斯博弈中的Bellman方程表明，当前阶段的均衡可以基于未来的价值函数来计算，因此在所有信息集上评估纳什均衡是不必要的。其次，基于我们先前的工作建立的类Lyapunov能量函数保证有效地求解Bellman方程。第三，我们提出的双神经网络结构具有很大的潜力，可以用时间不敏感的结构来近似值函数，而不会引入维数灾难。该项目将开发一款视频游戏，以实时测试人类的算法。该算法具有很大的潜力，可以自动化和智能化安全问题中的防御策略，多代理系统中的协调策略，6 G超密集网络中的资源分配，Metaverse的治理等等。由于算法可以在典型的PC上运行，它将允许更多的科学家和研究人员研究一般随机贝叶斯博弈中的复杂均衡行为。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。