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

Florida State University, Tallahassee FL

Investigators

Abstract

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.