We introduce a model for ant trail formation, building upon previous work on biologically feasible local algorithms that plausibly describe how ants maintain trail networks. The model is a variant of a reinforced random walk on a directed graph, where ants lay pheromone on edges as they traverse them and the next edge to traverse is chosen based on the level of pheromone; this pheromone decays with time. There is a bidirectional flow of ants in the network: the forward flow proceeds along forward edges from source (e.g. the nest) to sink (e.g. a food source), and the backward flow in the opposite direction. Some fraction of ants are lost as they pass through each node (modeling the loss of ants due to exploration observed in the field). We initiate a theoretical study of this model. We note that ant navigation has inspired the field of ant colony optimization, heuristics that have been applied to several combinatorial optimization problems; however the algorithms developed there are considerably more complex and not constrained to being biologically feasible.

We first consider the linear decision rule, where the flow divides itself among the next set of edges in proportion to their pheromone level. Here, we show that the process converges to the path with minimum leakage when the forward and backward flows do not change over time. On the other hand, when the forward and backward flows increase over time (caused by positive reinforcement from the discovery of a food source, for example), we show that the process converges to the shortest path. These results are for graphs consisting of two parallel paths (a case that has been investigated before in experiments). Through simulations, we show that these results hold for more general graphs drawn from various random graph models; proving this convergence in the general case is an interesting open problem.  Further, to understand the behaviour of other decision rules beyond the linear rule, we consider a general family of decision rules. For this family, we show that there is no advantage of using a non-linear decision rule, if the goal is to find the shortest or the minimum leakage path. We also show that bidirectional flow is necessary for convergence to such paths. Our results provide a plausible explanation for field observations, and open up new avenues for further theoretical and experimental investigation.

Despite the simplicity of our model and similarity to other random walk processes studied in the literature, the dynamics of this simple process are remarkably complex. For a graph consisting of two parallel paths (that has been investigated before in experiments), we study the process where ants choose the next edge with probability proportional to pheromone level. We call such a decision rule the linear decision rule. Here, we show that the process converges to the path with minimum leakage when the rate of the forward and backward flows do not change over time.
On the other hand, when the forward and backward flows increase over time (caused by positive reinforcement from the discovery of a food source, for example), we show that the process converges to the shortest path. Further, to understand the behaviour of other decision rules beyond the linear rule, we identify the equilibrium states for a general family of decision rules. For this family, we show that if the goal is to find the shortest or the minimum leakage path, then there is no advantage of using non-linear decision rule. We also show that bidirectional flow is necessary for convergence to the shortest path or the path with minimum leakage. We report on experiments that show the convergence of this process on more general graphs drawn from various random graph models; proving this convergence in the general case is an interesting open problem.

§ INTRODUCTION

Collective behavior is widespread in nature. Global behavior operates without central control using simple local interactions among individuals. Well known examples include the coordinated movement of schools of fish and flocks of birds couzin2005effective.  Such behavior is based on biological distributed algorithms navlakha2011algorithms that have raised questions of interest in theoretical computer science, for example opinion dynamics and bird flocking chazelle2009natural,chazelle2012dynamics,bhattacharyya2013convergence.

A recent focus of research on collective behavior is how it is tuned to changing environmental conditions gordon2016evolution. Social insects such as ants live in colonies that function collectively. The 14K species of ants  that live in very diverse habitats provide an opportunity to learn how local conditions have shaped the evolution of the algorithms that regulate collective behavior.

Here we examine how local interactions generate trail networks in arboreal ants. Many ant species create networks of foraging trails. The arboreal turtle ant C. goniodontus nests and forages in trees, its trail networks constrained to lie on a natural graph formed by tangled branches and vines in the tree canopy.
Turtle ants form a routing backbone of foraging trails linking several nests and temporary food sources.  The backbone trail network can be large, extending hundreds of meters, spanning many trees and using many junctions in dense vegetation. The colony chooses paths from amongst a wide range of possibilities, constrained by the graph structure of the vegetation. Ants lay trail pheromone as they move along the edges, and this pheromone guides their choice of edges to traverse.

figureTangled branches in which the turtle ants forage. Picture from chandrasekhar2018distributed.

chandrasekhar2018distributed proposed a biologically feasible distributed algorithm that could plausibly describe how these ants with limited memory maintain the routing backbone and find alternative paths to circumvent broken links in the backbone, communicating only through pheromone without a specific targeted recipient.
They model the movement of each ant as a Markov process on an undirected graph which must choose an edge to traverse at each node (junction) based on the pheromone levels detected.
The traversal of an edge by an ant reinforces the pheromone level of that edge (additively); this pheromone also decays with time (multiplicatively).

They identified local decision rules for selecting edges to traverse which (in simulations) resulted in trail networks with short paths with low entropy (a measure of convergence towards a single consensus path).

More recently, chandrasekhar2019better used data from field observations of the trail networks of turtle ants to test what objective functions these trails may be optimizing.

They identified each node or junction in the vegetation where an ant had a choice among more than one edge in the direction it was traveling. They measured the length of each edge. They also measured variation among nodes in physical configuration by assigning  a transition index to each transition from one edge through a node to another edge, to indicate the likelihood of successive ants taking the same trajectory through the node and thus reinforcing it with pheromone.

Their conclusion was that the ants’ networks favored the maintenance of coherent trails over choosing shortest paths. In particular, the ants' trails  were more likely to maximize the probability of rapid reinforcement with pheromone , and  minimize the number of nodes, than minimizing the distance travelled.
They reasoned that maximizing the probability of reinforcement and minimizing the number of nodes contribute to coherence because they both diminish the risk of losing ants from the trail.
Trail networks must balance exploration (necessary for the colony to construct trails, search for new resources, repair breaks) and coherence.

There is a small probability of exploration at each node; thus, minimizing the number of nodes traversed reduces opportunities for the ants to get lost.
They also point out that the algorithm proposed in their previous work chandrasekhar2018distributed did not distinguish between minimizing the number of nodes and the distance traveled, and that further work is needed to develop an algorithm that captures the role of physical variation in the configuration of the nodes in the environment.

Here we address  this by developing a simple model for how ants form a trail that explicitly accounts for exploration at nodes of the network that results in the loss of ants. Our model builds on chandrasekhar2018distributed.

We model trails as a bidirectional flow from nest to food source and back, and model ants getting lost by leakage.
Our flows are akin to flows in traffic networks for example wardrop1952road, beckmann1955studies, roughgarden2002bad.
We start with the linear decision rule, where the flow divides among the next set of edges in proportion to their pheromone level.
Starting from the original graph, we show that the dynamics under this linear decision rule converges to the path with minimum leakage.
Previous studies  have also shown that Argentine  ants sometimes find shortest paths goss1989self. We show that in our model, the same dynamics converges to the shortest path if the flow is increasing with time.
Note that the rate of flow of ants is positively reinforced by the detection of food sources and other factors deneubourg1986random,gordon2012dynamics;
we show that such increasing flow actually leads to convergence to the shortest path. This suggests that, at least in principle, ants have the ability to obtain information about path length by varying their flow rate. It would be fascinating to explore experimentally whether ants actually use this ability to find the shortest path. We prove these results for a network consisting of two parallel paths, a case that has received some attention in the literature goss1989self, dorigo2001experimental.
Our simulations indicate that the dynamics converge for general graphs drawn from various random graph models.

The bidirectional nature of flow is crucial for our results.
This is different from the traditional theoretical computer science literature where the flows considered  are usually unidirectional.
In the case of unidirectional flow, we show that no pheromone based rule can find the shortest or minimum leakage path.
However bidirectional flow is characteristic of many biological networks, including ant trails,
and is also found in engineered systems such as telecommunication networks.

For example, bidirectional flow in the ant trail network was essential for the ability to repair breaks in chandrasekhar2018distributed.

Our convergence results are for the linear decision rule. To understand the dynamics for non-linear rules, we consider a very general family of decision rules. We show that the linear decision rule is the unique member of this family with guaranteed convergence properties to the minimum leakage and shortest paths.

The model we study has some resemblance to reinforced random walks introduced by Diaconis and others, that have received some attention in the literature diaconis1980finetti,davis1990reinforced,pemantle2007survey,

and have found applications in biology
Here a single agent traverses a graph by choosing edges with probability proportional to their edge weight (analogous to pheromone). This edge weight increases additively each time the edge is traversed. However, there are a few key differences between the model we study and the setup for reinforced random walks:
1) We have a large number of ants in the system (modeled by a flow) and their behavior is affected by their collective actions ,while the model for reinforced random-walks considers a single agent whose behavior is influenced by its past random choices.
2) Pheromone decays geometrically over time in our model, but edge weights do not decrease in reinforced-random walks.
3) Our model has leakage at each node, and this is not present in the setup for reinforced-random walks.

Nevertheless, the model we propose and study is a Markov process of particular relevance to biology, in a similar spirit to random walk like processes studied before. Despite the apparent simplicity of our model, understanding its behavior is surprisingly non-trivial.
Our goal is to introduce this process and make a first attempt at understanding its properties. The behavior of this process in simulations suggests that it should be possible to significantly generalize the results we prove here.
We think our work raises fascinating questions that we hope will be interesting to both computer scientists and biologists.

Related Work:
In related work, nakagaki2000maze experimentally demonstrated that slime mold finds the the shortest path in a maze. In an attempt to understand this phenomenon, tero2007mathematical gave a mathematical model for the dynamics of slime mold . Subsequently, convergence to the shortest path for these dynamics were proved miyaji2007mathematical,miyaji2008physarum, bonifaci2012physarum, and the model was generalized to other graph problems straszak2016natural, bonifaci2020physarum. straszak2016irls showed a surprising connection between the slime mold dynamics and the Iteratively Reweighted Least Squares (IRLS) algorithm used in compressed sensing.

In the slime mold dynamics, current flows from $s$ to $t$ in an electrical resistor network. The diameter of resistors increase in proportion to the current level along them. Here, the diameter of resistors is analogous to the pheromone level at edges in our model. However, beyond this similarity, we are not aware of any other connections between the two models.

The $s$-$t$ shortest path problem has also been studied in the distributed systems literature under the Local and Congest models lynch1996distributed, elkin2017distributed, ghaffari2018improved, becker2016near.
Here machines, each with a local view of the network, communicate with their neighbors to cooperatively perform a computation.
Communication proceeds in synchronized rounds and the typical measure of complexity is the number of rounds needed.

Our work is different from traditional ant-colony optimization dorigo1991distributed, dorigo2005ant, lopez2018ant, where the algorithms considered are not required to be biologically plausible. Models of ant colony optimization (ACO) are inspired by ant behavior to solve combinatorial optimization problems, such as the traveling salesman problem and the shortest path problem . In ACO, individual agents (simulating ants) construct candidate solutions using heuristics, and then use limited communication (simulating pheromone) to lead other agents towards better solutions.

In ACO, the simulated ants have significantly more computational power than is biologically plausible for real ants. Unlike ants, the simulated ants have the ability to remember, retrace and reinforce entire paths, and can determine the amount of “pheromone” laid by the quality of the global solution.

Organization: In <Ref>, we provide the mathematical definition of our model for ant trail formation. In <Ref>, we state all the main results of our paper. In <Ref>, we provide proof overviews for all our main results and defer the formal proofs to Appendix.

Some high level points:

* Deborah's recent paper chandrasekhar2019better showed that turtle ants prefer paths with minimum number of vertices. Intuition given in that paper was that more vertices in a path would lead to higher chances of getting lost.

* How do ants find such paths with no central control and minimal computational resources?

* Ants use pheromone to communicate.

* We model this as bidirectional flow from nest to food source and back, and model ants getting lost by leakage.

* Starting from the original graph, we show that the flow converges to the path with minimum leakage.

* Previous works have also shown that argentine  ants sometimes find shortest paths goss1989self. We show that in our model, the flow converges to the shortest path if the flow is increasing with time.

* We also show fundamental limits for a very general class of pheromone based rules. For example, we show that change in flow is necessary for any continuous monotone pheromone based rule to be able to converge to the shortest path.

* The bidirectional nature of flow is crucial for our results. This is different from the traditional TCS literature where the flows considered  are usually unidirectional.

* Connections to reinforced-random walks.

* Connections to distributed systems.

* In the past, nakagaki2000maze experimentally showed that slime mold converges to the shortest paths in a maze. Later, tero2007mathematical gave a mathematical model for slime mold dynamics and showed using simulations that it converges to the shortest path. miyaji2007mathematical,miyaji2008physarum began the analytical study of the dynamics showing convergence for a restricted family of graphs. Finally,  bonifaci2012physarum proved that the slime mold dynamics converge to the shortest path for general graphs.  straszak2016natural extended this result to show that the slime mold dynamics can be used to solve the  uncapacitated mincost flow problem as well. straszak2016irls showed a connection between the slime mold dynamics and the Iteratively Reweighted Least Squares (IRLS) algorithm used in compressed sensing.

In a similar spirit, our work can be considered as an effort towards giving a biologically plausible model for ants, with analytical results on some family of graphs, and simulation results for general graphs.  Slime mold dynamics also have some similarity with the ant dynamics. In the slime mold dynamics, current flows from s to t in a resistor network. The diameter of the resistor increases in proportion to the current level along the resistor. And they show that eventually all the current flows through the shortest path. Their notion of diameter, and our notion of pheromone level seems similar, but there is no obvious similarity in the dynamics.

* Our work different from traditional ant-colony optimization, where the algorithms considered are not required to be biologically plausible. From one of Deborah's paper chandrasekhar2018distributed: “Models of ant colony optimization (ACO), frst proposed in 1991, loosely mimic ant behavior to solve combinatorial optimization problems, such as the traveling salesman problem and the shortest path problem. In ACO, individual ants each use a heuristic to construct candidate solutions, and then use pheromone to lead other ants towards higher quality solutions. Recent advances improve ACO through techniques such as local search, cunning ants, and iterated ants. ACO, however, provides simulated ants more computational power than turtle actually ants possess; in particular, ACO-simulated ants have sufcient memory to remember, retrace, and reinforce entire paths or solutions, and they can choose how much pheromone to lay in retrospect, based on the optimality of the solution”

§ THE MODEL

We consider bidirectional flow on a directed graph $G = (V, E)$ with source vertex and destination vertex $s$ and $d$ respectively.  For each vertex $v$, let $\fflow{v}(t)$ and $\bflow{v}(t)$ denote the forward and backward flows on $v$ present at time $t$. The forward flow moves along the direction of the edges, and the backward flow moves in the opposite direction. Let $p_{uv}(t)$ denote the pheromone level on edge $(u, v)$ at time $t$.  The pheromone levels and flows together constitute the state of the system at any time $t$, which gets updated as follows:

* Flow movement: At each time step,  the forward flow on a vertex  moves along its outgoing edges,  dividing itself based on a decision rule that depends on the pheromone levels on these edges. The simplest such rule divides the flow  proportional to the pheromone level on the outgoing edges. Formally, let $\fflow{uv}(t)$ denote the forward flow moving  along edge $(u, v)$ at time $t$. Then according to this rule,

\begin{equation}
\fflow{uv}(t) = \fflow{u}(t)\frac{p_{uv}(t)}{\sum\limits_{z: (u, z) \in E} {p_{uz}(t)}}
\end{equation}

We call this decision rule the linear decision rule as it divides the flow proportional to the pheromone levels.
All our positive results are for this particular rule. Our negative results are for a more general class of rules defined later.

The total forward flow on vertex $v$ is the sum of flow along its incoming edges:

\begin{equation}
\label{eq:no_leak_flow}
\fflow{v}(t+1) = \sum\limits_{z: (z, v) \in E}
\fflow{zv}(t)
\end{equation}

Leakage: In addition, there is possible leakage of flow at any vertex $v$ governed by a leakage parameter $l_v \in [0, 1]$, such that $l_v$ fraction of flow at $v$ leaks out. Equation <ref> corresponds to the case when leakage at vertex $v$, $l_v = 0$. In general, the total forward flow on vertex $v$ is given by

\begin{equation}
\label{eq:leak_flow}
\fflow{v}(t+1) = (1 - l_v)  \sum\limits_{z: (z, v) \in E}
\fflow{zv}(t)
\end{equation}

Movement for backward flow takes place in exactly the same manner, with the direction of the flow reversed. Formally, let $\bflow{uv}(t)$ denote the backward flow moving along the edge $(u, v)$ at time $t$. Then

\begin{equation}
\bflow{uv}(t) =  \ \bflow{v}(t)\frac{p_{uv}(t)}{\sum\limits_{z: (z,v) \in E} {p_{zv}(t)}}
\end{equation}

The total backward flow at $u$ is the sum of backward flow along its outgoing edges, multiplied by the leakage parameter. For simplicity, in our model, the leakage parameter for any given vertex  is same for forward and backward flows.

\begin{equation}
\bflow{u}(t+1) = (1 - l_u) \sum\limits_{z: (u,z) \in E}
\bflow{uz}(t)
\end{equation}

At each time $t$, new forward and backward flow $\fflow{s}(t)$ and $\bflow{d}(t)$ appears on the source vertex and destination vertex $s$ and $d$ respectively.

* Pheromone update: At each time step, the pheromone level on each edge increases by the amount of flow along the edge, and decays by a multiplicative factor of $\delta$:

\begin{equation}
p_{uv}(t+1) = \delta(p_{uv}(t) + \fflow{uv}(t)  + \bflow{uv}(t))
\end{equation}

Note that while the flows are directional, the pheromone level present on an edge does not have any direction, and gets affected by the flows from both the directions.

Forward and backward flow in a graph with parallel paths.

Parameters: Here we define the parameters of our model.

* Let $\ell(t)$ and $r(t)$ be the input flow from the left and right side respectively.

* Let $\alpha$ and $\beta$ be the leakage values of the top and the bottom path respectively.

* Let $n$ and $m$ be the number of nodes in the top and the bottom path respectively.

* For any edge $(a,b)$ be use $\mathrm{f_{ab}(t)}$ to denote its pheromone level at time $t$. For instance, $\fbc{t}$ denotes the pheromone level of the edge $(B,C)$ at time $t$.

* Let $\delta$ be the decay parameter.

Update rule: Here we describe the update rule of our model. For simplicity, we define it for the simple graph shown in Figure <ref>.

We consider bidirectional flow on a directed graph $G = (V, E)$ with source vertex and destination vertex $s$ and $d$. Each edge $e$ lies on some path from $s$ to $d$. For each directed edge $(u, v)$, $\fflow{uv}(t)$ and $\bflow{uv}(t)$ denote the forward and backward flows on edge $(u, v)$ at time $t$. $p_{uv}(t)$ denotes the pheromone level on edge $(u, v)$ at time $t$. For notational consistency, we also introduce two new vertices $s_0$ and $d_0$, and add terminal edges $(s_0, s)$ and $(d, d_0)$. The forward and backward flows first appear on edges $(s_0, s)$ and $(d, d_0)$ respectively. The pheromone levels and flows on edges together constitute the state of the system at any time $t$, which gets updated through the following dynamics:

* Pheromone update: At each time step, the pheromone level on each edge increases by the amount of flow present on the edge, and decays by a multiplicative factor of $\delta$:

\begin{equation}
p_{uv}(t) = \delta(p_{uv}(t-1) + \fflow{uv}(t-1) + \bflow{uv}(t-1))
\end{equation}

Note that while the flows are directional, the pheromone level present on an edge does not have any direction, and gets affected by the flows from both the directions.

* Flow movement: At each time step, the forward flow on an edge $(u, v)$ moves to the outgoing edges from $v$,  dividing itself based on a decision rule that depends on the pheromone levels on these edges. The simplest such rule divides the flow  proportional to the pheromone level on the outgoing edges. Formally, let $f_{{uv} \rightarrow {vw}}(t)$ denote the forward flow on edge $(v, w)$ at time $t$ that came from edge $(u, v)$. Then according to this rule,

\begin{equation}
f_{{uv} \rightarrow {vw}}(t) = \fflow{uv}(t-1)\frac{p_{vw}(t)}{\sum\limits_{z: (v, z) \in E} {p_{vz}(t)}}
\end{equation}

We call this decision rule the linear decision rule as it divides the flow proportional to the pheromone levels. All our positive results are for this particular rule. Our negative results are for a more general class of rules defined later.

Leakage: In addition, there is possible leakage of flow at each vertex $v$ governed by a leakage parameter $l_v \in [0, 1]$, such that $l_v$ fraction of flow passing through $v$ leaks out. When $l_v = 0$, the incoming flow through vertex $v$ at any time is equal to the outgoing flow. After accounting for leakage, the flow from $(u, v)$ to $(v, w)$ at time $t$ is given by:

\begin{equation}
f_{{uv} \rightarrow {vw}}(t) = (1-l_v) \ \fflow{uv}(t-1)\frac{p_{vw}(t)}{\sum\limits_{z: (v, z) \in E} {p_{vz}(t)}}
\end{equation}

The total forward flow on edge $(v, w)$ is the sum of all such incoming flows:

\begin{equation}
\fflow{vw}(t) = \sum\limits_{z: (z, v) \in E}
f_{{z v} \rightarrow {vw}}(t)
\end{equation}

The movement for backward flow takes place in exactly the same manner, with the direction of flow reversed. In this case, the backward flow $\bflow{uv}(t)$ on edge $(u, v)$ would depend on pheromone levels on the incoming edges at vertex $v$, and the leakage parameter $l_v$ remains the same for backward as well as forward flow. Formally, let $f_{{uv} \leftarrow {vw}}(t)$ denote the backward flow on edge $(u, v)$ at time $t$ that came from edge $(v, w)$.

\begin{equation}
f_{{uv} \leftarrow {vw}}(t) = (1 - l_v) \ \bflow{vw}(t-1)\frac{p_{uv}(t)}{\sum\limits_{z: (z, v) \in E} {p_{zv}(t)}}
\end{equation}

\begin{equation}
\bflow{uv}(t) = \sum\limits_{z: (u, v) \in E}
f_{{u v} \leftarrow {vz}}(t)
\end{equation}

The terminal edges $(s_0, s)$ and $(d, d_0)$ do not have any incoming forward and backward flows respectively. New forward flow $\fflow{s_0 s}(t)$ and backward flow $\bflow{dd_0}(t)$ appear on $(s_0, s)$ and $(d, d_0)$ respectively.

§ RESULTS

We describe our results in this section. In Section <ref>, we consider the dynamics for the linear decision rule when the graph consists of two parallel paths between the source vertex and the destination vertex. In this case, we show that when the incoming forward and backward flows do not change with time, the flow dynamics converge to the path with the minimum leakage. When the incoming forward and backward flows are increasing,  in the absence of leakage, the dynamics converge to the shortest path. This demonstrates that, at least in principle, ants have the ability to obtain information about path length by changing their flow rate.

These results raise several questions.  How important is the bi-directional nature of flow? How would the dynamics behave when we use some non-linear decision rule? We try to understand these questions in <Ref>.

First, we argue that bi-directional flow is indeed necessary for convergence to the shortest path or the minimum leakage path for any pheromone based decision rule. We then consider a very general family of decision rules. For this family, we argue that there is no advantage of using non-linear decision rules if the goal is to find the shortest or the minimum leakage path.

Flow dynamics for the linear decision rule converge to the path with the minimum leakage (shown by blue vertices) when the forward and backward flows do not change with time. Larger dots represent vertices with smaller leakage, and thickness of the green edges corresponds to the flow level. Notice that the paths with smaller leakage get pruned later.

The proofs of convergence in Section <ref> are for the case of parallel paths between the source and the destination vertices. How do the dynamics behave for more general graphs? In Section <ref>, using simulations, we demonstrate that our convergence results hold for general graphs drawn from various random graph models. Given the simplicity of the model, it is somewhat surprising that it is able to find the shortest path, or the path with the minimum leakage. Proving this convergence for general graphs is an important open problem. We discuss the major challenges in proving such a result in section <ref>.

§.§ Parallel paths with Linear Decision Rule

We show that when the incoming forward and backward flows do not change with time, the dynamics governed by the linear decision rule converge to the path with the minimum leakage. We prove this result for graphs consisting of two parallel paths from the source vertex to the destination vertex.  Here, for any path $P$, we define its leakage as $l_P = 1 - \Pi_{{v} \in P \setminus \{s,d\}} (1 - l_v)$. $l_P$ represents the fraction of flow that leaks out while moving through path $P$, when edges $(u, v) \in P$ are the only edges with positive pheromone level. [For convenience, we overload notation, and use $v \in P$ and $(u, v) \in P$ to denote the vertices and edges present on path $P$ respectively.] We use $len_P$ to denote the length of path $P$.

Our convergence results are in terms of normalized pheromone levels, where we show that the normalized pheromone level  for any edge on the path with minimum leakage tends to $1$. While the pheromone level on an edge has no associated direction, there is a forward and backward normalized pheromone level for each edge depending on whether the normalization is done with respect to the incoming edges or the outgoing edges. Formally, the normalized pheromone level is defined as follows:

