Solving Simple Stochastic Games with Few Random Vertices

Details Solving Simple Stochastic Games with Few Random Vertices Solving Simple Stochastic Games with Few Random Vertices

2007-12-11

arxiv.org/abs/0712.1765v6

LMCS 5 (2:9) 2009

Computer Science

Computer Science and Game Theory

Scientific paper

10.2168/LMCS-5(2:9)2009

Simple stochastic games are two-player zero-sum stochastic games with turn-based moves, perfect information, and reachability winning conditions. We present two new algorithms computing the values of simple stochastic games. Both of them rely on the existence of optimal permutation strategies, a class of positional strategies derived from permutations of the random vertices. The "permutation-enumeration" algorithm performs an exhaustive search among these strategies, while the "permutation-improvement" algorithm is based on successive improvements, \`a la Hoffman-Karp. Our algorithms improve previously known algorithms in several aspects. First they run in polynomial time when the number of random vertices is fixed, so the problem of solving simple stochastic games is fixed-parameter tractable when the parameter is the number of random vertices. Furthermore, our algorithms do not require the input game to be transformed into a stopping game. Finally, the permutation-enumeration algorithm does not use linear programming, while the permutation-improvement algorithm may run in polynomial time.

Affiliated with

Also associated with

No associations

Rating

Solving Simple Stochastic Games with Few Random Vertices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solving Simple Stochastic Games with Few Random Vertices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving Simple Stochastic Games with Few Random Vertices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-474561