Double Oracle Algorithm for
Game-Theoretic Robot Allocation on Graphs

The environment where two players allocate robots can be abstracted into a graph as shown in Fig. 1. An ordered pair $G=(\mathcal{V},\mathcal{E})$ can be used to define an undirected graph, comprising set of nodes $\mathcal{V}$ and set of edges $\mathcal{E}\mathrel{\mathop{\mathchar 58\relax}}=\{\{x,y\}\ |\ x,y\in\mathcal{V}\}$. Particularly, a complete graph is a simple undirected graph in which every pair of distinct nodes is connected by a unique edge [38]. Replacing nodes $\{x,y\}$ in $\mathcal{E}$ by ordered sequence of two elements $(x,y)$ in $\mathcal{V}$ leads to directed graph, or digraph with $\mathcal{E}\mathrel{\mathop{\mathchar 58\relax}}=\{(x,y)\ |\ (x,y)\in\mathcal{V}^{2}\}$ a set of edges. For an edge $\varepsilon=(x,y)$ directed from node $x$ to $y$, $x$ and $y$ are called the endpoints of the edge with $x$ the tail of $\varepsilon$ and $y$ the head of $\varepsilon$. A directed graph $G$ is called unilaterally connected or unilateral if $G$ contains a directed path from $x$ to $y$ or a directed path from $y$ to $x$ for every pair of nodes $\{x,y\}$ [39].

Previous studies on Colonel Blotto games do not incorporate graphs [27, 28, 37]. If the same logic is applied, they can be seen as the games conducted on a complete graph since there is no limitation on the robot transitions between any two nodes. In this paper, we focus on the Colonel Blotto games on unilateral graphs where the robots must be transitioned on the edges. Graph nodes are the strategic points where two players can allocate robots. We denote the number of nodes as $N$. We model the robot allocation by its two characteristics—type denoted as $R$, and number denoted as $A$. If there are $M$ robot types i.e., $R_{1},R_{2},\cdots,R_{M}$, the number of robots for each type can be denoted by $A_{1},A_{2},\cdots,A_{M}$, respectively. In the paper, $M=1$ denotes homogeneous robot allocation and $M>1$ denotes heterogeneous robot allocation. To start the game of robot allocation, there must be an initial robot distribution for both players. Denote $\mathbf{d}_{0}^{x}(R_{i})$ and $\mathbf{d}_{0}^{y}(R_{i})$ as the initial distribution of $i$-th type robots from Player 1 and Player 2, respectively. Notably, $\mathbf{d}_{0}^{x}(R_{i})$ (or $\mathbf{d}_{0}^{y}(R_{i})$) is a vector of $N$ entries, each of which stands for the $i$-th type robots allocated on a particular node. Fig. 2(a) demonstrates an example of homogeneous robot allocation. The initial robot distribution of Player 1 (red) is $[1,0,2,2,0]$. Then she translates one robot from node 3 to node 2 and another from node 4 to node 1. The robot distribution becomes $[2,0,2,1,0]$. Since $(1,4),(1,5)\in\mathcal{E}$, this allocation is valid. Meanwhile, the robot allocation of Player 2 (blue) after one step is $[1,1,0,2,1]$. If the rule stipulates that the player who owns more robots on a node wins that node, then the outcome is that Player 2 wins. That is because she wins nodes $2,4,5$ while Player 1 only wins nodes $1,3$.

