Decomposition of Probability Marginals for Security Games in Max-Flow/Min-Cut Systems

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 $\mathrm{Pr}[e\in S]={\rho }_e$ for all $e\in E$ and $\mathrm{Pr}[P\cap S\mathrm{\ne }\mathrm{\varnothing }]\ge {\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\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 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.