\begin{equation}
\nfp{uv}(t) = \frac{p_{uv}(t)}{\sum\limits_{z: (u, z) \in E} p_{uz}(t)} \ \text{, } \
\nbp{uv}(t) = \frac{p_{uv}(t)}{\sum\limits_{z: (z, v) \in E} p_{zv}(t)}
\end{equation}

Consider a graph $G$ consisting of two parallel paths $P_1$ and $P_2$ from $s$ to $d$. Let $P_1 $ be the path with the minimum leakage such that $l_{P_1} < l_{P_2}$.  If (1) the incoming forward and backward flow values $\fflow{s}(t)$ and $\bflow{d}(t)$ are non-zero and unchanging with time, and (2) the initial pheromone level ${p}_{uv}(0)$ is positive for all edges $(u, v) \in P_1$, then the flow dynamics governed by the linear decision rule converges to a state in which the forward and backward normalized pheromone levels for any edge $(u, v) \in P_1$ tends to $1$. That is, $\nfp{uv}(t) \geq 1 - \epsilon$ and $\nbp{uv}(t) \geq 1 - \epsilon$, for all $t = \Omega\left(log \left(\frac{1}{\epsilon}\right)\right)$ and $(u, v) \in P_1$.

Here the $\Omega$ notation hides  terms dependent on $\delta$, the forward and backward flow levels, the initial pheromone levels, and length of the paths. The dependence on these terms can be found in the proof in <Ref>.

chandrasekhar2019better noticed in field observations that turtle ants favour paths which minimize the probability of getting lost. Our result in <Ref> suggests a plausible way in which ants converge to such paths.   Also, note that while we describe our model for unweighted graphs, it is general enough to captures the case with integral/rational edges lengths. For instance, an edge with length $k$ can be represented using $k$ unit length edges connected in series, with leakage at the nodes connecting these edges set to zero.

In <Ref>, we assumed that the incoming forward and backward flows do not change with time. Now we consider the effect of change in flow. We show that if the incoming forward and backward flows increasing with time, in the absence of leakage, the dynamics governed by the linear decision rule converge to the shortest path.

Consider a graph $G$ consisting of two parallel paths $P_1$ and $P_2$ from $s$ to $d$. Let $P_1$ be the shorter path such that $len_{P_1} < len_{P_2}$.  If  (1)  the initial pheromone levels ${p}_{uv}(0)$ is positive for all edges $(u, v) \in P_1$,
and (2) leakage $l_{P_1} = l_{P_2} = 0$, then the following is true:

* Exponential increase: When $\fflow{s}(t) = \alpha^t \fflow{s}(0)$ and $\fflow{d}(t) = \alpha^t \fflow{d}(0)$, for any  $\alpha > 1$,  we get $\nfp{uv}(t) \geq 1 - \epsilon$ and $\nbp{uv}(t) \geq 1 - \epsilon$, for all  $t = \Omega \left(log \left(\frac{1}{\epsilon}\right)  \right)$ and  $(u, v) \in P_1$.

* Linear increase: When $\fflow{s}(t) = \fflow{s}(0) + \alpha t$ and $\fflow{d}(t) = \fflow{d}(0) +\alpha t$, for any  $\alpha > 0$,  we get  $\nfp{uv}(t) \geq 1 - \epsilon$ and $\nbp{uv}(t) \geq 1 - \epsilon$, for all  $t = \Omega \left(  \left(\frac{1}{\epsilon} \right)^{C_{\delta, len_{P_2}}}\right) $ and $(u, v) \in P_1$. Here, $C_{\delta, len_{P_2}}$ is some constant dependent on $\delta$ and $len_{P_2}$.

Consider a graph $G$ consisting of two parallel paths $P_1$ and $P_2$ from $s$ to $d$. Let $P_1$ be the shorter path such that $len_{P_1} < len_{P_2}$.  If
(1)  the initial pheromone levels ${p}_{uv}(0)$ is positive for any edge $(u, v) \in P_1$,
and (2) leakage $l_{P_1} = l_{P_2} = 0$, and (3) $\fflow{s}(t)$ and $\bflow{d}(t)$ are monotonically increasing with $t$, such that
$$\lim_{t \rightarrow \infty} \fflow{s}(t) = \infty, \ \ \lim_{t \rightarrow \infty} \bflow{d}(t) = \infty, \ \frac{\fflow{s}(t)}{\bflow{d}(t - len_{P_2})} \leq c, \  \frac{\bflow{d}(t)}{\bflow{s}(t - len_{P_2})} \leq c$$

where $c$ is some constant independent of $t$ but possibly dependent on  $len_{P_2}$,    then the flow dynamics governed by the linear decision rule converges to a state in which the forward and backward normalized pheromone levels for any edge $(u, v) \in P_1$ tends to $1$. In particular, the following is true:

* Exponential increase: When $\fflow{s}(t) = \alpha^t \fflow{s}(0)$ and $\fflow{d}(t) = \alpha^t \fflow{d}(0)$, for some $\alpha > 1$,  the above conditions are satisfied, and we get  $\nfp{uv}(t) \geq 1 - \epsilon$ and $\nbp{uv}(t) \geq 1 - \epsilon$, for all  $t \geq O \left(log \left(\frac{1}{\epsilon}\right) \alpha^{len_{P_2}}  \right)$ and  $(u, v) \in P_1$.

* Linear increase: When $\fflow{s}(t) = \fflow{s}(0) + \alpha t$ and $\fflow{d}(t) = \fflow{d}(0) +\alpha t$, for some $\alpha > 0$,  the above conditions are satisfied, and we get  $\nfp{uv}(t) \geq 1 - \epsilon$ and $\nbp{uv}(t) \geq 1 - \epsilon$, for all  $t \geq O  \left(\frac{{len_{P_2}}}{\epsilon}\right) $ and $(u, v) \in P_1$.

Again, the $\Omega$ notation hides the terms dependent on $\delta$, the forward and backward flow levels, the initial pheromone levels, and length of the paths. The dependence on these terms can be found in the proof in <Ref>.

Previous studies have shown that Argentine ants are capable of finding the shortest path in certain simple graphs goss1989self. We also know that factors such as detection of new food sources can positively reinforce the rate of flow of ants deneubourg1986random,gordon2012dynamics. <Ref> suggests a possible connection between these two
phenomena. It would be fascinating to explore experimentally whether certain ant species actually change their flow rates to find short paths.

§.§ General Rules and Fundamental Limits

In the previous subsection, we showed that for  graphs with two parallel paths, bidirectional flow with linear decision rule converges to the path with the minimum leakage when the flow is fixed, and to the shortest path when the flow is increasing and there is no leakage. This raises several questions: How crucial is the bidirectional nature of the flow? How do the dynamics behave when the decision rule is non-linear? How important is the increase in flow for converging to the shortest path? For instance, is it possible that with some non-linear decision rule, the dynamics can converge to the shortest path even without any change in flow? We understand the answer to these questions in this subsection.

Necessity of bi-directional flow.
We show that bi-directional flow is indeed necessary to find the path with minimum leakage or the shortest path. This result holds independent of the decision rule, leakage levels and the change in flow level; we formally state this result next. Let $\mathcal{G}$ be the set of all pheromone based rules that  distribute the forward (backward) flow at any vertex, onto the outgoing (incoming) edges based on their pheromone levels.

Bi-directional flow is necessary for all pheromone based rules in the class $\mathcal{G}$ to guarantee convergence to the shortest path or path with the minimum leakage.

The idea behind this result is straightforward. Without loss of generality, let us assume there is one way flow from $s$ to $d$. In this case, the pheromone level on the edges incident on $s$ is only a function of the forward flow at $s$ and does not get affected by the properties of the rest of the graph. Therefore, in the case of two parallel paths, for a given decision rule and initial setting of the pheromone levels, if the dynamics converge to a particular path, then they will converge to the other path if we swap the initial pheromone level on the two edges incident on $s$.

The conflict between leakage, change in flow and non-linearity.
To understand the dynamics for other decision rules beyond the linear rule, we consider a very general family of decision rules for the case of two parallel paths. These rules essentially distribute the forward (backward) flow among the outgoing (incoming) edges of any vertex, based on the normalized pheromone levels at these edges. We assume that these rules are continuous in the sense that a small change in the pheromone level will not lead to a large change in the proportions of the flow distributed. We also assume that these rules are monotone in the sense that increasing the normalized pheromone level at any edge will never decrease the proportion of flow entering that edge. As both these properties seem reasonable, the class of rules considered is sufficiently general.

More formally, we consider the family of rules given by functions $g:[0,1/2] \rightarrow [0,1] \in \setflb$. For any vertex with out-degree (in-degree) $1$, these rules send the forward (backward) flow to the next (previous) vertex, just as in the case of linear rules. For any vertex with out-degree (in-degree) $2$,   these rules use the function $g:[0,1/2] \rightarrow [0,1]$, which takes the minimum of the  normalized pheromone levels on the two outgoing (incoming)  edges, and returns the fraction of the forward (backward) flow on the edge with minimum pheromone level. We assume that  $g$ is monotonically increasing, that is, $g(x) \leq g(x')$ for all  $x \leq x'$. Further, $g$ satisfies $g(0)=0$ and $g(1/2)=1/2$. This condition says that if one of the edges has $0$ normalized pheromone, we do not send any flow on it, and if both the edges have equal pheromone level, then we send equal flow on them.

* The rule $g$ is symmetric, that is, the same rule apply to both $s$ and $d$.

* The rule $g:[0,1/2] \rightarrow [0,1]$ is pheromone ratio based, meaning at all time steps it takes the minimum of the two normalized pheromone levels on edges belonging to the two paths and returns the fraction of the flow on the minimum edge.

* The rule $g$ is monotonically non-decreasing, meaning $g(x) \leq g(x')$ for all $x,x' \in [0,1/2]$ and $x \leq x'$. Further, $g$ satisfies $g(0)=0$ and $g(1/2)=1/2$.

Note that the linear decision rule studied in previous subsection belongs to $\setflb$, and corresponds to $g(x) = x$.

We try to understand the dynamics when the decision rule belongs to the above class and is non-linear. We show that non-linearity hinders the convergence of the dynamics to paths with minimum leakage or the shortest path. In particular, we show that for every non-linear rule $g \in \setflb$, there exists a setting of leakage in which the dynamics fail to converge to the path with minimum leakage.

Consider any graph $G$ consisting of two parallel paths from $s$ to $d$. When the incoming forward and backward flows are fixed, for every non-linear decision rule $g \in \setflb$, there exists a setting of leakage parameter dependent on $g$, such that the dynamics do not converge to the path with the minimum leakage.

Similarly, we show an analogous result for the increasing flow case with no leakage.

Consider  any graph $G$ consisting of two parallel paths from $s$ to $d$ with a unique shortest path. When the leakage is zero for all the vertices, for every non-linear decision rule $g \in \setflb$, there exists a setting where the incoming forward and backward flows increase by a fixed multiplicative factor at each time, such that the dynamics do not converge to the shortest path. This multiplicative factor is chosen as a function of $g$.

From the last subsection, we can view increasing flow and leakage as two possibly conflicting forces, the former preferring paths with small leakage and the latter preferring the shorter paths.  The above results suggest that non-linearity in the decision rule can be viewed as another force, possibly in conflict with the forces of leakage and increasing flow, preferring certain states that may not correspond to the shortest path or the path with the minimum leakage. In this sense, if the goal is to find the path with minimum leakage or the shortest path, there is no advantage of using non-linear decision rules over the linear decision rule.

Note that these results only suggest that linear decision rule is necessary for guaranteed convergence to the shortest or the minimum leakage path. It is still possible that even for non-linear decision rules, for certain graph families, the forces of increasing flow and leakage never
nudge the dynamics towards longer or higher leakage paths respectively. That is, the path found in the presence of these forces has length (respectively leakage) at least as small, and sometimes smaller, than the length (respectively leakage) of the path found in their absence. This would demonstrate the utility of leakage and increasing flow in finding such desirable paths even for non-linear decision rules.  Understanding when such a statement holds is another interesting open direction.

For a dynamics governed by $g$ with fixed flow and no leakage on both the paths. For any $r\in S_{g}$, if the initial flows on all the edges in path $P_1$ are $r$ and $1-r$ for $P_2$. Then the state where the normalized flow and pheromone level on edges $(s,s_1)$ and $(d,d_1)$ equal to $r$ is an equilibrium state.

For the flow dynamics on a directed graph $G(V,E)$, we already defined the normalized pheromone levels on an edge $(u,v)\in E$ at time $t$ and we use $\pft,\pbt \in \R^{E}$ to denote the vector of these normalized pheromone levels. We next define the normalized pheromone levels on an edge $(u,v) \in E$ as follows:

\begin{equation}
\nfflow{uv}(t) = \frac{\fflow{uv}(t)}{\sum\limits_{z: (u, z) \in E} \fflow{uz}(t)} \ \text{, } \
\nbflow{uv}(t) = \frac{\bflow{uv}(t)}{\sum\limits_{z: (z, v) \in E} \bflow{zv}(t)}
\end{equation}

Let $\ft,\bt \in \R^{E}$ denote the vector of the normalized pheromone levels on the edges $E$.

§.§ Beyond Parallel Paths

We showed that the dynamics converge to the path with the minimum leakage, and the shortest path in Theorem <ref> and <ref> respectively, for the case of parallel paths between the source and the destination. How do the dynamics behave for general graphs? To understand this, we ran simulations on random graphs with linear decision rule, and observed the same behaviour (see Figure <ref>). In all the simulated instances, the dynamics converge to the path with minimum leakage when the forward and backward flow at the source and destination does not change with time. When the forward and backward flow is increasing, in the absence of leakage, the dynamics converges to the shortest path.

We ran the simulations for three kinds of directed graphs: graphs sampled from the $G(n, p)$ model, graphs sampled from  the $G(n, p)$ model with the additional constraint that an edge can exist between vertex $i$ and $j$ only if $|i - j| \leq k$ for some parameter $k$ (with the source and the destination vertex numbered 1 and $n$ respectively), and the grid graph. $G(n, p)$ model with the additional constraint ensures that the graph has long paths between the source and the destination. We generated a large number of instances with different values for $n$, $p$, $k$ and other parameters, and observed the desired convergence in all the simulated instances. More details about the simulations can be found in Appendix <ref>.

These simulations suggest that the dynamics of our model converge to the path with the minimum leakage or the shortest path for general graphs. Proving this in a worst or average-case sense is an important open problem for future work.

Despite the apparent simplicity of our model, understanding its dynamics is surprisingly non-trivial. Even in the seemingly simple case of parallel paths, the proof of convergence requires a carefully constructed potential function. In this case, we saw that change in flow and leakage are two possibly conflicting forces, the former preferring paths with less leakage and the latter preferring shorter paths. In the case of general graphs, even if we assume that the flow is not changing at the source vertex and the destination vertex, it can still change at the other vertices. It is not clear how to analyze the interaction between the two forces of leakage and change in flow at these vertices, making it significantly more challenging to understand the dynamics for general graphs.

§ PROOF OVERVIEW

In this section, we describe the the proof ideas for various theorems. We give the complete proofs in Appendix.

§.§ Linear Decision Rule with Leakage

For a graph consisting of two parallel paths $P_1$ and $P_2$, with $l_{P_1} < l_{P_2}$, we show in <Ref> that the dynamics converge to the path $P_1$ when the incoming forward and backward flow values are fixed. Less leakage on $P_1$ ensures that relatively more pheromone accumulates on it with time.

Let $s_1$ and $s_2$ be the neighboring vertices of $s$, and $d_1$ and $d_2$ be the neighboring vertices of $d$, on path $P_1$ and $P_2$ respectively. Note that only the pheromone level on edges $(s, s_1), (s, s_2), (d_1, d), (d_2, d)$ affect the dynamics for this graph.  To get some intuition, it is instructive to consider the ratio of pheromone levels on $(s, s_1)$ and $(s, s_2)$ at time $(t+1)$:

\begin{align}
\frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1)} &= \frac{\delta(p_{ss_1}(t) + \fflow{ss_1}(t)  + \bflow{ss_1}(t))}{\delta(p_{ss_2}(t) + \fflow{ss_2}(t)  + \bflow{ss_2}(t))}\\
&= \frac{p_{ss_1}(t) + \fflow{ss_1}(t)  + (1 - l_{P_1})\bflow{d_1d}(t- len_{P_1}+1)}{p_{ss_2}(t ) + \fflow{ss_2}(t)  + (1 - l_{P_2})\bflow{d_2d}(t - len_{P_2}+1)}
\end{align}

