One of the central issues in facilitating mobile teamwork is the creation and establishment of teams from autonomous agents. It is widely accepted that team building assumes an expression of, and agreement on, common interests. This paper describes a new approach to the provision of mechanisms to facilitate the creation of teams and to help resolve conflict through automated negotiation. The negotiation mechanism is mplemented by a combination of a game theory approach and a co-evolutionary approach. This scheme involves a process that iterates over the generation of a set of strategies by the co-evolutionary approach, the encoding of these strategies into a payoff matrix, and the reasoning on the matrix by the game theory approach in order to find an optimised point. The process terminates when the game theory approach finds an optimised point that satisfies both agents. The main advantage of this system is that agents, without knowing each other?s strategies, agree on an optimised solution that conforms to Nash equilibrium and Pareto efficiency.