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 \(\textbf{Pr}\left[ e \in S\right] = \rho _e\) for all \(e \in E\) and \(\textbf{Pr}\left[ P \cap S \ne \emptyset \right] \ge \pi _P\) for all \(P \in \mathcal {P}\) . We extend the results of Dahan, Amin, and Jaillet [6] 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 \ge \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 in [6] 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 [20]. We further show that a conservation law proposed in [6] for the requirement vector \(\pi \) in DAGs can be reduced to the setting of affine requirements described above.
