Decomposing Probability Marginals Beyond Affine Requirements

Consider the triplet \((E, \mathcal {P}, \pi )\) , where E is a finite ground set,  \(\mathcal {P}\subseteq 2^E\) is a collection of subsets of E and \(\pi : \mathcal {P}\rightarrow [0,1]\) is a requirement function. Given a vector of marginals \(\rho \in [0, 1]^E\) , our goal is to find a distribution for a random subset \(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}\) , or to determine that no such distribution exists. Generalizing results of Dahan, Amin, and Jaillet [6], we devise a generic decomposition algorithm that solves the above problem when provided with a suitable sequence of admissible support candidates (ASCs). We show how to construct such ASCs for numerous settings, including supermodular requirements, Hoffman-Schwartz-type lattice polyhedra [14], and abstract networks where \(\pi \) fulfils a conservation law. The resulting algorithm can be carried out efficiently when  \(\mathcal {P}\) and  \(\pi \) can be accessed via appropriate oracles. For any system allowing the construction of ASCs, our results imply a simple polyhedral description of the set of marginal vectors for which the decomposition problem is feasible. Finally, we characterize balanced hypergraphs as the systems  \((E, \mathcal {P})\) that allow the perfect decomposition of any marginal vector \(\rho \in [0,1]^E\) , i.e., where we can always find a distribution reaching the highest attainable probability  \(\textbf{Pr}\left[ P \cap S \ne \emptyset \right] = \min \left\{ \sum _{e \in P} \rho _e, 1\right\} \) for all  \(P \in \mathcal {P}\) .