Incremental Multiple Oracle

Wepresentaframeworkforcomputingapproximatemixed-strategy Nash equilibria of continuous-action games. It is a modification of the traditional double oracle algorithm, extended to multiple players and continuous action spaces. Unlike prior methods, it maintains fixed-cardinality pure strategy sets for each player. Thus, unlike prior methods, only a constant amount of memory is necessary. Furthermore, it does not require exact metagame solving on each iteration, which can be computationally expensive for large metagames. Moreover, it does not require global best-response computationoneach iteration, whichcanbecomputationallyexpensive or even intractable for high-dimensional action spaces and general games. Our method incrementally reduces the exploitability of the strategy profile in the finite metagame, pushing it toward Nash equilibrium. Simultaneously, it incrementally improves the pure strategies that best respond to this strategy profile in the full game. We test our method on various continuous games. It obtains approximate mixed-strategy Nash equilibria with low exploitability.

Authors

• Carlos Martin Carnegie Mellon University
• Tuomas Sandholm Carnegie Mellon University, Strategy Robot, Inc. , Optimized Markets, Inc. , & Strategic Machine, Inc.

Keywords

• game theory
• game solving
• equilibrium finding
• continuous games