# Min-max theorem for the game of Cops and Robber on geodesic spaces

Bojan Mohar
Department of Mathematics
Simon Fraser University
Burnaby, BC V5A 1S6, Canada
<EMAIL_ADDRESS>Supported in part by the NSERC Discovery Grant R611450 (Canada),
and by the Research Project J1-2452 of ARRS (Slovenia).On leave from IMFM,
Department of Mathematics, University of Ljubljana.

###### Abstract

The game of Cops and Robber is traditionally played on a finite graph. The
purpose of this note is to introduce and analyze the game that is played on an
arbitrary geodesic space. The game is defined in such a way that it preserves
the beauty and power of discrete games played on graphs and also keeps the
specialties of the pursuit-evasion games played on polyhedral complexes. It is
shown that the game can be approximated by finite games of discrete type and
as a consequence a min-max theorem is obtained.

##  1 Introduction

Pursuit-evasion games have a long history, especially in the setup of
_differential games_ [14, 25, 16, 20, 21]. Differential games with more
pursuers were also introduced in the 1970s, see, e.g. [12, 9, 22, 15] or a
more recent paper [11] and references therein. More recent important
application is design of robot movement in complicated environment, see e.g.
[1]. A more general class of such games played on finite graphs has been
devised in discrete setting. Nowakowski and Winkler [19] and Quilliot [23]
independently introduced the game of Cop and Robber that is played on a
(finite) graph. Aigner and Fromme [3] extended the game to include more than
one cop. For each graph $G$ and a positive integer $k$, the _Cops and Robber
game_ on $G$, involves two players. The first player controls $k$ _cops_
placed at the vertices of the graph, and the second player controls the
_robber_ , who is also positioned at some vertex. While the players
alternately move to adjacent vertices (or stay at their current position), the
cops want to catch the robber and the robber wants to prevent this ever to
happen. The main question is how many cops are needed on the given graph $G$
in order that they can guarantee the capture. The minimum such number of cops
is termed as the _cop number_ $c(G)$ of the graph.

The game of cops and robbers gained attention because of its ties with
structural graph theory. Classes of graphs that can be embedded in a surface
of bounded genus [3] and those that exclude some fixed graph as a minor [4]
have bounded cop number. In particular, all graphs that can be embedded in the
plane have cop number at most 3 [3]. We refer to the monograph by Bonato and
Nowakowski [6] for further details about the history of the game and for
overview of the main results.

One of our aims is to introduce the game in a more general setup of geodesic
metric spaces and study the relationship between the cop number and the
topology and geometry of the geodesic space.

The famous Lion and Man problem that was proposed by Richard Rado in the late
1930s and discussed in Littlewood’s Miscellany [17, 18] is a version of the
game with one pursuer (the Lion) and one evader (the Man). The man and the
lion are within a circular arena (unit disk in the plane) and they run with
equal maximum speed. It seems that in order to avoid the lion, the man would
choose to run on the boundary of the disk. A simple argument then shows that
the lion could always catch the man by staying on the segment joining the
center of the disk with the point of the man and slowly approaching him.
However, Besicovitch proved in 1952 (see [18, pp. 114–117]) that the man has a
simple strategy, in which he will approach but never reach the boundary, that
enables him to avoid capture forever no matter what the lion does.111The game
defined in this paper allows the use of Besicovitch strategy for the man, so
this example shows that the lion is able to come arbitrarily close to the man,
but can never catch him. More details can be found in [5].

One can prove that two lions are enough to catch the man in a disk. A recent
work by Abrahamsen et al. [1, 2] discusses the game with many lions versus one
man in an arbitrary compact subset of the plane whose boundary consists of
finitely many rectifiable simple closed curves and prove that three lions can
always get their prey. They also discuss the game when the man is just
slightly faster than lions, and find some surprising conclusions.

The game of cops and robbers can be defined on any metric space. However, it
is far from obvious how such a game can be defined in order to be natural,
resembling interesting examples and allowing for powerful mathematical tools.
Subtleties of the various versions of the game are nicely outlined in an
influential paper by Bollobás, Leader, and Walters [5], who were the first to
provide a general setup for such a game.

In this article we discuss the game of cops and robbers on arbitrary geodesic
spaces (see Section 2 or [7, 8] for definitions). We come up with a version of
the game that is somewhat different from the game version in [5], but
preserves all the beauty and power of discrete games played on graphs.
Moreover, our version keeps the characteristics of the pursuit-evasion games
played in a continuous setting and for instance allows for using strategies
similar to that of Besicovitch in the case of the Man and Lion game. It is
shown that our game can be approximated by finite games of discrete type and
as a consequence we are able to prove the min-max theorem.

##  2 Intrinsic metric in geodesic spaces

We consider a metric space $(X,d)$ and the corresponding metric space topology
on $X$. For $x,y\in X$, an _$(x,y)$ -path_ is a continuous map $\gamma:I\to X$
where $I=[0,1]$ is the unit interval on $\mathbb{R}$ and $\gamma(0)=x$ and
$\gamma(1)=y$. We allow the paths to be parametrized differently and in
particular we can replace $I$ with any finite interval on $\mathbb{R}$. The
space is _path-connected_ if for any $x,y\in X$, there exists an $(x,y)$-path
connecting them.

One can define the _length_ $\ell(\gamma)$ of the path $\gamma$ by taking the
supremum over all finite sequences $0=t_{0}<t_{1}<t_{2}<\cdots<t_{n}=1$ of the
values $\sum_{i=1}^{n}d(\gamma(t_{i-1}),\gamma(t_{i}))$. Note that
$\ell(\gamma)$ may be infinite; if it is finite, we say that $\gamma$ is
_rectifiable_. Note that the length of any $(x,y)$-path is at least $d(x,y)$.
The metric space $X$ is a _geodesic space_ if for every $x,y\in X$ there is an
$(x,y)$-path $\gamma$ whose length is equal to $d(x,y)$.

An $(x,y)$-path $\gamma$ is _isometric_ if $\ell(\gamma)=d(x,y)$. Observe that
for $0\leq t<t^{\prime}\leq 1$ the subpath $\gamma|_{[t,t^{\prime}]}$ is also
isometric. Therefore the set $\gamma(I)=\\{\gamma(t)\mid t\in I\\}$ is an
isometric subset of $X$. With a slight abuse of terminology, we say that the
image $\gamma(I)\subset X$ is an _isometric path_ in $X$.

A path $\gamma$ is a _geodesic_ if it is locally isometric, i.e., for every
$t\in[0,1]$ there is an $\varepsilon>0$ such that the subpath $\gamma|_{J}$ on
the interval $J=[t-\varepsilon,t+\varepsilon]\cap[0,1]$ is isometric. A path
with $\gamma(0)=\gamma(1)$ is called a _loop_ (or a _closed path_). When we
say that a loop is a geodesic, we mean it is geodesic as a path and it is also
locally isometric around its base point, i.e.
$\gamma|_{[1-\varepsilon,1]\cup[0,\varepsilon]}$ is isometric for some
$\varepsilon>0$.

Alternatively, one can consider any path-connected compact metric space $X$
and then define the shortest path distance. For $x,y\in X$, the _shortest path
distance_ from $x$ to $y$ is defined as the infimum of the lengths of all
$(x,y)$-paths in $X$. If any two points in $X$ are joined by a path of finite
length, then the shortest path distance gives the same topology on $X$. By the
Arzelà-Ascola theorem (see e.g. [7]), compactness implies that any sequence of
$(x,y)$-paths contains a point-wise convergent subsequence, and that the limit
points determine an $(x,y)$-path. This implies that there is a path whose
length is equal to the infimum of all path lengths. Hence, for this metric,
which is also known as the _intrinsic metric_ , $X$ is a geodesic space.

If $X$ is a geodesic space, each of its points appears on a geodesic. But some
points only appear as the end-points of isometric paths in $X$ and cannot
appear as interior points of those. Such points are called _corners_. All
other points appear as internal points on geodesics in $X$ and are said to be
_regular points_ in $X$. It is obvious that regular points are dense in $X$.
On the other hand, the set of corners can also be very rich. It may contain
the whole boundary component, but in the interior of $X$, it is totally path-
disconnected in the sense that every path containing only corners is either
trivial (a single point), or is contained in $\partial X$.

Common examples of geodesic spaces include any connected cell complex endowed
with the intrinsic metric. If a geodesic space is homeomorphic to a
1-dimensional cell complex (graph), then we say that it is a _metric graph_.
If $G$ is a graph and $w:E(G)\to\mathbb{R}_{+}$ is a function specifying the
length of each edge, we define the _metric graph_ $X(G,w)$ corresponding to
$G$ and $w$ as the metric graph $G$ in which each edge $e$ is represented by a
real interval of length $w(e)$.

We refer to [7] and [8] for a thorough treatment of geodesic spaces.

##  3 Game of Cops and Robber on geodesic spaces

### Rules of the game

Let $X$ be a compact geodesic space endowed with intrinsic metric $d$, and let
$k\geq 1$ be an integer. A _Game of Cops and Robber_ on the _game space_ $X$
with $k$ cops is a two-person game with complete information defined as
follows. The first player controls an avatar, who is positioned at a point
$r\in X$ and whom we call the _robber_. The second player controls a set of
$k$ _cops_ $C_{1},\dots,C_{k}$ that are also positioned in $X$. It is allowed
that different cops occupy the same position in $X$. There are rules how the
game starts and how the players move, and the goal of the second player is to
come as close as possible to the robber (possibly catching him, i.e. one of
the cops to occupy the same point in $X$ as the robber). The details about
these rules are specified below.

A _position_ in a game with $k$ cops is a $(k+1)$-tuple
$(r,c_{1},\dots,c_{k})\in X^{k+1}$ enlisting the positions of the robber and
the cops. Instead of $(r,c_{1},\dots,c_{k})$ we also write $(r,c)$, where
$c=(c_{1},\dots,c_{k})\in X^{k}$. The game is defined by the following
parameters (in addition to the game space $X$ and $k$):

(I)

A rule that specifies the set of _admissible initial positions_ of the robber
and the cops. This is just a set of $(k+1)$-tuples, $\mathcal{Y}^{0}\subseteq
X^{k+1}$.

(S)

A set $\Sigma^{0}$ of _agility functions_ , each of which maps
$\mathbb{N}\to\mathbb{R}_{+}$.

The _standard game_ $\Gamma_{0}$ has $\mathcal{Y}^{0}=X^{k+1}$ and
$\Sigma^{0}$ contains all positive functions
$\tau:\mathbb{N}\to\mathbb{R}_{+}$ for which $\sum_{n\geq 1}\tau(n)=\infty$.
Throughout this paper we will stick with these assumptions unless stated
differently.

Given (I) and (S), the robber selects an initial position
$Y^{0}=(r^{0},c_{1}^{0},\dots,c_{k}^{0})\in\mathcal{Y}^{0}$ and selects his
agility $\tau\in\Sigma^{0}$. Then the game proceeds as a discrete game in
consecutive steps. Having made $n-1$ steps $(n\geq 1)$, the players are in
position $(r^{n-1},c_{1}^{n-1},\dots,c_{k}^{n-1})\in X^{k+1}$. The $n$th step
will have its duration determined by the agility: the move will last for time
$\tau(n)$, and each player can move with unit speed up to a distance at most
$\tau(n)$ from his current position. First, the robber moves to a point
$r^{n}\in X$ at distance at most $\tau(n)$ from its current position, i.e.
$d(r^{n-1},r^{n})\leq\tau(n)$. The destination $r^{n}$ is revealed to the
cops. Then each cop $C_{i}$ ($i\in[k]$) selects his new position $c_{i}^{n}$
at distance at most $\tau(n)$ from its current position, i.e.
$d(c_{i}^{n-1},c_{i}^{n})\leq\tau(n)$. The game stops if $c_{i}^{n}=r^{n}$ for
some $i\in[k]$. In that case, the _value of the game_ is 0 and we say that the
cops _have caught_ the robber. Otherwise the game proceeds with the next step.
If it never stops, the _value of the game_ is

$v=\inf_{n\geq 0}\min_{i\in[k]}d(r^{n},c_{i}^{n}).$ (1)

If the value is 0, we say that the _cops won_ the game; otherwise the _robber
wins_. Note that the cops can win even if they never catch the
robber.222Consider the afore-mentioned strategy of Besicovitch [5] for the
game of Lion and Man.

The traditional description of pursuit-evasion games starts by the cops first
choosing their position and then the robber choosing his. This setting is
actually equivalent to our standard game, since the cops can always move to
their desired initial positions during the beginning of the game.

We will also consider other variants of the game:

  * •

The _game $\Gamma(r,c)$ with the fixed initial position $(r,c)$_. Here we have
$\mathcal{Y}^{0}=\\{(r,c)\\}$.

  * •

The _game $\Gamma(\tau)$ with the fixed agility_ $\tau$, and its version where
also the initial position is fixed, $\Gamma(r,c,\tau)$. Here we have
$\Sigma^{0}=\\{\tau\\}$ (and $\mathcal{Y}^{0}=\\{(r,c)\\}$), and we allow that
$T=\sum_{n\geq 1}\tau(n)$ is either finite or infinite.

  * •

A _finite $N$-step game_ $\Gamma(N,\tau)$ and its version with the initial
position fixed, $\Gamma(r,c,N,\tau)$. The game stops after $N$ steps. Here,
only the first $N$ values of $\tau$ are important for the game, so we may
assume that $\tau:[N]\to\mathbb{R}^{+}$ or that $\tau(n)=0$ for $n>N$.

  * •

A _finite-time game_ $\Gamma(T)$ or $\Gamma(r,c,T)$ is a finite-step game,
where the constraint is not the number of steps but the total duration, i.e.,
the agility functions satisfy $\sum_{n\geq 1}\tau(n)=T$. Here $T$ is a
positive real number, the _duration of the game_. This version may be combined
with fixing the number of steps, $\Gamma(N,T)$ or even fixing the agility,
$\Gamma(N,\tau,T)$, where we ask $\sum_{n=1}^{N}\tau(n)=T$; additionally, we
can fix the initial position.

It will always be clear by the listed set of parameters which version of the
game we have in mind.

In general, we should also add the game space $X$ and the number $k$ of cops
among the parameters, but since this is almost always implicit from the
context, we usually omit them.

### Strategies and value of the game

The value of the game when played in $X$ is defined by (1). Note that the
strategy of a player depends not only on the current position but also on the
agility chosen by the robber at the very beginning. To formalize this
dependence, we introduce the notion of a strategy.

The strategy of the robber is first to select an initial position and agility.
This is a formal part of his strategy. The rest of his strategy and a strategy
of the cops may be defined via a game with a fixed initial position and fixed
agility, $\Gamma(r,c,\tau)$. Formally (and leaving out the initial choice of
the robber), a _strategy of the robber_ is a function $s:(r,c,\tau)\mapsto
r^{\prime}$, such that $d(r,r^{\prime})\leq\tau(1)$. This can be interpreted
as moving the robber from $r$ to $r^{\prime}$ along some geodesic of length
$d(r,r^{\prime})$. Then, each cop $C_{i}$ moves from his current position
$c_{i}$ to a point $c_{i}^{\prime}$ at distance at most $\tau(1)$ from
$c_{i}$. The choice of such destinations
$c^{\prime}=(c_{1}^{\prime},\dots,c_{k}^{\prime})$ constitutes a _strategy of
cops_. Formally, it is a function $q:(r^{\prime},c,\tau)\mapsto c^{\prime}$.
Performing the moves determined by both strategies gives the new game
$\Gamma(r^{\prime},c^{\prime},\delta\tau)$ with the fixed position and
agility, where $\delta\tau(n):=\tau(n+1)$ ($n\geq 1$).

Given the agility $\tau$ and strategies $s,q$ of the robber and the cops, we
denote by $v_{\tau}(s,q)$ the value of the game when it is played using these
strategies. Now we define the _guaranteed outcome_ for each of the players.
First for the robber:

$\overline{\mathop{{\hbox{\sc
Val}}}}_{R}(\tau)=\inf_{q}\sup_{s}v_{\tau}(s,q)\quad\textrm{and}\quad\overline{\mathop{{\hbox{\sc
Val}}}}_{R}=\sup_{\tau}\overline{\mathop{{\hbox{\sc Val}}}}_{R}(\tau).$

Similarly for the cops,

$\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(\tau)=\sup_{s}\inf_{q}v_{\tau}(s,q)\quad\textrm{and}\quad\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}=\sup_{\tau}\underline{\mathop{{\hbox{\sc Val}}}}_{\,C}(\tau).$

For each $\varepsilon>0$, there is $q$ such that for every $s$,
$v_{\tau}(s,q)<\overline{\mathop{{\hbox{\sc Val}}}}_{R}(\tau)+\varepsilon$.
This implies that

$\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(\tau)\leq\overline{\mathop{{\hbox{\sc
Val}}}}_{R}(\tau)\quad\textrm{and}\quad\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}\leq\overline{\mathop{{\hbox{\sc Val}}}}_{R}.$

If $\underline{\mathop{{\hbox{\sc Val}}}}_{\,C}=0$, then we say that _cops
win_ the game. If $\overline{\mathop{{\hbox{\sc Val}}}}_{R}>0$, then the
_robber wins_.

It is an interesting question whether it can happen that
$\underline{\mathop{{\hbox{\sc Val}}}}_{\,C}<\overline{\mathop{{\hbox{\sc
Val}}}}_{R}$ for some game space $X$ and some $k$. In particular, is it
possible that both players, the cops and the robber win the game? This
question was offered as the main open problem in the afore-mentioned work by
Bollobás et al. [5]. For our version of the game, we will answer this question
in the negative. Indeed, the subtleties of our definition will allow us to
make the conclusion that $\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}=\overline{\mathop{{\hbox{\sc Val}}}}_{R}$, see Theorem 12.

Since $X$ is compact, for every $\varepsilon>0$ there exists an integer $k$
such that $k$ cops can always achieve the value of the game be less than
$\varepsilon$. (Place the cops at the centers of open balls of radius
$\varepsilon$ that cover $X$. Then, no matter where the robber is, he will be
at distance less than $\varepsilon$ from one of the cops.) Hence, with the
growing number of cops, the value of the game tends to 0.

Given a game space $X$, let $k$ be the minimum integer such that $k$ cops win
the game on $X$. This minimum value will be denoted by $c(X)$ and called the
_cop number_ of $X$. If such a $k$ does not exist, then we set $c(X)=\infty$.
Similarly we define the _strong cop number_ $c_{1}(X)$ as the minimum $k$ such
that $k$ cops can always catch the robber.

### Examples:

1\. The $n$-ball. Let us consider the game with one cop on the $n$-dimensional
ball of radius $1$, $X=B^{n}=\\{x\in\mathbb{R}^{n}\mid\|x\|_{2}\leq 1\\}$.
This is the higher-dimensional analogue of the game of Man and Lion. It turns
out that the ball of any dimension has cop number 1, i.e., one cop can win the
game (although the robber can make sure he is never caught). In this game, the
cop can use a strategy from the Man and Lion game (the 2-dimensional version)
as follows. First, the cop moves to the center of the ball. From now on he
will make sure to always be at the line segment from the center to the current
position of the robber. By considering the 2-dimensional plane $\Pi$ through
the origin, containing the former and the new position of the robber, he can
keep this strategy and approach the robber using the 2-dimensional strategy in
$\Pi$ (in which the cop keeps the requirement to be on the line from the
center to the robber), thus approaching the robber and achieving infimum of
his distance to the robber to be 0.

Note that a slight modification of the described strategy of the cop can be
defined so that it only depends on the positions of the players and the
current step length, i.e., it does not need the whole information on agility.
It goes as follows: If the step duration is $t$ and the cop can reach a point
on the segment from the center to the robber, he moves to the point on this
segment that is closest to the robber. If he cannot reach the segment in the
current step, then he moves distance $t$ towards the center.

The above strategy shows that $c(B^{n})=1$. It can be shown that
$c_{1}(B^{n})=n$, see [10, 13].

2\. The $n$-sphere. The game with one cop played on the $n$-dimensional sphere
of radius $1$ in $\mathbb{R}^{n+1}$,
$S^{n}=\\{x\in\mathbb{R}^{n+1}\mid\|x\|_{2}=1\\}$ is somewhat different. Here
the robber may invoke the following strategy. Let $\tau_{\varepsilon}$ be the
agility in which each step has length $\varepsilon$. The robber can choose
this agility and select the initial position of the cop to be at the north
pole, while he positions himself at the south pole. At the first step, the
robber stays put. Then, the cop moves, and in the next step, the robber can
move to the point that is antipodal to the position of the cop. It is easy to
see that the minimum distance between the cop and the robber is never below
$\pi-\varepsilon$, so the value of the standard game is $\pi$ in this case.

Differential pursuit-evasion game on $S^{n}$ was studied by Satimov and
Kuchkarov [24], who proved that $n+1$ cops can catch the robber on $S^{n}$ and
that $n$ cops cannot catch him. Our version of the game has the same outcome,
i.e. $c_{1}(S^{n})=n+1$, see [13]. However, an interesting fact from [13] is
that two cops can win the game, i.e. $c(S^{n})=2$.

3\. The cylinder. Let $B$ be a game space (a compact geodesic space with
intrinsic metric $d$). The _cylinder over $B$_ is the geodesic space
$X=B\times I$, endowed with the product topology, where $I=[0,1]$ is a real
interval of length 1. We consider the $\ell_{p}$-metric $d_{p}$ for some
$p\geq 1$:

$d_{p}((a,s),(b,t))=\left(d(a,b)^{p}+|s-t|^{p}\right)^{1/p}.$

Clearly, $X$ is a geodesic space. For any number $k$ of cops, the value of the
game of Cops and Robber on $X$ is the same as on $B$ if $p>1$:
$\overline{\mathop{{\hbox{\sc Val}}}}_{R}(X)=\overline{\mathop{{\hbox{\sc
Val}}}}_{R}(B)$. To see this, let us consider any agility $\tau$ and for any
$\varepsilon>0$, consider a strategy $s_{0}$ of the robber in $B$ such that

$\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(B,\tau)=\sup_{s}\inf_{q}v_{\tau}(s,q)\leq\inf_{q}v_{\tau}(s_{0},q)+\varepsilon.$

The robber can use the same agility and the same strategy on $X$, if he always
stays in $B\approx B\times\\{0\\}$ and considers the cops’ positions as being
in $B$ by projecting them to the first coordinate. By using the strategy
$s_{0}$, he will be able to keep distance $v_{\tau}(s_{0},q)$ from the cops,
where $q$ is the projection of cops’ strategy to $B$. Since $\varepsilon$ is
arbitrarily small, this shows that $\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(B,\tau)\leq\underline{\mathop{{\hbox{\sc Val}}}}_{\,C}(X,\tau)$,
and since $\tau$ is arbitrary, it also implies that
$\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(B)\leq\underline{\mathop{{\hbox{\sc Val}}}}_{\,C}(X)$.

Similarly we see that $\overline{\mathop{{\hbox{\sc
Val}}}}_{R}(B)\geq\overline{\mathop{{\hbox{\sc Val}}}}_{R}(X)$. Here, the cops
will use a strategy in $B$ to get close to the robber in $B\approx
B\times\\{0\\}$. Once one of the cops is at distance less than $\varepsilon$
from the projection of the robber’s position onto $B$, then that cop follows
the moves of the robber in the $B$-coordinate and slowly increases its
$I$-coordinate with a constant slope, so that after making distance $t$, his
$I$-coordinate would have changed by 1, and the length $t$ of his path will be
at most $\varepsilon$ larger than the length $t_{0}$ of the projected path.
For instance, we can take $t$ large enough so that
$t-(t^{p}-1)^{1/p}<\varepsilon$. Such $t$ exists since $p>1$. It is easy to
see that in this way, the cop will come to a distance less than $2\varepsilon$
from the robber. Again, since $\varepsilon$ is arbitrarily small and $\tau$ is
arbitrary, we conclude that $\overline{\mathop{{\hbox{\sc
Val}}}}_{R}(B)\geq\overline{\mathop{{\hbox{\sc Val}}}}_{R}(X)$. Both
inequalities show that $\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(B)\leq\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(X)\leq\overline{\mathop{{\hbox{\sc
Val}}}}_{R}(X)\leq\overline{\mathop{{\hbox{\sc Val}}}}_{R}(B)$. Finally, our
Theorem 12 implies that

$\underline{\mathop{{\hbox{\sc Val}}}}_{\,C}(B)=\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(X)=\overline{\mathop{{\hbox{\sc
Val}}}}_{R}(X)=\overline{\mathop{{\hbox{\sc Val}}}}_{R}(B).$

The same result holds if instead of $X=B\times I$ we consider the product
$B\times T$, where $T$ is any metric graph homeomorphic to a tree.

##  4 Approximation with a finite game

The analysis of the game of cops and robber as defined in this article is
somewhat complicated due to the fact that the game may have infinitely many
steps and that the set of agility functions is not compact. However, the game
can be approximated by a finite game within an arbitrary precision. This
approximation result is described next.

Suppose that we fix an initial position $(r,c)\in X^{k+1}$, a positive integer
$N$ and an agility $\tau$. Then we can consider $N$ steps of the game, and let
$T=T_{N}(\tau)=\sum_{i=1}^{N}\tau(i)$ be the duration of the game during these
$N$ steps. We will use $\tau^{N}$ to denote the restriction of $\tau$ to the
first $N$ values since the rest of $\tau$ is not important for the finite
game. This means that we either view $\tau^{N}$ as a function
$[N]\to\mathbb{R}_{+}$ or as a function that has $\tau^{N}(n)=0$ for every
$n>N$. We also define $d(r,c)=\min\\{d(r,c_{i})\mid i\in[k]\\}$,
$d(c,c^{\prime})=\max\\{d(c_{i},c_{i}^{\prime})\mid i\in[k]\\}$, and
$d((r,c),(r^{\prime},c^{\prime}))=\max\\{d(r,r^{\prime}),d(c,c^{\prime})\\}$.
Given $\tau$, we define its _shift_ $\tau_{1}=\delta\tau$ by the rule
$\tau_{1}(i)=\tau(i+1)$ for $i\geq 1$.

For each game $\Gamma(*)$ (where $(*)$ is the defining set of parameters), we
will define the value of the game $\mathop{{\hbox{\sc Val}}}(\Gamma(*))$,
which we will abbreviate by writing simply $\mathop{{\hbox{\sc Val}}}(*)$.

Given the finite game $\Gamma(r,c,N,\tau^{N})$ with initial position $(r,c)$,
its _value_ can be defined recursively as follows:

$\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})=\left\\{\begin{array}[]{ll}d(r,c),&\hbox{if
$N=0$;}\\\\[4.2679pt] \max\limits_{\begin{subarray}{c}r^{\prime}\\\
d(r,r^{\prime})\leq\tau(1)\end{subarray}}~{}~{}\min\limits_{\begin{subarray}{c}c^{\prime}\\\
d(c,c^{\prime})\leq\tau(1)\end{subarray}}\mathop{{\hbox{\sc
Val}}}(r^{\prime},c^{\prime},N-1,\tau_{1}^{N-1}),&\hbox{otherwise.}\end{array}\right.$
(2)

The reader will realize that we used maximum and minimum (instead of supremum
and infimum) in the definition; this is justified since $X$ is compact and the
value of the game is continuous. This fact is formally stated and proved as
Lemma 3 below. Definition (2) then shows that both players have optimal
strategies that assure them achieving the value $\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})$ if they stick with these strategies. Let
$s_{0}:(r,c,N,\tau^{N})\mapsto r^{\prime}$, where $r^{\prime}$ is the position
of the robber for which the maximum in (2) is attained; and for each
$r^{\prime}$, let $q_{0}:(r^{\prime},c,N,\tau^{N})\mapsto c^{\prime}$, where
$c^{\prime}$ is a cops’ position at which the minimum in (2) is attained. Note
that for any strategies $s$ and $q$ of the robber and the cops (respectively),
we have:

$v_{\tau}(s,q_{0})\leq v_{\tau}(s_{0},q_{0})=\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})\leq v_{\tau}(s_{0},q).$

There is another small detail about the definition of the value
$\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})$ in (2). Namely, (2) defines the
value as the distance $d(r^{N},c^{N})$ at the end of the game, while the
definition of $v_{\tau}(s,q)$ also considers intermediate distances. This
means that the definition should have been introduced as

$\mathop{{\hbox{\sc
Val}}}\nolimits^{\prime}(r,c,N,\tau^{N})=\left\\{\begin{array}[]{ll}d(r,c),&\hbox{if
$N=0$;}\\\\[4.2679pt] \min\bigl{\\{}d(r,c),\
\max\limits_{r^{\prime}}~{}\min\limits_{c^{\prime}}~{}\mathop{{\hbox{\sc
Val}}}(r^{\prime},c^{\prime},N-1,\tau_{1}^{N-1})\bigr{\\}},&\hbox{otherwise}\end{array}\right.$
(3)

where the maximum and the minimum are taken over the same nearby points
$r^{\prime}$ and $c^{\prime}$ as in (2). However, this definition is
equivalent as shown below.

######  Lemma 1.

For any finite-step game $\Gamma(r,c,N,\tau^{N})$, we have $\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})=\mathop{{\hbox{\sc Val}}}^{\prime}(r,c,N,\tau^{N})$.

###### Proof.

The proof is by induction on the number of steps. By using the induction
hypothesis, the only way that $\mathop{{\hbox{\sc
Val}}}^{\prime}\neq\mathop{{\hbox{\sc Val}}}$ is that
$d(r,c)<\mathop{{\hbox{\sc Val}}}(r^{\prime},c^{\prime},N-1,\tau_{1}^{N-1})$.
However, if that were the case, the cop at distance $d(r,c)$ from the robber
could just follow the robber throughout the game, and achieve the value
$d(r,c)$, which is a contradiction to the assumption that
$d(r,c)<\mathop{{\hbox{\sc Val}}}(r^{\prime},c^{\prime},N-1,\tau_{1}^{N-1})$.
∎

A corollary of Lemma 1 is that the value of the game is non-increasing in
terms of its number of steps, which we state formally below.

######  Lemma 2.

For any agility $\tau$, initial position $(r,c)$ and positive integers $N\leq
M$, we have

$\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})\geq\mathop{{\hbox{\sc
Val}}}(r,c,M,\tau^{M}).$

For our later use we now define the value of a (non-finite) game with given
agility:

$\mathop{{\hbox{\sc Val}}}(r,c,\tau)=\lim_{N\to\infty}\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N}).$ (4)

The limit exists since the value of the game decreases with $N$.

Our goal is to approximate the game with finite games, and we use the
following as the definition what it means to approximate the game. The game
$\Gamma(r,c,\tau)$ is _$\varepsilon$ -approximated_ with a finite game
$\Gamma(r,c,N,\tau^{N})$ if $\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})-\mathop{{\hbox{\sc Val}}}(r,c,\tau)<\varepsilon$. Note
that by Lemma 2, the difference $\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})-\mathop{{\hbox{\sc Val}}}(r,c,\tau)$ cannot be
negative.

We are ready to proceed with a proof that the game value is continuous.

######  Lemma 3.

The value $\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})$ of a finite game is
continuous in terms of its initial position $(r,c)$ and $\tau^{N}$. More
precisely, if $d((r,c),(r^{\prime},c^{\prime}))\leq\delta$, then

$\left|\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})-\mathop{{\hbox{\sc
Val}}}(r^{\prime},c^{\prime},N,\tau^{N})\right|\leq 2\delta$

and if
$\|\tau^{N}-{\tau^{\prime}}^{N}\|_{1}:=\sum_{n=1}^{N}|\tau(n)-\tau^{\prime}(n)|\leq\varepsilon$,
then

$\left|\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})-\mathop{{\hbox{\sc
Val}}}(r,c,N,{\tau^{\prime}}^{N})\right|\leq 2\varepsilon.$

###### Proof.

Suppose that $d((r,c),(r^{\prime},c^{\prime}))\leq\delta$. Suppose that the
starting position is $(r^{\prime},c^{\prime})$. We say that the robber
_mimics_ the game strategy for the initial position $(r,c)$ if he plays so
that he is always within distance $\delta$ from the position he would have in
the game when starting with $(r,c)$. The first move is now obvious, the robber
would move to a point $x$ at distance at most $\tau(1)$ from $r$. Since
$d(r^{\prime},r)\leq\delta$, he can move to a point $r^{\prime\prime}$ that is
within distance $\delta$ from $x$. Now the cops move to their new positions
$c_{i}^{\prime\prime}$. Since $c_{i}^{\prime}$ was within distance $\delta$
from $c_{i}$, there is a point $y_{i}$ at distance at most $\delta$ from
$c_{i}^{\prime\prime}$ and at distance at most $\tau(1)$ from
$c_{i}^{\prime}$. The robber considers the position $(x,y_{1},\dots,y_{k})$ as
the imaginary position in this step and uses the strategy for the game
$\Gamma(r,c,N,\tau^{N})$ game as being at this position in the current step.
This shows that the distance between $x$ and $y$ is all the time at least
$\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})$, and thus

$d(r^{\prime\prime},c^{\prime\prime})\geq\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})-2\delta.$

This implies that $\mathop{{\hbox{\sc
Val}}}(r^{\prime},c^{\prime},N,\tau^{N})\geq\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})-2\delta$. To obtain the inequality in the other way,
just switch the roles of $(r,c)$ and $(r^{\prime},c^{\prime})$.

Similarly we prove continuity with respect to $\tau$. Here we assume that
$\sum_{n=1}^{N}|\tau(n)-\tau^{\prime}(n)|\leq\varepsilon$. In the game
$\Gamma(r,c,N,{\tau^{\prime}}^{N})$, either player can mimic his strategy for
$\Gamma(r,c,N,\tau^{N})$, and all the time being at most $\varepsilon$ away
from the imaginary positions in the gameplay of $\Gamma(r,c,N,\tau^{N})$. This
implies the stated inequality. ∎

Having defined the value of a finite-step game by (2) (or, equivalently, by
(3)), let us fix $T>0$ and consider all finite-time games $\Gamma(r,c,T)$ with
duration $T$. Then we define

$\mathop{{\hbox{\sc Val}}}(r,c,T)=\sup_{\begin{subarray}{c}N,\tau\\\
T_{N}(\tau)=T\end{subarray}}\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})$ (5)

and for the standard game $\Gamma(r,c)$, we define:

$\mathop{{\hbox{\sc Val}}}(r,c)=\inf_{T\to\infty}\mathop{{\hbox{\sc
Val}}}(r,c,T).$ (6)

Let us observe that by Lemma 2, $\mathop{{\hbox{\sc Val}}}(r,c,T)$ is non-
increasing with $T$, thus the infimum in (6) can also be replaced by a limit
when $T\to\infty$. Instead of (6), we could as well have used (4) since we
have

$\mathop{{\hbox{\sc Val}}}(r,c)=\sup_{\tau}\mathop{{\hbox{\sc
Val}}}(r,c,\tau).$

##  5 Choice of agility functions

It is helpful to know that the “approximately-best” agility (which is
initially chosen by the robber) may be assumed to be decreasing. This is an
easy consequence of the fact that by subdividing a step of duration $t$ into
two or more steps of the same total duration will not decrease the value of
the game. Formally this is settled by the following result.

Let $\tau$ be an agility, let $0\leq\alpha\leq 1$ and $i\geq 1$. Let
$\sigma_{i}^{\alpha}\tau$ be the agility defined by the rule:

$\sigma_{i}^{\alpha}\tau(j)=\left\\{\begin{array}[]{ll}\tau(j),&\hbox{if
$1\leq j<i$;}\\\ \alpha\tau(i),&\hbox{if $j=i$;}\\\
(1-\alpha)\tau(i),&\hbox{if $j=i+1$;}\\\ \tau(j-1),&\hbox{if $j\geq
i+2$.}\end{array}\right.$ (7)

We say that the agility $\sigma_{i}^{\alpha}\tau$ has been obtained from
$\tau$ by an _elementary subdivision_ of the $i$th step. Agility
$\tau^{\prime}$ is a _subdivision_ of $\tau$ if it can be obtained from $\tau$
by a series of elementary subdivisions. Here we allow infinitely many
elementary subdivisions, but it is requested that each step of $\tau$ is
subdivided into finitely many substeps in order to obtain $\tau^{\prime}$. We
write $\tau^{\prime}\preceq\tau$ if $\tau^{\prime}$ is a subdivision of
$\tau$.

For further reference we state the following easy observation, whose proof is
left to the reader.

######  Lemma 4.

Any two agility functions have a common subdivision.

The following lemma shows that using $\tau^{\prime}$ instead of $\tau$ goes to
the favour of the robber. As a consequence, we may assume that the robber
always chooses a decreasing agility.

######  Lemma 5.

Suppose that $\tau^{\prime}$ is a subdivision of an agility $\tau$. Then

$\mathop{{\hbox{\sc Val}}}(r,c,\tau)\leq\mathop{{\hbox{\sc
Val}}}(r,c,\tau^{\prime}).$

###### Proof.

It suffices to prove the result for finite-step games, and for each such game
$\Gamma(r,c,N,\tau^{N})$, it suffices to prove that an elementary subdivision
does not increase the value of the game, i.e.

$\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})\leq\mathop{{\hbox{\sc
Val}}}(r,c,N+1,\sigma_{i}^{\alpha}\tau^{N+1}).$

To see this, consider steps $i$ and $i+1$ of the game with the subdivided
agility. The robber can just follow the optimal strategy of the $i$th step
from the original game $\Gamma(r,c,N,\tau^{N})$ and move to the desired
position in two steps. It is easy to see that this cannot give him smaller
value of the game. ∎

######  Lemma 6.

For every initial position $(r,c)$ and every $\varepsilon>0$, there is an
integer $N$ and an agility $\tau^{N}$ such that for any initial position
$(r,c)$ we have:

$\mathop{{\hbox{\sc Val}}}(r,c)-\varepsilon<\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})<\mathop{{\hbox{\sc Val}}}(r,c)+\varepsilon.$

###### Proof.

Take $T$ large enough so that $\mathop{{\hbox{\sc
Val}}}(r,c,T)\leq\mathop{{\hbox{\sc Val}}}(r,c)+\varepsilon$ and then choose
$N,\tau^{N}$ so that $T_{N}(\tau)=T$ and $\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})\geq\mathop{{\hbox{\sc Val}}}(r,c,T)-\varepsilon$. This
implies that $\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})\geq\mathop{{\hbox{\sc
Val}}}(r,c,T)-\varepsilon\geq\mathop{{\hbox{\sc Val}}}(r,c)-\varepsilon$ and
$\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})\leq\mathop{{\hbox{\sc
Val}}}(r,c,T)\leq\mathop{{\hbox{\sc Val}}}(r,c)+\varepsilon$. ∎

######  Corollary 7.

For every $\varepsilon>0$ and $T>0$, there exists a finite game with $N$ steps
and finite agility $\tau^{N}$ with $T_{N}(\tau)\geq T$ such that for every
initial position $(r,c)$, we have

$\mathop{{\hbox{\sc Val}}}(r,c)-\varepsilon<\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})<\mathop{{\hbox{\sc Val}}}(r,c)+\varepsilon.$

###### Proof.

The goal is to show that there are $N$ and $\tau^{N}$ that approximate the
game for any initial position. We will say that $N,\tau^{N}$ give
_$\varepsilon$ -approximation_ for $(r,c)$ if the inequalities of the
corollary hold for the initial position $(r,c)$. Since $X$ and hence also
$X^{k+1}$ is compact, there is a finite set $Y$ of initial positions such that
any other initial position is within distance $\varepsilon/4$ from one of the
positions in $Y$. For each $(r,c)\in Y$, there are $N$ and $\tau^{N}$ that
give $\varepsilon/2$-approximation. By Lemma 4 there is a common subdivision
of all such agility functions $\tau^{N}$. Since by subdividing the agility,
the value only increases (Lemma 5), we may assume that the same pair
$N,\tau^{N}$ $\varepsilon/2$-approximates every initial position $(r,c)\in Y$.
Since any other position is at distance at most $\varepsilon/4$ from $Y$,
Lemma 3 implies that the finite game with $N,\tau^{N}$
$\varepsilon$-approximates every initial position. ∎

Corollary 7 combined with Lemma 3 implies that the value $\mathop{{\hbox{\sc
Val}}}(r,c)$ of any Cops and Robber game is a continuous function, depending
on the initial position. This in particular shows that the set of cop-winning
initial positions is closed.

The use of agility functions is the main technical reason that makes the game
“non-compact”. Usually, there will be no optimal agility since the set of all
agility functions is not closed. However, we can make some general
observations that will enable us to use certain assumptions about “near-
optimal” agility.

We say that $\tau$ is _decreasing_ if $\tau(n+1)<\tau(n)$ for every $n\geq 1$.
It is easy to see by using induction that for every $\tau$ there is a
decreasing agility $\tau^{\prime}$ such that $\tau^{\prime}\preceq\tau$. The
following lemma shows that using $\tau^{\prime}$ instead of $\tau$ goes to the
favour of the robber, and therefore, we may assume that the robber always
chooses a decreasing agility.

For each agility $\tau\in\Sigma^{0}$, there is a decreasing agility
$\tau^{\prime}\in\Sigma^{0}$ that is a subdivision of $\tau$. The following
statement enables us to restrict our attention to decreasing agility functions

######  Lemma 8.

Suppose that $\tau\in\Sigma^{0}$ is an agility function and that
$\tau^{\prime}$ is a subdivision of $\tau$ that is decreasing.

(a) If $s:X^{k+1}\to X$ is a strategy of the robber with agility function
$\tau$, then there is a strategy $s^{\prime}:X^{k+1}\to X$ for agility
$\tau^{\prime}$ such that

$\inf_{q^{\prime}}v_{\tau^{\prime}}(s^{\prime},q^{\prime})\geq\inf_{q}v_{\tau}(s,q),$
(8)

where $q$ and $q^{\prime}$ in both infima run over all strategies of the cops
with agility $\tau$ and $\tau^{\prime}$, respectively.

(b) For any position $(r,c)$, $\mathop{{\hbox{\sc
Val}}}(r,c,\tau^{\prime})\geq\mathop{{\hbox{\sc Val}}}(r,c,\tau)$.

###### Proof.

(a) For the subdivided $n$th step of $\tau$, the agility $\tau^{\prime}$
provides a finite number of steps, whose total duration is equal to $\tau(n)$.
If the strategy $s$ tells the robber to move from position $r$ to
$r^{\prime}$, the robber can do the same with subdivided steps, and his
strategy $s^{\prime}$ will move from $r$ through all substeps to $r^{\prime}$.
Formally, there could have been a problem with this if at some later substep
would need to make the same decision. But since $\tau^{\prime}$ is decreasing,
the strategy for the same position will have smaller values in the agility
function, so any later substeps can use different strategy values.

To prove (8), we just argue that if the robber, when using strategy $s$, is
able to keep distance $v$ from the cops for any cops’ strategy $q$, he is also
able to keep the same distance by using his strategy $s^{\prime}$. Suppose
not. Then the cops have a strategy $q^{\prime}$ achieving better outcome. They
can mimic that strategy under $\tau$. If they gain better distance in a
substep, they can keep that distance by following the robber.

(b) This is an immediate corollary of the definition (4) of
$\mathop{{\hbox{\sc Val}}}(r,c,\tau)$ and of part (a) of this lemma. ∎

##  6 Volatile games

Suppose that we have nonnegative real numbers $(\varepsilon_{n})_{n\geq 0}$
and that two players play the game of cops and robber in $X$. Suppose that
after completing each step $n$ of the game ($n\geq 0$), an _adversary_ changes
the positions of the robber and of the cops by moving them to points that are
at most $\varepsilon_{n}$ away from their current position. Then we say that
the players play a _volatile game_ with _perturbation
$(\varepsilon_{n})_{n\geq 0}$_.

Lemma 3 can be interpreted as making a small change in the position before
making step 1 (which is “after making step 0”), thus it corresponds to a
volatile game where $\varepsilon_{0}=\varepsilon$ and $\varepsilon_{n}=0$ for
$n\geq 1$. For a general finite-step volatile game
$\Gamma(r,c,N,\tau^{N},(\varepsilon_{n})_{n\geq 0})$ we define the guaranteed
value for the robber as the minimum distance from the cops over all possible
strategies, when the adversary “helps the cops” as much as he can. This can be
defined recursively in the same way as in (2):

$\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(r,c,N,\tau^{N},(\varepsilon_{n})_{n\geq
0})=\left\\{\begin{array}[]{ll}\max\\{d(r,c)-2\varepsilon_{0},0\\},&\hbox{if
$N=0$;}\\\\[4.2679pt]
\min\limits_{r^{\prime},c^{\prime}}\,\max\limits_{r^{\prime\prime}}\,\min\limits_{c^{\prime\prime}}\,\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(r^{\prime\prime},c^{\prime\prime},N-1,\tau_{1}^{N-1},(\varepsilon^{\prime}_{n})_{n\geq
0})),&\hbox{otherwise;}\end{array}\right.$ (9)

where $\varepsilon^{\prime}_{n}=\varepsilon_{n+1}$ for $n\geq 0$ and the
minima and the maximum are taken over all
$r^{\prime},c^{\prime},r^{\prime\prime},c^{\prime\prime}$ for which
$d(r,r^{\prime})\leq\varepsilon_{0}$,
$d(c_{i},c^{\prime}_{i})\leq\varepsilon_{0}$,
$d(r^{\prime},r^{\prime\prime})\leq\tau(1)$, and
$d(c^{\prime}_{i},c^{\prime\prime}_{i})\leq\tau(1)$ ($i\in[k]$). In the
definition (the case $N=0$) we have used the fact that at the last step of the
game, the adversary can move the robber and its closest cop towards each other
by the distance of maximum allowed perturbation in this step. For the
recursive step we also used the possibility of the worst perturbation of the
positions made by the adversary.

Similarly, we define the guaranteed value for the cops as the minimum distance
from the robber over all possible strategies. This can be defined recursively
in the same way as in (9):

$\overline{\mathop{{\hbox{\sc
Val}}}}_{R}(r,c,N,\tau^{N},(\varepsilon_{n})_{n\geq
0})=\left\\{\begin{array}[]{ll}d(r,c),&\hbox{if $N=0$;}\\\\[4.2679pt]
\max\limits_{r^{\prime},c^{\prime}}\,\max\limits_{r^{\prime\prime}}\,\min\limits_{c^{\prime\prime}}\,\overline{\mathop{{\hbox{\sc
Val}}}}_{R}(r^{\prime\prime},c^{\prime\prime},N-1,\tau_{1}^{N-1},(\varepsilon^{\prime}_{n})_{n\geq
0})),&\hbox{otherwise.}\end{array}\right.$ (10)

The difference here is that we have estimated the worst way for the cops when
the adversary will try to “help the robber”.

Clearly, $\underline{\mathop{{\hbox{\sc Val}}}}_{\,C}$ and
$\overline{\mathop{{\hbox{\sc Val}}}}_{R}$ for volatile games need not be the
same, and it may also happen that $\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}>\overline{\mathop{{\hbox{\sc Val}}}}_{R}$. However, the two
values cannot be too far from each other as we prove next.

######  Lemma 9.

Let $\Gamma(r,c,N,\tau^{N})$ be a finite-step game and let
$\Gamma(r,c,N,\tau^{N},(\varepsilon_{n})_{n\geq 0})$ be a volatile version.
Set $\delta_{n}=\sum_{i=0}^{n}\varepsilon_{i}$. Then

$\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(r,c,N,\tau^{N},(\varepsilon_{n})_{n\geq
0})\geq\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})-2\delta_{N}$

and

$\overline{\mathop{{\hbox{\sc
Val}}}}_{R}\left(r,c,N,\tau^{N},(\varepsilon_{n})_{n\geq
0}\right)\leq\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})+2\delta_{N-1}.$

###### Proof.

The proof is not complicated, but requires thoughtful description. We will
only show the first inequality. Here it suffices to describe a strategy of the
robber such that no matter how the cops play, the final result will in the
worst case be close to the value $\mathop{{\hbox{\sc Val}}}(r,c,N,\tau^{N})$
of the finite game.

Let $s_{0}$ be the optimal strategy for the game $\Gamma(r,c,N,\tau^{N})$. It
suffices to prove by induction on $N$ that the robber can stay “close” to the
gameplay in the unperturbed game in which he uses strategy $s_{0}$ and the
cops use some strategy $q$ since in that gameplay the distance between the
cops and the robber will always be at least $\mathop{{\hbox{\sc
Val}}}(r,c,N,\tau^{N})$. By “close” we mean that his position and the position
of each cop after $n$ steps is at most $\delta_{n}$ away from a position in
the usual gameplay with the robber using strategy $s_{0}$.

When $N=0$, this is clear. If $N>0$, use the induction hypothesis to conclude
that after $N-1$ steps, we are $\delta_{N-1}$-close to a position
$(r^{N-1},c^{N-1})$ of the unperturbed gameplay. By mimicing the last step of
the game, the players can come to within the distance $\delta_{N-1}$ from the
position $(r^{N},c^{N})$ in the optimal gameplay. Finally, the adversary can
move each player up to distance $\varepsilon_{N}$ further away from that
position. Since $\delta_{N-1}+\varepsilon_{N}=\delta_{N}$, players could be at
most $2\delta_{N}$ closer than in the optimal gameplay performed by the
robber. This completes the proof. ∎

##  7 Limits of strategies

The somewhat technical definition of our Cops and Robber games using agility
functions enables us to prove that each game $\Gamma(r,c)$ or
$\Gamma(r,c,\tau)$ can be approximated by finite discrete games of the form
$\Gamma(r,c,T_{i},\tau)$, where $T_{i}$ is an increasing sequence of positive
real numbers tending to infinity. When $\tau$ is fixed, we can equivalently
approximate $\Gamma(r,c,\tau)$ with finite-step games
$\Gamma(r,c,N_{i},\tau^{N_{i}})$, where $0<N_{1}<N_{2}<N_{3}<\cdots$ is a
sequence of positive integers tending to infinity. However, strategies are not
continuous functions, so there is an obvious question if one can define a
limiting strategy, knowing optimal strategies for finite games that are
$\varepsilon$-approximations with $\varepsilon\to 0$. This question is our
goal in this section. Answering what are the limits of strategies will also
yield our final min-max theorem.

Suppose that $\tau$ is an agility that is decreasing. Let
$0<T_{1}<T_{2}<\cdots$ be an increasing sequence tending to infinity. For each
$i$, let $N_{i}$ be the smallest integer such that
$T(N_{i}):=\sum_{n=1}^{N_{i}}\tau(n)\geq T_{i}$. If we start instead with an
increasing sequence of positive integers tending to infinity,
$N_{1}<N_{2}<N_{3}<\cdots$, we can define $T_{i}=T(N_{i})$ and then proceed as
we would with the sequence $(T_{i})_{i\geq 1}$. We will also use, with a fixed
value of $\varepsilon$, the following decreasing sequence:
$\varepsilon_{i}:=2^{-i-1}\varepsilon$ ($i\geq 0$). Note that $\sum_{i\geq
0}\varepsilon_{i}=\varepsilon$.

Let us recall that by Corollary 7, for every $\varepsilon>0$ and every agility
$\tau$, there is $T=T(\varepsilon)$ such that $\Gamma(r,c,\tau)$ is
$\varepsilon$-approximated with the finite game $\Gamma(r,c,T,\tau)$ for every
initial position $(r,c)$. Let us now choose $T_{i}$ ($i\geq 1$) so that
$\Gamma(r,c,\tau)$ is $\varepsilon_{i}$-approximated with the finite game
$\Gamma(r,c,T_{i},\tau)=\Gamma(r,c,N_{i},\tau^{N_{i}})$. For each $i\geq 1$,
let $s_{i}$ and $q_{i}$ be optimal strategies of the robber and the cops
(respectively) for the finite game $\Gamma(r,c,N_{i},\tau^{N_{i}})$.

We now define the notion of an $\varepsilon$-approximate limit of strategies
$(s_{i})_{i\geq 1}$ and $(q_{i})_{i\geq 1}$ for the game $\Gamma(r,c,\tau)$.
Since $\tau$ is decreasing, we can define the limiting strategies depending
only on the current step length $\tau(n)$, and this is defined first for
$n=1$, then for $n=2$, etc. Suppose that strategies have been defined for
steps $1,2,\dots,n-1$. Consider the next step, whose length is $t=\tau(n)$.
Consider a finite point-set $Y^{n}\subset X^{k+1}$ such that every point in
$X^{k+1}$ is at distance less than $\varepsilon_{n}$ from $Y^{n}$. For every
position $(r^{n},c^{n})\in Y^{n}$, each strategy $s_{i}$ ($i\geq 1$) gives the
new position $r_{i}^{n}$ of the robber that is at most $t$ away from $r^{n}$.
Since $X$ is compact, the sequence $(r_{i}^{n})_{i\geq 1}$ contains a
convergent subsequence with limit $r^{\prime}$, and $r^{\prime}$ is still at
most $t$ away from $r^{n}$. We say that this subsequence is _appropriate_ for
$(r^{n},c^{n})$ if, moreover, $d(r_{i}^{n},r^{\prime})<\varepsilon_{n}$ for
each $i\geq 1$. Since $Y^{n}$ is finite, there is a subsequence
$j_{1}^{n}<j_{2}^{n}<j_{3}^{n}<\dots$ of indices that is appropriate for all
points in $Y^{n}$. We will from now on, in all succeeding steps, only consider
this subsequence and its subsequences; so in particular, if $n>1$, then
$(j_{i}^{n})_{i\geq 1}$ is a subsequence of $(j_{i}^{n-1})_{i\geq 1}$. The
corresponding lengths of the finite games will also be denoted using
superscripts $n$, $N_{i}^{n}:=N_{j_{i}^{n}}$ ($i\geq 1$). The assignment
$s_{0}:(r^{n},c^{n},t)\mapsto r^{\prime}$ then defines the strategy of the
robber in step $n$ restricted to the positions in $Y^{n}$.

If a position $(r^{n},c^{n})$ is not in $Y^{n}$, then we find the closest
position, say $(a,b)\in Y^{n}$, and consider its strategy limit point
$r^{\prime}=s_{0}(a,b,t)$. Now, we first move the robber from $r^{n}$ to $a$
and then proceed towards $r^{\prime}$ using a geodesic from $a$ to
$r^{\prime}$. Of course, the total length we can make is $t$, and we may need
to stop before reaching $r^{\prime}$. Let $r^{\prime\prime}$ be the point
reached in this way, and we set $s_{0}:(r^{n},c^{n},t)\mapsto
r^{\prime\prime}$. Observe that we also have
$d(r^{\prime\prime},r^{\prime})\leq\varepsilon_{n}$. This defines the strategy
of the robber for the $n$th step.

Similarly we define a strategy $q_{0}:(r,c,t)\mapsto c^{\prime})$ for the cops
in the $n$th step of length $t$, again passing to a subsequence $(N_{i}^{n})$
of $(N_{i}^{n-1})$. We may assume that the same subsequence that was
appropriate for all $(r^{n},c^{n})\in Y^{n}$ for the robber is also
appropriate with respect to the cops’ positions, so we do not need to
introduce new notation.

By repeating the above process for each $n\geq 1$, we end up with strategies
$s_{0}$ and $q_{0}$ for the game $\Gamma(\tau)$, where $\tau$ is a fixed
decreasing agility. Note that there is some freedom in the process by taking
different converging subsequences, so these need not be unique. Any strategies
$s_{0}$ and $q_{0}$ obtained in this way are said to be _$\varepsilon$
-approximate limits of strategies_ $(s_{i})_{i\geq 1}$ and $(q_{i})_{i\geq 1}$
for the finite games $(\Gamma(r,c,N_{i},\tau^{N_{i}}))_{i\geq 1}$.

######  Lemma 10.

Let $\tau$ be a decreasing agility function and $(r^{0},c^{0})$ be a fixed
initial position for the game of cops and robber on $X$. Suppose that $s_{0}$
and $q_{0}$ are $\varepsilon$-approximate limits of optimal strategies for
finite games $\Gamma(r^{0},c^{0},N_{i},\tau^{N_{i}})$ with $N_{i}\to\infty$ as
$i\to\infty$. Then for arbitrary strategies, $s$ of the robber and $q$ of the
cops, for the game $\Gamma(r^{0},c^{0},\tau)$, we have

$v_{\tau}(s,q_{0})-4\varepsilon<v_{\tau}(s_{0},q_{0})<v_{\tau}(s_{0},q)+4\varepsilon.$

###### Proof.

We will give details only for the second inequality. The first one can be
proved in exactly the same way, using estimates on the positions of each of
the cops.

Suppose that the players start with position $(r^{0},c^{0})$ and then play the
game using agility $\tau$, where the robber uses the limit strategy $s_{0}$
and the cops use any strategy $q$. When defining $s_{0}$ as the
$\varepsilon$-approximate limit strategy in the $n$th step, we have considered
a finite point set $Y^{n}$ such that each point in $X^{k+1}$ was at distance
less than $\varepsilon_{n}$ from $Y^{n}$, and we considered a subsequence
$(N_{i}^{n})_{i\geq 1}$ of the (sub)sequence $(N_{i}^{n-1})_{i\geq 1}$ from
the previous step. For $N_{i}^{n}$, the optimal strategies of the finite games
$\Gamma(r^{0},c^{0},N_{i}^{n},\tau^{N_{i}^{n}})$ converge for each $(r,c,t)$
with $(r,c)\in Y^{n}$ and $t=\tau(n)$ to the point $r^{\prime}$ which we have
used when defining the strategy $s_{0}$.

We can interpret the gameplay as a volatile game, where the adversary first
moves the robber from where he would have ended using his optimal strategy to
the limiting value $r^{\prime}$. By our choice of subsequences, this moves the
robber at most $\varepsilon_{n}$ away in the $n$th step. Next, the adversary
moves both, the robber and the cops, each at most $\varepsilon_{n}$ away, by
placing them to the nearest position $(a,b)\in Y^{n}$. Thus, the first $n$
steps of the gameplay of _each_ finite game
$\Gamma(r^{0},c^{0},N_{i}^{n},\tau^{N_{i}^{n}})$ ($i\geq 1$) corresponds to a
volatile game with perturbations $(2\varepsilon_{n})_{n\geq 1}$. By Lemma 9,
the value $v_{\tau}(s_{0},q)$ of this gameplay is within $2\delta_{N_{i}^{n}}$
from $\mathop{{\hbox{\sc Val}}}(r^{0},c^{0},N_{i}^{N},\tau^{N_{i}^{n}})$,
where $\delta_{n}=\sum_{j=1}^{n}2\varepsilon_{j}<2\varepsilon$. This completes
the proof. ∎

Our final results are now immediate consequences of Lemma 10 when combined
with the definitions of $\underline{\mathop{{\hbox{\sc Val}}}}_{\,C}(\tau)$
and $\overline{\mathop{{\hbox{\sc Val}}}}_{R}(\tau)$. The lemma gives the min-
max theorem for $\Gamma(r,c,\tau)$, where $(r,c)$ is any initial position. If
the approximate strategies for different initial values in the same step $n$
were different, we can unify them so that they will be the same. Having done
this, we may assume that we have $\varepsilon$-approximate strategies for all
initial positions, forming the $\varepsilon$-approximate strategy for the game
$\Gamma(\tau)$. This gives the following result.

######  Corollary 11.

Suppose that $\tau$ is a decreasing agility function and that $s_{0}$ and
$q_{0}$ are $\varepsilon$-approximate limits of optimal strategies for finite
games $\Gamma(N_{i},\tau)$ with $N_{i}\to\infty$ as $i\to\infty$. Then

$\overline{\mathop{{\hbox{\sc Val}}}}_{R}(\tau)-\varepsilon\leq
v_{\tau}(s_{0},q_{0})\leq\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(\tau)+\varepsilon.$

Finally, taking $\varepsilon\to 0$, we get a min-max result.

######  Theorem 12.

For every decreasing agility $\tau$ we have $\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}(\tau)=\overline{\mathop{{\hbox{\sc Val}}}}_{R}(\tau)$.
Consequently, $\underline{\mathop{{\hbox{\sc
Val}}}}_{\,C}=\overline{\mathop{{\hbox{\sc Val}}}}_{R}$.

The above “min-max theorem” implies that for every $\varepsilon>0$ there are
$\varepsilon$-approximating strategies for both players, and if either one of
them uses his strategy, the other player cannot do more than $\varepsilon$
better than just using his own $\varepsilon$-approximating strategy.

## References

  * [1] Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen.  Best laid plans of lions and men.  In 33rd International Symposium on Computational Geometry, volume 77 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 6, 16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017.
  * [2] Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen.  Escaping an infinitude of lions.  Amer. Math. Monthly, 127(10):880–896, 2020.
  * [3] M. Aigner and M. Fromme.  A game of cops and robbers.  Discrete Applied Mathematics, 8(1):1 – 12, 1984.
  * [4] Thomas Andreae.  On a pursuit game played on graphs for which a minor is excluded.  J. Combin. Theory Ser. B, 41(1):37–47, 1986.
  * [5] B. Bollobás, I. Leader, and M. Walters.  Lion and man—can both win?  Israel J. Math., 189:267–286, 2012.
  * [6] Anthony Bonato and Richard J. Nowakowski.  The game of cops and robbers on graphs, volume 61 of Student Mathematical Library.  American Mathematical Society, Providence, RI, 2011.
  * [7] Dmitri Burago, Yuri Burago, and Sergei Ivanov.  A course in metric geometry, volume 33 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2001.
  * [8] Yuri Burago and David Shoenthal.  Metric geometry.  In New analytic and geometric methods in inverse problems, pages 3–50. Springer, Berlin, 2004.
  * [9] F. L. Chernous’ko.  A problem of evasion from many pursuers.  J. Appl. Math. Mech., 40:11–20, 1976.
  * [10] H. T. Croft.  ’Lion and man’: A postscript.  J. Lond. Math. Soc., 39:385–390, 1964.
  * [11] Massimiliano Ferrara, Gafurjan Ibragimov, Idham Arif Alias, and Mehdi Salimi.  Pursuit differential game of many pursuers with integral constraints on compact convex set.  Bull. Malays. Math. Sci. Soc., 43(4):2929–2950, 2020.
  * [12] P. Hagedorn and J. V. Breakwell.  A differential game with two pursuers and one evader.  J. Optim. Theory Appl., 18(1):15–29, 1976.  Differential game issue.
  * [13] Vesna Iršič and Bojan Mohar.  Cops and robber on balls and spheres in higher dimensions.  ArXiv e-prints, December 2021.
  * [14] Rufus Isaacs.  Differential games. A mathematical theory with applications to warfare and pursuit, control and optimization.  John Wiley & Sons, Inc., New York-London-Sydney, 1965.
  * [15] A. Yu. Levchenkov and A. G. Pashkov.  A game of optimal pursuit of one noninertial object by two inertial objects.  Prikl. Mat. Mekh., 49(4):536–547, 1985.
  * [16] Joseph Lewin.  Differential games.  Springer-Verlag London, Ltd., London, 1994.  Theory and methods for solving game problems with singular surfaces.
  * [17] J. E. Littlewood.  A mathematician’s miscellany.  Methuen & Co., Ltd., London, 1953.
  * [18] J. E. Littlewood.  Littlewood’s miscellany.  Cambridge University Press, Cambridge, 1986.  Edited and with a foreword by Béla Bollobás.
  * [19] Richard Nowakowski and Peter Winkler.  Vertex-to-vertex pursuit in a graph.  Discrete Mathematics, 43(2):235–239, 1983.
  * [20] A. G. Pashkov.  On a certain convergence game.  J. Appl. Math. Mech., 34:772–778, 1970.
  * [21] Leon A. Petrosjan.  Differential games of pursuit, volume 2 of Series on Optimization.  World Scientific Publishing Co., Inc., River Edge, NJ, 1993.  Translated from the Russian by J. M. Donetz and the author.
  * [22] B. N. Pshenichnyj.  Simple pursuit by several objects.  Kibernetika, 12(3):145–146, 1976.
  * [23] A Quilliot.  Jeux et pointes fixes sur les graphes.  Thèse de 3ème cycle, Université de Paris, VI:131–145, 1978\.
  * [24] N. Yu. Satimov and A. Sh. Kuchkarov.  On the solution of a model differential pursuit-evasion game on a sphere.  Uzb. Mat. Zh., 2000(1):45–50, 2000.
  * [25] Jiongmin Yong.  Differential games.  World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015.  A concise introduction.


# Light-wave coherent control of the insulator-to-metal transition in a
strongly correlated material

Eduardo B. Molinero<EMAIL_ADDRESS>_Instituto de Ciencia de Materiales
de Madrid, Consejo Superior de Investigaciones Científicas (ICMM-CSIC),
Madrid, Spain_ Rui E. F. Silva<EMAIL_ADDRESS><EMAIL_ADDRESS>_Instituto de Ciencia de Materiales de Madrid, Consejo Superior de
Investigaciones Científicas (ICMM-CSIC), Madrid, Spain_ _Max-Born-Institut,
Max Born Strasse 2A, D-12489 Berlin, Germany_

###### Abstract

The use of intense tailored light fields is the perfect tool to achieve
ultrafast control of electronic properties in quantum materials. Among them,
Mott insulators are materials in which strong electron-electron interactions
drive the material into an insulating phase. When shinning a Mott insulator
with a strong laser pulse, the electric field may induce the creation of
doublon-hole pairs, triggering an insulator-to-metal phase transition. In this
work, we take advantage of the threshold character of this insulator-to-metal
transition and we propose a pump-probe scheme that consists of a mid-infrared
laser pulse and a train of short pulses separated by half-period of the mid-
infrared with alternating phases. By varying the time-delay between the two
pulses and the internal carrier envelope phase of the short pulses, we achieve
control of the phase transition, which leaves its fingerprint at its high
harmonic spectrum.

The latest developments in laser science have unlocked the possibility to
engineer intense ultrashort pulses that are able to steer and control the
dynamics of electrons, both in atoms and molecules (Krausz and Ivanov, 2009)
as well as in solid state materials (Kruchinin  _et al._ , 2018). When the
light-matter interaction is comparable with the Coulomb potential created by
the nuclei, highly non-linear optical phenomena start to appear. In
particular, strong field ionization and high harmonic generation are the two
fundamental processes in strong field physics (Keldysh, 1965; Corkum, 1993;
Lewenstein  _et al._ , 1994; Ivanov  _et al._ , 2005) and have played a key
role in our understanding of ultrafast electron dynamics (Ivanov  _et al._ ,
2005; Smirnova  _et al._ , 2009; Lépine  _et al._ , 2014).

The rapid development of lightwave engineering allowed the emergence of
several laser techniques that are able to probe ultrafast dynamics at the
attosecond timescale, such as streaking (Constant  _et al._ , 1997; Hentschel
_et al._ , 2001; Itatani  _et al._ , 2002; Kaldun  _et al._ , 2016) and RABBIT
(reconstruction of attosecond beating by interference of two-photon
transitions) (Paul  _et al._ , 2001; Silva  _et al._ , 2012; Rivière  _et al._
, 2012; Gruson  _et al._ , 2016). Both techniques use a pump-probe setup, an
attosecond pulse train (RABBIT) or a single attosecond pulse (streaking) as
pump and an infrared pulse (attosecond pulse train) as a probe.

Recently, there has been an increasing effort to port the attosecond
techniques that were developed in the context of atoms and molecules to
phenomena that are relevant in the condensed phase (Kruchinin  _et al._ ,
2018; Ghimire and Reis, 2019). The discovery of high harmonic generation in
ZnO (Ghimire  _et al._ , 2011) triggered the use of high harmonic spectroscopy
in the condensed phase allowing for: the all-optical reconstruction of bands
(Vampa  _et al._ , 2015), the observation of Bloch oscillations (Schubert  _et
al._ , 2014; Ghimire  _et al._ , 2011), electron-hole dynamics (Vampa  _et
al._ , 2014; Hohenleutner  _et al._ , 2015; Yue and Gaarde, 2020), van-Hove
singularities (Uzan  _et al._ , 2020), topological phase transitions (Silva
_et al._ , 2019; Chacón  _et al._ , 2020; Baykusheva  _et al._ , 2021; Bai
_et al._ , 2021; Schmid  _et al._ , 2021) and dynamics in strongly correlated
materials (Silva  _et al._ , 2018; Bionta  _et al._ , 2021; Tancogne-Dejean
_et al._ , 2018; Murakami  _et al._ , 2018; Imai  _et al._ , 2020; Murakami
_et al._ , 2021; Shao  _et al._ , 2022; Orthodoxou  _et al._ , 2021; Zhu  _et
al._ , 2021).

In a strongly correlated material the formation of doublon-hole pairs under
the presence of a strong electric field has a threshold character (Oka, 2012).
Previous works (Mayer  _et al._ , 2015; Yamakawa  _et al._ , 2017; Mazza  _et
al._ , 2016) have shown that we can induce a dynamical phase transition on the
system by varying the field strength $F_{0}$ of the electric field (given a
fixed interaction parameter $U$). More precisely, the laser can break the
antiferromagnetic order of the Mott insulator by favoring the appearance of
doublon-hole pairs. The mechanism behind this phenomenon is analogous to that
present in strong field ionization in atoms. In fact, one could define an
adiabaticity parameter $\gamma_{K}$ which plays the same role as the Keldysh
parameter in atoms (Keldysh, 1965; Ivanov  _et al._ , 2005), this parameter is
defined as $\gamma_{K}=\hbar\omega_{L}/\xi F_{0}$ where $\xi$ is the
correlation length (Oka, 2012) and $\omega_{L}$ is the frequency of the laser.
In the _tunneling_ regime, $\gamma_{K}\ll 1$, an electron can tunnel through
the interaction repulsion over an distance $\sim\xi$ due to the presence of
the laser. Thus, a doublon-hole pair is formed, which leads to the melting of
the insulator state, see Fig. 1(a). However and due to its threshold
character, this will only happens if the field goes higher than a certain
value $F_{\text{th}}$ (Oka, 2012; Silva  _et al._ , 2018). In Mott-like
systems, this threshold is given by $F_{\text{th}}=\Delta/2e\xi$ where
$\Delta$ is the Mott gap and $\xi$ is the correlation length (Oka, 2012).

Figure 1: (a) Schematic representation of the tunneling phenomenon in the 1D
Fermi-Hubbard model. (b) Representation of the two different lasers. The red
line denotes the mid-IR laser while the blue line corresponds to the train of
short pulses with $\phi_{\text{CEP}}=0$. Lighter blue lines shows how a
$\pm\delta$ delay affects the train.

In this work, we propose the use of a pump-probe scheme, similar to the one
used in RABBIT, that consists of a femtosecond pulse train and a mid-infrared
pulse, see Fig. 1(b), and by taking advantage of the threshold character of
the insulator-to-metal transition to be able to control the insulator-to-metal
transition in a strongly correlated material.

## Results

We will focus on the one-dimensional Hubbard model and we will use parameters
to mimic $\mathrm{Sr_{2}CuO_{3}}$, see Methods for further details. The main
purpose of the present work is to show that one can take advantage of this
tunneling phenomenon, in order to acquire a coherent control over the
insulator-to-metal transition in a strongly correlated material.

