Abstract Negotiation scenarios involving nonlinear utility functions are specially challenging, because traditional negotiation mechanisms cannot be applied. Even mechanisms designed and proven useful for nonlinear utility spaces may fail if the utility space is highly nonlinear. For example, although both contract sampling and constraint sampling have been successfully used in auction based negotiations with constraint-based utility spaces, they tend to fail in highly nonlinear utility scenarios. In this paper, we will show that the performance of these approaches decrease drastically in highly nonlinear utility scenarios, and propose a mechanism which balances utility and deal probability for the bidding and deal identifification processes. The experiments show that the proposed mechanisms yield better results than the previous approaches in highly nonlinear negotiation scenarios