×

An average polynomial algorithm for solving antagonistic games on graphs. (English. Russian original) Zbl 1394.05078

J. Comput. Syst. Sci. Int. 57, No. 1, 88-96 (2018); translation from Izv. Ross. Akad. Nauk, Teor. Sist. Upr. 2018, No. 1, 89-97 (2018).
Summary: An algorithm that determines the winner in a cyclic game in polynomial time is proposed. The two-person game occurs continuously on the edges of a directed graph until a vertex visited earlier is reached. If the weight of the resulting cycle is nonnegative, then the maximizing player wins; if this cycle has a negative weight, then the minimizing player wins. A polynomial estimate of the expected algorithm execution time is obtained under the condition that the weights of the game’s graph edges are distributed uniformly. A brief justification of the time estimate of the algorithm is given. Such games have applications in the validating the correctness of parallel-distributed computer systems, including problems of making up a feasible schedule with logical precedence conditions and preprocessing possibilities.

MSC:

05C57 Games on graphs (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Vorobyov, S., Cyclic games and linear programming, Discrete Appl. Math., 156, 2195-2231, (2008) · Zbl 1142.91310 · doi:10.1016/j.dam.2008.04.012
[2] Karp, R. M., A characterization of the minimum cycle meaning in a digraf, Discrete Math., 23, 309-311, (1978) · Zbl 0386.05032 · doi:10.1016/0012-365X(78)90011-0
[3] Karzanov, A. V.; Klimov, V. S. (ed.), On average weight minimum sections and cycles of an oriented graph, 72-83, (1985), Yaroslavl’
[4] Ehrenfenfeucht, A.; Mycielski, J., Positional strategies for mean payoff games, Int. J. Game Theory, 8, 109-113, (1979) · Zbl 0499.90098 · doi:10.1007/BF01768705
[5] Denardo, E. V., Contraction mappings in the theory underlying dynamic programming, SIAM Rev., 9, 165-177, (1967) · Zbl 0154.45101 · doi:10.1137/1009030
[6] Gurvich, V. A.; Karzanov, A. V.; Khachiyan, L. G., Cyclic games and an algorithm to find minimax cycle means in directed graphs, USSR Comput. Math. Math. Phys., 28, 85-91, (1988) · Zbl 0695.90105 · doi:10.1016/0041-5553(88)90012-2
[7] Pisaruk, N., Mean cost cyclical games, Math. Operat. Res., 24, 817-828, (1999) · Zbl 0996.91016 · doi:10.1287/moor.24.4.817
[8] Björklund, A.; Vorobyov, S., A combinatorial strongly subexponential strategy improvemant algorithm for mean payoff games, Discrete Appl. Math., 155, 210-229, (2007) · Zbl 1176.68087 · doi:10.1016/j.dam.2006.04.029
[9] Beier, R.; Vöcking, B., Typical properties of winners and losers in discrete optimization, SIAM J. Comput., 35, 855-881, (2006) · Zbl 1096.68066 · doi:10.1137/S0097539705447268
[10] Spielman, D. A.; Teng, S. H., Smoothed analysis: an attempt to explain the behavior of algorithm in practice, Commun. ACM, 52, 76-84, (2009) · doi:10.1145/1562764.1562785
[11] E. M. Clark, Jr., O. Grumberg, and D. A. Peled, Model Checking (MIT Press, 111Cambridge, MA, 1999).
[12] Emerson, E. A.; Jutla, C. S., Tree automata. mu-callculus and determinacy, 368-377, (1991), Washington, DC
[13] Alifanov, D. V.; Lebedev, V. N.; Tsurkov, V. I., Optimization of schedules with precedence logical conditions, J. Comput. Syst. Sci. Int., 48, 932, (2009) · Zbl 1198.49037 · doi:10.1134/S1064230709060094
[14] Kifer, Yu. I., The optimal policy in games with unbounded sequence of moves, Teor. Veroyatn. Primen., 14, 279-286, (1969)
[15] Zwick, U.; Paterson, M., The complexity of mean payoff games on graphs, Theor. Comput. Sci., 158, 343-359, (1996) · Zbl 0871.68138 · doi:10.1016/0304-3975(95)00188-3
[16] Zermelo, E., Über eine anwendung der mengenlehere auf die theorie des schaspiels, (1912), Cambridge
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.