Clustering Variables by Their Agents

When approaching DCOPs with multiple variables per agent it is common practice to first decompose each agent into several virtual agents, each holding a single variable, and then solve the problem using standard DCOP algorithms. This solving method is generic and allows using state-of-the-art DCOP algorithms. Nevertheless, in some situations, such as in algorithms that use pseudo-trees, these virtual agents may be driven apart to different areas of the problem-solving process. This phenomenon has negative implications on both communication overhead and privacy. Thus, it is important that variables remain clustered together by their original agents. In the present study we show that it is impossible to achieve such clustering in some multiple-variable DCOPs. As an example, we relate to PEAV, which is the most popular formulation of multiple-variable DCOPs. We then state sufficient conditions under which the desired clustering is achievable. Finally, we propose a technique that enables the construction of clustered pseudo-trees for various DCOPs, including all PEAV-DCOPs, by strategically modifying the original problem.