Title :
Games of network disruption and idempotent algorithms
Author :
McEneaney, William M. ; Desir, Antoine
Author_Institution :
Dept. of Mech. & Aerosp. Eng., Univ. of California San Diego, La Jolla, CA, USA
Abstract :
We consider a game on the space of network disruptions. An application in command and control is used as a guide for the development of the model. The outcome of any set of physical actions depends on the information available to the controller. We suppose that information flows along a network of humans and machines. The opposing player may act to intermittently block information flow along the network. This may be combined with physical actions such that our controller might be making decisions based on information that is not as current as would be possible without the induced delays. We find that the model of information delay dynamics is best captured as a controlled min-plus linear system. We also find that the minimax value function may be represented as a min-plus convex functional over the space of delay vectors. This is a max-min linear space. Backward dynamic programming propagation of the value function leads to (max-min) sum and product compositions. This yields a particularly nice solution algorithm. Computational and solution-representation complexity are examined.
Keywords :
computational complexity; game theory; linear systems; network theory (graphs); command and control; controlled min-plus linear system; delay vectors; idempotent algorithms; information delay dynamics; information flows; max-min linear space; min-plus convex functional; network disruption games; solution-representation complexity; Aerospace electronics; Delays; Games; Probability distribution; Sensors; Vectors;
Conference_Titel :
Control Conference (ECC), 2013 European
Conference_Location :
Zurich