Geodesic
An idempotent algorithm for a class of network-disruption games
Kybernetika, Tome 52 (2016) no. 5, pp. 666-695
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

A game is considered where the communication network of the first player is explicitly modelled. The second player may induce delays in this network, while the first player may counteract such actions. Costs are modelled through expectations over idempotent probability measures. The idempotent probabilities are conditioned by observational data, the arrival of which may have been delayed along the communication network. This induces a game where the state space consists of the network delays. Even for small networks, the state-space dimension is high. Idempotent algebra-based methods are used to generate an algorithm not subject to the curse-of-dimensionality. An example is included.
A game is considered where the communication network of the first player is explicitly modelled. The second player may induce delays in this network, while the first player may counteract such actions. Costs are modelled through expectations over idempotent probability measures. The idempotent probabilities are conditioned by observational data, the arrival of which may have been delayed along the communication network. This induces a game where the state space consists of the network delays. Even for small networks, the state-space dimension is high. Idempotent algebra-based methods are used to generate an algorithm not subject to the curse-of-dimensionality. An example is included.
DOI : 10.14736/kyb-2016-5-0666
Classification : 14T05, 15A80, 49L20, 90C35, 91A80
Keywords: idempotent; max-plus; tropical; network; dynamic programming; game theory; command and control 
@article{10_14736_kyb_2016_5_0666,
     author = {M. McEneaney, William and Pandey, Amit},
     title = {An idempotent algorithm for a class of network-disruption games},
     journal = {Kybernetika},
     pages = {666--695},
     year = {2016},
     volume = {52},
     number = {5},
     doi = {10.14736/kyb-2016-5-0666},
     mrnumber = {3602010},
     zbl = {06674934},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-5-0666/}
}
TY  - JOUR
AU  - M. McEneaney, William
AU  - Pandey, Amit
TI  - An idempotent algorithm for a class of network-disruption games
JO  - Kybernetika
PY  - 2016
SP  - 666
EP  - 695
VL  - 52
IS  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-5-0666/
DO  - 10.14736/kyb-2016-5-0666
LA  - en
ID  - 10_14736_kyb_2016_5_0666
ER  - 
%0 Journal Article
%A M. McEneaney, William
%A Pandey, Amit
%T An idempotent algorithm for a class of network-disruption games
%J Kybernetika
%D 2016
%P 666-695
%V 52
%N 5
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2016-5-0666/
%R 10.14736/kyb-2016-5-0666
%G en
%F 10_14736_kyb_2016_5_0666
M. McEneaney, William; Pandey, Amit. An idempotent algorithm for a class of network-disruption games. Kybernetika, Tome 52 (2016) no. 5, pp. 666-695. doi: 10.14736/kyb-2016-5-0666

[1] Akian, M.: Densities of idempotent measures and large deviations. Trans. Amer. Math. Soc. 351 (1999), 4515-4543. | DOI | MR | Zbl

[2] Akian, M., Gaubert, S., Lakhoua, A.: The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis. SIAM J. Control Optim. 47 (2008), 817-848. | DOI | MR | Zbl

[3] Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J.-P.: Synchronization and Linearity. Wiley, New York 1992. | MR | Zbl

[4] Cohen, G., Gaubert, S., Quadrat, J.-P.: Duality and separation theorems in idempotent semimodules. Linear Algebra Appl. 379 (2004), 395-422. | DOI | MR | Zbl

[5] Elliot, N. J., Kalton, N. J.: The existence of value in differential games. Mem. Amer. Math. Soc. 126 (1972). | DOI | MR

[6] Fleming, W. H.: Max-plus stochastic processes. Appl. Math. Optim. 49 (2004), 159-181. | DOI | MR | Zbl

[7] Fleming, W. H., Kaise, H., Sheu, S.-J.: Max-plus stochastic control and risk-sensitivity. Applied Math. Optim. 62 (2010), 81-144. | DOI | MR | Zbl

[8] Gaubert, S., McEneaney, W. M.: Min-max spaces and complexity reduction in min-max expansions. Applied Math. Optim. 65 (2012), 315-348. | DOI | MR | Zbl

[9] Gaubert, S., Qu, Z., Sridharan, S.: Bundle-based pruning in the max-plus curse of dimensionality free method. In: Proc. 21st Int. Symp. Math. Theory of Networks and Systems 2014.

[10] Heidergott, B., Olsder, G. J., Woude, J. van der: Max-Plus at Work: Modeling and Analysis of Synchronized Systems. Princeton Univ. Press 2006. | DOI | MR

[11] Kolokoltsov, V. N., Maslov, V. P.: Idempotent Analysis and Its Applications. Kluwer 1997. | DOI | MR | Zbl

[12] Litvinov, G. L., Maslov, V. P., Shpiz, G. B.: Idempotent functional analysis: an algebraic approach. Math. Notes 69 (2001), 696-729. | DOI | MR | Zbl

[13] McEneaney, W. M.: Distributed dynamic programming for discrete-time stochastic control, and idempotent algorithms. Automatica 47 (2011), 443-451. | DOI | MR | Zbl

[14] McEneaney, W. M.: Max-Plus Methods for Nonlinear Control and Estimation. Birk\-hau\-ser, Boston 2006. | DOI | MR | Zbl

[15] McEneaney, W. M.: A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs. SIAM J. Control Optim. 46 (2007), 1239-1276. | DOI | MR | Zbl

[16] McEneaney, W. M.: Idempotent method for deception games. In: Proc. 2011 Amer. Control Conf., pp. 4051-4056. | DOI

[17] McEneaney, W. M., Desir, A.: Games of network disruption and idempotent algorithms. In: Proc. European Control Conf. 2013, pp. 702-709.

[18] McEneaney, W. M.: Idempotent algorithms for discrete-time stochastic control through distributed dynamic programming. In: Proc. IEEE CDC 2009, pp. 1569-1574. | DOI

[19] McEneaney, W. M., Charalambous, C. D.: Large deviations theory, induced log-plus and max-plus measures and their applications. In: Proc. Math. Theory Networks and Sys. 2000.

[20] Nitica, V., Singer, I.: Max-plus convex sets and max-plus semispaces I. Optimization 56 (2007) 171-205. | DOI | MR | Zbl

[21] Puhalskii, A.: Large Deviations and Idempotent Probability. Chapman and Hall/CRC Press 2001. | DOI | MR | Zbl

[22] Qu, Z.: A max-plus based randomized algorithm for solving a class of HJB PDEs. In: Proc. 53rd IEEE Conf. on Dec. and Control 2014. | DOI

[23] Rubinov, A. M., Singer, I.: Topical and sub-topical functions, downward sets and abstract convexity. Optimization 50 (2001), 307-351. | DOI | MR | Zbl

[24] Singer, I.: Abstract Convex Analysis. Wiley-Interscience, New York 1997. | MR | Zbl

Cité par Sources :