Back to Search
Start Over
Probability Distributions on Partially Ordered Sets and Network Interdiction Games
- Source :
- Mathematics of Operations Research. 47:458-484
- Publication Year :
- 2022
- Publisher :
- Institute for Operations Research and the Management Sciences (INFORMS), 2022.
-
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.
- Subjects :
- FOS: Computer and information sciences
021103 operations research
General Mathematics
0211 other engineering and technologies
0102 computer and information sciences
02 engineering and technology
Management Science and Operations Research
16. Peace & justice
01 natural sciences
Computer Science Applications
Computer Science - Computer Science and Game Theory
Optimization and Control (math.OC)
010201 computation theory & mathematics
FOS: Mathematics
Mathematics - Optimization and Control
Computer Science and Game Theory (cs.GT)
Subjects
Details
- ISSN :
- 15265471 and 0364765X
- Volume :
- 47
- Database :
- OpenAIRE
- Journal :
- Mathematics of Operations Research
- Accession number :
- edsair.doi.dedup.....643f8942a055218d6816c4dd6331ccc9