Asymmetric Distributed Constraint Optimization Problems

Tal Grinshpoun, Alon Grubshtein, Roie Zivan, Arnon Netzer, Amnon Meisels

Abstract

This paper introduces Asymmetric Distributed Constraint Optimization Problems (ADCOPs), a novel framework for multi-agent coordination where agents incur different personal costs for shared constraints. Traditional Distributed Constraint Optimization (DCOP) models assume symmetry, which fails to capture real-world scenarios like meeting scheduling where preferences vary significantly between participants. We present a suite of complete and local search algorithms specifically designed for the ADCOP framework. Our results demonstrate that these algorithms are significantly faster, more scalable, and more effective at preserving privacy than existing workarounds like the Private Events As Variables (PEAV) model.

Introduction

In Distributed Constraint Optimization (DCOP), a group of autonomous agents must coordinate their actions to minimize a global cost function. A fundamental assumption in standard DCOP research is symmetry: if two agents share a constraint, they both incur the exact same cost for any given outcome. However, real-world interactions are inherently asymmetric. For example, in a shared task, one agent might find a specific deadline mildly inconvenient while another finds it impossible due to prior commitments.

Previous attempts to model this asymmetry relied on the PEAV (Private Events As Variables) model. PEAV attempts to force asymmetry into a symmetric framework by duplicating variables for each agent and adding "hard equality" constraints to ensure they agree on a value. As we will discuss, this approach introduces significant computational overhead and creates algorithmic "traps" that hinder effective optimization.

The ADCOP Framework

The authors propose the ADCOP framework to represent asymmetric preferences naturally. In an ADCOP, a constraint between agents maps a combination of variable assignments to a tuple of costs—one for each participating agent. This allows each agent to maintain its own private cost table for shared interactions.

Figure 1: ADCOP cost representation using tuples for asymmetric preferences.

The PEAV Trap

The primary drawback of the PEAV model is its impact on the search space. By duplicating variables, the state space grows quadratically, leading to a "bloated" representation. More critically, PEAV creates artificial local optima. In local search, any state that satisfies the hard equality constraints becomes a trap; algorithms get stuck because moving to a better global state would require temporarily violating the equality constraint, which standard DCOP algorithms are not designed to do.

Figure 2: The PEAV model's expanded search space and complex variable dependencies compared to the ADCOP model.

Methods

To address these challenges, the paper introduces two classes of algorithms tailored for ADCOPs:

  1. Complete Search (Exact Solutions):
    • SyncABB (Synchronous Asymmetric Branch & Bound): A synchronous algorithm that uses back-checking to ensure all agents' costs are aggregated before proceeding, ensuring the global optimum is found.
  2. ATWB (Asynchronous Two-Way Bounding): An asynchronous variant that allows agents to check bounds in parallel, potentially increasing efficiency in distributed environments.
  3. Local Search (Approximate Solutions):
    • ACLS (Asymmetric Coordinated Local Search): A coordination-based approach where agents evaluate the "impact" of their potential moves on neighbors.
  4. MCS-MGM & GCA-MGM: Variants of the Maximum Gain Message algorithm. These utilize "minimal constraint sharing," where agents only reveal small portions of their private cost functions when a neighbor's action would cause a significant cost increase. GCA-MGM notably provides a mathematical guarantee of convergence to a local optimum.

Evaluation and Results

The algorithms were tested across three domains: Random Asymmetric Max-DisCSPs, Random Graphical Games, and Scale-Free Networks.

Key Findings

  • Performance: ADCOP-specific complete search algorithms like SyncABB outperformed PEAV-based standard algorithms by orders of magnitude in terms of runtime. Surprisingly, the synchronous SyncABB often beat the asynchronous ATWB due to lower communication overhead.
  • Scalability: While PEAV-based models often crashed or timed out with more than 6 agents, the ADCOP algorithms scaled effectively to larger, denser networks.
  • Solution Quality: In local search benchmarks, MCS-MGM and ACLS consistently found lower-cost solutions than standard DCOP algorithms (like DSA or Max-Sum), which frequently failed to converge in asymmetric settings.
  • Privacy: Using entropy-based metrics, the authors demonstrated that their algorithms reveal significantly less private information than full-disclosure methods, with the majority of information leakage occurring only in the initial iterations.

Conclusion

By formalizing Asymmetric DCOPs, this research bridges a critical gap between theoretical multi-agent coordination and real-world application. The ADCOP framework avoids the computational pitfalls of variable duplication while providing a robust platform for efficient, private optimization. Future work will focus on extending these methods to n-ary constraints and exploring dynamic environments where agent preferences evolve over time.

Summary updated

BibTeX
@article{grinshpoun2013asymmetric,
  author = {Tal Grinshpoun and Alon Grubshtein and Roie Zivan and Arnon Netzer and Amnon Meisels},
  title = {{Asymmetric Distributed Constraint Optimization Problems}},
  journal = {J. Artif. Intell. Res.},
  year = {2013},
  doi = {10.1613/jair.3945},
}
Figure