kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Network Monitoring Game with Heterogeneous Component Criticality Levels
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Decision and Control Systems (Automatic Control).ORCID iD: 0000-0002-2045-5665
KTH, School of Electrical Engineering and Computer Science (EECS), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Decision and Control Systems (Automatic Control).ORCID iD: 0000-0003-1835-2963
2019 (English)In: Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc. , 2019, p. 4379-4384Conference paper, Published paper (Refereed)
Abstract [en]

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. 

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers Inc. , 2019. p. 4379-4384
Keywords [en]
Computation theory, Game theory, Linear programming, Column generation, Equilibrium strategy, Heterogeneous component, Large-scale network, Minimum set cover, Network Monitoring, Sensor location, Set packing problem, Criticality (nuclear fission)
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-274080DOI: 10.1109/CDC40024.2019.9029427ISI: 000560779004006Scopus ID: 2-s2.0-85082501356ISBN: 9781728113982 (print)OAI: oai:DiVA.org:kth-274080DiVA, id: diva2:1451195
Conference
58th IEEE Conference on Decision and Control, CDC 2019, 11 December 2019 through 13 December 2019
Note

QC 20200702

Available from: 2020-07-02 Created: 2020-07-02 Last updated: 2022-12-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Milosevic, JezdimirSandberg, Henrik

Search in DiVA

By author/editor
Milosevic, JezdimirSandberg, Henrik
By organisation
Decision and Control Systems (Automatic Control)ACCESS Linnaeus Centre
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf