# Should you hire new searchers?
Optimal number of agents in a collective search, and when to launch them.

Hugues Meyer  Department of Theoretical Physics & Center for Biophysics,
Saarland University, 66123 Saarbrücken, Germany  Heiko Rieger  Department of
Theoretical Physics & Center for Biophysics, Saarland University, 66123
Saarbrücken, Germany  INM – Leibniz Institute for New Materials, Campus D2 2,
66123 Saarbrücken, Germany

###### Abstract

Search processes often involve multiple agents that collectively look for a
randomly located target. While increasing the number of agents usually
decreases the time at which the first agent finds the target, it also requires
resources to create and sustain more agents. In this letter, we consider a
collective search cost that not only accounts for the search time but also for
the cost associated to the creation and the maintenance of an agent. We first
present a general formalism for independent agents in terms of the survival
probability of the target for a single-agent search $s(t)$, where we allow
agents to be introduced in the system one after the other. From this, we first
derive analytically the optimal number of searchers to launch initially in the
system. Then, we identify the optimal strategies for exponential and algebraic
single-agent survival probabilities by pointing out the ideal times at which
new searchers should be launched in the system. Our results show that all
searchers should be launched simultaneously in the exponential case, while
some should be launched at later times in the algebraic case. Finally, we
compare these results with numerical simulations of a strongly interacting
collective search, the true self-avoiding walk, and show how the optimal
strategy differ from the non-interacting case.

Search processes are encountered in a very wide variety of systems as this
term encompasses any phenomenon where one or multiple agents are looking for a
target. From immune processes and the search for pathogens krummel2016t , to
animal foraging and hunting and the search for food sumpter2010collective ;
viswanathan2011physics , or to human search processes such as police
investigations, most of these tasks need to be optimized in a certain way.
Most frequently, one requires the typical time to find the target to be
minimized with respect to the parameters governing the search process and that
can be tuned by the searchers. Over the past recent years, a considerable
amount of work has been dedicated to identifying efficient and optimal search
strategies in various contexts. For individual searchers, it has for instance
been shown that intermittent search strategies as well as Lévy walks are
particularly efficient and are frequently observed in nature
viswanathan1996levy ; viswanathan1999optimizing ; oshanin2007intermittent ;
yang2009cuckoo ; reynolds2009levy ; benichou2011intermittent . More recently,
many studies have investigated the impact of stochastic resetting on search
efficiency and have shown that the resetting rate can also be optimized to
improve the search efficiency kusmierz2014first ; chechkin2018random ;
bressloff2020search ; evans2020stochastic ; pal2020search . Finally, non-
markovian searches have attracted some attention as well, where the influence
of memory on the search properties has been studied tejedor2012optimizing ;
meyer2021optimal ; barbier2022self ; klimek2022optimal ;
altshuler2023environmental .

Beyond the case of individual searches, collective processes have also been
extensively studied over the past decade in various contexts: for hunting and
foraging or for the global immune response, understanding how the first-
passage time properties vary with the number of searchers is important, not
only for non-interacting agents mejia2011first , but also for systems where
searchers can interact and communicate romanczuk2009collective ;
martinez2013optimizing ; janosov2017group ; kamimura2019group ;
surendran2019spatial . To this day, the number of searchers has however very
rarely been considered as a variable to be optimized. While it is clear that
the large majority of processes will lead to a monotonically decreasing mean
search time as a function of the number of searchers, it must be emphasized
that adding more searchers to a process may have a cost. For a human search
problem where one needs to pay agents and material resources to perform the
search, one can very easily understand that it is not optimal to hire as much
agents as possibly available as it would have a huge financial cost.
Similarly, in an immune response process, hiring more cells to find a pathogen
requires a substantial amount of metabolic energy. This is precisely the
motivation for the question that we are raising in this letter: given the cost
associated to the hiring and maintenance of an agent in a collective search
process, what is the optimal number of them and when should one launch them in
to the system?

To answer this, we first formalize the question for non-interacting searchers
in terms of the survival probability of the target in a single-agent search.
We allow the searchers to be introduced in the system at different times and
we define a mean search cost which consists in one contribution from the
overall search time, one from the total time spent by searchers in the system
and one from the creation/hiring of a searcher. We first derive general
results, in particular the optimal number of searchers to introduce
simultaneously at the start of the search. We then consider the main two
classes of single-agent target survival probabilities, namely exponential and
algebraic, for which we optimize the introduction times. Finally, we consider
a process with trail-leaving interacting searchers, and we compare its optimal
number of searchers to the non-interacting case.

Formalism and definition of search cost. We consider a search process of N
independent searchers for a single target, all characterized by a common
single-agent survival probability (SASP) of the target, denoted as $s(t)$. We
consider in this paper only cases where $\lim_{t\to\infty}s(t)=0$, i.e. the
target will eventually be found with probability 1. At time $t_{i}$, the
$i$-th searcher is introduced into the system and performs an independent
search without interacting with the searchers introduced previously. The
entire process is stopped whenever one of the searchers finds the target. The
question that we are raising here is: what are the optimal introduction times
$t_{i}$ that make the search most efficient? In order to respond, we need to
be more specific on the meaning of search efficiency. We therefore define the
search cost $\mathcal{K}$ as

$\mathcal{K}=J_{T}\bar{T}+J_{N}\bar{\mathcal{T}}+K_{N}\bar{N}$ (1)

where $\bar{T}$ is the mean search time, $\bar{\mathcal{T}}$ is the mean sum
of times spent by all searchers in the system until the target is found, and
$\bar{N}$ is the mean number of searchers introduced in the system until the
target is found. $J_{T}$, $J_{N}$ an $K_{N}$ are parameters that weight each
contribution to the search cost. They can be interpreted as follows:

  * •

$J_{T}$ is the target cost rate: it quantifies a cost associated to the only
presence of the target and can be thought of as a rate of damage due to the
presence of the target.

  * •

$J_{N}$ is the searcher maintenance rate: it quantifies the amount of
resources required to sustain one searcher per unit time.

  * •

$K_{N}$ is the searcher hiring cost: it quantifies the amount of resources
required to introduce a searcher into the system.

The optimal search strategy is then defined by the set of introduction times
$t_{i}$ that minimize $\mathcal{K}$. For compactness, we introduce the
normalized parameters $\gamma=J_{N}/J_{T}$ and $\kappa=K_{N}/J_{T}$ and set
$J_{T}=1$ as our cost rate unit for the rest of the paper.

To calculate $\bar{T}$, $\bar{\mathcal{T}}$ and $\bar{N}$, we first need to
formalize the target survival probability, i.e. the probability that neither
of the searchers has found the target yet after a certain time $t$. For
$t_{n}\leq t<t_{n+1}$, there are $n$ searchers in the system, and we have

$S(t)=S_{n}(t)\equiv\prod_{k=1}^{n}s(t-t_{k})$ (2)

Note that we choose by convention $t_{1}=0^{+}$ as the time origin. Following
the calculation reported in the Supplemental material, we rewrite
$\mathcal{K}$ as

