IDEAS home Printed from https://ideas.repec.org/p/hit/hitcei/2015-2.html
   My bibliography  Save this paper

From Sabotage Games to Border Protection

Author

Listed:
  • Kvasov, Dmitriy

Abstract

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
    as

    Download full text from publisher

    File URL: https://hermes-ir.lib.hit-u.ac.jp/hermes/ir/re/28290/wp2015-2.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Alan Washburn & Kevin Wood, 1995. "Two-Person Zero-Sum Games for Network Interdiction," Operations Research, INFORMS, vol. 43(2), pages 243-251, April.
    2. 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.
    3. Sunghoon Hong, 2011. "Strategic Network Interdiction," Working Papers 2011.43, Fondazione Eni Enrico Mattei.
    4. Hong, Sunghoon, 2011. "Strategic Network Interdiction," Climate Change and Sustainable Development 108252, Fondazione Eni Enrico Mattei (FEEM).
    5. Jackson, Matthew O. & Zenou, Yves, 2015. "Games on Networks," Handbook of Game Theory with Economic Applications,, Elsevier.
    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. 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.
    2. William M. Kroshl & Shahram Sarkani & Thomas A Mazzuchi, 2015. "Efficient Allocation of Resources for Defense of Spatially Distributed Networks Using Agent‐Based Simulation," Risk Analysis, John Wiley & Sons, vol. 35(9), pages 1690-1705, September.
    3. 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.
    4. Orlova, Olena, 2020. "Personal preferences in networks," Center for Mathematical Economics Working Papers 631, Center for Mathematical Economics, Bielefeld University.
    5. Daniel Woods & Mustafa Abdallah & Saurabh Bagchi & Shreyas Sundaram & Timothy Cason, 2022. "Network defense and behavioral biases: an experimental study," Experimental Economics, Springer;Economic Science Association, vol. 25(1), pages 254-286, February.
    6. 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.
    7. Yann Bramoullé & Habiba Djebbari & Bernard Fortin, 2020. "Peer Effects in Networks: A Survey," Annual Review of Economics, Annual Reviews, vol. 12(1), pages 603-629, August.
    8. 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.
    9. Dequiedt, Vianney & Zenou, Yves, 2017. "Local and consistent centrality measures in parameterized networks," Mathematical Social Sciences, Elsevier, vol. 88(C), pages 28-36.
    10. Daron Acemoglu & Asuman Ozdaglar & Alireza Tahbaz-Salehi, 2015. "Networks, Shocks, and Systemic Risk," NBER Working Papers 20931, National Bureau of Economic Research, Inc.
    11. 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.
    12. 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," Working Papers hal-03459820, HAL.
    13. Russell Golman & Aditi Jain & Sonica Saraf, 2019. "Hipsters and the Cool: A Game Theoretic Analysis of Social Identity, Trends and Fads," Papers 1910.13385, arXiv.org.
    14. Chen, Ying-Ju & Zenou, Yves & Zhou, Junjie, 2022. "The impact of network topology and market structure on pricing," Journal of Economic Theory, Elsevier, vol. 204(C).
    15. 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).
    16. repec:spo:wpmain:info:hdl:2441/78vacv4udu92eq3fec89svm9uv is not listed on IDEAS
    17. 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.
    18. Bayer, Péter & Herings, P. Jean-Jacques & Peeters, Ronald, 2021. "Farsighted manipulation and exploitation in networks," Journal of Economic Theory, Elsevier, vol. 196(C).
    19. Jadbabaie, Ali & Kakhbod, Ali, 2019. "Optimal contracting in networks," Journal of Economic Theory, Elsevier, vol. 183(C), pages 1094-1153.
    20. 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.
    21. John Higgins & Tarun Sabarwal, 2023. "Control and spread of contagion in networks with global effects," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 25(6), pages 1149-1187, December.

    More about this item

    Keywords

    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:

    Statistics

    Access and download statistics

    Corrections

    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.

    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 (email available below). General contact details of provider: https://edirc.repec.org/data/cehitjp.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.