We introduce a framework based on Description Logics, which can be used to encode and solve decision problems in terms of combining inference services in DL and utility theory to represent preferences of the agent. The novelty of the approach is that we consider ABoxes as alternatives and weighted concept and role assertions as preferences in terms of possible outcomes. We discuss a relevant use case to show the bene ts of the approach from the decision theory point of view.
Preference representation is an ongoing research subject in arti cial intelligence,
gaining more popularity every day. Since the rst attention of multi-attribute
utility theory in [
Description Logics (DL) is a family of logic languages which is mainly based on decidable fragments of rst order logic. It has been designed to be used as a formalism in the eld of knowledge representation, and it has become one of the major approaches over the last decade. In the context of the Semantic Web, it embodies a theoretical foundation for the OWL Web Ontology Language, a standard de ned by the World Wide Web Consortium.
In this paper we introduce a Description Logic framework, which can be used to encode and solve decision problems in terms of combining inference services in Description Logics and utility theory to represent preferences of the decision maker. Within our approach we consider ABoxes as alternatives and weighted concept and role assertions as preferences in terms of possible outcomes. We discuss some relevant cases and restrictions about our framework.
The framework that we propose in this paper works with classical-DLs, and
it can be applied to decision making scenarios where uncertainty is not involved
e.g,. transportation model, or the theory of consumer choice [
In our work, we have not speci ed any speci c language of DL, since the core idea is regardless of the chosen language. Therefore, we used the basic DL language ALC to introduce our framework. However, for convenience, we have used the DL language with concrete domains in the example section (Section 3.3), since numerical domains are typically used in Decision Theory.
In the remainder of the paper, we rst brie y present preliminaries in utility theory and DL in Section 2. Then, we introduce our framework and discuss an example (Section 3). In the example, an agent (car buyer) is giving a decision between two alternatives (two cars), according to her criteria. In Section 4, we discuss the related works. Finally, we conclude and give a brief outline for future research in Section 5. 2
In this section, rst we will give a basic introduction to preferences and utility theory. Then we brie y inform the reader about our notation for DL. 2.1
In prescriptive decision theory [
It is said that, a is weakly preferred 1 (strictly preferred ) to b whenever a (a b), a is indi erent to b whenever a b. b
In order to represent the preference relation numerically, one introduces the term utility, which is is a function that maps a choice from the choice set to a positive real number re ecting the degree of usefulness. From now on, we will consider only the case which X is nite.
De nition 2 (Utility Function). Given a nite choice set X = fx1; : : : ; xng, and preference on X. Then u : X ! R is a utility function if for any xi, xj 2 X with i; j n, the following holds: xi xi xi xj () u(xi) > u(xj ) , xj () u(xi) u(xj ) , xj () u(xi) = u(xj ) .
For the proof of such a function exist, we refer the reader to the so-called
representation theorems in [
The basic principle in utility theory is that a rational agent should always try to maximize its utility, or should take the choice with the highest utility. Note that the decisions in real world are far more complex than requiring to consider just a single criteria (e.g. unary utility functions). Multi-attribute utility functions is an approach to deal with such decision problems.
De nition 3 (Multiattribute Utility Function). Let X = X1 : : : Xn be the set of multiple attributes over which the decision maker has preferences where n 2 . Let be the preference relation de ned on X, then u is a multiattribute utility function representing if and only if 8(x1; : : : ; xn); (y1; : : : ; yn) 2 X, (x1; : : : ; xn) (y1; : : : ; yn) () u(x1; : : : ; xn) u(y1; : : : ; yn) : (1) 2.2
It is assumed that the reader has some familiarity with DL. If that is not the
case, we refer the interested reader to [
The signature of the DL language we use, is (NC ; NR; NI ), where NC is the set of atomic concepts, NR is the set of role names, and NI is the set of individuals. Along the text, we assume the unique name assumption, which means that di erent individuals have di erent names. We denote concepts by 1 It is also called preference-indi erence relation, since it is the union of strict preference and indi erence relation.
C and D, roles by R and S, and individuals as a and b. Concept descriptions are de ned inductively by NC , :C, C u D, and C t D if C and D are concept descriptions, and 9R:C and 8R:C if R 2 NR and C is a concept description. The top concept > is abbreviation for C t :C and the bottom concept ? is for :>. An interpretation is a pair I = ( I ; I ) where the domain I is a non-empty set and I is interpretation function that assigns to every concept name C a set CI I and to every role name R a binary relation RI I I . It is de ned inductively for every concept description as follows; (:C)I = I n CI , (C u D)I = CI \ DI , (C t D)I = CI [ DI , (9R:C)I = fa 2 I j 9b:(a; b) 2 RI ^ b 2 CI g, and (8R:C)I = fa 2 I j 8b:(a; b) 2 RI =) b 2 CI g. Any other extension is de ned accordingly, and will be clari ed when it is necessary.
In Description Logics, there is a distinction between terminological knowledge (TBox) and assertional knowledge (Abox). TBox is a set of concept inclusion axioms: C v D where the interpretation is CI DI . C D if C v D and C v D. ABox is a set of concept assertions C(a) where a 2 NI and C(a)I = aI 2 CI , and role assertions R(a; b) where (a; b) 2 NI NI and R(a; b)I = (aI ; bI ) 2 RI .
A concept is satis able if there is an interpretation I such that CI 6= ;. A concept is satis able with respect to T if and only if there is a model I of T such that CI 6= ;. A concept inclusion C v D is said to be satis able if and only if there is an I which respects CI DI (i.e. I j= C v D). A concept C is subsumed by a concept D with respect to T if CI DI for every model of I of T (i.e. C vT D or T j= C v D). If T is a set of axioms, then I is a model of T if and only if I satis es every element of T . Such a TBox is called coherent. We say that an assertion is entailed by ABox A (i.e. A j= ) if every model of A also satis es . One basic reasoning service we will use is instance check ; to check for a given ABox A and , weather A j= holds. An ABox A is consistent w.r.t. a TBox T if there is a model of both T and A. We call the pair K = hT ; Ai a knowledge base, and also say that K is satis able if A is consistent w.r.t. T .
A concrete domain D is a pair ( D; pred(D)) where D is the domain of D
and pred(D) is the set of predicate names of D. It is assumed that I \ D = ;,
and each P 2 pred(D) which is of arity n, is associated with P D ( D)n. We
will denote functional roles with lower case r. In DL with concrete domains, it
is assumed that NR is partitioned into a set of functional roles and the set of
ordinary roles. A role r is functional if for every (x; y) 2 r and (w; z) 2 r it
implies that x = w =) y = z. Functional roles, in the extended language,
is interpreted as partial functions from I to I D. Functional roles and
ordinary roles are both allowed to be used with both the existential quanti cation
and the universal quanti cation. Concrete domain is required to be closed under
negation (denoted by P ), in order to be able to compute the negation normal
form of the concepts de ned via extended constructs. For more information
about DL, we refer the interested reader to [
We consider a decision problem (in the terminology of decision theory) from the
agent perspective: in the light of background knowledge and preferences which
alternative should be chosen? We should note that, in this paper we do not
concern ourselves with problems regarding elicitation or uncertainty. In this regard,
we assume that agents preferences are elicited and there is no uncertainty. This
is usually the case for decision making in the domain of consumer choice theory,
([
We represent the background knowledge of the agent by the DL knowledge base K, which includes the concept hierarchy T and known assertions about individuals which are represented in A. The choice set C represents a priori alternatives which utilities yet are unknown by the agent. U is the set of criteria or outcomes where each element consists of an assertion ai and a value ui assigned to this assertion with the condition that every ai has a unique ui. We will use the terms criteria, attributes and outcomes interchangeably.
De nition 4 (Decision Base). A decision base, D = (K; C; U ) is a triple with; { K = (T ; A) is a description logic knowledge base (background knowledge) in which T is an acyclic TBox and A is an ABox, { C = fC1; : : : ; Cng is a choice box, a non-empty nite set of choices, each being an ABox, { U = fha1; u1i; : : : ; ham; umig is a utility box (UBox), a nite set of utility assertions, in which ai being an assertion and ui 2 R is the assigned basic utility value for ai, with the restriction ai T aj =) ui = uj .
Note that U can be inconsistent in terms of arbitrary unions of ais with regard to K. Another way to look at it, is to think of it as a (possibly inconsistent) union of ABoxes. One can think of a utility assertion as an outcome, or an instantiation of an attribute, and the value ui is the corresponding basic (uninferred) utility value for that outcome. This gives us the exibility to model a decision problem in various ways in terms of preferences.
The rst way is, if one interprets a concept name in UBox, as a single
attribute then the preference is de ned just as they were de ned in parallel to
the standard multi attribute utility theory [
Another obvious way to model preferences in a decision problem is to regard a concept name in UBox as a criteria or property (possibly de ned or interrelated to other concepts via background knowledge K), e.g. GourmetT rip(trip1), EconomicT rip(trip2). The utility of a choice is de ned straightforward. De nition 5 (Utility). The utility U of a choice C w.r.t D = (K; C; U ) is, U (C) =
fha;ui2UjK[Cj=agu where C 2 C and K [ C is consistent.
From the de nition above, it follows that the utility of an inconsistent alternative (with respect to the knowledge base) is unde ned. Thus we restrict ourselves to assess only the consistent decisions. This naturally provides a service to eliminate alternatives which can cause inconsistencies. Note that one could also de ne utilities for inconsistent decisions simply by extending the de nition, e.g., assigning zero, however, this causes an inconsistent decision and a possible zero-utility choice to be regarded indi erently in terms of utility score, if no restriction on U is applied, e.g., ui 1. As the consistency of a decision with respect to background knowledge or a previously taken decision is critical to a decision maker, so it is for a decision support system. In case of logical languages, hence of DLbased ontologies, consistency checking is a standard reasoning service. A decision support system based on this framework, whose choices are given, could easily help the decision maker in cases it is hard to see the logical implications and possible inconsistencies.
Notice that calculating the utility of a choice, can be thought of as answering a series of instance checking inferences i.e. K [ Ci j=? a1; K [ Ci j=? a2; : : : ; K [ Ci j=? ajUj and collecting positive answers. Now, given the decision base and the utility of a choice Ci, one can de ne a decision problem. A typical form of the decision problem would be nding the best decision expressed as choosing the choice with the maximum utility:
Cmax = arg mCaxfU (C) j C 2 Cg This can be generalized in terms of picking up the best n-choices together.
Cmnax = arg
max (C1;:::;Cn)
n fU ( [ Ci) j C1; : : : ; Cn 2 C and n i=1 jCjg Or it can be logically restricted to a level that the decision maker can pick up at most one choice (mutually exclusive), with the following de nition. De nition 6 (Mutual Exclusion). A decision base D = (K; C; U ) is mutually exclusive if for every Ci; Cj 2 C with i 6= j, Ci [ Cj [ K is inconsistent. (2) (3) In general, in order to model the concerned type of a decision problem, one can bring some restrictions on C and U .
Proposition 1. The utility function U induces a rational preference relation. Proof. Since the codomain of U is R+, is a complete quasiorder (complete and transitive). For any two consistent (w.r.t K) choices C1 and C2, set C1 C2 if U (C1) U (C2), and set C1 C2 if C1 C2 and C2 C1. 3.2
Since utility functions represent preferences, it is well-known that certain classes
of utility functions correspond to certain type of preferences. In this section, we
will discuss some of the expressivity of D (de ned in De nition 5) in terms of the
utility functions. Following [
De nition 5), and C1; C2; C3 are pairwise consistent ABoxes. Then, 1. U is non-negative i U (C) 0 for all C. 2. U is monotonic i U (C1) U (C2) whenever C1 3. U is subadditive i U (C1 [ C2) U (C1) + U (C2)
and C2. 4. U is superadditive i U (C1 [ C2)
and C2. 5. U is concave i U (C1 [ C2) U (C2)
whenever C3 C2. 6. U is convex i U (C1 [C2) U (C2)
C3 C2. 7. U is modular i U (C1 [ C2) = U (C1) + U (C2)
C2.
U (C1) + U (C2)
Monotonicity means, more of a good (or choice) is better. Concavity means
that if we move (from C3) to a better position (or the choice C2), the marginal
utility (of the choice C1) decreases. This describes the behaviour of risk-averse
agents. The opposite occurs when the function is convex; exposing a risk-seeking
behaviour. Modularity is the intersection of both classes. From the informal
argument in [
Proposition 2. Let U be a utility function, then: (1) if U is concave, then it is subadditive, (2) if U is convex, then it is superadditive.
Proof. Set C3 as C1 \ C2.
U (C1 [ C3)
U (C3) for all C1 U (C1 [C3) U (C3) for all C1 whenever
U (C1 \ C2) for all C1 and
C2.
U (C1 \ C2) for all C1 U (C1 \ C2) for all C1 tu The following negative result will help us to discuss the expressive power of U w.r.t. D.
Theorem 1. U is (1) not non-negative, (2) not monotonic, (3) not subadditive, (4) not superadditive, (5) not concave, (6) not convex, (7) not modular w.r.t. some D.
Proof. (1) follows from De nition 4 and De nition 5 by setting basic utilities as negative reals. (2) follows from (1). To prove (3), set K = ;, C1 = fD(a)g, C2 = fE(a)g and U = fhD(a); 10i; hE(a); 10i h(D uE)(a); 100ig. (4) follows from setting K = ;, C3 6= ;, C3 C2 C1, and UBox U as the non-negative assertions of C1. (5) follows from the contrapositive of Proposition 2- 1. (6) follows from the contrapositive of Proposition 2-2. (7) follows from both (5) and also (6). tu
Observe that Theorem 1 follows from the expressive power and therefore the exibility of U (w.r.t D). Therefore, with adequate restrictions on D (in particular UBox U ), one might change U into one of the aforementioned class (in De nition 7). For instance de ning basic utilities non-negative (ui 2 R+) would guarantee the non-negativity (trivially), and monotonicity (since j= is also monotone). Observe that in U one can express complement attributes (as in the proof of Theorem 1.3 that is, the utility of having both criteria is greater than sum of each (e.g. Hotel reservation and Plane ticket of a holiday). Similarly one can express substitute attributes e.g., assigning a negative value to having both attribute. Not allowing complementary attributes and setting U non-negative would guarantee modularity. Certainly, investigations over such restrictions and their interrelations need a closer inspection, which we plan to do in future work. 3.3
Consider an agent who wants to buy a second hand sports car. After visiting various car dealers, he nds two alternatives as fair deals; a sport Mazda (Mx-5 Miata Roadster, 2013 ) which ts his original purpose and a BMW (335i Sedan, 2008 ) which is also worth considering since it has a very strong engine (300 horsepower (hp)) and also comes with a sport kit. The car buyer's decision base (background knowledge (T ; ;), choices C, and criteria U ) is as in Figure1.
As the use of numerical domains is common to classical Decision Theory, we will use the language with concrete domains. If the reader is already familiar with concrete domains, she can skip the technical de nitions and move directly to Figure 1.
Let us clarify concrete domains and predicates which are used in the example. We take the concrete domain Car and Car = $ [ sec [ mpg [ mph [ hp with $ \ sec \ mpg \ mph \ hp = ;, and pred(Car) = pred($)[pred(mpg)[ pred(mph) [ pred(sec). We de ne the partition (of the domain Car) $ as a denumerable set fi$g where i 2 N, pred($) = f<$; >$; $; $; =$; 6=$g. (<$ )$(x; y) = f(x; y) 2 $ $ j i; j 2 N with i$ = x and j$ = y such that i < jg.
Other predicates are de ned similarly in an obvious way parallel to usual binary relations over N. For convenience, we extend pred($) with nitely many unary predicates in the form of <x= f8y 2 $ j<$ (x; y)g and also of >x, x, x, =x, 6=x which are similarly de ned, enough to express the intended TBox. Note that pred($) is closed under negation: <$(x; y) = $ (x; y), etc. For other partitions, we take sec = fi sec j i 2 R+ f0gg, mpg = fi mpg j i 2 Ng, mph = fi mph j i 2 Ng, hp = fi hp j i 2 N f0gg. The rest of the respective predicate names and functional roles are de ned in an obvious way (hasP riceI : I $, hasKit : I I , etc).
According to the agent, taking T into account, a Bmw is a prestigious car. Considering a 200 hp or above is enough to refer to a car as strong. An economic car should go for more than 20 miles per gallon (mpg ). A car is young if it was manufactured in 2012 or later.
Considering U in Figure1, the agent (car buyer) is more interested in having a prestigious car than having an inexpensive car. He prefers convertible to sedan. However, these are not as important as a car to be an economic car, or a strong car. Using the given decision base, we can calculate the utility of each choice (U (C1) = 220, U (C2) = 170), which implies (by the assumption: the higher the utility, the more desirable is the choice) that C1 C2.
The example of the decision problem given above is (intrinsically) mutually exclusive since it was obvious that we were deciding between two choices (buying just one car). Therefore we used a unique individual car instead of car1, car2. Mutual exclusion is implied (e.g., by Bmw u M azda v ?). Consider the case where there is an assertion in a particular choice or an expansion of it which is not implied by any utility assertion. For instance, assume that in the car buyer example, C1 has hasColour(car; red). This might be quite important for the decision maker. However, as this outcome is not included in U , it will not be re ected in the evaluation of the utility for C1. In this case, the utility function, which is implicitly de ned for the choice C, does not really capture the implications of C. That means preferences are not comprehensive enough in terms of having all the necessary outcome information. This in turn diminishes the quality of accuracy in evaluating the utility of a decision (perhaps in trade-o regarding to ease the storage of preference and save of computational resources). By a comprehensive preference with respect to a choice, we understand a preference structure which captures (having a value assigned) all of its logical implications.
(faig) in U , and clT (C) = fx j C [ T j= xg be the closure of a choice C (w.r.t T ). Then U is called comprehensive w.r.t. C i clT (C) U 0.
Comprehensiveness is also an important property that should be taken into account for a possible interest of automated generation of UBoxes.
Note that one can extend the present framework in terms of considering not only the choices but also an extra available information prior to giving a decision. This case is especially relevant when the agent is considered to have an incomplete background knowledge. The extra information can encoded in terms of an axiom or assertion. This allows us to evaluate the value of information in terms of its utility, with respect to a choice. Informally, the value of information w.r.t. a choice C is the di erence between the utility of C with the extra information and without. We will consider the axiom case.
De nition 9 (Value of Information). Let D = ((T ; A); C; U ) be a decision base and D0 = ((T [T ; A); C; U ) be the decision base extended with the additional information T . Then, the value of information with respect to a choice C and decision base D is U (T ) = UD0 (C) UD(C), whenever T [ T [ C is consistent.
For instance, assume that in car buyer example, our agent does not know what a roadster car really is (which means we assume that the TBox in Figure1 does not include the axiom SportsCar u Convertible Roadster), even though he knows that a roadster is prestigious. Without that information the Mazda does not become a prestigious car in all models of T . That means the utility of C1 can not get extra 55 utility score for being a P restigiousCar. Thus the value of the regarded information is 55 for C1 whereas it is 0 for C2. 4
Preference representation using logical languages has become popular over the
last decade. Many of these approaches are based on propositional logic [
In [
In [
We have introduced a framework based on knowledge representation formalism DL, for it can be applied to solve decision problems, i.e., multi-attribute discrete alternatives. Using our formalism, we have also de ned formally some concepts such as mutually exclusive choices, comprehensiveness ,value of information which is promising for future directions. One aim is to make a closer investigation on expressive power of D.
As the major part of the utility theory literature is concerned with
uncertainty, one major future research direction is to extend the framework with
probabilistic description logics, e.g., [
A second major research direction is to extend the framework to sequential decisions (e.g. Di ! Di+1, sequence of decision bases). Once sequential decisions are de ned, one can represent policies, strategies and de ne a planner.
It can be extended to represent collaborative decision making scenarios as well as game theoretical set-ups by considering more than one agent and specifying restrictions between their choice sets and knowledge bases. As an example, in an arbitrary set-up, rules of the game could be a subset of intersection of both agent's knowledge bases, then the knowledge bases would get extended according to each players choices if each player can see what others choose. It can be checked whether a game-theoretical condition is satis ed, in terms of ontologies.
Currently, we are working on the implementation of the basic framework as a Protege2 plug-in. Our plugin is planned to consist, rst of all, of an editor for the de nition of UBoxes and choices, while the background knowledge is loaded via the standard interfaces of Protege. Our extension will then be able to compute the utility of the given choices in order to display a ranking. The development of our Protege plugin is motivated by the idea to demonstrate the bene ts of our approach to a set of di erent application scenarios. 2 http://protege.stanford.edu/