Leila Amgoud

Yannis Dimopoulos

Pavlos Moraitis

Making decisions through preference-based argumentation

Decision making is usually based on the comparative evaluation of different alternatives by means of a decision criterion. The whole decision process is compacted into a criterion formula on the basis of which alternatives are compared. It is thus, impossible for an end user to understand why an alternative is good, or better than another. Recently, some decision criteria were articulated in terms of a two-steps argumentation process: i) an inference step in which arguments in favor/against each option are built and evaluated, and ii) a comparison step in which pairs of alternatives are compared on the basis of "accepted" arguments. Thus, not only the best alternative is provided to the user but also the reasons justifying this recommendation. However, a two steps approach is not in accordance with the principle of an argumentation system, whose accepted arguments are intended to support the "good" options. Moreover, with such an approach it is difficult to define proof procedures for testing directly whether a given option may be the best one without computing the whole ordering. Finally, it is difficult to analyze how an ordering is revised in light of a new argument. This paper proposes a novel approach for argumentationbased decision making. We propose a Dung style system that takes as input different arguments and a defeat relation among them, and returns as outputs a status for each option, and a total preordering on a set of options. The status is defined on the basis of different inference mechanisms. The total preordering privileges the option that is supported by the strongest argument, provided that this argument survives to the attacks. The properties of the system are investigated.

Introduction

Decision making relies on the comparative evaluation of different options or alternatives on the basis of a decision criterion, which can be usually justified by means of a set of postulates. This is, for example, the Savage view of decision under uncertainty based on expected utility. Thus, standard approaches for decision making consist in defining decision criteria in terms of analytical expressions that summarize the whole decision process. It is then hard for a person who is not familiar with the abstract decision methodology, to understand why a proposed alternative is good, or better than another. It is thus important to have an approach in which one can better understand the underpinnings of the evaluation. Argumentation is the most appropriate way to advocate a choice thanks to its explanatory power.

Argumentation has been introduced in decision making analysis by several researchers only in the last few years (e.g. [START_REF] Bonet | Arguing for decisions: A qualitative model of decision making[END_REF][START_REF] Fox | On using arguments for reasoning about actions and values[END_REF][START_REF] Gordon | The Zeno Argumentation Framework[END_REF][START_REF] Dimopoulos | Argumentation based modeling of decision aiding for autonomous agents[END_REF][START_REF] Amgoud | A general argumentation framework for inference and decision making[END_REF]). Indeed, in everyday life, decision is often based on arguments and counter-arguments. Argumentation can be also useful for explaining a choice already made.

Recently, in [START_REF] Amgoud | A general argumentation framework for inference and decision making[END_REF]), a decision model in which some decision criteria were articulated in terms of a twosteps argumentation process has been proposed. At the first step, called inference step, the model uses a Dung style system in which arguments in favor/against each option are built, then evaluated using a given acceptability semantics. At the second step, called comparison step, pairs of alternatives are compared using a given criterion. This criterion is generally based on the "accepted" arguments computed at the inference step. The model returns thus, an ordering on the set of options, which may be either partial or total depending on the decision criterion that is encoded. This approach presents a great advantage since not only the best alternative is provided to the user but also the reasons justifying this recommendation.

However, a two steps approach is not in accordance with the principle of an argumentation system, whose accepted arguments are intended to support the "good" conclusions (i.e. the best options in a decision making problem). Indeed, in the above approach, the first step is unfortunately not sufficient to rank-order the options. Consequently, it is difficult to define proof procedures for testing directly whether a given option is the best one without having to compute the whole ordering. The reason is that such a proof procedure will make use of both steps. Finally, it is difficult to analyze how an ordering is revised in light of a new argument.

This paper proposes a novel approach for argumentationbased decision making. We propose a Dung style system that rank-orders the different options in one step. The system takes as input a set of epistemic arguments (supporting beliefs), a set of practical arguments (supporting options), an attack relation among these arguments, and a preference relation between arguments, and returns: i) a status for each option, and ii) a total preorder on the set of options. The status of an option is defined using well-known inference mechanisms. These later are defined in the literature for inferring conclusions from different sets of formulas. We show that such mechanisms can be adapted to the argumentation setting, and provide a good basis for defining the ordering on options. The properties of the system are investigated, and the characteristics of the best "option" are given. Namely, we show that our model privileges the option that is supported by the strongest practical argument provided that this argument is not undermined by epistemic arguments. With such an approach, it is possible to use the proof procedures defined in argumentation theory for testing whether a given option is the "best". This amounts to test whether its argument is skeptically accepted under a given semantics.

The paper is organized in the following way. The first section presents the different types of arguments that are involved in a decision making problem. Then, we detail the different attack relations that may exist between these arguments. The next section presents the decision system as well as its extensions. Then, the different status of options are defined and the total preordering is provided. The model is then illustrated on a real-world example. Finally, we conclude with some remarks and perspectives.

The arguments

Solving a decision problem amounts to defining a preordering, usually a complete one, on a set of possible options, on the basis of the different consequences of each decision. Let us illustrate this problem through a simple example borrowed from [START_REF] Fox | On using arguments for reasoning about actions and values[END_REF].

Example 1 (Having or not a surgery)

The example is about having a surgery (sg) or not (¬sg), knowing that the patient has colonic polyps. The knowledge base is:

• not having surgery avoids having side-effects,

• when having a cancer, having a surgery avoids loss of life,

• the patient has colonic polyps, • having colonic polyps may lead to cancer.

In addition to the above knowledge, the patient has also some goals like: "no side effects" and "to not lose his life". Obviously it is more important for him to not lose his life than to not have side effects.

In what follows, L will denote a logical language. From L, a finite set O = {o 1 , . . . , o n } of n distinct options is identified. The options are assumed to be mutually exclusive, and an agent has to choose only one of them. Note that an option o i may be a conjunction of other options in O. Let us for instance assume that an agent wants a drink and has to choose between tea, milk or both. Thus, there are three options: o 1 : tea, o 2 : milk and o 3 : tea and milk. In Example 1, the set O contains only two options: sg and ¬sg.

Types of arguments

As shown in Example 1, decisions are made on the basis of available knowledge and the preferences of the de-cision maker. Thus, two categories of arguments are distinguished: i) epistemic arguments justifying beliefs and are themselves based only on beliefs, and ii) practical arguments justifying options and are built from both beliefs and preferences/goals.

Example 2 (Example 1 cont.) In this example, α = ["the patient has colonic polyps", and "having colonic polyps may lead to cancer"] is considered as an argument for believing that the patient may have cancer. This epistemic argument involves only beliefs. While δ 1 = ["the patient may have a cancer", "when having a cancer, having a surgery avoids loss of life"] is an argument for having a surgery. This is a practical argument since it supports the option "having a surgery". Note that such argument involves both beliefs and preferences. Similarly, δ 2 = ["not having surgery avoids having side-effects"] is a practical argument in favor of "not having a surgery".

In what follows, A e denotes a set of epistemic arguments, and A p denotes a set of practical arguments such that A e ∩ A p = ∅. Let A = A e ∪ A p (i.e. A will contain all those arguments). The structure and origin of the arguments are assumed to be unknown. Throughout the paper, we assume that arguments in A p highlight positive features of their conclusions, i.e. they are in favor of their conclusions. Epistemic arguments will be denoted by variables α 1 , α 2 , . . ., while practical arguments will be referred to by variables δ 1 , δ 2 , . . . When no distinction is necessary between arguments, we will use the variables a, b, c, . . .

Example 3 (Example 1 cont.)

A e = {α} while A p = {δ 1 , δ 2 }.
Let F be a function that returns for a given option, the arguments in favor of it. Thus, for o ∈ O, F(o) ⊆ A p . Each practical argument supports only one option. That is,

∀o, o ′ ∈ O with o = o ′ , it holds that F(o) ∩ F(o ′ ) = ∅.
When δ ∈ F(o), we say that o is the conclusion of δ, and we write Conc(δ) = o. We assume that A p = F(o i ) meaning that the available practical arguments concern options in O.

Comparing arguments

In argumentation literature, it has been acknowledged that arguments may not have equal strength. Some arguments may be stronger than others for different reasons. For instance, because they are built from more certain information. In our particular application, three preference relations between arguments are defined. The first one, denoted by ≥ e , is a partial preorder (i.e. a reflexive and transitive binary relation) on the set A e . The second relation, denoted by ≥ p , is a partial preorder on the set A p . Finally, a third relation, denoted by ≥ m (m stands for mixed relation), captures the idea that any epistemic argument is stronger than any practical argument. The role of epistemic arguments in a decision problem is to validate or to undermine the beliefs on which practical arguments are built. Indeed, decisions should be made under "certain" information. Thus, ∀α ∈ A e , ∀δ ∈ A p , (α, δ) ∈≥ m and (δ, α) / ∈≥ m . Note that (a, b) ∈≥ x , with x ∈ {e, p, m}, means that a is at least as good as b. At some places, we will also write a ≥ Example 4 (Example 1 cont.) ≥ e = {(α, α)} and ≥ m = {(α, δ 1 ), (α, δ 2 )}. Now, regarding ≥ p , one may assume that δ 1 is stronger than δ 2 since the goal satisfied by δ 1 (namely, not loss of life) is more important than the one satisfied by δ 2 (not having side effects). Thus, ≥ p = {(δ 1 , δ 1 ), (δ 2 , δ 2 ), (δ 1 , δ 2 )}.

Attacks among arguments

Generally arguments may be conflicting. These conflicts are captured by a binary relation on the set of arguments. In what follows, three such relations are distinguished:

• The first relation, denoted by R e , captures the different conflicts that may exist between epistemic arguments. It is assumed abstract and its origin is not specified. • Practical arguments may also be conflicting. These conflicts are captured by the binary relation R p ⊆ A p × A p . Indeed, since options are distinct and competitive (i.e. only one option will be chosen), arguments in favor of different options are assumed to be conflicting. However, arguments supporting the same offer are not since they are defending the same option. Finally, self-conflicting arguments are not allowed.

Rp = {(δ, δ ′ ) s.t. δ, δ ′ ∈ Ap, δ = δ ′ and Conc(δ) = Conc(δ ′ )}
This relation behaves in some sense in the same way as the "rebut" relation defined in (Elvang-Gøransson, [START_REF] Elvang-Gøransson | Dialectic reasoning with inconsistent information[END_REF], and which says that two arguments are conflicting with each other if they support different conclusions.

• Finally, practical arguments may be attacked by epistemic ones. The idea is that an epistemic argument may undermine the beliefs part of a practical argument. However, practical arguments are not allowed to attack epistemic ones. This avoids wishful thinking. This relation, denoted by R m , contains pairs (α, δ) where α ∈ A e and δ ∈ A p .

Property 1 The relation R p is symmetric and R m is asymmetric.

Example 5 (Example 1 cont.) Recall that A e = {α} and )

A p = {δ 1 , δ 2 }. R e = ∅, R m = ∅, while R p ={(δ 1 , δ 2 ), (δ 2 , δ 1 )}.
Def e = ∅, Def m = ∅, while Def p ={(δ 1 , δ 2 )}.
Another straightforward property says that arguments in favor of the same option are not defeating each others.

Property 3 Let o ∈ O. ∄δ 1 , δ 2 ∈ F(o) such that (δ 1 , δ 2 ) ∈ Def p .

Extensions of arguments

Now that the sets of arguments and the defeat relations are identified, we can define the decision system.

Definition 2 (Argument-based decision system) Let O be a set of options. A decision system1 for ordering O is a pair

AF = (A, Def) where A = A e ∪ A p and Def = Def e ∪ Def p ∪ Def m .
The decision system AF = (A, Def) can be seen as the union of two distinct argumentation systems: AF e = (A e , Def e ), called epistemic system, and AF p = (A p , Def p ), called practical system. The two systems are related to each other by the defeat relation Def m . It is important to notice that the epistemic system AF e is very general and does not necessarily present particular properties like for instance the existence of stable/preferred extensions.

Due to Dung's acceptability semantics defined in [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], it is possible to identify among all the conflicting arguments, which ones will be kept for ordering the options. An acceptability semantics amounts to define sets of arguments that satisfy a consistency requirement and must defend all their elements. Definition 3 (Conflict-free, Defence) Let (A, Def) be a decision system, B ⊆ A, and

a ∈ A. • B is conflict-free iff ∄ a, b ∈ B s.t. (a, b) ∈ Def. • B defends a iff ∀ b ∈ A, if (b, a) ∈ Def, then ∃ c ∈ B s.t. (c, b) ∈ Def.
The main semantics introduced by Dung are recalled in the following definition.

Definition 4 (Acceptability semantics) Let (A, Def) be a decision system, and B be a conflict-free set of arguments.

• B is admissible extension iff it defends any element in B.

• B is a preferred extension iff B is a maximal (w.r.t set ⊆) admissible set. • B is a stable extension iff it is a preferred extension that defeats any argument in A\B.

Using these acceptability semantics, the status of each argument can be defined as follows.

Definition 5 (Argument status) Let (A, Def) be an argumentation system, and E 1 , . . . , E x its extensions under a given semantics. Let a ∈ A.

• a is skeptically accepted

iff a ∈ E i , ∀E i=1,...,x , E i = ∅. • a is credulously accepted iff ∃E i such that a ∈ E i and ∃E j such that a / ∈ E j . • a is rejected iff ∄E i such that a ∈ E i .
Example 7 (Example 1 cont.) Recall that Def e = ∅, Def m = ∅, and Def p = {(δ 1 , δ 2 )}. Thus, the argumentation system (A, Def) has exactly one extension {α, δ 1 } that is both stable and preferred.

It is worth noticing that an extension may contain both epistemic and practical arguments. Moreover, it can be shown that any extension does not contain R p or R m conflicts, i.e. it does not contain a pair (a, b) of arguments such that (a, b) ∈ R p or (a, b) ∈ R m . In this case, we say that the extension is R x -conflict-free with x ∈ {p, m}.

Theorem 1 Any admissible extension of

(A, Def) is R x - conflict-free with x ∈ {p, m}.
A consequence of this result is that any admissible extension supports at most one option.

Corollary 1 Let E be an admissible extension of AF. If

E ∩ A p = ∅ then ∃o ∈ O s.t. ∀δ ∈ E ∩ A p , Conc(δ) = o.
In what follows, we will show that the result of the decision system depends broadly on the outcome of its epistemic system. The first result states that the epistemic arguments of each admissible extension of AF constitute an admissible extension of the epistemic system AF e .

Theorem 2 Let AF = (A e ∪ A p , Def e ∪ Def p ∪ Def m ) be a decision system, E 1 , . . . , E n its admissible extensions, and AF e = (A e , Def e ) its associated epistemic system.

• ∀E i , the set E i ∩ A e is an admissible extension of AF e . • ∀E ′ such that E ′ is an admissible extension of AF e , ∃E i such that E ′ ⊆ E i ∩ A e .
Finally, it is easy to show that when Def m is empty, i.e. no epistemic argument defeats a practical one, then the preferred extensions of AF are exactly the different combinations of the preferred extensions of AF e and AF p .

Theorem 3 Let AF = (A e ∪ A p , Def e ∪ Def p ∪ Def m ) be a decision system. Let E 1 , . . . , E n be the preferred extensions of AF e , and S 1 , . . . , S k be the preferred extensions of AF p .

If Def m = ∅ then ∀E i , i = 1, . . . , n and ∀S j , j = 1, . . . , k the set E i ∪ S j is a preferred extension of AF.

Note that in a decision system, when the defeat relation Def m is empty, the epistemic arguments become useless for the decision problem, i.e. for ordering options. Thus, only the practical system AF p is needed. It is then important to analyze the properties of this system. We investigate three kinds of issues:

1. The structure of the directed graph associated to the corresponding argumentation system. 2. The existence of extensions under different acceptability semantics, and the characterization of those extensions. 3. The characterization of the accepted arguments of such systems.

In what follows, we will show that the graph associated to AF p has no elementary odd-length cycles. Before presenting formally the result, let us first define what is an elementary cycle. Definition 6 (Elementary cycle) Let X = {a 1 , . . ., a n } be a set of arguments of A p . X is an elementary cycle iff:

1. ∀i ≤ n -1, (a i , a i+1 ) ∈ Def p and (a n , a 1 ) ∈ Def p 2. ∄X ′ ⊆ X such that X ′ satisfies condition 1.
Let us illustrate this notion of elementary cycles through the following simple example. A first result states that when the preference relation ≥ p is a partial pre-order, the graph associated to the corresponding argumentation system AF p has no elementary odd-length cycles. This result is important since the existence of oddlength cycles prevents the existence of stable extensions. Consequently, no option among elements of O is suggested. This is not suitable since in most practical cases, an agent wants to choose in anyway one solution. Let us for instance consider the case of a researcher who went to Chicago to attend a conference. Once arrived at the airport, this person had three options to attend the conference site: i) to take a taxi, ii) to take the metro or iii) to take a bus. If we assume that each option is supported by an argument, and the three arguments form a cycle of length 3, it is clear that according to the different acceptability semantics presented in Definition 4, there is no stable extension and there is one empty preferred extension. In such a case, there is no option to suggest to this person, which means that he would have to stay at the airport. This is of course not the case since he will choose one solution.

Theorem 4 Let AF p be an argumentation system built on a partial pre-order ≥ p . The graph G has no elementary oddlength cycles.

The previous result lets us not only characterizing the structure of graphs associated with the system AF p , but also proving other interesting results concerning the extensions under the well-known acceptability semantics, in particular stable one. Indeed, we will show that the practical system AF p is coherent (i.e. its stable semantics and preferred ones coincide). Formally: Theorem 5 The system AF p is coherent (i.e. each preferred extension is a stable one).

In addition to the above result, we will show that there are non-empty extensions. This result is of great importance since it ensures that among all the different options of O, one of them will be for sure proposed as a candidate.

Theorem 6

The system AF p has at least one non-empty preferred extension.

Regarding the link between the different stable extensions, we show that they are all pairwise disjoint, i.e. they don't have any common argument. Moreover, each extension contains only arguments of the same option, and arguments of a given option may not appear in different extensions.

Theorem 7 Let AF p be a practical system.

• Arguments of an extension are all in favor of the same option.

• Arguments of an option belong to at most one extension.

Note that the second bullet of this theorem is not true in the general decision system AF. Indeed, it may be the case that two arguments supporting the same option appear in distinct extensions.

