Kybernetika 52 no. 5, 666-695, 2016

An idempotent algorithm for a class of network-disruption games

William M. McEneaney and Amit PandeyDOI: 10.14736/kyb-2016-5-0666

Abstract:

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.

Keywords:

game theory, dynamic programming, idempotent, max-plus, tropical, network, command and control

Classification:

15A80, 49L20, 90C35, 91A80, 14T05

paper.pdf

References:

  1. M. Akian: Densities of idempotent measures and large deviations. Trans. Amer. Math. Soc. 351 (1999), 4515-4543.   DOI:10.1090/s0002-9947-99-02153-4
  2. M. Akian, S. Gaubert and A. Lakhoua: 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:10.1137/060655286
  3. F. L. Baccelli, G. Cohen, G. J. Olsder and J.-P. Quadrat: Synchronization and Linearity. Wiley, New York 1992.   CrossRef
  4. G. Cohen, S. Gaubert and J.-P. Quadrat: Duality and separation theorems in idempotent semimodules. Linear Algebra Appl. 379 (2004), 395-422.   DOI:10.1016/j.laa.2003.08.010
  5. N. J. Elliot and N. J. Kalton: The existence of value in differential games. Mem. Amer. Math. Soc. 126 (1972).   DOI:10.1090/memo/0126
  6. W. H. Fleming: Max-plus stochastic processes. Appl. Math. Optim. 49 (2004), 159-181.   DOI:10.1007/s00245-003-0785-3
  7. W. H. Fleming, H. Kaise and S.-J. Sheu: Max-plus stochastic control and risk-sensitivity. Applied Math. Optim. 62 (2010), 81-144.   DOI:10.1007/s00245-010-9097-6
  8. S. Gaubert and W. M. McEneaney: Min-max spaces and complexity reduction in min-max expansions. Applied Math. Optim. 65 (2012), 315-348.   DOI:10.1007/s00245-011-9158-5
  9. S. Gaubert, Z. Qu and S. Sridharan: Bundle-based pruning in the max-plus curse of dimensionality free method. In: Proc. 21st Int. Symp. Math. Theory of Networks and Systems 2014.   CrossRef
  10. B. Heidergott, G. J. Olsder and J. van der Woude: Max-Plus at Work: Modeling and Analysis of Synchronized Systems. Princeton Univ. Press 2006.   DOI:10.1515/9781400865239
  11. V. N. Kolokoltsov and V. P. Maslov: Idempotent Analysis and Its Applications. Kluwer 1997.   DOI:10.1007/978-94-015-8901-7
  12. G. L. Litvinov, V. P. Maslov and G. B. Shpiz: Idempotent functional analysis: an algebraic approach. Math. Notes 69 (2001), 696-729.   DOI:10.1023/a:1010266012029
  13. W. M. McEneaney: Distributed dynamic programming for discrete-time stochastic control, and idempotent algorithms. Automatica 47 (2011), 443-451.   DOI:10.1016/j.automatica.2010.10.006
  14. W. M. McEneaney: Max-Plus Methods for Nonlinear Control and Estimation. Birk\-hau\-ser, Boston 2006.   DOI:10.1007/0-8176-4453-9
  15. W. M. McEneaney: A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs. SIAM J. Control Optim. 46 (2007), 1239-1276.   DOI:10.1137/040610830
  16. W. M. McEneaney: Idempotent method for deception games. In: Proc. 2011 Amer. Control Conf., pp. 4051-4056.   DOI:10.1109/acc.2011.5990870
  17. W. M. McEneaney and A. Desir: Games of network disruption and idempotent algorithms. In: Proc. European Control Conf. 2013, pp. 702-709.   CrossRef
  18. W. M. McEneaney: Idempotent algorithms for discrete-time stochastic control through distributed dynamic programming. In: Proc. IEEE CDC 2009, pp. 1569-1574.   DOI:10.1109/cdc.2009.5400306
  19. W. M. McEneaney and C. D. Charalambous: Large deviations theory, induced log-plus and max-plus measures and their applications. In: Proc. Math. Theory Networks and Sys. 2000.   CrossRef
  20. V. Nitica and I. Singer: Max-plus convex sets and max-plus semispaces I. Optimization 56 (2007) 171-205.   DOI:10.1080/02331930600819852
  21. A. Puhalskii: Large Deviations and Idempotent Probability. Chapman and Hall/CRC Press 2001.   DOI:10.1201/9781420035803
  22. Z. Qu: A max-plus based randomized algorithm for solving a class of HJB PDEs. In: Proc. 53rd IEEE Conf. on Dec. and Control 2014.   DOI:10.1109/cdc.2014.7039624
  23. A. M. Rubinov and I. Singer: Topical and sub-topical functions, downward sets and abstract convexity. Optimization 50 (2001), 307-351.   DOI:10.1080/02331930108844567
  24. I. Singer: Abstract Convex Analysis. Wiley-Interscience, New York 1997.   CrossRef