Simple Strategy-Iteration with Dantzig's Rule is not Strongly Polynomial on Turn-Based Deterministic Games

We study turn-based deterministic zero-sum games with discounted and long-run average costs. For discounted costs, we establish exponential and superpolynomial iteration lower bounds for the simple strategy-iteration method with Dantzig's rule under unrestricted costs and unit weights, respectively.