From Theorem 7 we immediately obtain the following corollary which says that a skeptically accepted argument exists only when the system has a unique extension.

Corollary 2

The system AF p has a skeptically accepted argument iff it has exactly one stable extension.

Comparing options

Recall that the main objective in a decision problem consists of ordering a set O of options. In what follows, we will show that such an ordering is defined on the basis of a status assigned to each option. The status is itself defined on the basis of a given mechanism. In what follows, we will adapt the mechanisms that have been developed in the literature for inferring conclusions from different maximal consistent bases to the argumentation case.

With the first mechanism, an option is good if it is supported by a skeptically accepted argument.

Definition 7 (Skeptical option) An option o is skeptical iff ∃δ ∈ F(o) such that δ is skeptically accepted under a given semantics. Let O s denote the set of skeptical options.

Let us illustrate this mechanism with the following example. For the sake of simplicity we will consider only one option in the set O. Of course, this is not the case in real world decision making applications.

Example 9 Let O = {o}, F(o) = {δ 1 , δ 2 }, and A e = {α 1 , α 2 , α 3 }. The graph of defeats among arguments is depicted below.

α 1 α 2 α 3 δ 2 δ 1
This decision system has two stable extensions:

E 1 = {α 1 , α 3 , δ 1 } and E 2 = {α 2 , δ 1 , δ 2 }.
The option o is thus skeptical since its argument δ 1 is in both extensions. This mechanism is, however, very strong as it can be seen on the following example.

Example 10 Let O = {o}, F(o) = {δ 1 , δ 2 }, and A e = {α 1 , α 2 }.
The graph of defeats is depicted below.

α 1 α 2 δ 1 δ 2
This decision system has two stable extensions:

E 1 = {α 1 , δ 2 } and E 2 = {α 2 , δ 1 }.
The option o is not skeptical even if it is supported by an argument in both extensions.

In order to palliate the limits of the above mechanism, we introduce the universal one that accepts an option as soon as it is supported by at least one argument in each extension. Definition 8 (Universal option) An option o is universal iff ∀E where E is an extension (under a given semantics), ∃δ ∈ F(o) such that δ ∈ E. Let O u denote the set of universal options.

Example 11 (Example 10 cont.) The option o is not skeptical but it is a universal one. This mechanism is not suitable in some cases as we can see in the following example.

Example 12 Let O = {o 1 , o 2 }, F(o 1 ) = {δ 1 }, F(o 2 ) = {δ 2 }, and A e = {α 1 , α 2 }. The graph of defeats is depicted below. α 1 α 2 δ 1 δ 2
This decision system has two stable extensions: In order to handle correctly the previous example, a new mechanism is introduced. The idea is to accept an offer if it is supported at least by an argument in an extension, provided that there is no other option supported in another extension. Let us now consider the following example.

E 1 = {α 1 } and E 2 = {α 2 , δ 1 }.

Definition 9 (Argued option)

Example 14 Let

O = {o 1 , o 2 , o 3 }, F(o 1 ) = {δ 1 }, F(o 2 ) = {δ 2 }, F(o 3 ) = {δ 3 }, and A e = {α 1 , α 2 }. The graph of defeats is depicted below. α 1 α 2 δ 3 δ 1 δ 2
This decision system has two stable extensions: It is worth mentioning that this mechanism is not recommended when handling inconsistency in knowledge bases since it may lead to inconsistent conclusions. However, in a practical reasoning problem, this mechanism may be useful for two reasons. First, it may reduce the space of choice. In example 14, the choice has been reduced from 3 options to only 2 options. Second, in a decision problem, one has to choose one solution. Indeed, depending on the decision problem at hand, one may have in the set O the different possibilities and the agent should make a choice. In some other cases, when all the options are not satisfactory for the agent, this later may choose to do nothing instead of making a bad choice. In this case, o = "do nothing" is considered as an alternative in the set O.

E 1 = {α 1 , δ 2 } and E 2 = {α 2 , δ 1 }.
The following property shows the links between the different mechanisms.

Property 4

The following inclusions hold:

O s ⊆ O u ⊆ O a ⊆ O c .
In addition to the above four classes of options, it is possible to characterize two other case types of options: the ones that are not supported at all by arguments, and the ones whose arguments are all rejected in the argumentation system. Definition 11 (Rejected option/Non-supported option)

An option o is rejected iff ∀ δ ∈ F(o), δ is rejected. It is non-supported iff F(o) = ∅.
Example 15 (Example 1 cont.) The argumentation system (A, Def) has one extension {α, δ 1 }. Thus, the two arguments α and δ 1 are skeptically accepted whereas δ 2 is rejected. Consequently, the option sg (having a surgery) is skeptical while ¬sg is rejected.

We can show that the set O of options can be partitioned into three classes: the credulous ones, the rejected and the non-supported options.

Property 5

The following equality holds:

O = O c ∪ O r ∪ O ns .
It can also be shown that there is at most one skeptical option. Similarly, there is at most one universal option and at most one argued option. Moreover, when such an option exists, then no credulous option is found.

Theorem 8 Let O be a set of options.

• |O s | 2 ≤ 1, |O u | ≤ 1 and |O a | ≤ 1. • If O s = ∅ then O s = O u = O a = O c . • If O u = ∅ then O u = O a = O c . • If O a = ∅ then O a = O c .
In addition to the best option which is an output of the ar It is easy to show that the relation is a total preorder. Property 6 The relation is a total preorder. The above preordering privileges the option that is supported by the strongest argument in the sense of

≥ p . Theorem 9 If R m = ∅, then an option o is skeptical iff ∃δ ∈ F(o) s.t. ∀δ ′ ∈ F(o ′ ) with o = o ′ , then (δ, δ ′ ) ∈ > p .
In [START_REF] Amgoud | Explaining qualitative decision under uncertainty by argumentation[END_REF], it has been shown that such a criterion captures the qualitative pessimistic criterion defined and axiomatized in [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF]. This shows that the argumentation model for decision making under uncertainty is in accordance with classical models.

Illustrative example

Let us study in this section the Omelette example introduced by Savage ((Savage ), pages 13-15) and which is very much used in most works on decision making under uncertainty. In this example, an agent prepares an omelette and should decide whether or not to add an egg to a 5 eggs omelette knowing that the available egg may be rotten. Thus, the uncertainty is on the state of the 6th egg.

