A Combination of Boolean Games with Description Logics for Automated Multi-Attribute Negotiation

Abstract

Multi-attribute negotiation has been extensively studied from a gametheoretic viewpoint. In negotiation settings, utility functions are used to express agent preferences. Normal and extensive form games, however, have the drawback of requiring an explicit representation of utility functions, listing the utility values for all combinations of strategies. Therefore, several logical preference languages have been proposed, to specify multi-attribute utility functions in a compact way. Among these approaches, there are also Boolean games. In this paper, we introduce Boolean description logic games, which are a combination of Boolean games with ontological background knowledge, formulated using expressive description logics. In this way, it is possible to enhance the expressiveness of preference representation, maintaining the advantages of the game-theoretic approach. We include and discuss several generalizations, showing their practical usefulness within a service negotiation scenario. Furthermore, we also provide complexity results.

-

During the recent decade, a huge amount of research activities has been centered around the problem of automated negotiation. This is especially due to the development of the World Wide Web, which has provided the means and the commercial necessity for the further development of computational negotiation and bargaining techniques [ 15 ].

Another area with an impressive amount of recent research activities is the Semantic Web [ 2,10 ], which aims at an extension of the current Web by standards and technologies that help machines to understand the information on the Web so that they can support richer discovery, data integration, navigation, and automation of tasks. The main ideas behind it are to add a machine-readable meaning to Web pages, to use ontologies for a precise definition of shared terms in the Web, to use knowledge representation technology for automated reasoning from the Web, and to apply cooperative agent technology for processing the information of the Web.

Only a marginal amount of research activities, however, focuses on the intersection of automated negotiation and the Semantic Web (see Section 6). This is surprising, since representation and reasoning technologies from the Semantic Web may be used to further enhance automated negotiation on the Web, e.g., by providing ontological background knowledge. Moreover, although one important ingredient of the Semantic Web is agent technology, the agents are still largely missing in Semantic Web research to date [ 13 ]. This paper is a first step in direction to filling this gap. Towards automated multi-attribute negotiation in the Semantic Web, we introduce Boolean description logic games. The main contributions of this paper are briefly summarized as follows: – We define n-agent Boolean description logic games, which are a combination of classical n-player Boolean games with description logics. They informally combine classical n-player Boolean games with ontological background knowledge; in addition, we also introduce strict agent requirements and overlapping agent control assignments. – We then generalize to n-agent Boolean description logic games where each agent has a set of weighted goals, which may be defined over free description logic concepts. – We analyze the complexity of important decision problems for n-agent Boolean description logic games. In particular, we show that n-agent Boolean description logic games relative to the DL-Lite family as underlying DLs have the same complexity as standard n-player Boolean games. – We provide examples from a service negotiation scenario, which illustrate the introduced concepts related to Boolean description logic games, and which give evidence of the practical usefulness of our approach.

Intuitively, Boolean description logic games can be seen as a one-step negotiation process. Clearly, the scenario presented here is also closely related to service matchmaking and resource retrieval, since the service provider and the service consumer can be both considered as agents having certain service specifications and service preferences, and the result of the negotiation process is then the service where the service specifications are matching optimally the service preferences.

The rest of this paper is organized as follows. In Section 2, we give some brief preliminaries. In Section 3, we then define Boolean description logic games. Section 4 introduces Boolean description logic games with weighted generalized goals. Section 5 provides complexity results. In Section 6, we discuss related work. Section 7 summarizes the main results and gives an outlook on future research. The proofs of all results in this paper are given in the extended paper. 2

Preliminaries

We assume the reader is familiar with the syntax and the semantics of Description Logics (DLs) [ 1 ], which we use as underlying ontology languages. Note that our approach to Boolean description logic games is not restricted to any specific DL; we only assume that the satisfiability of a knowledge base is decidable. Thus, the underlying DL may be a tractable DL such as the ones of the DL-Lite family [ 6 ] or a very expressive DL such as the ones behind OWL Lite and OWL DL [ 14 ]. As a running example, we refer to a service negotiation scenario, which is based on the following travel ontology. Example 2.1 (travel ontology). We refer to a DL knowledge base L encoding a travel ontology (adapted from http://protege.cim3.net/file/pub/ontologies/travel/) given by the axioms in Fig. 1. For example, there are some axioms encoding that bed and breakfast (BB) accommodations and hotels are different accommodations, and that a budget accommodation is an accommodation that has one or two stars as a rating.

We now briefly recall the definition of classical n-player Boolean games [ 3 ], which are a generalization of 2-player Boolean games from [ 12,11 ]. Given a set of propositional variables V = fp1; p2; : : : ; pkg, we denote by LV the set of all propositional formulas (denoted by Greek letters ; ; : : :) built inductively from V via the Boolean operators :, ^, and _. An n-player Boolean game G = (N; V; ; ) consists of 1. a set of n players N = f1; 2; : : : ; ng, n > 2, 2. a finite set of propositional variables V , 3. a control assignment : N ! 2V , which associates with every player i 2 N a set of variables (i) V , which she controls, such that f (i) j i 2 N g partitions V , and 4. a goal assignment : N ! LV , which associates with every player i 2 N a propositional formula (i) 2 LV , denoted the goal of i. 3

Boolean Description Logic Games

In this section, we present our approach to Boolean description logic games, which combine classical n-player Boolean games with ontologies. The main differences to classical n-player Boolean games are summarized as follows: – Rather than unrelated propositional variables, agents now control atomic DL concepts, which may (abbreviate complex DL concepts and) be related via a DL knowledge base. In fact, the assumption that the controlled variables are unrelated in classical n-player Boolean games is quite unrealistic; often the variables (attributes) are related through some background knowledge, e.g., the different types of accommodation or destinations (see Fig. 1). – Rather than having only preferences, agents may now also have strict goals, which have to be necessarily true in an admissible agreement. This reflects the fact that agents accept no agreement where some strict conditions are not true; such strict conditions are very common in many applications in practice, e.g., an agent may necessarily want an accommodation in a BB located in a rural area. – Rather than defining a partition, the control assignment may now be overlapping. It means that, because of the ontology through which concepts are related, agents cannot have an exclusive control on concepts anymore. Instead, they “share the power” on some concepts, which means that they do not longer control that. In fact, such overlapping control assignments are also more realistic. Moreover, it is not necessary that “each” concept has to be assigned to a single player, some concepts will be decided as consequence of the others or of axioms stated in the ontology.

We first give some preparative definitions as follows. Here, we use a finite set of atomic concepts A instead of a set of propositional variables V in n-player Boolean games. We denote by LA the set of all concepts (denoted by Greek letters ; ; : : :)

BedAndBreakfast v Accommodation;

Hotel v Accommodation;

BedAndBreakfast v :Hotel;

BudgetAccommodation Accommodation u 9hasRating.fOneStarRating; TwoStarRatingg;

UrbanArea v Destination;

City v UrbanArea;

Capital v City;

RuralArea v Destination;

NationalPark v RuralArea;

RuralArea v :UrbanArea;

BudgetHotelDestination 9hasAccommod

u 8hasAccommod.(BudgetAccommodation u Hotel);

AccommodationRating fOneStarRating;

TwoStarRating; ThreeStarRatingg;

Sightseeing v Activity;

Hiking v Sport;

Sport v Activity;

ThemePark v Activity;

FamilyDestination 9hasDestination

u 9hasAccommod u > 3 hasActivity;

RelaxDestination 9hasDestination.NationalPark

u 9hasActivity.Sightseeing; hasActivity isOfferedAt . built inductively from A via the Boolean operators :, u, and t. An interpretation I is a full conjunction of atomic concepts and negated atomic concepts from A. We say I satisfies a DL knowledge base L, denoted I j= L, iff L [ fI(o)g is satisfiable, where o is a new individual. We say I satisfies a concept over A under L, denoted I j=L , iff L j= I v . We say is satisfiable under L iff there exists an interpretation I such that I j=L . We are now ready to define n-agent Boolean description logic games. Definition 3.1 (n-agent Boolean description logic games). An n-agent Boolean description logic game (or n-agent Boolean dl-game) G = (L; N; A; ; ; ) consists of 1. a DL knowledge base L, 2. a finite set of n agents N = f1; 2; : : : ; ng, n > 2, 3. a finite set of atomic concepts A, 4. a control assignment : N ! 2A, which associates with every agent i 2 N a set of atomic concepts (i) A, which she controls, 5. a strict goal assignment : N ! LA, which associates with every agent i 2 N a concept (i) 2 LA that is satisfiable under L, denoted the strict goal of i, and 6. a goal assignment : N ! LA, which associates with every agent i 2 N a concept (i) 2 LA that is satisfiable under L, denoted the goal of i.

As for the difference between strict and general goals, the agents necessarily want their strict goals to be satisfied, but they only would like their general goals to be satisfied.

Example 3.1 (travel negotiation). A two-agent Boolean dl-game G = (L; N; A; ; ; ), where the traveler (agent 1) negotiates with the travel agency (agent 2) on the conditions of a vacation, is given as follows: 1. L is the travel ontology of Example 2.1, depicted in Fig. 1. 2. N = f1; 2g, where agent 1 (resp., 2) is the traveler (resp., travel agent). 3. A consists of the following atomic concepts (that are relevant to the negotiation): U R BHD BA H BB NP C

9hasDestination u 8hasDestination.UrbanArea;

9hasDestination u 8hasDestination.RuralArea;

BudgetHotelDestination;

9hasAccommod u 8hasAccommod.BudgetAccommodation;

9hasAccommod u 8hasAccommod.Hotel;

9hasAccommod u 8hasAccommod.BedAndBreakfast;

9hasDestination u 8hasDestination.NationalPark;

9hasDestination u 8hasDestination.Capital:

4. Agents 1 and 2 control the following concepts (1) and (2), respectively: Informally, agent 1 decides whether the trip takes place to an urban, rural, or budget hotel destination, while 2’s offers fix the budget, the type of accommodation (hotel or BB), and the destination to a national park or capital city. 5. Agents 1 and 2 have the following strict goals (1) and (2), respectively: (1) = fU; R; BHDg; (2) = fBA; H; BB; NP; Cg: (1) = (U t R) u (H t BB); (2) = NP t C: Informally, agent 1 necessarily wants a destination in an urban or a rural area, e.g., she does not like beach destinations, and she also wants an accommodation for her trip in a hotel or a bed and breakfast, so she is excluding, e.g., camping grounds. Indeed, even if she is not explicitly saying anything about camping grounds, because of the disjointness axioms in the ontology, choosing an accommodation in either a hotel or a BB will also exclude the camping ground one. Whereas agent 2 is trying to sell a destination in a national park or a capital city. 6. Agents 1 and 2 have the following goals (1) and (2), respectively, (1) = (R u BB) t (C u BHD); (2) = (U u BB) t (NP u BHD): Informally, agent 1 would like a destination in a rural area and an accommodation in a bed and breakfast, or a budget hotel accommodation in a capital city. Whereas agent 2 would like to sell a destination in an urban area and an accommodation in a bed and breakfast, or a budget hotel destination in a national park.

We next define the notions of strategies, strategy profiles, and utility functions. In classical n-agent Boolean games, a strategy for agent i is a truth assignment si to all the variables she controls, and the utility functions of the agents depend on their goals built from the variables. In our setting, in contrast, atomic concepts are related to each other through a DL knowledge base L, and each agent may have some strict requirements, and so some truth assignments to the atomic concepts may be infeasible because of L and the strict requirements. We thus exclude such infeasible strategies. In addition, some combinations I of feasible strategies may result in an infeasible strategy profile due to L and the fact that the control assignment may be overlapping. We model this, exploiting the utility structure: if I is infeasible due to L or the overlapping control assignment, then the utility to all agents is 1; in contrast, if I is feasible, then the utility to agent i under I is equal to 1, if its goal (i) is satisfied, and 0, otherwise. Therefore, when the agreement I is unsatisfiable, then the utilities are always negative, that is, always less than the utilities when the agreement I is satisfiable. Hence, the unsatisfiable agreement will never be chosen by the agents.

Definition 3.2 (strategies, strategy profiles, utilities). Let G = (L; N; A; ; ; ) be an n-agent Boolean dl-game. Then, a strategy for agent i 2 N is an interpretation Ii for the concepts in (i) that satisfies both (i) L and (ii) (i) under L. A strategy profile I = (I1; I2; : : : ; In) consists of one strategy Ii for every agent i 2 N . We say I = (I1; I2; : : : ; In) is consistent iff (i) there exists an interpretation J for A such that Ii is the restriction of J to (i), for every agent i 2 N , and (ii) I satisfies L. The utility to agent i 2 N under I , denoted ui(I ), is defined as follows: ui(I ) = 8> 1 <

1 >:0

Example 3.2 (travel negotiation cont’d). The sets of all strategies I1 and I2 of agents 1

and 2, respectively, in the travel negotiation example are given as follows: I1 = fBA u H u :BB u NP u :C; BA u :H u BB u NP u :C;

BA u H u :BB u :NP u C; BA u :H u BB u :NP u C; :BA u H u :BB u NP u :C; :BA u :H u BB u NP u :C; :BA u H u :BB u :NP u C; :BA u :H u BB u :NP u Cg; I2 = fU u :R u BHD; :U u R u BHD;

U u :R u :BHD; :U u R u :BHDg: The set of all strategy profiles is I1 I2. The utility pairs (u1(I ); u2(I )) for each strategy profile I = (I1; I2) are shown in Fig. 2, which actually depicts the normal form of the two-agent Boolean dl-game G. Note that all inconsistent strategy profiles (due to the DL knowledge base L) are associated with two negative utilities.

U u :R u BHD u SS u HK :U u R u BHD u SS u HK U u :R u BHD u SS u :HK :U u R u BHD u SS u :HK U u :R u BHD u :SS u HK :U u R u BHD u :SS u HK BA u H u :BB u NP u :C u TP ( 1; 1) (1; 1) ( 1; 1) (0:7; 0:3) ( 1; 1) (0:4; 0)

BA u H u :BB u :NP u C u TP (0:7; 0:3) ( 1; 1) (0:4; 0) ( 1; 1) (0:4; 0) ( 1; 1)

BA u H u :BB u NP u :C u :TP ( 1; 1) (0:7; 0:7) ( 1; 1) (0:3; 0:3) ( 1; 1) (0:4; 0)

BA u H u :BB u :NP u C u :TP (0:4; 0) ( 1; 1) (0; 0) ( 1; 1) (0:4; 0) ( 1; 1)

We next define (pure) Nash equilibria of n-agent Boolean dl-games. Informally, as in the classical case, they are strategy profiles where no agent has the incentive to deviate from its part once the other agents stick to their parts.

Definition 3.3 (pure Nash equilibria). Let G = (L; N; A; ; ) be an n-agent Boolean dl-game with N = f1; : : : ; ng. Then, a strategy profile I = (I1; : : : ; In) is a (pure) Nash equilibrium of G iff ui(I C I0) 6 ui(I) for every strategy Ii0 of agent i and for every i agent i 2 N , where I C Ii0 is the strategy profile obtained from I by replacing Ii by Ii0.

Another concept of optimality for strategy profiles, which serves for choosing the best among a set of Nash equilibria, is the notion of Pareto-optimality. Informally, a strategy profile is Pareto-optimal if there exists no other strategy profile that makes one agent better off and no agent worse off in the utility. Note that, as in the classical case, Nash equilibria are not necessarily Pareto-optimal.

Definition 3.4 (Pareto-optimal strategy profiles). Let G = (L; N; A; ; ) be an nagent Boolean dl-game with N = f1; : : : ; ng. Then, a strategy profile I = (I1; : : : ; In) is Pareto-optimal iff there exists no strategy profile I0 such that (i) ui(I0) > ui(I) for some agent i 2 N and (ii) ui(I0) > ui(I) for every agent i 2 N .

Example 3.3 (travel negotiation cont’d). The set of all (pure) Nash equilibria of the two-agent Boolean dl-game G of Example 3.1 are given by the bold entries in Fig. 2. It is not difficult to verify that all, except for the (0; 0) ones, are also Pareto-optimal. 4

Weighted Generalized Goals

In this section, we further extend Boolean dl-games by weighted and generalized goals: – Instead of one single goal that each agent wants to satisfy, we now assume a set of goals for each agent, where each goal of an agent is associated with a weight. This considers the fact that goals can have different importance, so the best agreement is not necessarily the agreement satisfying the greatest number of goals for each agent. We thus define Boolean dl-games with weighted goals, that is, multi-valued preferences. Note that agent utilities are normalized to 1 to make them comparable. – We also do not assume that agent goals are constructed from the controlled atomic concepts.

Definition 4.1 (n-agent Boolean dl-games with weighted goals). An n-agent Boolean dl-game with weighted goals G = (L; N; A; ; ; ) consists of 1. a description logic knowledge base L, 2. a finite set of n agents N = f1; 2; : : : ; ng, n > 2, 3. a finite set of atomic concepts A, 4. a control assignment : N ! 2A, which associates with every agent i 2 N a set of atomic concepts (i) A, which she controls, 5. a strict goal assignment : N ! LA, which associates with every agent i 2 N a concept (i) 2 LA that is satisfiable under L, denoted the strict goal of i, and 6. a weighted goal assignment , which associates with every agent i 2 N a mapping i from a finite set of concepts Li that are satisfiable under L (denoted the weighted goals of i) to <+ such that P 2Li i( ) = 1.

Example 4.1 (travel negotiation cont’d). A two-agent Boolean dl-game with weighted goals G0 = (L0; N 0; A0; 0; 0; 0) for the travel negotiation example is obtained from the two-agent Boolean dl-game G = (L; N; A; ; ; ) of Example 3.1 as follows: 1. L0 = L. 2. N 0 = N . 3. A0 consists of the atomic concepts in A and the following new ones: TP SS HK

9hasActivity.ThemePark;

9hasActivity.Sightseeing;

9hasActivity.Hiking:

(1) = fU; R; BHD; SS; HKg; (2) = fBA; H; BB; NP; C; TPg: 4. Agents 1 and 2 control the following concepts (1) and (2), respectively: More concretely, compared to Example 3.1, the agents now control more variables, namely, Sightseeing and Hiking for agent 1, and ThemePark for agent 2. 5. Agents 1 and 2 have the following strict goals (1) and (2), respectively: (1) = (U t R) u (H t BB) u BHD; (2) = (NP t C) u >1 hasActivity: More specifically, compared to Example 3.1, the agents 1 and 2 now also require BudgetHotelDestination and >1 hasActivity, respectively, in the strict goals. Informally, agent 1 also wants a budget hotel destination, while agent 2 is trying to sell a destination which includes at least one activity. 6. Agents 1 and 2 have the following weighted goals 1 and 2, respectively, 1(FamilyDestination) = 0:3; 1(RelaxDestination) = 0:3; 1(9hasDestination.(Capital t RuralArea)u

9hasActivity.(Sport u ThemePark)) = 0:4; 2(9hasDestination.RuralAreau

9hasActivity.Sightseeing)

2(FamilyDestination u 9hasActivity.ThemePark)

2(RelaxDestination u 9hasActivity.Hiking)

= 0:3; = 0:3; = 0:4: Informally, agent 1 would like either (a) a family destination, or (b) a relax destination, or (c) a capital or rural destination with sports activities in a theme park, the latter with a slightly higher weight. Whereas agent 2 would like to sell either (a) a destination in a rural area with sightseeing, or (b) a family destination with theme park, or (c) a relax destination with hiking, the latter with slightly higher weight.

The notions of strategies and strategy profiles along with the consistency of strategy profiles are defined in the same way as for Boolean dl-games with binary goals. The following definition extends the notion of utility to weighted goals. Definition 4.2 (utilities with weighted goals). Let G = (L; N; A; ; ; ) be an nagent Boolean dl-game with weighted goals. Then, the utility to agent i 2 N under I, denoted ui(I), is defined as follows: ui(I) =

Example 4.2 (travel negotiation cont’d). The normal form representation of the twoagent Boolean dl-game with weighted goals G of Example 4.1 is depicted in Fig. 3. Its only (pure) Nash equilibria are given by the bold entries in Fig. 3. Observe that the Nash equilibrium with utility pair (1; 1) is also Pareto-optimal. 5

Complexity

We now analyze the complexity of important decision problems for n-player Boolean dl-games with weighted goals.

While much of the research on DLs of the last decade was centered around decidability issues, there is a current trend towards highly scalable techniques, which are especially necessary for applications in the Web and the Semantic Web. For this reason, we consider the DL-Lite family of tractable DLs [ 6 ] here. They are a restricted class of classical DLs for which the main reasoning tasks in DLs can be done in deterministic polynomial time in the size of the knowledge base and some of these tasks even in LogSpace in the size of the ABox in the data complexity. The DL-Lite DLs are the most common tractable DLs in the Semantic Web context. They are especially directed towards data-intensive applications.

It turns out that relative to the DL-Lite family of tractable DLs, n-player Boolean dl-games with weighted goals have the same complexity as standard n-player Boolean games.

The following result shows that deciding whether an interpretation satisfies a knowledge base in DL-Lite is tractable. Recall here that an interpretation is a full conjunction of atomic concepts and negated atomic concepts from A.

Theorem 5.1 (see [ 17 ]). Given a knowledge base L in DL-Lite and an interpretation I, deciding whether I j= L holds can be done in polynomial time.

The next result shows that deciding whether a strategy profile is a pure Nash equilibrium of a Boolean dl-game with weighted goals is co-NP-complete. Here, the upper bound follows from the fact that guessing and verifying a better strategy profile can be done in nondeterministic polynomial time, since deciding I j= L can be done in polynomial time, by Theorem 5.1, and the lower bound follows from the NP-hardness of propositional satisfiability.

Theorem 5.2. Given an n-agent Boolean dl-game G = (L; N; A; ; ; ) with weighted goals, where L is in DL-Lite, and a strategy profile I, deciding whether I is a pure Nash equilibrium of G is co-NP-complete. Hardness holds even when n = 2, L = ;, and (i) = > and j (i)j = 1 for all i 2 N .

Similarly, deciding whether a strategy profile is a Pareto-optimal pure Nash equilibrium is also complete for co-NP.

Theorem 5.3. Given an n-agent Boolean dl-game G = (L; N; A; ; ; ) with weighted goals and L in DL-Lite, and a strategy profile I, deciding if I is a Pareto-optimal pure Nash equilibrium of G is co-NP-complete. Hardness holds even when n = 2, L = ;, and (i) = > and j (i)j = 1 for all i 2 N .

The following result shows that deciding whether an n-agent Boolean dl-game has a pure Nash equilibrium is complete for 2p. Here, the upper bound follows from the observation that guessing a pure Nash equilibrium and verifying it can be done in nondeterministic polynomial time with an oracle for NP, since deciding I j= L can be done in polynomial time, by Theorem 5.1. The lower bound follows from the 2p-hardness of deciding whether a standard 2-player Boolean game has a pure Nash equilibrium. Theorem 5.4. Given an n-agent Boolean dl-game G = (L; N; A; ; ; ) with weighted goals, where L is in DL-Lite, deciding whether G has a pure Nash equilibrium is 2p-complete. Hardness holds even when n = 2, L = ;, and (i) = > and j (i)j = 1 for all i 2 N .

As an immediate consequence, deciding the existence of Pareto-optimal pure Nash equilibria is also 2p-complete.

Corollary 5.1. Given an n-agent Boolean dl-game G = (L; N; A; ; ; ) with weighted goals, where L is in DL-Lite, deciding whether G has a Pareto-optimal pure Nash equilibrium is 2p-complete. Hardness holds even when n = 2, L = ;, and (i) = > and j (i)j = 1 for all i 2 N .

For more expressive DLs, deciding I j= L has in general a higher complexity, and consequently also the above decision problems for n-agent Boolean dl-games have a higher complexity. For example, for the DLs behind OWL Lite and OWL DL, deciding I j= L is in EXP and NEXP, respectively. Thus, verifying pure and Pareto-optimal pure Nash equilibria is in EXP and NEXP, respectively, while deciding their existence is in EXP and NPNEXP = PNEXP, respectively. 6

Related Work

A large number of negotiation mechanisms have been proposed and studied in the literature. It is possible to distinguish, among others, game-theoretic ones [ 16,20 ], heuristicbased approaches [ 9,8 ] and logic-based approaches. In the following, we give a brief overview of logic-based approaches to automated negotiation, comparing our approach to existing ones and highlighting relevant differences. Several recent logic-based approaches to negotiation are based on propositional logic. Bouveret et al. [ 5 ] use weighted propositional formulas (WPFs) to express agent preferences in the allocation of indivisible goods, but no common knowledge (as our ontology) is present. The use of an ontology allows, e.g., to discover inconsistencies between strategies, as well as attributes, or find out if an agent preference is implied by a combination of strategies (an interpretation) which is fundamental to model a multi-attribute negotiation. Chevaleyre et al. [ 7 ] classify utility functions expressed through WPFs according to the properties of the utility function (sub/super-additive, monotone, etc.). We used the most expressive functions according to that classification, namely, weights over unrestricted formulas. Zhang and Zhang [ 22 ] adopt a kind of propositional knowledge base arbitration to choose a fair negotiation outcome. However, common knowledge is considered as just more entrenched preferences, that could be even dropped in some deals. Instead, the logical constraints in our ontology must always be enforced in the negotiation outcomes. Wooldridge and Parsons [ 21 ] define an agreement as a model for a set of formulas from both agents. However, Wooldridge and Parsons [ 21 ] only study multiple-rounds protocols 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 compute utility values and check if the reached agreement is Pareto-optimal or a Nash equilibrium. For what concerns approaches using more expressive ontology languages, namely, DLs, there is the work by Ragone et al. [ 18 ], which although uses the rather inexpressive DL ALE H(D), proposes a semantic-based alternating-offers protocol exploiting non-standard inference services (such as concept contraction) and utility theory to find the most suitable agreements. Furthermore, differently from our approach, no game-theoretic analysis is provided about Nash equilibria. Another work exploits DLs in negotiation scenarios [ 19 ], where the more expressive SHOIN (D) is used to model the logic-based negotiation protocol; a scenario with fully incomplete information is studied, where agents do not know anything about the opponent (neither preferences nor utilities). Furthermore, also this framework lacks a game-theoretic analysis about Nash equilibria. 7

Summary and Outlook

We have introduced Boolean description logic games, which combine classical Boolean games with expressive description logics. As further generalizations of classical Boolean games, they also include strict agent requirements, overlapping agent control assignments, and weighted goals, which may be defined over free description logic concepts. We have also analyzed the complexity of Boolean description logic games for the DL-Lite family of description logics. Furthermore, formulations of a travel service negotiation scenario have given a hint of the practical usefulness of our approach.

An interesting topic for future research is to implement a tool for solving Boolean dl-games and testing it on negotiation scenarios. Another topic for future research is a generalization to qualitative conditional preference structures, such as the ones expressed through CP-nets [ 4 ]. Acknowledgments. Azzurra Ragone wishes to thank Francesco M. Donini and Tommaso Di Noia for fruitful suggestions and discussions. This work has been partially supported by the Apulia Region funded project PS 092 Distributed Production to Innovative System (DIPIS), by the Austrian Science Fund (FWF) under the project P18146N04, and by the German Research Foundation (DFG) under the Heisenberg Programme.

References

1. F. Baader , D. Calvanese , D. L. McGuinness , D. Nardi , and P. F. Patel- Schneider, editors. The Description Logic Handbook . Cambridge University Press, 2003 .

2. T. Berners-Lee. Weaving the Web . Harper, San Francisco, CA, 1999 .

3. E. Bonzon , M.- C. Lagasquie-Schiex , J. Lang , and B. Zanuttini . Compact preference representation and Boolean games . Auton. Agent. Multi-Ag., 18 ( 1 ): 1 - 35 , 2008 .

4. C. Boutilier , R. I. Brafman , C. Domshlak , H. H. Hoos , and D. Poole . CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements . J. Artif. Intell. Res. , 21 : 135 - 191 , 2004 .

5. S. Bouveret , M. Lemaitre , H. Fargier , and J. Lang . Allocation of indivisible goods: A general model and some complexity results . In Proc. AAMAS-2005 , pp. 1309 - 1310 .

6. D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , and R. Rosati . Tractable reasoning and efficient query answering in description logics: The DL-Lite family . J. Autom. Reasoning , 39 ( 3 ): 385 - 429 , 2007 .

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

8. P. Faratin , C. Sierra , and N. R. Jennings . Using similarity criteria to make issue trade-offs in automated negotiations . Artif . Intell., 142 ( 2 ): 205 - 237 , 2002 .

9. S. Fatima , M. Wooldridge , and N. R. Jennings . Optimal agendas for multi-issue negotiation . In Proc. AAMAS-2003 , pp. 129 - 136 .

10. D. Fensel , W. Wahlster , H. Lieberman , and J. Hendler, editors. Spinning the Semantic Web: Bringing the World Wide Web to Its Full Potential . MIT Press, 2002 .

11. P. Harrenstein . Logic in Conflict. PhD thesis , Utrecht University, The Netherlands, 2004 .

12. P. Harrenstein , W. van der Hoek, J.-J. C. Meyer, and C. Witteveen . Boolean games . In Proc. TARK-2001 , pp. 287 - 298 .

13. J. A. Hendler . Where are all the intelligent agents? IEEE Intell . Syst., 22 ( 3 ): 2 - 3 , 2007 .

14. I. Horrocks and P. F. Patel-Schneider . Reducing OWL entailment to description logic satisfiability . J. Web Sem ., 1 ( 4 ): 345 - 357 , 2004 .

15. N. R. Jennings , P. Faratin , A. R. Lomuscio , S. Parsons , M. Wooldridge , and C. Sierra . Automated negotiation: Prospects , methods and challenges. Group Decision and Negotiation , 10 : 199 - 215 , 2001 .

16. S. Kraus . Strategic Negotiation in Multiagent Environments . MIT Press, 2001 .

17. T. Lukasiewicz . Expressive probabilistic description logics . Artif . Intell., 172 ( 6 /7): 852 - 883 , 2008 .

18. A. Ragone , T. Di Noia , E. Di Sciascio , and F. M. Donini . Alternating-offers protocol for multi-issue bilateral negotiation in semantic-enabled marketplaces . In Proc. ISWC-2007 , pp. 395 - 408 .

19. A. Ragone , T. Di Noia , E. Di Sciascio , and F. M. Donini . Description logics for multi-issue bilateral negotiation with incomplete information . In Proc. AAAI-2007 , pp. 477 - 482 .

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

21. M. Wooldridge and S. Parsons . Languages for negotiation . In Proc. ECAI-2000 , pp. 393 - 400 .

22. D. Zhang and Y. Zhang. A computational model of logic-based negotiation . In Proc. AAAI2006 , pp. 728 - 733 .