From Sabotage Games to Border Protection

Dmitriy Kvasov

No 2015-2, CEI Working Paper Series from Center for Economic Institutions, Institute of Economic Research, Hitotsubashi University

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.

Keywords: sabotage games; games on graphs; dynamic graph reliability; network interdiction; border security (search for similar items in EconPapers)
JEL-codes: C72 C73 D85 (search for similar items in EconPapers)
Pages: 21 pages
Date: 2015-06
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://hermes-ir.lib.hit-u.ac.jp/hermes/ir/re/28290/wp2015-2.pdf

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hit:hitcei:2015-2

Access Statistics for this paper

More papers in CEI Working Paper Series from Center for Economic Institutions, Institute of Economic Research, Hitotsubashi University Contact information at EDIRC.
Bibliographic data for series maintained by Reiko Suzuki ( this e-mail address is bad, please contact ).