An idempotent algorithm for a class of network-disruption games

William M. McEneaney; Amit Pandey

Kybernetika (2016)

  • Volume: 52, Issue: 5, page 666-695
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

M. McEneaney, William, and Pandey, Amit. "An idempotent algorithm for a class of network-disruption games." Kybernetika 52.5 (2016): 666-695. <http://eudml.org/doc/287528>.

@article{M2016,
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.},
author = {M. McEneaney, William, Pandey, Amit},
journal = {Kybernetika},
keywords = {idempotent; max-plus; tropical; network; dynamic programming; game theory; command and control; idempotent; max-plus; tropical; network; dynamic programming; game theory; command and control},
language = {eng},
number = {5},
pages = {666-695},
publisher = {Institute of Information Theory and Automation AS CR},
title = {An idempotent algorithm for a class of network-disruption games},
url = {http://eudml.org/doc/287528},
volume = {52},
year = {2016},
}

TY - JOUR
AU - M. McEneaney, William
AU - Pandey, Amit
TI - An idempotent algorithm for a class of network-disruption games
JO - Kybernetika
PY - 2016
PB - Institute of Information Theory and Automation AS CR
VL - 52
IS - 5
SP - 666
EP - 695
AB - 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.
LA - eng
KW - idempotent; max-plus; tropical; network; dynamic programming; game theory; command and control; idempotent; max-plus; tropical; network; dynamic programming; game theory; command and control
UR - http://eudml.org/doc/287528
ER -

References

top
  1. Akian, M., 10.1090/s0002-9947-99-02153-4, Trans. Amer. Math. Soc. 351 (1999), 4515-4543. Zbl0934.28005MR1466943DOI10.1090/s0002-9947-99-02153-4
  2. Akian, M., Gaubert, S., Lakhoua, A., 10.1137/060655286, SIAM J. Control Optim. 47 (2008), 817-848. Zbl1157.49034MR2385864DOI10.1137/060655286
  3. Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J.-P., Synchronization and Linearity., Wiley, New York 1992. Zbl0824.93003MR1204266
  4. Cohen, G., Gaubert, S., Quadrat, J.-P., 10.1016/j.laa.2003.08.010, Linear Algebra Appl. 379 (2004), 395-422. Zbl1042.46004MR2039751DOI10.1016/j.laa.2003.08.010
  5. Elliot, N. J., Kalton, N. J., 10.1090/memo/0126, Mem. Amer. Math. Soc. 126 (1972). MR0359845DOI10.1090/memo/0126
  6. Fleming, W. H., 10.1007/s00245-003-0785-3, Appl. Math. Optim. 49 (2004), 159-181. Zbl1138.93379MR2033833DOI10.1007/s00245-003-0785-3
  7. Fleming, W. H., Kaise, H., Sheu, S.-J., 10.1007/s00245-010-9097-6, Applied Math. Optim. 62 (2010), 81-144. Zbl1197.49029MR2653896DOI10.1007/s00245-010-9097-6
  8. Gaubert, S., McEneaney, W. M., 10.1007/s00245-011-9158-5, Applied Math. Optim. 65 (2012), 315-348. Zbl1244.93051MR2902695DOI10.1007/s00245-011-9158-5
  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, 10.1515/9781400865239, Princeton Univ. Press 2006. MR2188299DOI10.1515/9781400865239
  11. Kolokoltsov, V. N., Maslov, V. P., 10.1007/978-94-015-8901-7, Kluwer 1997. Zbl0941.93001MR1447629DOI10.1007/978-94-015-8901-7
  12. Litvinov, G. L., Maslov, V. P., Shpiz, G. B., 10.1023/a:1010266012029, Math. Notes 69 (2001), 696-729. Zbl1017.46034MR1846814DOI10.1023/a:1010266012029
  13. McEneaney, W. M., 10.1016/j.automatica.2010.10.006, Automatica 47 (2011), 443-451. Zbl1219.93146MR2878297DOI10.1016/j.automatica.2010.10.006
  14. McEneaney, W. M., 10.1007/0-8176-4453-9, Birkhauser, Boston 2006. Zbl1103.93005MR2189436DOI10.1007/0-8176-4453-9
  15. McEneaney, W. M., 10.1137/040610830, SIAM J. Control Optim. 46 (2007), 1239-1276. Zbl1251.65168MR2346381DOI10.1137/040610830
  16. McEneaney, W. M., 10.1109/acc.2011.5990870, In: Proc. 2011 Amer. Control Conf., pp. 4051-4056. DOI10.1109/acc.2011.5990870
  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., 10.1109/cdc.2009.5400306, In: Proc. IEEE CDC 2009, pp. 1569-1574. DOI10.1109/cdc.2009.5400306
  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., 10.1080/02331930600819852, Optimization 56 (2007) 171-205. Zbl1121.52002MR2288512DOI10.1080/02331930600819852
  21. Puhalskii, A., 10.1201/9781420035803, Chapman and Hall/CRC Press 2001. Zbl0983.60003MR1851048DOI10.1201/9781420035803
  22. Qu, Z., 10.1109/cdc.2014.7039624, In: Proc. 53rd IEEE Conf. on Dec. and Control 2014. DOI10.1109/cdc.2014.7039624
  23. Rubinov, A. M., Singer, I., 10.1080/02331930108844567, Optimization 50 (2001), 307-351. Zbl1007.26010MR1892908DOI10.1080/02331930108844567
  24. Singer, I., Abstract Convex Analysis., Wiley-Interscience, New York 1997. Zbl0941.49020MR1461544

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.