Applying Max-Sum to Asymmetric Distributed Constraint Optimization

Roie Zivan, Tomer Parash, Yarden NavehIJCAI 2015

Introduction

In Distributed Constraint Optimization Problems (DCOP), multiple agents coordinate to find a global assignment of variables that minimizes total cost. Traditional DCOP models assume symmetry, where shared constraints result in the same cost for all involved agents. However, real-world scenarios—such as meeting scheduling or resource allocation—are often asymmetric, as different participants may have vastly different private valuations of the same outcome.

Asymmetric DCOPs (ADCOPs) were developed to address these nuances. While local search algorithms are common in symmetric DCOPs, they often struggle with convergence or solution quality in asymmetric settings. This paper explores the adaptation of Max-Sum, a popular inference-based algorithm, to effectively solve ADCOPs while maintaining privacy and performance.

Methods: Asymmetric Factor Graphs and Node Ordering

The researchers adapted Max-Sum ADVP (an alternating-layer version of Max-Sum with value propagation) by redefining the underlying factor graph. In a standard DCOP, a constraint is a single function node. In an ADCOP, each binary constraint is represented by two function nodes, allowing each agent to maintain its own private valuation.

Because Max-Sum ADVP processes nodes in a specific sequence based on a Directed Acyclic Graph (DAG), the authors introduced three Inner Constraint Orderings (ICO) to manage the four nodes (two variables and two functions) in an asymmetric constraint:

  • SIO (Standard): Function nodes are positioned between variable nodes.
  • DIO (Diverse): Variable nodes are grouped together, separated from function nodes.
  • PIO (Partial): A mixed ordering where one function node is processed before the second variable.
Visual representation of the three proposed node orderings: Standard (SIO), Diverse (DIO), and Partial (PIO).

The authors mathematically proved that using the Standard (SIO) ordering ensures Max-Sum ADVP performs identically on an asymmetric problem as it would on an equivalent symmetric one, preserving its known convergence properties.

Key Results and Performance Analysis

The approach was evaluated against common benchmarks, including uniform random problems, scale-free networks, and meeting scheduling tasks. Max-Sum ADVP significantly outperformed existing ADCOP-specific local search algorithms, such as MCS-MGM and GCA-MGM, in terms of solution quality.

Comparison of cost over iterations for various Max-Sum and local search algorithms on ADCOP benchmarks.

As shown in the performance data, while the Standard (SIO) ordering converged rapidly, the Partial (PIO) ordering—which breaks execution symmetry—eventually achieved even lower-cost solutions. This suggests that PIO acts as a form of exploration, helping the algorithm escape local minima that might trap the standard symmetric version.

Privacy and Convergence

A critical advantage of the Max-Sum approach in ADCOPs is privacy. Unlike local search methods that exchange specific cost table entries, Max-Sum propagates aggregated utilities. The study found that Max-Sum revealed an average of only 3.3 to 12.4 cost entries per agent, whereas local search methods exposed significantly more private data to neighbors.

Furthermore, the robustness of the inference-based approach was confirmed by the fact that most Max-Sum variants performed similarly on both symmetric and asymmetric versions of the same problem, provided the correct node ordering was applied.

Conclusion

This research demonstrates that Max-Sum is a powerful tool for solving Asymmetric DCOPs. By utilizing asymmetric factor graphs and specific node orderings like SIO and PIO, the algorithm provides superior solution quality and privacy compared to traditional local search methods. Future work may look toward extending these findings to N-ary constraints involving three or more agents and optimizing the communication overhead inherent in doubling function nodes for asymmetric models.

Summary updated

BibTeX
@inproceedings{zivan2015applying,
  author = {Roie Zivan and Tomer Parash and Yarden Naveh},
  title = {{Applying Max-Sum to Asymmetric Distributed Constraint Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure