Agent negotiation over multiple issues is often seen as the process of searching for a solution in a complex and large space. Depending on the negotiation mechanism such search space can be dynamic wherein agents may be cooperative or non-cooperative. In a realistic negotiation, agents are unwilling to reveal their utility functions to their opponents or collaborators. These important characteristics of negotiation increase the complexity of the design of efficient and effective negotiation agents. In this paper, we propose a novel approach that combines a co-evolutionary mechanism with the notion of degree of satisfaction. The former effectively searches the space, while the latter improves negotiation efficiency. Agents under the proposed scheme can carry out co-operative, or non-cooperative, without revealing their utility functions. The proposed approach is implemented as a prototype system and evaluated through a number of experiments. The evaluation shows the effectiveness of the proposed approach in cooperation and non-cooperation.