A Provable Semi-Infinite Programming Approach for Solving Dynamic Nash Games

Many engineering problems must account for the non-cooperative decisions and actions of multiple players. These problems can be modeled within a game-theoretic framework. The approach herein is to model problems as Nash games, convert them to semi-infinite programs, and leverage provable semi-infinite algorithms to solve the original problem. A particular algorithm that leverages off-the-shelf solvers is used to solve four low-dimensional benchmark problems successfully. Two types of linear quadratic dynamic games are then investigated: ones where each player’s problem is convex and ones where at least one player’s problem is nonconvex. Within each type, variations based on information structure, communication structure, number of players, and semi-infinite objective are considered. The selected algorithm in conjunction with MATLAB’s fmincon successfully solves all cases except the distributed communication case. The numerical solutions approximate theoretical solutions (when they are known) within approximately one percent. Run times varied problem to problem from seconds to days. Capture cases proved challenging as they correspond to singular solutions in optimal control.