As previoulsy mentioned, we will use two different lasers (in a pump-probe
scheme) and tune the time delay $\delta$ between them in order to obtain the
control. The first of them will consist on a mid-IR laser with frequency
$\omega_{\text{IR}}=32.92$ THz and an amplitude of $F_{0,\text{IR}}=5$ MV/cm.
The second laser will be a train made up of 4 short pulses (their total
duration is roughly $6$ fs) equally splitted. The time-delay between 2
consecutive short pulses is half-period of the mid-IR laser pulse and they
have alternating phases, in accordance to what is obtained by means of high
harmonic generation. The parameters for the short pulses are
$\omega_{\text{pul}}=5\omega_{\text{IR}}=164.6$ THz, having a central
frequency that corresponds to the 5th harmonic, and a amplitude of
$F_{0,\text{pul}}=8$ MV/cm. Both lasers are modulated by a $\cos^{2}$ envelope
(Joachain  _et al._ , 2009) as it can be appreciated in Fig. 1(b), see Methods
for further details. The threshold field (Oka, 2012) for
$\mathrm{Sr_{2}CuO_{3}}$ takes a value of $F_{\text{th}}=9.1$ MV/cm so neither
of the fields can surpass it on their own; only when the two amplitudes sum in
a coherent way, namely when the short pulses land right on the peaks of the
mid-IR, the electric field will break the threshold and thus, the phase
transition will take place. The specific delays in which this will occur will
heavily depend on carrier-envelope phase (CEP), denoted by
$\phi_{\text{CEP}},$ of the short pulses. For example, by looking at Fig. 1(b)
one can easily guess that for $\phi_{\text{CEP}}=0$, the two laser will sum
coherently at $\delta=0$. As a result, we can _control the phase transition_
by light-wave engineer of the two parameters $\delta$ and $\phi_{\text{CEP}}$.
It must be emphasized that these laser parameters are well within experimental
reach.

To characterize the insulator-to-metal transition, one must pay attention to
both charge and spin degrees of freedom. To do so, we will compute the
following observables in the Schrödinger picture. Firstly, the average number
of doublon-hole pairs

$D(t)=\frac{1}{L}\sum_{j}\left\langle
n_{j,\uparrow}n_{j,\downarrow}\right\rangle$ (1)

and secondly, the next-neighbour spin–spin correlation function

$\eta(t)=\frac{1}{L}\sum_{j}\left\langle\vec{S}_{j}\cdot\vec{S}_{j+1}\right\rangle,$
(2)

where $\vec{S}_{j}$ is the vector of spin matrices for spin $1/2$ and site
$j$.

At first, it may seems that predicting for which values of $\delta$ and
$\phi_{\text{CEP}}$ the phase transition takes place can be quite a task.
However, we can accomplish such thing by just computing the maximum production
rate $\Gamma$ of the doublon-hole pairs in _the tunneling regime_. Following
Ref. (Oka, 2012), we take the production rate as

$\Gamma=\exp\text{$\left(-\pi\frac{F_{\text{th}}}{\max|F(t)|}\right)$}.$ (3)

Therefore, only by knowing the shape of the laser and the threshold amplitude
(which depends solely on the material), we can do a very confident guess of
the non-equilibrium behaviour of the material. It must be noted that this
rough estimation is only valid when we are in the tunneling regime. By
calculating the adiabaticity parameter for both pulses separately, we found
that $\gamma_{K,\mathrm{pul}}=1.03$ and $\gamma_{K,\mathrm{IR}}=0.33$. The
mid-IR pulse is well in the tunneling regime and the train pulse is in the
frontier between multiphoton and tunneling regime. However, when calculating
$\gamma_{K,\mathrm{pul}}$ summing the two field strengths we get
$\gamma_{K,\mathrm{pul}}=0.63$, which is indeed in the tunneling regime.
Consequently, $\Gamma$ as defined in Eq. (3), for our laser parameters, can be
used as a good number indicating whether or not we are inducing an insulator-
to-metal transition.

Figure 2: Average number of doublon-hole pairs, $D\left(t\right)$, (a) and
next-neighbour spin–spin correlation function, $\eta\left(t\right)$, (b) as a
function of time and $\delta$, for different values of $\phi_{\mathrm{CEP}}$.
The values shown are convoluted with a normal distribution function with
$\sigma=1$ fs. The orange line shows the total production rate $\Gamma$
obtained for the corresponding delay. The CEP of the laser is shown inside
each figure.

To prove the above assumptions, we have performed several numerical
calculations. In Fig. 2(a) we can see that the profile of $D(t)$ coincides
almost perfectly with the prediction given by $\Gamma$. When the production
rate starts to increase, i.e., when the delay $\delta$ (and the
$\phi_{\text{CEP}}$) causes the field to fulfill $\max|F(t)|>F_{\text{th}}$,
doublon-hole pairs begin to appear due to the tunneling mechanism and so, the
insulator state breaks down, leaving the system in a photo-induced saturated
state (Oka and Aoki, 2008; Oka, 2012). On the other hand, when $\delta$ and
$\phi_{\text{CEP}}$ are such so that the field do not surpass the threshold,
the initial ground state is kept intact. The same trend can be appreciated for
$\eta(t)$, the antiferromagnetic order of the Mott state is lost when $\Gamma$
becomes maximum and is conserved in the opposite case (Fig. 2(b)). Despite the
simplicity of Eq. (3), it does capture the physics of the system in a
remarkable manner, predicting even abrupt changes in the phase of the system
(Fig. 2(a) and (b) corresponding to the case
$\phi_{\text{CEP}}=90\text{\textordmasculine}$). This resemblance between
$\Gamma$ and the physical observables reaffirms that the dynamics of the
system are heavily dominated by the tunneling mechanism.

The possibility of making accurate predictions along with the tunability of
the two parameters $\delta$ and $\phi_{\text{CEP}}$, is what gives us the
_control over the Mott transition_ as shown in Fig. 3, where we have included
$\Gamma$ alongside the phase diagram of the system for a range of $\delta$ and
$\phi_{\text{CEP}}$. Comparing Fig. 3(a) with (b), one can see the clear
correspondence between the theoretical prediction of the production rate and
the obtained phase. As stated previously, when the production rate reaches a
maximum, the system undergoes a phase transition if not, the system stays in
the Mott insulator state. Nevertheless, and in spite of the similarities
between the two quantities, they do not show exactly the same behavior. This
is because tunneling is not a deterministic process but rather a probabilistic
one; the electron is _not guaranteed_ to tunnel over the potential barrier.
Also, is worth noting the expected periodicity both in the delay and in the
CEP.

Figure 3: (a): Total production rate $\Gamma$. Phase diagrams of the
$D\left(t\right)$ (b) and $\eta\left(t\right)$ (c). Both these phase diagrams
are obtained as the mean value on a 30 fs period of time after the end of the
laser pulse.

However, measuring correlations in Mott-like systems is not an easy task (Dean
_et al._ , 2016). Therefore, if we want to engineer the phase transition it is
almost mandatory to find a more suitable figure of merit. Naturally, and since
we are generating optical charge excitations, this process must manifest
itself in the optical response of the system. Indeed, previous works have
shown that the insulator-to-metal transition induced by strong laser fields
leaves a fingerprint in the corresponding harmonic emission (Silva  _et al._ ,
2018; Orthodoxou  _et al._ , 2021). To compute the optical emission, we first
obtain the electric current operator (Essler  _et al._ , 2005)

$\hat{J}(t)=-\mathrm{i}ea\tau\sum_{j,\sigma}(e^{-\mathrm{i}\Phi(t)}c_{j,\sigma}^{\dagger}c_{j+1,\text{$\sigma$}}-\mathrm{h.c.}).$
(4)

Afterwards, the harmonic spectra is computed through the Larmor’s formula
$I(\omega)\propto\omega{{}^{2}}|\braket{\hat{J}(\omega)}|^{2}$. The spectrum
(Fig. 4) displays the same features presented in (Silva  _et al._ , 2018). The
low intra-band harmonics are mostly suppressed while the high harmonics are
the most prominent. Furthermore, these are centered around the harmonic
$N=U/\omega_{L}\sim 21$ as expected. However, if we compare the emission
between different CEPs (Figs. 4 (a) and (b)) there is no significant
difference between $\phi_{\text{CEP}}=0\text{\textordmasculine}$ and
$\phi_{\text{CEP}}=90\text{\textordmasculine}$. Additionally, varying the
delay doesn’t give a different spectra either.

However, if one now computes the integrated spectrum

$\mathcal{S}=\int_{\omega_{-}}^{\omega_{+}}\text{d}\omega\,I(\omega),$ (5)

a different behavior can be appreciated. We first note that the frequencies
$\omega_{+}$ and $\omega_{-}$ corresponds to the upper and lower limits of the
energy of the first allowed optical excitations (Oka, 2012; Essler  _et al._ ,
2005), namely $\omega_{-}=\Delta$ and $\omega_{+}=\Delta+8\tau$. In Fig. 4(c)
we have obtained $\mathcal{S}$ for the whole range of CEPs and delays, where
it can be seen the noteworthy resemblance between that quantity and the
prediction made in Fig. 3(a) using $\Gamma$. Accordingly, we can also
characterize the phase of the material thanks to its optical response.

Figure 4: Harmonic spectra in arbitrary units for $\phi_{\text{CEP}}=0$ (a)
and for $\phi_{\text{CEP}}=90$ (b). We have included only five different
delays in each plot for the sake of clarity. (c) Integrated spectrum
$\mathcal{S}$ computed for the same range of $\delta$ and $\phi_{\text{CEP}}$
as in Fig. 3.

Our work has shown that is possible to acquire control of the Mott transition
in one dimensional systems using electric fields. More specifically, we have
shown that by superposing two different lasers, a mid-IR and a train of short
pulses, the phase transition can be engineered by tuning the internal
parameters of the lasers, the time-delay between them and the internal carrier
envelope phase of the short pulses ($\delta$ and $\phi_{\text{CEP}}$ in our
case). Alongside this tunability, we proved that the total doublon-hole
production rate, $\Gamma$, gives a simple, yet accurate, method of predicting
the transition. Lastly, we found the existence of a more appropriate figure of
merit to characterize the transition experimentally, by looking at the
nonlinear optical response of the system. This work may pave the way to
experimental efforts in which the insulator-to-metal transition in strongly
correlated systems can be achieved in a coherent way using tailored laser
pulses.

## Methods

In order to model the dynamics, we consider the one dimensional Hubbard model,

$\displaystyle H=$
$\displaystyle-\tau\sum_{j=1,\sigma}^{L}(e^{-\mathrm{i}\Phi(t)}c_{j,\sigma}^{\dagger}c_{j+1,\text{$\sigma$}}+\mathrm{h.c.})$
$\displaystyle+U\sum_{j=1}^{L}n_{j,\uparrow}n_{j,\downarrow},$ (6)

where $c_{j,\sigma}^{\dagger}(c_{j,\sigma})$ is the fermionic creation
(annihilation) operator for site $j$ and spin $\sigma$ and
$n_{j,\sigma}=c_{j,\sigma}^{\dagger}c_{j,\sigma}$ is the number operator. The
physical parameters $\tau$ and $U$ have been set to $\tau=0.52$ eV and
$U=5.96\tau$ to mimic $\mathrm{Sr_{2}CuO_{3}}$ (Oka, 2012), which also ensures
us that we are in the strong coupling limit, i.e., $U\gg\tau$. We will focus
on the half-filling case (one electron per site). In this case, the ground
state (also referred as the Mott insulator) has a short-range
antiferromagnetic order (Essler  _et al._ , 2005); the electrons become
localized in position space with anti-parallel spins respective to their
adjacent sites. The laser electric field, $F(t)$, is taken into account
through the Peierls phase (Essler  _et al._ , 2005):
$\mathrm{d}\Phi(t)/\mathrm{d}t=-eaF(t)$, where $a=7.56$ a.u. is the lattice
constant of $\mathrm{Sr_{2}CuO_{3}}$ and $e$ is the electron charge. We will
solve it using $N=L=12$, setting periodic boundary conditions
($c_{j+L,\sigma}=c_{j,\sigma}$) and focusing on the $S_{z}=0$ subspace. Our
approach consist of exactly solving the time-depedent Schrödinger equation
(TDSE) using a timestep of $dt=0.5$ a.u.. Convergence with the number of sites
was checked by performing calculations where $N=L=14$.

The laser field is modeled as the sum of a mid-IR pulse and a train of short
femtosecond pulses, see Fig 1(b). If one defines a single laser pulse as

