# A Population-Based Search Approach to Solve Continuous Distributed Constraint Optimization Problems
## 4 Theoretical Analysis  
In this section, we prove the anytime property of PGSA and provide some theoretical properties of PLSA and PGSA in terms of communication, computation, and memory. We assume that the graph structure is a binary constraint graph \(G=(N,E)\), the number of nodes is \(|A|\), and the number of edges of the constraint graph is \(|F|\). Since the agent calculates the sum of local utilities (Algorithm 1: Line 14 and Algorithm 2: Line 8) or adds the sum of utilities of children agents (Algorithm 2: Line 14) in the decision phase, and the agent updates its value assignments in the update phase (Algorithm 1: Line 18 and Algorithm 2: Line 23), we define one iteration as the entire process of the decision and update phase. **Theorem 1**. : _PGSA is an anytime algorithm._  
Proof. : In PGSA, the root agent tracks the aggregate utility through a pseudo-tree. We assume that the \(\Gamma\) and the aggregate utility \(\mathbf{U}\) at the \(m\) iterations are \(\Gamma^{m}\) and \(\mathbf{U}^{m}\), respectively. According to Algorithm 2, Line 32-33, the \(\Gamma^{m}\leq\mathbf{U}^{m}\). Only the root agent finds the aggregate utility \(\mathbf{U}^{m+\Delta}\) at the \(m+\Delta(\lambda>0)\) iterations and \(\mathbf{U}^{m+\Delta}<\Gamma^{m}\leq\mathbf{U}^{m}\), \(\Gamma^{m+\Delta}\) is assigned the value of \(\mathbf{U}^{m+\Delta}\), the \(\Gamma^{m+\Delta}<\Gamma^{m}\). Otherwise, \(\Gamma^{m}\) maintains the best aggregate utility so far. In other words, \(\Gamma^{m+\Delta}\leq\Gamma^{m}\) and the aggregate utility decreases monotonically as the number of iterations increases. Therefore, the PGSA is an anytime algorithm. **Theorem 2**. : _The total number of messages of PLSA and PGSA with \(t\) iterations are \(2t|F|\) and \(4t|F|\), respectively._  
Proof. : In one iteration of PLSA, for every constraint \(f_{ij}(x_{i},x_{j})\), the agent \(x_{i}\) sends a message to \(x_{j}\) to share value assignments and vice versa. So there are two messages per edge, and thus the number of messages is \(2*|F|\), where \(|F|\) is the number of constraints and also the number of edges. Therefore, the total number of messages of PLSA with \(t\) iterations is \(2t|F|\). Similarly, the agent \(x_{i}\) in PGSA sends a message to \(x_{j}\) and receives a message from \(x_{j}\). In addition, the agent \(x_{i}\) sends a message (the sum of utilities) to the parent agent (Algorithm 2: Line 15) and **Messages** to children agents (Algorithm 2: Line 24). Hence, the total number of messages of PGSA with \(t\) iterations is \(4t|F|\). **Theorem 3**. : _In one iteration, the message sizes of PLSA and PGSA are, respectively, \(K\) and \(K+1\), where \(K\) is the number of solutions._  
Proof. : In PLSA, the agent sends a message containing \(K\) values to its neighbors in one iteration. Therefore, the message size of PLSA in one iteration is \(K\), where \(K\) is the number of solutions. In PGSA, the agent sends three types of messages: the values assignments, the sum of local utilities, and **Messages**, whose message sizes are \(K\), \(K\), and \(K+1\), respectively. Hence, the message size of PGSA in one iteration is \(max\{K,K,K+1\}=K+1\). **Theorem 4**. : _In one iteration, the computational overhead of one agent in PLSA and PGSA are, respectively, \(K(|\mathcal{N}|+1)\) and \(K(|\mathcal{N}|+1+|\mathcal{C}|)\), where \(K\) is the number of solutions, \(|\mathcal{N}|\) is the number of neighbors, and \(|\mathcal{C}|\) is the number of children agents in the BFS pseudo-tree. Further, the overall computational overheads of PLSA and PGSA in one iteration are \(K(2|F|+|A|)\) and \(K(2|F|+2|A|-1)\), respectively._  
**Proof. ** We define the number of neighbors of one agent is \(|\mathcal{N}|\). In PLSA, each agent calculates the sum of local utilities with its neighbors and updates the value assignments of \(K\) solutions. The computational overhead of one agent in one iteration is \(K(|\mathcal{N}|+1)\).