1. In a system having a processor for carrying out a negotiation concerning a set of actions to be performed by selected ones of a plurality of participants, a method for carrying out the negotiation with at least one of the plurality of participants encapsulating a constraint solver in a service, comprising: defining processing instructions in a memory of the system for carrying out the negotiation using the service encapsulating the constraint solver; and executing the processing instructions for carrying out the negotiation with the service encapsulating the constraint solver; wherein said executing the processing instructions for carrying out the negotiation with the service encapsulating the constraint solver further comprises: (A) establishing encapsulation input in the memory that includes: (a) a mapping between aspects of parameters of the service and corresponding variables of the constraint solver, (b) a translation between negotiation statements on the aspects of the parameters of the service and domain constraints imposed on the corresponding variables of the constraint solver, and (c) a set of semantic constraints of the service on variables of the constraint solver; (B) constructing a graph in the memory for negotiating the set of actions to be performed; each node of the graph defining a negotiation context that has associated therewith a constraint store with at least a set of domain constraints stored therein; (C) propagating constraints defined by the set of semantic constraints and the set of domain constraints associated with nodes of the graph to other participants in the negotiation as domain constraints augment the set of semantic constraints during the negotiation.