Seminar: Jannik Matuschke (KU Leuven)

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 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,
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.

Video: