A multi-issue negotiation protocol among competitive agents and its extension to a nonlinear utility negotiation protocol

ABSTRACT

Multi-issue negotiation mechanisms have been studied very widely and represent a promising field because most negotiations in the real world are multi-issue negotiations. We model multi-issue negotiation with competitive agents. This reflects the real world in which people have to make agreements on constraints. A combinatorial winner determination mechanism is employed for solving a constraint satisfaction problem with competitive agents. The features of our protocol include Pareto efficiency on constraints. Our experimental results show that our proposed protocol is scalable with the number of agents, and that a heuristic method can achieve good utility. The above protocol is designed for linear utility domains. We also extend our protocol so that we can handle nonlinear utilities.

REFERENCES

• 1: Mihai Barbuceanu , Wai-Kau Lo, Multi-attribute Utility Theoretic Negotiation for Electronic Commerce, Agent-Mediated Electronic Commerce III, Current Issues in Agent-Based Electronic Commerce Systems (includes revised papers from AMEC 2000 Workshop), p.15-30, January 2001
• 2: Shaheen S. Fatima , Michael Wooldridge , Nicholas R. Jennings, An agenda-based framework for multi-issue negotiation, Artificial Intelligence, v.152 n.1, p.1-45, January 2004 [doi>10.1016/S0004-3702(03)00115-2]
• 3: Catholijn Jonker , Valentin Robu, Automated Multi-Attribute Negotiation with Efficient Use of Incomplete Preference Information, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1054-1061, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.70]
• 4: M. Klein, P. Faratin, H. Sayama, and Y. Bar-Yam. Negotiating complex contracts. Group Decision and Negotiation, 12(2):58--73, 2003.
• 5: R. J. Lin and S. T. Chou. Bilateral multi-issue negotiations in a dynamic environment. In Proc. of AMEC V, 2003.
• 6: Xudong Luo , Nicholas R. Jennings , Nigel Shadbolt , Ho-fung Leung , Jimmy Ho-man Lee, A fuzzy constraint based model for bilateral, multi-issue negotiations in semi-competitive environments, Artificial Intelligence, v.148 n.1-2, p.53-102, August 2003 [doi>10.1016/S0004-3702(03)00041-9]
• 7: Leen-Kiat Soh , Xin Li, Adaptive, Confidence-Based Multiagent Negotiation Strategy, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1048-1055, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.43]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.1 Office Automation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms

Keywords:
constraint satisfaction, multi-issue negotiation, nonlinear utility