Notice: Undefined offset: -24 in /srv/www/htdocs-cs/cie08/print-abs.php on line 7
CiE 2008 -
Computability in Europe 2006
Logical Approaches to Computational Barriers

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

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

Notice: Undefined index: cancelled in /srv/www/htdocs-cs/cie08/conf-code.php on line 530

Notice: Undefined variable: del in /srv/www/htdocs-cs/cie08/conf-code.php on line 552
Speaker: Rahul Savani
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 579