In this paper, we use formal specification techniques to provide precompiled and provably correct domain-specific knowledge to autonomous agents. This allows for verifying agent interactions in the environment. In particular, we show that negotiating agents can resolve mutually incompatible local preferences and settle for an acceptable compromise by reasoning with formally specified default and exception behaviors. We use Swarm, a formal specification language, to characterize the preference of negotiating agents that are using a variation of the contract-net protocol. The framework is illustrated on an example from the service interaction problem in telecommunications systems. The combination of formal specification and negotiating agents is a multi-paradigm approach that we believe will provide comprehensive solutions to a variety of multi-agent coordination problems.