Computability in Europe 2006
Logical Approaches to Computational Barriers

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

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 2008-01-02