We propose correct and efficient algorithms for locating the optimal contract of negotiating agents that represent their utility space with the constraints based utility space model. It is argued that the agents that use the model can be classified in to two extreme kinds: sensitive and insensitive. When the negotiation is between a sensitive agent and many in- sensitive agents, the optimal contract can be computed correctly and efficiently by avoiding Exhaustive Matching. © Springer-Verlag Berlin Heidelberg 2013.