Logic as a power tool to model negotiation mechanisms in the Semantic Web Era

Abstract

The research problem The key theme of our research is the modeling of multi-attribute negotiation scenarios with the aid of logic languages, going from very simple (and not so expressive) languages as propositional logic up to more expressive logics, such as Description Logics (DLs). The approach to multi-attribute negotiation we are investigating on exploits logic languages at least in two ways: (1) to model, through an ontology, relations between attributes to be negotiated and (2) to characterize buyer and seller preferences. Some of the advantages of such an approach are intuitive: the possibility to model disjontness, implication, utilities on bundle of issues are all useful in settings where negotiation is not limited to undifferentiated goods but is based on complex descriptions that require adequate negotiation mechanisms to produce -in an automated way- fair deals. The research problem is both challenging and very timely for the Semantic Web initiative, because of the undeniable importance of e-commerce and negotiation over the Web and because Description Logics are at the core of Semantic Web languages. Indeed, many recent research efforts have been focused on automated negotiation in various contexts, including e-marketplaces, resource allocation settings, online auctions, supply chain management and, generally speaking, e-business processes. We think that, as it will be outlined in the next sections, DLs can be the pivotal tool in modeling negotiation mechanisms in the tumultuous Semantic Web arena.

-

are fundamental issues to model an e-marketplace. We borrow from [ 11 ] the definition of agreement as a model for a set of formulas from both agents. However, in [ 11 ] only multiple-rounds protocols are studied, and the approach leaves the burden to reach an agreement to the agents themselves, although they can follow a protocol. The approach does not take preferences into account, so that it is not possible to guarantee that the reached agreement is Pareto-efficient. Our approach, instead, aims at giving an automated support to negotiating agents to reach Pareto agreements. With reference to the work presented in [ 12 ], adopting a propositional logic setting, common knowledge is considered as just more entrenched preferences, that could be even dropped in some deals. We adopt a knowledge base, or ontology T , of formulas which are common knowledge for both agents, whose constraints must always be enforced in the negotiation outcomes. Moreover we use additive utilitites over formulas: this allows an agent to make compensations between its requests and its concessions, while in [ 12 ] the concession of a more entrenched formula can never be compensated by less entrenched ones, no matter how many they are. Finally we devised a protocol which the agents should adhere to while negotiating; in contrast in [ 12 ] a game-theoretic approach is taken, presenting no protocol at all, since communication between agents is not considered. To the best of our knowledge our approach is the first one using DLs to design a logic-based negotiation mechanism, ensuring a greater expressiveness w.r.t. propositional logic. Moreover, w.r.t. to non-logic-based approaches, the use of an ontology T allows exploiting inference services that are used in the actual negotiation mechanisms. 3

Expected contributions

Bilateral negotiation is a challenging problem, which finds applications in a number of different scenarios, each one with its own peculiarities and issues. Among others, the approach can suitably model negotiation in e-marketplaces. Clearly, here we do not deal with simple marketplaces of commodities and undifferentiated goods, where only price, time or quantity have to be taken into account. We refer to e-marketplaces dealing with complex products (e.g., computers, automobiles, houses, and so on) where both offers/requests are referring to goods/services that cannot be simply described in a machine understandable way without the help of some Knowledge Representation (KR) language. When a potential buyer browses e.g., an automobile e-marketplace, she looks for a car fulfilling her needs and/or wishes, so not only the price is important, but also warranty or delivery time, as well as look, model, comfort and so on. In such domains it is harder to model not only the negotiation process, but also the request/offer descriptions, as well as finding the best suitable agreement. Furthermore preferences can refer to (1) bundle of issues, e.g., Sports car with navigator pack where both the meaning of sport car and navigator pack are in the ontology; or preferences can be (2)conditional ones – when issues are inter-dependent i.e., the selection of one issue depends on the selection made for other issues – e.g., I would like a car with leather seats if its color is black. In such a cases some kind of logical theory (ontology), able to let users express their needs/offers, could surely help. Also, when descriptions refer to complex needs, we should take into account preferences, distinguishing them from hard mandatory constraints (strict requirements), e.g., I would like a black station wagon, preferably with GPS system1. The possibility to handle some of the above mentioned issues in some electronic facility may help not only in the discovery/matchmaking stage of a transaction process, thus selecting most promising counterparts to initiate a negotiation, but also in the actual negotiation stage. Obviously, the one described above is not the only feasible scenario to apply the approach proposed, since the negotiation framework we propose is very general and can be applied to many other negotiation scenarios where resource descriptions have to be modeled through KR languages, as e.g., in (web)service scenarios. 4

Research methodology

In the early stage of our research we started modeling preferences and goods/services descriptions using propositional logic. In [ 6 ] we presented the theoretical framework, which makes use of a facilitator to compute, through a one-shot negotiation protocol, some particular Pareto-efficient outcomes – the ones which maximize the social welfare and the product of utilities.

