This article poses the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset's elements and maximal chains is satisfied? We present a combinatorial algorithm to positively resolve this question. The algorithm can be implemented in polynomial time in the special case where maximal chain probabilities are affine functions of their elements. This existence problem is relevant for the equilibrium characterization of a generic strategic interdiction game on a capacitated flow network. The game involves a routing entity that sends its flow through the network while facing path transportation costs, and an interdictor who simultaneously interdicts one or more edges while facing edge interdiction costs. Using our existence result on posets and strict complementary slackness in linear programming, we show that the Nash equilibria of this game can be fully described using primal and dual solutions of a minimum-cost circulation problem. Our analysis provides a new characterization of the critical components in the interdiction game. It also leads to a polynomial-time approach for equilibrium computation.

翻译：本条提出了如下问题: 是否在有限部分定单的子集( 位数) 上存在概率分布, 从而满足一系列限制, 包括表面元素和最大链链的边际概率? 我们为积极解决这一问题提出了一个组合算法。 该算法可以在多个时段实施, 在特殊情况下, 最大链概率是其元素的对等功能。 这个存在问题与能力强的流量网络上通用战略阻截游戏的均衡定性有关。 该游戏涉及一个在面临路径运输成本时通过网络输送其流量的实体, 以及一个在面临边缘阻截成本时同时拦截一个或多个边缘的截击器。 我们利用我们关于表面和线性编程的严格补充松懈的结果, 显示这个游戏的 Nash 平衡可以用最低成本循环问题的原始和双重解决方案来充分描述。 我们的分析为阻截游戏的关键组件提供了新的定性。 它还导致平衡计算时的多时段方法 。