An Equilibrium Analysis of the Arad-Rubinstein Game*

Christian Ewerhart† Stanisław Kaźmierowski‡

Abstract. Colonel Blotto games with discrete strategy spaces effectively
illustrate the intricate nature of multidimensional strategic reasoning. This
paper studies the equilibrium set of such games where, in line with prior
experimental work, the tie-breaking rule is allowed to be flexible. We begin
by pointing out that equilibrium constructions known from the literature
extend to our class of games. However, we also note that, irrespective of the
tie-breaking rule, the equilibrium set is excessively large. Specifically, any
pure strategy that allocates at most twice the fair share to each battlefield
is used with positive probability in some equilibrium. Furthermore,
refinements based on the elimination of weakly dominated strategies prove
ineffective. To derive specific predictions amid this multiplicity, we compute
strategies resulting from long-run adaptive learning.

Keywords. Colonel Blotto games, multidimensional strategic reasoning, tie-
breaking rules, Nash equilibrium, dominated strategies, adaptive learning

JEL codes. C72 Noncooperative games; C91 Laboratory, individual behavior; D74
Conflict, conflict resolution, alliances, revolutions

*) This paper has benefited from valuable comments and suggestions by Marcin Dziubiński, Dan Kovenock, Brian Roberson, and attendants of the session “Contests I” at the SAET Conference in Santiago de Chile. The second-named author thanks the Department of Economics of the University of Zurich for its hospitality. The work has been supported by the Polish National Science Center through grant 2018/29/B/ST6/00174. This manuscript reflects copy-edit suggestions put forth by ChatGPT 3.5.

$\dagger$) Department of Economics, University of Zurich;
<EMAIL_ADDRESS>
$\ddagger$) Department of Computer Science, University of Warsaw;
<EMAIL_ADDRESS>
1\. Preliminaries

1.1 Introduction

In a Colonel Blotto game, as envisaged by Borel (1921), two adversaries are
tasked with allocating their budgets of a resource secretly over a given set
of battlefields, aiming to conquer as many battlefields as possible. In each
battlefield, victory is awarded to the adversary allocating a higher amount of
the resource, where a tie-breaking rule is invoked when both parties assign an
equal amount. Applications of Colonel Blotto games extend beyond military
conflicts to areas such as strategic marketing, electoral competition,
innovation contests, and network security. Key contributions in the
literature, including Roberson (2006) for continuous and Hart (2008) for
discrete strategy spaces, assumed that the Colonel Blotto game is constant-sum
at ties, i.e., that any tied battlefield is ultimately conquered by one
contestant or another, but never lost. This characteristic of the standard
model ensures that the Colonel Blotto game is a two-person constant-sum game,
significantly simplifying the equilibrium analysis. Notably, however, the
assumption is not satisfied in experimental studies such as Arad and
Rubinstein’s (2012) investigation of multidimensional strategic reasoning. In
their case, tied battlefields count as lost for both parties, rendering the
standard equilibrium characterization invalid.111See Arad and Rubinstein
(2012, p. 584) for their statement: “We are not aware of any analysis of the
Nash equilibria of our version of the game.”

The present study investigates a class of Colonel Blotto games characterized
by discrete strategy spaces and flexible tie-breaking rules. Our model nests
both the constant-sum version of the game and its variant where tied
battlefields generate no value. We present an approach that allows
constructing Nash equilibria in this wider class of games. In particular, we
find an equilibrium in the example considered by Arad and Rubinstein (2012).
However, a caveat emerges. Specifically, our analysis reveals an excessively
large equilibrium set within the model. Furthermore, attempts to narrow the
set of equilibria down by applying the concept of weak dominance prove
ineffective. To derive specific predictions nevertheless, we explore the
implications of long-run adaptive learning.

1.2 Contribution

The present study contributes to the literature on finite Blotto games in two
main ways. Firstly, we construct Nash equilibria in the analyzed class of
games. For the constant-sum game, Hart (2008) demonstrated that marginal
distributions on individual battlefields can be chosen to be essentially
uniform. Consequently, assuming divisibility, players can partition the set of
battlefields into pairs, evenly distribute their resources, and randomize
uniformly within each pair. We observe that the precise form of the tie-
breaking rule is less crucial, as the probability of a tie remains constant
across bid levels used in equilibrium. We also point out that the loss of
payoffs due to ties, when compared to the constant-sum version, is
insufficient to make overbidding an attractive strategy. Based on these
observations, we establish equilibria in the model with flexible tie-breaking,
specifically in the Arad-Rubinstein game. In doing so, we identify conditions
under which the equilibrium initially identified by Hart (2008) persists in
games with modified tie-breaking.

Our second main contribution is the observation that irrespective of the tie-
breaking rule, the equilibrium set of games in the considered class is
excessively large. More specifically, we show that any pure strategy that does
not put too many resources on any individual battlefield is part of some
equilibrium strategy. The idea of identifying pure strategies that are part of
some equilibrium arises already in Tukey (1949), who termed those strategies
as “good.” We find that any pure strategy that allocates at most twice the
fair share of the budget to each battlefield is good in this
sense.222Conversely, strategies that concentrate the resource on too few
battlefields are never good. Moreover, none of these strategies can be
eliminated by equilibrium refinements based on the elimination of weakly
dominated strategies. As a remedy to this problem, we propose simulating long-
run adaptive learning, which indeed yields definite predictions commensurate
with experimental data.333The analysis also leads to a number of supplementary
observations on the constant-sum model, which we decided to report upon in a
separate section before the conclusion.

1.3 Related literature

In his seminal paper on Colonel Blotto games, Borel (1921) considered both
continuous and finite strategy spaces. For the model with continuous strategy
spaces, Roberson (2006) characterized optimal marginal distributions and
unique equilibrium payoffs. He also noted that in the continuous model, tie-
breaking rules often do not matter (but may need modification to ensure
existence).

For the model with discrete strategy spaces, Hart (2008) constructed
equilibria not only in all cases with homogeneous endowments, but also for
special cases with heterogeneous endowments. He used two auxiliary models. In
the Colonel Lotto game, players can be thought of as being restricted to mixed
strategies that are invariant under arbitrary permutations of the set of
battlefields. In the General Lotto game, the budget constraint needs to be
satisfied in expectation only. Solutions of the General Lotto game turn into
solutions of the corresponding Colonel Lotto and Colonel Blotto games provided
that those solutions are feasible, i.e., marginals can be derived from a joint
distribution that satisfies the budget constraint with equality. Building on
these concepts, Dziubiński (2013, 2017) characterized the set of optimal
marginal distributions in the General Lotto game and, provided that the number
of resources is divisible by the number of battlefields, also the set of
optimal marginal distributions of Colonel Blotto games with discrete strategy
spaces. Despite this progress, the general characterization of the equilibrium
set in Colonel Blotto games with discrete strategy spaces has remained
elusive. More recently, Liang et al. (2019) and Aspect and Ewerhart (2022)
characterized equilibria in discrete Colonel Blotto games with two
battlefields. Prior work has not attempted to characterize the equilibrium in
a discrete Colonel Blotto game with a modified tie-breaking rule.444However,
Rapoport and Almadoss (2000) and Dechenaux et al. (2006) have considered an
all-pay auction with discrete bids and a modified tie-breaking rule.

Experimental tests of Blotto games not mentioned above include Avrahami and
Kareev (2009), Kohli et al. (2012), Chowdhury et al. (2013), Avrami et al.
(2014), and Montero et al. (2016), among others.

1.4 Overview of the paper

The structure of this paper is as follows. Section 2 introduces the model. In
Section 3, we present an approach for constructing Nash equilibria within the
analyzed class of games. Section 4 concerns the equilibrium set. Section 5
deals with refinements, while Section 6 reports on the simulation of adaptive
learning utilizing a high-performance computing environment. Section 7
discusses extensions. Our supplementary findings regarding the standard model
are compiled in Section 8. Section 9 concludes the paper. Technical proofs are
provided in an appendix.

2\. The model

2.1 Setup and notation

Two players, denoted by ${A}$ and ${B}$, each allocate a total of $N\geq 1$
units of a resource over $K\geq 2$ battlefields.555In the excluded cases where
$N=0$ or $K=1$, players have only one strategy. However, note that we allow
for $K=2$, which is not necessarily trivial in our model. Units of the
resource are not divisible. Hence, a pure strategy of player $i$ is a vector

$s^{i}=\left(\begin{matrix}s^{i}_{1}\\\ \vdots\\\
s^{i}_{K}\end{matrix}\right)\text{,}$

such that $s_{i}^{k}\in\\{0,1,\ldots,N\\}$ for every $k\in\\{1,\ldots,K\\}$,
and

$\sum^{K}_{k=1}s_{k}^{i}=N.$

The set of strategies for players $A$ and $B$ is identical and denoted by $S$.
As usual, we refer to the opponent of player $i$ by $-i$. For a given pure
strategy profile $(s^{i},s^{-i})\in S\times S$, the payoff of player
$i\in\\{{A},{B}\\}$ in the Colonel Blotto game is defined by

$\mathrm{\pi}^{i}\left(s^{i},s^{-i}\right)=\sum^{K}_{k=1}\left(\mathds{1}_{s_{k}^{i}>s_{k}^{-i}}+\frac{\alpha}{2}\cdot\mathds{1}_{s_{k}^{i}=s_{k}^{-i}}\right),$

where $\mathds{1}_{s_{k}^{i}>s_{k}^{-i}}$ equals one if player $i$’s bid in
battlefield $k$ exceeds that of player $-i$, and zero otherwise,
$\mathds{1}_{s_{k}^{i}=s_{k}^{-i}}$ equals one in the case of a tie on
battlefield $k$, and zero otherwise, and $\alpha$ is a parameter. The
departure from the standard model is the introduction of flexible tie-
breaking, represented by $\alpha$. We call the two-player game with strategy
sets and payoffs defined as above the Colonel Blotto game
$\mathcal{B}_{\alpha}\equiv\mathcal{B}_{\alpha}(N,K)$.

2.2 Examples

Below, we recall two examples of finite Colonel Blotto games that have been
considered in the literature.

