A cooperative, multi-step negotiation mechanism for multi-agent systems is presented. This mechanism uses marginal utility gain and marginal utility cost to structure the negotiation process. This enables an agent to understand another agent's situation in order to find a solution that increases their combined utility. These two values summarize the agent's local information and reduce the communication load. This allows agents to negotiate over multiple attributes of the commitment which makes it more likely for agents to find a solution that increases the global utility by producing more options. Performed experiments show how different protocols perform in a variety of common situations. The experiments allow observation of the factors that affect the agent's ability to strike a good balance between the negotiation gain and the negotiation cost.