Probability Distributions on Partially Ordered Sets and Network Interdiction Games
<jats:p> 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 combinato...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143704 |
| _version_ | 1826214365332766720 |
|---|---|
| author | Dahan, Mathieu Amin, Saurabh Jaillet, Patrick |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Dahan, Mathieu Amin, Saurabh Jaillet, Patrick |
| author_sort | Dahan, Mathieu |
| collection | MIT |
| description | <jats:p> 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. </jats:p> |
| first_indexed | 2024-09-23T16:03:56Z |
| format | Article |
| id | mit-1721.1/143704 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:03:56Z |
| publishDate | 2022 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1437042023-08-11T17:18:36Z Probability Distributions on Partially Ordered Sets and Network Interdiction Games Dahan, Mathieu Amin, Saurabh Jaillet, Patrick Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Operations Research Center <jats:p> 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. </jats:p> 2022-07-13T15:18:11Z 2022-07-13T15:18:11Z 2022 2022-07-13T15:14:15Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/143704 Dahan, Mathieu, Amin, Saurabh and Jaillet, Patrick. 2022. "Probability Distributions on Partially Ordered Sets and Network Interdiction Games." Mathematics of Operations Research, 47 (1). en 10.1287/MOOR.2021.1140 Mathematics of Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) arXiv |
| spellingShingle | Dahan, Mathieu Amin, Saurabh Jaillet, Patrick Probability Distributions on Partially Ordered Sets and Network Interdiction Games |
| title | Probability Distributions on Partially Ordered Sets and Network Interdiction Games |
| title_full | Probability Distributions on Partially Ordered Sets and Network Interdiction Games |
| title_fullStr | Probability Distributions on Partially Ordered Sets and Network Interdiction Games |
| title_full_unstemmed | Probability Distributions on Partially Ordered Sets and Network Interdiction Games |
| title_short | Probability Distributions on Partially Ordered Sets and Network Interdiction Games |
| title_sort | probability distributions on partially ordered sets and network interdiction games |
| url | https://hdl.handle.net/1721.1/143704 |
| work_keys_str_mv | AT dahanmathieu probabilitydistributionsonpartiallyorderedsetsandnetworkinterdictiongames AT aminsaurabh probabilitydistributionsonpartiallyorderedsetsandnetworkinterdictiongames AT jailletpatrick probabilitydistributionsonpartiallyorderedsetsandnetworkinterdictiongames |