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

We study $n$-player turn-based games played on a finite directed graph. Foreach play, the players have to pay a cost that they want to minimize. Insteadof the well-known notion of Nash equilibrium (NE), we focus on the notion ofsubgame perfect equilibrium (SPE), a refinement of NE well-suited in theframework of games played on graphs. We also study natural variants of SPE,named weak (resp. very weak) SPE, where players who deviate cannot use the fullclass of strategies but only a subclass with a finite number of (resp. aunique) deviation step(s).  Our results are threefold. Firstly, we characterize in the form of a Folktheorem the set of all plays that are the outcome of a weak SPE. Secondly, forthe class of quantitative reachability games, we prove the existence of afinite-memory SPE and provide an algorithm for computing it (only existence wasknown with no information regarding the memory). Moreover, we show that theexistence of a constrained SPE, i.e. an SPE such that each player pays a costless than a given constant, can be decided. The proofs rely on our Folk theoremfor weak SPEs (which coincide with SPEs in the case of quantitativereachability games) and on the decidability of MSO logic on infinite words.Finally with similar techniques, we provide a second general class of games forwhich the existence of a (constrained) weak SPE is decidable.

Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability