Abstract
Given a set system (E, P) with ρ ∈ [0, 1]^E and π ∈ [0,1]^ P, our goal is to find a probability distribution for a random set S ⊆ E such that Pr[e ∈ S] = ρ_e for all e ∈ E and Pr[P ∩ S ≠ ∅] ≥ π_P for all P ∈ P. We extend the results of Dahan, Amin, and Jaillet (MOR 2022) who studied this problem motivated by a security game in a directed acyclic graph (DAG). We focus on the setting where π is of the affine form π_P = 1 - Σ_e ∈ P μ_e for μ ∈ [0, 1]^E. A necessary condition for the existence of the desired distribution is that Σ_e ∈ P ρ_e ≥ π_P for all P ∈ P. We show that this condition is sufficient if and only if P has the weak max-flow/min-cut property. We further provide an efficient combinatorial algorithm for computing the corresponding distribution in the special case where (E, P) is an abstract network. As a consequence, equilibria for the security game by Dahan et al. can be efficiently computed in a wide variety of settings (including arbitrary digraphs). As a subroutine of our algorithm, we provide a combinatorial algorithm for computing shortest paths in abstract networks, partially answering an open question by McCormick (SODA 1996). We further show that a conservation law proposed by Dahan et al. for the requirement vector π in DAGs can be reduced to the setting of affine requirements described above.