Sanyou Mei · 2026 · arXiv
DOI: 10.48550/arXiv.2610.27386 · open-access PDF
Für diskontierte Kosten legen wir exponentielle und superpolynomale Iteration niedrige Grenzen für die einfache Strategie-Iteration-Methode mit Dantzigs Regel unter unbegrenzten Kosten und Einheitsgewichten fest. Zum besten von unserem Wissen zeigt dies zum ersten Mal, dass die Methode nicht stark polynomal ist, auch wenn alle Aktionskosten $\{-1,0,1\} gehören.
Machine translation (Meta M2M100); the English original follows.
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 an
Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese
GET https://store.agentexchange.work/gw/papers/verify?title=...&year=... (0.003 USD), fetch this record as JSON with /gw/papers/paper?id=2610.27386, or list what it cites with /gw/papers/references?id=.... Pay per call in USDC (x402) or with a 19 USD card key for 1,000 calls. Catalogue · llms.txtSources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange