In non-cooperative multi-agent planning, resolution of multiple conflicting goals is the result of finding compromise solutions. Previous research has dealt with such multi-agent problems where planning goals are well-specified, subgoals can be enumerated, and the utilities associated with subgoals known. Our research extends the domain of problems to include non-cooperative multi-agent interactions where planning goals are ill-specified, subgoals cannot be enumerated, and the associated utilities are not precisely known. We provide a model of goal conflict resolution through negotiation implemented in the PERSUADER, a program that resolves labor disputes. Negotiation is performed through proposal and modification of goal relaxations. Case-Based Reasoning is integrated with the use of multi-attribute utilities to portray tradeoffs and propose novel goal relaxations and compromises. Persuasive arguments are generated and used as a mechanism to dynamically change the agents’ utilities so that convergence to an acceptable compromise can be achieved.