12.00 noon
Orderfield Property of Stochastic Games via Dependency Graphs.
Nagarajan Krishnamurthy
Chennai Mathematical Institute.
19-10-09

---

Abstract

We propose the concept of dependency graphs of stochastic games and mixtures of classes of stochastic games. We use this concept to derive conditions which are sufficient for a stochastic game to possess the orderfield property. Vertices in the dependency graph are either states of the game or combinations of states and action pairs. We draw an edge from vertex u to v if there exists a positive transition probability from u to v for some choice of actions of the players.

By analyzing simple structural properties of these dependency graphs, we find if (certain subclasses of) mixtures of stochastic games have the orderfield property or not. For example, a mixture of classes of discounted stochastic games has the orderfield property if there are no cycles involving states from different classes. This works even if a "sink" in the graph is an undiscounted game but does not always work if an internal vertex is undiscounted. "Big Match" is a counter example. Here, we are talking about the graph where each vertex is a class.

Given a stochastic game with rational inputs, these "sufficient conditions" can be verified in polynomial time. One way is to find bi-connected components in the dependency graph and topologically sort them.

This is joint work with Prof. T. Parthasarathy and Dr. G. Ravindran of the Indian Statistical Institute, Chennai.