  Given a set system $(E, \mathcal{P})$ with $\rho \in [0, 1]^E$ and $\pi \in
[0,1]^{ \mathcal{P}}$, our goal is to find a probability distribution for a
random set $S \subseteq E$ such that $\operatorname{Pr}[e \in S] = \rho_e$ for
all $e \in E$ and $\operatorname{Pr}[P \cap S \neq \emptyset] \geq \pi_P$ for
all $P \in \mathcal{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 $\pi$ is of the affine form $\pi_P = 1 -
\sum_{e \in P} \mu_e$ for $\mu \in [0, 1]^E$. A necessary condition for the
existence of the desired distribution is that $\sum_{e \in P} \rho_e \geq
\pi_P$ for all $P \in \mathcal{P}$. We show that this condition is sufficient
if and only if $\mathcal{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, \mathcal{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 $\pi$ in DAGs can be
reduced to the setting of affine requirements described above.

Discrete Mathematics;Computer Science and Game Theory;Combinatorics