Recently, multi-attribute negotiation has been extensively studied from a game-theoretic viewpoint. Since normal and extensive form games have the drawback of requiring an explicit representation of utility functions (listing the utility values for all combinations of strategies), logical preference languages have been proposed, which provide a convenient way to compactly specify multiattribute utility functions. Among these preference languages, there are also Boolean games. In this paper, towards automated multi-attribute negotiation in the Semantic Web, we introduce Boolean description logic games, which are a combination of Boolean games with ontological background knowledge, formulated in expressive description logics. We include and discuss several generalizations, and show how a travel and a service negotiation scenario can be formulated in Boolean description logic games, which shows their practical usefulness.
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 [1].
Another area with an impressive amount of recent research activities is the Semantic Web [2,3], which aims at an extension of the current World Wide 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 Web resources, to use knowledge representation technology for automated reasoning from Web resources, 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 [4]. 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 Boolean description logic games, which are a combination of n-player Boolean games with description logics. They informally combine 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 Boolean dl-games where each agent has a set of weighted goals, which may be defined over free description logic concepts. We finally propose another generalization, where the agents own roles rather than concepts. – We provide many examples (from a travel and 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, such games aim at a centralized one-step negotiation process, where the agents reveal their preferences to a central mediator, which then calculates one optimal strategy for each agent. Clearly, this 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 (see also Example 5.1).
The rest of this paper is organized as follows. In Section 2, we recall the basics of description logics and Boolean games. Section 3 defines Boolean description logic games. In Section 4, we introduce Boolean description logic games with weighted generalized goals. Section 5 generalizes the ontological ownerships. In Section 6, we discuss related work. Section 7 summarizes the main results and gives an outlook on future research. 2
2.1
Description Logics In this section, we recall the basic concepts of description logics and Boolean games. We now recall the description logics SHIF (D) and SHOIN (D), which stand behind the web ontology languages OWL Lite and OWL DL [5], respectively. Intuitively, description logics model a domain of interest in terms of concepts and roles, which represent classes of individuals and binary relations between classes of individuals, respectively. A description logic knowledge base encodes especially subset relationships between concepts, subset relationships between roles, the membership of individuals to concepts, and the membership of pairs of individuals to roles. Syntax. We first describe the syntax of SHOIN (D). We assume a set of elementary datatypes and a set of data values. A datatype is either an elementary datatype or a set of data values (called datatype oneOf ). A datatype theory D = ( D; D) consists of a datatype domain D and a mapping D that assigns to each elementary datatype a subset of D and to each data value an element of D. The mapping D is extended to all datatypes by fv1; : : :gD = fv1D; : : :g. Let A, RA, RD, and I be pairwise disjoint (nonempty) denumerable sets of atomic concepts, abstract roles, datatype roles, and individuals, respectively. We denote by RA the set of inverses R of all R 2 RA.
A role is an element of RA [ RA [ RD. Concepts are inductively defined as follows. Every 2 A is a concept, and if o1; : : : ; on 2 I, then fo1; : : : ; ong is a concept (called oneOf). If , 1, and 2 are concepts and if R 2 RA [ RA, then also ( 1 u 2), ( 1 t 2), and : are concepts (called conjunction, disjunction, and negation, respectively), as well as 9R: , 8R: , >nR, and 6nR (called exists, value, atleast, and atmost restriction, respectively) for an integer n > 0. If D is a datatype and U 2 RD, then 9U:D, 8U:D, >nU , and 6nU are concepts (called datatype exists, value, atleast, and atmost restriction, respectively) for an integer n > 0. We write 9R and 8R to abbreviate 9R:> and 8R:>, respectively. We write > and ? to abbreviate the concepts t : and u : , respectively, and we eliminate parentheses as usual.
An axiom has one of the following forms: (
The syntax of SHIF (D) is as the above syntax of SHOIN (D), but without the oneOf constructor and with the atleast and atmost constructors limited to 0 and 1. Example 2.1 (travel ontology). A description logic knowledge base L encoding a travel ontology (adapted from http://protege.cim3.net/file/pub/ontologies/travel/) is given by the axioms in Fig. 1. For example, there are some axioms encoding that bed and breakfast accommodations and hotels are different accommodations, and that a budget accommodation is an accommodation that has one or two stars as a rating. Semantics. An interpretation I = ( I ; I ) w.r.t. a datatype theory D = ( D; D) consists of a nonempty (abstract) domain I disjoint from D, and a mapping I that assigns to each atomic concept 2 A a subset of I , to each individual o 2 I an element of I , to each abstract role R 2 RA a subset of I I , and to each datatype role U 2 RD a subset of I D. We extend I to all concepts and roles, and we define the satisfaction of an axiom F in an interpretation I = ( I ; I ), denoted I j= F , as usual [5]. We say I satisfies the axiom F , or I is a model of F , iff I j= F . We say I satisfies a knowledge base L, or I is a model of L, denoted I j= L, iff I j= F for all F 2 L. We say L is satisfiable (resp., unsatisfiable) iff L has a (resp., no) model. An axiom F is a logical consequence of L, denoted L j= F , iff each model of L satisfies F .
BudgetHotelDestination
u 8hasAccomodation.(BudgetAccommodation u Hotel); fOneStarRating; TwoStarRating; ThreeStarRatingg; AccommodationRating
hasActivity isOfferedAt .
Example 2.2 (travel ontology cont’d). It is not difficult to verify that the description logic knowledge base L of Example 2.1 is satisfiable, and that the two concept inclusion axioms Capital v UrbanArea and Capital v :RuralArea are logical consequences of L. Informally, L implies that capitals are urban and not rural areas. We now recall n-player Boolean games from [7], which are a generalization of 2-player Boolean games from [8,9]. Such games are essentially normal form games where propositional logic is used for compactly specifying multi-attribute utility functions. We first give some preparative definitions, and then recall n-player Boolean games, including their ingredients, strategy profiles, and important notions of optimality.
We assume a finite 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
(
Example 2.3 (Boolean game). A two-player Boolean game G = (N; V; ; ) is given by:
(
A strategy for player i 2 N is any truth assignment si to the variables in (i). A strategy profile s = (s1; : : : ; sn) consists of one strategy si for every i 2 N . The utility to player i 2 N under s, denoted ui(s), is 1, if s satisfies i’s goal (i), and 0, otherwise.
Towards optimal behavior of the players in an n-player Boolean game, we are especially interested in strategy profiles s, called Nash equilibria, where no agent has the incentive to deviate from its part, once the other agents play their parts. More formally, a strategy profile s = (s1; : : : ; sn) is a Nash equilibrium iff ui(s C s0i) 6 ui(s) for every strategy s0i of player i and for every player i 2 N , where s C s0i is the strategy profile obtained from s = (s1; : : : ; sn) by replacing si by s0i.
Another important notion of optimality is Pareto-optimality. Informally, a strategy profile is Pareto-optimal if there exists no other strategy profile that makes one player better off and no player worse off in the utility. More formally, a strategy profile s is Pareto-optimal iff there exists no strategy profile s0 such that (i) ui(s0) > ui(s) for some player i 2 N and (ii) ui(s0) > ui(s) for every player i 2 N .
Example 2.4 (Boolean game cont’d). Consider again the two-player Boolean game G = (N; V; ; ) of Example 2.3. Player 1 has all truth assignments to the variables a and c (that is, a; c 7! true; true, a; c 7! true; false, a; c 7! false; true, and a; c 7! false; false, denoted a c, a c, a c, and a c, respectively) as strategies, while player 2 has all truth assignments to b as strategies (that is, b 7! true and b 7! false, denoted b and b, respectively). Any combination of the strategies of two players is a strategy profile. For example, (a c; b) is a strategy profile combining the strategy a c of player 1 and the strategy b of player 2.
The normal form of this two-player Boolean game, using the above strategy profiles s = (s1; s2), which combine all strategies s1 and s2 of the players 1 and 2, respectively, is depicted in Fig. 2: for every strategy profile s = (s1; s2), the matrix has one entry, which shows the pair of utilities (u1(s); u2(s)) under s to the two players. The utility ui(s) is equal to 1, when (i) is satisfied in s, and 0, otherwise.
It is then not difficult to verify that the strategy profile (a c; b) is a (pure) Nash equilibrium of this two-player Boolean game G, which is also Pareto-optimal, while (a c; b) is also a (pure) Nash equilibrium of G, but not Pareto-optimal.
In this section, we combine classical n-player Boolean games with ontologies. The main differences to classical n-player Boolean games are summarized as follows (note that many of the new features are also illustrated in Example 3.1): – Rather than unrelated propositional variables, the agents now control atomic description logic concepts, which may (abbreviate complex description logic concepts and) be related via a description logic knowledge base. In fact, the assumption that the controlled variables are unrelated in classical n-player Boolean games is quite unrealistic; often the variables are related through some background knowledge. – Rather than having only preferences, the 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. – Rather than defining a partition, the control assignment may now be overlapping.
In fact, such overlapping control assignments are also more realistic.
We first give some preparative definitions as follows. We use a finite set of atomic
concepts A as set of propositional variables V in n-player Boolean games. We denote
by LA the set of all concepts (denoted by Greek letters ; ; : : :) 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 description
logic 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
(
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. The following example illustrates n-agent Boolean dl-games.
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:
(
BudgetHotelDestination; 9hasAccomodation u 8hasAccomodation.BudgetAccommodation; 9hasAccomodation u 8hasAccomodation.Hotel; 9hasAccomodation u 8hasAccomodation.BedAndBreakfast; 9hasDestination u 8hasDestination.NationalPark;
(
Whereas agent 2 is trying to sell a destination in a national park or a capital city.
(
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 description logic 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 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 C :BA u :H u BB u :NP u C
U u :R u BHD :U u R u BHD U u :R u :BHD :U u R u :BHD ( 1; 1) (0; 1) ( 1; 1) (0; 0) ( 1; 1) ( 1; 1) ( 1; 1) (1; 0)
(1; 0) ( 1; 1) (0; 0) ( 1; 1) ( 1; 1) ( 1; 1) (0; 1) ( 1; 1) ( 1; 1) ( 1; 1) ( 1; 1) (0; 0) ( 1; 1) ( 1; 1) ( 1; 1) (1; 0) ( 1; 1) ( 1; 1) (0; 0) ( 1; 1) ( 1; 1) ( 1; 1) (0; 1) ( 1; 1) 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:
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. 3, which actually depicts the normal form of the two-agent Boolean dl-game G. Note that all inconsistent strategy profiles (due to the description logic knowledge base L) are associated with two negative utilities.
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 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 .
We illustrate the notions of Nash equilibria and Pareto-optimality in our example. 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. 3. It is not difficult to verify that all except for the (0; 0) ones are also Pareto-optimal. 4
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 first define Boolean dl-games with weighted goals, that is, multi-valued preferences. Note that agent utilities are normalized to 1 to make them comparable. – As another difference to Boolean dl-games, we also do not assume anymore 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
(
We give an example of a Boolean dl-game with weighted goals.
TP SS HK 9hasActivity.ThemePark;
(
9hasActivity.(Sport u ThemePark)) = 0:4; 2(9hasDestination.RuralArea u 9hasActivity.Sightseeing) = 0:3; 2(FamilyDestination u 9hasActivity.ThemePark) = 0:3; 2(RelaxDestination u 9hasActivity.Hiking) = 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. 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 ( 1; 1) 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: 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. 4. Its only (pure) Nash equilibria are given by the bold entries in Fig. 4. Observe that the Nash equilibrium with utility pair (1; 1) is also Pareto-optimal. 5
In this section, we present a further generalization of Boolean dl-games where agents
control roles instead of concepts. In this case, every strategy is intuitively an
instantiation of concepts. We also provide a further application scenario from web service
negotiation, along which we sketch this generalization of Boolean dl-games.
Example 5.1 (web service negotiation). Consider a service negotiation scenario, where
a service provider (agent 2) and a service requester (agent 1) are negotiating on the
conditions of a supply. The description logic knowledge base L is given by the ontology in
Fig. 5. We assume the set of two agents N = f1; 2g. The roles (
HighQualityService v 9assistance u 8assistance.Onsite u =2 year guarantee; LowQualityService v 9assistance u 8assistance.Phone u =1 year guarantee;
Agents 1 and 2 have the following goals (
(9hasQuality u 8hasQuality.HighQualityService u
The normal form of the two-agent Boolean dl-game is depicted in Fig. 6, where (for the sake of conciseness) we define the following atomic concepts:
C1 C2 HQ WW SE
Notice that in this approach agents do not have to enumerate all the possible combinations of concepts they control, as before, but, as they control roles instead of concepts, it is enough to consider only concepts that they are interested in, such as e.g. for agent 1 HighQualityService or for agent 2 only the type of contracts she wants to offer. This approach is surely more compact than the previous one, even if it could be not exhaustive and give more power w.r.t. some attributes to one agent, the one controlling the role indeed can control an entire set of attributes, e.g., thanks to the control on hasType, agent 2 is the only one that can choose what type of contract to offer.
A large number of negotiation mechanisms have been proposed and studied in the literature. It is possible to distinguish, among others, game-theoretic ones [10,11], heuristicbased approaches [12,13] and logic-based approaches. Although pure game-theoretic and heuristic-based approaches are highly suitable for a wide range of applications, they have some limitations and disadvantages. Often in game-theoretic approaches, it is assumed that no relation exists between agent’s strategies and that all the combinations of strategies are possible. Moreover, they usually do not model relations about issues, which is, instead, fundamental in multi-attribute negotiation. On the other hand, heuristic-based approaches use empirical evaluations to find an agreement, which can be sub-optimal, as they do not explore the entire space of possible outcomes.
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. There is an extensive literature on argumentation-based negotiation [14,15,16]. In these approaches, an agent can accept/reject/critique a proposal of its opponent, so agents can argue about their beliefs, given their desires and so pursue their intentions. With respect to our framework, these approaches require a larger number of communication rounds in order to exchange information, while our approach is a one-shot negotiation, which ensures the termination after only one round; indeed in argumentationbased frameworks, usually, agent interactions go back and forth for multiple rounds.
Several recent logic-based approaches to negotiation are based on propositional logic. Bouveret et al. [17] 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. [18] 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 [19] 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 [20] define an agreement as a model for a set of formulas from both agents. However, Wooldridge and Parsons [20] 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. In the work by Ragone et al. [21], a basic propositional logic framework endowed with an ontology was proposed, which is further extended in [22], introducing the extended logic P(N ) (a propositional logic with concrete domains), thus handling numerical features, and showed how to compute Pareto-optimal agreements, by solving an optimization problem and adopting a one-shot negotiation protocol.
For what concerns approaches using more expressive ontology languages, namely, description logics, there is the work by Ragone et al. [23], which although uses a rather inexpressive description logic, ALE H(D), proposes a semantic-based alternating-offers protocol exploiting non-standard inference services, as concept contraction, and utility theory to find the most suitable agreements. Concept contraction can be useful to provide an explanation of “what is wrong” between request and offer, that is, the reason why agents cannot reach an agreement and what has to be given up in order to reach that. Furthermore, differently from our approach, no game-theoretic analysis is provided about Nash equilibria, even if in this framework, agents do not have to reveal their utilities to the opponent. Another work exploits description logics in negotiation scenarios [24], 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
Towards automated multi-attribute negotiation in the Semantic Web, we have introduce 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 and overlapping agent control assignments. We have also considered two generalizations, one with weighted goals, which may be defined over free description logic concepts, and one where the agents own roles rather than concepts. Furthermore, formulations of a travel and a service negotiation scenario have given evidence of the practical usefulness of our approach.
An interesting topic for future research is to more deeply analyze the semantic and the computational properties of Boolean description logic games. In particular, an important issue is the development of algorithms for computing optimal strategy profiles, and the analysis of its computational complexity. Furthermore, it would be interesting 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 [25]. From a larger perspective, Boolean dl-games aim at a centralized one-step negotiation process, where the agents reveal their preferences to a central mediator, which then calculates one optimal strategy for each agent. In this framework, it is important to study how it is possible to avoid that the agents report untruthful preferences in order to obtain better strategies, which is touching the problem of mechanism design [26].
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 P18146-N04, and by the German Research Foundation (DFG) under the Heisenberg Programme.