Metraipolis › archive › dc_d7a0bb669cfc

Attaining Optimal Values under Sure Constraints — arXiv:2611.09244

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.09244
License (as archived): CC0-1.0
Archived: 2026-11-09T22:37:52.628Z
SHA-256 of the archived text: d2952fbd20aa91b7ea21d2c4959b104862c39989cfea8060587aa40846569004
Stable URL of this page: https://metraipolis.com/documento/dc_d7a0bb669cfc

How to cite

Attaining Optimal Values under Sure Constraints — arXiv:2611.09244 — arXiv (en), https://arxiv.org/abs/2611.09244 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d7a0bb669cfc (Metraipolis archive dc_d7a0bb669cfc, sha256 d2952fbd20aa91b7ea21d2c4959b104862c39989cfea8060587aa40846569004)

BibTeX

@misc{dcd7a0bb669cfc,
  title = {Attaining Optimal Values under Sure Constraints — arXiv:2611.09244},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.09244},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d7a0bb669cfc; sha256 d2952fbd20aa91b7ea21d2c4959b104862c39989cfea8060587aa40846569004},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09244. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A game may have, for each target below its value, a finite controller meeting that target, yet no finite controller attaining the value itself. We study finite stochastic games with a hard specification that must hold on every supported execution, including paths of probability zero. Max uses a pure finite controller; Min may use any pure public-history strategy. We distinguish three numerical questions: can a supplied target be met, can the unspecified optimum be attained, and what is one exact value? For explicit hard and Boolean soft Streett conditions, the strict and non-strict supplied-threshold problems are coNP-complete, attainment of the unsupplied supremum is $\mathrm P^{\mathrm{NP}}$-complete, and one exact reduced fraction is $\mathrm{FP}^{\mathrm{NP}}$-complete under polynomial metric reductions. The proofs preserve both the value and its finite attainability when fixing a single opponent, and encode adaptive queries without computing unknown subgame values. The same construction yields matching value-comparison and exact-output lower bounds for ordinary stochastic Streett games with unrestricted randomized history strategies. We also bound the memory needed for optimal finite implementations for arbitrary Muller hard conditions and rational rewards in $[0,1]$ determined by infinitely recurring states. One controller is sure from the entire original sure region and attains at every finitely attained start, with no attainment premise on the other states. For $n$ states in that region it uses $2^{O(n\log(n+1))}Q(1+\log R)$ modes, where $Q$ is the product of the least common denominators of full original chance rows sourced in that sure region and $R$ clears all reward values. Its joint dependence on $Q$ and $R$ is worst-case sharp at each fixed $n\ge6$ when $Q,R\ge2$. Optimal dependence on arena size and efficient general synthesis are not resolved here.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2611.09244 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-09T22:32:17.015Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).