### Abstract

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G=(V,E), with local rewards r:E→Z, and three types of positions: black V _{B} , white V _{W} , and random V _{R} forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when |V _{R} |=0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, ^{1} we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with |V _{R} |=O(1), a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in |V _{W} |+|V _{B} |, the maximum absolute local reward, and the common denominator of the transition probabilities.

Original language | English (US) |
---|---|

Pages (from-to) | 74-95 |

Number of pages | 22 |

Journal | Information and Computation |

Volume | 267 |

DOIs | |

State | Published - Aug 2019 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics

### Keywords

- Equilibrium computation
- Perfect information
- Pseudo-polynomial algorithm
- Stochastic games
- Zero-sum games

## Fingerprint Dive into the research topics of 'A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions'. Together they form a unique fingerprint.

## Cite this

*Information and Computation*,

*267*, 74-95. https://doi.org/10.1016/j.ic.2019.03.005