Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 107

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 117
CiE 2008 - Special Session Talk: - A simple P-matrix linear complementarity problem for discounted games
Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Special Session Talk:
A simple P-matrix linear complementarity problem for discounted games

Edit abstract data

Speaker: Rahul Savani
Author(s): Marcin Jurdzinski and Rahul Savani

Abstract

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
2008-01-02 Valid HTML 4.01! Valid CSS!