Nonzero-Sum Nonlinear Network Path Interdiction

Abstract: A novel nonzero-sum game is presented for a variant of a classical network interdiction problem. In this model an interdictor (e.g. an enforcement agent) decides how much of an inspection resource to spend along each arc in the network in order to capture the evader (e.g. a smuggler). The evader selects a probability distribution on paths from one or more source nodes to potentially several destinations. The probability of evading each of the arcs nonlinearly decreases in the amount of resource that is spent on its inspection. We show that under reasonable assumptions with respect to the evasion probability functions, (approximate) Nash equilibria of this game can be determined in polynomial time; depending on whether the evasion functions are exponential or general, exact Nash equilibria or approximate Nash equilibria, respectively, are computed.