×

Probability distributions on partially ordered sets and network interdiction games. (English) Zbl 07527997

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

MSC:

91A43 Games involving graphs
06B35 Continuous lattices and posets, applications
05C21 Flows in graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] [1] Adler I, Monteiro RDC (1992) A geometric view of parametric linear programming. Algorithmica 8(1):161-176.Crossref, Google Scholar · Zbl 0767.90042 · doi:10.1007/BF01758841
[2] [2] Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Upper Saddle River, NJ).Google Scholar · Zbl 1201.90001
[3] [3] Aneja YP, Chandrasekaran R, Nair KPK (2001) Maximizing residual flow under an arc destruction. Networks 38(4):194-198.Crossref, Google Scholar · Zbl 0993.90014 · doi:10.1002/net.10001
[4] [4] Assadi S, Emamjomeh-Zadeh E, Norouzi-Fard A, Yazdanbod S, Zarrabi-Zadeh H (2014) The minimum vulnerability problem. Algorithmica 70(4):718-731.Crossref, Google Scholar · Zbl 1306.05113 · doi:10.1007/s00453-014-9927-z
[5] [5] Assimakopoulos N (1987) A network interdiction model for hospital infection control. Comput. Biology Medicine 17(6):413-422.Crossref, Google Scholar · doi:10.1016/0010-4825(87)90060-6
[6] [6] Avenhaus R, Canty MJ (2009) Inspection games. Meyers RA, ed. Encyclopedia of Complexity and Systems Science (Springer, New York), 4855-4868.Crossref, Google Scholar · Zbl 1171.93001 · doi:10.1007/978-0-387-30440-3_287
[7] [7] Balinski M, Tucker A (1969) Duality theory of linear programs: A constructive approach with applications. SIAM Rev. 11(3):347-377.Crossref, Google Scholar · Zbl 0225.90024 · doi:10.1137/1011060
[8] [8] Ball MO, Golden BL, Vohra RV (1989) Finding the most vital arcs in a network. Oper. Res. Lett. 8(2):73-76.Crossref, Google Scholar · Zbl 0679.90086 · doi:10.1016/0167-6377(89)90003-5
[9] [9] Baykal-Gürsoy M, Duan Z, Poor HV, Garnaev A (2014) Infrastructure security games. Eur. J. Oper. Res. 239(2):469-478.Crossref, Google Scholar · Zbl 1339.90105 · doi:10.1016/j.ejor.2014.04.033
[10] [10] Bertsimas D, Nasrabadi E, Orlin JB (2016) On the power of randomization in network interdiction. Oper. Res. Lett. 44(1):114-120.Crossref, Google Scholar · Zbl 1408.91038 · doi:10.1016/j.orl.2015.11.005
[11] [11] Bertsimas D, Nasrabadi E, Stiller S (2013) Robust and adaptive network flows. Oper. Res. 61(5):1218-1242.Link, Google Scholar · Zbl 1291.90046
[12] [12] Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Oper. Res. 46(2):184-197.Link, Google Scholar · Zbl 0987.90516
[13] [13] Disser Y, Matuschke J (2020) The complexity of computing a robust flow. Oper. Res. Lett. 48(1):18-23.Crossref, Google Scholar · Zbl 1525.90091 · doi:10.1016/j.orl.2019.10.012
[14] [14] Dwivedi A, Yu X (2013) A maximum-flow-based complex network approach for power system vulnerability analysis. IEEE Trans. Indust. Inform. 9(1):81-88.Crossref, Google Scholar · doi:10.1109/TII.2011.2173944
[15] [15] Gilpin A, Hoda S, Peña J, Sandholm T (2007) Gradient-based algorithms for finding Nash equilibria in extensive form games. Deng X, Graham FC, eds. Internet and Network Economics (Springer, Berlin Heidelberg), 57-69.Crossref, Google Scholar · doi:10.1007/978-3-540-77105-0_9
[16] [16] Goldman AJ, Tucker AW (1957) Theory of linear programming. Kuhn HW, Tucker AW, eds. Linear Inequalities and Related Systems, Annals of Mathematic Studies, vol. 38 (Princeton University Press, Princeton, NJ), 53-98.Crossref, Google Scholar · Zbl 0072.37601 · doi:10.1515/9781400881987-005
[17] [17] Gueye A, Marbukh V (2012) A game-theoretic framework for network security vulnerability assessment and mitigation. Grossklags J, Walrand J, eds. Decision and Game Theory for Security (Springer, Berlin Heidelberg), 186-200.Crossref, Google Scholar · Zbl 1377.90013 · doi:10.1007/978-3-642-34266-0_11
[18] [18] Gueye A, Marbukh V, Walrand JC (2012) Towards a metric for communication network vulnerability to attacks: A game theoretic approach. Krishnamurthy V, Zhao Q, Huang M, Wen Y, eds. Game Theory for Networks (Springer, Berlin Heidelberg), 259-274.Crossref, Google Scholar · Zbl 1268.91037 · doi:10.1007/978-3-642-35582-0_20
[19] [19] Guo Q, An B, Zick Y, Miao C (2016) Optimal interdiction of illegal network flow. Proc. 25th Internat. Joint Conf. Artificial Intelligence (AAAI Press/IJCAI, Palo Alto, CA), 2507-2513.Google Scholar
[20] [20] Hoàng CT (1994) Efficient algorithms for minimum weighted colouring of some classes of perfect graphs. Discrete Appl. Math. 55(2):133-143.Crossref, Google Scholar · Zbl 0815.68076 · doi:10.1016/0166-218X(94)90004-3
[21] [21] Jansen B, Roos C, Terlaky T (1994) The theory of linear programming: Skew symmetric self-dual problems and the central path. Optim. 29(3):225-233.Crossref, Google Scholar · Zbl 0820.90067 · doi:10.1080/02331939408843952
[22] [22] Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4(4):373-395.Crossref, Google Scholar · Zbl 0557.90065 · doi:10.1007/BF02579150
[23] [23] Lipton RJ, Markakis E, Mehta A (2003) Playing large games using simple strategies. Proc. 4th ACM Conf. Electronic Commerce (ACM, New York), 36-41.Google Scholar
[24] [24] McMahan HB, Gordon GJ, Blum A (2003) Planning in the presence of cost functions controlled by an adversary. Proc. 20th Internat. Conf. Machine Learn. (AAAI Press, Palo Alto, CA), 536-543.Google Scholar
[25] [25] McMasters AW, Mustin TM (1970) Optimal interdiction of a supply network. Naval Res. Logist. Quart. 17(3):261-268.Crossref, Google Scholar · Zbl 0222.90017 · doi:10.1002/nav.3800170302
[26] [26] Neumayer S, Zussman G, Cohen R, Modiano E (2008) Assessing the impact of geographically correlated network failures. Proc. 2008 Military Commun. Conf. (IEEE, Piscataway, NJ), 1-6.Google Scholar
[27] [27] Orlin JB, Plotkin SA, Tardos É (1993) Polynomial dual network simplex algorithms. Math. Programming 60(1):255-276.Crossref, Google Scholar · Zbl 0784.90097 · doi:10.1007/BF01580615
[28] [28] Ratliff HD, Sicilia GT, Lubore SH (1975) Finding the n most vital links in flow networks. Management Sci. 21(5):531-539.Link, Google Scholar · Zbl 0311.90073
[29] [29] Sullivan KM, Cole Smith J (2014) Exact algorithms for solving a Euclidean maximum flow network interdiction problem. Networks 64(2):109-124.Crossref, Google Scholar · Zbl 1387.90294 · doi:10.1002/net.21561
[30] [30] Szeto W (2013) Routing and scheduling hazardous material shipments: Nash game approach. Transportmetrica B: Transport Dynam. 1(3):237-260.Crossref, Google Scholar · doi:10.1080/21680566.2013.861330
[31] [31] Washburn A, Wood K (1995) Two-person zero-sum games for network interdiction. Oper. Res. 43(2):243-251.Link, Google Scholar · Zbl 0832.90124
[32] [32] Wollmer R (1964) Removing arcs from a network. Oper. Res. 12(6):934-940.Link, Google Scholar · Zbl 0204.20102
[33] [33] Wood RK (1993) Deterministic network interdiction. Math. Comput. Model. 17(2):1-18.Crossref, Google Scholar · Zbl 0800.90772 · doi:10.1016/0895-7177(93)90236-R
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.