article

Cyclic games and linear programming

Author:

Sergei VorobyovAuthors Info & Claims

Discrete Applied Mathematics, Volume 156, Issue 11

Pages 2195 - 2231

https://doi.org/10.1016/j.dam.2008.04.012

Published: 01 June 2008 Publication History

Abstract

New efficient algorithms for solving infinite-duration two-person adversary games with the decision problem inNP@?coNP, based on linear programming (LP), LP-representations, combinatorial LP, linear complementarity problem (LCP), controlled LP are surveyed.

References

[1]

Andersson, D., An improved algorithm for discounted payoff games. In: Huitink, J., Katrenko, S. (Eds.), Proceedings of the 11th ESSLLI Student Session, Málaga, Spain. pp. 91-98.

[2]

D. Andersson, S. Vorobyov, Fast algorithms for monotonic discounted linear programs with two variables per inequality, Preprint NI06019-LAA, Isaac Newton Institute for Mathematical Sciences, Cambridge, UK, May 2006. {http://www.newton.cam.ac.uk/preprints2006.html}.

[3]

E. Beffara, S. Vorobyov, Is randomized Gurvich-Karzanov-Khachiyan's algorithm for parity games polynomial? Technical Report 2001-025, Department of Information Technology, Uppsala University, November 2001. {http://www.it.uu.se/research/reports/}.

[4]

H. Björklund, Combinatorial Optimization for Infinite Games on Graphs, Ph.D. Thesis, Uppsala University, 2005.

[5]

H. Björklund, O. Nilsson, O. Svensson, S. Vorobyov, Controlled linear programming: boundedness and duality, Technical Report DIMACS-2004-56, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, December 2004. {http://dimacs.rutgers.edu/TechnicalReports/}.

[6]

H. Björklund, O. Nilsson, O. Svensson, S. Vorobyov, The controlled linear programming problem, Technical Report DIMACS-2004-41, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, September 2004. {http://dimacs.rutgers.edu/TechnicalReports/}.

[7]

Björklund, H., Sandberg, S. and Vorobyov, S., A discrete subexponential algorithm for parity games. In: Alt, H., Habib, M. (Eds.), Twentieth International Symposium on Theoretical Aspects of Computer Science, STACS'2003, Lecture Notes in Computer Science, vol. 2607. Springer, Berlin. pp. 663-674.

Digital Library

[8]

H. Björklund, S. Sandberg, S. Vorobyov, On combinatorial structure and algorithms for parity games, Technical Report 2003-002, Department of Information Technology, Uppsala University, January 2003. {http://www.it.uu.se/research/reports/}.

[9]

Björklund, H., Sandberg, S. and Vorobyov, S., Memoryless determinacy of parity and mean payoff games: A simple proof. Theoret. Comput. Sci. v310 i1-3. 365-378.

Digital Library

[10]

H. Björklund, O. Svensson, S. Vorobyov, Controlled linear programming for infinite games, Technical Report DIMACS-2005-13, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, April 2005.{http://dimacs.rutgers.edu/TechnicalReports/}.

[11]

H. Björklund, O. Svensson, S. Vorobyov, Linear complementarity algorithms for mean payoff games. Technical Report DIMACS-2005-05, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, February 2005. {http://dimacs.rutgers.edu/TechnicalReports/}, International Journal of Game Theory, to appear.

[12]

Björklund, H. and Vorobyov, S., Combinatorial structure and randomized subexponential algorithms for infinite games. Theoret. Comput. Sci. v349 i3. 347-360.

Digital Library

[13]

Björklund, H. and Vorobyov, S., A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Appl. Math. v155 i2. 210-219.

Digital Library

[14]

E. Cohen, N. Megiddo, Improved algorithms for linear inequalities with two variables per inequality, in: ACM Annual Symposium on Theory of Computing, 1991, pp. 145-154.

Digital Library

[15]

Condon, A., The complexity of stochastic games. Inform. and Comput. v96. 203-224.

Digital Library

[16]

Cottle, R.W. and Dantzig, G.B., A generalization of the linear complementarity problem. J. Combin. Theory. v8. 79-90.

[17]

Cottle, R.W., Pang, J.-S. and Stone, R.E., The Linear Complementarity Problem. 1992. Academic Press, New York.

[18]

Coxson, G., The P-matrix problem is coNP-complete. Math. Programming. v64. 173-178.

Digital Library

[19]

A Ebiefung, A. and Kostreva, M.M., The generalized linear complementarity problem: least element theory and Z-matrices. J. Global Optim. v11. 151-161.

Digital Library

[20]

Ehrenfeucht, A. and Mycielski, J., Positional games over a graph. Notices Amer. Math Soc. v20. 334

[21]

Ehrenfeucht, A. and Mycielski, J., Positional strategies for mean payoff games. Internat. J. Game Theory. v8. 109-113.

[22]

Emerson, E.A., Model checking and the µ-calculus. In: Immerman, N., Kolaitis, Ph.G. (Eds.), DIMACS Series in Discrete Mathematics, vol. 31. pp. 185-214.

[23]

E.A. Emerson, C.S. Jutla, Tree automata, µ-calculus and determinacy, in: Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 368-377.

Digital Library

[24]

Fulkerson, D.R. and Harding, G.C., Maximizing the minimum source-sink path subject to a budget constraint. Math. Programming. v13. 116-118.

[25]

B. Gärtner, L. Rüst, Simple stochastic games and P-matrix generalized linear complementarity problem, in: Fundamentals of Computation Theory (FCT), vol. 3623, Lecture Notes in Computer Science, Springer, Berlin, 2005, pp. 209-220.

Digital Library

[26]

Gillette, D., Stochastic games with zero stop probabilities. Contrib. Theory Games. vIII. 179-187.

[27]

Gurvich, V.A., Karzanov, A.V. and Khachiyan, L.G., Cyclic games and an algorithm to find minimax cycle means in directed graphs. U.S.S.R. Comput. Math. Math. Phys. v28 i5. 85-91.

Digital Library

[28]

Hammer, P.L., Simeone, B., Liebling, Th.M. and De Werra, D., From linear separability to unimodality: a hierarchy of pseudo-Boolean functions. SIAM J. Discrete Math. v1 i2. 174-184.

Digital Library

[29]

Hochbaum, D.S. and Naor, J., Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. v23 i6. 1179-1192.

Digital Library

[30]

Hoffman, A.J. and Karp, R.M., On nonterminating stochastic games. Manage. Sci. v12 i5. 359-370.

[31]

Israeli, E. and Wood, R.K., Shortest path network interdiction. Networks. v40 i2. 97-111.

[32]

M. Jurdziński, M. Paterson, U. Zwick, A deterministic subexponential algorithm for solving parity games, in: ACM SODA'06, 2006, pp. 117-123.

Digital Library

[33]

G. Kalai, A subexponential randomized simplex algorithm, in: 24th ACM STOC, 1992, pp. 475-482.

Digital Library

[34]

Kalai, G., Linear programming, the simplex algorithm and simple polytopes. Math. Prog. (Ser. B). v79. 217-234.

Digital Library

[35]

Karzanov, A. and Lebedev, V., Cyclical games with prohibitions. Math. Programming. v60. 277-293.

Digital Library

[36]

L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf, J. Zhao, On short path interdiction problems: total and node-wise limited interdiction, RUTCOR Research Report RRR 25-2006, RUTCOR, Rutgers Center of Operations Research, October 2006, Theory Comput. Syst. vol. 43, no. 2, August 2008, to appear.

[37]

L. Khachiyan, V. Gurvich, J. Zhao, Extending Dijkstra's algorithm to maximize the shortest path by node-wise limited arc intediction, RUTCOR Research Report RRR 31-2005, RUTCOR, Rutgers Center of Operations Research, October 2005.

[38]

M. Kojima, N. Megiddo, T. Noma, A. Yoshise, A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, in: Lecture Notes in Computer Science, vol. 538, Springer, Berlin, 1991.

[39]

J. Matoušek, M. Sharir, M. Welzl, A subexponential bound for linear programming, in: 8th ACM Symposium on Computational Geometry, 1992, pp. 1-8.

Digital Library

[40]

Matoušek, J., Sharir, M. and Welzl, M., A subexponential bound for linear programming. Algorithmica. v16. 498-516.

[41]

N. Megiddo, A note on the complexity of P-matrix LCP and computing the equilibrium, Technical Report RJ 6439 (62557) 9/19/88, IBM Almaden Research Center, 1988.

[42]

Morris, W.D., Randomized pivot algorithms for P-matrix linear complementarity problems. Math. Programming, Ser. A. v92. 285-296.

[43]

Moulin, H., Extensions of two person zero sum games. J. Math. Anal. Appl. v55. 490-508.

[44]

Moulin, H., Prolongements des jeux í deux joueurs de somme nulle. Bull. Soc. Math. France. v45.

[45]

K.G. Murty, F.-T. Yu, Linear Complementarity, Linear and Nonlinear Programming, Heldermann, Berlin, 1988. {http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/}.

[46]

Pisaruk, N., Mean cost cyclical games. Math. Oper. Res. v24 i4. 817-828.

Digital Library

[47]

Schrijver, A., Theory of Linear and Integer Programming. 1986. Wiley, New York.

Digital Library

[48]

A. Schrijver, Combinatorial Optimization, vols. A-C, Springer, Berlin, 2003.

[49]

Shapley, L.S., Stochastic games. Proc. Nat. Acad. Sci. U.S.A. v39. 1095-1100.

[50]

O. Svensson, Mean payoff games and linear complementarity, in: Proceedings of the ESSLLI'2005, European Summer School on Logic, Language, and Information, Edingburgh, Scotland, August 2005, Kluwer Academic Press, Dordrecht.

[51]

O. Svensson, S. Vorobyov, Linear complementarity and P-matrices for stochastic games, in: 6th International Andrei Ershov Memorial Conference on "Perspectives of System Informatics", Lecture Notes in Computer Science, vol. 4378, Novosibirsk, Russia, 27-30 June 2006, Springer, Berlin, pp. 412-425. Preliminary version: DIMACS TR 2005-20.

Digital Library

[52]

O. Svensson, S. Vorobyov, Linear programming polytope and algorithm for mean payoff games, in: Second International Conference on Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science, vol. 4041, Hong Kong, China, 20-22 June 2006, Springer, Berlin, pp. 64-78, Preliminary version: RUTCOR RRR 34-2005.

Digital Library

[53]

B.P. Szanc, The generalized complementarity problem, Ph.D. Thesis, Rensselaer Polytechnic Institute, Troy, New York, 1989.

[54]

Williamson Hoke, K., Completely unimodal numberings of a simple polytope. Discrete Appl. Math. v20. 69-81.

Digital Library

[55]

J. Zhao, V. Gurvich, L. Khachiyan, Extending Dijkstra's algorithm to shortest paths with blocks, Technical Report DIMACS-2005-04, DIMACS: Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, NJ, February 2005. {http://dimacs.rutgers.edu/TechnicalReports/}.

[56]

Zwick, U. and The complexity of mean payoff games on graphs, M.Paterson., . Theoret. Comput. Sci. v158. 343-359.

Digital Library

Cited By

Lebedev VTsurkov V(2018)An Average Polynomial Algorithm for Solving Antagonistic Games on GraphsJournal of Computer and Systems Sciences International10.1134/S106423071801004557:1(88-96)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1134/S1064230718010045
Boros EElbassioni KFouz MGurvich VMakino KManthey B(2018)Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random PositionsAlgorithmica10.1007/s00453-017-0372-780:11(3132-3157)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s00453-017-0372-7
Boros EElbassioni KGurvich VMakino K(2017)A nested family of $$\varvec{k}$$-total effective rewards for positional gamesInternational Journal of Game Theory10.1007/s00182-016-0532-z46:1(263-293)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s00182-016-0532-z
Show More Cited By

Index Terms

Recommendations

A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games

We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem. It is based on iteratively improving the longest shortest distances to a sink in a possibly cyclic directed graph. We identify a ...
Combinatorial structure and randomized subexponential algorithms for infinite games

The complexity of solving infinite games, including parity, mean payoff, and simple stochastic, is an important open problem in verification, automata, and complexity theory. In this paper, we develop an abstract setting for studying and solving such ...
On linear programming relaxations for solving polynomial programming problems
Highlights
- Theoretically compared the tightness of the J-set relaxation with the recursive McCormick relaxations.
Abstract
This paper studies linear programming (LP) relaxations for solving polynomial programming problems. A polynomial programming problem can be equivalently formulated as a quadratically constrained quadratic program (QCQP) by introducing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 156, Issue 11

June, 2008

288 pages

ISSN:0166-218X

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2008.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 June 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lebedev VTsurkov V(2018)An Average Polynomial Algorithm for Solving Antagonistic Games on GraphsJournal of Computer and Systems Sciences International10.1134/S106423071801004557:1(88-96)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1134/S1064230718010045
Boros EElbassioni KFouz MGurvich VMakino KManthey B(2018)Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random PositionsAlgorithmica10.1007/s00453-017-0372-780:11(3132-3157)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s00453-017-0372-7
Boros EElbassioni KGurvich VMakino K(2017)A nested family of $$\varvec{k}$$-total effective rewards for positional gamesInternational Journal of Game Theory10.1007/s00182-016-0532-z46:1(263-293)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s00182-016-0532-z
Chatterjee KHenzinger MKrinninger SNanongkai D(2014)Polynomial-Time Algorithms for Energy Games with Special Weight StructuresAlgorithmica10.1007/s00453-013-9843-770:3(457-492)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1007/s00453-013-9843-7
Chatterjee KHenzinger MKrinninger SNanongkai D(2012)Polynomial-Time algorithms for energy games with special weight structuresProceedings of the 20th Annual European conference on Algorithms10.1007/978-3-642-33090-2_27(301-312)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33090-2_27
Boros EElbassioni KFouz MGurvich VMakino KManthey B(2011)Stochastic mean payoff gamesProceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I10.5555/2027127.2027144(147-158)Online publication date: 4-Jul-2011
https://dl.acm.org/doi/10.5555/2027127.2027144
Boros EElbassioni KGurvich VMakino K(2010)A pumping algorithm for ergodic stochastic mean payoff games with perfect informationProceedings of the 14th international conference on Integer Programming and Combinatorial Optimization10.1007/978-3-642-13036-6_26(341-354)Online publication date: 9-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-13036-6_26

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents