Networked systems for transport, communication, and social interaction have contributed to all aspects of life by increasing economic and social efficiency. However, increased connectivity also gives intruders and attackers better opportunities to maliciously spread in the network, whether the spread is of disinformation, or of contamination in the water supply [26]. Anyone participating in a networked system may therefore desire to undertake appropriate security measures in order to protect themselves from such malicious influences.

We introduce a Network Cutting Game, which is a game-theoretic framework where a group of self-interested players protect vertices that they own by cutting them off from parts of the network that they find untrustworthy. Cutting an edge should not be interpreted as destroying a part of the network: instead it can correspond to taking security measures on that edge such as placing sentries on lines of communication. These notions are applicable in areas such as airline security. Consider a situation where country A requires extra security screening of passengers or cargo from country B. Due to the networked multi-hop structure of international air travel, the optimal locations for carrying out such screenings may lie somewhere in between the two countries. In general, the goal of each player is to make sure that nothing can get to it from an “untrustworthy” part of the network without passing through an edge with installed security measures.