The agent has to choose one among the three following actions: i) to break the egg directly on the omelette (bo), ii) to break the egg in a cup (bc), and iii) to throw away this egg (ta). Thus, O = {bo, bc, ta}.

This agent has the following goals, presented in the order of their importance: i) to not waste the omelette (¬wo), ii) to not waste the 6th egg (¬we), iii) to have a 6 eggs omelette (6e), and iv) to avoid having a cup to wash (cw).

The possible consequences of the actions are as follows: 1. If the egg is good and the agent chooses to break it directly to the omelette (bo), then he will get a 6 eggs omelette (6e), he will neither waste an egg nor have to wash a cup. More importantly, he will not waste the omelette. This constitutes an argument, say δ 1 , in favor of bo. 2. If the egg is rotten and the agent decides to break it on the omelette, then he will for sure waste the omelette. This constitutes an argument δ 2 whose conclusion is bo. 3. If the egg is good and the agent chooses to break the egg apart in a cup, then he will get a 6 eggs omelette, he will not waste neither the egg nor the omelette. However, he will have to wash the cup. This constitutes an argument δ 3 for bc.

4. If the egg is rotten and the agent breaks it in a cup, then he will have a 5 eggs omelette and he will not thus waste his omelette. However, he will have to wash the cup. This gives birth to an argument δ 4 for bc. 5. If the egg is good and the agent decides to throw it away then he wastes the egg but not the omelette. He will not have to wash a cup. This forms an argument δ 5 for ta. 6. If the egg is rotten and the agent throws it away then all his preferences will be satisfied except the one of having 6 eggs omelette. Let δ 6 denote this argument for ta. It is worth noticing that in this example the knowledge is consistent, thus epistemic arguments are not necessary. Indeed, in classical decision making, the knowledge is always assumed consistent. In our decision model, only its practical part, i.e. AF p = (A p , Def p ) is then needed. Let us define this system. It is clear that

A p = {δ 1 , δ 2 , δ 3 , δ 4 , δ 5 , δ 6 }.
The relation Def p is a combination of an attack relation R p and a preference relation between arguments ≥ p . From the definition of R p , arguments supporting different options are conflicting. For instance, the pairs (δ 1 , δ 3 ), (δ 3 , δ 1 ), (δ 1 , δ 4 ) and (δ 4 , δ 1 ) are in R p . However, arguments referring to the same option are not conflicting. Thus, (δ 1 , δ 2 ) / ∈ R p , (δ 2 , δ 1 ) / ∈ R p . Similar thing holds for δ 3 and δ 4 , and also for δ 5 and δ 6 .

If the egg is good, it is clear that we have the following preferences among the arguments: δ 1 ≥ p δ 3 ≥ p δ 5 . The reason is that δ 1 refers to the most important goals of the agent. Similarly, δ 3 violates the less important goal of the agent, namely wc, whereas δ 5 violates a more important one, ¬we. In case the egg is rotten, it is also natural to consider the following preferences:

δ 6 ≥ p δ 4 ≥ p δ 2 .
It is clear from argument δ 1 that if the egg is good, then the four goals of the agent will be satisfied. So the question is then why does not he choose the action bo? The answer is that there is an uncertainty on the state of the egg. Le us consider three possibilities:

1) the agent is quite sure that the egg is good. In this case, it is clear that δ 1 ≥ δ 6 . The argumentation system is then depicted in figure below:

δ 1 δ 3 δ 5 δ 4 δ 6 δ 2
In this case, the system has one stable/preferred extension, 1 , δ 2 }, thus one skeptical option bo. The two others bc and ta are both rejected.

2) Assume now that the agent is quite sure that the egg is rotten. Thus, δ 6 ≥ p δ 1 . In this case, it can be checked that the system will have one stable/preferred extension {δ 5 , δ 6 }, concluding thus that the best action would be to throw the egg away.

3) Let us now assume that the probability that the egg is rotten is equal to the probability that it is good. In this case, it is natural to consider the following preferences:

δ 1 ≥ p δ 4 , δ 4 ≥ p δ 1 . Moreover, δ 4 ≥ p δ 6 ≥ p δ 3 ≥ p δ 5 ≥ p δ 2 .
The corresponding argumentation system AF p has two stable/preferred extensions: {δ 1 , δ 2 } and {δ 3 , δ 4 }. This means that there are two credulous options: bo and bc, whereas ta is a rejected option.

Related work

As said in the introduction, some works have been done on arguing for decision. Quite early, in [START_REF] Gordon | How to buy a porsche: An approach to defeasible decision making[END_REF] Brewka and Gordon have outlined a logical approach to decision (for negotiation purposes), which suggests the use of defeasible consequence relation for handling prioritized rules, and which also exhibits arguments for each choice. However, arguments are not formally defined.

In the framework proposed by Fox and Parsons in [START_REF] Fox | On using arguments for reasoning about actions and values[END_REF], no explicit distinction is made between knowledge and goals. However, in their examples, values (belonging to a linearly ordered scale) are assigned to formulas which represent goals. These values provide an empirical basis for comparing arguments using a symbolic combination of strengths of beliefs and goals values. This symbolic combination is performed through dictionaries corresponding to different kinds of scales that may be used. In this work, only one type of arguments is considered in the style of arguments in favor of beliefs.

In [START_REF] Bonet | Arguing for decisions: A qualitative model of decision making[END_REF], Bonet and Geffner have also proposed an approach to qualitative decision, inspired from Tan and Pearl [START_REF] Tan | Qualitative decision theory[END_REF], based on "action rules" that link a situation and an action with the satisfaction of a positive or a negative goal. However in contrast with the previous two works and the work presented in this paper, this approach does not refer to any model in argumentative inference.

In [START_REF] Amgoud | A general argumentation framework for inference and decision making[END_REF], an abstract and general decision system has been proposed. That system is defined in two steps. At the first step, arguments in favor each option are built. Arguments in favor of beliefs are also allowed. In that setting, practical arguments are not conflicting at all. The idea was to keep all the practical arguments that survive to epistemic attacks. Then, at the second step, options are compared on the basis of a decision principle. This principle is based on the accepted practical arguments. While this approach is general and flexible, it has some drawbacks. These are related to the separation of the two steps.

Conclusion

The work reported here concerns a novel approach for decision making. We have proposed an argumentation-based model that returns the best option(s) among different alternatives in one step. The model is fully fledged Dung's style and computes in one step different outputs: skeptical, universal, argued, credulous, rejected and non-supported options. These outputs and the links between them make it possible to define a total preordering on the set of options. We have shown that such an ordering privileges the option that is supported by the strongest argument among the ones that successfully passed the threats of epistemic arguments. This criterion has been studied in [START_REF] Amgoud | Explaining qualitative decision under uncertainty by argumentation[END_REF]. Recall that in this later paper, the authors have shown that this criterion captures the result of classical qualitative decision making proposed in [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF].

The properties of our system are investigated, and can be partitioned into three parts: the first part concerns the role of epistemic arguments in a decision system. We have shown that they validate the beliefs part of practical arguments. The second part concerns the properties of the of practical system embodied in the decision system. Finally, the characteristics of the options have been investigated.

An extension of this work would be to study proof procedures and to propose algorithms that check the status of an option. Another work to be done consists of extending the proposed model for capturing more decision criteria. In [START_REF] Amgoud | Explaining qualitative decision under uncertainty by argumentation[END_REF], different criteria for comparing pairs of options have been proposed. Some of them are based on the number of arguments supporting each offer, and others consist of aggregating arguments. Capturing the results of these criteria in a Dung style system is important since the number of steps is reduced into one.

Proof

• Let E i be an admissible extension of AF.

Let E = E i ∩ A e .
Let us assume that E is not an admissible extension of AF e . There are two cases: Case 1: E is not conflict-free. This means that ∃α 1 , α 2 ∈ E such that (α 1 , α 2 ) ∈ Def e . Thus, ∃α 1 , α 2 ∈ E i such that (α 1 , α 2 ) ∈ Def. This is impossible since E i is an admissible extension, thus conflict-free. Case 2: E does not defend its elements. This means that ∃α ∈ E, such that ∃α ′ ∈ A e , (α ′ , α) ∈ Def e and ∄α ′′ ∈ E such that (α ′′ , α ′ ) ∈ Def e . Since (α ′ , α) ∈ Def e , this means that (α ′ , α) ∈ Def with α ∈ E i . However, E i is admissible, then ∃a ∈ E i such that (a, α ′ ) ∈ Def. Assume that a ∈ A p . This is impossible since practical arguments are not allowed to defeat epistemic ones. Thus, a ∈ A e . Hence, a ∈ E. Contradiction.

• Let E ′ be an admissible extension of AF e . Let us prove that E ′ is an admissible extension of AF. Assume that E ′ is not an admissible extension of AF. There are two possibilities: i) E ′ is not conflict-free in AF. This is not possible since E ′ an admissible extension of AF e , thus conflict-free.

ii) E ′ does not defend all its elements in the system AF. This means that ∃a ∈ E ′ such that E ′ does not defend a. This means also that ∃b / ∈ E ′ such that (b, a) ∈ Def and ∄c ∈ E ′ such that (c, b) ∈ Def. There are two cases: either b ∈ A e or b ∈ A p . b cannot be in A e since E ′ is an admissible extension thus defends its arguments against any attack, consequently it defends also a against b. Assume now that b ∈ A p , this is also impossible since practical arguments are not allowed to attack epistemic ones. Thus, E ′ is an admissible extension of the system AF.

Theorem 3 Let AF = (A e ∪ A p , Def e ∪ Def p ∪ Def m ) be a decision system. Let E 1 , . . . , E n be the preferred extensions of AF e , and S 1 , . . . , S k be the preferred extensions of AF p . If Def m = ∅ then ∀E i , i = 1, . . . , n and ∀S j , j = 1, . . . , k the set E i ∪ S j is a preferred extension of AF.

Proof Let E be a preferred extension of AF e and S be a preferred extension of AF p . Let us assume that E ∪ S is not a preferred extension of AF. There are three cases:

Case 1: E∪S is not conflict-free. Since E and S are conflictfree, then ∃α ∈ E and ∃δ ∈ S such that (α, δ) ∈ Def. [START_REF] Berge | Graphs and Hypergraphs[END_REF]) that a graph without elementary odd-length cycles has a maximal non-empty kernel. Moreover, Doutre has shown in [START_REF] Doutre | Autour de la sémantique préférées des systèmes d'argumentation[END_REF]) that a maximal kernel corresponds exactly to a preferred extension. Thus AF p has at least one non-empty preferred extension. Theorem 7 Let AF p be a practical system.

• Arguments of an extension are all in favor of the same option. • Arguments of an option belong to at most one extension.

Proof

• Let E be a given extensions of AF p . Assume that ∃δ 1 , δ 2 ∈ E such that δ 1 = δ 2 . Assume also that Conc(δ 1 ) = o 1 and Conc(δ 2 ) = o 2 with o 1 = o 2 . Since o 1 = o 2 , (δ 1 , δ 2 ) ∈ R p and (δ 2 , δ 1 ) ∈ R p (from the definition of R p ). However, according to Theorem 1, the extension E does not contain R p conflicts. Contradiction. • Let o ∈ O. Assume that δ 1 , δ 2 ∈ F(o). Let E 1 , E 2 be two stable extensions of AF p such that E 1 = E 2 , δ 1 ∈
• If O s = ∅ then O s = O u = O a = O c . • If O u = ∅ then O u = O a = O c . • If O a = ∅ then O a = O c .
Proof Let (A, Def) be a decision system, and E 1 , . . . , E n is extensions under a given semantics. (2) From ( 1) and ( 2), it follows that δ, δ ′ ∈ E j . However, according to the definition of R p , both (δ, δ ′ ) ∈ R p and (δ ′ , δ) ∈ R p hold. This contradicts the fact that E j is R p conflict-free (according to Theorem 1).

  x b. In what follows, > x denotes the strict relation associated with ≥ x . It is defined as follows: (a, b) ∈> x iff (a, b) ∈≥ x and (b, a) / ∈≥ x . Moreover, when (a, b) ∈≥ x and (b, a) ∈≥ x , we say that a and b are indifferent. When (a, b) / ∈≥ x and (b, a) / ∈≥ x , the two arguments are said incomparable.

Property 2

 2 Each preference relation ≥ x (with x ∈ {e, p, m}) is combined with the conflict relation R x into a unique relation between arguments, denoted by Def x and called defeat relation, in the same way as in ((Amgoud & Cayrol 2002), Definition 3.3, page 204). Definition 1 (Defeat relation) Let A be a set of arguments, and a, b ∈ A. (a, b) ∈ Def x iff: • (a, b) ∈ R x , and • (b, a) / ∈> x Let Def e , Def p and Def m denote the three defeat relations corresponding to the three attack relations. In case of Def m , the second bullet of Definition 1 is always true since epistemic arguments are strictly preferred (in the sense of ≥ m ) to any practical arguments. Thus, Def m = R m (i.e. the defeat relation is exactly the attack relation R m ). Regarding the two other relations (Def e and Def p ) they coincide with their corresponding attack relations in case all the arguments are incomparable. A straightforward consequence is the following simple property. The relation Def p is symmetric iff ∀δ, δ ′ ∈ A p , δ and δ ′ are incomparable. Def m is asymmetric. Example 6 (Example 1 cont.

  In graph (1) of the above figure, the set {a, b, c, d} forms an elementary cycle. However, in graph (2), the set {a, b, c, d} is not an elementary cycle since its subset {c, d} already satisfies the first condition of Definition 6.

  Let o ∈ O. The option o is argued iff ∃E such that E is an extension (under a given semantics), and ∃δ ∈ F(o) and δ ∈ E, and ∄E ′ such that E ′ is an extension that contains an argument δ ′ with Conc(δ ′ ) = o. Let O a denote the set of argued options. Example 13 (Example 12 cont.) The option o is argued in the sense of Definition 9.

  gumentation system, a preference relation on O ( ⊆ O × O) is also provided. For two options o, o ′ , (o, o ′ ) ∈ O (or o o ′ ) means that o is at least as good as o ′ . Let ≻ denote the strict version of (i.e. (o, o ′ ) ∈≻ iff (o, o ′ ) ∈ and (o ′ , o) / ∈ ). The idea is that credulous options are strictly preferred to any non-supported option. A non-supported option is better than a rejected option. For simplicity reasons, we will write O x ≻ O y to denote that any option in O x is strictly preferred to any option in O y . Options of the same set O x with x ∈ {c, r, ns} are equally preferred (i.e. ∀o, o ′ ∈ O x , both (o, o ′ ) and (o ′ , o) are in ). Definition 12 Let O be a set of options. O c ≻ O ns ≻ O r .

  The options o 1 and o 2 are not universal. However, compared to o 2 , the argument of o 1 is in at least one extension. Thus, one would prefer o 1 to o 2 . The reason is that in the current state of the world, the argument δ 2 cannot hold, thus one cannot rely on its conclusion o 2 . However, there is a possibility that o 1 reaches the desired state, i.e. the goal satisfied by o 1 .

  Contradiction with the fact that Def m = ∅. Case 2: E ∪ S does not defend its elements. This means that: i) ∃α ∈ E such that ∃α ′ ∈ A e , (α ′ , α) ∈ Def e and E ∪ S does not defend it. Impossible since E is a preferred extension then it defends its arguments. ii) ∃δ ∈ S such that ∃a ∈ A, and (a, δ) ∈ Def and δ is not defended by E ∪ S. Since Def m = ∅, a ∈ A p . However, S is an extension and defends its arguments. Contradiction. Assume that a ∈ A e . This means that E ∪ {a} is conflict-free and defends a. This contradicts the fact that E is a preferred extension of AF e . Similarly, if assume that a ∈ A p , this means that S ∪ {a} is conflict-free and defends a. This contradicts the fact that S is a preferred extension of AF p . Theorem 4 Let AF p be an argumentation system built on a partial pre-order ≥ p . The graph G has no elementary oddlength cycles. Proof Let δ 1 , . . . , δ 2n+1 be arguments of A p . Let us assume that there is an elementary odd-length cycle between these arguments, i.e. ∀i ≤ 2n, (δ i , δ i+1 ) ∈ Def p , and (δ 2n+1 , δ 1 ) ∈ Def p . Since the cycle is elementary, then ∄δ i , δ i+1 such that (δ i , δ i+1 ) ∈ Def p and (δ i+1 , δ i ) ∈ Def p . Thus, δ i > p δ i+1 , ∀i ≤ 2n. Thus, δ 1 > p δ 2 > p . . . δ 2n > p δ 2n+1 > p δ 1 . Since the relation > p is transitive, then we have both δ 1 > p δ 2n+1 and > p δ 2n+1 > p δ 1 , contradiction.

	defends a. Theorem 5 The system AF p is coherent (i.e. each preferred
	extension is a stable one).
	Proof According to Theorem 4, the graph associated with
	(A, Def) has no elementary odd-length cycles. Moreover, it
	has been shown by Dunne and Bench Capon in (Dunne &
	Capon 2002) that if the graph associated with an argumen-
	tation system has no elementary odd-length cycles then it is
	coherent.
	Theorem 6 The system AF
	Case 3: E ∪ S is not maximal for set inclusion. This means
	that ∃a ∈ A such that E ∪ S ∪ {a} is conflict-free and

p has at least one non-empty preferred/stable extension. Proof According to Theorem 4, the graph associated with AF p has no elementary odd-length cycles. Besides, Berge has proved in

  E 1 and δ 2 ∈ E 2 . According to the first bullet of this theorem, E 1 and E 2 contain only arguments in favor of o. Thus, according to Property 3, ∀δ ∈ E 1 and ∀δ ′ ∈ E 2 , (δ, δ ′ ) / ∈ Def p and (δ ′ , δ) / ∈ Def p . This contradicts the fact that E 1 and E 2 are stable extensions. Corollary 2 The system AF p has a skeptically accepted argument iff it has exactly one stable extension. Proof The proof follows directly from Theorem 7, and Definition 5. Indeed, an argument cannot belong to more than one extension. Property 4 The following inclusions hold: Os ⊆ O u ⊆ O a ⊆ O c .Proof Let AF be a decision system for ordering O. Let E 1 , . . . , E n its extensions under a given semantics.• O s ⊆ O u ? Let o ∈ O s . Thus, ∃δ ∈ F(o) such that δ ∈ E i . Thus, ∀E i , δ ∈ E i , and consequently, o ∈ O u . • O u ⊆ O a ? Let o ∈ O u . Thus, ∀E i , ∃δ ∈ F(o) such that δ ∈ E i . Itis thus clear that each extension E i supports the option o. Moreover, according to Corollary 1, each extension supports only one option at most. Thus, o ∈ O a . • O a ⊆ O c ? Let o ∈ O a . Then, ∃E i such that ∃δ ∈ F(o) and δ ∈ E i . Thus, o ∈ O c . Property 5 The following equality holds: O = O c ∪ O r ∪ O ns .

Proof Let us proceed by case analysis. Let o ∈ O. There are two situations: i)

F(o) = ∅, thus o ∈ O ns , ii) F(o) = ∅.

In this case, there are five possibilities:

• ∀δ ∈ F(o), δ is rejected. Thus, o ∈ O r . • ∀δ ∈ F(o), δ is skeptically accepted. Thus, o ∈ O s . • ∃δ ∈ F(o), δ is skeptically accepted. Thus, o ∈ O s . • ∀δ ∈ F(o), δ is credulously accepted. Thus, o ∈ O c . • ∃δ ∈ F(o)

, δ is credulously accepted. Thus, o ∈ O c . Theorem 8 Let O be a set of options. • |O s | 3 ≤ 1, |O u | ≤ 1 and |O a | ≤ 1.

•

  Let us assume that ∃o 1 , o 2 ∈ O s . This means that ∃δ 1 , δ 2 ∈ A p such that Conc(δ 1 ) = o 1 , Conc(δ 2 ) = o 2 and δ 1 , δ 2 are skeptically accepted. This means also that δ 1 , δ 2 ∈ i=1,...,n E i . Let's take a given extension E j . It is clear that δ 1 , δ 2 ∈ E j . According to Theorem 1, E j does not contain a R p conflict. However, according to the definition of R p , since δ 1 and δ 2 support different options, then both (δ 1 , δ 2 ) ∈ R p and (δ 2 , δ 1 ) ∈ R p hold. Contradiction. || denotes the cardinal of a given set. • Let us assume that O s = ∅ and that O c \ O s = ∅. Since O s = ∅, this means that ∃o ∈ O such that ∃δ ∈ F(o) and δ is skeptically accepted. This means also that δ ∈ i=1,...,n E i . (1) Besides, O c \ O s = ∅ means that ∃o ′ ∈ O c \ O s . This means also that ∃δ ′ ∈ F(o ′ ) and δ ′ is credulously accepted. It follows that ∃E j (1 ≤ j ≤ n) such that δ ′ ∈ E j .

3

  Theorem 9 If R m = ∅, then an option o is skeptical iff ∃δ ∈ F(o) s.t. ∀δ ′ ∈ F(o ′ ) with o = o ′ , then (δ, δ ′ ) ∈ > p . Proof Let R m = ∅, and o ∈ O. • Assume that o is skeptical, this means that ∃δ ∈ F(o)such that δ is skeptically accepted. According to Corollary 2, this means that the system AF p has a unique stable extension, say E. Moreover, according to Corollary 1, each extension supports only one option. Thus,∀δ ′ ∈ F(o ′ ), (δ, δ ′ ) ∈ Def p and (δ ′ , δ) / ∈ Def p . Thus, (δ, δ ′ ) ∈ > p . • Assume that ∃δ ∈ F(o) such that ∀δ ′ ∈ F(o ′ ), (δ, δ ′ ) ∈> p . Moreover, from the definition of R m , ∀δ ′ ∈ F(o ′ ), (δ, δ ′ ) ∈ Def p and (δ ′ , δ) ∈ Def p . Thus, (δ, δ ′ ) ∈ Def p and (δ ′ , δ) / ∈ Def p .Thus, δ is undefeated. Consequently, it belongs to every preferred extension. Thus, δ is skeptically accepted. Consequently, o is skeptical.

At some places, it is also called argumentation system.

|| denotes the cardinal a given set.

Acknowledgment

The authors would like to thank Srdjan Vesic for his useful comments.

Appendix

Property3 Let o ∈ O. ∄δ 1 , δ 2 ∈ F(o) such that (δ 1 , δ 2 ) ∈ Def p . Proof Let o ∈ O. Assume that ∃δ 1 , δ 2 ∈ F(o) such that (δ 1 , δ 2 ) ∈ Def p . This means that (δ 1 , δ 2 ) ∈ R p . This is not allowed according to the definition of R p . Theorem 1 Any admissible extension of (A, Def) is R xconflict-free with x ∈ {p, m}.

Proof Let E be an admissible extension of the system (A, Def). Since R m = Def m , then if E contains a R m conflict, then it contains a Def m conflict, which contradicts the fact that E is conflict-free.

Let us assume that E contains a R p conflict between two arguments δ 1 and δ

This contradicts the fact that E is an admissible extension. • Case 3: δ 2 > x δ 1 . Since (δ 1 , δ 2 ) ∈ R p , it holds that (δ 2 , δ 1 ) ∈ Def p . Thus, δ 1 and δ 2 should not appear in the same extension E. • Case 4: δ 1 > x δ 2 . Similar to case 3 since R p is symmetric.

Corollary 1 Let E be an admissible extension of AF p . If

Proof Let E be an admissible extension. Assume that E ∩ A p = ∅. There are two cases:

Moreover, each argument supports only one option. Thus,

According to the definition of R p , it holds that (δ 1 , δ 2 ) ∈ R p and (δ 2 , δ 1 ) ∈ R p . However, according to Theorem 1, the set E is R p conflict-free. Contradiction.

Theorem 2 Let AF = (A e ∪ A p , Def e ∪ Def p ∪ Def m ) be a decision system, E 1 , . . . , E n its admissible extensions, and AF e = (A e , Def e ) its associated epistemic system.

• ∀E i , the set E i ∩ A e is an admissible extension of AF e .

• ∀E ′ such that E ′ is an admissible extension of AF e , ∃E i such that E ′ ⊆ E i ∩ A e .