<script src="//d2wy8f7a9ursnm.cloudfront.net/bugsnag-3.min.js" data-apikey="3f7d54ba1348e2ecacfa1de11aa47254"></script> <script> <% if current_user %> Bugsnag.user = { signed_in: true, id: '<%= current_user.id %>', name: '<%= escape_javascript current_user.display_name %>', email: '<%= escape_javascript current_user.email %>', active_account_id: '<%= current_user.active_account_id %>' }; <% else %> Bugsnag.user = { signed_in: false }; <% end %> Bugsnag.context = '<%= escape_javascript controller_path %>#<%= escape_javascript action_name %>'; Bugsnag.metaData = { request_id: '<%= escape_javascript request.uuid %>', locale: '<%= escape_javascript I18n.locale.to_s %>', embed: window.parent !== window, referer: '<%= escape_javascript request.referer %>' }; </script>

Stochastic Two-Player Games

by · Feb 27, 2014 · 8 625 views ·

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.

© SlidesLive Inc.