=Paper=
{{Paper
|id=Vol-416/paper-6
|storemode=property
|title=Combining Boolean Games with the Power of Ontologies for Automated Multi-Attribute Negotiation in the Semantic Web
|pdfUrl=https://ceur-ws.org/Vol-416/paper5.pdf
|volume=Vol-416
|dblpUrl=https://dblp.org/rec/conf/semweb/LukasiewiczR08
}}
==Combining Boolean Games with the Power of Ontologies for Automated Multi-Attribute Negotiation in the Semantic Web==
https://ceur-ws.org/Vol-416/paper5.pdf
Combining Boolean Games with the Power of
Ontologies for Automated Multi-Attribute
Negotiation in the Semantic Web
Thomas Lukasiewicz1,3 and Azzurra Ragone2
1
Computing Laboratory, University of Oxford
Wolfson Building, Parks Road, Oxford OX1 3QD, UK
thomas.lukasiewicz@comlab.ox.ac.uk
2
Information Systems Laboratory, Politecnico di Bari
Via E. Orabona 4, 70125 Bari, Italy
a.ragone@poliba.it
Abstract. 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 multi-
attribute utility functions. Among these preference languages, there are also Boo-
lean games. In this paper, towards automated multi-attribute negotiation in the
Semantic Web, we introduce Boolean description logic games, which are a com-
bination 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.
1 Introduction
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,
3
Alternative address: Institut für Informationssysteme, Technische Universität Wien, Favoriten-
str. 9-11, 1040 Wien, Austria; email: lukasiewicz@kr.tuwien.ac.at.
2 T. Lukasiewicz and A. Ragone
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 pro-
pose 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 de-
scription 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 Preliminaries
In this section, we recall the basic concepts of description logics and Boolean games.
2.1 Description Logics
We now recall the description logics SHIF(D) and SHOIN (D), which stand be-
hind 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, re-
spectively. 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.
Combining Boolean Games with the Power of Ontologies 3
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 {v1 , . . .}D = {v1D , . . .}. 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 R− −
A the set of inverses R of all R ∈ RA .
−
A role is an element of RA ∪ RA ∪ RD . Concepts are inductively defined as fol-
lows. Every φ ∈ A is a concept, and if o1 , . . . , on ∈ I, then {o1 , . . . , on } is a concept
(called oneOf). If φ, φ1 , and φ2 are concepts and if R ∈ RA ∪ R− A , then also (φ1 u φ2 ),
(φ1 t φ2 ), and ¬φ are concepts (called conjunction, disjunction, and negation, respec-
tively), as well as ∃R.φ, ∀R.φ, >nR, and 6nR (called exists, value, atleast, and at-
most restriction, respectively) for an integer n > 0. If D is a datatype and U ∈ RD , then
∃U.D, ∀U.D, >nU , and 6nU are concepts (called datatype exists, value, atleast, and
atmost restriction, respectively) for an integer n > 0. We write ∃R and ∀R to abbrevi-
ate ∃R.> and ∀R.>, 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: (1) φ v ψ (called concept inclusion ax-
iom), where φ and ψ are concepts; (2) R v S (called role inclusion axiom), where ei-
ther R, S ∈ RA or R, S ∈ RD ; (3) Trans(R) (called transitivity axiom), where R ∈ RA ;
(4) φ(a) (called concept membership axiom), where φ is a concept and a ∈ I; (5) R(a, b)
(resp., U (a, v)) (called role membership axiom), where R ∈ RA (resp., U ∈ RD ) and
a, b ∈ I (resp., a ∈ I and v is a data value); and (6) a = b (resp., a 6= b) (equality (resp.,
inequality) axiom), where a, b ∈ I. A knowledge base L is a finite set of axioms. For
decidability, number restrictions in L are restricted to simple abstract roles [6]. Since
knowledge bases encode ontologies, we also use ontology to denote a knowledge base.
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 break-
fast accommodations and hotels are different accommodations, and that a budget ac-
commodation 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 ) con-
sists of a nonempty (abstract) domain ∆I disjoint from ∆D , and a mapping ·I that
assigns to each atomic concept φ ∈ A a subset of ∆I , to each individual o ∈ I an ele-
ment of ∆I , to each abstract role R ∈ RA a subset of ∆I × ∆I , and to each datatype
role U ∈ RD a subset of ∆I × ∆D . We extend ·I to all concepts and roles, and we de-
fine the satisfaction of an axiom F in an interpretation I = (∆I , ·I ), denoted I |= F , as
usual [5]. We say I satisfies the axiom F , or I is a model of F , iff I |= F . We say I sat-
isfies a knowledge base L, or I is a model of L, denoted I |= L, iff I |= F for all F ∈ 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 |= F , iff each model of L satisfies F .
4 T. Lukasiewicz and A. Ragone
BedAndBreakfast v Accomodation;
Hotel v Accomodation;
BedAndBreakfast v ¬Hotel;
BudgetAccommodation ≡ Accomodation u ∃hasRating.{OneStarRating, TwoStarRating};
UrbanArea v Destination;
City v UrbanArea;
Capital v City;
RuralArea v Destination;
NationalPark v RuralArea;
RuralArea v ¬UrbanArea;
BudgetHotelDestination ≡ ∃hasAccomodation
u ∀hasAccomodation.(BudgetAccommodation u Hotel);
AccommodationRating ≡ {OneStarRating, TwoStarRating, ThreeStarRating};
Sightseeing v Activity;
Hiking v Sport;
Sport v Activity;
ThemePark v Activity;
FamilyDestination ≡ ∃hasDestination u ∃hasAccomodation u > 3 hasActivity;
RelaxDestination ≡ ∃hasDestination.NationalPark u ∃hasActivity.Sightseeing;
hasActivity ≡ isOfferedAt− .
Fig. 1. Travel ontology.
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.
2.2 Boolean Games
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 propo-
sitional 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 = {p1 , p2 , . . . , pk }. 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 = {1, 2, . . . , n}, n > 2,
(2) a finite set of propositional variables V ,
(3) a control assignment π : N → 2V , which associates with every player i ∈ N a set
of variables π(i) ⊆ V , which she controls, such that {π(i) | i ∈ N } partitions V , and
(4) a goal assignment Φ : N → LV , which associates with every player i ∈ N a propo-
sitional formula Φ(i) ∈ LV , denoted the goal of i.
Example 2.3 (Boolean game). A two-player Boolean game G = (N, V, π, Φ) is given by:
(1) the set of two players N = {1, 2},
Combining Boolean Games with the Power of Ontologies 5
b b
ac (1,0) (0,1)
ac (1,0) (1,1)
ac (0,0) (0,1)
ac (0,0) (1,0)
Fig. 2. Normal form of a two-player Boolean game.
(2) the set of propositional variables V = {a, b, c},
(3) the control assignment π(1) = {a, c} and π(2) = {b}, and
(4) the goal assignment Φ(1) = (a ∧ b) ∨ (¬c ∧ ¬b) and Φ(2) = (c ∧ ¬b) ∨ (a ∧ ¬b).
Informally, we have two players 1 and 2, and three propositional variables a, b, and c.
Player 1 (resp., 2) controls the variables a and c (resp., the variable b) and has the goal
expressed by the propositional formula Φ(1) (resp., Φ(2)).
A strategy for player i ∈ 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 ∈ N . The utility
to player i ∈ 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 es-
pecially 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 ∈ N , where s C s0i is the strategy profile ob-
tained 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 ∈ N and (ii) ui (s0 ) > ui (s) for every player i ∈ 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 pro-
file. 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 util-
ity 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.
6 T. Lukasiewicz and A. Ragone
3 Boolean Description Logic Games
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 de-
scription 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 |= L, iff L ∪ {I(o)} is satisfiable, where o is a
new individual. We say I satisfies a concept φ over A under L, denoted I |=L φ,
iff L |= I v φ. We say φ is satisfiable under L iff there exists an interpretation I such
that I |=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 de-
scription logic game (or n-agent Boolean dl-game) G = (L, N, A, π, Σ, Φ) consists of
(1) a description logic knowledge base L,
(2) a finite set of n agents N = {1, 2, . . . , n}, n > 2,
(3) a finite set of atomic concepts A,
(4) a control assignment π : N → 2V , which associates with every agent i ∈ N a set of
atomic concepts π(i) ⊆ A, which she controls,
(5) a strict goal assignment Σ : N → LA , which associates with every agent i ∈ N
a concept Σ(i) ∈ 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 ∈ N a concept
Φ(i) ∈ 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 satis-
fied. 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:
Combining Boolean Games with the Power of Ontologies 7
(1) L is the travel ontology of Example 2.1, depicted in Fig. 1.
(2) N = {1, 2}, 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 ≡ ∃hasDestination u ∀hasDestination.UrbanArea;
R ≡ ∃hasDestination u ∀hasDestination.RuralArea;
BHD ≡ BudgetHotelDestination;
BA ≡ ∃hasAccomodation u ∀hasAccomodation.BudgetAccommodation;
H ≡ ∃hasAccomodation u ∀hasAccomodation.Hotel;
BB ≡ ∃hasAccomodation u ∀hasAccomodation.BedAndBreakfast;
NP ≡ ∃hasDestination u ∀hasDestination.NationalPark;
C ≡ ∃hasDestination u ∀hasDestination.Capital.
(4) Agents 1 and 2 control the following concepts π(1) and π(2), respectively:
π(1) = {U, R, BHD};
π(2) = {BA, H, BB, NP, C}.
Informally, agent 1 decides whether the trip takes place to an urban, rural, or budget
hotel destination, while agent 2’s offers fix the budget, hotel, or bed and breakfast
accommodation, and the destination to a national park or a capital city.
(5) Agents 1 and 2 have the following strict goals Σ(1) and Σ(2), respectively:
Σ(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.
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 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
8 T. Lukasiewicz and A. Ragone
U u ¬R u BHD ¬U u R u BHD U u ¬R u ¬BHD ¬U u R u ¬BHD
BA u H u ¬BB u NP u ¬C (−1, −1) (0, 1) (−1, −1) (0, 0)
BA u ¬H u BB u NP u ¬C (−1, −1) (−1, −1) (−1, −1) (1, 0)
BA u H u ¬BB u ¬NP u C (1, 0) (−1, −1) (0, 0) (−1, −1)
BA u ¬H u BB u ¬NP u C (−1, −1) (−1, −1) (0, 1) (−1, −1)
¬BA u H u ¬BB u NP u ¬C (−1, −1) (−1, −1) (−1, −1) (0, 0)
¬BA u ¬H u BB u NP u ¬C (−1, −1) (−1, −1) (−1, −1) (1, 0)
¬BA u H u ¬BB u ¬NP u C (−1, −1) (−1, −1) (0, 0) (−1, −1)
¬BA u ¬H u BB u ¬NP u C (−1, −1) (−1, −1) (0, 1) (−1, −1)
Fig. 3. Normal form of a two-agent Boolean dl-game.
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 ∈ 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 ∈ 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 ∈ N , and (ii) I satisfies L. The utility
to agent i ∈ N under I, denoted ui (I), is defined as follows:
−1 if I is inconsistent, or I 6|=L Σ(i);
ui (I) = 1 if I is consistent, I |=L Σ(i), and I |=L Φ(i);
0 if I is consistent, I |=L Σ(i), and I 6|=L Φ(i).
We illustrate the above ideas with the help of a simple example.
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 = {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};
I2 = {U u ¬R u BHD, ¬U u R u BHD, U u ¬R u ¬BHD, ¬U u R u ¬BHD}.
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 de-
viate from its part once the other agents stick to their parts.
Combining Boolean Games with the Power of Ontologies 9
Definition 3.3 (pure Nash equilibria). Let G = (L, N, A, π, Φ) be an n-agent Boolean
dl-game with N = {1, . . . , n}. Then, a strategy profile I = (I1 , . . . , In ) is a (pure) Nash
equilibrium of G iff ui (I C Ii0 ) 6 ui (I) for every strategy Ii0 of agent i and for every
agent i ∈ 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 n-
agent Boolean dl-game with N = {1, . . . , n}. Then, a strategy profile I = (I1 , . . . , In )
is Pareto-optimal iff there exists no strategy profile I 0 such that (i) ui (I 0 ) > ui (I) for
some agent i ∈ N and (ii) ui (I 0 ) > ui (I) for every agent i ∈ 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 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 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
(1) a description logic knowledge base L,
(2) a finite set of n agents N = {1, 2, . . . , n}, n > 2,
(3) a finite set of atomic concepts A,
(4) a control assignment π : N → 2V , which associates with every agent i ∈ N a set of
atomic concepts π(i) ⊆ A, which she controls,
(5) a strict goal assignment Σ : N → LA , which associates with every agent i ∈ N
a concept Σ(i) ∈ LA that is satisfiable under L, denoted the strict goal of i, and
(6) a weighted goal assignment Φ, which associates with every agent i ∈ N a map-
ping Φi from a finite set of conceptsP Li that are satisfiable under L (denoted the
weighted goals of i) to <+ such that φ∈Li Φi (φ) = 1.
We give an example of a Boolean dl-game with weighted goals.
10 T. Lukasiewicz and A. Ragone
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 ≡ ∃hasActivity.ThemePark;
SS ≡ ∃hasActivity.Sightseeing;
HK ≡ ∃hasActivity.Hiking.
(4) Agents 1 and 2 control the following concepts π(1) and π(2), respectively:
π(1) = {U, R, BHD, SS, HK};
π(2) = {BA, H, BB, NP, C, TP}.
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. Infor-
mally, agent 1 also wants a budget hotel destination, while agent 2 wants to include
in the travel package that she is trying to sell 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 (∃hasDestination.(Capital t RuralArea)u
∃hasActivity.(Sport u ThemePark)) = 0.4;
Φ2 (∃hasDestination.RuralArea u ∃hasActivity.Sightseeing) = 0.3;
Φ2 (FamilyDestination u ∃hasActivity.ThemePark) = 0.3;
Φ2 (RelaxDestination u ∃hasActivity.Hiking) = 0.4.
Informally, agent 1 would like either (a) a family destination, or (b) a relax destina-
tion, 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 strat-
egy 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.
Combining Boolean Games with the Power of Ontologies 11
BA u H u ¬BB u BA u H u ¬BB u BA u H u ¬BB u BA u H u ¬BB u
NP u ¬C u TP ¬NP u C u TP NP u ¬C u ¬TP ¬NP u C u ¬TP
U u ¬R u BHD u
(−1, −1) (0.7, 0.3) (−1, −1) (0.4, 0)
SS u HK
¬U u R u BHD u
(1, 1) (−1, −1) (0.7, 0.7) (−1, −1)
SS u HK
U u ¬R u BHD u
(−1, −1) (0.4, 0) (−1, −1) (0, 0)
SS u ¬HK
¬U u R u BHD u
(0.7, 0.3) (−1, −1) (0.3, 0.3) (−1, −1)
SS u ¬HK
U u ¬R u BHD u
(−1, −1) (0.4, 0) (−1, −1) (0.4, 0)
¬SS u HK
¬U u R u BHD u
(0.4, 0) (−1, −1) (0.4, 0) (−1, −1)
¬SS u HK
Fig. 4. Normal form of a two-agent Boolean dl-game with weighted generalized goals.
Definition 4.2 (utilities with weighted goals). Let G = (L, N, A, π, Φ, Σ) be an n-
agent Boolean dl-game with weighted goals. Then, the utility to agent i ∈ N under I,
denoted ui (I), is defined as follows:
(
−1 if I is inconsistent, or I 6|=L Σ(i);
ui (I) =
Σφ∈Li , I|=L φ Φi (φ) if I is consistent, I |= L, and I |=L Σ(i).
We give an example to illustrate the utilities in the case of weighted goals.
Example 4.2 (travel negotiation cont’d). The normal form representation of the two-
agent 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 Controlling Roles
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 instan-
tiation 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 con-
ditions 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 = {1, 2}. The roles π(1) and π(2) controlled
by agents 1 and 2, respectively, are given as follows:
π(1) = {delivery, hasQuality};
π(2) = {hasType}.
12 T. Lukasiewicz and A. Ragone
EU v WorldWide;
US v WorldWide;
Contract1 v Contract;
Contract2 v Contract;
Contract1 v ¬Contract2;
Cash v PaymentType;
Instalments v PaymentType;
HighQualityService v ∃assistance u ∀assistance.Onsite u =2 year guarantee;
LowQualityService v ∃assistance u ∀assistance.Phone u =1 year guarantee;
Contract1 ≡ ∃payment u ∀payment.Instalments u ∃delivery u ∀delivery.(US u EU);
Contract2 ≡ ∃payment u ∀payment.Cash u ∃delivery u ∀delivery.WorldWide.
Fig. 5. Service ontology.
C1 C2
HQ u WW (−1, −1) (0, 1)
HQ u SE (1, 0) (0, 1)
Fig. 6. Normal form of a two-agent Boolean dl-game with controlled roles.
Agents 1 and 2 have the following goals Φ(1) and Φ(2), respectively (for ease of pre-
sentation, we omit strict and weighted goals here):
Φ(1) = ∃payment u ∀payment.Instalments;
Φ(2) = (∃hasQuality u ∀hasQuality.LowQualityService u
∃hasType u ∀hasType.Contract1) t
(∃hasQuality u ∀hasQuality.HighQualityService u
∃hasType u ∀hasType.Contract2).
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 ≡ ∃hasType u ∀hasType.Contract1;
C2 ≡ ∃hasType u ∀hasType.Contract2;
HQ ≡ ∃hasQuality u ∀hasQuality.HighQualityService;
WW ≡ ∃delivery u ∀delivery.WorldWide;
SE ≡ ∃delivery u ∀delivery.(US u EU).
Notice that in this approach agents do not have to enumerate all the possible combina-
tions 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 exhaus-
tive 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.
Combining Boolean Games with the Power of Ontologies 13
6 Related Work
A large number of negotiation mechanisms have been proposed and studied in the litera-
ture. It is possible to distinguish, among others, game-theoretic ones [10,11], heuristic-
based 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 combina-
tions 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 differ-
ences. 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 communi-
cation rounds in order to exchange information, while our approach is a one-shot nego-
tiation, which ensures the termination after only one round; indeed in argumentation-
based 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 classifica-
tion, namely, weights over unrestricted formulas. Zhang and Zhang [19] adopt a kind
of propositional knowledge base arbitration to choose a fair negotiation outcome. How-
ever, 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 bur-
den to reach an agreement to the agents themselves, although they can follow a proto-
col. 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
14 T. Lukasiewicz and A. Ragone
inexpressive description logic, ALEH(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 pro-
vide 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 util-
ities 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 negoti-
ation 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
Towards automated multi-attribute negotiation in the Semantic Web, we have intro-
duce 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 im-
portant 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 sce-
narios. 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 opti-
mal 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.
References
1. Jennings, N.R., Faratin, P., Lomuscio, A.R., Parsons, S., Wooldridge, M., Sierra, C.: Auto-
mated negotiation: Prospects, methods and challenges. Group Decision and Negotiation 10
(2001) 199–215
Combining Boolean Games with the Power of Ontologies 15
2. Berners-Lee, T.: Weaving the Web. Harper, San Francisco, CA (1999)
3. Fensel, D., Wahlster, W., Lieberman, H., Hendler, J., eds.: Spinning the Semantic Web:
Bringing the World Wide Web to Its Full Potential. MIT Press (2002)
4. Hendler, J.A.: Where are all the intelligent agents? IEEE Intelligent Systems 22(3) (2007)
2–3
5. Horrocks, I., Patel-Schneider, P.F.: Reducing OWL entailment to description logic satisfia-
bility. In: Proc. ISWC-2003. Volume 2870 of LNCS, Springer (2003) 17–29
6. Horrocks, I., Sattler, U., Tobies, S.: Practical reasoning for expressive description logics. In:
Proc. LPAR-1999. Volume 1705 of LNCS, Springer (1999) 161–180
7. Bonzon, E., Lagasquie-Schiex, M.C., Lang, J., Zanuttini, B.: Compact preference represen-
tation and Boolean games. Autonomous Agents and Multi-Agent Systems (2008) In press.
8. Harrenstein, P., van der Hoek, W., Meyer, J.J.C., Witteveen, C.: Boolean games. In: Proc.
TARK-2001, Morgan Kaufmann (2001) 287–298
9. Harrenstein, P.: Logic in Conflict. PhD thesis, Utrecht University, The Netherlands (2004)
10. Kraus, S.: Strategic Negotiation in Multiagent Environments. MIT Press (2001)
11. Rosenschein, J.S., Zlotkin, G.: Rules of Encounter. MIT Press (1994)
12. Fatima, S., Wooldridge, M., Jennings, N.R.: Optimal agendas for multi-issue negotiation.
In: Proc. AAMAS-2003, ACM Press (2003) 129–136
13. Faratin, P., Sierra, C., Jennings, N.R.: Using similarity criteria to make issue trade-offs in
automated negotiations. Artificial Intelligence 142(2) (2002) 205–237
14. Rahwan, I., Ramchurn, S.D., Jennings, N.R., McBurney, P., Parsons, S.: Argumentation-
based negotiation. The Knowledge Engineering Review 18(4) (2003) 343–375
15. Sadri, F., Toni, F., Torroni, P.: Dialogues for negotiation: Agent varieties and dialogue se-
quences. In: Intelligent Agents VIII. Volume 2333 of LNCS, Springer (2002) 405–421
16. Bentahar, J., Moulin, B., Meyer, J.J.C., Chaib-draa, B.: A modal semantics for an
argumentation-based pragmatics for agent communication. In: Argumentation in Multi-
Agent Systems. Volume 3366 of LNCS, Springer (2005) 44–63
17. Bouveret, S., Lemaitre, M., Fargier, H., Lang, J.: Allocation of indivisible goods: A general
model and some complexity results. In: Proc. AAMAS-2005, ACM Press (2005) 1309–1310
18. Chevaleyre, Y., Endriss, U., Lang, J.: Expressive power of weighted propositional formulas
for cardinal preference modeling. In: Proc. KR-2006, AAAI Press (2006) 145–152
19. Zhang, D., Zhang, Y.: A computational model of logic-based negotiation. In: Proc. AAAI-
2006, AAAI Press (2006) 728–733
20. Wooldridge, M., Parsons, S.: Languages for negotiation. In: Proc. ECAI-2000, IOS Press
(2000) 393–400
21. Ragone, A., Di Noia, T., Di Sciascio, E., Donini, F.M.: A logic-based framework to compute
Pareto agreements in one-shot bilateral negotiation. In: Proc. ECAI-2006, IOS Press (2006)
230–234
22. Ragone, A., Di Noia, T., Di Sciascio, E., Donini, F.M.: Logic-based automated multi-issue
bilateral negotiation in peer-to-peer e-marketplaces. Autonomous Agents and Multi-Agent
Systems 16(3) (2008) 249–270
23. Ragone, A., Di Noia, T., Di Sciascio, E., Donini, F.M.: Alternating-offers protocol for multi-
issue bilateral negotiation in semantic-enabled marketplaces. In: Proc. ISWC-2007. Volume
4825 of LNCS. Springer (2007) 395–408
24. Ragone, A., Di Noia, T., Di Sciascio, E., Donini, F.M.: Description logics for multi-issue
bilateral negotiation with incomplete information. In: Proc. AAAI-2007, AAAI Press (2007)
477–482
25. Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H., Poole, D.: CP-nets: A tool for
representing and reasoning with conditional ceteris paribus preference statements. J. Artif.
Intell. Res. 21 (2004) 135–191
26. Sandholm, T.: Computing in mechanism design. In: New Palgrave Dictionary of Economics.
(2008)