Distributed constraint optimization

Distributed constraint optimization (DCOP) is the distributed analogue to constraint optimization.

Definition

A DCOP can be defined as a tuple $\langle A,V,{\mathcal {D}},F,\alpha ,\sigma \rangle$, where:

• $A$ is a set of agents;
• $V$ is a set of variables, $\{v_{1},v_{2},\ldots ,v_{|V|}\}$;
• ${\mathcal {D}}$ is a set of domains, $\{D_{1},D_{2},\ldots ,D_{|V|}\}$, where each $D\in {\mathcal {D}}$ is a finite set containing the values to which its associated variable my be assigned.
• $F$ is a set of $|V|^{2}$ cost functions, one for each pair of the variables, such that $f_{ij}:D_{i}\times D_{j}\rightarrow \mathbb {N} \cup \infty$. In other words, for all pairs of variables there exists a cost function that maps every possible value assignment of the variables to a cost. These functions can also be thought of as binary constraints between variables.
• $\alpha$ is a function $\alpha :V\rightarrow A$ mapping variables to their associated agent. $\alpha (v_{i})\mapsto a_{j}$ implies that it is agent $a_{j}$'s responsibility to assign the value of variable $v_{i}$. Note that it is not necessarily true that $\alpha$ is either an injection or surjection.
• $\sigma$ is a function $\sigma :F\rightarrow \mathbb {N} \cup \infty$ that aggregates the individual costs. This is usually accomplished through summation of the costs.

The objective of a DCOP is to have each agent assign values to its associated variables in order to either minimize or maximize $\sigma (F)$ for a given assignment of the variables.