• Articles • Previous Articles     Next Articles

Fuzzy Constraint-Based Agent Negotiation

Menq-Wen Lin1, K. Robert Lai2, and Ting-Jung Yu2   

  1. 1Department of Information Management, Ching Yun University, Chung-Li
    2Department of Computer Science and Engineering, Yuan Ze University, Chung-Li
  • Received:2003-10-20 Revised:2004-09-23 Online:2005-05-10 Published:2005-05-10

Conflicts between two or more parties arise forvarious reasons and perspectives. Thus, resolution of conflicts frequentlyrelies on some form of negotiation. This paper presents a generalproblem-solving framework for modeling multi-issue multilateral negotiationusing fuzzy constraints. Agent negotiation isformulated as a distributed fuzzy constraint satisfaction problem (DFCSP).Fuzzy constrains are thus used to naturally represent each agent's desiresinvolving imprecision and human conceptualization, particularly when lexicalimprecision and subjective matters are concerned. On the other hand, based onfuzzy constraint-based problem-solving, our approach enables an agent not onlyto systematically relax fuzzy constraints to generate a proposal, but also toemploy fuzzy similarity to select the alternative that is subject to itsacceptability by the opponents. This task of problem-solving is to reach anagreement that benefits all agents with a high satisfaction degree of fuzzyconstraints, and move towards the deal more quickly since their search focusesonly on the feasible solution space. An application to multilateralnegotiation of a travel planning is provided to demonstrate the usefulness andeffectiveness of our framework.

Key words: Methodology of software engineering; abstract model theory; many-valued logic;

[1] Bradshaw Jeffrey M. Software Agents. AAAI/The MIT Press, 1997.

[2] Huhns Michnel N, Munindar P Singh (eds.).Readings in Agents. San Francisco, California: Morgan KaufmannPublishers, Inc., 1998.

[3] Pruitt D G. Negotiation Behavior. Academic Press, New York, 1981.

[4] Kersten Gregory E, Gordon Lo. Negotiation support systems andsoftware agents in e-business negotiations. In The FirstInternational Conference on Electronic Business, Hong Kong,December, 2001, pp.19--21.

[5] Rosenschein J S, Zlotkin G.Rules of Encounter: Designing Conventions for Automated Negotiation AmongComputers. Cambridge, Massachusetts: MIT Press, 1994.

[6] Ren Z, Anumba C J, Ugwu O O. Negotiation in a multi-agentsystem for construction claims negotiation. Applied ArtificialIntelligence, 2002, 16: 359--394.

[7] Oliver Jim R. On artificial agents fornegotiation in electronic commerce. In Proc. The 29th AnnualHawaii International Conference on System Sciences, 1996, pp.337--346.

[8] Eaton P S, Freuder E C, Wallace R J. Constraints and agents:Confronting Ignorance. AI Magazine, 1998, 19(2): 51--65.

[9] Zeng D, Sycara K. Bayesian learning in negotiation. Internat. J. Human-Computer Stud., 1998, 48(1): 125--141.

[10] Choi Samuel P M, Liu Jiming, Chan Sheung-Ping. A geneticagent-based negotiation system. Computer Networks, 2001, 37:195--204.

[11] Sycara K. Multi-agent compromise vianegotiation. In -Distributed Artificial Intelligence, Vol. 2.Gasser L, Huhns M (eds.), Morgan Kaufmann, San Mateo, CA, 1989, pp.119--139.

[12] Sathi A, Fox M. Constraint-directed negotiation of resourcereallocation. In Distributed Artificial Intelligence,Vol. 2. Gasser L, Huhns M (eds.), Morgan Kaufmann, San Mateo, CA, 1989,pp.163--195.

[13] Matos Noyda, Carles Sierra. Evolutionary computing andnegotiating agents. Agent Mediated ElectronicCommerce, AMET-98, In Lecture Notes in Artificial Intelligent 1571, 1998, pp.126--150.

[14] Barbuceanu M, Lo W-K. A multi-attribute utility theoreticnegotiation architecture for electronic commerce. In Proc.the Fourth International Conference on Autonomous Agents, 2000,pp.239--246.

[15] Luo Xudong, Nicholas R Jennings, Nigel Shadbolt et al. A fuzzy constraint based model forbilateral multi-issue negotiations in semi-competitive environments. Artificial Intelligence, 2003, 148: 53--102.

[16] Kowalczyk R, Bui V. FeNAs: A fuzzy e-negotiation agentssystem. In Proc. The IEEE/IAFE/INFORMS 2000 Conference onComputational Intelligence $($CIFEr 2000$)$, New York, 2000, pp.26--29.

[17] Faratin P, Sierra C, Jennings N R.Using similarity criteria to make trade-offs in automated negotiation. Artificial Intelligence, 2002, 142(2): 205--237.

[18] Zadeh L A. Fuzzy sets as a basis for atheory of possibility. Fuzzy Sets and Systems, 1978, 1: 3--28.

[19] Lai R. Fuzzy constraint processing

[Dissertation].NCSU, Raleigh, N. C., 1992.

[20] Dubois D, Fragier H, Prade H. Propagation and satisfaction offlexible constraints. In -Fuzzy Sets, Neural Networks and SoftComputing, Van Nostrand Reinhold
, Yager R, Zadeh L (eds.), New York,1994, pp.166--187.

[21] Bowen J, Lai R, Bahler D. Lexical imprecision in fuzzyconstraint networks. In Proc. AAAI-92, San Jose, CA, 1992,pp.616--621.

[22]Saaty T L. The Analytic Hierarchy Process. McGraw-Hill, NewYork, 1980.

[23] Yager R R, Filev D P. Essential of Fuzzy Modeling andControl. John Wiley & Sons, New York, 1994.

[24] Liu X. Entropy, distance measure and similarity measure offuzzy sets and their relations. Fuzzy Sets and Systems, 1992, 52:305--318.

[25] Finin T, McKay D, McEntire R. KQML---A language and protocolfor knowledge and information exchange. Technical Report CS-94-02,Computer Science Department, University of Maryland, UMBC, Baltimore MD21228, 1994.

[26] Searle J. Speech Acts. Cambridge University Press, 1969.

[27] Bellman R E, Zadeh L A. Decision making in a fuzzyenvironment. Management Science, 1970, 17: 141--164.
[1] Ying Mingsheng;. Putting Consistent Theories Together in Institutions [J]. , 1995, 10(3): 260-266.
[2] Ying Mingsheng;. Institutions of Variable Truth Values:An Approach in the Ordered Style [J]. , 1995, 10(3): 267-273.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved