Get started
      <script type="text/javascript" src="//"></script>

<script type="text/javascript" id="sle81767">
slidesLive = createSlidesLiveBox();

Antonín Kučera | Stochastic Two-Player Games

Wait a moment... We are trying to load HTML5 player instead of flash, this might take a minute or two.

Or you can download FlashPlayer Get Adobe Flash player

Pražský informatický seminář |
Feb 27, 2014
</> Embed

Stochastic two-player games on directed graphs are widely used for modeling and analysis of discrete systems operating in an unknown (adversarial) environment. Possible configurations of a system and its environment are represented as vertices, and the transitions correspond to actions of the system, its environment, or "nature". A run of the system then corresponds to an infinite path in the graph. Thus, a system and its environment can be seen as two players with antagonistic objectives, where one player (the system) aims at maximizing the probability of "good" runs, while the other player (the environment) aims at the opposite. In many cases, there exists an equilibrium value of this probability, but optimal strategies for both players may not exist. We introduce basic concepts and algorithmic questions studied in this area, and we mention some long-standing open problems. Then, we mention selected recent results.