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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The beyond worst-case threshold problem (BWC), recently introduced byBruy\`ere et al., asks given a quantitative game graph for the synthesis of astrategy that i) enforces some minimal level of performance against anyadversary, and ii) achieves a good expectation against a stochastic model ofthe adversary. They solved the BWC problem for finite-memory strategies andunidimensional mean-payoff objectives and they showed membership of the problemin NP$\cap$coNP. They also noted that infinite-memory strategies are morepowerful than finite-memory ones, but the respective threshold problem was leftopen. We extend these results in several directions. First, we considermultidimensional mean-payoff objectives. Second, we study both finite-memoryand infinite-memory strategies. We show that the multidimensional BWC problemis coNP-complete in both cases. Third, in the special case when the worst-caseobjective is unidimensional (but the expectation objective is stillmultidimensional) we show that the complexity decreases to NP$\cap$coNP. Thissolves the infinite-memory threshold problem left open by Bruy\`ere et al., andthis complexity cannot be improved without improving the currently knowncomplexity of classical mean-payoff games. Finally, we introduce a naturalrelaxation of the BWC problem, the beyond almost-sure threshold problem (BAS),which asks for the synthesis of a strategy that ensures some minimal level ofperformance with probability one and a good expectation against the stochasticmodel of the adversary. We show that the multidimensional BAS threshold problemis solvable in P.

Multidimensional beyond worst-case and almost-sure problems for mean-payoff objectives