An automated negotiation mechanism based on co-evolution and game theory

ABSTRACT

The problems associated with current automated negotiation approaches are of little feasibility in practical industry applications. This paper describes a new method that combines a game theory approach and a co-evolutionary approach to support an effective negotiation model for agents to resolve conflict. Under this proposed method, the agents without knowing the other agent's strategies and payoffs, produce an optimised resolution that complies Nash equilibrium and Pareto efficiency concepts. We use a finitely repeated prisoner's dilemma game to demonstrate the proposed method.

REFERENCES

• 1: Axelrod. R., 1987, The Evolution of Strategies in the Iterated Prisoner's Dilemma, Genetic Algorithms and Simulated Annealing, edited by L. Davis, London: Pittman. pp. 32-41.
• 2: K. Suzanne Barber , David C. Han , Tse-Hsin Liu, Strategy selection-based meta-level reasoning for multi-agent problem-solving, First international workshop, AOSE 2000 on Agent-oriented software engineering, p.269-283, January 2001, Limerick, Ireland
• 3: Castlefranchi, C., & Conte, R., 1997, Limits of Strategic Rationality for Agents and M-A Systems. Proc of the 4th ModelAge Workshop on "Formal Models of Agents, pp. 59-70.
• 4: Lorrie Faith Cranor , Paul Resnick, Protocols for automated negotiations with buyer anonymity and seller reputations, Netnomics, v.2 n.1, p.1-23, March 2000 [doi>10.1023/A:1019170325938]
• 5: Fudenberg D., Levine D. K., 1998, The Theory of Learning in Games, Cambridge: M.I.T. Press.
• 6: John R. Koza , James P. Rice, Genetic programming (videotape): the movie, MIT Press, Cambridge, MA, 1992
• 7: Sarit Kraus, Negotiation and cooperation in multi-agent environments, Artificial Intelligence, v.94 n.1-2, p.79-97, July 1997 [doi>10.1016/S0004-3702(97)00025-8]
• 8: Kreps, D. M., 1990, A Course in Microeconomic Theory, Princeton University Press.
• 9: Oliver, J. R., 1997, On Automated Negotiation and Electronic Commerce, PhD thesis, University of Pennsylvania.
• 10: Peyman. F., Jennings. N. R., Lomuscio. A. R., Parsons. S., Sierra. C. & Wooldridge. M., 2001, Automated Negotiation: Prospects, Methods and Challenges, Int. J. of Group Decision and Negotiation, Vol 10, No 2, pp.199-215.
• 11: Peyman, F., 2000, Automated Service Negotiation Between Autonomous Computational Agents, PhD thesis, University of London.
• 12: Rasmusen, E., 1994, Games & Information: An Introduction to Game Theory, Blackwell Publishers.
• 13: Rosenschein, J. S., & Zlotkin, G., 1994, Rules of Encounter, Cambridge. USA: The MIT Press.
• 14: Soo, V-W & Wu, S-H., 2000, Negotiation Without Knowing Other Agents Payoffs in the Trusted Third-Party Mediated-Game, Second workshop on game theoretic and decision theoretic agents.
• 15: Wunderlich, R., 1998, Genetic Strategy Selection for the Finitely Repeated Prisoner's Dilemma, http://www.roland.wunderlich.com/Papers/GameTheory.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Design, Experimentation, Theory

Keywords:
game theory, genetic algorithm, no fear of deviation, prisoner dilemma