Name
Abstract | ||
|---|---|---|
We present a new algorithm for solving Simple Stochastic Games (SSGs). This algorithm is based on an exhaustive search of a special kind of positional optimal strategies, the f-strategies. The running time is O( |VR|! ċ (|V ||E| + |p|) ), where |V |, |VR|, |E| and |p| are respectively the number of vertices, random vertices and edges, and the maximum bit-length of a transition probability. Our algorithm improves existing algorithms for solving SSGs in three aspects. First, our algorithm performs well on SSGs with few random vertices, second it does not rely on linear or quadratic programming, third it applies to all SSGs, not only stopping SSGs. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-78499-9_2 | FoSSaCS |
Keywords | Field | DocType |
simple stochastic games,exhaustive search,quadratic programming,maximum bit-length,random vertex,new algorithm,simple stochastic game,positional optimal strategy,transition probability,special kind,quadratic program | Discrete mathematics,Combinatorics,Vertex (geometry),Brute-force search,Computer science,Markov chain,Quadratic programming,Stochastic game | Conference |
Volume | ISSN | ISBN |
4962 | 0302-9743 | 3-540-78497-7 |
Citations | PageRank | References |
15 | 0.92 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hugo Gimbert | 1 | 249 | 21.31 |
| Florian Horn | 2 | 53 | 6.57 |