IDEAS home Printed from
   My bibliography  Save this paper

From Sabotage Games to Border Protection


  • Kvasov, Dmitriy


Sabotage games on a graph involve Runner who wants to travel between two given vertices and Blocker who aims to prevent Runner from arriving at his destination by destroying edges. This paper introduces and studies several generalizations of sabotage games. First, it completely characterizes games with multiple destinations on weighted trees for both local and global cutting rules of arbitrary capacity, using an algorithmic labeling procedure. Second, it introduces the transformation procedure that associates a weighted tree with any weighted graph. The procedure allows complete characterization of games on weighted graphs for local cutting rules of arbitrary capacity and provides sufficient conditions for Blocker to win for global cutting rules. The applications of sabotage games to the issue of border security are discussed.

Suggested Citation

  • Kvasov, Dmitriy, 2015. "From Sabotage Games to Border Protection," CEI Working Paper Series 2015-2, Center for Economic Institutions, Institute of Economic Research, Hitotsubashi University.
  • Handle: RePEc:hit:hitcei:2015-2

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. Jackson, Matthew O. & Zenou, Yves, 2015. "Games on Networks," Handbook of Game Theory with Economic Applications,, Elsevier.
    2. Alan Washburn & Kevin Wood, 1995. "Two-Person Zero-Sum Games for Network Interdiction," Operations Research, INFORMS, vol. 43(2), pages 243-251, April.
    3. McBride, Michael & Hewitt, David, 2013. "The enemy you can’t see: An investigation of the disruption of dark networks," Journal of Economic Behavior & Organization, Elsevier, vol. 93(C), pages 32-50.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Simpson Zhang & Mihaela van der Schaar, 2018. "Reputational Dynamics in Financial Networks During a Crisis," Working Papers 18-03, Office of Financial Research, US Department of the Treasury.
    2. Orlova, Olena, 2020. "Personal preferences in networks," Center for Mathematical Economics Working Papers 631, Center for Mathematical Economics, Bielefeld University.
    3. Dalmazzo, Alberto & Pin, Paolo & Scalise, Diego, 2014. "Communities and social inefficiency with heterogeneous groups," Journal of Economic Dynamics and Control, Elsevier, vol. 48(C), pages 410-427.
    4. Kenju Kamei & Louis Putterman, 2018. "Reputation Transmission Without Benefit To The Reporter: A Behavioral Underpinning Of Markets In Experimental Focus," Economic Inquiry, Western Economic Association International, vol. 56(1), pages 158-172, January.
    5. Dequiedt, Vianney & Zenou, Yves, 2017. "Local and consistent centrality measures in parameterized networks," Mathematical Social Sciences, Elsevier, vol. 88(C), pages 28-36.
    6. Bravard, Christophe & Charroin, Liza & Touati, Corinne, 2017. "Optimal design and defense of networks under link attacks," Journal of Mathematical Economics, Elsevier, vol. 68(C), pages 62-79.
    7. Russell Golman & Aditi Jain & Sonica Saraf, 2019. "Hipsters and the Cool: A Game Theoretic Analysis of Social Identity, Trends and Fads," Papers 1910.13385,
    8. Picard, Pierre M. & Zenou, Yves, 2015. "Urban Spatial Structure, Employment and Social Ties: European versus American Cities," IZA Discussion Papers 9166, Institute of Labor Economics (IZA).
    9. Yann Algan & Quoc-Anh Do & Nicolò Dalvit & Alexis Le Chapelain & Yves Zenou, 2015. "How Social Networks Shape Our Beliefs: A Natural Experiment among Future French Politicians," Sciences Po publications info:hdl:2441/78vacv4udu9, Sciences Po.
    10. Laan, Corine M. & van der Mijden, Tom & Barros, Ana Isabel & Boucherie, Richard J. & Monsuur, Herman, 2017. "An interdiction game on a queueing network with multiple intruders," European Journal of Operational Research, Elsevier, vol. 260(3), pages 1069-1080.
    11. Bayer, Péter & Herings, P. Jean-Jacques & Peeters, Ronald, 2019. "Farsighted manipulation and exploitation in networks," Research Memorandum 023, Maastricht University, Graduate School of Business and Economics (GSBE).
    12. Jadbabaie, Ali & Kakhbod, Ali, 2019. "Optimal contracting in networks," Journal of Economic Theory, Elsevier, vol. 183(C), pages 1094-1153.
    13. Bulat Sanditov & Saurabh Arora, 2016. "Social network and private provision of public goods," Journal of Evolutionary Economics, Springer, vol. 26(1), pages 195-218, March.
    14. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2019. "Interdiction Games and Monotonicity, with Application to Knapsack Problems," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 390-410, April.
    15. Michael D. König & Xiaodong Liu & Yves Zenou, 2019. "R&D Networks: Theory, Empirics, and Policy Implications," The Review of Economics and Statistics, MIT Press, vol. 101(3), pages 476-491, July.
    16. Andrea Galeotti & Benjamin Golub & Sanjeev Goyal, 2020. "Targeting Interventions in Networks," Econometrica, Econometric Society, vol. 88(6), pages 2445-2471, November.
    17. Verdier, Thierry & Zenou, Yves, 2017. "The role of social networks in cultural assimilation," Journal of Urban Economics, Elsevier, vol. 97(C), pages 15-39.
    18. Sidartha Gordon & Emeric Henry & Pauli Murto, 2018. "Waiting for my Neighbors," Sciences Po publications 2018-10, Sciences Po.
    19. Dirk Bergemann & Stephen Morris, 2013. "Robust Predictions in Games With Incomplete Information," Econometrica, Econometric Society, vol. 81(4), pages 1251-1308, July.
    20. Yves Zenou, 2013. "Social Interactions and the Labor Market," Revue d'économie politique, Dalloz, vol. 123(3), pages 307-331.

    More about this item


    sabotage games; games on graphs; dynamic graph reliability; network interdiction; border security;
    All these keywords.

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • C73 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Stochastic and Dynamic Games; Evolutionary Games
    • D85 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Network Formation

    NEP fields

    This paper has been announced in the following NEP Reports:


    Access and download statistics


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hit:hitcei:2015-2. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: . General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Reiko Suzuki The email address of this maintainer does not seem to be valid anymore. Please ask Reiko Suzuki to update the entry or send us the correct address (email available below). General contact details of provider: .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.