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. 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.
    4. Sunghoon Hong, 2011. "Strategic Network Interdiction," Working Papers 2011.43, Fondazione Eni Enrico Mattei.
    5. Hong, Sunghoon, 2011. "Strategic Network Interdiction," Climate Change and Sustainable Development 108252, Fondazione Eni Enrico Mattei (FEEM).
    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. 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.
    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. 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.
    8. 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).
    9. repec:spo:wpmain:info:hdl:2441/78vacv4udu92eq3fec89svm9uv is not listed on IDEAS
    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. Jadbabaie, Ali & Kakhbod, Ali, 2019. "Optimal contracting in networks," Journal of Economic Theory, Elsevier, vol. 183(C), pages 1094-1153.
    12. 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.
    13. Yann Bramoullé & Christian Ghiglino, 2022. "Loss Aversion and Conspicuous Consumption in Networks," AMSE Working Papers 2206, Aix-Marseille School of Economics, France.
    14. 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.
    15. Verdier, Thierry & Zenou, Yves, 2017. "The role of social networks in cultural assimilation," Journal of Urban Economics, Elsevier, vol. 97(C), pages 15-39.
    16. Sidartha Gordon & Emeric Henry & Pauli Murto, 2021. "Waiting for my neighbors," RAND Journal of Economics, RAND Corporation, vol. 52(2), pages 251-282, June.
    17. Bayer, Péter & Herings, P. Jean-Jacques & Peeters, Ronald, 2021. "Farsighted manipulation and exploitation in networks," Journal of Economic Theory, Elsevier, vol. 196(C).
    18. Dirk Bergemann & Stephen Morris, 2013. "Robust Predictions in Games With Incomplete Information," Econometrica, Econometric Society, vol. 81(4), pages 1251-1308, July.
    19. Semyon Malamud & Marzena Rostek, 2012. "Decentralized Exchange," Working Papers 12-18, NET Institute.
    20. Zenou, Yves & Patacchini, Eleonora & Liu, Xiaodong, 2013. "Peer Effects: Social Multiplier or Social Norms?," CEPR Discussion Papers 9366, C.E.P.R. Discussion Papers.
    21. Abumoslem Mohammadi & Javad Tayyebi, 2019. "Maximum Capacity Path Interdiction Problem with Fixed Costs," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(04), pages 1-21, August.

    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.