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

Japanese

割引および長期平均コストを持つターンベースの決定的なゼロサムゲームを研究します。割引コストの場合、我々は、無制限コストおよび単位重量の下で、ダンツィッグのルールを用いて、単純な戦略イテレーション方法の下限を、スーパーポリノミクスとスーパーポリノミクスイテレーションの下限に設定します。我々の知る限りでは、この方法は、すべてのアクションコストが$\{-1,0,1\}ドルに属する場合でも、強くポリノミクスではないことを初めて示しています。長期平均コストの場合、我々は、無制限コストのダンツィッグの同僚の終了のために、スーパーポリノミクス低

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