Negotiation as Creative Social Interaction Using Concept Hierarchies Frederick E. Petry1 and Ronald R.Yager2 1 Naval Research Laboratory, Stennis Space Center, MS 39529 [email protected] 2 Machine Intelligence Institute, Iona College, New Rochelle, NY 10801 [email protected] Abstract. Negotiation is a process that ranges from international issues to common society interactions. We present approaches to facilitate the process by exploring alternative spaces for this process. We base the approach on explor- ing alternative terminology that can resolve conflicts in the negotiation solution. Concept hierarchies can provide higher level concepts that can be used to obtain agreement between parties in the negotiation. Keywords: Negotiation, Concept Hierarchy, Generalization, Partitions, Consensus. 1 Introduction In this paper we propose an approach to the negotiation process which views this inexact process as a co-operative societal interaction among concerned parties. Nego- tiation can be defined as a process in which explicit proposals are put forward for the purpose of reaching agreement on an exchange or on the realization of common inter- est when conflicting interests are present [1]. Specifically we focus on ways to over- come barriers in negotiations due to differences in the semantics of language and concepts used by the negotiating parties. Since this is a complex issue we can view solutions as representing creative aspects of problem resolution. A specific mechanism we utilize to assist in this resolution is the use of concept hi- erarchies to generalize specific terminology that occurred during the negotiations. We will assume that for each party there is a space of concept hierarchies that cap- tures the semantics of terms under discussion in one or more relevant conceptual contexts. Thus when differences arise, some searching of the space of these concept hierarchies could discover common generalizations for the terms in dispute. Such generalizations can then be used to cast the discussions into a broader context that is more acceptable or amenable to both parties avoiding the otherwise contentious im- plications of the original terminology. 2 Background In this section we provide an overview of the generalization approach that can be used in exploration of the space of alternative terminology for the negotiation process. Next creativity as related to generalization and the exploration of alternatives is described. E. Hüllermeier, R. Kruse, and F. Hoffmann (Eds.): IPMU 2010, LNAI 6178, pp. 281–289, 2010. © Springer-Verlag Berlin Heidelberg 2010 Report Documentation Page Form Approved OMB No. 0704-0188 Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number. 1. REPORT DATE 3. DATES COVERED 2010 2. REPORT TYPE 00-00-2010 to 00-00-2010 4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER Negotiation as Creative Social Interaction Using Concept Hierarchies 5b. GRANT NUMBER 5c. PROGRAM ELEMENT NUMBER 6. AUTHOR(S) 5d. PROJECT NUMBER 5e. TASK NUMBER 5f. WORK UNIT NUMBER 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION Naval Research Laboratory,Stennis Space Center,MS,39529 REPORT NUMBER 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S) 11. SPONSOR/MONITOR’S REPORT NUMBER(S) 12. DISTRIBUTION/AVAILABILITY STATEMENT Approved for public release; distribution unlimited 13. SUPPLEMENTARY NOTES 14. ABSTRACT Negotiation is a process that ranges from international issues to common society interactions. We present approaches to facilitate the process by exploring alternative spaces for this process. We base the approach on exploring alternative terminology that can resolve conflicts in the negotiation solution. Concept hierarchies can provide higher level concepts that can be used to obtain agreement between parties in the negotiation. 15. SUBJECT TERMS 16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF 18. NUMBER 19a. NAME OF ABSTRACT OF PAGES RESPONSIBLE PERSON a. REPORT b. ABSTRACT c. THIS PAGE Same as 9 unclassified unclassified unclassified Report (SAR) Standard Form 298 (Rev. 8-98) Prescribed by ANSI Std Z39-18 282 F.E. Petry and R.R.Yager 2.1 Generalization Generalization is a broad concept that has been used in several contexts. One is the idea of data summarization, a process of grouping of data, enabling transformation of similar item sets, stored originally in a database at the low (primitive) level, into more abstract conceptual representations. Summarization of data is typically performed with utilization of concept hierarchies [2,3], which in ordinary databases are consid- ered to be a part of background knowledge In fuzzy set theory an important consid- eration is the treatment of data from a linguistic viewpoint. From this an approach has been developed that uses linguistically quantified propositions to summarize the content of a database, by providing a general characterization of the analyzed data [4- 7]. There have also been several approaches to the use of fuzzy hierarchies for data generalization [8-10]. Fuzzy gradual rules for data summarization have also been considered [11]. In a previous research effort [12] we developed an approach to data summarization that involves aspects of generalization and compression. The use of concept hierarchies, ontologies, to provide categories to be utilized in this process has been well established [13]. Now consider an example of data generalization letting D= {Oakland, San Jose, …., Sacramento} be a set of cities. However for a particular application, this data may be at too low a level, i.e. too specific. Figure 1 illustrates part of a concept hierarchy H for an attribute Location, describ- 1 ing US cities based on the geographical location. This concept hierarchy represents some of the domain background knowledge we have a priori. By ascending the hierarchy, for the attribute Location in the set D, the values San_Francisco, Santa_Cruz, Oakland, and San_Jose are generalized to the higher level category (also called the hypernym) Bay_Area, while the value (or hyponym) Sacramento is generalized to Sacramento_Metropolitan_Area. Thus R = G (D, H ) = 1 1 {Bay_Area, Sacramento_Metropolitan_Area. }. As we have discussed depending on a semantic context there may be other hierar- chy for the data being generalized. These may represent another application for the data or another context that is desired to be related to the original one. For the domain of cities we have discussed, another context might be the classification of the city based on population compared to the geographical context of Figure 1. This is illus- trated by H below in Figure 2. 2 California Bay Area Sacramento Metropolitan Area San Francisco Santa Cruz Oakland San Jose Sacramento Fig. 1. Example Concept Hierarchy for Cities in California Negotiation as Creative Social Interaction Using Concept Hierarchies 283 Population Large City Small City San Francisco Sacrament Oakland San Jose Santa Cruz Fig. 2. Concept Hierarchy Based on Population Size 2.2 Creativity Generalization construed broadly is a central facet of intelligent behavior, an induc- tive process going from the specific to the general. Here we focus on a data generali- zation process G for which relevant concept hierarchies are used to reduce the specific set of terms T into a small set of general concepts by an induction process. There have been a number of approaches to evaluating machine creativity and we discuss here some aspects relevant to generalization [14, 15]. Usually it is desired to use domain independent criteria to be as broadly applicable as possible. A creative act can be thought of in two stages – generation and evaluation. The basis for the evalua- tion of creativity can be viewed as an assessment of the output of a generation process after factoring out the input to the process. The input to the process can be considered as the implicit and explicit knowledge termed the inspiring set I by Ritchie [16] If we denote by R the results of the genera- tion, then the items to be considered as creative must lie in R/I, i.e. R-I. For the gener- alization process G we are considering that I = T ∪ H, where T is some set of i terms and H ∈ {H , H , …H } is one hierarchy of the set of hierarchies that may be i 1 2 n used for generalization. R = G ( I ) therefore is the result of the generalization process i on T using H. i Often it may become difficult to exactly specify the input I so strong and weak ver- sions of I have been introduced [15]. I contains those values specifically known to S the generalization process G, so a creative item must be completely new. Often the influence of other information on the process is difficult to quantify so I is intro- W duced, containing items that are known to have influenced the generalization. Since this information may be difficult to identify exactly, it may be desirable to consider I W as a fuzzy set. 3 Negotiation The process of negotiation is a pervasive activity in human society ranging from ne- gotiations between nations to individual negotiations in everyday life. The importance of negotiation is reflected by article 33, paragraph 1 of the United Nations charter which states that negotiation should be the first method to be used for peaceful set- tlement of international disputes [17]. 284 F.E. Petry and R.R.Yager In order for a negotiation to be successful, there must be common ground between parties for the process to bridge their respective positions. This is an issue our ap- proach addresses by investigating techniques to explore the space of concepts and terms used in negotiations by the involved parties. 3.1 Formalization of Negotiation We can provide a general description of the negotiation process with respect to how generalization can be used. Assume the negotiation involves N issues {I ,…,I } and 1 N these issues encompass a domain X of the terminology involved relative to the issues under consideration. Also let there be two hierarchies over X: H and H for sides 1 1 2 and 2 respectively in the negotiation. Each specific issue I involves some set of terms k T ⊆ X. So the problem can be described as that in order to negotiate an issue both k sides must be in agreement A on a sufficient number of terms. Let an agreement A be a simple one – assume each side has partitioned the termi- nology space X into two sets – terms with a positive import P and terms with a nega- tive import N. Then for issue I and the term set T , side 1 has T = P1 ∪ N1 . k k k k k Similarly for side 2, T = P2 ∪ N2 . Obviously if there is not enough overlap in k k k positive / negative terms for both sides negotiations will not succeed. The negotiation process must obtain sufficient agreement to succeed. Let us as- sume in this case a simple agreement A is obtained for the positive terms, A(P1 , P2 ) k k and for the negative A(N1 , N2 ). The objective is that the positive terms agreed k k upon should mostly cover the term set T under negotiation and the negative terms k agreed upon should mostly be avoided in the negotiation issue I . This means A(N1 , k k N2 ) ∩ T should be small. In order to achieve these agreements the sets of terms in k k dispute can be generalized by the two sides’ hierarchies H and H . Then it might be 1 2 possible that there are more general concepts that the two sides can accept as agree- able. We will illustrate in the next section approaches to find consensus among the possible partitions of term sets induced by the hierarchies. Clearly much of the inexact negation process involves subjective and soft criteria mentioned above such as “sufficient” agreement or “most” coverage. The representa- tion of such linguistic terms used during the negotiation can be assisted by the concept of linguistic quantifiers. Zadeh [18] noted that human dialogue makes con- siderable use of terms such as most, about 50%, some, all which he referred to as linguistic quantifiers. These terms are used to provide a linguistic explanation of some proportion and can be represented by fuzzy subsets over the unit interval such that the membership measures the satisfaction to the concept. In figure 3 we illustrate a typical graphical representation of the concept “Most”. Most 1 0 1 Fig. 3. Example for criterion. “Most” Negotiation as Creative Social Interaction Using Concept Hierarchies 285 A specific example of this sort of function is illustrated by the function F1 below: 0 x < a { F1(x, a, b) = (x-a) / (b-a) a < x < b 1 x > b where the values of a and b might be 0.75 and 0.85 respectively. Often the negotiation process involves negotiators who are agents representing the actual parties. If parties are unable to resolve differences by negotiation, a third party may step in to lead the parties to a solution by compromise. This is termed mediation. A mediator may even play an active role in this process and be flexible or innovative enough to obtain some consensus. Such an individual should have psychological understanding to appreciate the way in which the two parties are visualizing the issues between them. For example labor union representatives must produce a contract that the union members will ratify; lawyers, in a divorce case, must satisfy both wife and husband in the settlement. Often this will concern the varying interpretations of the language in the contract and so a final stage is the actual acceptance by the concerned parties. So as part of the overall process, the negotiation agents may have to explore phrasing that can satisfy the involved parties [19]. Assume there are two negotiators N1 and N2 and that they agree to take an action A1. Next they must explain this to their constituents or audience. Here there are a number of language semantics issues that must be considered. Let the action A1 involve some set of terms in a subset X’ of the space X. Then each audience has their own decomposition of X’ in the line of positive, negative and indifferent. D1 – X’ = P1∪ N1 ∪ I1; and their own reduction rules D2 – X’ = P2∪ N2 ∪ I2; and their own reduction rules Can the negotiators explore this space of possibilities to obtain an agreement be- tween D1 and D2? For example consider that there are 3 definite subsets of X, S1, S2 and S3. These are sets that generalize to some specific concept(s) in a given hierar- chy H. The remaining elements of X, S0 = X – S1 ∪ S2 ∪ S3. This is a set of undif- ferentiated elements that the party has no preference for generalization – so they might consider that the domain has positive and negative terms for them but the re- maining ones – S0 – are undifferentiated and the person has no preferences relative to them. Note this means that S0 doesn’t have specific constraints in the context. Assume we have two elements of S0 – a and b. These could be generalized to mul- tiple concepts – C and C’ – could be included in the generalization to say S2, could generalize independently to different concepts, etc, etc. This leads us to consider the issues of partially generalizing hierarchies and a space of concept hierarchies. – a partially partitioned space. So we consider the process of trying to reach agreements to do negotiations as a search thru this space – an exploration of such a space. This fits into the aspect of creativity – exploration. So we can see that inherently the proc- ess of negotiation can be viewed as a creative process. 3.2 Consensus and Partitions One approach to searching a space of hierarchies can be based on the how different the original data generalized from different hierarchies appears to be. We consider the idea of a consensus of generalized data [20, 21] in terms of the concept of congruence. 286 F.E. Petry and R.R.Yager One approach is to introduce a measure of similarity, congruence, between two partitions using the underlying equivalence relations. Here we now consider formu- lating a congruence measure from the perspective of the partitions themselves. Assume we have two partitions of the set D, P1 = A1, ..., Aq P2 = B1, ..., Bp q p where D = ∪ Aj and Ai ∩ Aj = ∅ for i ≠ j and D = ∪ Bj and Bi ∩ Bj = ∅ for i ≠ j. j = 1 j = 1 Without loss of generality we shall assume q = p. If q > p we can augment the par- tition P by adding q - p subsets, B = B = ...= B = ∅. Thus in the following 2 P+1 P+2 q we assume the two partitions have the same number of classes, q. We now introduce an operation called a pairing of P and P , denoted g(P , P ), 1 2 1 2 which associates with each subset A of P a unique partner B from P . Formally if i 1 j 2 Q = {1, 2, ..., q} then a pairing is a mapping g: Q → Q that is bijective, one to one and onto. Essentially g is a permutation of Q. We then have that a pairing g(P , P ) is a 1 2 collection of q pairs, (A, B ). j g(j) We shall now associate with each pairing a score, Score(g(P , P )), defined as fol- 1 2 lows. Denoting Cg.j = Aj ∩ Bg(j) for j= 1 to q we obtain q ∑ Score(g(P , P )) = ( Card (C ) )/ Card (D) 1 2 g.j j=1 Example: Now we consider an example of a labor negotiation for a faculty union at a university for which the issues are D = [Medical, Retirement, Raises, Tenure, Intellec- tual Property}. Based on negotiating positions of the two sides possible partitions might be: P consisting of: A = [Medical, Retirement, Tenure, Raises}, A = { Intel- 1 1 2 lectual Property }; and a partition P is B = [Medical, Retirement, Intellectual Prop- 2 1 erty, Raises }, and B = {Tenure}. In this case there are two pairings. 2 One pairing is g(j) = j in which case we get the pairs (A , B ), (A , B ). From this 1 1 2 2 Cg.1 = A1 ∩ B1 = { Medical, Retirement, Holidays } C = A ∩ B = ∅ g.2 2 2 In this case Score(g(P , P )) = 3/5. 1 2 The other pairing is g(1) = 2, g(2) = 1 and here our pairs are (A , B ), (A , B ). 1 2 2 1 and Cg.1 = A1 ∩ B2 = {Tenure} C = A ∩ B = { Intellectual Property } g.2 2 1 In this case Score(g(P , P )) = 2/5 1 2 We now shall use this to obtain a measure of congruence, Cong (P , P ). Let G 2 1 2 be the set of all pairings, g ∈ G. We define Cong (P , P ) = Max Score(g(P , P )) 2 1 2 1 2 g∈G Negotiation as Creative Social Interaction Using Concept Hierarchies 287 Thus this measure of congruence is the score of the largest pairing. We see that for q ∑ any pairing g, 0 ≤ Card (C ) ≤ Card(D). From this it follows that 0 ≤ g.j j=1 Cong2(P1, P2) ≤ 1. More precisely since for any two partitions we can always find a q ∑ pairing g in which Card (C ) ≥ 1 we see that g.j j=1 1 ≤ Cong2(P1, P2) ≤ 1 Card(D) So this measure allows us to compare partitions produced by generalization using different hierarchies. Now we can discuss how to apply consensus measures to issues concerning nego- tiation. Consider the terms that might be part of the dispute in the negotiation. For example one of disagreement on terms is seen in the set D1 = P2 ∩ N1 By generalizing this set D1 of contentious terms we can, so to speak, cast these into a different phrasing as higher level concepts on which the parties may be able to achieve more agreement. Again recall that negotiation is an inexact process so the degree of agreement on these concepts need not be complete but by mediation the agreement can be phrased as “Mostly” agreed upon. Since it is more likely that agreement can be found on a smaller set of higher level concepts, the search of the space of hierarchies to find a better consensus is the overall objective. Another way of viewing the result of the generalization is that a higher level concept corresponds to (covers) a larger subset of the terms in dispute. Each of the sides in the negotiation may then be able to focus on different aspects or components of such a subset and which they may then find more satisfactory. Finally if there was not a satisfactory solution obtained, a creative approach could be to consider various combinations of partitions utilizing the sets of terms the parties are indifferent towards. This would mean that the set D1 could be extended prior to generalizations. Let S2 be the set of terms that the second party is indifferent to- wards. Note not all of these would be indifferent to the other side, indeed some might be viewed as positive, negative, or indifferent. Certainly the subset of S2 viewed negatively (S2 ∩ N1) would not be included in an extension. A variety of choices are to include some of the positive and / or indifferent terms of S2 in the extension de- pending on what negotiators or mediators think would be most beneficial to obtaining a satisfactory resolution. 4 Summary In this paper we described an approach to the negotiation process which views this inexact process as a co-operative social interaction. Negotiation is a process that ranges from international issues to common society interactions. We presented ap- proaches to facilitate the process by exploring alternative spaces for this process. We 288 F.E. Petry and R.R.Yager based the approach on exploring alternative terminology that can resolve conflicts in the negotiation solution. Concept hierarchies were shown to provide higher level concepts that can be used to obtain agreement between parties in the negotiation Acknowledgments. We would like to thank the Naval Research Laboratory’s Base Program, Program Element No. 0602435N for sponsoring this research. Ronald R. Yager's contribution has been supported in part by ARO MURI grant W911NF-09-1- 0392 under Dr. J. Lavery and ONR grant N000141010121. References [1] Ikle, F.: How Nations Negotiate. Evanston and London, New York (1964) [2] Han, J., Cai, Y., Cercone, N.: Knowledge discovery in databases: An attribute-oriented approach. In: Proceedings of 18th VLDB Conf., pp. 547–559 (1992) [3] Han, J.: Mining Knowledge at Multiple Concept Levels. In: Proc. 4th Int’l Conf. on In- formation and Knowledge Management, pp. 19–24. ACM Press, New York (1995) [4] Yager, R.: On linguistic summaries of data. In: Piatesky-Shapiro, G., Frawley (eds.) Knowledge Discovery in Databases, pp. 347–363. MIT Press, Boston (1999) [5] Kacprzyk, J.: Fuzzy logic for linguistic summarization of databases. In: Proc.8th Int’l Conf. on Fuzzy Systems, Seoul, Korea, pp. 813–818 (1999) [6] Dubois, D., Prade, H.: Fuzzy sets in data summaries - outline of a new approach. In: Proc. 8th Int’l Conf. on Information Processing and Management of Uncertainty in Knowledge- Based Systems, Madrid, pp. 1035–1040 (2000) [7] Feng, L., Dillon, T.: Using Fuzzy Linguistic Representations to Provide Explanatory Se- mantics for Data Warehouses. IEEE Transactions on Knowledge and Data Engineer- ing 15(1), 86–102 (2003) [8] Lee, D., Kim, M.: Database summarization using fuzzy ISA hierarchies. IEEE Transac- tions On Systems, Man, and Cybernetics - part B 27(1), 68–78 (1997) [9] Raschia, G., Mouaddib, N.: SAINTETIQ:a fuzzy set-based approach to database summa- rization. Fuzzy Sets and Systems 129, 37–162 (2002) [10] Angryk, R., Petry, F.: Data Mining Fuzzy Databases Using Attribute-Oriented Generali- zation. In: Proc.IEEE Int. Conf. Data Mining Workshop on Foundations and New Direc- tions in Data Mining, Melbourne, FL, pp. 8–15 (2003) [11] Cubero, J., Medina, J., Pons, O., Vila, M.: Data Summarization in Relational Databases Through Fuzzy Dependencies. Information Sciences 121(3-4), 233–270 (1999) [12] Petry, F., Zhao, L.: Data Mining by Attribute Generalization with Fuzzy Hierarchies in Fuzzy Databases. Fuzzy Sets and Systems 160 (#15), 2206–2223 (2009) [13] Han, J., Kamber, M.: Data Mining: Concepts and Techniques, 2nd edn. Morgan Kauf- mann, San Francisco (2006) [14] Boden, M.: The Creative Mind: Myths and Mechanisma. Weidenfield and Nicholson, London (1990) [15] Pease, A., Winterstein, D., Colton, S.: Evaluating Machine Creativiity. In: Proc. of ICCBR’01 – Workshop on Creative Systems, Vancouver, CA, pp. 56–61 (2001) [16] Ritchie, G.: Assessing Creativity. In: Proc. Of AISB ’01 Symp. on AI and Creativity in Arts and Science, pp. 3–11 (2001) [17] Northedge, F., Donelan, M.: International Disputes – the Political Aspects. St. Martin’s Press, New York (1971) Negotiation as Creative Social Interaction Using Concept Hierarchies 289 [18] Zadeh, L.: Fuzzy logic = computing with words. IEEE Transactions on Fuzzy Systems 4, 103–111 (1996) [19] Jackson, M.: Industrial Relations, 3rd edn. Croom Helm Ltd., Beckenham (1985) [20] Yager, R.: Some Measures Relating Partitions Useful for Computatuional Intelligence. Int. Jour. Computational Intelligence Systems 1(#1), 1–18 (2008) [21] Petry, F., Yager, R.: A Framework for Use of Imprecise Categorization in Developing In- telligent Systems. IEEE Transactions On Fuzzy Systems 18(#2), 348–361 (2010)