Sequential Interdiction with Incomplete Information and Learning

Juan S. Borrero (), Oleg A. Prokopyev () and Denis Sauré ()
Additional contact information
Juan S. Borrero: School of Industrial Engineering & Management, Oklahoma State University, Stillwater, Oklahoma 74078
Oleg A. Prokopyev: Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261
Denis Sauré: Department of Industrial Engineering, University of Chile, Santiago 8370456, Chile

Operations Research, 2019, vol. 67, issue 1, 72-89

Abstract: We present a framework for a class of sequential decision-making problems in the context of general interdiction problems, in which a leader and a follower repeatedly interact. At each period, the leader allocates resources to disrupt the performance of the follower (e.g., as in defender–attacker or network interdiction problems), who, in turn, minimizes some cost function over a set of activities that depends on the leader’s decision. Although the follower has complete knowledge of the follower’s problem, the leader has only partial information and needs to learn about the cost parameters, available resources, and the follower’s activities from the feedback generated by the follower’s actions. We measure policy performance in terms of its time-stability, defined as the number of periods it takes for the leader to match the actions of an oracle with complete information. In particular, we propose a class of greedy and robust policies and show that these policies are weakly optimal, eventually match the oracle’s actions, and provide a real-time certificate of optimality. We also study a lower bound on any policy performance based on the notion of a semioracle. Our numerical experiments demonstrate that the proposed policies consistently outperform a reasonable benchmark and perform fairly close to the semioracle.

Keywords: bilevel programming; attacker-defender; interdiction; learning; incomplete information; online optimization; robust optimization (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
https://doi.org/10.1287/opre.2018.1773 (application/pdf)

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:inm:oropre:v:67:y:2019:i:1:p:72-89

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().