Dynamic Adversarial Resource Allocation: the dDAB Game

1. Problem Formulation

The paper introduces the Dynamic Defender-Attacker Blotto (dDAB) game, a novel extension of the classical static Colonel Blotto game into a dynamic, graph-constrained setting.

• Environment: The game is played on a directed, strongly connected graph $G=(V, E)$ where nodes represent physical locations and edges represent traversability.
• Players: Two players, a Defender (Blue) and an Attacker (Red), compete for control over a subset of nodes called Key Nodes ($V_{key}$).
• Resources: Players possess continuous (or discrete) resources (e.g., robots) with total amounts $X$ and $Y$, respectively.
• Dynamics: The game proceeds in discrete time steps. Unlike static Blotto games where allocation is instantaneous, resources must traverse edges. In each step:
  1. The Defender moves resources based on the current state (transition matrix $K_t$).
  2. The Attacker observes the Defender's new state and moves resources (transition matrix $F_t$).
  3. Winning Condition: The Attacker wins if, at any key node $i$, the attacker's resource count exceeds the defender's ($[y_t]_i > [x_t]_i$). The Defender wins if they can prevent this condition for a specified horizon $T$ (or indefinitely).
• Objective: Determine the Critical Resource Ratio (CRR), $\alpha_T$, which is the minimum ratio $X/Y$ required for the Defender to guarantee a win against any rational Attacker strategy, and to synthesize the corresponding feedback strategies.

2. Methodology

The authors develop a reachability-based analysis combined with set-based dynamic programming to solve the game.

A. Reachable Sets and Polytopes

Instead of analyzing action spaces directly, the authors analyze the Reachable Sets ($R(x_t)$), which represent all possible states a player can reach in one step from a current state $x_t$.

• Polytope Structure: The reachable set is proven to be a polytope (a convex hull of vertices).
• Extreme Actions: The set of admissible actions is characterized by extreme actions (vertices of the action polytope), where resources move entirely to one neighbor or stay put. Any admissible action is a convex combination of these extreme actions.

B. Required Sets ($P_{req}$)

To guarantee defense at time $t+1$, the Defender must allocate resources such that they outnumber the Attacker's maximum possible allocation at every key node.

• The Required Set $P_{req}(y_t)$ is defined as the set of all Defender states $x_{t+1}$ that satisfy $[x_{t+1}]_i \geq \max_{y' \in R(y_t)} [y']_i$ for all key nodes.
• If the Defender cannot reach $P_{req}(y_t)$ from their current state, they lose.

C. Q-Sets (k-step Safe Sets)

To handle multi-step horizons, the authors define Q-sets ($Q^{(i)}_k$), representing the set of Defender states from which they can guarantee defense for $k$ steps against an Attacker currently concentrated at node $i$.

• Recursive Definition:
  $$Q^{(i)}_k = \{ x \mid x \in P_{req}(y^{(i)}) \land \forall j \in N_i, R(x) \cap Q^{(j)}_{k-1} \neq \emptyset \}$$
  This means a state is safe for $k$ steps if it is safe for the current step AND the Defender can reach a safe state for $k-1$ steps regardless of which neighbor the Attacker moves to next.
• Indefinite Defense: The intersection of all $Q^{(i)}_k$ as $k \to \infty$ yields the Indefinite Safe Sets ($Q^{(i)}_\infty$). If these are non-empty, indefinite defense is possible.

D. Handling Splitting Strategies

A major theoretical challenge is whether the Attacker gains an advantage by splitting resources into multiple sub-teams.

• Subteam Superposition: The authors model the Attacker's splitting as a superposition of "sub-teams."
• Key Theorem: They prove that if the Defender has enough resources to defend against a No-Splitting (concentrated) Attacker, they can also defend against any splitting strategy.
• Implication: The Attacker has no incentive to split. The CRR derived for the no-splitting case is sufficient for the general case.

E. Algorithmic Solution

• Q-Prop Algorithm: An iterative algorithm computes the Q-sets by propagating constraints backward from the horizon. It uses Inverse Reachable Sets (computed via a reversed graph) to efficiently determine the intersection of reachable sets and required sets.
• Action Extraction: Once a target state in the Q-set is identified, the algorithm solves a linear program to find the specific transition matrix (action) to reach that state.

3. Key Contributions

1. Formulation of dDAB: First formulation of the Blotto game with dynamic, graph-constrained resource movement and turn-based feedback.
2. Necessary and Sufficient Conditions: Derivation of the Critical Resource Ratio (CRR) and the Q-sets, providing exact conditions for guaranteed defense.
3. No-Splitting Equivalence: Proof that splitting resources does not provide the Attacker with an advantage, simplifying the strategy synthesis significantly.
4. Feedback Strategies: Synthesis of optimal feedback strategies for both players that react to the current state rather than pre-computed open-loop plans.
5. Non-Integer CRR: Demonstration that the CRR can be non-integer (e.g., 3.5) in finite-horizon games, challenging the intuition that resource ratios must be integers.

4. Results

• Numerical Simulations:
  • Demonstrated on various graph topologies (rings, general directed graphs).
  • Showed that adding edges does not always increase the CRR; in some cases, it decreases it (e.g., adding a self-loop or specific bidirectional edges can improve Defender efficiency).
  • Verified that the Q-sets converge to a fixed point for strongly connected graphs, enabling indefinite defense.
• Hardware Experiments (Robotarium):
  • Implemented the algorithm on a physical multi-robot testbed (Georgia Tech Robotarium).
  • Scenario 1: 8 Defender robots vs. 2 Attacker robots on a 7-node graph. The Defender successfully maintained numerical superiority at key nodes.
  • Scenario 2: 4 Defender robots vs. 1 Attacker in an indoor surveillance setting (9 rooms). The system maintained continuous surveillance despite the Attacker's random movements.
  • The experiments validated the algorithm's ability to handle discrete, embodied resources by wrapping the continuous solution with a discrete allocation strategy.

5. Significance

• Theoretical Impact: Bridges the gap between static game theory (Blotto) and dynamic control (population dynamics on graphs). It provides a rigorous framework for safety-critical resource allocation under adversarial uncertainty.
• Practical Application: Offers a provable method for deploying robotic systems in contested environments (e.g., perimeter defense, wildfire surveillance, power grid protection) where resources must move physically and demands change dynamically.
• Computational Efficiency: The use of polytope geometry and set-based dynamic programming avoids the "curse of dimensionality" often associated with game trees, making the approach scalable for moderate-sized graphs.
• Robustness: The derived strategies provide worst-case guarantees, ensuring defense even against an optimal, rational adversary.

In summary, this paper establishes a complete theoretical and algorithmic framework for dynamic adversarial resource allocation, proving that centralized feedback strategies based on reachable set analysis can guarantee defense with minimal resource overhead, even in the presence of intelligent, adaptive attackers.