Here, $len_{P_1}$ and $len_{P_2}$ represent the lengths of path $P_1$ and $P_2$. Now, note that the forward flow at $s$ divides itself in the ratio of pheromone at $(s, s_1)$ and $(s, s_2)$,
$\frac{\fflow{ss_1}(t)}{\fflow{ss_2}(t)} = \frac{p_{ss_1}(t)}{p_{ss_2}(t)}$. Therefore,
the forward flows $\fflow{ss_1}$ and $\fflow{ss_2}$ do not affect the ratio of the pheromone levels $\frac{p_{ss_1}}{p_{ss_2}}$. The relationship between $\frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1)}$ and $\frac{p_{ss_1}(t)}{p_{ss_2}(t)}$ is governed by the backward flow coming from $d$. Since leakage $l_{P_1} < l_{P_2}$, the $(1 - l_{P_1})$ and $(1 - l_{P_2})$ terms would ensure $\frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1)} > \frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1) }$, if $\frac{\bflow{d_1d}(t- len_{P_1}+1)}{\bflow{d_2d}(t - len_{P_2}+1)} \geq \frac{p_{ss_1}(t)}{p_{ss_2}(t)}$. However, this is not true in general, and the ratio of pheromone levels $p_{ss_1}$ and $p_{ss_2}$ does not increase monotonically with time. As the lengths of the two paths can be different, directly analysing the trajectory of the ratio of pheromone level becomes tricky even for this seemingly simple case.

To get past this obstacle, we consider a potential function  given by the minimum of the ratio of the pheromone levels $\frac{p_{ss_1}(t)}{p_{ss_2}(t)}$ and $\frac{p_{d_1d}(t)}{p_{d_2d}(t)}$ across the last $max(len_{P_1}, len_{P_2})$ time steps. Let $r_{ss_1}(t) \defeq \frac{p_{ss_1}(t)}{p_{ss_2}(t)}$, $r_{ss_2}(t) \defeq \frac{p_{d_1d}(t)}{p_{d_2d}(t)}$, and $L \defeq max(len_{P_1}, len_{P_2})$. Our potential function is given by

$$r_{min}(t) \defeq min\{r_{ss_1}(t), r_{ss_1}(t-1), \cdots, r_{ss_1}(t-L+1), r_{d_1d}(t), r_{d_1d}(t-1), \cdots, r_{d_1d}(t-L+1)   \} $$

From the definition, we know that $\frac{\fflow{ss_1}(t)}{\fflow{ss_2}(t)} = \frac{p_{ss_1}(t)}{p_{ss_2}(t)} = r_{ss_1}(t) \geq r_{min}(t)$. Further, it is not hard to see that $\bflow{d_1d}(t- len_{P_1}+1) \geq  \frac{\bflow{d} r_{min}(t)}{1+r_{min}(t)}$, and $\bflow{d_2d}(t- len_{P_2}+1) \leq  \frac{\bflow{d} }{1+r_{min}(t)}$, which implies $\frac{\bflow{d_1d}(t- len_{P_1}+1)}{\bflow{d_2d}(t- len_{P_2}+1)} \geq r_{min}(t)$. These inequalities give us

\begin{align}
\frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1)} &\geq r_{min}(t)\frac{p_{ss_2}(t) + \fflow{ss_2}(t)  + (1 - l_{P_1})\bflow{d_2d}(t- len_{P_2}+1)}{p_{ss_2}(t ) + \fflow{ss_2}(t)  + (1 - l_{P_2})\bflow{d_2d}(t - len_{P_2}+1)}\\
&> r_{min}(t)
\end{align}

where we used $l_{P_1} < l_{P_2}$ for the last inequality. This gives us $\frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1)} = r_{ss_1}(t+1) > r_{min}(t)$. Similarly, we can show $r_{d_1d}(t+1) > r_{min}(t)$. This implies that $r_{min}(t)$ never decreases and strictly increases every $L$ time steps. In <Ref>, we show that this increase is at least by a factor of $(1+c)$ for some constant $c > 0$. This implies the convergence of the dynamics to path $P_1$.

§.§ Linear Decision Rule with Increasing Flow

For a graph consisting of two parallel paths $P_1$ and $P_2$, with $len_{P_1} < len_{P_2}$, we show in <Ref> that the dynamics converge to the path $P_1$ when the incoming forward and backward flow values increase by a multiplicative or additive factor with time.
Again, consider the ratio of pheromone levels on $(s, s_1)$ and $(s, s_2)$ at time $t+1$:

\begin{align}
\frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1)}
&= \frac{p_{ss_1}(t) + \fflow{ss_1}(t)  + (1 - l_{P_1})\bflow{d_1d}(t- len_{P_1}+1)}{p_{ss_2}(t ) + \fflow{ss_2}(t)  + (1 - l_{P_2})\bflow{d_2d}(t - len_{P_2}+1)}
\end{align}

Setting leakage $l_{P_1} = l_{P_2} = 0$, and writing the backward flow in terms of normalized pheromone level, we get:

\begin{align}
\frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1)}
&= \frac{p_{ss_1}(t) + \fflow{ss_1}(t)  + \bflow{d}(t- len_{P_1}+1) \nbp{d_1d}(t - len_{P_1}+1)}{p_{ss_2}(t ) + \fflow{ss_2}(t)  + \bflow{d}(t - len_{P_2}+1)\nbp{d_2d}(t - len_{P_2}+1)}
\end{align}

For simplicity, let us assume $\bflow{d}(t) = \alpha^t$, for some $\alpha > 1$. This gives

\begin{align}
\frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1)}
&= \frac{p_{ss_1}(t) + \fflow{ss_1}(t)  + \alpha^{(t - len_{P_1}+1)} \nbp{d_1d}(t - len_{P_1}+1)}{p_{ss_2}(t ) + \fflow{ss_2}(t)  + \alpha^{(t - len_{P_2}+1)}\nbp{d_2d}(t - len_{P_2}+1)}
\end{align}

As $len_{P_1} < len_{P_2}$, we get $\alpha^{(t - len_{P_1}+1)} > \alpha^{(t - len_{P_2}+1)}$. $\alpha^{(t - len_{P_1}+1)}$ and $\alpha^{(t - len_{P_2}+1)}$ terms would ensure  $\frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1)} > \frac{p_{ss_1}(t+1)}{p_{ss_2}(t+1) }$, if $\frac{\nbp{d_1d}(t- len_{P_1}+1)}{\nbp{d_2d}(t - len_{P_2}+1)} \geq \frac{p_{ss_1}(t)}{p_{ss_2}(t)}$. However, this is not true in general, and the ratio of pheromone levels $p_{ss_1}$ and $p_{ss_2}$ does not increase monotonically. To get past this obstacle, similar to the proof for leakage with fixed flow case, we consider the potential function $r_{min}(t)$, given by the minimum of the ratio of the pheromone levels $\frac{p_{ss_1}(t)}{p_{ss_2}(t)}$ and $\frac{p_{d_1d}(t)}{p_{d_2d}(t)}$ across the last $max(len_{P_1}, len_{P_2})$ time steps. We show that this potential function never decreases and increases sufficiently every $max(len_{P_1}, len_{P_2})$ time steps.

§.§ Understanding Other Decision Rules

Here we provide the proof sketch for all the results stated in <Ref>.

In <Ref>, we show that the bi-directional flow is necessary for any pheromone based rule $g \in \mathcal{G}$ for it to converge to the shortest or the minimum leakage path. The proof of this result is straightforward. Without loss of generality, let us assume there is one way flow from $s$ to $d$. In this case, the pheromone level on the edges incident on $s$ is only a function of the forward flow at $s$ and does not get affected by the properties of the rest of the graph. Therefore, in the case of two parallel paths, for a given decision rule and initial setting of the pheromone levels, if the dynamics converge to a particular path, then they will converge to the other path if we swap the initial pheromone level on the two edges incident on $s$.

