テクニカルレポート From Sabotage Games to Border Protection

Kvasov, Dmitriy

2015-06 , Institute of Economic Research, Hitotsubashi University
内容記述
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.
本文を読む

http://hermes-ir.lib.hit-u.ac.jp/rs/bitstream/10086/27568/1/wp2015-2.pdf

このアイテムのアクセス数:  回

その他の情報