@inproceedings{769bc44af10e44e1be0eeefb44fae4e7,
title = "How to solve large scale deterministic games with mean payoff by policy iteration",
abstract = "Min-max functions are dynamic programming operators of zero-sum deterministic games with finite state and action spaces. The problem of computing the linear growth rate of the orbits (cycle-time) of a min-max function, which is equivalent to computing the value of a deterministic game with mean payoff, arises in the performance analysis of discrete event systems. We present here an improved version of the policy iteration algorithm given by Gaubert and Gunawardena in 1998 to compute the cycle-time of a min-max functions. The improvement consists of a fast evaluation of the spectral projector which is adapted to the case of large sparse graphs. We present detailed numerical experiments, both on randomly generated instances, and on concrete examples, indicating that the algorithm is experimentally fast.",
keywords = "Graph algorithms, Maxplus algebra, Nonlinear harmonic functions, Policy iteration, Repeated games",
author = "Vishesh Dhingra and St{\'e}phane Gaubert",
year = "2006",
month = dec,
day = "1",
doi = "10.1145/1190095.1190110",
language = "English",
isbn = "1595935045",
series = "ACM International Conference Proceeding Series",
booktitle = "Proceedings of VALUETOOLS",
note = "VALUETOOLS: 1st International Conference on Performance Evaluation Methodologies and Tools ; Conference date: 11-10-2006 Through 13-10-2006",
}