Inspection Game with Location-Specific Detection Capabilities: Exact and Approximate Algorithms for Strategic Resource Coordination Article Swipe

PDF

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2404.11545

We consider a zero-sum inspection game, in which a defender positions detectors across a critical system to detect multiple attacks caused by an attacker. We assume that detection is imperfect, and each detector location is associated with a probability of detecting attacks within its set of monitored system components. The objective of the defender (resp. attacker) is to minimize (resp. maximize) the expected number of undetected attacks. To compute Nash equilibria for this large-scale zero-sum game, we formulate a linear program with a small number of constraints that can be solved via column generation. We provide an exact mixed-integer program for the pricing problem and leverage its supermodular structure to design two efficient approaches for computing approximate Nash equilibria with theoretical guarantees: A column generation and a multiplicative weights update algorithm, both with approximate best responses. To address the computational challenges posed by combinatorial attacker strategies, each iteration of our multiplicative weights update algorithm computes a projection onto the polytope of marginal attack probabilities under the unnormalized relative entropy, for which we derive a closed-form expression and a linear-time algorithm. Computational results on real-world gas distribution networks illustrate the performance and scalability of our solution approaches.

Related Topics

Computer Science

Business

Concepts

Computer science Business

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2404.11545
PDF: https://arxiv.org/pdf/2404.11545
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4394948092

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4394948092

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2404.11545

Digital Object Identifier
Title: Inspection Game with Location-Specific Detection Capabilities: Exact and Approximate Algorithms for Strategic Resource Coordination

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-04-17

Full publication date if available
Authors: Bastián Bahamondes, Mathieu Dahan

List of authors in order
Landing page: https://arxiv.org/abs/2404.11545

Publisher landing page
PDF URL: https://arxiv.org/pdf/2404.11545

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2404.11545

