  The double oracle algorithm is a popular method of solving games, because it
is able to reduce computing equilibria to computing a series of best responses.
However, its theoretical properties are not well understood. In this paper, we
provide exponential lower bounds on the performance of the double oracle
algorithm in both partially-observable stochastic games (POSGs) and
extensive-form games (EFGs). Our results depend on what is assumed about the
tiebreaking scheme -- that is, which meta-Nash equilibrium or best response is
chosen, in the event that there are multiple to pick from. In particular, for
EFGs, our lower bounds require adversarial tiebreaking, whereas for POSGs, our
lower bounds apply regardless of how ties are broken.
