Optimality Gap of Decentralized Submodular Maximization under Probabilistic Communication

This paper considers the problem of decentralized submodular maximization subject to a partition matroid when agents implement a sequential greedy algorithm with probabilistic inter-agent communication. We study a network of $n$ agents, denoted as $\mathcal{A}=\{1,\ldots,n\}$, each equipped with communication and computation capabilities and interconnected via a directed chain graph (see Fig. 1). The goal for each agent $i\in\mathcal{A}$ is to select up to $\kappa_{i}\in\mathbb{Z}_{>0}$ strategies from its local distinct discrete strategy set $\mathcal{P}_{i}$ in way that a normal monotone increasing and submodular utility function $f:2^{\mathcal{P}}\to\mathbb{R}_{\geq 0}$, $\mathcal{P}\!=\!\bigcup_{i\in\mathcal{A}}\mathcal{P}_{i}$, evaluated at collective strategy set of the agents is maximized. The optimization problem is expressed as

Submodular function maximization problems such as (1) are often NP-hard [1]. However, submodularity, a property of set functions with deep theoretical implications, enables the establishment of constant factor approximate (suboptimal) solutions for submodular maximization problems. A fundamental result by Nemhauser et al. [1] establishes that the simple sequential greedy algorithm shown in Algorithm 1 is guaranteed to provide a constant $1/2$-approximation factor solution for the submodular maximization problem (1).

Submodular maximization problems subject to matroid constraints appear in many data-centric problems, such as agglomerative clustering, exemplar-based clustering [2], categorical feature compression [3], and data subset selection [4]. To alleviate the burden on central sequential greedy solvers handling massive data, various parallel computing methods such as MapReduce-based solvers or federated learning frameworks [5] have been proposed.

In the domain of cyber-physical systems, submodular maximization problems of the form (1) appear in various optimal resource allocation and scheduling tasks, such as optimal sensor placement [6], energy storage placement [7, 8], measurement scheduling [9], voltage control in smart grids [10], and persistent monitoring via mobile robots [11]. These applications often require decentralized solutions, where agents achieve a global optimal solution through local computations and inter-agent interactions/communication.

Distributed solutions based on continuous relaxations [12, 13] are proposed in the literature to solve problem (1) over graph integration topologies, however, they often come with significant communication and computation costs. The sequential decision-making structure of Algorithm 1 lends itself naturally to decentralized implementation over a directed chain graph using sequential message-passing, as described in Algorithm 2 [11]. Starting with the first agent in the chain, each agent, after receiving $\bar{\mathcal{S}}_{SG}$—the compound choices of the preceding agents—from its in-neighbor, runs a local sequential greedy algorithm over its local dataset to make its choices considering the choices already made. After determining its local selections and incorporating them into $\bar{\mathcal{S}}_{SG}$, the agent forwards this updated set to its out-neighbor. This method of sequential message-passing can also be facilitated through cloud access.

In practice, message delivery reliability between an in-neighbor and its out-neighbor is not always assured. The effect of delivery failures on a decentralized sequential greedy algorithm has been explored in [14]; refer to Section II for more information. This research examines how a specific message passing sequence impacts the optimality gap from a deterministic point of view. However, practical message delivery success is subject to unpredictable factors such as communication channel strength, agent reliability, and network congestion. The impact of probabilistic communication on convergence in various optimization problems is well documented in the literature, such as in [15, 16]. These studies offer theoretical insights and have practical significance for the design and analysis of decentralized systems in uncertain communication settings. Considering these uncertainties, this paper addresses the pivotal research question of how probabilistic message-passing affects the guaranteed optimality gap of a decentralized sequential greedy algorithm. We frame this challenge as the following problem statement.

The main objective of this paper is to investigate and address Problem 1, focusing on characterizing the probabilistic optimality gap, $\alpha_{p}$. Understanding $\alpha_{p}$ is crucial for decentralized sequential greedy algorithms operating under probabilistic message-passing conditions. This work not only contributes theoretical insights but also has practical implications for designing and analyzing decentralized systems in uncertain communication environments.

To set the stage to address Problem 1, it is pivotal to first examine the consequences of failed message deliveries and the ensuing disruption in the flow of information during the algorithm’s operation. For this purpose, we use two specific graph topologies: the communication graph $\mathcal{G}$, which describes the sequence of message transfers, and the information graph $\mathcal{G}_{I}$, which describes the dissemination of information as a result of the message-passing process; see Fig. 2. In the information graph, an arrow from agent $i$ to agent $j$ indicates that agent $j$ has successfully received information from agent $i$, either directly or through message-passing by other agents preceding agent $i$.

When implementing Algorithm 2, a fully successful message transmission sequence, depicted in Fig. 2(a), equates to the formation of a complete graph in the undirected version of the communication graph $\mathcal{G}_{I}$. Conversely, interruptions in the message-passing path, as shown in Fig. 2(b), result in an undirected version of $\mathcal{G}_{I}$ that lacks full connectivity. To evaluate the degree to which $\mathcal{G}_{I}$ approaches a complete graph configuration, we employ the clique number of the information graph, denoted by $\mathcal{W}(\mathcal{G}_{I})$, as a metric. This measure, indicative of the size of the largest clique (complete sub-graph) within the graph, serves to quantify the graph’s connectivity level. In the context of Algorithm 2, a complete $\mathcal{G}_{I}$ yields a clique number equal to $n$. Interruptions in message passage, however, diminish this number, signifying reduced information connectivity. One can expect that the larger the clique number, indicating a larger fully connected component in the information graph, the better the optimality gap should be for the sequential greedy algorithm. This hypothesis has been formally validated in [14], which demonstrates that the optimality gap of a sequential greedy algorithm tackling problem (1)–under the condition that agents’ policy sets do not overlap–can be effectively quantified as follows.

This bound recovers the well-known optimality gap of $1/2$ when the information graph is complete, i.e., $\mathcal{W}(\mathcal{G}_{I})=n$.

When message-passing success is probabilistic, both the outcome of the algorithm’s execution and the clique number of the information graph become random variables. To deduce the expected optimality gap, we propose employing a decision tree representation to account for all possible message-passing outcomes. The upper diagram in Fig. 3 shows this decision tree for the network of five agents shown in Fig. 2, where the red dashed lines represent unsuccessful messages and the black arrows denote successful ones. The lower diagram in Fig. 3 displays the associated clique number for each message-passing sequence outcome. For instance, the leftmost path on the decision tree, indicating a scenario where no messages are successfully passed, results in a clique number of one. In contrast, the rightmost path, which signifies a scenario in which all messages are successfully delivered, resulting in $\mathcal{W}(\mathcal{G}_{I})\!=\!n\!=\!5$. With a comprehensive overview of all possible message-passing scenarios,the expected optimality gap of Algorithm 2 can be accurately characterized as follows.

As shown in Fig. 3, a probabilistic communication chain of length $n-1$ has $2^{n-1}$ possible message-passing sequences. Denote the collection of all such sequence outcomes as $\mathcal{S}_{seq}$, and the random variable associated with any given sequence outcome as $seq$. The probability of each $seq\in\mathcal{S}_{seq}$ can be computed from a combination of $n-1$ Bernoulli distributions, each representing a possible connection between agents, that is, $seq\sim\mathsf{B}(p_{1},\ldots,p_{n-1})$. Consequently, computing the clique number and associated probability for each sequence individually, will lead to an exponential time computation to determine $\alpha_{p}$. However, as seen in Fig. 3, multiple sequence outcomes can have the same clique number. In what follows, we propose a methodology that groups sequences based on their underlying structure. Specifically, to determine the probability of each clique number, we analyze the structure common to sequences that result in the same clique numbers and derive an exact formula for these probabilities. Our approach reduces the complexity of computing $\alpha_{p}$ to polynomial time. The critical information in our study is that the clique number is defined by the length of the longest directed path in the message-passing graph, plus one. We start with the following result. In this result and what follows, to simplify the notation, we write $P(\mathcal{W}(\mathcal{G}_{I}))$ as $P(\mathcal{W})$.

In what follows, we explain how to compute $P(\mathcal{W}\geq l+1)$ to fully describe $\alpha_{p}$ from (4). $P(\mathcal{W}\geq l+1)$ is equivalent to determining the probability of a family of message-passing sequences achieving a maximum connected component length of $l$. To this end, we introduce some essential definitions. A family of message-passing sequences, denoted by $\mathcal{F}$, refers to a group of sequences that exhibit a specific pattern of connectivity. Thus, a family of message-passing sequences is an event associated with the random variable $seq$. With a slight abuse of terminology, we define a generative sequence as the guideline in which a connectivity structure is imposed on some of the edges of the massage-passing sequence, e.g., the first two edges are connected, but the fourth is not. Thus, a generative sequence becomes basis for a family of sequences in which all members have the first two edges connected but the fourth not. We denote a generative sequence by $g(\mathcal{C},\mathcal{D})$, where $\mathcal{C},\mathcal{D}\subset\{1,\cdots,n-1\}$, respectively, specify the set of connected edges and disconnected edges of the generative sequence. For examples of generative sequences, see Fig. 4. We let $\mathcal{F}(g(\mathcal{C},\mathcal{D}))$ to denote the family generated by $g(\mathcal{C},\mathcal{D})$.

Lemma II.3’s proof follows trivially by writing all the outcomes generated by $g(\mathcal{C},\mathcal{D})$ and adding their probabilities.

We call two generative sequences independent when the families they initiate are distinct, in the sense that there exists no $seq\in\mathcal{S}_{seq}$ that is a member of the families generated by these generative sequences. For example, in top plot of Fig. 4 generative sequences A and B, and A and C are independent, but generative sequences A and D are not independent.

Next, we walk through the process of creating a family of message-passing sequences that feature connected components with a minimum length of $l\in\{1,\ldots,n-1\}$. For a specified $l$, we consider the generative sequences $g_{i}^{l}(\mathcal{C}_{i},\mathcal{D}_{i})$, where $i\in\{1,\ldots,n-l\}$, with $\mathcal{C}_{i}=\{i,i+1,\ldots,i+l-1\}$ representing the pre-specified connected components, and $\mathcal{D}_{i}=\{i-1\}$ indicating the pre-specified disconnected components, noting that $\mathcal{D}_{1}=\emptyset$. These generative sequences each contribute to the creation of families of message-passing sequences that ensure the presence of connected components at least $l$ units long. Collectively, these sequences constitute $\cup_{i=1}^{n-l}\mathcal{F}(g^{l}_{i})$, capturing the full set of message-passing sequences with connected components of at least $l$ in length, as depicted in Fig. 4 through examples involving a chain of $8$ agents. It is noteworthy that

Given the construction where $\mathcal{C}_{i}\cap\mathcal{D}_{j+1}\neq{\emptyset}$ for any $i\in\{1,\ldots,l\}$ and $j\in\{i,\ldots,l+1\}$, as illustrated in Fig. 4, the families generated by $g_{i}^{l}$ for $i\in\{1,\ldots,l+1\}$ are independent and thus mutually exclusive events. Therefore,

However, families from $i=l+1$ to $i=n-l$ have dependencies that we discuss next. With the same statement used for $i\in\{1,\cdots,l+1\}$, a family $\mathcal{F}(g_{i}^{l})$ with $i\in\{l+2,\cdots,n-l\}$ will be dependent with families with $j\in\{1,\ldots,i-l-1\}$ as $(\mathcal{C}_{i}\cup\mathcal{D}_{i})\cap(\mathcal{C}_{j}\cup\mathcal{D}_{j})\!=\!\emptyset$. Therefore, we are seeking for the independent set of families in $\mathcal{F}(g_{i}^{l})$ which can defined as the sequences in $\mathcal{F}(g_{i}^{l})$ that do not belong to previous families $\mathcal{F}(g_{j}^{l})$, in set notation $\mathcal{F}(g_{i}^{l})\backslash\mathcal{F}(g_{j}^{l})$. Note that by invoking a general probability rule ¹¹1For two independent events $A$ and $B$, we have $P(A\backslash B)=P(A)\cdot(1-P(B))$[17]. we obtain

