Computability in Europe 2008
Logic and Theory of Algorithms
Special Session Talk:
|Author(s):||Marcin Jurdzinski and Rahul Savani|
The values of a two-player zero-sum binary discounted game are characterized by a P-matrix linear complementarity problem (LCP). Simple formulas are given to describe the data of the LCP in terms of the game graph, discount factor, and rewards. Hence it is shown that the unique sink orientation (USO) associated with this LCP coincides with the valuation USO associated with the discounted game. As an application of this fact, it is shown that Murty's least index method for P-matrix LCPs corresponds to both known and new variants of strategy improvement algorithms for discounted games.
|websites: Arnold Beckmann||
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie08/conf-code.php on line 136