Probability Distributions on Partially Ordered Sets and Network Interdiction Games
Probability Distributions on Partially Ordered Sets and Network Interdiction Games
复制标题
DOI：
10.1287/moor.2021.1140
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Mathieu Dahan;Saurabh Amin;Patrick Jaillet
中科院分区：
文献类型：
--
作者：
Mathieu Dahan;Saurabh Amin;Patrick Jaillet
本文提出了以下问题：是否存在一个有限偏序集（偏序集）的子集上的概率分布，使得包含偏序集元素和最大链的边际概率的一组约束满足？我们提出了一种组合算法来积极解决这个问题。在最大链概率为其元素的仿射函数的特殊情况下，该算法可以在多项式时间内实现。这一存在性问题与有能力流网络上通用策略拦截对策的均衡表征有关。该博弈涉及一个路由实体，它在面临路径运输成本的情况下通过网络发送其流，以及一个拦截器，它在面临边缘拦截成本的情况下同时拦截一条或多条边。利用线性规划中关于偏置集和严格互补松弛性的存在性结果，证明了该博弈的纳什均衡可以用最小代价循环问题的原始解和对偶解来完全描述。我们的分析提供了一个新的特征在拦截游戏的关键组成部分。这也导致了平衡计算的多项式时间方法。
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.