Computing nash equilibrium in interdependent defense games

摘要: Roughly speaking, Interdependent Defense (IDD) games, previously proposed, model the situation where an attacker wants to cause as much damage possible a network by attacking one of sites in network. Each site must make investment decision regarding security protect itself against direct or indirect attack, latter due potential transfer-risk from unprotected neighboring site. The work introducing IDD games discusses applications essence real-world scenarios such 2006 transatlantic aircraft plot. In this paper, our focus is study problem computing Nash Equilibrium (NE) games. We show that efficient algorithm determine whether some attacker's strategy can be part NE instance unlikely exist. Yet, we provide dynamic programming compute approximate when graph/network structure game directed tree with single source, and it FPTAS. also introduce improved heuristic on arbitrary graph structures. Our experiments more efficient, provides better approximations, than best-response-gradient dynamics for case Internet class introduced studied original