Back to search

Clemson University

Selected Interdiction Games with Uncertain, Risk-Averse, and Simultaneous Play Considerations

Abstract

dc:description.abstract

This dissertation examines two network interdiction problems: a shortest-path interdiction problem under uncertainty and a network interdiction problem in a simultaneous game. Both problems happen in two stages over a directed network, and involve a leader and a follower who have opposing interests. In the first problem, the leader acts first to lengthen a subset of arcs, and a follower acts second to select a shortest path across the network. The cost for a follower’s arc consists of a base cost if the arc is not interdicted, plus an additional cost that is incurred if the arc is interdicted. The leader is not aware of the base costs when the interdiction action is taken, but does know that the base cost values are uniformly distributed within given (arc-specific) intervals. The follower, on the other hand, observes the exact value of the base costs, plus the additional costs due to interdiction actions. We consider two variants of this problem. In the first variant, the leader is risk-neutral, whose goal is to maximize the expected minimum cost attainable by the follower. We provide a partitioning algorithm for computing an exact optimal solution to this problem, leveraging bounds gleaned from Jensen’s inequality as proposed in an earlier study on a maximum-flow interdiction problem. Several algorithmic strategies for accelerating the convergence of the algorithm are also introduced. In the second variant, the leader is risk-averse, seeking to maximize the conditional value-at-risk of the follower's shortest-path costs, given some specified risk parameter. We provide an exact method for this problem that utilizes row generation, partitioning, and bounding strategies. We demonstrate the efficacy of our approaches on randomly-generated instances. In the second problem, the follower aims to access the sink node without being detected by the leader. Both players are aware of the probability of detection of each arc in the network. In the first stage, the leader interdicts and removes a subset of arcs from the network given a budget constraint. This information becomes available to the follower before the start of the second stage when both players participate in a simultaneous game. The simultaneous game involves the leader monitoring a subset of arcs to increase the probability of detecting the follower, and the follower traversing on a source-sink path. We present a tri-level formulation for the interdiction in a simultaneous game, as well as a bi-level reformulation that enables constraint and column generation and Benders decomposition to solve this problem exactly. We also provide strategies to improve the efficiency of the proposed solution approach along with computational results over a set of randomly-generated instances.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Industrial Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Nguyen, Di H.
Contributors dc:contributor
  • Yongjia Song
  • J. Cole Smith
  • Mary Elizabeth Kurz
  • Brian C. Dean

Subjects

dc:subject × 12

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/2974

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Nguyen, Di H.. Selected Interdiction Games with Uncertain, Risk-Averse, and Simultaneous Play Considerations. Dissertation thesis, https://open.clemson.edu/all_dissertations/2974