In the remainder of this section we provide a proof sketch for <Ref> and <Ref>. The proofs for both these results are quite similar and here we provide the intuition for just the <Ref>. For any $g \in \setflb$, consider some $r\geq 0$  such that $g(r)\neq r$. Such an $r$ exists because $g$ is non-linear. Further, as $g$ is continuous, there exists an $\epsilon >0$ such that for all $0<s\leq \epsilon$ one of the following two conditions holds: 1) $g(r+s)< r+s$, 2)$g(r+s)>r+s$. Suppose $g$ is such that $g(r+s)< r+s$ for all
$0<s\leq \epsilon$, then consider the instance where the initial normalized pheromone level and flow values on the edges of the top (minimum leakage) path are at most $r+\epsilon$ and bottom path are at least $1-r-\epsilon$. The decision rule $g$ sends at most $r+\epsilon-c_{g,\epsilon}$ (because $g(r+\epsilon)< r+\epsilon$ and $g$ is monotone) amount of forward and backward flow on the top path and at least $1-r-\epsilon+c_{g,\epsilon}$ on the bottom path, where $c_{g,\epsilon}$ is a fixed positive constant dependent on $g$ and $\epsilon$. Therefore, we can choose the leakage parameter for the two paths carefully such that the normalized pheromone level and flow levels on the top path remain at most $r+\epsilon$ throughout the future; therefore never converging to the top or the minimum leakage path. The intuition for the second case $g(r+s)> r+s$ for all $0<s\leq \epsilon$ is similar. In this case we assign the normalized pheromone level and flow values of $r+\epsilon$ on the bottom path (maximum leakage path). The rule $g$ in this case sends at least $r+\epsilon+c_{g,\epsilon}$ (because $g(r+\epsilon)> r+\epsilon$ and $g$ is monotone) amount of flow on the bottom path. The presence of the additive term $c_{g,\epsilon}$ helps ensure that the normalized pheromone level and the flow on this path never falls below $r+\epsilon$; thus the dynamics never converge to the minimum leakage path.

§ ACKNOWLEDGEMENTS

We are thankful to the anonymous reviewers for their helpful comments. Moses Charikar was supported by a Simons Investigator Award, a Google Faculty Research Award and an Amazon Research Award. Shivam Garg was supported by NSF awards AF-1813049 and AF-1704417, and a Stanford Interdisciplinary Graduate Fellowship. Deborah M. Gordon was supported the  Templeton Fund.
Kirankumar Shiragur was supported by a Stanford Data Science Scholarship and a Dantzig-Lieberman Operations Research Fellowship.

§ DISCUSSION AND OPEN DIRECTIONS

Remove this section or add it in organization
We propose a simple and biologically plausible model of ant foraging, as bidirectional flow in a graph with pheromone accumulation on the edges that guides the future flow, and  possible leakage of flow on the vertices. Despite the simplicity of the model, we observe that it's dynamics end up discovering paths with desirable properties — the one with the minimum leakage or the the shortest path.

* Analysing the dynamics for general graphs: While our analysis is for the case of parallel paths, our simulation results suggest that the dynamics of our model converge to the path with the minimum leakage or the shortest path for more general graphs. Can we prove that for general graphs

* Generalizations such as repellent flow?

* Analysis when the flow is discrete.

* Other variations in flows? Cyclic flows?

* More accurate models of leakage, and exploration?

* Potential applications in distributed systems?

* Other systems with bidirectional flow? Gossip spreading?

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

journaltitlearXiv preprint arXiv:1607.05127
titleNear-optimal approximate shortest paths and transshipment in distributed and streaming models

booktitleProceedings of the 4th conference on Innovations in Theoretical Computer Science
titleOn the convergence of the Hegselmann-Krause system

journaltitleJournal of theoretical biology
titlePhysarum can compute shortest paths

Rand Corporation

titleStudies in the Economics of Transportation

titlePhysarum Multi-Commodity Flow Dynamics

Nature Publishing Group

journaltitleScientific reports
titleA distributed algorithm to maintain and repair the trail networks of arboreal ants

Cold Spring Harbor Laboratory

titleBetter tired than lost: turtle ant trail networks favor coherence over shortest paths

booktitleProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms
titleNatural algorithms

booktitle2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
titleThe dynamics of influence systems

Nature Publishing Group

titleEffective leadership and decision-making in animal groups on the move

The Royal Society London

journaltitleJournal of the Royal Society Interface
titleRandom walk models in biology

journaltitleProbability Theory and Related Fields
titleReinforced random walk

journaltitleTheoretical computer science
titleAnt colony optimization theory: A survey

titleDistributed optimization by ant colonies

journaltitlePhysica D: nonlinear phenomena
titleRandom behaviour, amplification processes and number of participants: how they contribute to the foraging properties of ants

journaltitleThe Annals of Probability
titlede Finetti's theorem for Markov chains

booktitle2001 WSES International Conference on Evolutionary Computation (EC’01)
titleAn experimental study of the simple ant colony optimization algorithm

booktitleProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
titleDistributed exact shortest paths in sublinear time

booktitleProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
titleImproved distributed algorithms for exact shortest paths

Public Library of Science

journaltitlePLoS One
titleThe dynamics of foraging trails in the tropical arboreal ant Cephalotes goniodontus

journaltitleCell systems
titleThe evolution of the algorithms for collective behavior

titleSelf-organized shortcuts in the Argentine ant

titleAnt Colony Optimization: A Component-Wise Overview.

titleDistributed algorithms

Hokkaido University, Department of Mathematics

journaltitleHokkaido Mathematical Journal
titleMathematical analysis to an adaptive network of the plasmodium system

journaltitleInternational Journal of Pure and Applied Mathematics
titlePhysarum can solve the shortest path problem on riemannian surface mathematically rigourously

John Wiley & Sons, Ltd Chichester, UK

journaltitleMolecular systems biology
titleAlgorithms in nature: the convergence of systems biology and computational thinking

Nature Publishing Group

titleMaze-solving by an amoeboid organism

The Institute of Mathematical Statistics
the Bernoulli Society

journaltitleProbability surveys
titleA survey of random processes with reinforcement

ACM New York, NY, USA

journaltitleJournal of the ACM (JACM)
titleHow bad is selfish routing?

The Royal Society

journaltitlePhilosophical Transactions of the Royal Society B: Biological Sciences
titleStochastic modelling of animal movement

journaltitleSIAM Journal on Applied Mathematics
titleAggregation, blowup, and collapse: the ABC's of taxis in reinforced random walks

journaltitlearXiv preprint arXiv:1601.02712
titleIRLS and slime mold: Equivalence and convergence

booktitleProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms
titleNatural algorithms for flow problems

journaltitleJournal of theoretical biology
titleA mathematical model for adaptive transport network in path finding by true slime mold

Thomas Telford-ICE Virtual Library

journaltitleProceedings of the institution of civil engineers
titleSome theoretical aspects of road traffic research.

§ PROOF OF CONVERGENCE

Here we provide proof for all the results stated in <Ref>.

§ CHARACTERIZATION OF OTHER RULES

Here we prove the results stated in <Ref> and for convenience we recall the definition of $\setflb$. Let $\setflb$ be the set of all symmetric, continuous, monotone, pheromone ratio based rules on the 2 parallel path graph; formally any $g \in \setflb$ satisfy the following:

* The rule $g$ is symmetric, that is, the same rule apply to both $s$ and $d$.

* The rule $g:[0,1/2] \rightarrow [0,1]$ is pheromone ratio based, meaning at all time steps it takes the minimum of the two normalized pheromone levels on edges belonging to the two paths and returns the fraction of the flow on the minimum edge.

* The rule $g$ is monotonically non-decreasing, meaning $g(x) \leq g(x')$ for all $x,x' \in [0,1/2]$ and $x \leq x'$. Further, $g$ satisfies $g(0)=0$ and $g(1/2)=1/2$.

§.§ Proof for the bidirectional flow lower bound (<Ref>)

In our proof, we show that the result holds even for the case of graphs with two paths $P_1$ and $P_2$ from $s$ to $d$. In the rest of the proof we assume that the two paths $P_1$ and $P_2$ are either of different lengths or have different leakage values.

As the flow is one sided and the dynamics at any vertex is just based on the pheromone levels of the incident edges, we get that $\psso(t)$ is some function $F$ of the following parameters,

$$\psso(t) = F(\psso(0),\psst(0) \dots \psso(t-1),\psst(t-1),\fflow{s}(0),\dots \fflow{s}(t-1))~.$$

Given $(\psso(0),\psst(0))$, and $\fflow{s}(t)$ for all $t \geq 0$, let the dynamics converge to $P_1$.  Suppose we swap the initial pheromone level on the two edges incident to $s$, then note that the dynamics would converge to $P_2$ in this case. Therefore one of these two initial pheromone levels does not converge to the minimum leakage or the shortest path and we conclude the proof.

§.§ Proof for the leakage lower bound (<Ref>)

For notational convenience, we define $\alpha=1-l_{P_1}$ and $\beta=1-l_{P_2}$. Without loss of generality we assume $P_{1}$ to be the path of minimum leakage and therefore we let $\alpha \geq \beta$. Let $n,m$ be the number of vertices between $s$ and $d$ on the top and bottom path respectively. We name the vertices from left to right on the top path by $v_{0}$ to $v_{n+1}$ and the bottom path by $u_0$ to $u_{m+1}$, with the convention $v_0=u_0=s$ and $v_{n+1}=u_{m+1}=d$. We divide the analysis into two cases.

For any $g \in \setflb$, let $r\geq 0$ be any $x \in (0,1/2)$ such that $g(x)\neq x$. For such an $r$, there exists an $\epsilon >0$ such that  $r+\epsilon<1/2$ and for all $0<s\leq \epsilon$ one of the following two conditions holds:

* $g(r+s)< r+s$.

* $g(r+s)>r+s$.

Case 1: Suppose $g(r+s)< r+s$, then pick the following initial configuration:

* Assign pheromone value on the edges $(s,v_1),(s,u_1), (d,v_n),(d,u_m)$ such that the normalized pheromone level on $(s,v_1),(d,v_n)$ is $\leq r+\epsilon$. Further assign the flow values on the edges such that they satisfy the following,

\begin{equation}
\fflow{v_{i}v_{i+1}}(0) \leq \fflow{s} (r+\epsilon)\prod_{j \leq i} (1-l_{v_{j}}) \text{ and }\bflow{v_{i}v_{i+1}}(0) \leq \fflow{d} (r+\epsilon)\prod_{j \geq i+1} (1-l_{v_{j}})
\end{equation}

\begin{equation}
\fflow{u_{i}u_{i+1}}(0) \geq \fflow{s} (1-r-\epsilon)\prod_{j \leq i} (1-l_{u_{j}}) \text{ and }\bflow{u_{i}u_{i+1}}(0) \geq \fflow{d} (1-r-\epsilon)\prod_{j \geq i+1} (1-l_{u_{j}})~.
\end{equation}

* Let the leakage values at each node be such that the parameters $\alpha$ and $\beta$ satisfy the following inequality,
$\frac{\lo}{\lt} \leq 1+ c_{g} \frac{\fflow{s}}{\bflow{d}}$, where $c_{g}\defeq \cue/4$ and $\cue \defeq (r+\epsp)-g(r+\epsp)>0$. Note that $c_{g}=0$ iff $g$ is the linear rule.  As the forward and backward flows are fixed, the above constraint on the leakage parameters only depend on $g$ and therefore satisfy the conditions of the lemma.

We show by induction that the above inequalities hold for all time $t\geq 0$ and therefore the system does not converge to the minimum leakage path.

Hypothesis: At time $t\geq 0$, pheromone values on the edges $(s,v_1),(s,u_1), (d,v_n),(d,u_m)$ are such that the normalized pheromone level on $(s,v_1),(d,v_n)$ is $\leq r+\epsilon$. Further the flow values on the edges satisfy the following,

\begin{equation}
\fflow{v_{i}v_{i+1}}(t) \leq \fflow{s} (r+\epsilon)\prod_{j \leq i} (1-l_{v_{j}}) \text{ and }\bflow{v_{i}v_{i+1}}(t) \leq \fflow{d} (r+\epsilon)\prod_{j \geq i+1} (1-l_{v_{j}})
\end{equation}

\begin{equation}
\fflow{u_{i}u_{i+1}}(t) \geq \fflow{s} (1-r-\epsilon)\prod_{j \leq i} (1-l_{u_{j}}) \text{ and }\bflow{u_{i}u_{i+1}}(t) \geq \fflow{d} (1-r-\epsilon)\prod_{j \geq i+1} (1-l_{u_{j}})~.
\end{equation}

Base case: The conditions trivially hold at time $0$ because of the initial configuration provided by the conditions of the lemma.

Induction Step: To prove the hypothesis for time $t+1$, all we need to show is that, $\npsso(t+1),\npddo \leq r+\epsp$, $\fflow{v_0v_1}(t+1)=\fflow{ss_1}(t+1) \leq \fflow{s} \cdot (r+\epsp)$ and $\bflow{v_{n}v_{n+1}}(t+1)=\bflow{d_1d}(t+1) \leq \bflow{d} \cdot (r+\epsilon)$; all the remaining inequalities follows from these basic inequalities. Also note that from the definition of our case, that is $g(r+s)<r+s$ for all $s \leq \epsilon$, we get that the inequalities $\npsso(t+1),\npddo(t+1) \leq r+\epsp$ further imply the following,

$$\fflow{ss_1}(t+1) = \fflow{s} \cdot g(\npsso(t+1)) \leq  \fflow{s}\cdot g(r+\epsp) < \fflow{s}\cdot(r+\epsp)~,$$

and similarly,

$$\bflow{d_1d}(t+1) < \bflow{d} (r+\epsilon)~.$$

Therefore it is enough to show that $\npsso(t+1),\npddo(t+1) \leq r+\epsp$. As the proof for the bound on $\npddo(t+1)$ is analogous to that of $\npsso(t+1)$, in the remainder we focus our attention towards the proof for $\npsso(t+1)$. Recall the definition of $\npsso(t+1)$,

\begin{align}
\npsso(t+1)=\frac{\psso(t+1)}{\psso(t+1)+\psst(t+1)} &= \frac{ \psso(t) +
\fsso(t) +  \fsos(t)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)}
\end{align}

