Computing Nash Equilibria in Generalized Interdependent Security Games
We study the computational complexity of computing Nash equilibria in generalized interdependent-security (IDS) games. Like traditional IDS games, originally introduced by economists and risk-assessment experts Heal and Kunreuther about a decade ago, generalized IDS games model agents' voluntary investment decisions when facing potential direct risk and transfer-risk exposure from other agents. A distinct feature of generalized IDS games, however, is that full investment can reduce transfer risk. As a result, depending on the transfer-risk reduction level, generalized IDS games may exhibit strategic complementarity (SC) or strategic substitutability (SS). We consider three variants of generalized IDS games in which players exhibit only SC, only SS, and both SC+SS. We show that determining whether there is a pure-strategy Nash equilibrium (PSNE) in SC+SS-type games is NP-complete, while computing a single PSNE in SC-type games takes worst-case polynomial time. As for the problem of computing all mixedstrategy Nash equilibria (MSNE) efficiently, we produce a partial characterization. Whenever each agent in the game is indiscriminate in terms of the transfer-risk exposure to the other agents, a case that Kearns and Ortiz originally studied in the context of traditional IDS games in their NIPS 2003 paper, we can compute all MSNE that satisfy some ordering constraints in polynomial time in all three game variants. Yet, there is a computational barrier in the general (transfer) case: we show that the computational problem is as hard as the Pure-Nash-Extension problem, also originally introduced by Kearns and Ortiz, and that it is NP-complete for all three variants. Finally, we experimentally examine and discuss the practical impact that the additional protection from transfer risk allowed in generalized IDS games has on MSNE by solving several randomly-generated instances of SC+SS-type games with graph structures taken from several real-world datasets.
The paper introduces a new type of game, generalized interdependent security games, based on Kearns and Ortiz 2004. Several new complexity results are derived and proven for this class of games and some preliminary experimental investigation is given. This is a dense technical paper with many new (but quite specific) contributions for this new class of games. The problem is well-motivated, and the paper reads smoothly in sections 1 and 2. Section 3 (Computational results of alpha-IDS games) is difficult to follow. It feels like there is a lot, possibly too much, that the authors tried to fit into a single paper here and the main contribution/story gets a bit lost amidst the lemmas and proofs. The results are new and should be of interest to (at least) the same audience as that of [8], but the scope of the content does still feel a bit narrow. The experiments section is one long paragraph that lacks structure and polish. There is no conclusion nor much discussion of these results.Questions: Is \Delta_i^sc = \Delta_i^ss? Why two different terms, for clarity of the context? In proof of Theorem one, "its clause" and "its literal": why are these singular? Fig2 shows variables can belong to several clauses. Also, I cannot explain the bounds (1-q)^2 > \Delta_i^sc > (1-q)^3 and 1 > \Delta_i^ss > (1-q); these seems inconsistent with the text and best response definitions, is there an error here?Minor points: - your's -> yours- references, several missed capitalization (nash -> Nash)** Added after response. I appreciate the clarifications made by the authors and pointers to previous research. These games seem to have been more widely-studied than I was first led to believe after my first read of the paper. I encourage the authors to make this more clear if possible. I understand that space is a limiting factor, but the second half of the paper could certainly use some "smoothing", and especially some more discussion on these results could help the impact this work will have, if accepted.