Newest papers

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

Sanyou Mei · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.27386 · cited by 0 works (OpenAlex) · open-access PDF

Spanish

Estudiamos juegos deterministas de suma cero basados en turnos con costes promedio descuentados y de largo plazo. Para costes descontados, establecemos límites inferiores de iteración exponencial y superpolinómica para el método de iteración de estrategia simple con la regla de Dantzig bajo costes ilimitados y pesos unitarios, respectivamente. A lo mejor de nuestro conocimiento, esto demuestra por primera vez que el método no es fuertemente polinomial incluso cuando todos los costes de acción pertenecen a $\{-1,0,1\}$. Para costes promedio de largo plazo, establecemos un límite inferior de iteración exponencial para la terminación de un homólogo de Dantzig con costes ilimitados y demuestra que admite una implementación fuertemente polinomial con pesos unitarios.

Machine translation (Meta M2M100); the English original follows.

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, this shows for the first time that the method is not strongly polynomial even when all action costs belong to $\{-1,0,1\}$. For long-run average costs, we establish an exponential iteration lower bound for termination of a Dantzig counterpart with unrestricted costs and prove that it admits a strongly polynomial implementation with unit weights.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Mathematics, Simple (philosophy), Polynomial, Exponential function, Upper and lower bounds, Combinatorics

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange