Probability Distributions on Posets: An Application to Security Games

We study an abstract problem regarding probability distributions on posets. The problem is to resolve the existence of a probability distribution over subsets of a poset, such that a set of constraints involving marginal probabilities of the constituting elements and the maximal chains is satisfied. We construct a combinatorial algorithm to positively answer this question. Our result enables us to solve a broad class of network security games. In such games, an attacker interdicts one or more edges to maximize her value of interdicted flow while facing attack costs; and the operator routes her flow to maximize the value of effective flow while facing transportation costs. Importantly, our equilibrium analysis provides new insights on the vulnerability of network components to attacks, which are not captured by the traditional cut-based metrics of vulnerability.