The Simple Strategy-Iteration Method is Strongly Polynomial for the Turn-Based Deterministic Forward Game

We study Turn-Based Deterministic Forward Games (TBDFGs), the subclass of turn-based deterministic zero-sum games in which no directed cycle contains actions controlled by both players.

This forward condition is strictly weaker than acyclicity: recurrent behavior may be arbitrarily rich within one player's states, while mixed-player feedback cycles are excluded.

Our main contribution separates two algorithmic consequences of this structure.

First, we analyze the simple strategy-iteration method of [11,14], a generic method for TBSGs whose execution neither tests for nor uses the TBDFG property.

We prove that this structure-oblivious algorithm nevertheless has a strongly polynomial guarantee on every TBDFG.

In particular, it terminates after at most $O(n^6m^4\log^4 n)$ simplex pivot steps.

Thus, the forward property acts as a structural certificate for convergence even when the algorithm is not informed that the input has this property.

Second, when the TBDFG structure is known in advance, a backward SCC propagation algorithm is proposed that solves a sequence of deterministic-MDP subproblems and improves the bound to $O(n^3m^2\log^2 n)$ simplex pivot steps.

Together, these results show that forward structure both regularizes the convergence of a general strategy-iteration method and supports a sharper structure-aware algorithm.