Decomposition of Probability Marginals for Security Games in Abstract Networks

11/09/2022

∙

by   Jannik Matuschke, et al.

∙

0

∙

share

Given a set system (E, 𝒫), let π∈ [0,1]^𝒫 be a vector of requirement values on the sets and let ρ∈ [0, 1]^E be a vector of probability marginals with ∑_e ∈ Pρ_e ≥π_P for all P ∈𝒫. We study the question under which conditions the marginals ρ can be decomposed into a probability distribution on the subsets of E such that the resulting random set intersects each P ∈𝒫 with probability at least π_P. Extending a result by Dahan, Amin, and Jaillet (MOR 2022) motivated by a network security game in directed acyclic graphs, we show that such a distribution exists if 𝒫 is an abstract network and the requirements are of the form π_P = 1 - ∑_e ∈ Pμ_e for some μ∈ [0, 1]^E. Our proof yields an explicit description of a feasible distribution that can be computed efficiently. As a consequence, equilibria for the security game studied by Dahan et al. can be efficiently computed even when the underlying digraph contains cycles. As a subroutine of our algorithm, we provide a combinatorial algorithm for computing shortest paths in abstract networks, answering an open question by McCormick (SODA 1996). We further show that a conservation law proposed by Dahan et al. for requirement functions in partially ordered sets can be reduced to the setting of affine requirements described above.