Automated negotiation is a key issue to facilitate e- Business. It is an on-going research area and attracts attention from both research communities and industry. In this paper, we propose a multiple-stage co-operative automated negotiation architecture, including a sophisticated negotiation strategy and protocol, to resolve the agents? conflicts. This proposed architecture attempts to address the discovery of joint efficiency for the negotiating agents in large and complex problem spaces using a co-evolutionary method. A game theoretic method is adapted to distribute the payoffs generated from the coevolutionary method. The architecture supports interactions between the two methods to demonstrate that high-quality solutions can be found through their complimentary functions. Using the structure it is possible to refine and explore potential agreements through an iterated process. This article also reports some experimental results and discussions.