A Network Monitoring Game with Heterogeneous Component Criticality Levels
We consider an attacker-operator game for monitoring a large-scale network that is comprised of components that differ in their criticality levels. In this zero-sum game, the operator seeks to position a limited number of sensors to monitor the network against the attacker who strategically targets...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/132672 |
| _version_ | 1826203095988699136 |
|---|---|
| author | Milosevic, Jezdimir Dahan, Mathieu Amin, Saurabh Sandberg, Henrik |
| author2 | Massachusetts Institute of Technology. Center for Computational Engineering |
| author_facet | Massachusetts Institute of Technology. Center for Computational Engineering Milosevic, Jezdimir Dahan, Mathieu Amin, Saurabh Sandberg, Henrik |
| author_sort | Milosevic, Jezdimir |
| collection | MIT |
| description | We consider an attacker-operator game for monitoring a large-scale network that is comprised of components that differ in their criticality levels. In this zero-sum game, the operator seeks to position a limited number of sensors to monitor the network against the attacker who strategically targets a network component. The operator (resp. attacker) seeks to minimize (resp. maximize) the network loss. To study the properties of mixed-strategy Nash Equilibria of this game, we first study two simple instances: When component sets monitored from individual sensor locations are mutually disjoint; When only a single sensor is positioned, but with possibly overlapping monitoring component sets. Our analysis reveals new insights on how criticality levels impact the players equilibrium strategies. Next, we extend a previously developed approach to obtain an approximate Nash equilibrium in the general case. This approach uses solutions to minimum set cover and maximum set packing problems to construct an approximate Nash equilibrium. Finally, we implement a column generation procedure to improve this solution and numerically evaluate the performance of our approach. |
| first_indexed | 2024-09-23T12:31:16Z |
| format | Article |
| id | mit-1721.1/132672 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:31:16Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1326722024-05-21T17:39:22Z A Network Monitoring Game with Heterogeneous Component Criticality Levels Milosevic, Jezdimir Dahan, Mathieu Amin, Saurabh Sandberg, Henrik Massachusetts Institute of Technology. Center for Computational Engineering Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Massachusetts Institute of Technology. Institute for Data, Systems, and Society We consider an attacker-operator game for monitoring a large-scale network that is comprised of components that differ in their criticality levels. In this zero-sum game, the operator seeks to position a limited number of sensors to monitor the network against the attacker who strategically targets a network component. The operator (resp. attacker) seeks to minimize (resp. maximize) the network loss. To study the properties of mixed-strategy Nash Equilibria of this game, we first study two simple instances: When component sets monitored from individual sensor locations are mutually disjoint; When only a single sensor is positioned, but with possibly overlapping monitoring component sets. Our analysis reveals new insights on how criticality levels impact the players equilibrium strategies. Next, we extend a previously developed approach to obtain an approximate Nash equilibrium in the general case. This approach uses solutions to minimum set cover and maximum set packing problems to construct an approximate Nash equilibrium. Finally, we implement a column generation procedure to improve this solution and numerically evaluate the performance of our approach. 2021-10-01T13:18:31Z 2021-10-01T13:18:31Z 2019 2021-09-30T18:12:55Z Article http://purl.org/eprint/type/ConferencePaper 2576-2370 https://hdl.handle.net/1721.1/132672 J. Milošević, M. Dahan, S. Amin and H. Sandberg, "A Network Monitoring Game with Heterogeneous Component Criticality Levels," 2019 IEEE 58th Conference on Decision and Control (CDC), 2019, pp. 4379-4384 en 10.1109/CDC40024.2019.9029427 Proceedings of the IEEE Conference on Decision and Control Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Milosevic, Jezdimir Dahan, Mathieu Amin, Saurabh Sandberg, Henrik A Network Monitoring Game with Heterogeneous Component Criticality Levels |
| title | A Network Monitoring Game with Heterogeneous Component Criticality Levels |
| title_full | A Network Monitoring Game with Heterogeneous Component Criticality Levels |
| title_fullStr | A Network Monitoring Game with Heterogeneous Component Criticality Levels |
| title_full_unstemmed | A Network Monitoring Game with Heterogeneous Component Criticality Levels |
| title_short | A Network Monitoring Game with Heterogeneous Component Criticality Levels |
| title_sort | network monitoring game with heterogeneous component criticality levels |
| url | https://hdl.handle.net/1721.1/132672 |
| work_keys_str_mv | AT milosevicjezdimir anetworkmonitoringgamewithheterogeneouscomponentcriticalitylevels AT dahanmathieu anetworkmonitoringgamewithheterogeneouscomponentcriticalitylevels AT aminsaurabh anetworkmonitoringgamewithheterogeneouscomponentcriticalitylevels AT sandberghenrik anetworkmonitoringgamewithheterogeneouscomponentcriticalitylevels AT milosevicjezdimir networkmonitoringgamewithheterogeneouscomponentcriticalitylevels AT dahanmathieu networkmonitoringgamewithheterogeneouscomponentcriticalitylevels AT aminsaurabh networkmonitoringgamewithheterogeneouscomponentcriticalitylevels AT sandberghenrik networkmonitoringgamewithheterogeneouscomponentcriticalitylevels |