As a generalization for the previous expression, for the sake of understanding, let us consider the families that creates dependency to $\mathcal{F}(g_{i}^{l})$, $\cup_{j=1}^{i-l-1}\!\mathcal{F}(g_{j}^{l})$, such as $\mathcal{S}_{i}$. Then, notice that

To obtain a close expression for (6) it is needed to find the independent expression for each family. By a simple set operation it can be seen that

where $\widetilde{\mathcal{F}}(g_{i}^{l})\!=\!\mathcal{F}(g_{i}^{l})\backslash\mathcal{S}_{i}$ is the independent expressions for families $i\in\{l+2,\ldots,n-l\}$. Therefore

Each $P(\mathcal{F}(g_{j}^{l}))$ is computed from (5). Notice that equation (8) can be computed in $\mathcal{O}(n-l)$ oracle calls to (5) and there is no need of computing all of the $2^{n-1}$ the possible sequences. With equation (8) at hand, from Lemma II.2 we arrive at

Now, using expression (9), the proposed optimality gap in Theorem II.1 can be easily computed in polynomial time. That not only allows the computation of the gap itself, but creates the possibility of pursuing an analysis of how the algorithm would perform in the worst-case scenario as a function of the parameters of the system.

By allowing repeated communication, we can increase the probability of message delivery and subsequently improve the optimality gap. However, multiple message-passing increases the end-to-end delay of executing the algorithm and may not be possible in resource limited scenarios. Therefore, the natural research question arises pertaining to the allocation of a finite quantity of multiple message-passing rights in an optimal manner.

The key observation is that the best agent to reinforce is not solely the one with the lowest communication probability but a combination of communication reliability and the agent’s position in the communication chain. This is demonstrated in our empirical study in Section IV.

The message-passing process from agent $i$ to agent $i+1$ follows a Bernoulli distribution

where $p_{i,0}$ is the probability of agent’s successful delivery in one communication, $T_{i}$ is the number of trials (messages sent) and $r$ is the number of successes (messages delivered). Since communication between two nodes is established when at least one success occurs, the probability that the recipient gets the message is

Note that $p_{i}(T_{i},r\geq 1)$ is the new communication probability from agent $i$ to agent $i+1$, for the sake of understanding, we will keep referring to them as $p_{i}$. By considering a Bernoulli measure, expression in Lemma II.3 can be re-defined as

enabling us to analyze the behavior of message-passing reinforcement for $T_{i}\geq 1$. Note that when the message-passing count $T_{i}$ for a device $i$ increases, the expected optimality gap needs to be recalculated. As previously mentioned, for each $l$, calculating its probability $P(\mathcal{W}\geq l)$ requires a time complexity of $\mathcal{O}(n-l)$. Consequently, the gap $\alpha_{p}$ can be determined within $\mathcal{O}(\frac{n\cdot(n-1)}{2})$, indicating that optimizing the communication strategy is a polynomial-time process. Further examination of (9) reveals that doubling the message-passing trail for agent $k$ does not influence families where $i\leq k-l+1$. Thus, by equipping the system with a certain memory capacity, computation time of $\alpha_{p}$ for all possible reinforcements can be significantly reduced.

