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

Vietnamese

Chúng tôi nghiên cứu các trò chơi tổng số không xác định dựa trên lượt với chi phí trung bình giảm giá và chi phí trung bình dài hạn. Đối với chi phí giảm giá, chúng tôi thiết lập giới hạn thấp hơn cho lặp đi lặp lại nhân số và siêu polynomial cho phương pháp lặp đi lặp lại chiến lược đơn giản với quy tắc của Dantzig dưới chi phí không giới hạn và trọng lượng đơn vị, tương ứng. Theo kiến thức tốt nhất của chúng tôi, điều này cho thấy lần đầu tiên rằng phương pháp này không đa năng mạnh ngay cả khi tất cả chi phí hành động thuộc $\{-1,0,1\}$. Đối với chi phí trung bình dài hạn, chúng tôi thiết lập một giới hạn thấp hơn lặp lại nhân số để chấm dứt một đối tác Dantzig với chi phí không giới hạn và chứng minh rằng nó cho phép thực hiện đa năng mạnh với trọng lượng đơn vị.

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