Simple Strategy-Iteration with Dantzig's Rule is not Strongly Polynomial on Turn-Based Deterministic Games
Abstract
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. To the best of our knowledge, we establish for the first time that the method is not strongly polynomial, and this remains true even when all action costs belong to {−1,0,1}. For long-run average costs, we extend the Dantzig counterpart in~\cite{zhongye2026} to the two-player setting and prove that it terminates at an optimal strategy profile. However, a similar counterexample construction establishes an exponential iteration lower bound for termination with unrestricted costs. This construction does not extend to unit weights, for which we prove that the algorithm admits a strongly polynomial implementation.
Related
- Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
- SDDP has polynomial iteration complexity in the horizon
- A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
- Subexponential Approximation of the Permanent in Deterministic Polynomial Time
- Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
BibTeX
@misc{mei2026simple,
title = {{Simple Strategy-Iteration with Dantzig's Rule is not Strongly Polynomial on Turn-Based Deterministic Games}},
author = {Sanyou Mei},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27386},
eprint = {2610.27386},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27386},
}
RIS
TY - UNPB
TI - Simple Strategy-Iteration with Dantzig's Rule is not Strongly Polynomial on Turn-Based Deterministic Games
AU - Sanyou Mei
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.27386
UR - https://arxiv.org/abs/2610.27386
AB - 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. To the best of our knowledge, we establish for the first time that the method is not strongly polynomial, and this remains true even when all action costs belong to {−1,0,1}. For long-run average costs, we extend the Dantzig counterpart in~\cite{zhongye2026} to the two-player setting and prove that it terminates at an optimal strategy profile. However, a similar counterexample construction establishes an exponential iteration lower bound for termination with unrestricted costs. This construction does not extend to unit weights, for which we prove that the algorithm admits a strongly polynomial implementation.
ER -