Skip to main content
MathOverflow

Return to Answer

fixed grammar
Source Link
Peter Shor
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

This is the simple stochastic games problem, but for only one player, and there is a polynomial-time algorithm for it based on linear programming, which is described in Anne Condon's paper "On Algorithms for Simple Stochastic Games." Look in this paper for the linear programming algorithm for SSG's with no min vertices. In one of her papers on simple stochastic games, Condon does indeed prove that the setting of the switches is independent of the start node, and that in the optimal strategy, the switch settings never need to change.

This is the simple stochastic games problem, but for only one player, and there is a polynomial-time algorithm for it based on linear programming, which is described in Anne Condon's paper "On Algorithms for Simple Stochastic Games." Look in this paper for the linear programming algorithm for SSG's with no min vertices. In one of her papers on simple stochastic games, Condon does indeed prove that the setting of the switches is independent of the start node, and in the optimal strategy, the switch settings never need to change.

This is the simple stochastic games problem, but for only one player, and there is a polynomial-time algorithm for it based on linear programming, which is described in Anne Condon's paper "On Algorithms for Simple Stochastic Games." Look in this paper for the linear programming algorithm for SSG's with no min vertices. In one of her papers on simple stochastic games, Condon does indeed prove that the setting of the switches is independent of the start node, and that in the optimal strategy, the switch settings never need to change.

Source Link
Peter Shor
Peter Shor
  • 6.3k
  • 4
  • 55
  • 65

This is the simple stochastic games problem, but for only one player, and there is a polynomial-time algorithm for it based on linear programming, which is described in Anne Condon's paper "On Algorithms for Simple Stochastic Games." Look in this paper for the linear programming algorithm for SSG's with no min vertices. In one of her papers on simple stochastic games, Condon does indeed prove that the setting of the switches is independent of the start node, and in the optimal strategy, the switch settings never need to change.