$\displaystyle E\left(t,t_{0},T,\omega,E_{0},\phi\right)=$ $\displaystyle
E_{0}\cos^{2}\left(\pi\left(t-t_{0}\right)T^{-1}\right)$
$\displaystyle\theta\left(0.5T-\left|t-t_{0}\right|\right)$
$\displaystyle\cos\left(\omega\left(t-t_{0}\right)+\phi\right),$ (7)

the pump-probe scheme used in this work is given by

$\displaystyle F\left(t\right)$
$\displaystyle=E\left(t,0,20T_{\text{IR}},\omega_{\text{IR}},F_{0,\text{IR}},\pi/2\right)$
$\displaystyle+$
$\displaystyle\sum_{n=1}^{4}E\left(t,t_{0,n},T_{\mathrm{pul}},\omega_{\text{pul}},F_{0,\text{pul}},\phi_{\mathrm{CEP}}-n\pi\right),$
(8)

where $\omega_{\text{IR}}=32.92$ THz is the frequency of the mid-IR pulse
($T_{\mathrm{IR}}=2\pi/\omega_{\mathrm{IR}}$),
$\omega_{\text{pul}}=5\omega_{\text{IR}}$ is the central frequency of the
single-cycle femtosecond pulses
($T_{\mathrm{pul}}=2\pi/\omega_{\mathrm{pul}}$), $F_{0,\text{IR}}=5$ MV/cm is
the amplitude of the mid-IR pulse, $F_{0,\text{pul}}=8$ MV/cm is the amplitude
of the single-cycle femtosecond pulses,
$t_{0,n}=\left(\left(2n-5\right)/4\right)T_{\mathrm{IR}}+\delta/\omega_{\mathrm{IR}}$,
$\delta$ is the delay between the two pulses in radians and
$\phi_{\mathrm{CEP}}$ is the carrier envelope phase of the single-cycle
femtosecond pulses.

## Data availability

The data that support the plots within this paper and other findings of this
study are available from the corresponding authors upon reasonable request.

## Author contributions

E. B. M. and R. E. F. S. developed the idea. E. B. M. performed the numerical
calculations and R. E. F. S. developed the numerical code. E. B. M. and R. E.
F. S. contributed to analysis of the results. E. B. M. and R. E. F. S. wrote
the main part of the manuscript. The manuscript was discussed by E. B. M. and
R. E. F. S..

## Competing interests

The authors declare no competing interests.

## Acknowledgments

The authors acknowledge fruitful discussions with Álvaro Jiménez-Galán and
Misha Ivanov. E. B. M. and R. E. F. S. acknowledge support from the fellowship
LCF/BQ/PR21/11840008 from “La Caixa” Foundation (ID 100010434).

## References

  * Krausz and Ivanov (2009) F. Krausz and M. Ivanov, Reviews of modern physics 81, 163 (2009).
  * Kruchinin  _et al._ (2018) S. Y. Kruchinin, F. Krausz, and V. S. Yakovlev, Reviews of Modern Physics 90, 021002 (2018).
  * Keldysh (1965) L. Keldysh, Sov. Phys. JETP 20, 1307 (1965).
  * Corkum (1993) P. B. Corkum, Physical review letters 71, 1994 (1993).
  * Lewenstein  _et al._ (1994) M. Lewenstein, P. Balcou, M. Y. Ivanov, A. L’huillier, and P. B. Corkum, Physical Review A 49, 2117 (1994).
  * Ivanov  _et al._ (2005) M. Y. Ivanov, M. Spanner, and O. Smirnova, Journal of Modern Optics 52, 165 (2005).
  * Smirnova  _et al._ (2009) O. Smirnova, Y. Mairesse, S. Patchkovskii, N. Dudovich, D. Villeneuve, P. Corkum, and M. Y. Ivanov, Nature 460, 972 (2009).
  * Lépine  _et al._ (2014) F. Lépine, M. Y. Ivanov, and M. J. Vrakking, Nature Photonics 8, 195 (2014).
  * Constant  _et al._ (1997) E. Constant, V. D. Taranukhin, A. Stolow, and P. Corkum, Physical Review A 56, 3870 (1997).
  * Hentschel  _et al._ (2001) M. Hentschel, R. Kienberger, C. Spielmann, G. A. Reider, N. Milosevic, T. Brabec, P. Corkum, U. Heinzmann, M. Drescher, and F. Krausz, Nature 414, 509 (2001).
  * Itatani  _et al._ (2002) J. Itatani, F. Quéré, G. L. Yudin, M. Y. Ivanov, F. Krausz, and P. B. Corkum, Physical review letters 88, 173903 (2002).
  * Kaldun  _et al._ (2016) A. Kaldun, A. Blättermann, V. Stooß, S. Donsa, H. Wei, R. Pazourek, S. Nagele, C. Ott, C. Lin, J. Burgdörfer, _et al._ , Science 354, 738 (2016).
  * Paul  _et al._ (2001) P.-M. Paul, E. S. Toma, P. Breger, G. Mullot, F. Augé, P. Balcou, H. G. Muller, and P. Agostini, Science 292, 1689 (2001).
  * Silva  _et al._ (2012) R. Silva, P. Rivière, and F. Martín, Physical Review A 85, 063414 (2012).
  * Rivière  _et al._ (2012) P. Rivière, R. Silva, and F. Martín, The Journal of Physical Chemistry A 116, 11304 (2012).
  * Gruson  _et al._ (2016) V. Gruson, L. Barreau, Á. Jiménez-Galan, F. Risoud, J. Caillat, A. Maquet, B. Carré, F. Lepetit, J.-F. Hergott, T. Ruchon, _et al._ , Science 354, 734 (2016).
  * Ghimire and Reis (2019) S. Ghimire and D. A. Reis, Nature physics 15, 10 (2019).
  * Ghimire  _et al._ (2011) S. Ghimire, A. D. DiChiara, E. Sistrunk, P. Agostini, L. F. DiMauro, and D. A. Reis, Nature physics 7, 138 (2011).
  * Vampa  _et al._ (2015) G. Vampa, T. Hammond, N. Thiré, B. Schmidt, F. Légaré, C. McDonald, T. Brabec, D. Klug, and P. Corkum, Physical review letters 115, 193603 (2015).
  * Schubert  _et al._ (2014) O. Schubert, M. Hohenleutner, F. Langer, B. Urbanek, C. Lange, U. Huttner, D. Golde, T. Meier, M. Kira, S. W. Koch, _et al._ , Nature photonics 8, 119 (2014).
  * Vampa  _et al._ (2014) G. Vampa, C. McDonald, G. Orlando, D. Klug, P. Corkum, and T. Brabec, Physical review letters 113, 073901 (2014).
  * Hohenleutner  _et al._ (2015) M. Hohenleutner, F. Langer, O. Schubert, M. Knorr, U. Huttner, S. W. Koch, M. Kira, and R. Huber, Nature 523, 572 (2015).
  * Yue and Gaarde (2020) L. Yue and M. B. Gaarde, Physical Review Letters 124, 153204 (2020).
  * Uzan  _et al._ (2020) A. J. Uzan, G. Orenstein, Á. Jiménez-Galán, C. McDonald, R. E. Silva, B. D. Bruner, N. D. Klimkin, V. Blanchet, T. Arusi-Parpar, M. Krüger, _et al._ , Nature Photonics 14, 183 (2020).
  * Silva  _et al._ (2019) R. Silva, Á. Jiménez-Galán, B. Amorim, O. Smirnova, and M. Ivanov, Nature Photonics 13, 849 (2019).
  * Chacón  _et al._ (2020) A. Chacón, D. Kim, W. Zhu, S. P. Kelly, A. Dauphin, E. Pisanty, A. S. Maxwell, A. Picón, M. F. Ciappina, D. E. Kim, _et al._ , Physical Review B 102, 134115 (2020).
  * Baykusheva  _et al._ (2021) D. Baykusheva, A. Chacón, J. Lu, T. P. Bailey, J. A. Sobota, H. Soifer, P. S. Kirchmann, C. Rotundu, C. Uher, T. F. Heinz, _et al._ , Nano Letters 21, 8970 (2021).
  * Bai  _et al._ (2021) Y. Bai, F. Fei, S. Wang, N. Li, X. Li, F. Song, R. Li, Z. Xu, and P. Liu, Nature Physics 17, 311 (2021).
  * Schmid  _et al._ (2021) C. P. Schmid, L. Weigl, P. Grössing, V. Junk, C. Gorini, S. Schlauderer, S. Ito, M. Meierhofer, N. Hofmann, D. Afanasiev, _et al._ , Nature 593, 385 (2021).
  * Silva  _et al._ (2018) R. E. F. Silva, I. V. Blinov, A. N. Rubtsov, O. Smirnova, and M. Ivanov, Nature Photonics 12, 266 (2018).
  * Bionta  _et al._ (2021) M. R. Bionta, E. Haddad, A. Leblanc, V. Gruson, P. Lassonde, H. Ibrahim, J. Chaillou, N. Émond, M. R. Otto, Á. Jiménez-Galán, _et al._ , Physical Review Research 3, 023250 (2021).
  * Tancogne-Dejean  _et al._ (2018) N. Tancogne-Dejean, M. A. Sentef, and A. Rubio, Physical review letters 121, 097402 (2018).
  * Murakami  _et al._ (2018) Y. Murakami, M. Eckstein, and P. Werner, Physical review letters 121, 057405 (2018).
  * Imai  _et al._ (2020) S. Imai, A. Ono, and S. Ishihara, Physical review letters 124, 157404 (2020).
  * Murakami  _et al._ (2021) Y. Murakami, S. Takayoshi, A. Koga, and P. Werner, Physical Review B 103, 035110 (2021).
  * Shao  _et al._ (2022) C. Shao, H. Lu, X. Zhang, C. Yu, T. Tohyama, and R. Lu, Physical Review Letters 128, 047401 (2022).
  * Orthodoxou  _et al._ (2021) C. Orthodoxou, A. Zaïr, and G. H. Booth, npj Quantum Materials 6, 1 (2021).
  * Zhu  _et al._ (2021) W. Zhu, B. Fauseweh, A. Chacon, and J.-X. Zhu, Physical Review B 103, 224305 (2021).
  * Oka (2012) T. Oka, Phys. Rev. B 86, 075148 (2012).
  * Mayer  _et al._ (2015) B. Mayer, C. Schmidt, A. Grupp, J. Bühler, J. Oelmann, R. E. Marvel, R. Haglund Jr, T. Oka, D. Brida, A. Leitenstorfer, _et al._ , Physical Review B 91, 235113 (2015).
  * Yamakawa  _et al._ (2017) H. Yamakawa, T. Miyamoto, T. Morimoto, T. Terashige, H. Yada, N. Kida, M. Suda, H. Yamamoto, R. Kato, K. Miyagawa, _et al._ , Nature Materials 16, 1100 (2017).
  * Mazza  _et al._ (2016) G. Mazza, A. Amaricci, M. Capone, and M. Fabrizio, Physical review letters 117, 176401 (2016).
  * Joachain  _et al._ (2009) C. J. Joachain, N. J. Kylstra, and R. M. Potvliege,  _Atoms in Intense Laser Fields_ (Cambridge University Press, 2009).
  * Oka and Aoki (2008) T. Oka and H. Aoki, Phys. Rev. B 78, 241104 (2008).
  * Dean  _et al._ (2016) M. P. M. Dean, Y. Cao, X. Liu, S. Wall, D. Zhu, R. Mankowsky, V. Thampy, X. M. Chen, J. G. Vale, D. Casa, J. Kim, A. H. Said, P. Juhas, R. Alonso-Mori, J. M. Glownia, A. Robert, J. Robinson, M. Sikorski, S. Song, M. Kozina, H. Lemke, L. Patthey, S. Owada, T. Katayama, M. Yabashi, Y. Tanaka, T. Togashi, J. Liu, C. R. Serrao, B. J. Kim, L. Huber, C.-L. Chang, D. F. McMorrow, M. Först, and J. P. Hill, Nature Materials 15, 601 (2016).
  * Essler  _et al._ (2005) F. H. L. Essler, H. Frahm, F. Göhmann, A. Klümper, and V. E. Korepin,  _The One-Dimensional Hubbard Model_ (Cambridge University Press, 2005).