We know by the induction step that,

\begin{align}\label{eq:P41}
\frac{\psso(t)}{\psst(t)+\psso(t)} < r+\epsp~.
\end{align}

Also note that,

\begin{equation}\label{eq:P42}
\frac{\fsos(t)}{ \fsts(t)+\fsos(t)} \leq \frac{\alpha}{\beta}(r+\epsp)~.
\end{equation}

In the above we used the monotonically non-decreasing property of $x/(1+x)$ and the conditions provided by the induction step at time $t$, that is $\fsos(t)\leq \bflow{d} \cdot (r+\epsp) \cdot \alpha$ and $\fsts(t)\geq \bflow{d} \cdot (1-r-\epsp)\cdot \beta$.

Recall the definition of $\cue$ and note that we also have the following upper bound on the flow value,

\begin{equation}\label{eq:P43}
\fsso(t) = \fflow{s} \cdot g(\npsso(t)) \leq  \fflow{s}\cdot g(r+\epsp) \leq \fflow{s}\cdot(r+\epsp-\cue)~,
\end{equation}

Using these bounds, we provide an upper bound for the normalized pheromone level.

\begin{align}
\npsso(t+1)&= \frac{ \psso(t) +
\fsso(t) +  \fsos(t)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
& \leq (r+\epsp)+\frac{(\frac{\lo}{\lt}-1)(r+\epsp)(\fsts(t)+\fsos(t))+
\left( \fsso(t)-(r+\epsp)(\fsso(t) +  \fsst(t))\right)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
& \leq (r+\epsp)+\frac{(\frac{\lo}{\lt}-1)2 \bflow{d}+
\left( \fsso(t)-(r+\epsp)\cdot \fflow{s}\right)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
& \leq (r+\epsp)+\frac{(\frac{\lo}{\lt}-1)2 \bflow{d}+
\fflow{s}\left( r+\epsp-\cue-r-\epsp\right)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
& \leq (r+\epsp)+\frac{(\frac{\lo}{\lt}-1)2 \bflow{d}-\cue
\fflow{s}}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
&\leq (r+\epsp)-\frac{\frac{1}{2}\cue
\fflow{s}}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)}~,\\
&\leq (r+\epsp)~.
\end{align}

In the second inequality we used <Ref>. In the third inequality we used $r+\epsilon<1$ and $\fsts(t),\fsos(t) \leq \bflow{d}$, $\fsso(t) +  \fsst(t) \leq \fflow{s}$ inequalities. In the fourth inequality we used <Ref>.
The sixth inequality holds because $(\frac{\lo}{\lt}-1)2 \bflow{d} \leq \frac{1}{2}\cue \fflow{s}$, which is equivalent to $\frac{\lo}{\lt} \leq 1+ \cue \frac{\fflow{s}}{4\cdot \bflow{d}}=1+ c_{g} \frac{\fflow{s}}{\bflow{d}}$. Note that this constraint is satisfied by our choice of values for leakage parameters. Further the previous derivation gives us,

$$\npsso(t+1) \leq r+\epsp~,$$

and we conclude the first case.

Case 2: Suppose $g(r+s)> r+s$, then pick the following initial configuration:

* Assign pheromone value on the edges $(s,v_1),(s,u_1), (d,v_n),(d,u_m)$ such that the normalized pheromone level on $(s,u_1),(d,u_n)$ is $\geq r+\epsilon$. Further assign the flow values on the edges such that they satisfy the following,

\begin{equation}
\fflow{v_{i}v_{i+1}}(0) \leq \fflow{s} (1-r-\epsilon)\prod_{j \leq i} (1-l_{v_{j}}) \text{ and }\bflow{v_{i}v_{i+1}}(0) \leq \fflow{d} (1-r-\epsilon)\prod_{j \geq i+1} (1-l_{v_{j}})
\end{equation}

\begin{equation}
\fflow{u_{i}u_{i+1}}(0) \geq \fflow{s} (r+\epsilon)\prod_{j \leq i} (1-l_{u_{j}}) \text{ and }\bflow{u_{i}u_{i+1}}(0) \geq \fflow{d} (r+\epsilon)\prod_{j \geq i+1} (1-l_{u_{j}})~.
\end{equation}

* Let the leakage values at each node be such that the parameters $\alpha$ and $\beta$ satisfy the following inequality,
$1 \geq \frac{\lt}{\lo} \geq 1- c_{g} \frac{\fflow{s}}{ \bflow{d}}$, where $c_{g}\defeq \cue/4$ and $\cue \defeq g(r+\epsp)-(r+\epsp)>0$. Note that $c_{g}=0$ iff $g$ is the linear rule.  As the forward and backward flows are fixed, the above constraint on the leakage parameters only depend on $g$ and therefore satisfy the conditions of the lemma.

We show by induction that the above inequalities hold for all time $t\geq 0$ and therefore the system does not converge to the minimum leakage path.

Hypothesis: At time $t\geq 0$, pheromone values on the edges $(s,v_1),(s,u_1), (d,v_n),(d,u_m)$ are such that the normalized pheromone level on $(s,u_1),(d,u_m)$ is $\geq r+\epsilon$. Further the flow values on the edges satisfy the following,

\begin{equation}
\fflow{v_{i}v_{i+1}}(t) \leq \fflow{s} (1-r-\epsilon)\prod_{j \leq i} (1-l_{v_{j}}) \text{ and }\bflow{v_{i}v_{i+1}}(t) \leq \fflow{d} (1-r-\epsilon)\prod_{j \geq i+1} (1-l_{v_{j}})
\end{equation}

\begin{equation}
\fflow{u_{i}u_{i+1}}(t) \geq \fflow{s} (r+\epsilon)\prod_{j \leq i} (1-l_{u_{j}}) \text{ and }\bflow{u_{i}u_{i+1}}(t) \geq \fflow{d} (r+\epsilon)\prod_{j \geq i+1} (1-l_{u_{j}})~.
\end{equation}

Base case: The condition trivially holds at $0$ because of the initial configuration provided by the conditions of the lemma.

Induction Step: To prove the hypothesis for time $t+1$, all we need to show is that, $\npsst(t+1),\npddt \geq r+\epsp$, $\fflow{u_0u_1}(t+1)=\fflow{ss_2}(t+1) \geq \fflow{s} \cdot (r+\epsp)$ and $\bflow{u_{m}u_{m+1}}(t+1)=\bflow{d_2d}(t+1) \geq \bflow{d} \cdot (r+\epsilon)$; all the remaining inequalities follows from these basic inequalities. Also note that from the definition of our case, that is $g(r+s)>r+s$ for all $s \leq \epsilon$, we get that the inequalities $\npsst(t+1),\npddt(t+1) \geq r+\epsp$ further imply the following,

$$\fflow{ss_2}(t+1) = \fflow{s} \cdot g(\npsst(t+1)) \geq  \fflow{s}\cdot g(r+\epsp) > \fflow{s}\cdot(r+\epsp)~,$$

and similarly,

$$\bflow{d_2d}(t+1) > \bflow{d} (r+\epsilon)~.$$

Therefore it is enough to show that $\npsst(t+1),\npddt(t+1) \geq r+\epsp$. As the proof for the bound on $\npddt(t+1)$ is analogous to that of $\npsst(t+1)$, in the remainder we focus our attention on the proof for $\npsst(t+1)$. Recall the definition of $\npsst(t+1)$,

\begin{align}
\npsst(t+1)=\frac{\psst(t+1)}{\psso(t+1)+\psst(t+1)} &= \frac{ \psst(t) +
\fsst(t) +  \fsts(t)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)}
\end{align}

We know by the induction step that,

\begin{align}\label{eq:P411}
\frac{\psst(t)}{\psso(t)+\psst(t)} \geq  r+\epsp~.
\end{align}

Also note that,

\begin{equation}\label{eq:P412}
\frac{\fsts(t)}{ \fsos(t)+\fsts(t)} \geq \frac{\beta}{\alpha}(r+\epsp)~.
\end{equation}

In the above we used the monotonically non-decreasing property of $x/(1+x)$ and the conditions provided by the induction step at time $t$, that is $\fsts(t)\geq \bflow{d} \cdot (r+\epsp) \cdot \beta$ and $\fsos(t)\leq \bflow{d} \cdot (1-r-\epsp)\cdot \alpha$.

Recall the definition of $\cue$ and note that we also have the following upper bound on the flow value,

\begin{equation}\label{eq:P413}
\fsst(t) = \fflow{s} \cdot g(\npsst(t)) \geq  \fflow{s}\cdot g(r+\epsp) \geq \fflow{s}\cdot(r+\epsp+\cue)~,
\end{equation}

Using these bounds, we provide an upper bound for the normalized pheromone level.

\begin{align}
\npsst(t+1)&= \frac{ \psst(t) +
\fsst(t) +  \fsts(t)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)},\\
& \geq (r+\epsp)+\frac{(\frac{\lt}{\lo}-1)(r+\epsp)(\fsts(t)+\fsos(t))+
\left( \fsst(t)-(r+\epsp)(\fsso(t) +  \fsst(t))\right)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)},\\
& \geq (r+\epsp)+\frac{(\frac{\lt}{\lo}-1)2 \bflow{d}+
\left( \fsst(t)-(r+\epsp)\cdot \fflow{s}\right)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)},\\
& \geq (r+\epsp)+\frac{(\frac{\lt}{\lo}-1)2 \bflow{d}+
\fflow{s}\left( r+\epsp+\cue-r-\epsp\right)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)},\\
& \geq (r+\epsp)+\frac{(\frac{\lt}{\lo}-1)2 \bflow{d}+\cue
\fflow{s}}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)},\\
&\geq (r+\epsp)+\frac{\frac{1}{2}\cue
\fflow{s}}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)}~,\\
&\geq (r+\epsp)'~.
\end{align}

In the second inequality we used <Ref>. In the third inequality we used $r+\epsilon<1$ and $\fsts(t),\fsos(t) \leq \bflow{d}$, $\fsso(t) +  \fsst(t) \leq \fflow{s}$ inequalities. In the fourth inequality we used <Ref>.
The sixth inequality holds because $(\frac{\lt}{\lo}-1)2 \bflow{d} \geq -\frac{1}{2}\cue \fflow{s}$, which is equivalent to $\frac{\lt}{\lo} \geq 1- \cue \frac{\fflow{s}}{4 \cdot \bflow{d}}= 1- c_{g} \frac{\fflow{s}}{ \bflow{d}}$. Note that this constraint is satisfied by our choice of values for leakage parameters. Further the previous derivation gives us,

$$\npsst(t+1) \geq r+\epsp~,$$

and we conclude the second case.

§.§ Proof for the increasing flow lower bound (<Ref>)

Without loss of generality we let $P_{1}$ to be the shortest path. Let $n,m$ be the number of vertices between $s$ and $d$ on the top and bottom path respectively. We name the vertices from left to right on the top path by $v_{0}$ to $v_{n+1}$ and the bottom path by $u_0$ to $u_{m+1}$, with the convention $v_0=u_0=s$ and $v_{n+1}=u_{m+1}=d$. We divide the analysis into two cases.

For any $g \in \setflb$, let $r\geq 0$ be any $x \in (0,1/2)$ such that $g(x)\neq x$. For such an $r$, there exists an $\epsilon >0$ such that $r+\epsilon<1/2$ and for all $0<s\leq \epsilon$ one of the following two conditions holds:

* $g(r+s)< r+s$.

* $g(r+s)>r+s$.

Case 1: Suppose $g(r+s)< r+s$, then we pick the following initial configuration and flow values:

* Assign pheromone values on the edges $(s,v_1),(s,u_1), (d,v_n),(d,u_m)$ such that the normalized pheromone level on $(s,v_1),(d,v_n)$ is $\leq r+\epsilon$. Further assign the flow values on the edges such that they satisfy the following,

\begin{equation}
\fflow{v_{i}v_{i+1}}(0) \leq \fflow{s}(0) (r+\epsilon) \text{ and }\bflow{v_{i}v_{i+1}}(0) \leq \fflow{d}(0) (r+\epsilon)
\end{equation}

\begin{equation}
\fflow{u_{i}u_{i+1}}(0) \geq \fflow{s}(0) (1-r-\epsilon) \text{ and }\bflow{u_{i}u_{i+1}}(0) \geq \fflow{d}(0) (1-r-\epsilon)~.
\end{equation}

* We specify the values of the flows $\fflow{s}(t),\bflow{d}(t)$ for times $t>0$ later in the proof.

We show by induction that the above inequalities hold for all time $t\geq 0$ and therefore the system does not converge to the shortest path.

Hypothesis: At time $t\geq 0$, pheromone value on the edges $(s,v_1),(s,u_1), (d,v_n),(d,u_m)$ are such that the normalized pheromone level on $(s,v_1),(d,v_n)$ is $\leq r+\epsilon$. Further the flow values on the edges satisfy the following,

\begin{equation}
\fflow{v_{i}v_{i+1}}(t) \leq \fflow{s}(t-i) (r+\epsilon) \text{ and }\bflow{v_{i}v_{i+1}}(t) \leq \fflow{d}(t-(n-i)) (r+\epsilon)
\end{equation}

\begin{equation}
\fflow{u_{i}u_{i+1}}(t) \geq \fflow{s}(t-i) (1-r-\epsilon) \text{ and }\bflow{u_{i}u_{i+1}}(t) \geq \fflow{d}(t-(n-i)) (1-r-\epsilon)~.
\end{equation}

In the above equations, $\fflow{s}(t')\defeq\fflow{s}(0)$ and $\bflow{d}(t')\defeq\bflow{d}(0)$ for all $t' <0$.

Base case: The condition trivially holds at $0$ because of the initial configuration provided by the conditions of the lemma.

Induction Step: To prove the hypothesis for time $t+1$, all we need to show is that, $\npsso(t+1),\npddo(t+1) \leq r+\epsp$, $\fflow{v_0v_1}(t+1)=\fflow{ss_1}(t+1) \leq \fflow{s}(t+1) \cdot (r+\epsp)$ and $\bflow{v_{n}v_{n+1}}(t+1)=\bflow{d_1d}(t+1) \leq \bflow{d}(t+1) \cdot (r+\epsilon)$; all the remaining inequalities follow from these basic inequalities. Also note that from the definition of our case, that is $g(r+s)<r+s$ for all $s \leq \epsilon$, we get that the inequalities $\npsso(t+1),\npddo(t+1) \leq r+\epsp$ further imply the following,

$$\fflow{ss_1}(t+1) = \fflow{s}(t+1) \cdot g(\npsso(t+1)) \leq  \fflow{s}(t+1)\cdot g(r+\epsp) < \fflow{s}(t+1)\cdot(r+\epsp)~,$$

and similarly,

$$\bflow{d_1d}(t+1) < \bflow{d}(t+1) (r+\epsilon)~.$$

Therefore it is enough to show that $\npsso(t+1),\npddo(t+1) \leq r+\epsp$. As the proof for the bound on $\npddo(t+1)$ is analogous to that of $\npsso(t+1)$, in the remainder we focus our attention on the proof for $\npsso(t+1)$. Recall the definition of $\npsso(t+1)$,

\begin{align}
\npsso(t+1)=\frac{\psso(t+1)}{\psso(t+1)+\psst(t+1)} &= \frac{ \psso(t) +
\fsso(t) +  \fsos(t)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)}
\end{align}

We know by the induction step that,

\begin{align}\label{eq:P51}
\frac{\psso(t)}{\psst(t)+\psso(t)} < r+\epsp~.
\end{align}

Also note that,

\begin{equation}\label{eq:P52}
\frac{\fsos(t)}{ \fsts(t)+\fsos(t)} \leq \frac{\bflow{d}(t-n)}{\bflow{d}(t-n)}(r+\epsp)~.
\end{equation}

In the above we used the monotonically non-decreasing property of $x/(1+x)$ and the conditions provided by the induction step at time $t$, that is $\fsos(t)\leq (r+\epsp) \cdot \bflow{d}(t-n)$ and $\fsts(t)\geq (1-r-\epsp)\cdot \bflow{d}(t-m)$.

Let $\cue \defeq (r+\epsp)-g(r+\epsp)>0$, then we have following upper bound on the flow value,

\begin{equation}\label{eq:P53}
\fsso(t) = \fflow{s}(t) \cdot g(\npsso(t)) \leq  \fflow{s}(t)\cdot g(r+\epsp) \leq \fflow{s}(t)\cdot(r+\epsp-\cue)~,
\end{equation}

Using these bounds, we provide an upper bound for the normalized pheromone level.

\begin{align}
\npsso(t+1)&= \frac{ \psso(t) +
\fsso(t) +  \fsos(t)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
& \leq (r+\epsp)+\frac{(\frac{\lo}{\lt}-1)(r+\epsp)(\fsts(t)+\fsos(t))+
\left( \fsso(t)-(r+\epsp)(\fsso(t) +  \fsst(t))\right)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
& \leq (r+\epsp)+\frac{(\frac{\lo}{\lt}-1)(\bflow{d}(t-m)+\bflow{d}(t-n))+
\left( \fsso(t)-(r+\epsp)\cdot \fflow{s}(t)\right)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
& \leq (r+\epsp)+\frac{(\frac{\lo}{\lt}-1)(\bflow{d}(t-m)+\bflow{d}(t-n))+
\fflow{s}(t)\left( r+\epsp-\cue-r-\epsp\right)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
& \leq (r+\epsp)+\frac{(\frac{\lo}{\lt}-1)(\bflow{d}(t-m)+\bflow{d}(t-n))-\cue
\fflow{s}(t)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
&\leq (r+\epsp)-\frac{\frac{1}{2}\cue
\fflow{s}(t)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)}~,\\
&\leq (r+\epsp)~.
\end{align}

In the second inequality we used <Ref>. In the third inequality we used $r+\epsilon<1$ and the following flow inequalities: $\fsts(t)\leq \bflow{d}(t-m)$, $\fsos(t) \leq \bflow{d}(t-n)$ and $\fsso(t) +  \fsst(t) \leq \fflow{s}(t)$ inequalities. In the fourth inequality we used <Ref>.
The sixth inequality holds if $(\frac{\lo}{\lt}-1)(\bflow{d}(t-m)+\bflow{d}(t-n)) \leq \frac{1}{2}\cue \fflow{s}(t)$, which enforces the constraints on the change of flow. For the symmetric case, that is $\fflow{s}(t)=\bflow{d}(t)=f(t)$ for all $t \geq 0$ and non-decreasing flow the above condition can be further simplified to $\frac{f(t-n)}{f(t-m)} \geq 1+c_{g}$ for some constant dependent only on $g$. Note that the constraints on the change of flow is multiplicative and only depends on $g$, thus satisfy the conditions of the lemma. Further the above derivation gives us,

$$\npsso(t+1) \leq r+\epsp~,$$

and we conclude the first case.

Case 2: Suppose $g(r+s)> r+s$, then we pick the following initial configuration:

* Assign pheromone value on the edges $(s,v_1),(s,u_1), (d,v_n),(d,u_m)$ such that the normalized pheromone level on $(s,u_1),(d,u_n)$ is $\geq r+\epsilon$. Further assign the flow values on the edges such that they satisfy the following,

\begin{equation}
\fflow{v_{i}v_{i+1}}(0) \leq \fflow{s}(0) (1-r-\epsilon) \text{ and }\bflow{v_{i}v_{i+1}}(0) \leq \fflow{d}(0) (1-r-\epsilon)
\end{equation}

\begin{equation}
\fflow{u_{i}u_{i+1}}(0) \geq \fflow{s}(0) (r+\epsilon) \text{ and }\bflow{v_{i}v_{i+1}}(0) \geq \fflow{d}(0) (r+\epsilon)~.
\end{equation}

* We specify the values of the flows $\fflow{s}(t),\bflow{d}(t)$ for times $t>0$ later in the proof.

We show by induction that the above inequalities hold for all time $t\geq 0$ and therefore the system does not converge to the shortest path.

Hypothesis: At time $t\geq 0$, pheromone value on the edges $(s,v_1),(s,u_1), (d,v_n),(d,u_m)$ are such that the normalized pheromone level on $(s,v_1),(d,v_n)$ is $\leq r+\epsilon$. Further the flow values on the edges satisfy the following,

\begin{equation}
\fflow{v_{i}v_{i+1}}(t) \leq \fflow{s}(t-i) (1-r-\epsilon) \text{ and }\bflow{v_{i}v_{i+1}}(t) \leq \fflow{d}(t-(n-i)) (1-r-\epsilon)
\end{equation}

\begin{equation}
\fflow{u_{i}u_{i+1}}(t) \geq \fflow{s}(t-i) (r+\epsilon) \text{ and }\bflow{v_{i}v_{i+1}}(t) \geq \fflow{d}(t-(n-i)) (r+\epsilon)~.
\end{equation}

In the above equations, $\fflow{s}(t')=\fflow{s}(0)$ and $\bflow{d}(t')=\bflow{d}(0)$ for all $t' <0$.

Base case: The condition trivially holds at $0$ because of the initial configuration provided by the conditions of the lemma.

Induction Step: To prove the hypothesis for time $t+1$, all we need to show is that, $\npsst(t+1),\npddt \geq r+\epsp$, $\fflow{u_0u_1}(t+1)=\fflow{ss_2}(t+1) \geq \fflow{s}(t+1) \cdot (r+\epsp)$ and $\bflow{u_{m}u_{m+1}}(t+1)=\bflow{d_2d}(t+1) \geq \bflow{d}(t+1) \cdot (r+\epsilon)$; all the remaining inequalities follows from these basic inequalities. Also note that from the definition of our case, that is $g(r+s)>r+s$ for all $s \leq \epsilon$, we get that the inequalities $\npsst(t+1),\npddt(t+1) \geq r+\epsp$ further imply the following,

$$\fflow{ss_2}(t+1) = \fflow{s}(t+1) \cdot g(\npsst(t+1)) \geq  \fflow{s}(t+1)\cdot g(r+\epsp) > \fflow{s}(t+1)\cdot(r+\epsp)~,$$

and similarly,

$$\bflow{d_2d}(t+1) > \bflow{d}(t+1) (r+\epsilon)~.$$

Therefore it is enough to show that $\npsst(t+1),\npddt(t+1) \geq r+\epsp$. As the proof for the bound on $\npddt(t+1)$ is analogous to that of $\npsst(t+1)$, in the remainder we focus our attention on the proof for $\npsst(t+1)$. Recall the definition of $\npsst(t+1)$,

\begin{align}
\npsst(t+1)=\frac{\psst(t+1)}{\psso(t+1)+\psst(t+1)} &= \frac{ \psst(t) +
\fsst(t) +  \fsts(t)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)}
\end{align}

We know by the induction step that,

\begin{align}\label{eq:P511}
\frac{\psst(t)}{\psso(t)+\psst(t)} \geq  r+\epsp~.
\end{align}

Also note that,

\begin{equation}\label{eq:P512}
\frac{\fsts(t)}{ \fsos(t)+\fsts(t)}\geq \frac{\bflow{d}(t-m)}{\bflow{d}(t-n)}(r+\epsp)~.
\end{equation}

In the above we used the monotonically non-decreasing property of $x/(1+x)$ and the conditions provided by the induction step at time $t$, that is $\fsts(t)\geq (r+\epsp) \cdot \bflow{d}(t-m)$ and $\fsos(t)\leq (1-r-\epsp)\cdot \bflow{d}(t-n)$.

Let $\cue \defeq g(r+\epsp)-(r+\epsp)>0$, then we have following lower bound on the flow value,

\begin{equation}\label{eq:P513}
\fsst(t) = \fflow{s}(t) \cdot g(\npsst(t)) \geq  \fflow{s}(t)\cdot g(r+\epsp) \geq \fflow{s}(t)\cdot(r+\epsp+\cue)~,
\end{equation}

Using these bounds, we provide an upper bound for the normalized pheromone level.

\begin{align}
\npsst(t+1)&= \frac{ \psst(t) +
\fsst(t) +  \fsts(t)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)},\\
& \geq (r+\epsp)+\frac{(\frac{\lt}{\lo}-1)(r+\epsp)(\fsts(t)+\fsos(t))+
\left( \fsst(t)-(r+\epsp)(\fsso(t) +  \fsst(t))\right)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)},\\
& \geq (r+\epsp)+\frac{(\frac{\lt}{\lo}-1)(\bflow{d}(t-m)+\bflow{d}(t-n))+
\left( \fsst(t)-(r+\epsp)\cdot \fflow{s}(t)\right)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)},\\
& \geq (r+\epsp)+\frac{(\frac{\lt}{\lo}-1)(\bflow{d}(t-m)+\bflow{d}(t-n))+
\fflow{s}(t)\left( r+\epsp+\cue-r-\epsp\right)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)},\\
& \geq (r+\epsp)+\frac{(\frac{\lt}{\lo}-1)(\bflow{d}(t-m)+\bflow{d}(t-n))+\cue
\fflow{s}(t)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)},\\
&\geq (r+\epsp)+\frac{\frac{1}{2}\cue
\fflow{s}(t)}{ \psso(t) + \psst(t)+ \fsso(t) +\fsst(t) +  \fsos(t)+\fsts(t)}~,\\
&\geq (r+\epsp)~.
\end{align}

In the second inequality we used <Ref>. In the third inequality we used $r+\epsilon<1$ and the following flow inequalities: $\fsts(t)\leq \bflow{d}(t-m)$, $\fsos(t) \leq \bflow{d}(t-n)$ and $\fsso(t) +  \fsst(t) \leq \fflow{s}(t)$ inequalities. In the fourth inequality we used <Ref>.
The sixth inequality holds if $(\frac{\lt}{\lo}-1)(\bflow{d}(t-m)+\bflow{d}(t-n)) \geq -\frac{1}{2}\cue
\fflow{s}(t)$, which enforces the constraints on the change of flow. For the symmetric case, that is $\fflow{s}(t)=\bflow{d}(t)=f(t)$ for all $t \geq 0$ and non-decreasing flow the above condition can be further simplified to $\frac{f(t-m)}{f(t-n)} \geq 1-c_{g}$ for some constant dependent only on $g$. Note that the constraints on the change of flow is multiplicative and only depends on $g$ satisfy the conditions of the lemma. Further the above derivation gives us,

$$\npsst(t+1) \geq r+\epsp~,$$

and we conclude the second case.

Define $c_{g,r}=\min(g(r-r_\epsilon)-(r-r_\epsilon),(r+r_\epsilon)-g(r+r_\epsilon))$ and $c_{g}=\min_{r \in S_{g}} c_{g,r}$.

For any $g \in \setflb$, let $r \in S_{g}$ be such that there exists an $\epsilon >0$ that satisfies the following two conditions,

* $g(s)<s$ for all $s\leq r+\epsilon$.

* $g(s)>s$ for all $s \geq r-\epsilon$.

Then $r$ is a stable equilibrium for the flow dynamics governed by $g$ that satisfies,

\begin{equation}\label{eq:condition}
|l_{P_1}-l_{P_2}| \leq c_{g}, |\fflow{s}(t+1)-\fflow{s}(t)|\leq  \text{ and } |\bflow{d}(t+1)-\bflow{d}(t)|\leq ~.
\end{equation}

To prove the stability of $r \in L$, we need to show the existence of an $\epsp>0$ such that the flow dynamics governed by the rule $g$ satisfying <Ref> and an initial configuration such that,

* $\npsso(0),\npddo(0)\in (r-\epsp,r+\epsp)$ and $\fflow{uv}(0) \in \fflow{s} \cdot (r-\epsp,r+\epsp)$, $\bflow{uv}(0) \in \bflow{d} \cdot (r-\epsp,r+\epsp)$  for all $(u,v) \in P_{1}$,

* $\npsst(0),\npddt(0)\in (1-r-\epsp,1-r+\epsp)$ and $\fflow{uv}(0) \in \fflow{s} \cdot (1-r-\epsp,1-r+\epsp)$, $\bflow{uv}(0) \in \bflow{d} \cdot (1-r-\epsp,1-r+\epsp)$  for all $(u,v) \in P_{2}$,

converges to $r$, that is, for any $\epspp>0$, there exists $t_{\epspp}$ such that for all $t \geq t_{\epspp}$ we have,

* $\npsso(t),\npddo(t)\in (r-\epspp,r+\epspp)$ and $\fflow{uv}(t),\bflow{uv}(t) \in (1-r-\epspp,1-r+\epspp)$ for all $(u,v) \in P_{1}$,

* $\npsst(t),\npddt(t)\in (r-\epspp,r+\epspp)$ and $\fflow{uv}(t),\bflow{uv}(t) \in (1-r-\epspp,1-r+\epspp)$ for all $(u,v) \in P_{2}$,

We divide the analysis of the proof into two parts, we first show that.

Hypothesis: At time $t\geq 0$, the normalized pheromone level on the top path is $\geq s-\epsp$. Flow on all the top edges is at least $s-\epsp$.

Base case: The condition holds at $0$ because of our initial configuration.

Induction Step: Here we first show that $\npsso(t+1) \geq s-\epsp$.

\begin{align}
\npsso(t+1)=\frac{\psso(t+1)}{\psso(t+1)+\psst(t+1)} &= \frac{ \psso(t) +
\fsso(t) +  \fsos(t)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)}
\end{align}

We know that

\begin{align}
\frac{\psso(t)}{\psst(t)+\psso(t)} \geq s-\epsp \text{ and } \frac{
\fsso(t)}{ \fsst(t)+\fsso(t)} > s-\epsp~.
\end{align}

Further by induction at time $t$ we have $\frac{\fsos(t)}{\fsts(t)+\fsos(t)} \geq s-\epsp$, therefore,

$$\npsso(t+1) \geq s-\epsp~.$$

Similar proof holds for the edge $(d,d_1)$ and therefore we also have,

$$\npddo(t+1) \geq s-\epsp~.$$

As the normalized flow on the edges $(s,s_1)$ and $(d,d_1)$ is at least $s-\epsp$, the new flow entering the top edges is at least $s-\epsp$ from the definition of the rule $g$. Similar proof also holds for the case $s+\epsp$.

Therefore for all time $t$, we have that the normalized pheromone level on the top path is between $s-\epsp$ and $s+\epsp$. Flow on all the top edges is between $s-\epsp$ and $s+\epsp$.

The flow

Let $c _{\ell} \defeq \min_{ s \in [r-\epsilon,r-\epspp] } g(s)-s$ and $\cue \defeq \min_{ s \in [r+\epsp,r+\epsilon] } s-g(s)$.

$$\fsso(t) = g(\npsso(t))>\npsso(t)+\cle~.$$

\begin{align*}
\npsso(t+1)&= \frac{ \psso(t) +
\fsso(t) +  \fsos(t)}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)}\\
&=\frac{ \frac{\psso(t)}{\psst(t) + \psso(t)}(\psst(t) + \psso(t)) +
\frac{\fsso(t)}{\fsst(t) +\fsso(t)}(\fsst(t) +\fsso(t)) +  \frac{\fsos(t)}{\fsts(t)+\fsos(t)}(\fsts(t)+\fsos(t))}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
&\geq \frac{ (s-\epsp)(\psst(t) + \psso(t)) +
(s-\epsp+\cle)(\fsst(t) +\fsso(t)) +  (s-\epsp)(\fsts(t)+\fsos(t))}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
&\geq s-\epsp+ \frac{\cle(\fsst(t) +\fsso(t))}{ \psst(t) + \psso(t)+ \fsst(t) +\fsso(t) +  \fsts(t)+\fsos(t)},\\
&\geq s-\epsp+d,
\end{align*}

where $d$ is a fixed constant.

In the fixed flow setting, for every $f\in \setflb$ there exists an initial configuration such that the system doesn't converge to the shortest path.

Therefore for any $g \in \setflb$, there exists an initial configuration such that the flow dynamics governed by the rule $g$ does not converge to the shortest path.

For any $f \in \setflb$, there exists an $\epsilon >0$ such that for all $s\leq \epsilon$ one of the following three conditions holds:

* $f(s)\leq s$.

* $f(s)>s$.

Case 1: Suppose $f(s)\leq s$, then pick the following initial configuration:

* Let top path be the long path.

* Assign $p_{\ell}=p_{r}=1$ and  $1-\epsp$ on the whole top path and $\epsp$ on the whole bottom path for any $\epsp <\epsilon$. Then it is immediate that

Case 2: Suppose $f(s) > s$, then pick the following initial configuration:

* Let top path be the long path.

* Assign $p_{\ell}=p_{r}=1$ and  $\epsp$ on the whole top path and $1-\epsp$ on the whole bottom path for any $\epsp >\epsilon$. Then it is immediate that

§ SIMULATION DETAILS

We ran the simulations for three kinds of directed graphs: graphs sampled from the $G(n, p)$ model, graphs sampled from  the $G(n, p)$ model with the additional constraint that an edge can exist between vertex $i$ and $j$ only if $|i - j| \leq k$ for some parameter $k$ (with the source vertex and the destination the vertex numbered 1 and $n$ respectively), and the grid graph. $G(n, p)$ model with the additional constraint ensures that the graph has long paths between the source and the destination. We generated a large number of instances with different values for $n$, $p$, $k$ and other parameters, with linear decision rule, and observed the desired convergence in all the simulated instances.  Below, we describe the details of the parameter settings we considered.

The decay parameter $\delta$ (which is same for all the edges), and the initial pheromone level on the edges was also chosen uniformly at random from $(0,1)$. The initial forward flow level at $s$ and backward flow level at $d$ was chosen uniformly at random from $(0.5,1)$, and the initial flow at all other vertices was set to $0$. We only considered instance where there was at least one path from the source to the destination.

§.§ Leakage with fixed flow

For all the randomly generated instance, we chose the leakage value of all the vertices uniformly at random from $(0,1)$. For all these instances, the dynamics converged to the path with the minimum leakage. Below, we describe the parameter values for different graph families.

* $G(n, p)$ model: We ran 1000 instances each with $(n,p)$ set to $(100, 0.05), (100, 0.1)$ and $(100, 0.5)$. We ran 100 instances with $(n,p)$ set to $(1000, 0.01)$ and $(1000, 0.1)$.

* $G(n, p)$ model with edge between $i$ and $j$ only if $|i - j| \leq k$: We ran 1000 instances with $(n, p, k) = (100, 0.5, 10)$, and 100 instances with $(n, p, k) = (1000, 0.5, 40)$.

* Grid graph: We ran the simulations on a $10X10$ grid graph with source and destination at the diagonally opposite extreme vertices. We ran $100$ instances. The graph structure was same across all these instances, but other parameter values such as leakage levels, decay parameter etc. were chosen randomly as described above.

§.§ Increasing flow with no leakage

In this case, the leakage was set to $0$ for all the vertices. We increase the forward flow level at $s$ and backward flow level at $d$ by a factor of $1.1$ every time step. One issue with this is that flow values can become too large exceeding the maximum allowed value in any programming language. To deal with this issue, instead of multiplying the forward and backward flow values at $s$ and $d$ by $1.1$, we keep these two values the same, and divide all other flow values and pheromone levels in the graph by a factor of $1.1$. As our decision rule is linear, it is not difficult to see that only the relative values of flow and pheromone level matter, and this gives rise to exactly the same dynamics (up to scaling) as when we multiply the forward  flow  at $s$ and backward flow at $d$ by $1.1$. When the value of pheromone level or flow at any edge became too small (smaller than the minimum allowed value in Matlab which is  $\approx 10^{-323}$), we rounded it to zero.

For all the graphs, we planted a short path in the graph so as to ensure that the shortest path is unique. In all the simulations, we observed that the dynamics converge to this shortest path. Below, we describe the details for different graph types.

* $G(n, p)$ model: We ran 1000 instances  with $(n,p)$ set to $(100, 0.05)$ and 100 instances with $(n, p)$  set to  $(1000, 0.01)$ and $(1000, 0.005)$. For all the instances, we find length of the shortest path and if the shortest path is not unique, we plant another randomly generated path with length 1 smaller than the previous shortest path, so that there is unique shortest path in the graph so obtained.

* $G(n, p)$ model with edge between $i$ and $j$ only if $|i - j| \leq k$: We ran 1000 instances with $(n, p, k) = (100, 0.5, 10)$, and 100 instances with $(n, p, k) = (1000, 0.5, 40)$. We planted the shortest path having edges $(1,k+1), (k+1, 2(k+1))
,(2(k+1),3(k+1))$   and so on. Here, $1$ is the source vertex and $n$ is the destination vertex.

* Grid graph: We ran the simulations on a $10X10$ grid graph with source and destination at the diagonally opposite extreme vertices.  We ran $100$ instances. For each instance, we planted a randomly generated shortest path of length 9.