$\mathcal{K}=\sum_{n=1}^{\infty}\left[(1+n\gamma)\int_{t_{n}}^{t_{n+1}}S_{n}(t)dt+\kappa
S_{n}(t_{n})\right]$ (3)

Note that this framework can be used to model a finite number of searchers $N$
simply by imposing $t_{p}\to\infty$ for $p>N$. In this case, we note the
search cost $\mathcal{K}_{N}$.

It should be emphasized that both $S$ and $s$ share the same level of
averaging with respect to the initial positions of the target and of the
searchers. If $s$ depends on these positions, $S$ does as well and corresponds
to the survival probability when all searchers are initialized at the same
position and look for the same target.

Condition for simultaneous introduction. Consider a process with a total
reservoir of $N$ searchers. We first want to know whether it is favorable to
introduce searchers simultaneously or if one should launch them one after the
other into the system.

Let us first assume that $\mathcal{K}_{N}$ is a convex function of
$\mathbf{t}_{N}=(t_{2},\cdots,t_{N})$, such that there exists at most one
local (and hence global) minimum of the cost function. This assumption is not
necessarily true for any SASP $s(t)$, but most standard cases satisfy this
hypothesis. Also note that the domain over which the function
$\mathcal{K}_{N}$ is defined is such that $t_{i}\geq t_{i-1}$ for any $i\geq
2$. Because of convexity, the minimum of $\mathcal{K}$ is therefore located at
a point $\mathbf{t}_{N}^{*}$ where either $t_{i}^{*}>t_{i-1}^{*}$ and
$\nabla_{i}\mathcal{K}_{N}(\mathbf{t^{*}_{N}})=0$, or $t_{i}^{*}=t_{i-1}^{*}$
and $\nabla_{i}\mathcal{K}_{N}(\mathbf{t^{*}_{N}})\geq 0$ 111We use the
notation $\nabla_{i}=\partial_{t_{i}}$.

Starting from this observation, we show in the Supplemental material that the
optimal strategy is such that no searchers are launched simultaneously later
than at the start of the process. The only agents introduced together are
launched at $t=0$ and their number $N_{sim}$ is the largest integer $k$ that
verifies $\nabla_{k}\mathcal{K}_{N}>0$ at the optimal point, where
$\nabla_{p}\mathcal{K}_{N}=0$ for any $p>N_{sim}$. This statement is valid for
any value of $N$ and therefore holds as $N\to\infty$. Moreover, we show that
for any $k\geq 2$, $\nabla_{k}\mathcal{K}$ evaluated at $t_{k}=t_{k-1}=...=0$
with the constraint that $\nabla_{p}\mathcal{K}=0$ for $p>k$ is given by

$\nabla_{k}\mathcal{K}=k^{-1}-(k-1)\kappa r(0)$ (4)

where $r(0)=-s^{\prime}(0)$ is the initial value of the single-agent first-
passage time distribution. $N_{sim}$ is therefore found as the largest integer
$k$ for which the latter quantity is positive, i.e. $k(k-1)\kappa r(0)<1$.
This leads to

$N_{sim}=\left\lfloor\frac{1}{2}\left(1+\sqrt{1+\frac{4}{\kappa
r(0)}}\right)\right\rfloor$ (5)

This result is very general as it does not rely on strong assumptions on
$s(t)$ and shows that $N_{sim}$ does not depend on $\gamma$ at all. No matter
how much it costs to sustain a searcher, the number of searchers to be
introduced into the system at $t=0$ will only be governed by $\kappa$.

While $N_{sim}$ can be found analytically in general, finding the optimal
values of $t_{i}$ for $i>N_{sim}$ must be treated specifically for a given
survival probability $s(t)$. Two prominent cases for $\lim_{t\to\infty}s(t)=0$
can be identified hughes1996random ; redner2001guide : exponentially or
algebraically decaying, both of which we treat separately in the following.

Exponential SASP. Let us consider a single-agent survival probability given by
$s(t)=e^{-\lambda t}$. We show in the Supplemental material that the
derivative of $\mathcal{K}$ with respect to $\Delta_{k}=t_{k+1}-t_{k}$ is
given by

$\partial_{\Delta_{k}}\mathcal{K}=\lambda
k\sum_{n=k+1}^{\infty}e^{-\lambda\sum_{l=1}^{n-1}l\Delta_{l}}\left(\frac{\lambda^{-1}}{n(n-1)}-\kappa\right)$
(6)

Because the function $1/n(n-1)$ is decreasing with $n$, all terms such that
$n(n-1)\lambda\kappa>0$ are a negative contribution to the derivative. This
condition is exactly the same as the one discussed in equations (4) and (5),
with $r(0)=\lambda$. Therefore, for $k+1>N_{sim}$ as defined in equation 5,
all contributions are negative, leading to an overall negative exponential
decay as a function of $\Delta_{k}$ for the derivative. This implies that for
all $k\geq N_{sim}$, $\Delta_{k}$ must be infinite for $\mathcal{K}$ to be
minimized, i.e. at most $N_{sim}$ particles should be introduced in the
system.

For $k<N_{sim}$, all terms of $\nabla_{k}\mathcal{K}$ with $n>N_{sim}$ are
vanishingly small as all $\Delta_{l}$ with $l>N_{sim}$ in the exponential need
to be infinitely large, as shown previously, leading to a zero contribution to
the derivative. The sum therefore runs for $k+1\leq n\leq N_{sim}$, where all
terms are positive. The overall minimum of the function will therefore be
found for $\Delta_{k}=0$. The best strategy is therefore simple: $N_{sim}$
searchers should be introduced in the system simultaneously at $t=0$ and none
after. As observed previously, this number does not depend on $\gamma$, and
the optimal cost grows as $2\sqrt{\kappa}$ for $\kappa r(0)\ll 1$ and linearly
with $\kappa$ for $\kappa r(0)\gg 1$ (see Supplemental material for the full
equation).

Algebraic SASP. Let us now consider single-agent survival probabilities
decaying as $t^{-\theta}$ for $t\to\infty$, where $\theta>0$ is the so-called
survival exponent. Examples of such processes include random walks on fractals
rammal1984random ; condamin2008probing ; meroz2011distribution , or in
infinite space bray2013persistence . Here, we can not calculate the search
cost $\mathcal{K}$ analytically as for the exponential case, therefore we
tackle it using numerical optimization and consider the following SASP:
$s(t)=\left(1+\lambda t\right)^{-\theta}$.

For arbitrary $\theta>0$, the cost function $\mathcal{K}$ should in principle
be minimized with respect to all introduction times $t_{i}$. In practice, we
performed a numerical gradient-descent optimization using $N$ of these times,
making sure that the algorithm converges to $S(t_{N})<0.001$. We used three
different values of $\theta$, namely $1/2$, $1$ and $3/2$.

The optimal strategy defined from the optimal introduction times $t_{n}$ was
found to differ substantially from the exponential case. Here, $N_{sim}$
searchers should first be introduced in the system, whose value matches
perfectly the prediction of equation (5) with $r(0)=\theta\lambda$. Then, the
next searchers should be introduced at an almost constant time interval
$\Delta^{*}$. In fact, the value of $\Delta_{n}$ very quickly reaches a
constant value as $n$ increases. This optimal interval becomes larger with
larger $\kappa$ and $\theta$ but decreases with $\gamma$, as shown in figure
1. This is also observed by analyzing the effective optimal number of
searchers $N_{opt}$ defined as $S(t_{N_{opt}})>0.01>S(t_{N_{opt}+1})$, whose
variation is opposite to the one of $\Delta^{*}$ as shown in figure 2.

Figure 1: Optimal values of $\Delta_{n}$ for $n\leq 4$, $\theta=0.5,1,1.5$ and
$\gamma=0.5$ as a function of $n(n-1)\theta\lambda\kappa$. The inset shows the
same data as a function of $n$ for various values of $\kappa$. The curves in
the main panel do not collapse on each other as suggested by the inset because
the $x$-axis depends explicitly on $n$, which is different for each curve.
Figure 2: $N_{opt}$, $N_{sim}$ and $\bar{N}$ for $\theta=0.5,1,1.5$ and
$\kappa\theta\lambda=0.128$ as a function of $\gamma$.

As algebraic SASPs correspond to searches where the searching time might be
very long, our results show that one should better not start all searchers
simultaneously. In fact, if all $N_{opt}$ agents were to be launched at $t=0$,
there would be a non-negligible probability that the target would still take a
lot of time to be found even with many searchers in the system, resulting in a
large overall cost. The searching resources must therefore be managed
carefully and launched into the system progressively only if the first ones
struggle to find the target.

Interacting searchers. While the results presented in the previous section
hold for non-interacting searchers, one can legitimately wonder to which
extent they are still valid for interacting ones. It is unfortunately not
possible to derive very general results for arbitrary interacting searchers as
the combined target survival probability $S(t)$ would highly depend on the
process under study. However, we can still optimize the launching strategy in
a particular process where searchers interact strongly and evaluate how the
results differ from the non-interacting case.

Here, we investigate a collective search by auto-chemotactic walkers, as
presented in refs. meyer2021optimal ; meyer2023alignment . There, a a field
$c$ is defined on a 2D-lattice. At each time step, each walker first adds an
amount $\delta c$ to the field $c$ on the site it occupies. Then, the field
diffuses over a certain duration following normal diffusion parametrized by a
diffusion coefficient $D_{c}$. Finally, each walker jumps to a neighboring
site $j$ with a probability proportional to $e^{-\beta c_{j}}$, where
$\beta>0$ quantifies the chemotactic coupling strength. For $D_{c}=0$, the
model reduces to the true self-avoiding walk amit1983asymptotic  where the
system retains an infinite memory as the trace left by walkers along their
paths never decays.

We run Monte-Carlo simulations of this model on a square lattice of size
$100\times 100$. Initially, a random site of the lattice is identified as a
target site. All walkers are also introduced into the system at random lattice
sites. We first ran simulations for a single walker, which we always found to
yield an exponential SASP. For the N-searcher problem, we first launched
$N_{sim}$ walkers in the system at $t=0$ and then introduced additional ones
one by one at a constant time interval $\Delta$ until one of the walkers
reaches the target. We show in figure 3 an example of the resulting mean cost
$\mathcal{K}$ as a function of $N_{sim}$ and $\Delta$ for $D_{c}=0$,
$\beta=1$, $\gamma=0.5$ and $\kappa\lambda=0.01$ where $\lambda^{-1}$ is the
timescale of the corresponding SASP. The minimum cost is here reached for
$N_{sim}=9$ and $\Delta=4\times 10^{3}$. We observe that the optimal value of
$\Delta$ is so large that the mean number of searchers $\bar{N}$ is only very
slightly larger than $N_{sim}$, i.e. it is very rare that the first $N_{sim}$
walkers will not find the target before the next searcher is launched. This is
consistent with the prediction made in the previous section for non-
interacting searches with an exponential SASP, for which $N_{sim}=\bar{N}$. We
also remark that strategies with lower values of $\Delta$ and $N_{0}$ yielding
the same value for $\bar{N}$ lead to a substantially larger search cost,
indicating that the mean number of searchers is not the only quantity that
matters but the details of the launching strategy have a major impact.

We also display in figure 3 the optimal number $N_{sim}$ as we impose
$\Delta\to\infty$ and show that it follows the same trend as the prediction of
equation (5) as a function of $\kappa\lambda$. The exact values differ
slightly but still remain close, even for the most strongly interacting
searchers that we have tested, i.e. for $D_{c}=0$ and $\beta=10$. The value of
the optimal search cost $\bar{\mathcal{K}}=\lambda\mathcal{K}$ also follow the
same trend but we clearly see that the cost becomes smaller for more strongly
interacting searchers. This implies that, although optimal search costs may be
reduced thanks to interactions, the optimal launching strategy derived for
independent searchers is very likely to be quasi-optimal for interacting
searchers.

Figure 3: Upper panel: Mean search cost of the auto-chemotactic search in the
$(\Delta,N_{sim})$-plane, for $D_{c}=0,\beta=1$ and
$\gamma=0.5,\kappa\lambda=0.01$. The lines show iso-curves of $\bar{N}$
(dotted) and $\bar{N}-N_{sim}$ (solid). Lower panel: Optimal number of walkers
$N_{sim}$ for $\Delta\to\infty$ as a function of $\kappa\lambda$ for various
values of $D_{c}$ and $\beta$ (solid lines) as well as equation (5) (dotted
lines). On the second y-axis, we report the associated optimal cost (dashed
lines) together with the optimal cost for independent searchers (dash-dotted
line).

Discussion. In this letter, we have identified the optimal strategy for when
to launch new agents in a search process. First, for non-interacting
searchers, if the single-agent survival probability of the target is
exponentially decaying, a well-defined number of agents should be launched
initially and none later. If it decays algebraically, some agents should also
be introduced initially but additional ones should then be launched at an
almost constant rate. For interacting searchers, we have shown on one example
that the optimal strategy derived for non-interacting ones is very close to
the actual optimal one, suggesting that the non-interacting optimal strategies
are reliable reference procedures.

As a direction for future works, we make the following points. First, as
mentioned originally, our results apply if $s(t)$ and $S(t)$ share the same
level of averaging with respect to the original positions of the searchers
$\mathbf{r}_{s}$ and the target $\mathbf{r}_{0}$. Assume $s(t)$ describes the
SASP where $\mathbf{r}_{s}$ and $\mathbf{r}_{0}$ are already averaged, then
the definition of $S(t)$ made in equation (2) corresponds to a process where
each new agent is initialized randomly following the distribution used in
$s(t)$. However, if one considers a process where each new agent is
initialized at the same location and one averages over all these possible
processes, then our formalism should be adapted. This could for instance be
the case for a process where one knows that the target is at a certain
distance from the launching center, but not precisely where.

More generally, this observation naturally raises the question of the use of
the information available to adapt optimal introduction strategy, as it has
for instance been studied for stochastic resetting processes pal2020search ;
bonomo2022mitigating . One could for instance consider a process where one
adapts the launching of new agents based on the history of previous walkers,
leading to non-markovian decision-making. One can also wonder about the
optimal launching locations, in addition to the optimal introduction times,
i.e. where should new agents be launched given the location of previous
agents. We believe that this letter is a first step towards the formalization
of such questions, which will be tackled in future studies.

##  I Acknowledgements

We acknowledge financial support by the DFG via the Collaborative Research
Center SFB 1027.

## References

  * (1) Matthew F Krummel, Frederic Bartumeus, and Audrey Gérard.  T cell migration, search strategies and mechanisms.  Nature Reviews Immunology, 16(3):193–201, 2016.
  * (2) David JT Sumpter.  Collective animal behavior.  Princeton University Press, 2010.
  * (3) Gandhimohan M Viswanathan, Marcos GE Da Luz, Ernesto P Raposo, and H Eugene Stanley.  The physics of foraging: an introduction to random searches and biological encounters.  Cambridge University Press, 2011.
  * (4) Gandhimohan M Viswanathan, Vsevolod Afanasyev, Sergey V Buldyrev, Eugene J Murphy, Peter A Prince, and H Eugene Stanley.  Lévy flight search patterns of wandering albatrosses.  Nature, 381(6581):413–415, 1996.
  * (5) Gandimohan M Viswanathan, Sergey V Buldyrev, Shlomo Havlin, MGE Da Luz, EP Raposo, and H Eugene Stanley.  Optimizing the success of random searches.  nature, 401(6756):911–914, 1999.
  * (6) G Oshanin, HS Wio, K Lindenberg, and SF Burlatsky.  Intermittent random walks for an optimal search strategy: one-dimensional case.  Journal of Physics: Condensed Matter, 19(6):065142, 2007.
  * (7) Xin-She Yang and Suash Deb.  Cuckoo search via lévy flights.  In 2009 World congress on nature & biologically inspired computing (NaBIC), pages 210–214. Ieee, 2009.
  * (8) Andy M Reynolds and Christopher J Rhodes.  The lévy flight paradigm: random search patterns and mechanisms.  Ecology, 90(4):877–887, 2009.
  * (9) Olivier Bénichou, Claude Loverdo, Michel Moreau, and Raphael Voituriez.  Intermittent search strategies.  Reviews of Modern Physics, 83(1):81, 2011.
  * (10) Lukasz Kusmierz, Satya N Majumdar, Sanjib Sabhapandit, and Grégory Schehr.  First order transition for the optimal search time of lévy flights with resetting.  Physical review letters, 113(22):220602, 2014.
  * (11) A Chechkin and Igor M Sokolov.  Random search with resetting: a unified renewal approach.  Physical review letters, 121(5):050601, 2018.
  * (12) Paul C Bressloff.  Search processes with stochastic resetting and multiple targets.  Physical Review E, 102(2):022115, 2020.
  * (13) Martin R Evans, Satya N Majumdar, and Grégory Schehr.  Stochastic resetting and applications.  Journal of Physics A: Mathematical and Theoretical, 53(19):193001, 2020.
  * (14) Arnab Pal, Łukasz Kuśmierz, and Shlomi Reuveni.  Search with home returns provides advantage under high uncertainty.  Physical Review Research, 2(4):043174, 2020.
  * (15) Vincent Tejedor, Raphael Voituriez, and Olivier Bénichou.  Optimizing persistent random searches.  Physical review letters, 108(8):088103, 2012.
  * (16) Hugues Meyer and Heiko Rieger.  Optimal non-markovian search strategies with n-step memory.  Physical Review Letters, 127(7):070601, 2021.
  * (17) A Barbier-Chebbah, O Bénichou, and R Voituriez.  Self-interacting random walks: Aging, exploration, and first-passage times.  Physical Review X, 12(1):011052, 2022.
  * (18) Anton Klimek and Roland R Netz.  Optimal non-markovian composite search algorithms for spatially correlated targets.  Europhysics Letters, 139(3):32003, 2022.
  * (19) Amy Altshuler, Ofek Lauber Bonomo, Nicole Gorohovsky, Shany Marchini, Eran Rosen, Ofir Tal-Friedman, Shlomi Reuveni, and Yael Roichman.  Environmental memory facilitates search with home returns.  arXiv preprint arXiv:2306.12126, 2023.
  * (20) Carlos Mejía-Monasterio, Gleb Oshanin, and Grégory Schehr.  First passages for a search by a swarm of independent random searchers.  Journal of Statistical Mechanics: Theory and Experiment, 2011(06):P06022, 2011.
  * (21) Pawel Romanczuk, Iain D Couzin, and Lutz Schimansky-Geier.  Collective motion due to individual escape and pursuit response.  Physical Review Letters, 102(1):010602, 2009.
  * (22) Ricardo Martínez-García, Justin M Calabrese, Thomas Mueller, Kirk A Olson, and Cristóbal López.  Optimizing the search for resources by sharing information: Mongolian gazelles as a case study.  Physical Review Letters, 110(24):248106, 2013.
  * (23) Milán Janosov, Csaba Virágh, Gábor Vásárhelyi, and Tamás Vicsek.  Group chasing tactics: how to catch a faster prey.  New Journal of Physics, 19(5):053003, 2017.
  * (24) Atsushi Kamimura and Toru Ohira.  Group Chase and Escape: Fusion of Pursuits-Escapes and Collective Motions.  Springer Nature, 2019.
  * (25) Anudeep Surendran, Michael J Plank, and Matthew J Simpson.  Spatial structure arising from chase-escape interactions with crowding.  Scientific reports, 9(1):14988, 2019.
  * (26) We use the notation $\nabla_{i}=\partial_{t_{i}}$.
  * (27) Barry D Hughes.  Random walks and random environments.  Oxford University Press, 1996.
  * (28) Sidney Redner.  A guide to first-passage processes.  Cambridge university press, 2001.
  * (29) R Rammal.  Random walk statistics on fractal structures.  Journal of Statistical Physics, 36:547–560, 1984.
  * (30) S Condamin, Vincent Tejedor, Raphaël Voituriez, Olivier Bénichou, and Joseph Klafter.  Probing microscopic origins of confined subdiffusion by first-passage observables.  Proceedings of the National Academy of Sciences, 105(15):5675–5680, 2008.
  * (31) Yasmine Meroz, Igor M Sokolov, and Joseph Klafter.  Distribution of first-passage times to specific targets on compactly explored fractal structures.  Physical Review E, 83(2):020104, 2011.
  * (32) Alan J Bray, Satya N Majumdar, and Grégory Schehr.  Persistence and first-passage properties in nonequilibrium systems.  Advances in Physics, 62(3):225–361, 2013.
  * (33) Hugues Meyer and Heiko Rieger.  Alignment interaction and band formation in assemblies of autochemorepulsive walkers.  Phys. Rev. E, 108:034604, Sep 2023.
  * (34) Daniel J Amit, Giorgio Parisi, and Luca Peliti.  Asymptotic behavior of the” true” self-avoiding walk.  Physical Review B, 27(3):1635, 1983.
  * (35) Ofek Lauber Bonomo, Arnab Pal, and Shlomi Reuveni.  Mitigating long queues and waiting times with service resetting.  PNAS nexus, 1(3):pgac070, 2022.

Supplement Material

## Definition of search cost

First, let us express the three contributions of the search cost in terms of
$S(t)$. First we have

$\displaystyle\bar{T}=$
$\displaystyle\int_{0}^{\infty}tR(t)dt=-\int_{0}^{\infty}tS^{\prime}(t)dt$
$\displaystyle=$ $\displaystyle\int_{0}^{\infty}S(t)dt$ (7)

Then, we have

$\displaystyle\bar{\mathcal{T}}=$
$\displaystyle\sum_{n=1}^{\infty}\int_{0}^{\infty}\frac{d}{dt}\left((t-t_{n})\Theta(t-t_{n})\right)S(t)dt$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\left[\int_{0}^{\infty}(t-t_{n})\delta(t-t_{n})S(t)dt\right.$
$\displaystyle\ \ \ \ \ \
\left.+\int_{0}^{\infty}\Theta(t-t_{n})S(t)dt\right]$ $\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\int_{0}^{\infty}\Theta(t-t_{n})S(t)dt$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\sum_{m=n}^{\infty}\int_{t_{m}}^{t_{m+1}}S_{m}(t)dt$
$\displaystyle=$
$\displaystyle\sum_{m=1}^{\infty}\sum_{n=1}^{m}\int_{t_{m}}^{t_{m+1}}S_{m}(t)dt$
$\displaystyle=$
$\displaystyle\sum_{m=1}^{\infty}m\int_{t_{m}}^{t_{m+1}}S_{m}(t)dt$ (8)

Finally, we have

$\displaystyle\bar{N}=$ $\displaystyle\int_{0}^{\infty}\Theta(t-t_{n})R(t)dt$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\int_{0}^{\infty}\delta(t-t_{n})S(t)dt$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}S(t_{n})=\sum_{n=1}^{\infty}S_{n}(t_{n})$ (9)

## Search cost in the exponential case

### General case

In the exponential case, we have $s(t)=e^{-\lambda t}$. Let us first compute
the collective mean first-passage time $\bar{T}$.

$\displaystyle\bar{T}=$
$\displaystyle\sum_{n=1}^{\infty}\int_{t_{n}}^{t_{n+1}}\prod_{k=1}^{n}s(t-t_{k})dt$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\int_{t_{n}}^{t_{n+1}}\prod_{k=1}^{n}e^{-\lambda(t-t_{k})}dt$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\int_{t_{n}}^{t_{n+1}}e^{-\lambda\sum_{k=1}^{n}(t-t_{k})}dt$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}e^{\lambda\sum_{k=1}^{n}t_{k}}\int_{t_{n}}^{t_{n+1}}e^{-\lambda
nt}dt$ $\displaystyle=$
$\displaystyle-\lambda^{-1}\sum_{n=1}^{\infty}\frac{e^{-\lambda\sum_{k=1}^{n}t_{n+1}-t_{k}}}{n}-\frac{e^{-\lambda\sum_{k=1}^{n}t_{n}-t_{k}}}{n}$
$\displaystyle=$
$\displaystyle-\lambda^{-1}\sum_{n=1}^{\infty}\frac{e^{-\lambda\sum_{k=1}^{n}t_{n+1}-t_{k}}}{n}-\frac{e^{-\lambda\sum_{k=1}^{n-1}t_{n}-t_{k}}}{n}$
$\displaystyle=$
$\displaystyle-\lambda^{-1}\left[\sum_{n=2}^{\infty}\frac{e^{-\lambda\sum_{k=1}^{n-1}t_{n}-t_{k}}}{n-1}-\sum_{n=1}^{\infty}\frac{e^{-\lambda\sum_{k=1}^{n-1}t_{n}-t_{k}}}{n}\right]$
$\displaystyle=$
$\displaystyle\lambda^{-1}\left[1-\sum_{n=2}^{\infty}\frac{e^{-\lambda\sum_{k=1}^{n-1}t_{n}-t_{k}}}{n(n-1)}\right]$
(10)

Similarly, we have

$\displaystyle\bar{\mathcal{T}}=$
$\displaystyle\sum_{n=1}^{\infty}n\int_{t_{n}}^{t_{n+1}}\prod_{k=1}^{n}s(t-t_{k})dt$
$\displaystyle=$
$\displaystyle-\lambda^{-1}\sum_{n=1}^{\infty}n\left(\frac{e^{-\lambda\sum_{k=1}^{n}t_{n+1}-t_{k}}}{n}-\frac{e^{-\lambda\sum_{k=1}^{n}t_{n}-t_{k}}}{n}\right)$
$\displaystyle=$
$\displaystyle-\lambda^{-1}\left[\sum_{n=2}^{\infty}e^{-\lambda\sum_{k=1}^{n-1}t_{n}-t_{k}}-\sum_{n=1}^{\infty}e^{-\lambda\sum_{k=1}^{n-1}t_{n}-t_{k}}\right]$
$\displaystyle=$ $\displaystyle\lambda^{-1}$ (11)

Finally, we compute $\bar{N}$ as

$\displaystyle\bar{N}=$
$\displaystyle\sum_{n=1}^{\infty}\prod_{k=1}^{n}s(t_{n}-t_{k})$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\prod_{k=1}^{n}e^{-\lambda(t_{n}-t_{k})}$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}e^{-\lambda\sum_{k=1}^{n}(t_{n}-t_{k})}$
$\displaystyle=$ $\displaystyle
1+\sum_{n=2}^{\infty}e^{-\lambda\sum_{k=1}^{n}(t_{n}-t_{k})}$ (12)

The total cost is thus given by

$\displaystyle\mathcal{K}=$ $\displaystyle\lambda^{-1}(1+\gamma)+\kappa$
$\displaystyle+\sum_{n=2}^{\infty}e^{-\lambda\sum_{k=1}^{n}(t_{n}-t_{k})}\left(\kappa-\frac{\lambda^{-1}}{n(n-1)}\right)$
(13)

Now, note that

$\displaystyle\sum_{k=1}^{n}(t_{n}-t_{k})=$ $\displaystyle
nt_{n}-\sum_{k=1}^{n}t_{k}$ $\displaystyle=$ $\displaystyle
n\sum_{k=1}^{n-1}\Delta_{k}-\sum_{k=1}^{n}\sum_{l=1}^{k-1}\Delta_{l}$ (14)
$\displaystyle=$ $\displaystyle
n\sum_{k=1}^{n-1}\Delta_{k}-\sum_{l=1}^{n-1}\sum_{k=l+1}^{n}\Delta_{l}$ (15)
$\displaystyle=$ $\displaystyle
n\sum_{k=1}^{n-1}\Delta_{k}-\sum_{l=1}^{n-1}(n-l)\Delta_{l}$ (16)
$\displaystyle=$ $\displaystyle\sum_{l=1}^{n-1}l\Delta_{l}$ (17)

where we have defined $\Delta_{k}=t_{k+1}-t_{k}$. We thus obtain

