Double Oracle Algorithm for Computing Equilibria in Continuous Games

• DOI: 10.1609/aaai.v35i6.16641
• Publication Date: 2022-09-08T18:43:10Z
• Authors: Lukáš Adam; Rostislav Horčík; Tomáš Kasl; Tomáš Kroupa
• Keywords: FOS: Computer and information sciences; Computer Science - Computer Science and Game Theory; Optimization and Control (math.OC); FOS: Mathematics; 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology; Mathematics - Optimization and Control; Computer Science and Game Theory (cs.GT)

Many efficient algorithms have been designed to recover Nash equilibria of various classes finite games. Special continuous games with infinite strategy spaces, such as polynomial games, can be solved by semidefinite programming. In general, however, are not directly amenable computational procedures. this contribution, we develop an iterative generation technique for finding a equilibrium in whole class two-person zero-sum compact sets. The procedure, which is called the double oracle algorithm, has successfully applied large past. We prove convergence algorithm equilibrium. Moreover, guaranteed approximate finitely-many steps. Our numerical experiments show that it outperforms fictitious play on several examples appearing literature. particular, provide detailed analysis version Colonel Blotto game.