In this paper we introduce a new modeling paradigm for shortest path games representation with Petri nets. Whereas previous works have restricted attention to tracking the net using Bellman's equation as a utility function, this work uses a Lyapunov-like function. In this sense, we change the traditional cost function by a trajectory-tracking function which is also an optimal cost-to-target function. This makes a significant difference in the conceptualization of the problem domain, allowing the replacement of the Nash equilibrium point by the Lyapunov equilibrium point in game theory. We show that the Lyapunov equilibrium point coincides with the Nash equilibrium point. As a consequence, all properties of equilibrium and stability are preserved in game theory. This is the most important contribution of this work. The potential of this approach remains in its formal proof simplicity for the existence of an equilibrium point.
@article{bwmeta1.element.bwnjournal-article-amcv16i3p387bwm,
author = {Clempner, Julio},
title = {Modeling shortest path games with Petri nets: a Lyapunov based theory},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {16},
year = {2006},
pages = {387-397},
zbl = {1142.91375},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv16i3p387bwm}
}
Clempner, Julio. Modeling shortest path games with Petri nets: a Lyapunov based theory. International Journal of Applied Mathematics and Computer Science, Tome 16 (2006) pp. 387-397. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv16i3p387bwm/
[000] Axelrod R. (1984): The Evolution of Cooperation. - NewYork: Basic Books.
[001] Bellman R.E. (1957): Dynamic Programming. - Princeton: Princeton University Press. | Zbl 0077.13605
[002] Bertsekas D.P. and Shreve S.E. (1978): Stochastic Optimal Control: The Discrete Time Case. - New York: Academic Press. | Zbl 0471.93002
[003] Bertsekas D.P. (1987): Dynamic Programming: Deterministic and Stochastic Models. - Englewood Cliffs: Prentice-Hall. | Zbl 0649.93001
[004] Bertsekas D.P. and Tsitsiklis J.N. (1989): Parallel and Distributed Computation: Numerical Methods. - Englewood Cliffs: Prentice-Hall. | Zbl 0743.65107
[005] Bertsekas D.P. and Tsitsiklis J.N. (1991): An analysis of stochastic shortest path problems. - Math. Oper. Res., Vol. 16, No. 3,pp. 580-595. | Zbl 0751.90077
[006] Blackwell D. (1967): Positive dynamicprogramming. - Proc. 5th Berkeley Symp. Math., Statist., and Probability, Berkeley, California, Vol. 1, pp. 415-418.
[007] Clempner J. (2005): Colored decision process petri nets: modeling, analysis and stability. - Int. J. Appl. Math. Comput. Sci., Vol. 15, No. 3, pp. 405-420. | Zbl 1169.93371
[008] Clempner J. (2006): Towards modeling the shortest path problem and games with petri nets. - Proc. Doctoral Consortium at 27-th Int. Conf. Application and Theory of Petri Nets and Other Models Of Concurrency, Turku, Finland, pp. 1-12.
[009] Derman C. (1970): Finite State Markovian Decision Processes. - New York: Academic Press. | Zbl 0262.90001
[010] Dynkin E.B. (1963): The optimum choice of the instant forstopping a Markov process. - Soviet Math. Doklady, Vol. 150, pp. 238-240.
[011] Eaton J.H. and Zadeh L.A. (1962): Optimal pursuit strategies indiscrete state probabilistic systems. - Trans. ASME Ser. D, J. Basic Eng., Vol. 84,pp. 23-29.
[012] Grigelionis R.I. and Shiryaev A.N. (1966): On Stefan'sproblem and optimal stopping rules for Markov processes. - Theory Prob. Applic., Vol. 11, pp. 541-558. | Zbl 0178.53303
[013] Hernandez-Lerma O. and Lasserre J.B. (1996): Discrete-Time Markov Control Process: Basic Optimality Criteria. - Berlin: Springer. | Zbl 0840.93001
[014] Hernandez-Lerma O., Carrasco G. and Pere-Hernandez R. (1999): Markov Control Processes with the Expected Total Cost Criterion: Optimality. - Stability and Transient Model. Acta Applicadae Matematicae, Vol. 59,No. 3, pp. 229-269. | Zbl 0964.93086
[015] Hernandez-Lerma O. and Lasserre J.B. (1999): Futher Topicson Discrete-Time Markov Control Process. - Berlin: Springer.
[016] Hinderer K. and Waldmann K.H (2003): The critical discount factor for finite Markovian decision process with an absorbing set.- Math. Meth. Oper. Res., Vol. 57, pp. 1-19. | Zbl 1023.90077
[017] Hinderer K. and Waldmann K.H. (2005): Algorithms for countable state Markov decision model with an absorbing set. - SIAM J. Contr.Optim., Vol. 43, pp. 2109-2131. | Zbl 1097.90067
[018] Howard R.A. (1960): Dynamic Programming and Markov Processes. - Cambridge, MA: MIT Press. | Zbl 0091.16001
[019] Kalman R.E. and Bertram J.E. (1960): Control system analysis and design via the 'Second Method' of Lyapunov. - J. Basic Eng.,ASME, Vol. 82(D), pp. 371-393.
[020] Kuhn H.W. and Nasae S. (Eds.) (2002): The Essential John Nash. - Princeton: Princeton University Press.
[021] Kumar P.R. and Shiau T.H. (1981): Zero sum dynamic games, In: Control and Dynamic Games, (C.T. Leondes, Ed.) - Academic Press, pp. 1345-1378. | Zbl 0549.90104
[022] Kushner H.J. and Chamberlain S.G. (1969): Finite state stochastic games: Existence theorems and computational procedures. - IEEE Trans. Automat. Contr., Vol. 14, No. 3. | Zbl 0182.20802
[023] Kushner H. (1971): Introduction to Stochastic Control. - New York: Holt, Rinehart and Winston. | Zbl 0293.93018
[024] Lakshmikantham S. Leela and Martynyuk A.A. (1990): Practical Stability of Nonlinear Systems. - Singapore: World Scientific. | Zbl 0753.34037
[025] Lakshmikantham V., Matrosov V.M. and Sivasundaram S. (1991): Vector Lyapunov Functions and Stability Analysis of Nonlinear Systems. - Dordrecht: Kluwer. | Zbl 0721.34054
[026] Mandl P. and Seneta E. (1969): The theory of non-negative matricesin a dynamic programming problem. - Austral. J. Stat., Vol. 11,pp. 85-96. | Zbl 0185.08003
[027] Nash J. (1951): Non-cooperative games. - Ann. Math., Vol. 54, pp. 287-295. | Zbl 0045.08202
[028] Nash J. (1996): Essays on Game Theory. - Cheltenham: Elgar.
[029] Pallu de la Barriere R. (1967): Optimal Control Theory. - Philadelphia: Saunders. | Zbl 0155.15203
[030] Patek S.D. (1997): Stochastic Shortest Path Games: Theory and Algorithms. - Ph.D. thesis, Dep. Electr. Eng. Comput.Sci., MIT, Cambridge, MA.
[031] Patek S.D. and Bertsekas D.P. (1999): Stochastic shortest pathgames. - SIAM J. Contr. Optim., Vol. 37, No. 3, pp. 804-824. | Zbl 0918.90148
[032] Patek S.D. (2001): On terminating Markov decision processes with a risk averse objective function. - Automatica, Vol. 37, No. 9, pp. 1379-1386. | Zbl 0995.93075
[033] Pliska S.R. (1978): On the transient case for Markov decision chains with general state space, In: Dynamic Programming and Its Applications, (M.L. Puterman, Ed.). - New York: Springer, pp 335-349.
[034] Puterman M.L. (1994): Markov Decision Processes: Discrete Stochastic Dynamic Programming. - New York: Wiley. | Zbl 0829.90134
[035] Rieder U. (1975): Bayesian dynamic programming. - Adv. Appl. Prob., Vol. 7, pp. 330-348. | Zbl 0316.90081
[036] Shapley L.S. (1953): Stochastic Games. - Proc. National. Acad. Sci., Mathematics, Vol. 39, pp. 1095-1100. | Zbl 0051.35805
[037] Shiryaev A.N. (1978): Optimal Stopping Problems. - New York: Springer. | Zbl 0391.60002
[038] Strauch R. (1966): Negative dynamic programming. - Ann. Math.Stat., Vol. 37, pp. 871-890. | Zbl 0144.43201
[039] Van der Wal J. (1981): Stochastic dynamic programming. - Math. Centre Tracts 139, Mathematisch Centrum, Amsterdam. | Zbl 0462.90055
[040] Veinott A.F., Jr. (1969): Discrete dynamic programming with sensitive discount optimality criteria. - Ann. Math. Stat., Vol. 40, No. 5, pp. 1635-1660. | Zbl 0183.49102
[041] Whittle P. (1983): Optimization over Time. - New York: Wiley, Vol. 2. | Zbl 0577.90046