$\displaystyle\mathcal{K}=$
$\displaystyle\lambda^{-1}(1+\gamma)+\kappa+\sum_{n=2}^{\infty}e^{-\lambda\sum_{l=1}^{n-1}l\Delta_{l}}\left(\kappa-\frac{\lambda^{-1}}{n(n-1)}\right)$
(18)

Now, we take the derivative with respect to $\Delta_{k}$. In the sum, only
terms with $k\leq n-1$ will yield a non-zero contribution. We obtain

$\partial_{\Delta_{k}}\mathcal{K}=\lambda
k\sum_{n=k+1}^{\infty}e^{-\lambda\sum_{l=1}^{n-1}l\Delta_{l}}\left(\frac{\lambda^{-1}}{n(n-1)}-\kappa\right)$
(19)

### Optimal cost

In the optimal case, we proved that there should be $N_{sim}$ searchers
launched at $t=0$ and none after. We therefore have

$\displaystyle\mathcal{K}_{opt}=$
$\displaystyle\bar{T}_{opt}+\gamma\lambda^{-1}+\kappa N_{sim}$
$\displaystyle=$
$\displaystyle\lambda^{-1}\left[1-\sum_{n=2}^{N_{sim}+1}\frac{1}{n(n-1)}\right]+\gamma\lambda^{-1}+\kappa
N_{sim}$ $\displaystyle=$
$\displaystyle\lambda^{-1}\left[1+\frac{1}{N_{sim}}-1\right]+\gamma\lambda^{-1}+\kappa
N_{sim}$ $\displaystyle\lambda\mathcal{K}_{opt}=$
$\displaystyle\frac{1}{N_{sim}}+\gamma+\kappa\lambda N_{sim}$

We rewrite
$N_{sim}=\frac{1}{2}\left(1+\sqrt{1+\frac{4}{\kappa\lambda}}\right)$ as

$\displaystyle N_{sim}=$
$\displaystyle\frac{1}{2}\left(1+\sqrt{1+\frac{4}{\kappa\lambda}}\right)$
$\displaystyle=$
$\displaystyle\frac{\sqrt{\kappa\lambda}+\sqrt{\kappa\lambda+4}}{2\sqrt{\kappa\lambda}}$
$\displaystyle\kappa\lambda N_{sim}=$
$\displaystyle\sqrt{\kappa\lambda}\frac{\sqrt{\kappa\lambda}+\sqrt{\kappa\lambda+4}}{2}$
$\displaystyle\mathcal{K}_{opt}=$
$\displaystyle\gamma+\frac{2\sqrt{\kappa\lambda}}{\sqrt{\kappa\lambda}+\sqrt{\kappa\lambda+4}}+\sqrt{\kappa\lambda}\frac{\sqrt{\kappa\lambda}+\sqrt{\kappa\lambda+4}}{2}$
$\displaystyle\mathcal{K}_{opt}=$
$\displaystyle\gamma+\sqrt{\kappa\lambda}\left(\frac{2}{\sqrt{\kappa\lambda}+\sqrt{\kappa\lambda+4}}+\frac{\sqrt{\kappa\lambda}+\sqrt{\kappa\lambda+4}}{2}\right)$
(21)

As $\kappa\to 0$, the terms between brackets will tend to 1 such that the
overall cost will grow as $\sqrt{\kappa\lambda}$. However, as
$\kappa\lambda\gg 1$, the brackets will be dominated by the second term which
will tend to $\sqrt{\kappa\lambda}$, making the cost grow linearly with
$\kappa\lambda$.

##  II Gradient computation

We calculate here the gradient of $\mathcal{K}$ with respect to an arbitrary
introduction times $t_{i}$. First, we have

$\displaystyle\nabla_{p}\mathcal{K}=$ $\displaystyle-\gamma S_{p-1}(t_{p})$
$\displaystyle+\sum_{n=1}^{\infty}\left[(1+n\gamma)\int_{t_{n}}^{t_{n+1}}\nabla_{p}S_{n}(t)dt+\kappa\nabla_{p}(S_{n}(t_{n}))\right]$
(22)

The first term comes from evaluating the integrand in $t=t_{p}$ for $n=p$ and
$n+1=p$. Then we have

$\displaystyle\nabla_{p}S_{n}(t)=$
$\displaystyle\partial_{t_{p}}\left[s(t-t_{n})s(t-t_{n-1})\cdots
s(t-t_{2})s(t)\right]$ $\displaystyle=$
$\displaystyle\left\\{\begin{tabular}[]{ll}$-s^{\prime}(t-t_{p})\prod_{\begin{subarray}{c}k=1\\\
k\neq p\end{subarray}}^{n}s(t-t_{k})$&if $n\geq p$\\\
$0$&otherwise\end{tabular}\right.$ (25)

Then

$\displaystyle\nabla_{p}(S_{n}(t_{n}))=$
$\displaystyle\partial_{t_{p}}\left[s(t_{n}-t_{n-1})\cdots
s(t_{n}-t_{2})s(t_{n})\right]$ $\displaystyle=$
$\displaystyle\left\\{\begin{tabular}[]{ll}$-s^{\prime}(t_{n}-t_{p})\prod_{\begin{subarray}{c}k=1\\\
k\neq p\end{subarray}}^{n}s(t_{n}-t_{k})$&if $n>p$\\\
$\sum_{k=1}^{p-1}s^{\prime}(t_{p}-t_{k})\prod_{\begin{subarray}{c}l=1\\\ k\neq
l\end{subarray}}^{p-1}s(t_{p}-t_{l})$&if $p=n$\\\
$0$&otherwise\end{tabular}\right.$ (29)

We therefore obtain

$\displaystyle\nabla_{p}\mathcal{K}=$ $\displaystyle-\gamma S_{p}(t_{p})$
$\displaystyle-\sum_{n=p}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}s^{\prime}(t-t_{p})\prod_{\begin{subarray}{c}k=1\\\
k\neq p\end{subarray}}^{n}s(t-t_{k})dt$
$\displaystyle+\kappa\sum_{n=1}^{p-1}s^{\prime}(t_{p}-t_{n})\prod_{\begin{subarray}{c}l=1\\\
l\neq n\end{subarray}}^{p-1}s(t_{p}-t_{l})$
$\displaystyle-\kappa\sum_{n=p+1}^{\infty}s^{\prime}(t_{n}-t_{p})\prod_{\begin{subarray}{c}k=1\\\
k\neq p\end{subarray}}^{n}s(t_{n}-t_{k})$ (30)

Let $\zeta(t)=\frac{d\ln s(t)}{dt}$. We finally obtain

$\displaystyle\nabla_{p}\mathcal{K}=$ $\displaystyle-\gamma S_{p}(t_{p})$
$\displaystyle-\sum_{n=p}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}\zeta(t-t_{p})S_{n}(t)dt$
$\displaystyle+\kappa\left(\sum_{n=1}^{p-1}\zeta(t_{p}-t_{n})S_{p}(t_{p})-\sum_{n=p+1}^{\infty}\zeta(t_{n}-t_{p})S_{n}(t_{n})\right)$
(31)

## Condition for simultaneous introduction

Here we want to find under which condition should multiple searchers be
launched simultaneously into the system. As mentioned in the main text, the
minimum of $\mathcal{K}$ is located at a point $\mathbf{t}_{N}^{*}$ where
either $t_{i}^{*}>t_{i-1}^{*}$ and
$\nabla_{i}\mathcal{K}_{N}(\mathbf{t^{*}_{N}})=0$, or $t_{i}^{*}=t_{i-1}^{*}$
and $\nabla_{i}\mathcal{K}_{N}(\mathbf{t^{*}_{N}})\geq 0$.

Let us now proceed by contradiction. Assume that $\mathcal{K}_{N}$ is minimal
at a point $\mathbf{t}^{*}_{N}$ where, for a certain $k>2$, we have
$t_{k}^{*}=t_{k-1}^{*}$ and $t_{k-1}^{*}>t_{k-2}^{*}$. Following our previous
observation, this implies that $\nabla_{k}\mathcal{K}_{N}>0$ and
$\nabla_{k-1}\mathcal{K}_{N}=0$. Let us now compute the difference between
$\nabla_{k-1}\mathcal{K}$ and $\nabla_{k}\mathcal{K}$ for $t_{k-1}=t_{k}$.
Following the calculation from the previous section, we have

$\displaystyle\nabla_{k-1}\mathcal{K}-\nabla_{k}\mathcal{K}=$
$\displaystyle-\gamma S_{k-1}(t_{k-1})+\gamma S_{k}(t_{k})$
$\displaystyle-\sum_{n=k-1}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}\zeta(t-t_{k-1})S_{n}(t)dt+\sum_{n=k}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}\zeta(t-t_{k})S_{n}(t)dt$
$\displaystyle+\kappa\left(\sum_{n=1}^{k-2}\zeta(t_{k-1}-t_{n})S_{k-1}(t_{k-1})-\sum_{n=k}^{\infty}\zeta(t_{n}-t_{k})S_{n}(t_{n})\right)$
$\displaystyle-\kappa\left(\sum_{n=1}^{k-1}\zeta(t_{k}-t_{n})S_{k}(t_{k})-\sum_{n=k+1}^{\infty}\zeta(t_{n}-t_{k})S_{k}(t_{k})\right)$
(32)

Now, note that for any $n>0$ it holds $S_{n-1}(t_{n})=S_{n}(t_{n})$. Using
$t_{k-1}=t_{k}$, we have $S_{k-1}(t_{k-1})=S_{k}(t_{k})$. With this, we note
that most of the terms in all the sums compensate each other and we obtain

$\displaystyle\left(\nabla_{k-1}-\nabla_{k}\right)\mathcal{K}=$
$\displaystyle-(1+(k-1)\gamma)\int_{t_{k-1}}^{t_{k}}\zeta(t-t_{k})S_{n}(t)dt$
$\displaystyle-\kappa\zeta(t_{k}-t_{k})S_{k}(t_{k})$
$\displaystyle-\kappa\zeta(t_{k}-t_{k-1})S_{k}(t_{k})$ $\displaystyle=$
$\displaystyle-2\kappa\zeta(0)S_{k}(t_{k})$ $\displaystyle=$
$\displaystyle-2\kappa s^{\prime}(0)S_{k}(t_{k})$ (33)

Note that this result also holds for a finite value of $N$ as the right-hand
side only depends on $t_{k}$, such that imposing $t_{N}\to\infty$ for $N>k$,
as one should to deal with $\mathcal{K}_{N}$, does not impact it. Because
$s^{\prime}(0)<0$, we therefore have
$\nabla_{k-1}\mathcal{K}_{N}>\nabla_{k}\mathcal{K}_{N}$. This is valid at any
point $\mathbf{t}_{N}$, provided that $t_{k}=t_{k-1}$, and in particular at
$\mathbf{t}^{*}_{N}$, where we have $\nabla_{k}\mathcal{K}_{N}>0$. We
therefore have $\nabla_{k-1}\mathcal{K}>\nabla_{k}\mathcal{K}>0$, which is in
contradiction with the original assumption. We therefore conclude that if
$t_{k}^{*}=t_{k-1}^{*}$ then for all $j<k$ we must have
$t_{k}^{*}=t_{j}^{*}=0$: in the optimal strategy, there can not be searchers
launched simultaneously later than at the start of the process.

Now, we want to calculate the optimal number of searchers $N_{sim}$ to be
launched at $t=0$. From our previous argument, we know that at the optimal
point, we have $\nabla_{k}\mathcal{K}_{N}>0$ for $k\leq N_{sim}$ and
$\nabla_{k}\mathcal{K}_{N}=0$ for $k>N_{sim}$. Let us now compute
$\nabla_{k}\mathcal{K}$ for $t_{2}=\cdots=t_{k}=0$ for an arbitrary value of
$k$, assuming that $\nabla_{p}\mathcal{K}=0$ for $p>k$. This latter condition
reads

$\displaystyle\gamma S_{p}(t_{p})$
$\displaystyle+\sum_{n=p}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}s^{\prime}(t-t_{p})s(t)^{k}\prod_{\begin{subarray}{c}l=k+1\\\
l\neq p\end{subarray}}^{n}s(t-t_{l})dt$
$\displaystyle-\kappa\left(\sum_{n=1}^{p-1}\zeta(t_{p}-t_{n})S_{p}(t_{p})-\sum_{n=p+1}^{\infty}\zeta(t_{n}-t_{p})S_{n}(t_{n})\right)=0$
(34)

Then, we compute $\nabla_{k}\mathcal{K}$:

$\displaystyle\nabla_{k}\mathcal{K}=$
$\displaystyle-\gamma-\sum_{n=k}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}s^{\prime}(t)s(t)^{k-1}\prod_{p=k+1}^{n}s(t-t_{p})dt$
$\displaystyle+\kappa\left((k-1)s^{\prime}(0)-\sum_{n=k+1}^{\infty}s^{\prime}(t_{n})s(t_{n})^{k-1}\prod_{p=k+1}^{n}s(t_{n}-t_{p})\right)$
(35)

First, we rewrite the second term using integration by parts, reading

$\displaystyle\int_{t_{n}}^{t_{n+1}}s^{\prime}(t)s(t)^{k-1}\prod_{p=k+1}^{n}s(t-t_{p})dt=$
$\displaystyle\left[\frac{s(t)^{k}}{k}\prod_{p=k+1}^{n}s(t-t_{p})\right]_{t_{n}}^{t_{n+1}}$
$\displaystyle-\frac{1}{k}\sum_{p=k+1}^{n}\int_{t_{n}}^{t_{n+1}}s(t)^{k}s^{\prime}(t-t_{p})\prod_{\begin{subarray}{c}l=k+1\\\
l\neq p\end{subarray}}^{n}s(t-t_{l})dt$ $\displaystyle=$
$\displaystyle\frac{1}{k}\left[S_{n}(t_{n+1})-S_{n}(t_{n})\right]$
$\displaystyle-\frac{1}{k}\sum_{p=k+1}^{n}\int_{t_{n}}^{t_{n+1}}s(t)^{k}s^{\prime}(t-t_{p})\prod_{\begin{subarray}{c}l=k+1\\\
l\neq p\end{subarray}}^{n}s(t-t_{l})dt$ (36)

Now, summing over all values of $n\geq k$ yields

$\displaystyle\sum_{n=k}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}s^{\prime}(t)s(t)^{k-1}$
$\displaystyle\prod_{p=k+1}^{n}s(t-t_{p})dt$ $\displaystyle=$
$\displaystyle-\frac{1}{k}+\frac{1}{k}\sum_{n=k}^{\infty}\gamma
n\left[S_{n}(t_{n+1})-S_{n}(t_{n})\right]$
$\displaystyle-\frac{1}{k}\sum_{p=k+1}^{\infty}\sum_{n=p}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}s(t)^{k}s^{\prime}(t-t_{p})\prod_{\begin{subarray}{c}l=k+1\\\
l\neq p\end{subarray}}^{n}s(t-t_{l})dt$ (37)

where we have used the fact that $S_{k}(t_{k})=1$. Now, we note that the
summand in the last term is exactly the second term in the gradient of
$\nabla_{p}\mathcal{K}$ in equation (34). Summing equation (34) over $p>k$
yields

$\displaystyle\sum_{p=k+1}^{\infty}\sum_{n=p}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}s(t)^{k}$
$\displaystyle s^{\prime}(t-t_{p})\prod_{\begin{subarray}{c}l=k+1\\\ l\neq
p\end{subarray}}^{n}s(t-t_{l})dt$ $\displaystyle=$
$\displaystyle-\sum_{p=k+1}^{\infty}\gamma S_{p}(t_{p})$
$\displaystyle+\sum_{p=k+1}^{\infty}\kappa\left(\sum_{n=1}^{p-1}\zeta(t_{p}-t_{n})S_{p}(t_{p})-\sum_{n=p+1}^{\infty}\zeta(t_{n}-t_{p})S_{n}(t_{n})\right)$
(38)

Let us now rewrite the terms proportional to $\kappa$. First, let us note
$A_{pn}=\zeta(t_{p}-t_{n})S_{p}(t_{p})$. Swapping the order of summation leads
to

$\displaystyle\sum_{p=k+1}^{\infty}\left(\sum_{n=1}^{p-1}A_{pn}-\sum_{n=p+1}^{\infty}A_{np}\right)=$
$\displaystyle\sum_{p=k+1}^{\infty}\left(\sum_{n=1}^{k}A_{pn}+\sum_{n=k+1}^{p-1}A_{pn}-\sum_{n=p+1}^{\infty}A_{np}\right)$
$\displaystyle=$
$\displaystyle\sum_{p=k+1}^{\infty}\sum_{n=1}^{k}A_{pn}+\sum_{n=k+1}^{\infty}\sum_{p=n+1}^{\infty}A_{pn}-\sum_{p=k+1}^{\infty}\sum_{n=p+1}^{\infty}A_{np}$
$\displaystyle=$ $\displaystyle\sum_{p=k+1}^{\infty}\sum_{n=1}^{k}A_{pn}$
$\displaystyle=$
$\displaystyle\sum_{p=k+1}^{\infty}\sum_{n=1}^{k}s^{\prime}(t_{p})s(t_{p})^{k-1}\prod_{l=k+1}^{p}s(t_{p}-t_{l})$
$\displaystyle=$ $\displaystyle
k\sum_{p=k+1}^{\infty}s^{\prime}(t_{p})s(t_{p})^{k-1}\prod_{l=k+1}^{p}s(t_{p}-t_{l})$
(39)

where we have again used the fact that $t_{n}=0$ for $n\leq k$ to evaluate
$A_{pn}$ in the sum. We therefore obtain

$\displaystyle\sum_{p=k+1}^{\infty}\sum_{n=p}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}s(t)^{k}$
$\displaystyle s^{\prime}(t-t_{p})\prod_{\begin{subarray}{c}l=k+1\\\ l\neq
p\end{subarray}}^{n}s(t-t_{l})dt$ $\displaystyle=$
$\displaystyle-\sum_{p=k+1}^{\infty}\gamma
S_{p}(t_{p})+k\kappa\sum_{p=k+1}^{\infty}s^{\prime}(t_{p})s(t_{p})^{k-1}\prod_{l=k+1}^{p}s(t_{p}-t_{l})$
(40)

Inserting this into equation (37) leads to

$\displaystyle\sum_{n=k}^{\infty}(1+n\gamma)\int_{t_{n}}^{t_{n+1}}s^{\prime}(t)s(t)^{k-1}\prod_{p=k+1}^{n}s(t-t_{p})dt=$
$\displaystyle-\frac{1}{k}+\frac{\gamma}{k}\sum_{n=k}^{\infty}n\left[S_{n}(t_{n+1})-S_{n}(t_{n})\right]+\frac{\gamma}{k}\sum_{p=k+1}^{\infty}S_{p}(t_{p})$
$\displaystyle-\kappa\sum_{p=k+1}^{\infty}s^{\prime}(t_{p})s(t_{p})^{k-1}\prod_{l=k+1}^{p}s(t_{p}-t_{l})$
(41)

We note that the last term of the latter equation compensates exactly the last
term of $\nabla_{k}\mathcal{K}$ in equation (35). Bringing everything together
yields

$\displaystyle\nabla_{k}\mathcal{K}=$
$\displaystyle-\gamma+\frac{1}{k}-\frac{\gamma}{k}\sum_{n=k}^{\infty}n\left[S_{n}(t_{n+1})-S_{n}(t_{n})\right]$
$\displaystyle-\frac{\gamma}{k}\sum_{n=k+1}^{\infty}S_{n}(t_{n})+\kappa(k-1)s^{\prime}(0)$
(42)

Now, we rewrite

$\displaystyle\sum_{n=k}^{\infty}n\left[S_{n}(t_{n+1})-S_{n}(t_{n})\right]$
$\displaystyle=\sum_{n=k}^{\infty}nS_{n+1}(t_{n+1})-\sum_{n=k}^{\infty}nS_{n}(t_{n})$
$\displaystyle=$
$\displaystyle\sum_{n=k+1}^{\infty}(n-1)S_{n}(t_{n})-\sum_{n=k}^{\infty}nS_{n}(t_{n})$
$\displaystyle=$ $\displaystyle-
kS_{k}(t_{k})-\sum_{n=k+1}^{\infty}S_{n}(t_{n})$ $\displaystyle=$
$\displaystyle-k-\sum_{n=k+1}^{\infty}S_{n}(t_{n})$ (43)

such that

$\displaystyle-\frac{\gamma}{k}\sum_{n=k}^{\infty}n\left[S_{n}(t_{n+1})-S_{n}(t_{n})\right]=$
$\displaystyle\gamma+\frac{\gamma}{k}\sum_{n=k+1}^{\infty}S_{n}(t_{n})$ (44)

to finally obtain

$\displaystyle\nabla_{k}\mathcal{K}=$
$\displaystyle\frac{1}{k}+\kappa(k-1)s^{\prime}(0)$ (45)

$N_{sim}$ is therefore found as the largest value of $k$ which is such that
this quantity is positive.