Distributed constraint optimization (DCOP or DisCOP) is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is minimized. Distributed Constraint Satisfaction is a framework for describing a problem in terms of constraints that are known and enforced by distinct participants (agents). The constraints are described on some variables with predefined domains, and have to be assigned to the same values by the different agents. Problems defined with this framework can be solved by any of the algorithms that are designed for it. The framework was used under different names in the 1980s. The first known usage with the current name is in 1990. Definitions DCOP The main ingredients of a DCOP problem are agents and variables. Importantly, each variable is owned by an agent; this is what makes the problem distributed. Formally, a DCOP is a tuple , where: is the set of agents, . is the set of variables, . is the set of variable-domains, where each is a finite set containing the possible values of variable . If contains only two values (e.g. 0 or 1), then is called a binary variable. is the cost function. It is a function that maps every possible partial assignment to a cost. Usually, only few values of are non-zero, and it is represented as a list of the tuples that are assigned a non-zero value. Each such tuple is called a constraint. Each constraint in this set is a function assigning a real value to each possible assignment of the variables. Some special kinds of constraints are: Unary constraints - constraints on a single variable, i.e., for some . Binary constraints - constraints on two variables, i.e, for some is the ownership function. It is a function mapping each variable to its associated agent. means that variable "belongs" to agent . This implies that it is agent 's responsibility to assign the value of variable . Note that is not necessarily an injection, i.e., one agent may own more than one variables. It is also not necessarily a surjection, i.e., some agents may own no variables. is the objective function. It is an operator that aggregates all of the individual costs for all possible variable assignments. This is usually accomplished through summation: