Decomposition of Probability Marginals for Security Games in Abstract Networks and Ideal Clutters.

Abstract: Consider a set system on a finite ground set E, where each set P in the system is equipped with a required hitting probability r(P) and each element e of E has a probability marginal p(e). We study the question whether the marginals can be decomposed into a distribution over all subsets of E such that the resulting random set intersects each set P from the system with probability at least r(P). A simple necessary condition is that for every set P in the system, the sum of the marginals of elements in P is at least r(P).

Extending a result by Dahan, Amin, and Jaillet (Mathematics of Operations Research 47:457-484, 2022) motivated by a security game in a directed acyclic graph, we show that the aforementioned necessary condition is also sufficient in the following two settings: (i) the set system fulfills a max-flow/min-cut property and the requirements are affine; (ii) the set system is an abstract network and the requirements fulfill a weak conservation law. We provide algorithms for the computation of the corresponding decompositions and, in some cases, simple explicit descriptions of these decompositions. As a subroutine, we also devise a combinatorial algorithm for computing shortest paths in abstract networks, partially answering an open question by McCormick (SODA 1996). A consequence of our results is that equilibria for the security game studied by Dahan et al. (2022) and similar games involving randomized surveillance strategies can be computed efficiently, even when the underlying digraph contains cycles.

Posted on Mar 13, 2023 in ACGO, Seminars