Counterfactual regret minimization for integrated cyber and air defense resource allocation

Andrew Keith and Darryl Ahner

European Journal of Operational Research, 2021, vol. 292, issue 1, 95-107

Abstract: This research presents a new application of optimal and approximate solution techniques to solve resource allocation problems with imperfect information in the cyber and air-defense domains. We develop a two-player, zero-sum, extensive-form game to model attacker and defender roles in both physical and cyber space. We reformulate the problem to find a Nash equilibrium using an efficient, sequence-form linear program. Solving this linear program produces optimal defender strategies for the multi-domain security game. We address large problem instances with an application of the approximate counterfactual regret minimization algorithm. This approximation reduces computation time by 95% while maintaining an optimality gap of less than 3%. Our application of discounted counterfactual regret results in a further 36% reduction in computation time from the base algorithm. We develop domain insights through a designed experiment to explore the parameter space of the problem and algorithm. We also address robust opponent exploitation by combining existing techniques to extend the counterfactual regret algorithm to include a discounted, constrained variant. A comparison of robust linear programming, data-biased response, and constrained counterfactual regret approaches clarifies trade-offs between exploitation and exploitability for each method. The robust linear programming approach is the most effective, producing an exploitation to exploitability ratio of 10.8 to 1.

Keywords: OR in defence; Regret; Exploitation; Robust; Cybersecurity (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720308912
Full text for ScienceDirect subscribers only

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:eee:ejores:v:292:y:2021:i:1:p:95-107

DOI: 10.1016/j.ejor.2020.10.015

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().