Consider a multi-sensor deployment problem where a group of $8$ heterogeneous agents $\mathcal{A}=\{1,\ldots,8\}$, each with two sensors to deploy at some prespecified deployment points of interest. There are $25$ total locations where sensors can be deployed, but each agent $i\in\mathcal{A}$ has access to only a subset of $12$ locations, denoted by $\mathcal{B}_{i}$. The sets $\mathcal{B}_{i}$ are not distinct, but using a simple trick, we can create the local selection set of the agents in a distinct way as $\mathcal{P}_{i}=\{(i,b)\mid b\in\mathcal{B}_{i}\}$ for $i\in\mathcal{A}$. The environment includes a set of $2,200$ randomly generated sampled points, denoted by $\mathcal{V}$. The sensor deployment objective is to cover as many points from $\mathcal{V}$ as possible, which is accomplished by solving a maximization problem of the form (1) with $\kappa_{i}=2$ and the utility function given by $f(\mathcal{S})=\sum\nolimits_{p\in\mathcal{V}}g(p)$, where $g(p)=1$ if there exists at least one element $(\ell,b)\in\mathcal{S}$ such that $\|c-p\|\leq\rho_{\ell}$; otherwise $g(p)=0$. Here, $\rho_{\ell}$ is the coverage radius of sensor $\ell$. This utility function is known to be submodular and monotone increasing. This problem is illustrated in Fig. 5.

For visualization of the communication chain, we label the agents alphabetically. Now consider two different sequences of communication: lexicographic order ABCDEFGH and a random shuffle DBHGFCAE, as shown in Fig. 6. Note that with $n$ agents, there are up to $n!$ possible communication chains that can be established. In this section, we consider only two sequences to illustrate the particular behavior under the allowance for extra message-passing. It is important to note that due to the probabilistic nature of the problem, the results presented in this section are the mean values from 10,000 iterations for each scenario.

Table I shows the results of our study for the communication chains illustrated in Fig. 6. The second column presents the average utility value over 10,000 iterations when agents use Algorithm 2 to determine their deployment locations. The third column shows $\alpha_{p}$ computed from (4). The fourth column identifies the agent $a^{\star}$ whose communication is reinforced by allowing two back-to-back communication trials. The agent to be reinforced is determined by computing $\alpha_{p}$ for all possible reinforcements, with these values shown in Table II. The fifth column indicates the edge label that is reinforced (the link coming out of $a^{\star}$). Finally, the sixth and seventh columns present the average utility value and $\alpha^{\prime}_{p}$ computed from (4) under communication reinforcement. As expected, we observe that $\alpha^{\prime}_{p}>\alpha_{p}$, indicating that reinforcement improves the expected optimality gap. This improvement is also reflected in the utility values. Another noteworthy observation is that the reinforced agent is not necessarily the one with the lowest communication probability, and the reinforced edge differs between sequences.

This paper addressed the problem of decentralized submodular maximization subject to partition matroid constraint using a sequential greedy algorithm with probabilistic inter-agent message-passing. We proposed a communication-aware framework that considers the reliability of communication between connected devices, emphasizing its impact on the optimality gap. Our analysis introduced the notion of the probabilistic optimality gap $\alpha_{p}$, highlighting its crucial role in understanding the expected performance of the sequential greedy algorithm under probabilistic communication. By characterizing $\alpha_{p}$ as an explicit function of communication probabilities, we created a framework to answer critical questions such as which agent should be reinforced (allowed multiple communications) to improve the optimality gap or how to compare the optimality gaps of various communication chains, where the order of agents in the chain changes while their reliability remains the same. In our empirical study, we specifically focused on the case where only one agent is allowed to communicate twice. However, the methodology we presented is generalizable and can be extended to scenarios where multiple agents are allowed multiple message-passing opportunities. This extension can be framed as a set function maximization problem subject to a uniform matroid constraint, with $\alpha_{p}$ as the utility function. What agents to reinforce can be efficiently decided using a sequential greedy approach, given that $\alpha_{p}$ is monotone increasing and, if shown to be submodular, would benefit from the known optimality gap of $0.63$. Future work will focus on formally proving the submodularity of $\alpha_{p}$ and developing strategies to optimize communication reinforcement in more complex scenarios involving multiple agents. We aim also to leverage insights from this study to design more robust and efficient decentralized systems for real-world applications, particularly in environments where communication reliability is variable and resources are limited.