CAP-DO: Learned Contextual Action Proposals for Certified Double-Oracle Solving Across Related Zero-Sum Games
2026-07-27 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study ways to solve repeated zero-sum security games where the game changes slightly each time but the actions stay the same. They improve on a method called Double Oracle (DO) by creating CAP-DO, which uses learned rankings to start each new game with smarter action choices. This approach keeps DO’s guarantees for finding good solutions and converges as before, but uses fewer costly calculations. Tests show CAP-DO finds solutions more reliably and efficiently than other methods on large and complex security game examples.
Zero-sum gamesDouble Oracle algorithmSecurity gamesBest responseGame theoryWarm startAction rankingContextual gamesAlgorithm convergenceInspection planning
Authors
Mu Wang, Zhenkun Liu, Liang Liang, Guofu Zhang
Abstract
Many security and inspection-planning problems require solving a sequence of related zero-sum games. Across this sequence, the feasible defender and attacker action spaces re-main fixed, whereas each context induces a different payoff matrix through changes in target values, inspection effective-ness, costs, and interaction effects. Double Oracle (DO) solves large zero-sum games without materializing the full payoff matrix by iteratively expanding a restricted game. However, applying standard DO independently to each new payoff context requires restarting the search from a generic restricted game and requires rediscovering context-relevant actions through full-space best responses. We propose Con-textual Action Proposal Double Oracle (CAP-DO), a learning-augmented framework that warm-starts DO for repeated contextual games. Offline, CAP-DO trains separate defender and attacker rankers once from solved contexts. Online, the fixed rankers propose initial restricted action sets for each new context. Learning therefore determines where certified search starts, while the current game, through full-space best-response checks and a two-sided certificate, still determines whether the output is accepted. Theoretically, CAP-DO pre-serves DO's full-game certification guarantee, so every accepted output meets the prescribed certificate tolerance. Under standard exact-oracle assumptions, CAP-DO also retains finite convergence when expansion is uncapped. Empirically, across three scales of a non-additive contextual inspection-game benchmark, with up to 9,880 actions per player, CAP-DO-balanced achieves higher certification rates and uses few-er full-space best-response calls than cold-start, trace-reuse, and heuristic warm starts under fixed expansion budgets.