Nonzero-Sum Nonlinear Network Path Interdiction

Speaker
Noam Goldberg
Date
05/05/2015 - 12:30 - 11:00Add To Calendar 2015-05-05 11:00:00 2015-05-05 12:30:00 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. Economics and Business Administration building (No. 504), room 011 אוניברסיטת בר-אילן - Department of Economics Economics.Dept@mail.biu.ac.il Asia/Jerusalem public
Place
Economics and Business Administration building (No. 504), room 011
Affiliation
Bar-Ilan University
Abstract

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.

Last Updated Date : 12/04/2015