Asymmetric distributed constraint optimization problems
From MaRDI portal
Abstract: Distributed Constraint Optimization (DCOP) is a powerful framework for representing and solving distributed combinatorial problems, where the variables of the problem are owned by different agents. Many multi-agent problems include constraints that produce different gains (or costs) for the participating agents. Asymmetric gains of constrained agents cannot be naturally represented by the standard DCOP model. The present paper proposes a general framework for Asymmetric DCOPs (ADCOPs). In ADCOPs different agents may have different valuations for constraints that they are involved in. The new framework bridges the gap between multi-agent problems which tend to have asymmetric structure and the standard symmetric DCOP model. The benefits of the proposed model over previous attempts to generalize the DCOP model are discussed and evaluated. Innovative algorithms that apply to the special properties of the proposed ADCOP model are presented in detail. These include complete algorithms that have a substantial advantage in terms of runtime and network load over existing algorithms (for standard DCOPs) which use alternative representations. Moreover, standard incomplete algorithms (i.e., local search algorithms) are inapplicable to the existing DCOP representations of asymmetric constraints and when they are applied to the new ADCOP framework they often fail to converge to a local optimum and yield poor results. The local search algorithms proposed in the present paper converge to high quality solutions. The experimental evidence that is presented reveals that the proposed local search algorithms for ADCOPs achieve high quality solutions while preserving a high level of privacy.
Recommendations
- Adopt: asynchronous distributed constraint optimization with quality guarantees
- Leximin asymmetric multiple objective distributed constraint optimization problem
- BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm
- Balancing local resources and global goals in multiply-constrained DCOP
- A class of algorithms for distributed constraint optimization.
Cited in
(18)- Forward bounding on pseudo-trees for DCOPs and ADCOPs
- Incentive-based search for efficient equilibria of the public goods game
- Incentive-based search for equilibria in Boolean games
- Integrating domain and constraint privacy reasoning in the distributed stochastic algorithm with breakouts
- A dual-population search differential evolution algorithm for functional distributed constraint optimization problems
- PC-SyncBB: a privacy preserving collusion secure DCOP algorithm
- Governing convergence of Max-sum on DCOPs through damping and splitting
- Privacy preserving region optimal algorithms for symmetric and asymmetric DCOPs
- Explorative anytime local search for distributed constraint optimization
- Adopt: asynchronous distributed constraint optimization with quality guarantees
- Balancing local resources and global goals in multiply-constrained DCOP
- Partial cooperation in multi-agent local search
- scientific article; zbMATH DE number 5547836 (Why is no real title available?)
- M-DPOP: faithful distributed implementation of efficient social choice problems
- A review of literature on parallel constraint solving
- Leximin multiple objective DCOPs on factor graphs for preferences of agents
- Leximin asymmetric multiple objective distributed constraint optimization problem
- Proactive Dynamic Distributed Constraint Optimization Problems
This page was built for publication: Asymmetric distributed constraint optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842196)
