Probability Distributions on Partially Ordered Sets and Network Interdiction Games

Mathieu Dahan (), Saurabh Amin () and Patrick Jaillet ()
Additional contact information
Mathieu Dahan: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Saurabh Amin: Department of Civil and Environmental Engineering, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Patrick Jaillet: Department of Electrical Engineering and Computer Science, Laboratory for Information and Decision Systems, and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Mathematics of Operations Research, 2022, vol. 47, issue 1, 458-484

Abstract: 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.

Keywords: Primary: 06A07; 91A05; 91A43; secondary: 05C21; 90C06; 90C46; probability distributions on posets; network interdiction games; duality theory (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1140 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:1:p:458-484

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().