A Colonel Blotto Game is a two-player constant-sum game in which the players are tasked to simultaneously allocate limited resources over several strategic nodes [22]. Each player selects strategies from a nonempty strategy set $\mathcal{X}=\mathcal{X}(G),~{}\mathcal{Y}=\mathcal{Y}(G)$, where $\mathcal{X},~{}\mathcal{Y}\subseteq\{\mathbf{S}_{M\times N}\ |\ 0\leq\mathbf{S}_{ij}\leq A_{i},\sum_{j}\mathbf{S}_{ij}=A_{i},i\in\{1,2,\cdots,M\},j\in\{1,2,...,N\}\}$. $\mathbf{S}_{ij}$ stands for amount of $i$-th resource allocated on $j$-th node. Each player picks their strategies combination $\hat{\mathcal{X}}\subseteq\mathcal{X},\hat{\mathcal{Y}}\subseteq\mathcal{Y}$ over probability distribution $\mathbf{P}_{x}$ and $\mathbf{P}_{y}$, respectively. The probability of strategy $\mathbf{S}_{x}$ adopted by Player 1 is denoted as $P_{x}(\mathbf{S}_{x})$. Analogously for Player 2, it is donated as $P_{y}(\mathbf{S}_{y})$. This strategy’s combination over the probability distribution is called mixed strategy, denoted by $\mathbf{\Delta}_{X}$ and $\mathbf{\Delta}_{Y}$. The number of strategies in a mixed strategy set is denoted by $K$. For example, if Player 1 decides to apply the mixed strategy of $K_{x}$ strategies from $\mathcal{X}$, then $\mathbf{\Delta}_{X}=\mathbf{P}_{x}\times\mathbf{S}_{x}\in\mathbb{R}^{M\times(N\times K_{x})}$. If $K=1$, the strategy is called pure strategy. Fig. 2(b) illustrates an example of heterogeneous robot allocation that expands from the case of homogeneous robot allocation (Fig. 2(a)). There are three types of robots, i.e., $M=3$ and each type has five robots, i.e., $A_{1}=A_{2}=A_{3}=5$. There are five nodes in the graph, i.e., $N=5$. For Player 1,

and for Player 2,

If the probability of taking the first strategy and the second strategy is respectively 0.4 and 0.6, i.e., $P_{x}(\mathbf{S}_{x}^{1})=0.4,P_{x}(\mathbf{S}_{x}^{2})=0.6$, then mixed strategy for Player 1 is

While Player 2 takes pure strategy with $P_{y}(\mathbf{S}_{y}^{1})=1$, thus $\mathbf{\Delta}_{Y}=\mathbf{S}_{y}^{1}$. Notably, the mixed strategy comprises elements from compact strategy sets $\mathcal{X}$ and $\mathcal{Y}$. For each strategy element $\mathbf{S}_{x}$ and $\mathbf{S}_{y}$, the utility function is a continuous function measuring the outcome of the game $u=u(\mathbf{S}_{x},\mathbf{S}_{y})\mathrel{\mathop{\mathchar 58\relax}}\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ for Player 1, while for Player 2 utility function is $-u$ if the game is zero-sum. In classic Colonel Blotto game (i.e., homogeneous robot allocation), the utility function can be modeled as a sign function since the player allocating more robots to a node wins that node. The utility is the total number of strategic points the player wins, as shown in Equation 1.

Here $\mathbf{S}_{x}$ and $\mathbf{S}_{y}$ are both $N$-dimension vectors since the classic Colonel Blotto game is a homogeneous game where $M=1$ (mentioned in section II-A), and $\mathbf{S}_{x,i},\mathbf{S}_{y,i}$ refer to $i$-th entry of $\mathbf{S}_{x}$ and $\mathbf{S}_{y}$. However, in games with heterogeneous resources, the utility functions can be more complicated.

The triple $\mathbb{C}=(\mathcal{X}(G),\mathcal{Y}(G),u)$ is called a continuous game. In a continuous game, given two players’ mixed strategies $\mathbf{\Delta}_{X}$ and $\mathbf{\Delta}_{Y}$, expected utility of Player 1 is defined as

According to [40], every continuous game has at least one equilibrium.

We consider a two-player game-theoretic robot allocation on a connected directed graph $G=(\mathcal{V},\mathcal{E})$ with $|\mathcal{V}|=N$. Suppose each player has $M$ types of robots $R_{1},R_{2},\cdots,R_{M}$ with corresponding quantity $A_{1},A_{2},\cdots,A_{N}$. The initial robot distributions of the two players are $\mathbf{d}_{x}^{0}$ and $\mathbf{d}_{y}^{0}$, respectively. We first introduce two basic assumptions.

With these two assumptions, we aim to compute the equilibrium (i.e., optimal mixed strategies for the two players) for three versions of the game-theoretic robot allocation on graphs.

The double oracle algorithm was first presented in [34]. Later, it was widely utilized to compute the equilibrium (or mixed strategies) for continuous games. [30, 41]. To better understand the algorithm, we first introduce the notion of best response strategy. The best response strategy of Player 1, given the mixed strategy $\mathbf{\Delta}_{Y}$ of Player 2, is defined as

It is Player 1’s best pure strategy against her opponent (i.e., Player 2). Similarly, Player 2’s best response strategy is

The double oracle algorithm begins from an initial strategy set $\mathcal{X}_{0}$ and $\mathcal{Y}_{0}$ for the two players, which are picked randomly from strategy space $\mathcal{X}$ and $\mathcal{Y}$. $\mathbb{C}_{0}=(\mathcal{X}_{0},\mathcal{Y}_{0},u)$ is a subgame of $\mathbb{C}=(\mathcal{X},\mathcal{Y},u)$, and the equilibrium of this subgame can be calculated by linear programming, as in Algorithm 1, line 2. From the equilibrium of the subgame, notated as $\mathbf{\Delta}_{X}^{i*}$ and $\mathbf{\Delta}_{Y}^{i*}$ in $i$-th iteration, best response strategies for both players are computed as in Algorithm 1, line 4. If these strategies are not in the subgame strategy set, then add them into the set to form a bigger subgame, and calculate whether equilibrium is reached. According to [37], the equilibrium condition (Lemma 1) is equivalent to the following lemma.

$\max{U(\mathbf{\Delta}_{X}^{*},\mathbf{S}_{y})}$ is called upper utility of the game, denoted by $U_{u}$, and $\min{U(\mathbf{S}_{x},\mathbf{\Delta}_{Y}^{*})}$ is called lower utility of the game, denoted by $U_{l}$. Note that, in practice, (4) is typically replaced by $\epsilon$-equilibrium equation for the simplicity of computation.

Therefore, the termination condition is $U_{u}-U_{l}>\epsilon$. In addition, since the output is the mixed strategy and too many redundant strategies with a low probability would slow down the algorithm, we delete strategies with a low probability, as shown in Algorithm 1, line 3.

The optimization problem in Algorithm 1, line 2 is a linear programming (LP) problem. Define the utility matrix over $\mathbf{S}_{x}$ and $\mathbf{S}_{y}$ by $\mathbf{U}$, with each entry $\mathbf{U}_{ij}$ being the utility of Player 1’s $i$-th strategy verses Player 2’s $j$-th strategy, i.e.,

Therefore, the expected utility can be calculated by

Suppose $\mathbf{U}$ is a $K_{x}\times K_{y}$ matrix (that is, Player 1’s mixed strategy set containing $K_{x}$ strategies and Player 2’s mixed strategy set containing $K_{y}$ strategies), the probability distribution of Player 1’s strategies $\mathbf{P}_{x}$ can be calculated by

For Player 2, the probability distribution $\mathbf{P}_{y}$ can be calculated by

These can be solved by linprog in Python.

The most crucial part of the double oracle algorithm is to compute the best response strategy (Algorithm 1, line 4). The graph constraints and various robot types we consider make the computation challenging. First, the strategy set $\mathcal{X}$ and $\mathcal{Y}$ in (2) and (3) depends on the graph $G$. Given that $G$ is unilaterally connected, not all nodes can be reached within one step. Therefore with an initial robot distribution, reachable strategy sets $\mathcal{X}$ and $\mathcal{Y}$ need to be computed first. This problem was introduced in paper [29], which we briefly summarize in Section III-B. Second, an appropriate utility is essential for computing the best response strategy. However, for CDH robots, no such function exists. To this end, we construct a continuous utility function to handle CDH robots (Section IV-C).

We leverage the notion of reachable set for computing strategy sets $\mathcal{X}(G)$ and $\mathcal{Y}(G)$ on graph $G$. We define the adjacency matrix $\mathbf{A}$ of a graph $G$ as:

The adjacency matrix describes the connectivity of nodes on a graph. We denote the $i$-th type robots $R_{i}$ distributed on a graph at time $t$ by a $N$-dimension vector $\mathbf{d}_{t}(R_{i})$ with $N$ the number of nodes and each element the number of this type robots on each node. Then we denote the Transition matrix $\mathbf{T}$ as

Note that the transition matrix $\mathbf{T}$ has two characteristics.

• •

  $\sum_{j}\mathbf{T}_{ij}=1.$

• •

  $\mathbf{T}_{ij}\geq 0,\ \mathbf{T}_{ij}=0\quad\text{if}\ \mathbf{A}_{ij}=0.$

All valid transition matrices form admissible action space $\widetilde{\mathcal{T}}$, i.e.,

To to determine closed-form expression of $\widetilde{\mathcal{T}}$, define extreme action space $\hat{\mathcal{T}}$ corresponding to the binomial allocation as

Extreme action space $\hat{\mathcal{T}}$ is a finite set and its element forms the base of $\widetilde{\mathcal{T}}$. Therefore, admissible action space can be calculated as a linear combination of all elements in extreme action space.