######  Example 1 (Hart, 2008).

In the standard version of the Colonel Blotto game, $\mathcal{B}_{1}(N,K)$,
player $i$’s payoff is defined as

$\mathrm{\pi}^{i}\left(s^{i},s^{-i}\right)=\sum^{K}_{k=1}\left(\mathds{1}_{s_{k}^{i}>s_{k}^{-i}}+\frac{1}{2}\cdot\mathds{1}_{s_{k}^{i}=s_{k}^{-i}}\right).$

The constant-sum setup underlying Example 1 has indeed been prevalent in the
literature. Borel (1921, p. 100) considered a particular case where $N=7$ and
$K=3$, a solution of which has been offered by Hart (2008). The setup in
Example 1 has been tested as a symmetric control by Avrahami et al. (2014) for
$N\in\\{16,24\\}$ and $K=8$.

######  Example 2 (Arad and Rubinstein, 2012).

Two colonels are asked to distribute a total of $N=120$ units of the resource
over a total of $K=6$ battlefields. The payoff of a player is the number of
battlefields that she assigned strictly more resources than her opponent.
Thus, the game is $\mathcal{B}_{0}(120,6)$, the common set of strategies is
given as
$S=\\{s^{i}\in\\{0,1,\ldots,120\\}^{6}:\sum^{6}_{k=1}s_{k}^{i}=120\\}$, and
the payoff of player $i$ is defined by

$\mathrm{\pi}^{i}\left(s^{i},s^{-i}\right)=\sum^{6}_{k=1}\,\mathds{1}_{s_{k}^{i}>s_{k}^{-i}}.$

Abstracting from the fact that the first example keeps $N$ and $K$ flexible,
the main difference between the two examples lies in the tie-breaking rule
applied. In contrast to Example 1, the game in Example 2 fails to be constant-
sum, as the sum of payoffs of both players depends on probabilities of ties
occurring on individual battlefields. This complicates the equilibrium
analysis but also makes the game more interesting. Intuitively, setting
$\alpha=0$ provides an additional incentive to outguess the opponent. For
instance, in an experiment with $\alpha=1$, subjects might perceive the pure
strategy $(20,20,20,20,20,20)^{\prime}$ as a focal point that leads to a fair
division.666Here and below, we represent the strategy as a row vector via
transposition. With $\alpha=0$, however, payoffs at this focal point are zero
for both players, i.e., there is a strong incentive to engage in at least some
additional reasoning. As this consideration is mentioned by Arad and
Rubinstein (2012) early in their work, it might have contributed to their
decision to depart from the standard tie-breaking rule.

2.3 Assumptions

For expositional reasons, we will initially work under a set of simplifying
assumptions. The implications of dropping these assumptions will be discussed
in the extensions section. Our first assumption concerns the parity of the
number of battlefields.

######  Assumption 1.

$K$ is even.

Assumption 1 simplifies the analysis but can often be dropped at the cost of
additional arguments. Experimental papers tend to work under the assumption.
Our second assumption concerns the relationship between $N$ and $K$.

######  Assumption 2.

$N$ is divisible by $K$.

Thus, in the main part of the analysis, we will assume that the number of
resources $N$ is a multiple of $K$. It follows from Assumption 2 that

$m=\frac{N}{K}$

is an integer. For an experimental subject, this means that the uniform
allocation that assigns $m$ units of the resource to each of the battlefields
is a possibility. E.g., Assumption 2 is violated in Avrahami and Kareev
(2014), but it holds in Avrahami et al. (2014). The parameter $m$ will play an
important role in the sequel. The same is true for the efficiency parameter
$\alpha$ on which we impose the following assumption.

######  Assumption 3.

$\alpha\in[0,2]$.

Assumption 3 may be considered natural but nevertheless restricts the
efficiency parameter in two ways. The restriction $\alpha\geq 0$ says that
ties cannot cause inefficiencies beyond the complete loss of the battlefield
value. For $\alpha<0$, players would have a very strong incentive to avoid
ties, which may lead to asymmetric equilibria. Conversely, for $\alpha>2$,
ties would be “superefficient,” so that pure-strategy equilibria become
natural. Such possibilities will be further discussed in the extensions
section.

Note that Assumptions 1 through 3 hold in the Arad-Rubinstein game. Indeed, in
Example 2, $K=6$ is even, $m=\frac{120}{6}=20$ is an integer, and
$\alpha=0\in[0,2]$.

2.4 Equilibrium concept

Given a finite non-empty set $X$, let $\mathrm{\Delta}\left(X\right)$ denote
the set of all probability distributions on $X$. We are interested in mixed-
strategy Nash equilibria of the game, i.e., mixed strategy profiles
$\sigma=(\sigma^{i},\sigma^{-i})\in\mathrm{\Delta}(S)\times\mathrm{\Delta}(S)$
such that no player can improve her expected payoff by unilaterally changing
her mixed strategy. By a symmetric Nash equilibrium strategy, we mean any
mixed strategy $\sigma^{i}$ such that $\sigma=(\sigma^{i},\sigma^{i})$ is a
mixed-strategy Nash equilibrium.

A crucial property of Colonel Blotto games is that payoffs are functions of
the respective marginal distributions at each battlefield. Given a mixed
strategy $\sigma^{i}$ and a battlefield $k\in\\{1,\ldots,K\\}$, let
$\sigma^{i}_{k}$ denote the marginal distribution of $\sigma^{i}$ at
battlefield $k$. Following Hart (2008), we denote the uniform marginal on
$\\{0,\dots,2m\\}$ by $U^{m}$. A mixed strategy $\sigma^{i}$ such that
$\sigma^{i}_{k}=U^{m}$ for every battlefield $k$ will be said to induce
uniform marginals.

3\. Equilibrium in the Colonel Blotto game with flexible tie-breaking

In this section, we present a simple approach that allows constructing an
equilibrium in the Colonel Blotto game with the flexible tie-breaking rule. As
mentioned before, this will lead us to an equilibrium in the Arad-Rubinstein
game as well.

3.1 A canonical equilibrium

The following result characterizes one particular Nash equilibrium in
$\mathcal{B}_{\alpha}(N,K)$.

######  Proposition 1.

Impose Assumptions 1 through 3. Then, a symmetric equilibrium strategy of
$\mathcal{B}_{\alpha}(N,K)$ is given by uniform randomization over the set of
pure strategies

$S_{0}=\left\\{{\left(\begin{matrix}0\\\ 2m\\\ \vdots\\\ 0\\\
2m\end{matrix}\right)},{\left(\begin{matrix}1\\\ 2m-1\\\ \vdots\\\ 1\\\
2m-1\end{matrix}\right)},\ldots,{\left(\begin{matrix}2m\\\ 0\\\ \vdots\\\
2m\\\ 0\end{matrix}\right)}\right\\}.$

In the resulting equilibrium, players’ expected payoffs amount to
$\pi^{*}=K\cdot\frac{m+\frac{\alpha}{2}}{2m+1}$.

  * Proof.

See the Appendix. ∎

As can be seen, players partition the set of battlefields into pairs. This is
possible, of course, because the number of battlefields has been assumed even
via Assumption 1.777We would like to add, however, that Assumption 1 can be
dropped, as will be explained in the extensions section. To each pair of
battlefields, a constant number of $2m$ resources is allocated, which is
feasible due to Assumption 2. Moreover, the split among the two battlefields
in each pair is uniformly distributed, with perfect correlation across pairs.
We note that players’ strategies induce uniform marginals. Indeed, for any
battlefield $k$, every number of resources in $\\{0,1,2,\ldots,2m\\}$ is
assigned to battlefield $k$ with the same probability of $\frac{1}{2m+1}$.

3.2 Discussion

Hart (2008) has shown that, under Assumptions 1 and 2, strategies inducing
uniform marginals form an equilibrium in the constant-sum game
$\mathcal{B}_{1}(N,K)$. The point to note is that this remains the case even
with flexible tie-breaking. The reason why the equilibrium property does not
break down with more flexible tie-breaking, and this is the main observation
that motivated our work on the present paper, is that, given uniform
marginals, the likelihood of getting tied is constant across all bid levels
that are used in equilibrium with positive probability. As a result, the
indifference in the standard setup with $\alpha=1$ is not affected by the
modification of the payoff functions at ties.

One might wonder if, with the modified tie-breaking in place, players would
not have an incentive to bid higher than $2m$ on some of the battlefields.
Such an incentive might arise for $\alpha<1$, because the tie-breaking is
inefficient in that case. However, overbidding cannot raise a player’s payoff.
The reason is that any additional unit of the resource required to assign more
than $2m$ on some battlefield needs to be taken from some other battlefield,
where this lowers the probability of winning by $\frac{1}{2m+1}$. Indeed,
every bid level in $\\{0,1,\ldots,2m\\}$ is used by the opponent on every
battlefield with the same probability of $\frac{1}{2m+1}$. On the other hand,
the increase in payoff from bidding $2m+1$ instead of $2m$ in a battlefield is
$\frac{1}{2m+1}\times(1-\alpha)\leq\frac{1}{2m+1}$. Therefore, given
Assumption 3, or more precisely given that $\alpha\geq 0$, the deviation never
yields a strictly higher payoff.888As the discussion shows, the conclusion of
Proposition 1 remains technically true for $\alpha>2$. However, as mentioned
before, there is no reason to hide one’s strategy for $\alpha\geq 2$, i.e.,
symmetric pure-strategy equilibria may be more plausible in that case.

3.3 Illustration

We illustrate Proposition 1 with an example.

######  Corollary 1 (Equilibrium in the Arad-Rubinstein game).

The following strategy is a symmetric Nash equilibrium strategy in
$\mathcal{B}_{0}(120,6)$. Both players individually and independently
randomize uniformly over the set

$S_{0}=\left\\{{\left(\begin{matrix}0\\\ 40\\\ 0\\\ 40\\\ 0\\\
40\end{matrix}\right)},{\left(\begin{matrix}1\\\ 39\\\ 1\\\ 39\\\ 1\\\
39\end{matrix}\right)},\ldots,{\left(\begin{matrix}40\\\ 0\\\ 40\\\ 0\\\ 40\\\
0\end{matrix}\right)}\right\\}\text{.}$

The equilibrium payoff is $\pi^{*}=\frac{120}{41}\approx 2.927$.

  * Proof.

Immediate from Proposition 1. ∎

Even though the equilibrium characterized by Proposition 1 has a canonical
structure (e.g., it has uniform marginals, and is symmetric with respect to
permutations of the battlefield pairings and within battlefield pairings), it
is not the only equilibrium, as will be shown in the next section.

4\. Understanding the equilibrium set

The equilibrium set turns out to be very large. To illustrate this point, we
study the support of equilibrium strategies in the present section. We first
identify pure strategies that are chosen with positive probability in some
mixed-strategy Nash equilibrium (Subsection 4.1). Then, we outline the proof
(Subsection 4.2). Finally, we turn to strategies that are never “good”
(Subsection 4.3).

4.1 Pure strategies that arise in some equilibrium

The following result provides an indication about the size of the equilibrium
set.

######  Proposition 2.

Impose Assumptions 1 through 3. Then, every pure strategy $s^{i}$ such that
$s^{i}_{k}\leq\frac{2N}{K}$ for every battlefield $k$, is used with positive
probability in some equilibrium strategy of $\mathcal{B}_{\alpha}(N,K)$.

  * Proof.

See Subsection 4.2. ∎

Thus, every pure strategy that does not allocate an excessive number of
resources to an individual battlefield is part of some mixed-strategy Nash
equilibrium.

In the Arad-Rubinstein game $\mathcal{B}_{0}(120,6)$, every pure strategy that
assigns at most 40 soldiers to each of the battlefields is part of some mixed
strategy Nash equilibrium. This observation illustrates a drawback of the Nash
equilibrium concept for the analysis of Colonel Blotto games with practical
relevance. The set of equilibrium predictions is simply very large. We will
come back to this issue in the next section.

Proposition 2 relates to observations made by Tukey (1949) saying that “there
are good strategies in which a given player either (i) sends out no units,
(ii) sends out more than half of some kind of unit, or (iii) sends units to
more than half of the available sites.”999These general observations hold, in
particular, for an asymmetric version of the Colonel Blotto game discussed in
McDonald and Tukey (1949). Interpreting “good” as appearing in the support of
an equilibrium strategy, it is not hard to see that Proposition 2 implies
conditions (i) and (iii) under the assumptions of the present paper. An
illustration of the possibility of condition (ii) will be given later in the
paper (see Example 3).

4.2 Proof of Proposition 2

To understand why Proposition 2 is true, suppose that both players uniformly
randomize over the set of pure strategies

$S_{1}=\left\\{\left(\begin{matrix}s_{1}\\\ 2m-s_{1}\\\ \vdots\\\ s_{L}\\\
2m-s_{L}\end{matrix}\right):s_{1},\ldots,s_{L}\in\\{0,1,\ldots,2m\\}\right\\}.$

Clearly, this strategy induces uniform marginals. But this implies, by the
discussion following Proposition 1, that both players are actually using an
equilibrium strategy.101010However, compared to Proposition 1, the correlation
of the $L$ uniform distributions, one for each pair of battlefields, has been
dropped.

Let $s$ be any pure strategy such that $s_{k}\leq 2m$ for all
$k\in\\{1,\ldots,K\\}$. Then, it suffices to replace the two pure strategies

$\left(\begin{matrix}s_{1}\\\ 2m-s_{1}\\\ \vdots\\\ s_{K-1}\\\
2m-s_{K-1}\end{matrix}\right)\text{, }\left(\begin{matrix}2m-s_{2}\\\ s_{2}\\\
\vdots\\\ 2m-s_{K}\\\ s_{K}\end{matrix}\right)$

in the support of the mixed strategy $\widehat{\sigma}$ by

$\left(\begin{matrix}s_{1}\\\ s_{2}\\\ \vdots\\\ s_{K-1}\\\
s_{K}\end{matrix}\right)\text{, }\left(\begin{matrix}2m-s_{2}\\\ 2m-s_{1}\\\
\vdots\\\ 2m-s_{K}\\\ 2m-s_{K-1}\end{matrix}\right)\text{,}$

respectively. The marginals do not change, and hence, we have found an
equilibrium strategy in which $s$ is played with positive probability. This
concludes the argument.

4.3 Strategies that are never “good”

In analogy to Proposition 2, one may ask what type of pure strategies are
never used in any equilibrium. To address this question, we identify the
maximum loss of efficiency that is feasible with modified tie-breaking. Then,
we derive conditions on pure strategies that make them render an expected
payoff too low to correspond to the maximum efficiency loss. Proceeding along
these lines, we show that any strategy that focuses on too few battlefields
will never be part of any mixed-strategy Nash equilibrium.

######  Proposition 3.

Impose Assumptions 1 and 2, and let $\alpha\in[0,1)$. Then, any pure strategy
that allocates the resource to strictly less than

$K^{\ast}=\frac{NK}{2N+K}\left(1-\frac{\alpha}{2-\alpha}\right)$

battlefields is never part of any equilibrium of $\mathcal{B}_{\alpha}(N,K)$.

  * Proof.

See the Appendix. ∎

How strong is the conclusion of Proposition 3 in specific games? For the Arad-
Rubinstein game,

$K^{\ast}=\frac{120\cdot 6}{2\cdot 120+6}=2.9268.$

This means that every pure strategy that assigns a positive number of
resources to less than three battlefields is never a part of any equilibrium.

######  Corollary 2.

In the Arad-Rubinstein game, any pure strategy that allocates the resource to
just one or two battlefields is never part of any equilibrium.

  * Proof.

See the text above. ∎

Thus, pure strategies such as $(120,0,0,0,0,0)^{\prime}$ and
$(60,60,0,0,0,0)^{\prime}$ are never good strategies in the example.
Regrettably, this leaves a gap to the conclusion of Proposition 2. I.e., we do
not know if strategies such as $(60,30,30,0,0,0)^{\prime}$ that assign
strictly positive resources over at least three battlefields and more than 40
soldiers to at least one of those are “good.”111111As $\alpha$ becomes larger,
the conclusion of Proposition 3 weakens. For instance, the conclusion becomes
void in the limit case as $\alpha\rightarrow 1$.

5\. Refinements

Given that the Arad-Rubinstein game is a static game, it is natural to check
if dominance relationships between strategies might help to narrow down the
set of equilibria (e.g., Kohlberg and Mertens, 1986).

Recall that a pure strategy $s^{i}\in S$ for player $i\in\\{A,B\\}$ is weakly
dominated by another pure strategy $\widehat{s}^{i}\in S$ if (i)
$\pi^{i}(s^{i},s^{-i})\leq\pi^{i}(\widehat{s}^{i},s^{-i})$ for every pure
strategy $s^{-i}\in S$, and (ii) there exists at least one pure strategy
$s^{-i}\in S$ for the opponent such that
$\pi^{i}(s^{i},s^{-i})<\pi^{i}(\widehat{s}^{i},s^{-i})$. Thus, a pure strategy
is weakly dominated by another pure strategy if it never yields a greater
payoff than the other strategy, but a strictly lower payoff than the other
strategy against at least one pure strategy of the opponent.

It turns out that the elimination of dominated strategies by pure strategies
is entirely ineffective for small $\alpha$.

######  Proposition 4.

Suppose that $\alpha<\frac{2}{K}$. Then, no pure strategy in
$\mathcal{B}_{\alpha}(N,K)$ is weakly dominated by any other pure strategy.

  * Proof.

See the Appendix. ∎

The condition in the proposition is satisfied, in particular, in the Arad-
Rubinstein game. There, given that identical choices of pure strategies by the
two players lead to ties in all battlefields, $\alpha=0$ implies that the
diagonal entries of the payoff matrix are all zero. In contrast, all of the
off-diagonal entries of the payoff matrix are positive because at least one
battlefield is won by each player if strategies differ. Therefore, no pure
strategy is weakly dominated by any other pure strategy if $\alpha=0$. This
idea of the proof generalizes in a straightforward way to positive but
sufficiently small $\alpha$.121212However, the conclusion of Proposition 4
need not hold for standard tie-breaking. As we are going to show in Section 8,
a pure strategy may be weakly dominated by another pure strategy if
$\alpha=1$.

######  Corollary 3.

In the Arad-Rubinstein game, there are no strategies that are weakly dominated
by a pure strategy.

  * Proof.

Immediate from Proposition 4.∎

6\. Adaptive learning

We have seen above that the traditional game-theoretic analysis of the Arad-
Rubinstein game is bound to remain inconclusive. Although a small number of
pure strategies could be categorized as “bad,” the concept of Nash
equilibrium, even after applying standard refinements, is not sufficiently
stringent to derive a meaningful reference point for empirical work. In this
section, we therefore approach the problem of making a theory-led prediction
from a different perspective, viz. by determining the implications of long-run
adaptive learning.

The biggest obstacle to a simulation of long-run adaptive learning in a
Colonel Blotto game is the size of the strategy space. The number of pure
strategies in the Arad-Rubinstein game is

$|S|=\binom{125}{5}=234^{\prime}531^{\prime}275\text{.}$

To be able to obtain results within a reasonable time frame, we decided to
exploit the symmetry of the game. Technically, this amounts to considering the
set of pure strategies in the corresponding Colonel Lotto game. Thereby, the
size of the strategy space reduces to $436^{\prime}140$ pure
strategies.131313Details on the computation of the number of strategies are
provided in the Appendix.

For adaptive learning, we assumed that players follow fictitious play (Brown,
1949; Robinson, 1951).141414For the computation of equilibrium, more efficient
algorithms are available (see, e.g., Ahmadinejad et al., 2019). However, our
aim here is the simulation of a learning process. Thus, after an initial
period of play, each player considers the empirical frequency distribution of
prior play as the best predictor for future play. In our simulation, players
interacted over 50 million rounds. The learning algorithm has been implemented
in Matlab. The computations were conducted on a NEMA cluster, which is a high-
performance SGI Altix UV2000 system, equipped with 4TBs of main memory and 96
physical CPU cores. The operating system was Unix.

