Contested Logistics: A Game Theoretic Approach

Abstract

We introduce Contested Logistics Games, a variant of logistics problems that account for the presence of an adversary that can disrupt the movement of goods in selected areas. We model this as a large two-player zero-sum game played on a graph representation of the physical world, with the optimal logistics plan described by the (randomized) Nash equilibrium of this game. Our logistics model is fairly sophisticated, and is able to handle multiple modes of transport and goods, accounting for possible storage of goods in warehouses, as well as Leontief utilities based on demand satisfied. We prove computational hardness results related to equilibrium finding and propose a practical double-oracle solver based on solving a series of best-response mixed-integer linear programs. We experiment on both synthetic and extit{real-world maps}, demonstrating that our proposed method scales to reasonably large games. We also demonstrate the importance of explicitly modeling the capabilities of the adversary via ablation studies and comparisons with a naive logistics plan based on heuristics.

Publication
Contested Logistics: A Game Theoretic Approach