### Abstract

This chapter explores models and algorithms applied to a class of Stackelberg games on networks. In these network interdictiongames, a network exists over which an operator wishes to execute some function, such as finding a shortest path, shipping a maximum flow, or transmitting a minimum cost multicommodity flow. The role of the interdictor is to compromise certain network elements before the operator acts, by (for instance) increasing the cost of flow or reducing capacity on an arc. We begin by reviewing the field of network interdiction and its related theoretical and mathematical foundations. We then discuss recent applications of stochastic models, valid inequalities, continuous bilinear programming techniques, and asymmetric analysis to network interdiction problems. Next, note that interdiction problems can be extended to a three-stage problem in which the operator fortifies the network (by increasing capacities, reducing flow costs, or defending network elements from the interdictor) before the interdictor takes action. We devote one section to ongoing research in this area and conclude by discussing areas for future research.

Original language | English (US) |
---|---|

Title of host publication | Springer Optimization and Its Applications |

Publisher | Springer International Publishing |

Pages | 609-644 |

Number of pages | 36 |

DOIs | |

State | Published - Jan 1 2008 |

Externally published | Yes |

### Publication series

Name | Springer Optimization and Its Applications |
---|---|

Volume | 17 |

ISSN (Print) | 1931-6828 |

ISSN (Electronic) | 1931-6836 |

### Keywords

- Bilinear programming
- Duality
- Mixed-integer programming
- Network fortification
- Network interdiction
- Stackelberg games

### ASJC Scopus subject areas

- Control and Optimization

## Fingerprint Dive into the research topics of 'Algorithms for network interdiction and fortification games'. Together they form a unique fingerprint.

## Cite this

*Springer Optimization and Its Applications*(pp. 609-644). (Springer Optimization and Its Applications; Vol. 17). Springer International Publishing. https://doi.org/10.1007/978-0-387-77247-9_24