# 1. Questions

In the online multi-agent k-Canadian Traveler Problem (m-k-CTP), an undirected connected network G=(V,E) with a given source node O and a destination node D, together with non-negative edge costs are given. There are L≥2 travelers in the network who are initially located at O and can communicate with each other in real time. There are k≥L non-recoverable blocked edges in the network which are not known to the travelers beforehand. A blocked edge is discovered online only if it is encountered by at least one of the travelers at one of its end-nodes. It is assumed that the network remains connected if the blocked edges are removed from E. The objective of the travelers is to devise an online algorithm such that at least one of them finds a feasible path without blocked edges, from O to D with minimum total cost of the edges travelled. From a network resilience perspective, the m-k-CTP investigates how reliable the transportation network is against adversarial blocked edges.

The single-agent version of this problem was introduced by Papadimitriou and Yannakakis (1991) and was analyzed with a bounded number of k blocked edges by Westphal (2008). In the past decade, several papers (Shiri and Salman 2020, 2019a, 2017; Zhang, Xu, and Qin 2013) have investigated online algorithms for the m-k-CTP by means of *competitive ratio* described in section 2. A lower bound of 2⌊kL⌋+1 on the competitive ratio of deterministic algorithms (Zhang, Xu, and Qin 2013) is the best lower bound found so far for this problem on general networks. However, an optimal deterministic online algorithm which meets this lower bound has not been provided so far. In this work, with the aim of narrowing the gap between the lower bound and worst-case performance of online algorithms, we prove a lower bound on the competitive ratio of deterministic online algorithms for the m-k-CTP which is tighter than the lower bound of 2⌊kL⌋+1 given in the literature.

# 2. Methods

In the *competitive analysis* framework (Sleator and Tarjan 1984), the performance of the *online* solution obtained under incomplete information is compared with the performance of the *offline* optimal solution obtained under complete information. The *competitive ratio* of an online algorithm applied to an online minimization problem is the supremum of the ratio of the cost of the online solution to the cost of the offline optimal solution over all instances of the problem.

Accordingly, a lower bound on the competitive ratio specifies the proximity of the objective function value of an online solution to the optimal objective function value of the offline optimal solution. To derive a lower bound of LB on the competitive ratio of deterministic online algorithms for the m-k-CTP, we should show that the competitive ratio of any deterministic online algorithm is not less than LB on at least one instance of the m-k-CTP. We refer the reader to Akbari and Shiri (2022), Akbari, Shiri, and Sibel Salman (2021), Akbari and Shiri (2021), and Shiri and Salman (2019b) for proofs of deriving lower bounds for similar online problems.

# 3. Findings

**Definition 1**. *For an integer k, a graph is called an adverse graph of order k if it has three connected parts as follows: a left part which is a perfect binary tree (see Appendix A) with k+1 levels where the root of the binary tree is the leftmost node, a right part which is a perfect binary tree with k+1 levels where the root of the binary tree is the rightmost node, and a bridge part that consists of 2k edges such that each one connects a leaf node of the left part to a leaf node of the right part. We call the edges in the bridge part the bridge edges.*

**Theorem 3.1**. *No deterministic online algorithm achieves a competitive ratio better than 2⌊k⌊2log2L⌋⌋+1 for the m-k-CTP.*

*Proof.* We assume that the input network Gadverse is an adverse graph of order k (Definition 1), where O is the root of the left tree and D is the root of the right tree. We set the traveling time of the bridge edges to 1 and the traveling time of the other edges to 0, i.e., the traveling time of edges on left and right trees are negligible compared to the traveling time of the bridge edges. Figure 1 represents an adverse graph of order 2 with specified values. Note that all the travelers are at O at time 0.

Suppose that an arbitrary deterministic online algorithm denoted by ALG ends in time interval (t∗,t∗+1], where t∗ is a non-negative integer number. Hence, ALG can be represented by set of pairs {((i,i+1],Li)} for i=0,1,2,...,t∗, where (i,i+1] represents a time interval and Li (Li∈{0,1,2,...,L}) denotes the number of travelers which depart from the left tree and enter the right tree by traversing a bridge edge in time interval (i,i+1].

Note that level j (j∈{1,2,...,k+1}) consists of 2j−1 nodes in both the left and right trees. We label the nodes of level j such that vleftwj and vrightwj represent the wth (w=1,2,...,2j−1) nodes of the jth level on the left and right trees, respectively. For ALG and the node vleftwj, we let xiwj denote the number of travelers that depart from the left tree and enter the right tree via vleftwj within time interval (i,i+1] for i=0,1,2,...,t∗. For ALG, we assume that the online adversary blocks the edges according to the *blocking strategy* in Algorithm 1.

We apply the next lemma which is proven in Appendix B to complete the proof.

**Lemma 2**. *The travelers can find at most ⌊2log2L⌋ blocked edges within time interval (2i,2i+2] for i=0,1,2,...,2⌊t∗2⌋ in ALG applied to Gadverse against the adverse blocking strategy.*

It takes at least ⌊k⌊2log2L⌋⌋ time intervals with length 2 from time 0 to find the k blocked edges. It takes one unit of time to arrive at D when all the blocked edges are identified. Thus, no deterministic algorithm terminates earlier than time 2⌊k⌊2log2L⌋⌋+1. Theorem 3.1 follows since it takes one unit of time from O to D in the offline optimal solution.

It is easy to verify that L>⌊2log2L⌋ for integers L>4 and L=⌊2log2L⌋ for L=2,3,4. Hence, 2⌊k⌊2log2L⌋⌋+1 (Theorem 3.1) is a tighter lower bound than 2⌊kL⌋+1 given in the literature. This result implies that the adversarial online blocked edges can have a significant negative effect on network reliability.