English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Two-player (antagonistic) games on (possibly stochastic) graphs are aprevalent model in theoretical computer science, notably as a framework forreactive synthesis.  Optimal strategies may require randomisation when dealing with inherentlyprobabilistic goals, balancing multiple objectives, or in contexts of partialinformation. There is no unique way to define randomised strategies. Forinstance, one can use so-called mixed strategies or behavioural ones. In themost general setting, these two classes do not share the same expressiveness. Aseminal result in game theory -- Kuhn's theorem -- asserts their equivalence ingames of perfect recall.  This result crucially relies on the possibility for strategies to useinfinite memory, i.e., unlimited knowledge of all past observations. However,computer systems are finite in practice. Hence it is pertinent to restrict ourattention to finite-memory strategies, defined as automata with outputs.Randomisation can be implemented in these in different ways: theinitialisation, outputs or transitions can be randomised or deterministicrespectively. Depending on which aspects are randomised, the expressiveness ofthe corresponding class of finite-memory strategies differs.  In this work, we study two-player concurrent stochastic games and provide acomplete taxonomy of the classes of finite-memory strategies obtained byvarying which of the three aforementioned components are randomised. Ourtaxonomy holds in games of perfect and imperfect information with perfectrecall, and in games with more than two players. We also provide an adaptedtaxonomy for games with imperfect recall.

Different Strokes in Randomised Strategies: Revisiting Kuhn's Theorem under Finite-Memory Assumptions