Then, given an initial distribution of the $i$-th robot type, $\mathbf{d}_{0}(R_{i})$, the reachable set for $i$-th robot type can be calculated as

Finally, the strategy set $\mathcal{X}$ for all types of robots can be expressed as a collection of their individual reachable sets.

The reachable set $\mathcal{Y}$ can be calculated analogously.

In Problem 1, two players allocate homogeneous robots (i.e., $M=1$) on graph $G$. We denote initial robot distribution as $\mathbf{d}_{0}(x)$ and $\mathbf{d}_{0}(y)$, or shorthand $\mathbf{d}_{x}$ and $\mathbf{d}_{y}$. We first calculate the reachable set of initial strategy sets $\mathcal{X}(\mathbf{d}_{x})$ and $\mathcal{Y}(\mathbf{d}_{y})$ by (6) and (7).

Then we utilize the Double Oracle algorithm (Algorithm 1) to compute the optimal mixed strategies for the two players with the utility function introduced in (1). Particularly, assume in $j$-th step $\mathbf{\Delta}_{y}^{j*}=[P_{y}(\mathbf{S}_{y}^{1})\cdot\mathbf{S}_{y}^{1},\ P_{y}(\mathbf{S}_{y}^{2})\cdot\mathbf{S}_{y}^{2},\ \cdots,\ P_{y}(\mathbf{S}_{y}^{K})\cdot\mathbf{S}_{y}^{K}]$ is known, the best response strategy for Player 1 is determined by

The approach to solve this problem will be discussed in Section IV-D.

In Problem 2, two players allocate linear heterogeneous robots (i.e., $M>1$) on graph $G$. Then the strategy space $\mathbf{S}\in\mathbb{R}^{M\times N}$ becomes a $M\times N$-dimension matrix. Denote the initial robot distribution as $\mathbf{d}_{x}$ and $\mathbf{d}_{y}$, which are also $M\times N$-dimension matrices. Different robot types can be linearly transformed, i.e., $R_{i}=I_{ij}R_{j}$ by an intrinsic matrix $\mathbf{I}$, i.e.,

The second equality ensures that the transformation between any two types of robots is reversible and multiplicative. Therefore, all types can be transformed to a specified type $f$, i.e., $R_{f}=\mathbf{I}_{fi}R_{i}$ for all $i\neq f,i\in\{1,2,\cdots,M\}$. This means that linear heterogeneous robots are transformed into homogeneous robots. In other words, Problem 2 becomes Problem 1. Specifically, after transformation, strategy space $\mathbf{S}^{\prime}\in\mathbb{R}^{N}$ and initial robot distributions $\mathbf{d}^{\prime}_{x},\mathbf{d}^{\prime}_{y}$ become $N$-dimension vectors. Then the reachable set of initial strategy sets $\mathcal{X}(\mathbf{d}^{\prime}_{x})$ and $\mathcal{Y}(\mathbf{d}^{\prime}_{y})$ can be calculated by (8) and Problem 2 can be solved using the same approach for Problem 1.

In Problem 3, two players allocate cyclic-dominance-heterogeneous (CDH) robots on graph $G$. In this paper, we specify that if robot type $R_{i}$ dominates robot type $R_{j}$, then $R_{i}$ is capable of neutralizing or overcoming a greater number of $R_{j}$ than its own quantity. With CDH robots, the linear intrinsic transformation between robot types is broken and not guaranteed to be closed anymore. For example, if $M=3$ and $R_{1}=2R_{2},R_{2}=2R_{3},R_{3}=2R_{1}$, by circularly converting $R_{1}$ to $R_{2}$, $R_{2}$ to $R_{3}$, and $R_{3}$ to $R_{1}$, the number of $R_{1}$ increases out of thin air. Therefore, we design a new transformation rule, named elimination transformation between different types of CDH robots.

Based on the elimination transformation rule, we construct a novel utility function to decide on the outcome of the game. In particular, we consider three types of CDH robots (i.e., $M=3$) as in the case of Rock-Paper-Scissor. ¹¹1For $M\geq 4$, the operation becomes even more complex and differs from the case of $M=3$, which we explain by an example in the Appendix. We leave the case of $M\geq 4$ for future research. Notably, the inhibiting property of the CDH robot allocation implies that the intrinsic matrix satisfies $\mathbf{I}_{ij}>1$ for $(i,j)\in\{(1,2),(2,3),(3,1)\}$.