Differently from well-known approaches that describe issues as uncorrelated; we represented buyer’s request, seller’s supply and their respective preferences as formulas endowed with a formal semantics. By modeling preferences as formulas it is hence possible to assign a utility value also to a bundle of issues, which is obviously more realistic than the trivial sum of utilities assigned to single elements in the bundle itself.

Afterward the approach has been extended and generalized and also complexity issues were discussed [ 5 ]: we proved the computational adequacy of our method by studying the complexity of the problem of finding Pareto-efficient solutions in a propositional logic setting, in particular we proved that both problems – the one maximizing the product and the one maximizing the sum of utilities – are NPO-complete problems. A further improvement has been presented in [ 9 ], where we extended the framework, so that it is possible to handle, in a homogeneous setting, both numerical features and non-numerical ones. The framework makes possible to formally represent typical situations in real e-marketplaces such as “if I spend more than 20000 e for a sedan then I want a navigator pack included” where both numerical (price) and nonnumerical (sedan, navigator pack) issues coexist. To this aim we introduce P(N ), a propositional logic extended with concrete domains, which allows to: model relations among issues (both numerical and not numerical ones) via logical entailment: e.g., the seller can state that if you want a car with a GPS system you have to wait at least one month: (GPS system ) deliverytime ¸ 31); as well as preferences can involve only numerical ones: e.g., the buyer can state that she would be willing to spend more than 25000 e for a sedan only if there is more than a two years warranty [(price > 25000) ) (year warranty > 2)].

In the approach we proposed, buyer and seller reveal their preferences to a mediator, which compute Pareto-efficient agreements solving a multi objective optimization problem (MOP). Actually, we solve a multi objective optimization problem as we try to make buyer and seller equally satisfied, maximizing different utility functions, both of the buyer and the seller. 1 Strict requirements, in contrast with preferences, are constraints the buyer and the seller want to be necessarily satisfied to accept the final agreement, while preferences are issues they may accept to negotiate on.

In addition to the set of functions to maximize, in a MOP there are also a set of constraints that have to be satisfied. In our setting, we have three different sets of constraints, coming from (1) the ontology, (2)the strict requirements (see Section 3) and (3) the disagreement thresholds 2. The returned solution to the MOP is the agreement proposed to the buyer and the seller. Notice that a solution to a MOP is always Pareto optimal.

The negotiation mechanisms described so far model a bargaining scenario where agents—acting on behalf of buyer and seller—reveal their preferences to a mediator, which has the burden of collecting information and proposes a fair agreements to both participants. The intervention of a mediator is due to the fact that usually bargainers may not want to disclose their preferences or utility function to the other party, but they can be ready to reveal these information to a trusted automated mediator helping negotiating parties to achieve efficient and equitable outcomes. Therefore we proposed a one-shot protocol with the intervention of a mediator suggesting to each participant the solution which is Pareto-efficient. For what concerns strategy, the players can choose to accept or refuse the solution proposed by the mediator; they refuse if they think possible to reach a better agreement looking for another partner, or another shot, or for a different e-marketplace.

However in some cases it is not possible to rely on a mediator, so a decentralized approach has to be adopted —instead of a centralized one— where agents negotiate without the help of a mediator. Obviously, in such cases it can be difficult to design negotiation mechanism leading to Pareto-efficient agreements [ 4 ]. We are currently investigating some alternative negotiation mechanisms without the presence of a mediator.

The need for more expressive languages to adequately model negotiation frameworks led us to [ 7, 8 ] move from propositional logic to DLs.

We are, to the best of our knowledge, the first ones proposing a DLs-based approach to model multi-attribute bilateral negotiation. Being, in general, much more expressive than e.g., propositional logic, DLs allow to model complex preferences on bundles of interrelated issues and to exploit inference services —such as satisfiability and subsumption— available in optimized reasoners. Satisfiability is useful to catch inconsistency between agent’s preferences w.r.t. the ontology T , i.e., inconsistent goals cannot be in the same agreement, (e.g., agents cannot agree on A and B at the same time if in T A is defined as disjoint from B). Through subsumption it is possible to discover if an agent’s goal is satisfied by a goal of the opponent’s one even if it does not immediately appears at the syntactic level.

In [ 7 ] we propose a logic-based alternating-offers protocol, inspired by Rubinstein’s one [ 10 ]. Our protocol merges both Description Logics formalism and reasoning services, and utility theory, to find the most suitable agreements. We have also implemented a prototype to carry out some preliminary experiments with a buyer negotiating with multiple sellers at the same time, as would be in a real e-marketplace.

In [ 8 ] we propose a novel negotiation mechanism designed to model scenario with fully incomplete information. Actually, while in [ 7 ] we consider a scenario with partial incomplete information—the agents know the goals (preferences) of the other agents ignoring the utility value assigned to them—in [ 8 ] we consider agents keeping as private 2 Thresholds are the minimum utility that each agent requires to pursue a deal. Minimum utilities may incorporate an agents attitude toward concluding the transaction, but also overhead costs involved in the transaction itself, e.g., fixed taxes. information both their goals and their worths [ 3 ]. The protocol we propose in [ 8 ] is able to deal with such incomplete information without forcing agents to reveal either their goals or utility functions, so it suits all scenarios where agents are not willing to reveal private information or when it is hard to design a truthful revelation mechanism [ 4 ]. We prove that the proposed protocol converges if the DL adopted to model buyer’s and seller’s goals is constrained to satisfy the so-called finite implicants property. Such a protocol allows agent to use different strategies: we introduce and discuss two possible strategies, highlighting their properties. We are planning the implementation of a prototype and test-beds to numerically evaluate best strategies to adopt w.r.t. the negotiation mechanism. 5

Conclusion and Future Work

We have presented new approaches to automate logic-based multi-attribute negotiation. The research started from the investigation of propositional logic as a language to model agent proposals. Propositional logic, equipped with an ontology, allows modeling bundle of preferences and implication between them. Differently from well-known approaches that describe issues as uncorrelated; we represent buyer’s request, seller’s supply and their respective preferences as formulas endowed with a formal semantics. By modeling preferences as logical formulas it is hence possible to assign a utility value also to a bundle of issues, which is obviously more realistic than the trivial sum of utilities assigned to single elements in the bundle itself. In the second year of my PhD we moved to DLs to express agent’s preferences. DLs in fact allow a greater expressiveness, remaining decidable. We have studied different negotiation mechanisms with the presence of a mediator [ 6, 5, 9 ] and without a mediator, with partial incomplete information [ 7 ] or fully incomplete information [ 8 ]. For each mechanism we illustrated the protocol followed by the agents and one or more strategies agents can adopt depending on the designed protocol. We have also implemented a prototype to carry out some initial experiments. In future work we are planning to validate our approach with agentbased simulations, and for the DLs-based frameworks [ 7, 8 ] we are also setting up an analysis of the game theoretic properties, as related properties of the negotiation protocols ( e.g., Pareto-efficiency), equilibrium strategies or properties of the agents (e.g., individual rationality).

Acknowledgments

References

1. S. Bouveret , M. Lemaitre , H. Fargier , and J. Lang . Allocation of indivisible goods: a general model and some complexity results . In Proc. of AAMAS '05 , pages 1309 - 1310 , 2005 .

2. Y. Chevaleyre , U. Endriss , and J. Lang . Expressive power of weighted propositional formulas for cardinal preference modeling . In Proc. of KR 2006 , pages 145 - 152 , 2006 .

3. J.S. Rosenschein and G. Zlotkin . Rules of Encounter. MIT Press,, 1994 .

4. Sarit Kraus . Strategic Negotiation in Multiagent Environments . The MIT Press, 2001 .

5. A. Ragone , T. Di Noia , E. Di Sciascio , and F.M. Donini . A logic-based framework to compute pareto agreements in one-shot bilateral negotiation . In Proc. of ECAI'06 , pages 230 - 234 , 2006 .

6. A. Ragone , T. Di Noia , E. Di Sciascio , and F.M. Donini . Propositional- logic approach to one-shot multi issue bilateral negotiation . ACM SIGecom Exchanges , 5 ( 5 ): 11 - 21 , 2006 .

7. Azzurra Ragone , Francesco Colasuonno, Tommaso Di Noia, Eugenio Di Sciascio, and Francesco M. Donini . Logic-based alternating-offers protocol for automated multi-issue bilateral negotiation in P2P e-marketplaces. Submitted for publication , 2007 .

8. Azzurra Ragone , Tommaso Di Noia, Eugenio Di Sciascio, and Francesco M. Donini . Description Logics for Multi-issue Bilateral Negotiation with Incomplete Information . Submitted for publication, 2007 .

9. Azzurra Ragone , Tommaso Di Noia, Eugenio Di Sciascio, and Francesco M. Donini . When price is not enough: Combining logical and numerical issues in bilateral negotiation . In proc. of International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2007 ). ACM Press, May 2007 . to appear.

10. A. Rubinstein . Perfect equilibrium in a bargaining model . Econometrica , 50 : 97 - 109 , 1982 .

11. M. Wooldridge and S. Parsons . Languages for negotiation . In Proc of ECAI '00 , pages 393 - 400 , 2000 .

12. Dongmo Zhang and Yan Zhang . A computational model of logic-based negotiation . In Proc. of the AAAI 06 , pages 728 - 733 , 2006 .