Figure 1: Rank-order analysis

The support of the learned mixed strategy in the Colonel Lotto game consisted
of $|S_{0}|=11^{\prime}008$ pure strategies. Table I shows the nine most
likely pure strategies in the learned mixed strategy and compares their
respective rank in the learned strategy (column “Nash rank”) to the rank found
by Arad and Rubinstein (2012, Table 9). As can be seen, the rankings are
related. Specifically, eight out of the top-9 ordered strategies appearing in
the Arad-Rubinstein data are among the top-30 unordered Nash strategies (the
exception being the rather odd strategy $(120,0,0,0,0,0)^{\prime}$). Moreover,
the modal strategy $(20,20,20,20,20,20)^{\prime}$ is identical between the two
rankings. As for Arad and Rubinstein’s (2012) “winning strategy”
$(31,31,31,23,2,2)^{\prime}$, it appears at position 47 in the creation of new
best responses during the fictitious-play process and later ends up at Nash
rank 272. These observations intuitively square with the iterative reasoning
explanation, and suggest that further inquiry of the relationship between
learning and iterative reasoning in multidimensional decision problems might
be worth to be pursued.

7\. Extensions

This section offers several extensions. We first discuss the case of an odd
number of battlefields (Subsection 7.1), then the case where $n$ is not
divisible by $K$ (Subsection 7.2), next payoff-inequivalent equilibria
(Subsection 7.3), and finally the possibility of pure strategy Nash equilibria
(Subsection 7.4).

7.1 Odd number of battlefields

If the number of battlefields is odd so that Assumption 1 is violated, then it
is no longer feasible to partition the set of battlefields into pairs. As a
result, the equilibrium analysis is complicated substantially. However, using
a result of Dziubiński (2017), the conclusion of Proposition 1 can be shown to
hold even if Assumption 1 is dropped. Specifically, even if $K$ is odd, there
still exists a mixed strategy that induces uniform marginals on every
battlefield. As space limitations make it impossible to replicate the original
arguments, we confine ourselves to an illustrative example.151515Further
background on this example is provided in the Appendix.

######  Example 3.

Consider the Colonel Blotto game $\mathcal{B}_{\alpha}(6,3)$, where
$\alpha\in[0,2]$. Then, the mixed strategy $\sigma^{i}$ given by

$\sigma^{i}\left(s^{i}\right)=\begin{cases}\;\dfrac{1}{10}&\text{ if $s^{i}\in
S_{a}$,}\\\ \\\ \;\dfrac{1}{20}&\text{ if $s^{i}\in S_{b}$,}\\\ \\\
\;\;0&\text{ otherwise,}\end{cases}$

where

$\displaystyle S_{a}$ $\displaystyle=$
$\displaystyle\left\\{\left(\begin{matrix}2\\\ 2\\\
2\end{matrix}\right),\left(\begin{matrix}3\\\ 3\\\
0\end{matrix}\right),\left(\begin{matrix}3\\\ 0\\\
3\end{matrix}\right),\left(\begin{matrix}0\\\ 3\\\
3\end{matrix}\right),\left(\begin{matrix}4\\\ 1\\\
1\end{matrix}\right),\left(\begin{matrix}1\\\ 4\\\
1\end{matrix}\right),\left(\begin{matrix}1\\\ 1\\\
4\end{matrix}\right)\right\\}\text{,}$ $\displaystyle S_{b}$ $\displaystyle=$
$\displaystyle\left\\{\left(\begin{matrix}4\\\ 2\\\
0\end{matrix}\right),\left(\begin{matrix}4\\\ 0\\\
2\end{matrix}\right),\left(\begin{matrix}2\\\ 4\\\
0\end{matrix}\right),\left(\begin{matrix}2\\\ 0\\\
4\end{matrix}\right),\left(\begin{matrix}0\\\ 4\\\
2\end{matrix}\right),\left(\begin{matrix}0\\\ 2\\\
4\end{matrix}\right)\right\\}\text{.}$

induces uniform marginals and is a symmetric equilibrium strategy.

Generalizing the construction underlying Example 3, we obtain the following
result.

######  Proposition 5.

The conclusion of Proposition 1 continues to be true if Assumption 1 is
dropped.

  * Proof.

See the Appendix. ∎

7.2 $N$ is not divisible by $K$

Assumption 2, which has been assumed in the main strand of the analysis,
requires that $N$ is divisible by $K$. We can relax this assumption somewhat,
as illustrated by the following example

######  Example 4.

Impose Assumption 3. Then, in $\mathcal{B}_{\alpha}(6,4)$, the mixed strategy
that randomizes uniformly over the set

$S_{\sigma^{i}}=\left\\{\left(\begin{matrix}0\\\ 3\\\ 0\\\
3\end{matrix}\right),\left(\begin{matrix}1\\\ 2\\\ 1\\\
2\end{matrix}\right),\left(\begin{matrix}2\\\ 1\\\ 2\\\
1\end{matrix}\right),\left(\begin{matrix}3\\\ 0\\\ 3\\\
0\end{matrix}\right)\right\\},$

is a symmetric equilibrium strategy.

It is not hard to convince oneself that the logic of the example, or
equivalently, the proof of Proposition 1, extends to any game in which
$K=2\cdot L$ is even and $N$ is divisible by $L$, which is the number of pairs
of battlefields.161616We have not attempted to go beyond that case, however.

7.3 Payoff-inequivalent equilibria

In the constant-sum model, all equilibria yield the same payoff. This is not
the case with flexible tie-breaking, however. To understand why, let
$U^{m}_{\text{O}}$ and $U^{m}_{\text{E}}$ denote uniform marginals on the odd
and even numbers between $0$ and $2m$, respectively. As shown by Hart (2008,
Thm. 7), any pair of strategies that induce marginals in the convex hull of
$\\{U^{m}_{\text{O}},U^{m}_{\text{E}}\\}$ is an equilibrium in
$\mathcal{B}_{1}(N,K)$. In particular, any strategy profile
$\sigma=(\sigma^{i},\sigma^{-i})$, where $\sigma^{i}_{k}=U^{m}_{\text{O}}$ and
$\sigma^{-i}_{k}=U^{m}_{\text{E}}$ for every battlefield $k$, is an asymmetric
equilibrium in $\mathcal{B}_{1}(N,K)$. But any such profile remains an
equilibrium for $\alpha\in[0,1]$, because inefficient tie-breaking makes
deviations less attractive. Moreover, given the absence of ties, equilibrium
payoffs are $K/2$ for both players, which is different from the expression in
Proposition 1. Similarly, every mixed strategy $\sigma^{i}$, where
$\sigma^{i}_{k}=U^{m}_{\text{O}}$ or $\sigma^{i}_{k}=U^{m}_{\text{E}}$ for
every battlefield $k$ is a symmetric equilibrium strategy in
$\mathcal{B}_{1}(N,K)$. Since deviations make ties less likely, these profiles
remain equilibria for $\alpha\in[1,2]$.

7.4 Equilibria in pure strategies

Pure-strategy Nash equilibria, both symmetric and asymmetric, are feasible if
parameters are outside of the usual range. For instance, if the payoffs from
ties are sufficiently high (i.e., if $\alpha$ is close to or exceeds 2), then
the Colonel Blotto game transforms into a coordination game with numerous
symmetric pure strategy equilibria.

######  Proposition 6.

If $\alpha\geq\frac{2\cdot(K-1)}{K}$, then every pure strategy $s^{i}\in S$ is
a symmetric Nash equilibrium strategy in $\mathcal{B}_{\alpha}(N,K)$.

  * Proof.

See the Appendix. ∎

The pathological outcome indicated by Proposition 6 in cases where $\alpha$ is
excessively large provides support for our Assumption 3, a premise upheld
throughout the main analysis.

Asymmetric pure strategy equilibria may emerge when the number of resources,
$N$, is small relative to the number of battlefields (and Assumption 3 is in
place). Specifically, if $2N\leq K$, adversaries can easily avoid conflict by
dividing the set of battlefields between them.

8\. Supplementary section: Implications for the standard model

Our analysis has also led to new insights for the Colonel Blotto game with
standard tie-breaking. These concern the characterization of the set of “good
strategies (Subsection 8.1), a refinement concept (Subsection 8.2), and the
effectiveness of weak dominance (Subsection 8.3).

8.1 “Good” strategies in the standard model

Combining Proposition 2 with a result by Dziubiński (2017), the conclusion can
be considerably sharpened in the constant-sum case.

######  Corollary 4.

Impose Assumptions 1 and 2. Then, an arbitrary pure strategy $s^{i}$ is used
with positive probability in some equilibrium of $\mathcal{B}_{1}(N,K)$ if and
only if $s^{i}_{k}\leq\frac{2N}{K}$ for every battlefield $k$.

  * Proof.

See the Appendix. ∎

8.2 Refinement

Let $\sigma_{\text{even}}$ and $\sigma_{\text{odd}}$ denote mixed strategies
with marginals uniform on the even and odd integers within
$\\{0,\ldots,2m\\}$, respectively. As shown by Hart (2008), under Assumptions
1 and 2, (i) such strategies exist and (ii) any convex combination of such
strategies is an equilibrium strategy in $B_{1}(N,K)$.

######  Proposition 7.

Impose Assumptions 1 through 3. Then, the only type of strategy that remains
an equilibrium strategy for all values of $\alpha$ in a neighborhood of
$\alpha=1$ has uniform marginals.

  * Proof.

See the Appendix. ∎

These observations suggest a simple form of equilibrium selection in finite
Colonel Blotto games with standard tie-breaking. The fact that the asymmetric
equilibrium $(\sigma_{\text{even}},\sigma_{\text{odd}})$ breaks down for
$\alpha>1$ is an indication that this equilibrium is not very robust in the
standard model of Hart (in addition to being difficult to coordinate upon,
given the asymmetry of the strategy profile). Similarly, the fact that
$(\sigma_{\text{even}},\sigma_{\text{even}})$ and
$(\sigma_{\text{odd}},\sigma_{\text{odd}})$ equilibria break down for
$\alpha<1$ is an indication that those equilibria are not very robust either,
which might explain why, in the standard model, any equilibrium with uniform
marginals, i.e., without parity considerations, is intuitively more plausible
than any of the other feasible combinations.

8.3 Weak dominance

The following example shows that weak dominance may actually eliminate
strategies in the Colonel Blotto game with standard tie-breaking.

######  Example 5.

In $\mathcal{B}_{1}(120,6)$, the pure strategy $(120,0,0,0,0,0)^{\prime}$ is
weakly dominated by $(115,1,1,1,1,1)^{\prime}$.

Details can be found in the Appendix. Example 5 shows that the condition on
$\alpha$ imposed in Proposition 4 cannot be simply dropped.171717The
determination of the set of strategies that are iteratively undominated in the
Colonel Blotto game with standard tie-breaking is, however, beyond the scope
of the present paper.

9\. Conclusion

While the equilibrium analysis of discrete Blotto games is mathematically
appealing, it falls short in explaining the observations from applied economic
research. Consequently, beyond merely characterizing the set of Nash
equilibria, it becomes imperative to pinpoint “reasonable” choices within the
expansive strategy set. As suggested by our simulation analysis, exploring the
limit points of adaptive learning processes might offer a promising avenue to
address this issue. However, it may not be the sole viable approach.

A. Appendix

This section contains proofs omitted from the body of the paper. The following
lemma prepares the proof of Proposition 1.

###### Lemma A. 1

Impose Assumptions 2 and 3. Let $\sigma=(\sigma^{A},\sigma^{B})$ be a mixed
strategy profile in $\mathcal{B}_{\alpha}(N,K)$ such that $\sigma^{i}$ induces
uniform marginals for $i\in\\{A,B\\}$. Then, $\sigma$ is a Nash equilibrium.

  * Proof.

Suppose that both players use the assumed mixed strategies that induce uniform
marginals. Then, the probability of a tie on any given battlefield is
$\frac{1}{2m+1}$. Therefore, each player $i$’s expected payoff from
$\sigma=(\sigma^{A},\sigma^{B})$ equals

$\pi^{i}(\sigma)=\frac{K}{2}+K\cdot\frac{1}{2m+1}\cdot\frac{\alpha-1}{2}=\frac{K\cdot\left(2N+\alpha
K\right)}{4N+2K}.$

Suppose that player $i\in\\{A,B\\}$ deviates to a pure strategy $s^{i}\in S$.
The mixed strategy $\sigma^{-i}$ allocates every number of resources in
$\\{0,1,2,\ldots,2m\\}$ on every battlefield $k$ with the same probability of
$\frac{1}{2m+1}$. If player $i$ assigns strictly more than $2m$ resources to a
battlefield, her payoff from that battlefield is $1$. If player $i$ assigns
weakly less than $2m$ to battlefield $k$, then she overwhelms the opponent on
that battlefield with probability $\frac{s_{k}^{i}}{2m+1}$ and achieves a tie
with probability $\frac{1}{2m+1}$. Hence, player $i$’s expected payoff from
battlefield $k$ is

$\pi^{i}_{k}\left(s^{i},\sigma^{-i}\right)=\min\\{1,\frac{s_{k}^{i}}{2m+1}+\frac{\alpha}{2}\cdot\frac{1}{2m+1}\\}.$

It follows that

$\displaystyle\pi^{i}\left(s^{i},\sigma^{-i}\right)$
$\displaystyle=\sum_{k=1}^{K}\pi^{i}_{k}\left(s^{i},\sigma^{-i}\right)$
$\displaystyle\leq\sum_{k=1}^{K}\left(\frac{s_{k}^{i}}{2m+1}+\frac{\alpha}{2}\cdot\frac{1}{2m+1}\right)$
(A.1) $\displaystyle=\frac{N}{2m+1}+\frac{K\cdot\alpha}{2\cdot(2m+1)}$
$\displaystyle=\frac{K\cdot(2N+\alpha K)}{4N+2K}.$

As both $i$ and $s^{i}$ were arbitrary, no player can raise her payoff by
deviating from $\sigma=(\sigma^{A},\sigma^{B})$. Hence, $\sigma$ is a Nash
equilibrium, which completes the proof. ∎

  * Proof of Proposition 1.

The mixed strategy $\sigma^{i}$ assigns every number of resources
$s_{k}^{i}\in\\{0,1,\ldots,2m\\}$ to every battlefield $k$ with the same
probability $\frac{1}{2m+1}$. Hence, $\sigma^{i}$ induces uniform marginals.
It therefore follows from Lemma A.1 that $\sigma^{i}$ is a symmetric
equilibrium strategy. ∎

  * Proof of Proposition 3.

Consider an arbitrary pure strategy $s^{i}$ that allocates a positive number
of units of the resource to $K_{+}\in\\{1,\ldots,K\\}$ battlefields and zero
units to the remaining battlefields. Then, player $i$’s expected payoff of
$s^{i}$ against an arbitrary pure strategy $s^{-i}$ satisfies the relationship

$\displaystyle\pi^{i}\left(s^{i},s^{-i}\right)$ $\displaystyle\leq K_{+}\cdot
1+(K-K_{+})\cdot\frac{\alpha}{2}$ $\displaystyle=\frac{\alpha}{2}\cdot
K+\frac{2-\alpha}{2}\cdot K_{+}\text{.}$ (A.2)

Consider now a deviation by player $i$ to some mixed strategy $\sigma^{i}$
that induces uniform marginals. Proposition 1 provides an example of such a
mixed strategy. The following analysis is analog to the proof of Lemma A.1. If
player $-i$ assigns strictly more than $2m$ units of the resource to
battlefield $k$, then $i$’s payoff from that battlefield is zero. If, however,
player $-i$ assigns weakly less than $2m$ to battlefield $k$, then player $i$
overwhelms her opponent on that battlefield with probability
$\frac{2m-s_{k}^{-i}}{2m+1}$ and achieves a tie with probability
$\frac{1}{2m+1}$. Hence, player $i$’s expected payoff from battlefield $k$ is

$\pi^{i}_{k}\left(\sigma^{i},s^{-i}\right)=\max\\{0,\frac{2m-s_{k}^{-i}}{2m+1}+\frac{\alpha}{2}\cdot\frac{1}{2m+1}\\}.$

It follows that

$\displaystyle\pi^{i}\left(\sigma^{i},s^{-i}\right)$
$\displaystyle=\sum_{k=1}^{K}\pi^{i}_{k}\left(\sigma^{i},s^{-i}\right)$
$\displaystyle\geq\sum_{k=1}^{K}\left(\frac{2m-s_{k}^{-i}}{2m+1}+\frac{\alpha}{2}\cdot\frac{1}{2m+1}\right)$
$\displaystyle=\frac{NK}{2N+K}+\frac{\alpha}{2}\cdot\frac{K^{2}}{2N+K}.$ (A.3)

A straightforward calculation shows that the right-hand side of equation (A.3)
strictly exceeds the right-hand side of equation (A.2) if and only if

$K_{+}<K^{\ast}\equiv\frac{2}{2-\alpha}\cdot\frac{NK(1-\alpha)}{2N+K}\text{.}$

In particular, in that case,
$\pi^{i}\left(\sigma^{i},s^{-i}\right)>\pi^{i}_{k}\left(\sigma^{i},s^{-i}\right)$,
for any $s^{-i}\in S$. Thus, $s^{i}$ is never a best response if
$K_{+}<K^{\ast}$. This proves the proposition.∎

  * Proof of Corollary 4.

(if) Immediate from Proposition 2. (only if) This follows from Dziubiński
(2017, Cor. 2). For the reader’s convenience, we offer a direct proof.
Consider a mixed-strategy equilibrium
$\sigma^{\ast}=(\sigma^{A,\ast},\sigma^{B,\ast})$ in $\mathcal{B}_{1}(N,K)$.
To provoke a contradiction, suppose that there is some player $i\in\\{A,B\\}$
and some pure strategy $s^{i}$ in the support of $\sigma^{i,\ast}$ such that
$s^{i}_{k}>2m$ for some battlefield $k$. As equilibrium strategies in two-
person constant-sum game are interchangeable (Osborne and Rubinstein, 1994, p.
23), $\sigma^{i,\ast}$ is a best response also to the mixed strategy
$\sigma^{-i}=\sigma^{i}$ identified in Proposition 1. Moreover, since the bid
vector $s^{i}$ is chosen with positive probability in the mixed strategy
$\sigma^{i,\ast}$, the pure strategy $s^{i}$ is likewise a best response to
$\sigma^{-i}$. But from $s^{i}_{k}>2m$ for some battlefield $k$, inequality
(A.1) in the proof of Lemma A.1 is strict, so that that

$\pi^{i}\left(s^{i},\sigma^{-i}\right)<\frac{K\cdot(2N+\alpha
K)}{4N+2K}=\pi^{i}\left(\sigma^{i},\sigma^{-i}\right).$

Thus, $s^{i}$ is not a best response to $\sigma^{-i}$ after all. The
contradiction proves the assertion. ∎

  * Proof of Proposition 4.

By contradiction. Suppose that $s$ is a pure strategy that is weakly dominated
by another pure strategy $\widehat{s}$. In $\mathcal{B}_{\alpha}(N,K)$, the
diagonal entries of the payoff matrix correspond to an outcome with $K$ ties
and are, therefore, equal to $K\cdot\frac{\alpha}{2}$. In particular, this is
the payoff of $\widehat{s}$ against itself. However, as $\widehat{s}$ is
necessarily different from $s$, the strategy $s$ bids strictly higher than
$\widehat{s}$ on at least one battlefield. Therefore, the payoff of $s$
against $\widehat{s}$ is at least one. Under the assumption made, this is
strictly higher than $K\cdot\frac{\alpha}{2}$. The contradiction shows that no
pure strategy can be weakly dominated by any other pure strategy. ∎

The following lemma is used in the proof of Proposition 5.

######  Lemma A. 2 (Dziubiński, 2017)

Suppose that Assumption 2 holds and that $K$ is odd. Then, there exists a
mixed strategy $\sigma^{i}$ such that $\sigma^{i}_{k}=U^{m}$ for every
battlefield $k\in\\{1,\ldots,K\\}$.

  * Proof.

See Dziubiński, (2017, Proposition 2). ∎

  * Proof of Proposition 5.

By Lemma A.2, we find a uniform strategy for each player even if Assumption 1
fails to hold. As Assumption 1 is not imposed in Lemma A1, the pair of
strategies constitutes a Nash equilibrium in $\mathcal{B}_{\alpha}(N,K)$. This
proves the claim. ∎

  * Details on Example 3..

We will construct a battlefield-symmetric uniform equilibrium strategy. Let
$p_{411}$ etc. denote the respective probability that a player chooses the
pure strategies $(4,1,1)^{\prime}$ etc. Then, accounting for symmetries,
$p_{411}=p_{141}=p_{114}$, etc. Moreover, any solution to the system

$\left(\begin{array}[]{ccccc}1&0&0&0&2\\\ 0&0&2&2&0\\\ 0&1&2&0&2\\\
2&0&2&0&0\\\ 0&0&0&1&2\end{array}\right)\left(\begin{array}[]{c}p_{411}\\\
p_{222}\\\ p_{123}\\\ p_{330}\\\
p_{420}\end{array}\right)=\left(\begin{array}[]{c}\frac{1}{5}\\\
\frac{1}{5}\\\ \frac{1}{5}\\\ \frac{1}{5}\\\ \frac{1}{5}\end{array}\right)$

induces uniform marginals. Restricting attention to solutions that yield
nonnegative probabilities, the general solution is given by

$\left(\begin{array}[]{c}p_{411}\\\ p_{222}\\\ p_{123}\\\ p_{330}\\\
p_{420}\end{array}\right)=(1-\lambda)\left(\begin{array}[]{c}\frac{1}{10}\\\
\frac{1}{10}\\\ 0\\\ \frac{1}{10}\\\
\frac{1}{20}\end{array}\right)+\lambda\left(\begin{array}[]{c}\frac{1}{15}\\\
0\\\ \frac{1}{30}\\\ \frac{1}{15}\\\ \frac{1}{15}\end{array}\right)\text{,}$

where $\lambda\in[0,1]$ is arbitrary. The solution shown in the body of the
paper corresponds to $\lambda=0$. ∎

  * Proof of Proposition 6.

Consider a symmetric profile $s=(s^{i},s^{-i})$ in pure strategies, where
$s^{i}=s^{-i}$. The payoff to both players from $s$ is equal to
$K\cdot\frac{\alpha}{2}$. As player $i$ is unable to win on all the
battlefields, the payoff for a deviating player $i$ is bounded from above by
$K-1$. Hence, $K-1\leq K\cdot\frac{\alpha}{2}$, which is equivalent to the
inequality in the statement of the proposition. ∎

  * Counting the number of strategies.

We start by noting that the number of pure strategies does not depend on the
tie-breaking rule. In general, as each pure strategy $s^{i}\in S$ in the
Colonel Blotto game $\mathcal{B}_{\alpha}(N,K)$ corresponds uniquely to a
finite sequence

$\textstyle\underbrace{1,\ldots,1}_{s_{1}^{i}},\ast,\underbrace{1,\ldots,1}_{s_{2}^{i}},\ast,\ldots,\ast,\underbrace{1,\ldots,1}_{s_{N}^{i}}\text{,}$

where each “1” stands for a unit of the resource and the “$\ast$” is a
separator between neighboring battlefields. Given that there are $N$ units of
the resource to allocate and $K-1$ separators, the number of pure strategies
in $\mathcal{B}_{\alpha}(N,K)$ is

$|S|=\binom{N+K-1}{K-1}.$

The number of pure strategies in the corresponding Colonel Lotto game, i.e.,
taking account of symmetries between battlefields, is given by $p(N+K,K)$,
where $p(N,K)$ denotes the number of partitions of $N$ into exactly $K$ parts.
Although a simple formula is unavailable, the recursive relationship

$p(N,K)=p(N-1,K-1)+p(N-K,K)$

with initial conditions $p(N,1)=1$ and $p(N,K)=0$ if $K>N$ allows computing
this number in specific examples (Gupta, 1970). ∎

  * Proof of Proposition 7.

The probability of a tie at any given battlefield is zero in
$(\sigma_{\text{even}},\sigma_{\text{odd}})$, and
$(\sigma_{\text{odd}},\sigma_{\text{even}})$; similarly, the probability of a
tie is $\frac{m+1}{2m+1}$ in $(\sigma_{\text{even}},\sigma_{\text{even}})$,
and $\frac{m}{2m+1}$ in $(\sigma_{\text{odd}},\sigma_{\text{odd}})$. If player
$-i$’s marginal is not uniform and $\alpha>1$ ($\alpha<1$), then player $i$
has the incentive to deviate to the parity that is used more (less) often by
$-i$. ∎

  * Details on Example 5..

Let $s^{i}=(120,0,0,0,0,0)^{\prime}$. We start by claiming that $s^{i}$ never
results in a payoff higher than 3 against any pure strategy $s^{-i}$. Indeed,
if $s^{-i}_{1}=120$, then player $i$’s payoff is 3. If, however,
$s^{-i}_{1}<120$, then player $i$ wins battlefield 1, loses at least one of
the other five battlefields, and achieves at most a tie on the remaining
battlefields. Again, therefore, the payoff for player $i$ from choosing
$s^{i}$ cannot exceed 3, which proves the claim. We continue and claim that
$s^{i}$ is weakly dominated by $\widehat{s}^{i}=(115,1,1,1,1,1)^{\prime}$. For
this, we check the conditions in the definition of weak dominance. (i) To
provoke a contradiction, suppose that $s^{i}$ yields a payoff strictly higher
than $\widehat{s}^{i}$ against a given pure strategy $s^{-i}$. Then, $s^{i}$
necessarily yields a payoff strictly higher than $\widehat{s}^{i}$ from the
first battlefield, meaning that $s^{-i}_{1}\geq 115$. Hence, $s^{-i}$ assigns
at most 5 units of the resource to the remaining 5 battlefields. But each of
those units can reduce the payoff from strategy $\widehat{s}^{i}$ on
battlefields 2 through 6 by at most 0.5 utils. Therefore, in the situation
considered, $\widehat{s}^{i}$ yields at least 2.5 units from battlefields 2
through 6. The exact value of 2.5 is only achieved when $s^{-i}_{1}=115$,
hence, the resulting payoff is at least 3, as the first battlefield is also
tied. When $s^{-i}_{1}>115$, the payoff from battlefields 2 through 6 is at
least 3. As follows, player $i$’s payoff from using $\widehat{s}^{i}$ is at
least 3 for every opponent’s strategy where $s^{-i}\geq 115$, in conflict with
the presumption made above. (ii) Suppose that
$s^{-i}=(119,1,0,0,0,0)^{\prime}$. Then, $\pi^{i}(s^{i},s^{-i})=3$, while
$\pi^{i}(\widehat{s}^{i},s^{-i})=4.5$. This proves the claim. ∎

## References

  * Ahmadinejad et al., (2019) Ahmadinejad, A., Dehghani, S., Hajiaghayi, M., Lucier, B., Mahini, H., and Seddighin, S. (2019).  From duels to battlefields: Computing equilibria of Blotto and other games.  Mathematics of Operations Research, 44(4):1304–1325.
  * Arad and Rubinstein, (2012) Arad, A. and Rubinstein, A. (2012).  Multi-dimensional iterative reasoning in action: The case of the Colonel Blotto game.  Journal of Economic Behavior & Organization, 84:571–585.
  * Aspect and Ewerhart, (2022) Aspect, L. and Ewerhart, C. (2022).  Colonel Blotto games with a head start.  Available at SSRN 4204082.
  * Avrahami and Kareev, (2009) Avrahami, J. and Kareev, Y. (2009).  Do the weak stand a chance? Distribution of resources in a competitive environment.  Cognitive Science, 33(5):940–950.
  * Avrahami et al., (2014) Avrahami, J., Kareev, Y., Todd, P. M., and Silverman, B. (2014).  Allocation of resources in asymmetric competitions: How do the weak maintain a chance of winning?  Journal of Economic Psychology, 42:161–174.
  * Borel, (1921) Borel, É. (1921).  La Théorie du Jeu et les Équations Intégrales à Noyau Symétrique.  Comptes Rendus de l’Académie des Sciences, 173:1304–1308.  Translated by Savage L. J., The theory of play and integral equations with skew symmetric kernels. Econometrica 21 (1953) 97–100.
  * Brown, (1949) Brown, G. W. (1949).  Some notes on computation of games solutions.  Rand Corporation.
  * Chowdhury et al., (2013) Chowdhury, S. M., Kovenock, D., and Sheremeta, R. M. (2013).  An experimental investigation of Colonel Blotto games.  Economic Theory, 52:833–861.
  * Dechenaux et al., (2006) Dechenaux, E., Kovenock, D., and Lugovskyy, V. (2006).  Caps on bidding in all-pay auctions: Comments on the experiments of A. Rapoport and W. Amaldoss.  Journal of Economic Behavior & Organization, 61(2):276–283.
  * Dziubiński, (2013) Dziubiński, M. (2013).  Non-symmetric discrete General Lotto games.  International Journal of Game Theory, 42(4):801–833.
  * Dziubiński, (2017) Dziubiński, M. (2017).  The spectrum of equilibria for the Colonel Blotto and the Colonel Lotto games.  In Bilò, V. and Flammini, M., editors, Algorithmic Game Theory, pages 292–306, Cham. Springer International Publishing.
  * Gupta, (1970) Gupta, H. (1970).  Partitions – a survey.  Journal of Res. of Nat. Bur. Standards-B Math. Sciences B, 74:1–29.
  * Hart, (2008) Hart, S. (2008).  Discrete Colonel Blotto and General Lotto games.  International Journal of Game Theory, 36:441–460.
  * Kohlberg and Mertens, (1986) Kohlberg, E. and Mertens, J.-F. (1986).  On the strategic stability of equilibria.  Econometrica, 54(5):1003–1037.
  * Kohli et al., (2012) Kohli, P., Kearns, M., Bachrach, Y., Herbrich, R., Stillwell, D., and Graepel, T. (2012).  Colonel Blotto on Facebook: The effect of social relations on strategic interaction.  In Proceedings of the 4th Annual ACM Web Science Conference, pages 141–150.
  * Liang et al., (2019) Liang, D., Wang, Y., Cao, Z., and Yang, X. (2019).  Colonel Blotto games with two battlefields.  SSRN Electronic Journal.
  * McDonald and Tukey, (1949) McDonald, J. and Tukey, J. (1949).  Colonel Blotto: A problem of military strategy.  Fortune, June, page 102.
  * Montero et al., (2016) Montero, M., Possajennikov, A., Sefton, M., and Turocy, T. L. (2016).  Majoritarian Blotto contests with asymmetric battlefields: An experiment on apex games.  Economic Theory, 61:55–89.
  * Osborne and Rubinstein, (1994) Osborne, M. J. and Rubinstein, A. (1994).  A Course in Game Theory.  MIT Press.
  * Rapoport and Amaldoss, (2000) Rapoport, A. and Amaldoss, W. (2000).  Mixed strategies and iterative elimination of strongly dominated strategies: An experimental investigation of states of knowledge.  Journal of Economic Behavior & Organization, 42(4):483–521.
  * Roberson, (2006) Roberson, B. (2006).  The Colonel Blotto game.  Economic Theory, 29(1):1–24.
  * Robinson, (1951) Robinson, J. (1951).  An iterative method of solving a game.  Annals of Mathematics, 54(2):296–301.
  * Tukey, (1949) Tukey, J. W. (1949).  A problem of strategy.  Econometrica, 17(1):73.


# Grounding from an AI and Cognitive Science Lens

Goonmeet Bajaj  The Ohio State University
<EMAIL_ADDRESS>Srinivasan Parthasarathy  The Ohio State University
<EMAIL_ADDRESS>Valerie L. Shalin  Wright State University
<EMAIL_ADDRESS>Amit Sheth  University of South Carolina
<EMAIL_ADDRESS>
###### Abstract

Grounding is a challenging problem, requiring a formal definition and
different levels of abstraction. This article explores grounding from both
cognitive science and machine learning perspectives. It identifies the
subtleties of grounding, its significance for collaborative agents, and
similarities and differences in grounding approaches in both communities. The
article examines the potential of neuro-symbolic approaches tailored for
grounding tasks, showcasing how they can more comprehensively address
grounding. Finally, we discuss areas for further exploration and development
in grounding.

## Introduction

Robust communication transcends human-human communication settings to include
human-machine, machine-machine, and multi-agent human-machine teams. Grounding
fosters a common understanding among agents performing a task - typically in
the real world. With the growing number of human-AI interactions, grounding is
a fundamentally important capability of AI systems, models, and agents [11, 5,
8, 17]. Grounding allows AI systems to bridge semantic gaps in the real world,
team with other agents in such environments, process inputs from the
environment, and learn from interactions. A successful synthetic teammate
requires several cognitive capacities, including situation assessment, task
behavior, language comprehension and generation [3], and knowledge gap
resolution processes. Grounding enables agents with different capabilities to
communicate.

Both cognitive scientists and computer scientists have focused on how to make
internal mechanisms (or representations) of external entities intrinsic to the
agent itself rather than being defined by an external designer or interpreted
by an observer [17]. Recent efforts in Natural Language Processing (NLP),
Computer Vision (CV), and Human-Computer Interaction (HCI) improve the
grounding of machine agents. However, it remains a multi-dimensional
challenge, encompassing diverse contexts, abstractions, and modalities of
understanding (see Figure 2). In the absence of a clear definition, we are
unable to determine genuine advances or task-specific adjustments.

This article sheds light on different aspects of grounding through the lens of
cognitive science and artificial intelligence (AI), discusses specific neuro-
symbolic solutions for grounding, and highlights future work).

“A successful synthetic teammate requires several cognitive capacities
including situation assessment, task behavior, language comprehension and
generation [3], and knowledge gap resolution processes. Grounding enables
agents with different capabilities to communicate.”

## Cognitive Science Lens

Identification of the symbol grounding problem in cognitive science dates to
Harnad. Following the introduction of computation with symbols credited to
McCarthy, Searle’s Chinese Room Problem revealed how amodal symbol
manipulation lacks grounding. Yet, symbol manipulation is often the foundation
of contemporary AI systems. Challenges to amodal symbol manipulation include
embodied grounding [12] and the recent use of language and simulation to
establish grounding [13]. Given this long-standing research problem, Ziemke
[17] groups grounding efforts into two categories: 1) cognitivist or 2)
enactivist.

Cognitivism grounds atomic primitives in sensorimotor invariants [17].
Concepts constructed from these inherit the grounding of their constituents.
Nevertheless, different agents may reason with different abstractions,
creating a divergence that requires repair. A more recent perspective,
enactivism values the role of action, embodiment, and environment. Robotic
agents can potentially obtain grounding by physically linking to an
environment through sensory input and motor output. Agent functions can be
either engineered or learned. With meticulously engineered grounding, systems
may demonstrate the ‘correct’ behavior, but their internal mechanisms are not
inherent to the system. Alternatively, an agent function can be acquired by
adjusting connection weights instead of requiring programming. However, the
definition of a correct agent function and how to evaluate various agent
functions remains a challenge.

Given our interest in real-world human-AI interaction and multimodal systems,
we emphasize enactivist grounding. However, cognitivist grounding remains
essential, as we summarize from Barsalou [13]:

> Mental imagery, cognitive grammar, mental spaces, and compositional
> reasoning support explanations for thought. Neuroimaging shows that higher
> cognition is realized in the brain’s model systems. One theory is that
> grounding mechanisms serve as an interface, peripheral to core cognitive
> operations.

Barsalou predicts that future cognitive research will integrate classic
symbolic architecture, statistical/dynamic systems, and grounding cognition.
Formal and computational accounts of grounding will shift from epiphenomenal
to casual. Grounding mechanisms may potentially replace the amodal mechanisms
in cognitive architectures. We believe that advancements in neuro-symbolic AI
will be instrumental here. Next, we describe the grounding problem from a
machine learning and AI perspective and highlight what is missing from a
cognitive science lens.

## Artificial Intelligence Lens

Grounding in AI has typically been referred to as connecting concepts to other
knowledge bases or world models. We first discuss the different grounding
efforts in the AI [11] community. We then draw parallels with the cognitive
science community[17, 13] and identify some nuanced distinctions.

Chandu et al. [11], note the use of static versus dynamic terminology used in
the NLP / CV context, similar to the cognitivist versus enactivist distinction
in cognitive science (see Figure 1). Static grounding – the most predominant
form, relies on accessible evidence supporting the common ground to connect
concepts within a given context to the real world [11]. For static grounding,
common ground is typically through an agent (e.g., machine) interacting with a
static knowledge base (KB) to frame a response and deliver it back to the
other agent (e.g., human). Both agents may share this common ground by
assuming its universality, i.e., no external references. The success of
grounding is measured based on the agent’s ability to link the query to the
available data. In contrast, dynamic grounding establishes common ground
iteratively, where both agents can communicate to seek and provide
clarifications, typically in a potentially changing physical environment. This
allows corrections to misunderstandings.

(a) The static and dynamic definitions in neurosymbolic AI loosely mirror the
cognitivist and enactivist grounding in cognitive science, respectively,
although there are subtle differences. Cognitive scientists tend to focus more
on the specific monitoring and repair processes in case of different
perspectives between interacting agents, whether due to differences in static
knowledge or engagement opportunities with an open world.

(b) For an AI or cognitive agent to interact effectively with its environment,
it must understand the language used by external agents, accurately assess the
current situation and context, and identify and address gaps in its knowledge
[4]. This process involves recognizing when it lacks understanding or has
difficulty with language comprehension and communicating these knowledge gaps
to other agents or external sources. By utilizing these processes, agents can
update their knowledge of the task and environment, avoiding catastrophic
errors and allowing for the iterative and interactive aspects of dynamic
grounding. Consider a machine agent, like a drone, working with a human
operator to survey a specific area. The agent can use its background (stored)
knowledge to understand the monitored environment and the mission’s purpose
(static/cognitivist grounding). Suppose the agent comes across something it
has not seen before and cannot identify. In that case, it will interactively
and iteratively ask the human operator for assistance in closing this gap
(dynamic/enactivist grounding).

Figure 1: Types of Grounding

Static grounding: According to Harnad, manipulating symbolic representations
without meaning cannot support reasoning. AI researchers responded with
different representations for different uses. Typically, these frameworks have
the following key components: the designator, denoting the name or symbol
utilized to identify the category; the epistemological representation,
employed to recognize instances of the category; and the inferential
representation, comprising “encyclopedic” knowledge about the category and its
members. The epistemological representations are termed concept descriptions.
In computer vision, these representations are considered object models [5].
This form of grounding is typically established using deductive learning. It
is consistent with cognitivist grounding, with little to no active or online
supervision from the environment or an external agent. ML efforts for static
grounding include using entity slot filling, adversarial references to
grounding visual referring expressions, visual semantic role labeling, and
disambiguation of concepts and entities [11]. Additionally, methods designed
for manipulating representations include fusion and concatenation,
representation alignment, and projection of representations into a shared
space. Finally, the ML community has designed different learning objectives to
address the grounding problem, including multitasking and joint training, the
design of new loss functions, and adversarial learning methods.