Direct OA link when available
Concepts: Computer science, Business

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4394948092
doi	https://doi.org/10.48550/arxiv.2404.11545
ids.doi	https://doi.org/10.48550/arxiv.2404.11545
ids.openalex	https://openalex.org/W4394948092
fwci
type	preprint
title	Inspection Game with Location-Specific Detection Capabilities: Exact and Approximate Algorithms for Strategic Resource Coordination
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11512
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.902999997138977
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Anomaly Detection Techniques and Applications
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.4517790377140045
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C144133560
concepts[1].level	0
concepts[1].score	0.4397064745426178
concepts[1].wikidata	https://www.wikidata.org/wiki/Q4830453
concepts[1].display_name	Business
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.4517790377140045
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/business
keywords[1].score	0.4397064745426178
keywords[1].display_name	Business
language	en
locations[0].id	pmh:oai:arXiv.org:2404.11545
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2404.11545
locations[0].version	submittedVersion
locations[0].raw_type
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2404.11545
locations[1].id	doi:10.48550/arxiv.2404.11545
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2404.11545
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5040602322
authorships[0].author.orcid	https://orcid.org/0000-0002-5426-3717
authorships[0].author.display_name	Bastián Bahamondes
authorships[0].author_position	first
authorships[0].raw_author_name	Bahamondes, Bastián
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5067459518
authorships[1].author.orcid	https://orcid.org/0000-0003-0973-6973
authorships[1].author.display_name	Mathieu Dahan
authorships[1].author_position	last
authorships[1].raw_author_name	Dahan, Mathieu
authorships[1].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2404.11545
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2024-04-19T00:00:00
display_name	Inspection Game with Location-Specific Detection Capabilities: Exact and Approximate Algorithms for Strategic Resource Coordination
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11512
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.902999997138977
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Anomaly Detection Techniques and Applications
related_works	https://openalex.org/W4391375266, https://openalex.org/W2748952813, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W4391913857, https://openalex.org/W2350741829, https://openalex.org/W2530322880
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2404.11545
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2404.11545
best_oa_location.version	submittedVersion
best_oa_location.raw_type
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2404.11545
primary_location.id	pmh:oai:arXiv.org:2404.11545
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2404.11545
primary_location.version	submittedVersion
primary_location.raw_type
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2404.11545
publication_date	2024-04-17
publication_year	2024
referenced_works_count	0
abstract_inverted_index.A	122
abstract_inverted_index.a	2, 8, 13, 37, 78, 82, 126, 155, 173, 177
abstract_inverted_index.To	67, 136
abstract_inverted_index.We	0, 24, 94
abstract_inverted_index.an	22, 96
abstract_inverted_index.be	89
abstract_inverted_index.by	21, 142
abstract_inverted_index.in	6
abstract_inverted_index.is	28, 34, 56
abstract_inverted_index.of	39, 45, 51, 64, 85, 148, 160, 192
abstract_inverted_index.on	182
abstract_inverted_index.to	16, 57, 109
abstract_inverted_index.we	76, 171
abstract_inverted_index.The	49
abstract_inverted_index.and	30, 104, 125, 176, 190
abstract_inverted_index.can	88
abstract_inverted_index.for	71, 100, 114, 169
abstract_inverted_index.gas	184
abstract_inverted_index.its	43, 106
abstract_inverted_index.our	149, 193
abstract_inverted_index.set	44
abstract_inverted_index.the	52, 61, 101, 138, 158, 165, 188
abstract_inverted_index.two	111
abstract_inverted_index.via	91
abstract_inverted_index.Nash	69, 117
abstract_inverted_index.best	134
abstract_inverted_index.both	131
abstract_inverted_index.each	31, 146
abstract_inverted_index.onto	157
abstract_inverted_index.that	26, 87
abstract_inverted_index.this	72
abstract_inverted_index.with	36, 81, 119, 132
abstract_inverted_index.exact	97
abstract_inverted_index.game,	5, 75
abstract_inverted_index.posed	141
abstract_inverted_index.small	83
abstract_inverted_index.under	164
abstract_inverted_index.which	7, 170
abstract_inverted_index.(resp.	54, 59
abstract_inverted_index.across	12
abstract_inverted_index.assume	25
abstract_inverted_index.attack	162
abstract_inverted_index.caused	20
abstract_inverted_index.column	92, 123
abstract_inverted_index.derive	172
abstract_inverted_index.design	110
abstract_inverted_index.detect	17
abstract_inverted_index.linear	79
abstract_inverted_index.number	63, 84
abstract_inverted_index.solved	90
abstract_inverted_index.system	15, 47
abstract_inverted_index.update	129, 152
abstract_inverted_index.within	42
abstract_inverted_index.address	137
abstract_inverted_index.attacks	19, 41
abstract_inverted_index.compute	68
abstract_inverted_index.pricing	102
abstract_inverted_index.problem	103
abstract_inverted_index.program	80, 99
abstract_inverted_index.provide	95
abstract_inverted_index.results	181
abstract_inverted_index.weights	128, 151
abstract_inverted_index.attacker	144
abstract_inverted_index.attacks.	66
abstract_inverted_index.computes	154
abstract_inverted_index.consider	1
abstract_inverted_index.critical	14
abstract_inverted_index.defender	9, 53
abstract_inverted_index.detector	32
abstract_inverted_index.entropy,	168
abstract_inverted_index.expected	62
abstract_inverted_index.leverage	105
abstract_inverted_index.location	33
abstract_inverted_index.marginal	161
abstract_inverted_index.minimize	58
abstract_inverted_index.multiple	18
abstract_inverted_index.networks	186
abstract_inverted_index.polytope	159
abstract_inverted_index.relative	167
abstract_inverted_index.solution	194
abstract_inverted_index.zero-sum	3, 74
abstract_inverted_index.algorithm	153
abstract_inverted_index.attacker)	55
abstract_inverted_index.attacker.	23
abstract_inverted_index.computing	115
abstract_inverted_index.detecting	40
abstract_inverted_index.detection	27
abstract_inverted_index.detectors	11
abstract_inverted_index.efficient	112
abstract_inverted_index.formulate	77
abstract_inverted_index.iteration	147
abstract_inverted_index.maximize)	60
abstract_inverted_index.monitored	46
abstract_inverted_index.objective	50
abstract_inverted_index.positions	10
abstract_inverted_index.structure	108
abstract_inverted_index.algorithm,	130
abstract_inverted_index.algorithm.	179
abstract_inverted_index.approaches	113
abstract_inverted_index.associated	35
abstract_inverted_index.challenges	140
abstract_inverted_index.equilibria	70, 118
abstract_inverted_index.expression	175
abstract_inverted_index.generation	124
abstract_inverted_index.illustrate	187
abstract_inverted_index.imperfect,	29
abstract_inverted_index.inspection	4
abstract_inverted_index.projection	156
abstract_inverted_index.real-world	183
abstract_inverted_index.responses.	135
abstract_inverted_index.undetected	65
abstract_inverted_index.approaches.	195
abstract_inverted_index.approximate	116, 133
abstract_inverted_index.closed-form	174
abstract_inverted_index.components.	48
abstract_inverted_index.constraints	86
abstract_inverted_index.generation.	93
abstract_inverted_index.guarantees:	121
abstract_inverted_index.large-scale	73
abstract_inverted_index.linear-time	178
abstract_inverted_index.performance	189
abstract_inverted_index.probability	38
abstract_inverted_index.scalability	191
abstract_inverted_index.strategies,	145
abstract_inverted_index.theoretical	120
abstract_inverted_index.distribution	185
abstract_inverted_index.supermodular	107
abstract_inverted_index.unnormalized	166
abstract_inverted_index.Computational	180
abstract_inverted_index.combinatorial	143
abstract_inverted_index.computational	139
abstract_inverted_index.mixed-integer	98
abstract_inverted_index.probabilities	163
abstract_inverted_index.multiplicative	127, 150
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	2
citation_normalized_percentile