Contested Logistics: A Game-Theoretic Approach
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914921492512768 |
|---|---|
| author | Cerny, Jakub Ling, Chun Kai Chakrabarti, Darshan Zhang, Jingwen Farina, Gabriele Kroer, Christian Iyengar, Garud |
| author_facet | Cerny, Jakub Ling, Chun Kai Chakrabarti, Darshan Zhang, Jingwen Farina, Gabriele Kroer, Christian Iyengar, Garud |
| contents | 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 one-shot game played on a graph representation of the physical world, with the optimal logistics plans described by the (possibly randomized) Nash equilibria 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_13057 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Contested Logistics: A Game-Theoretic Approach Cerny, Jakub Ling, Chun Kai Chakrabarti, Darshan Zhang, Jingwen Farina, Gabriele Kroer, Christian Iyengar, Garud Computer Science and Game Theory 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 one-shot game played on a graph representation of the physical world, with the optimal logistics plans described by the (possibly randomized) Nash equilibria 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 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. |
| title | Contested Logistics: A Game-Theoretic Approach |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2408.13057 |