Dynamic grounding: Dynamic efforts in ML are typically designed for situations
where an entity in an environment is matched with an epistemological
representation that activates a larger knowledge structure containing the
composite concept representation. Such systems learn to ground their own
experience dynamically in the environment, creating more robust capabilities
not dependent on pre-programmed representations [5]. Grounding frameworks such
as learning from example and learning by conversation are consistent with
enactivist grounding in cognitive science. Efforts in the ML community for
dynamic grounding include grounding embodied agents, natural interactions with
human-in-the-loop feedback, and, more recently, grounding LLM-based agents
(https://rb.gy/2pfq1g). Nevertheless, grounding in mainstream machine learning
exploits deductive learning [5].

Limitations: One notable omission in ML is grounding with sensors or
environmental data [1]. Furthermore, the study of latent pragmatics is also
missing from Chandu et al.’s work. Pragmatic analysis, pioneered by Austin,
Grice, and Searle and extended by others such as Sperber, focuses on
understanding functional intentions and implications based on variations in
linguistic content across different contexts [18, 15, 16].

The lack of a consistent definition of grounding creates considerable
ambiguity regarding how to ground, what to ground, and where to ground. To
bridge this gap, Chandu et al. [11] outline the following grounding stages:
Stage 1 - Localization, Stage 2 - External Knowledge, Stage 3 - Common Sense,
and Stage 4 - Personalized Consensus. However, these stages are insufficient.
Consider a challenging example of grounding a drone (with an AI-based
decision-making model) to ensure safety concerns. Localization requires that
the drone accurately determine its position relative to its surroundings.
Next, grounding with external knowledge introduces additional information,
such as weather and airspace regulations, that inform subsequent action.
However, which external knowledge sources should be used and prioritized in
the decision-making? Stage 3 - Common sense could include avoiding obstacles
in its flight path and taking proactive measures to avoid risks or mitigate
potential harm. However, it is not easy to quantify and measure this grounding
stage. Stage 4 - Personalized consensus can help ground decisions to the
drone’s perception of the environment and prior experiences. However, it is
unclear whether the drone must adhere to its prior experiences when it
conflicts with human instructions that reflect a broader understanding of the
situation. While a helpful initial attempt, these stages are not sufficiently
specific to standardize how grounding occurs and at what abstraction levels.
The lack of definition allows for creative interpretation of the problem and,
therefore, new tasks, datasets, and methods. However, in the future, the
community will benefit from a standardized, comprehensive definition.

“The lack of a consistent definition of grounding creates considerable
ambiguity regarding how to ground, what to ground, and where to ground.”

Figure 2: Grounding has multiple dimensions and needs knowledge at different
levels of abstractions (this is similar to the need for linguistic, common
sense, world model, and domain knowledge for language understanding; see Fig.
3 of (https://bit.ly/KiLU). Grounding may occur at different levels in the
task execution process. For example, the drone agent must be able to
comprehend the instructions in a natural language format. Next, the
instruction may require parsing relevant symbols (in the case of neuro-
symbolic methods) for reasoning processes. The information extracted must then
be grounded to the drone’s capabilities (common-sense grounding). Finally, the
instruction must be grounded in the specific navigation task.

## Neuro-Symbolic Grounding

Neuro-symbolic methods can benefit grounding by integrating traditional
symbolic reasoning approaches with the generalization capabilities of neural
networks. Neuro-symbolic systems integrate the statistical learning
capabilities of neural networks with the structured, symbolic representations
used in classical AI. Neuro-symbolic AI seeks to benefit from the synergy of
symbolic and neural methods. Traditional symbolic reasoning methods use formal
languages (e.g., Planning Domain Definition Language (PDDL)) for reasoning
over knowledge stored in a structured format and represented by ‘symbols.’
These reasoning methods manipulate and infer from structured symbolic
representations, such as logic-based rules, knowledge graphs, or ontologies.
The symbolic representations provide a transparent and interpretable framework
for knowledge representations and logical reasoning. However, these systems
are brittle and often cannot be generalized. But combined with neural methods,
traditional methods leverage advancements in deep learning to acquire
knowledge representations and enhanced generalization capabilities effectively
[10]. Neural networks consist of interconnected layers of artificial neurons
that use weighted connections, enabling them to learn complex mappings between
inputs and outputs. These networks are instrumental in pattern recognition,
classification, regression, and sequence prediction. Therefore, neuro-symbolic
methods leverage the strengths of each paradigm.

As noted above, many of the grounding efforts in ML rely on deductive learning
and lack active or online supervision from the environment or an external
agent. Neuro-symbolic methods for grounding can offer several advantages,
including compositional reasoning and situational awareness.

“Neuro-symbolic methods for grounding can offer several advantages, including
compositional reasoning and situational awareness.”

One particular asset of neuro-symbolic methods is the use of functional
modules. Natural language texts (i.e., instructions or queries) are mapped to
functional modules that carry out atomic actions. These functional modules can
be user-defined or learned. This allows agent functions grounded in symbolic
representations to complete specific actions or generate responses.
Additionally, the compositional nature of these functional programs allows for
generalization to new combinations of parsed instructions or queries. The
functional modules can be used for both dynamic and static grounding as the
modules can operate over knowledge bases (including KGs). This aspect of
neuro-symbolic methods can help establish common ground, enabling agents to
interpret and execute instructions in a manner that aligns with symbolic human
reasoning. For example, Mao et al. [14] designed a new neuro-symbolic concept
learner that can learn embeddings for symbolic visual inputs. Learning these
mappings allows for continual learning and adaptation of new environmental
variables while preserving an agent’s task behavior. In this manner, neuro-
symbolic approaches can allow for the grounding of new concepts in an
environment and facilitate knowledge gap detection, identification, and
resolution processes leading to adaptive and robust models.

## Concluding Remarks

We have focused on explicit notions of grounding. We conclude with remarks on
implicit forms of grounding. Recently, the use of digital twins has emerged to
augment the performance of machine learning systems in domains ranging from
autonomous transportation [6] to next-generation wireless communication [7].
Digital twins can provide a high-fidelity representation of physical entities
by accurately modeling the structure, behavior, and characteristics of a real-
world system (world model) governed by physical laws. Such ideas can expand
the training dataset (out-of-distribution), allowing models to be generalized.
This implicit grounding in physical laws can prevent non-factual generation,
reduce hallucinations, and anchor model responses to specific information,
facilitating harmonization with the corresponding world model. We note that
using digital twins for grounding parallels the contention of Pickering and
Garrod [8] that interlocutors implicitly comprehend each other by aligning
their models of the discussed situation at various levels of cognitive and
linguistic representation. Such implicit alignment processes between agents
(akin to digital twins) inspire computational grounding processes.

Finally, we advocate for more knowledge-infused neuro-symbolic learning and
reasoning systems that naturally integrate linguistic, common-sense, general
(world model), and domain-specific processes and knowledge to facilitate
static grounding. We expect fundamental progress on the synergistic use of
neural networks and structured semantics to advance from content processing to
content understanding and reasoning with the infusion of symbolic knowledge
(https://rb.gy/67wgx3). These methods require dynamic knowledge-elicitation
strategies integrating multimodal pragmatic context and interactions with
domain experts in the loop to achieve dynamic grounding and alignment with
user intent.

Acknowledgements: We acknowledge the National Science Foundation (NSF) Award
#2335967 (AS and VS) and NSF award #CNS-2112471 (GB and SP).

## References

  * [1] Cangelosi, A., and Riga, T. (2006). An embodied model for sensorimotor grounding and grounding transfer: Experiments with epigenetic robots. Cognitive Science.
  * [2] W. Horton, B. Keysar. (1996). ”When do speakers take into account common ground?,” Cognition.
  * [3] Ball, J., et. al. (2010). The synthetic teammate project. Computational and Mathematical Organization Theory.
  * [4] Bajaj, G. et. al. (2022). Knowledge Gaps: A Challenge for Agent-Based Automatic Task Completion. Topics in Cognitive Science.
  * [5] P. Davidsson, (1993). ”Toward a general solution to the symbol grounding problem: combining machine learning and computer vision,” AAAI Fall Symposium.
  * [6] McClellan, A., et. al. (2022). A physics-based digital twin for model predictive control of autonomous unmanned aerial vehicle landing. Philosophical Transactions of the Royal Society A.
  * [7] Banerjee A. et. al., (2024). HORCRUX: Accurate Cross Band Channel Prediction, ACM MobiCom.
  * [8] M. Pickering, S. Garrod. (2004). ”Toward a mechanistic psychology of dialogue,” Behavioral and Brain Sciences.
  * [9] Branigan, H., et al. (2010).”Linguistic alignment between people and computers,” Journal of Pragmatics.
  * [10] A. Sheth et. al., (2023). ”Neurosymbolic Artificial Intelligence (Why, What, and How),” IEEE Intelligent Systems.
  * [11] K. Chandu. et. al., (2021), ”Grounding ‘Grounding’ in NLP,” Findings of ACL.
  * [12] R. Nuñez et. al., (1999), ”Embodied cognition as grounding for situatedness and context in mathematics education,” in Educational Studies in Mathematics.
  * [13] L. Barsalou. (2010). ”Grounded cognition: Past, present, and future,” Topics in Cognitive Science.
  * [14] Mao, J., et. al. (2019). The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision. ICLR.
  * [15] G. Leech, Principles of pragmatics. Routledge, 2016.
  * [16] D. Jurafsky. ”Pragmatics and computational linguistics,” in The handbook of pragmatics, pp. 578–604, 2006.
  * [17] T. Ziemke. (1999). ”Rethinking grounding,” in Understanding Representation in the Cognitive Sciences: Does Representation Need Reality.
  * [18] J. Searle, Speech acts: An essay in the philosophy of language. Cambridge university press, 1969.

Goonmeet Bajaj is a Ph.D. Candidate at the Ohio State University (OSU) and is
interested in cognitive-inspired AI. Contact her at<EMAIL_ADDRESS>
Srinivasan Parthasarathy is a Professor of Computer Science & Engineering and
co-directs the Data Analytics program at OSU. He is a fellow of the IEEE, AAIA
and the Robert Bosch Center for Data Science & AI. Contact him at
<EMAIL_ADDRESS>
Valerie Shalin is a Professor of Psychology at Wright State University.
Contact her at<EMAIL_ADDRESS>
Amit Sheth is the founding director of the AI Institute, NCR Professor of
Comp. Sc.& Engg. at USC. He received the 2023 IEEE-CS Wallace McDowell award
and is a fellow of IEEE, AAAI, AAIA, AAAS, and ACM. Contact him at
<EMAIL_ADDRESS>