Tight worst case for the double oracle algorithm

The double oracle algorithm (DO) is an iterative algorithm that computes a mixed-strategy Nash equilibrium of a game without fully expanding the players' strategy spaces. It is the basis of Policy-Space Response Oracles (PSRO) and many related population-based methods for multiagent reinforcement learning, where each iteration trains a new policy. In this paper, we give a general, explicit construction that maximizes the number of iterations DO needs to converge. Specifically, for all integers $M,N\ge 2$, we give an explicit $M$-by-$N$ matrix that forces DO, starting from the first row and column, to run for $M+N-2$ iterations. This equals the trivial worst-case upper bound. DO does not specify how to choose among multiple Nash equilibria or best responses, and our construction works for every choice. It also works when the equilibrium and best-response oracles are inexact, as in PSRO, provided they are sufficiently accurate. To our knowledge, this is the first such general construction. We formalize these results in Lean.