Algorithms for Network Interdiction and Fortification Games

J. Cole Smith () and Churlzu Lim ()
Additional contact information
J. Cole Smith: University of Florida
Churlzu Lim: University of North Carolina at Charlotte

A chapter in Pareto Optimality, Game Theory And Equilibria, 2008, pp 609-644 from Springer

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.

Keywords: network interdiction; network fortification; bilinear programming; Stackelberg games; mixed-integer programming; duality (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations: View citations in EconPapers (19)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-0-387-77247-9_24

Ordering information: This item can be ordered from
http://www.springer.com/9780387772479

DOI: 10.1007/978-0-387-77247-9_24

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().