| Title:
|
An idempotent algorithm for a class of network-disruption games (English) |
| Author:
|
M. McEneaney, William |
| Author:
|
Pandey, Amit |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
52 |
| Issue:
|
5 |
| Year:
|
2016 |
| Pages:
|
666-695 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
idempotent |
| Keyword:
|
max-plus |
| Keyword:
|
tropical |
| Keyword:
|
network |
| Keyword:
|
dynamic programming |
| Keyword:
|
game theory |
| Keyword:
|
command and control |
| MSC:
|
14T05 |
| MSC:
|
15A80 |
| MSC:
|
49L20 |
| MSC:
|
90C35 |
| MSC:
|
91A80 |
| idZBL:
|
Zbl 06674934 |
| idMR:
|
MR3602010 |
| DOI:
|
10.14736/kyb-2016-5-0666 |
| . |
| Date available:
|
2017-01-02T13:23:53Z |
| Last updated:
|
2018-01-10 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145963 |
| . |
| Reference:
|
[1] Akian, M.: Densities of idempotent measures and large deviations..Trans. Amer. Math. Soc. 351 (1999), 4515-4543. Zbl 0934.28005, MR 1466943, 10.1090/s0002-9947-99-02153-4 |
| Reference:
|
[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. Zbl 1157.49034, MR 2385864, 10.1137/060655286 |
| Reference:
|
[3] Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J.-P.: Synchronization and Linearity..Wiley, New York 1992. Zbl 0824.93003, MR 1204266 |
| Reference:
|
[4] Cohen, G., Gaubert, S., Quadrat, J.-P.: Duality and separation theorems in idempotent semimodules..Linear Algebra Appl. 379 (2004), 395-422. Zbl 1042.46004, MR 2039751, 10.1016/j.laa.2003.08.010 |
| Reference:
|
[5] Elliot, N. J., Kalton, N. J.: The existence of value in differential games..Mem. Amer. Math. Soc. 126 (1972). MR 0359845, 10.1090/memo/0126 |
| Reference:
|
[6] Fleming, W. H.: Max-plus stochastic processes..Appl. Math. Optim. 49 (2004), 159-181. Zbl 1138.93379, MR 2033833, 10.1007/s00245-003-0785-3 |
| Reference:
|
[7] Fleming, W. H., Kaise, H., Sheu, S.-J.: Max-plus stochastic control and risk-sensitivity..Applied Math. Optim. 62 (2010), 81-144. Zbl 1197.49029, MR 2653896, 10.1007/s00245-010-9097-6 |
| Reference:
|
[8] Gaubert, S., McEneaney, W. M.: Min-max spaces and complexity reduction in min-max expansions..Applied Math. Optim. 65 (2012), 315-348. Zbl 1244.93051, MR 2902695, 10.1007/s00245-011-9158-5 |
| Reference:
|
[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. |
| Reference:
|
[10] Heidergott, B., Olsder, G. J., Woude, J. van der: Max-Plus at Work: Modeling and Analysis of Synchronized Systems..Princeton Univ. Press 2006. MR 2188299, 10.1515/9781400865239 |
| Reference:
|
[11] Kolokoltsov, V. N., Maslov, V. P.: Idempotent Analysis and Its Applications..Kluwer 1997. Zbl 0941.93001, MR 1447629, 10.1007/978-94-015-8901-7 |
| Reference:
|
[12] Litvinov, G. L., Maslov, V. P., Shpiz, G. B.: Idempotent functional analysis: an algebraic approach..Math. Notes 69 (2001), 696-729. Zbl 1017.46034, MR 1846814, 10.1023/a:1010266012029 |
| Reference:
|
[13] McEneaney, W. M.: Distributed dynamic programming for discrete-time stochastic control, and idempotent algorithms..Automatica 47 (2011), 443-451. Zbl 1219.93146, MR 2878297, 10.1016/j.automatica.2010.10.006 |
| Reference:
|
[14] McEneaney, W. M.: Max-Plus Methods for Nonlinear Control and Estimation..Birk\-hau\-ser, Boston 2006. Zbl 1103.93005, MR 2189436, 10.1007/0-8176-4453-9 |
| Reference:
|
[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. Zbl 1251.65168, MR 2346381, 10.1137/040610830 |
| Reference:
|
[16] McEneaney, W. M.: Idempotent method for deception games..In: Proc. 2011 Amer. Control Conf., pp. 4051-4056. 10.1109/acc.2011.5990870 |
| Reference:
|
[17] McEneaney, W. M., Desir, A.: Games of network disruption and idempotent algorithms..In: Proc. European Control Conf. 2013, pp. 702-709. |
| Reference:
|
[18] McEneaney, W. M.: Idempotent algorithms for discrete-time stochastic control through distributed dynamic programming..In: Proc. IEEE CDC 2009, pp. 1569-1574. 10.1109/cdc.2009.5400306 |
| Reference:
|
[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. |
| Reference:
|
[20] Nitica, V., Singer, I.: Max-plus convex sets and max-plus semispaces I..Optimization 56 (2007) 171-205. Zbl 1121.52002, MR 2288512, 10.1080/02331930600819852 |
| Reference:
|
[21] Puhalskii, A.: Large Deviations and Idempotent Probability..Chapman and Hall/CRC Press 2001. Zbl 0983.60003, MR 1851048, 10.1201/9781420035803 |
| Reference:
|
[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. 10.1109/cdc.2014.7039624 |
| Reference:
|
[23] Rubinov, A. M., Singer, I.: Topical and sub-topical functions, downward sets and abstract convexity..Optimization 50 (2001), 307-351. Zbl 1007.26010, MR 1892908, 10.1080/02331930108844567 |
| Reference:
|
[24] Singer, I.: Abstract Convex Analysis..Wiley-Interscience, New York 1997. Zbl 0941.49020, MR 1461544 |
| . |
