Non-oblivious Strategy Improvement

Preprint English OPEN
Fearnley, John;
(2010)
  • Related identifiers: doi: 10.1007/978-3-642-17511-4_13
  • Subject: Computer Science - Computer Science and Game Theory
    arxiv: Computer Science::Computer Science and Game Theory

We study strategy improvement algorithms for mean-payoff and parity games. We describe a structural property of these games, and we show that these structures can affect the behaviour of strategy improvement. We show how awareness of these structures can be used to acce... View more
  • References (16)
    16 references, page 1 of 2

    [1] H. Bjo¨ rklund, S. Sandberg, and S. Vorobyov. A discrete subexponential algorithm for parity games. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, volume 2607 of LNCS, pages 663-674, London, UK, 2003. Springer-Verlag.

    [2] H. Bjo¨ rklund and S. Vorobyov. A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Applied Mathematics, 155(2):210-229, 2007.

    [3] A. Condon. On algorithms for simple stochastic games. In J.-Y. Cai, editor, Advances in Computational Complexity Theory, volume 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 51-73. American Mathematical Society, 1993.

    [4] E. A. Emerson, C. S. Jutla, and A. P. Sistla. On model-checking for fragments of μ -calculus. In C. Courcoubetis, editor, Computer Aided Verification, 5th International Conference, CAV'93, volume 697 of LNCS, pages 385-396. Springer-Verlag, 1993.

    [5] O. Friedman. A super-polynomial lower bound for the parity game strategy improvement algorithm as we know it. In Logic in Computer Science (LICS). IEEE, 2009.

    [6] O. Friedman. A super-polynomial lower bound for the parity game strategy improvement algorithm as we know it. Preprint, January 2009.

    [7] R. Howard. Dynamic Programming and Markov Processes. Technology Press and Wiley, 1960.

    [8] M. Jurdzin´ ski, M. Paterson, and U. Zwick. A deterministic subexponential algorithm for solving parity games. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pages 117-123. ACM/SIAM, 2006.

    [9] L. Khachiyan, V. Gurvich, and J. Zhao. Extending dijkstra's algorithm to maximize the shortest path by node-wise limited arc interdiction. In Computer Science - Theory and Applications, volume 3967 of LNCS, pages 221-234. Springer, 2006.

    [10] T. M. Liggett and S. A. Lippman. Stochastic games with perfect information and time average payoff. SIAM Review, 11(4):604-607, 1969.

  • Metrics
Share - Bookmark