Damien Sarah

Sif Nico Pierre

Keywords: théorie de décision, théorie de possibilité, axiomatisation, choix collectif, arbres de décision decision theory, possibility theory, axiomatization, collective choice, decision trees

Tout d'abord, je remercie toutes celles et tous ceux qui ont contribué à la préparation et la rédaction de ma thèse. Bien évidemment, il m'est difficile de remercier tout le monde, chacun par son nom car c'est grâce à l'aide de nombreuses personnes que j'ai pu mener cette thèse à son terme.

Je souhaiterais en premier lieu exprimer ma gratitude empreinte d'affection à toute ma famille, merci à mon père et ma mère qui ont été pour moi des étoiles lumineuses tout au long du chemin et qui ont toujours cru en moi. Je remercie énormément ma soeur Chaima, mon frère Ayoub, mon mari Raed et toute ma famille pour leur amour sincère et leur soutien sans faille au cours de ces années.

Mes remerciements vont également aux rapporteurs, Jérôme Lang et Patrice Perny, auxquels j'associe les membres Zied Elouedi, Régis Sabbadin ainsi que Didier Dubois, président du jury de ma soutenance, pour m'avoir fait l'honneur de prendre le temps de relire en détail mon travail et dont la gentillesse, l'intérêt et les conseils pour continuer et améliorer ma recherche sont inestimables. Que de telles personnes, exemples parfaits de chercheurs accomplis, se soient assis à la table de mon jury est un accomplissement en soi et m'emplit de fierté.

Je remercie grandement mes directrices de thèse Nahla Ben Amor et Hélène Fargier de m'avoir acceptée et encadrée tout au long de la préparation de ma thèse. Je suis ravie d'avoir pu travailler en leur compagnie car en plus de leur appui scientifique et le côté humain, elles sont toujours été là pour me soutenir et me conseiller tout au long de l'élaboration de mes travaux surtout aux moments difficiles.

Un remerciement spécial pour Maroua: tu étais toujours là pour moi. Je remercie également tous mes amis qui m'ont apporté le soutien moral pendant les années de cette thèse: Héla, Zeineb, Nahla, Soumaya, Imen, Sleh et Wided.

Durant mes séjours à IRIT, j'ai rencontré plusieurs personnes sympathiques avec qui j'ai partagé de bons moments: Fayçal, Mariem, Ameni, Chloé, Juliette,

Résumé

Cette Thèse pose la question de la décision collective sous incertitude possibiliste. On propose différents règles de décision collective qualitative et on montre que dans un contexte possibiliste, l'utilisation d'une fonction d'agrégation collective pessimiste égalitariste ne souffre pas du problème du Timing Effect. On étend ensuite les travaux de Dubois et Prade (1995, 1998) relatifs à l'axiomatisation des règles de décision qualitatives (l'utilité pessimiste) au cadre de décision collective et montre que si la décision collective comme les décisions individuelles satisfont les axiomes de Dubois et Prade ainsi que certains axiomes relatifs à la décision collective, particulièrement l'axiome de Pareto unanimité, alors l'agrégation collective égalitariste s'impose. Le tableau est ensuite complété par une axiomatisation d'un pendant optimiste de cette règle de décision collective.

Le système axiomatique que nous avons développé peut être vu comme un pendant ordinal du théorème de [START_REF] Harsanyi | Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility[END_REF]. Ce résultat á été démontré selon un formalisme qui et basé sur le modèle de de Von NeuMann and Morgenstern (1948) et permet de comparer des loteries possibilistes. Par ailleurs, on propose une première tentative pour la carectérisation des règles de décision collectives qualitatives selon le formalisme de Savage (1972) qui offre une représentation des décisions par des actes au lieu des loteries.

De point de vue algorithmique, on considère l'optimisation des stratégies dans les arbres de décision possibilistes en utilisant les critères de décision caractérisés dans la première partie de ce travail. On offre une adaptation de l'algorithme de Programmation Dynamique pour les critères monotones et on propose un algorithme de Programmation Multi-dynamique et un algorithme de Branch and Bound pour les critères qui ne satisfont pas la monotonie.

Finalement, on établit une comparaison empirique des différents algorithmes proposés. On mesure les CPU temps d'exécution qui augmentent linéairement en fonction de la taille de l'arbre mais restent abordable même pour des grands arbres. Ensuite, nous étudions le pourcentage d'exactitude de l'approximation des algorithmes exacts par Programmation Dynamique: Il apparaît que pour le critère U -max ante l'approximation de l'algorithme de Programmation Multi-dynamique n'est pas bonne. Mais, ceci n'est pas si dramatique puisque cet algorithme est polynomial (et efficace dans la pratique). Cependant, pour la règle U +min ante l'approximation par Programmation Dynamique est bonne et on peut dire qu'il devrait être possible d'éviter une énumération complète par Branch and Bound pour obtenir les stratégies optimales .

INTRODUCTION General introduction

Decision theory is an important field in Artificial Intelligence (AI) that has emerged to support decision making, particularly decision making under uncertainty. Making a decision amounts to comparing possible alternatives and choose the best among them on the basis of a criterion or a decision rule. The use of one or another criterion depends essentially on the nature of the decision maker preferences and on the manner he or she expresses his knowledge. Besides, in order to solve any decision problem, one should clearly define the environment of decision. In the last decades, a significant progress has been noticed in this domain leading to several decision models [START_REF] Bouyssou | Decision-making process -Concepts and Methods[END_REF][START_REF] Inoue | Decision theory: Principles and approaches[END_REF][START_REF] Kochenderfer | Decision Making Under Uncertainty: Theory and Application[END_REF]. Each of them is motivated by one or several concerns such as uncertainty, collectivity, multiple objectives, or multiple criteria handling.

In this Thesis, we are interested in decision making problems where the knowledge about states of nature is pervaded with uncertainty. The most well known approach for decision making under uncertainty is the expected utility model. This model relies on a probabilistic representation of uncertainty and it owes its success to an axiomatic justification for both objective (VNM's approach [START_REF] Morgenstern | Theory of Games and Economic Behavior[END_REF]) and subjective (Savage approach [START_REF] Savage | The Foundations of Statistics[END_REF]) modeling of uncertainty.

In some cases, numerical information are unavailable and the decision maker is not able to express his preferences quantitatively. Therefore, probability theory becomes inappropriate, and gives a way to other uncertainty theories such as possibility theory where only an order between different consequences may be required. The latter offers a simple and natural framework to handle qualitative uncertainty. However, giving up the probabilistic quantification of uncertainty yields giving up the EU criterion as well. Fortunately, the growth of possibilistic decision theory has led to the proposal and the characterization of a panoply of possibilistic decision rules. In this work, we are, particularly, interested in optimistic and pessimistic criteria that are the qualitative counterparts of EU criterion [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Dubois | Decision theoretic foundations of qualitative possibility theory[END_REF][START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF].

In addition to uncertainty, another important aspect should be considered when making decisions, is "time". Generally, a decision maker does not make simple non related decisions but he follows a strategy i.e. a sequence of decisions that are executed successively. That is why graph-1 General introduction 2 ical models are of special interest. Such models indeed, allow a clear description of the problem with a simple representation of different decision scenarios. Besides, they offer valuable computational methods; based on Dynamic Programming and variable elicitation; to compare them. In the literature, we can specify four main families of decision models which are: decision trees [START_REF] Raiffa | Decision Analysis-Introductory lectures on choices under uncertainty[END_REF], influence diagrams [START_REF] Howard | Influence diagrams[END_REF], Markov decision processes [START_REF] Bellman | A Markovian Decision Process[END_REF] and Valuation Based Systems [START_REF] Shenoy | Valuation-based systems for Bayesian decision analysis[END_REF].

Simultaneously, in recent years there is a growing interest for collective decision problems in the Artificial Intelligence community. This field, is inherited from classical sciences in particular the branch of economic theory, social choice and welfare theory. Collective decision making aims to provide a social or collective utility function that can be used to evaluate different policies and to make decisions that satisfy not only one person but a group of persons or agents. Then, we can say that the main question to answer in the context of collective decision is how to aggregate individual utilities in order to obtain a collective one.

However, decision making process usually requires to deal with uncertainty. So, as for single decision making, collective decision making under uncertainty has been studied by many scholars. A seminal work has been proposed in 1955 by Harsanyi [START_REF] Harsanyi | Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility[END_REF] to solve collective decision problems under risk. In fact, under the assumption that individual preference relations as well as the collective one satisfy VNM's axioms and considering the Pareto indifference axiom, Harsanyi proved that the collective utility is a weighted sum of the individual expected utilities. This representation theorem has always been interpreted as a justification of utilitarian aggregation.

Many contributions were inspired by this theorem, some of them have been developed to clarify and to confirm the use of the sum of expected utilities in context of collective decision making under uncertainty [START_REF] Weymark | A reconsideration of the harsanyi-sen debate on utilitarianism[END_REF]. Others, like Myerson [START_REF] Myerson | Utilitarianism, egalitarianism, and the timing effect in social choice problems[END_REF] proved that the use of Harsanyi's Theorem is the only way to avoid timing effect. More recently, several works [START_REF] Gilboa | Utilitarian aggregation of beliefs and tastes[END_REF][START_REF] Mongin | The paradox of the bayesian experts and state-dependent utility theory[END_REF] have been proposed as an attempt to extend Harsanyi's theorem to the context of subjective expected utility model. However, Harsanyi's approach has been criticized by other researchers such that Diamonds [START_REF] Diamond | Cardinal welfare, individualistic ethics, and interpersonal comparison of utility: Comment[END_REF] who suggested the use of egalitarianism to aggregate individual preferences.

Nowadays, collective decision problems under uncertainty form an attractive field that is always in vogue. To the best of our knowledge, all the contributions provided in this domain rely on probability theory. However, as we have mentioned before, this framework is inappropriate to handle partial ignorance or qualitative uncertainty. In this work, we attempt to tackle this problematic and to answer the following question: How to solve a collective decision problem under qualitative uncertainty?

In this thesis, we propose eight qualitative decision rules that differ with regard to the decision maker attitude toward uncertainty, the used aggregation function and the time where uncertainty is integrated. Hence, we consider uncertainty then a multi-agent aggregation (ex-post aggregation) or the contrary collectivity then uncertainty (ex-ante aggregation). Afterward, we have studied the relationship between those rules and proved that the coincidence between ex-ante and ex-post approach is not synonym of utilitarianism. This result has motivated us to provide a qualitative egalitarian counterpart of Harsanyi's theorem. So, we have performed an axiomatic system rel-

Part I Background 4 CHAPITRE 1
Decision making under probabilistic uncertainty

Introduction

According to an old scientific tradition, decision making theory is a prevalent concern in cognitive psychology, economics and social sciences. In this domain, still in vogue, several studies have been carried out to justify the use of this or that decision criterion to compare alternatives. This justification is based on a set of axioms capturing the choice behavior of the decision maker.

The most known models for decision making under uncertainty are based on the expected utility (EU) criterion. It relies on a probabilistic representation of uncertainty. This classical decision rule has been provided with an axiomatic justification, in the middle of the last century.

In this chapter, we study the properties of this model (i.e. the expected utility model) and we recall its axiomatic foundations. First, we present the main definitions and notations relative to decision theory under uncertainty in Section 1.2. Then, Section 1.3 details the expected utility (EU) criterion and its axiomatization in the context of risk. Finally, Section 1.4 is devoted to subjective expected utility (SEU) and Savage's axiomatic system.

Basic concepts of decision theory

Decision making is primarily a matter of choosing between alternatives that most commonly are expressed implicitly. Thus, solving a decision problem amounts to providing appealing choice with respect to the specification of the decision problem at hand, i.e. the available knowledge about the environment and the decision maker preferences relative to possible results of different actions.

Decision problems under uncertainty

Formally, a decision making problem under uncertainty is defined by a set of possible states of the world S (states of nature) and a set of possible outcomes or consequences denoted by X. A decision also called action or act, assigns a consequence to each state of nature, it is a mapping from S to X. Besides, it is assumed that any decision maker is able to provide a well-defined preference relation denoted by over the set of consequences.

Uncertainty

In order to make a decision, it is necessary beforehand to clearly define the knowledge over the set of states of nature and the associated consequences. According to the type of available information relative to states of nature, we can distinguish several forms of uncertainty, namely:

• Probabilistic uncertainty: where uncertainty can be modeled via a probability distribution. We can distinguish two types of probabilities:

1. Objective probabilities: indicate the relative frequency of the realization of events. A situation of uncertainty characterized by objective probability is called a situation of risk. In this report, as in literature, we use the term risk to indicate objective probabilistic uncertainty.

2. Subjective probabilities: are probabilistic measures derived from an individual's personal belief about whether an event is likely to occur when no frequencies are available.

• Non probabilistic uncertainty: Since probability theory presents some draw-backs to represent ignorance, in particular total ignorance, several non probabilistic theories (also named non classical theories of uncertainty) have been defined to cope with this issue, such as imprecise probabilities [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF], evidence theory [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], rough set theory [START_REF] Pawlak | Rough sets[END_REF] and possibility theory [START_REF] Dubois | Possibility Theory: An Approach to Computerized Processing of Uncertainty (traduction revue et augmentée de Théorie des Possibilités)[END_REF][START_REF] Dubois | An introductory survey of possibility theory and its recent developments[END_REF][START_REF] Zadeh | Fuzzy sets as a basis for theory of possibility[END_REF][START_REF] Zadeh | A theory of approximate reasoning[END_REF] that will be investigated in the next chapter.

Preferences

A preference relation can be defined by a complete pre-order order over a set of consequences. Formally, the preference between two consequences x and y ∈ X is denoted by x y. It means that "x is at least as good as y" for the decision maker. denotes the asymmetric part of and ∼ its symmetrical part such that:

• The strict preference relation is defined by x y if and only if x y and y x and it means that"x is strictly preferred to y".

• The indifference relation ∼ is defined by x ∼ y if and only if x y and y x and it means that " x and y are indifferently preferred".

Generally, a preference relation is assumed to verify a set of properties (axioms). The main axioms are defined as follows [START_REF] Fishburn | Utility Theory for Decision Making[END_REF]:

Axiom. (Completeness) ∀x, y either x y or y x.

Axiom. (Antisymmetry) If x y and y x then x = y.

Axiom. (Asymmetry) If x is strictly preferred to y, then y is not strictly preferred to x.

x y then ¬(y x).

Axiom. (Transitivity) If x is at least as good as y and y is at least as good as z, then x is at least as good as z.

If (x y and y z) then (x z).

Axiom. (Reflexivity)The relation over a set X is reflexive if every element of X is related to itself. ∀x ∈ X, x x.

In the remainder of this work, we are in particular interested by preference relations defining pre-order over consequences. The relation is a pre-order on X iff it is transitive and reflexive. If the relation satisfies also the completeness then we have a complete pre-order.

The preference relation of an agent over a set of consequences is usually represented by a utility function. This latter, denoted by u, is a mapping from the set of consequences X to a numerical or ordinal scale U (u : X → U ). Formally, U = {u 1 , . . . u n } is a totally ordered set that belongs to R such that u 1 ≤ • • • ≤ u n . The worst (resp. best) utility is denoted by u ⊥ (resp. u ).

Expected Utility: Von Neumann and Morgenstern's theory

In this section, we present the expected utility model, the most known framework to deal with decision making problems under risk. Expected utility (EU) theory has emerged in 1738 with Bernoulli [START_REF] Bernoulli | Exposition of a New Theory on the Measurement of Risk[END_REF] in "Commentarii Academiae Scientiarum Imperialis Petropolitanae" (translated as "Exposition of a new theory on the measurement of risk"). It was proposed in order to solve the Saint Petersburg paradox [START_REF] Clark | The st. petersburg paradox. Paradoxes from A to Z[END_REF].

This paradox is a theoretical game used in economics related to probability and decision theories. It presents the human beings behavior faced to random events. The value of the random variable is probably small with infinite expected payoff. Bernoulli has shown that in this situation, probability theory dictates a decision that no reasonable player would take. Thus to solve this problem, he proposed to use expected utility rather than expected value (outcome). This proposition has motivated Von Neumann and Morgenstern [START_REF] Morgenstern | Theory of Games and Economic Behavior[END_REF] to provide an axiomatic system to justify the use of expected utility and to define necessary conditions under which a utility function exists.

Von Neumann and Morgenstern's approach

In a framework of decision making under risk, the decision maker's knowledge about the states of nature S is represented by a probability distribution. Besides, it is also assumed that the decision maker has a well defined weak preference relation on the set of possible consequences X of its choices.

In Von Neumann and Morgenstern's (VNM) approach, an act or a decision is represented by a probability distribution over the set of possible outcomes. It is called a simple probabilistic lottery and it is denoted by L = λ 1 /x 1 , . . . , λ n /x n , where λ i = p(x i ) is the probability that the decision leads to an outcome x i .

A probabilistic compound lottery denoted by λ 1 /L 1 , . . . , λ m /L m is a normalized probability distribution over the set of lotteries where λ i is the probability to obtain lottery L i . Therefore, a decision making problem under risk can be represented using:

• A set of consequences (outcomes) X,

• A set of probabilistic lotteries L, where each lottery L i is a probability distribution p over the set of consequences X,

• A utility function u: X → U .

Any compound probabilistic lottery can be reduced into a simple one, denoted by Reduction (

λ 1 /L 1 , . . . , λ m /L m ).
Formally, it is defined by: Obviously, the reduction of a simple lottery gives a simple lottery as result. Since, the sum ( ) and the product (×) operations are polynomial, the reduction is polynomial in the size of the compound lottery. Note that the size of a simple probabilistic lottery is simply the number of its outcomes; and the size of a compound lottery is the sum of the sizes of its sub-lotteries.

Reduction( λ 1 /L 1 , . . . , λ m /L m ) = j=1..m (λ j × λ j 1 )/x 1 , . . . , j=1..m (λ j × λ j n )/x n (1.1) Example 1.1. Let L 1 = 0.7/
Solving a decision problem under risk amounts to evaluating risky alternatives and choosing among them. In this context, Von Neumann and Morgenstern's proposed to use the expected utility (EU) criterion to compare lotteries, i.e. probability distribution over consequences. Formally, the computation of the expected utility of a lottery L is performed as follows: Definition 1.1. Given a probabilistic lottery L = λ 1 /x 1 , . . . , λ n /x n and a utility function u, the computation of the expected utility of L (denoted by EU (L)) is computed by:

EU (L) = x i ∈X λ i × u(x i ).
(1.

EU (L ) = (0.7 × 0) + (0.3 × 20) = 6.
So, we can deduce that L is preferred to L .

Formally, considering the expected utility criterion, any preference order EU defined on simple probabilistic lotteries can be extended to compare compound lotteries as follows:

L EU L iff Reduction(L) EU Reduction(L ).
(1.3)

Axiomatic system of Von Neumann and Morgenstern

At the middle of the last century, Von Neumann and Morgenstern have provided an axiomatic justification to the expected utility criterion [START_REF] Morgenstern | Theory of Games and Economic Behavior[END_REF]. They have shown that if the preference relation of any decision maker satisfies a set of axioms of rationality, then it can be represented via a utility function (EU) over lotteries. This axiomatic system is detailed in the following section.

Von Neumann and Morgenstern axiomatic system that characterize preference relation over lotteries is based on three fundamental axioms defined as follows:

Axiom. (V N M 1: Weak order) The preference relation is reflexive, complete and transitive.

Axiom. (V N M 2: Continuity) For any three probabilistic lotteries L, L and L , if L is at least good as L and L is at least good as L then there is a probability p for which the rational agent (DM) will be indifferent between lottery L and the lottery in which L comes with probability p, L with probability

(1 -p). L L L ⇒ ∃ p ∈ ]0, 1[ s.t. pL + (1 -p)L ∼ L .
Axiom. (V N M 3: Independence) For any probabilistic lotteries L, L and L , if a DM prefers L to L , then his preferences over these lotteries isn't affected by mixing in a third one.

L L ⇔ ∃ p ∈]0, 1] s.t. pL + (1 -p)L pL + (1 -p)L .
The key axiom of VNM's formalism is the independence axiom (V N M 3). It is the central axiom of the (objective) expected utility model and it can be interpreted as follows: If the decision maker prefers L to L and he have to choose between p×L+(1-p)×L and p×L +(1-p)×L then he will prefer the mixture p×L+(1-p)×L to p×L+(1-p)×L whatever the probability of the event that happens.

Von Neumann and Morgenstern [START_REF] Morgenstern | Theory of Games and Economic Behavior[END_REF] have claimed that a preference relation satisfying the above axioms can be represented by an expected utility function. Their representation theorem is defined by: Theorem 1.1. If the preference relation satisfies axioms V N M 1, . . . , V N M 3 then it is exists a utility function u: X → R over the set of lotteries L such that:

∀L, L , L L ⇔ EU (L) ≥ EU (L ).
(1.4) Theorem 1.1 can be described as follows: if the preference relation of any decision maker satisfies completeness, transitivity, continuity and independence axioms, then the DM behavior's obeys the maximization of the expected utility.

Subjective Expected Utility: Savage's approach

The VNM's model is a powerful and attractive tool to handle decision making under risk. However in real world problems, objective probabilities are not always available. To deal with such cases, Savage provided an extension of expected utility theory to a subjective context, namely Subjective expected utility [START_REF] Savage | The Foundations of Statistics[END_REF].

Savage approach

In Savage's framework, a decision problem is represented by:

• A set of consequences X,
• A set of states of nature S (a subset E of S is an event),

• A decision (or "act") is a function f : S → X and the set of acts is denoted by F,

•

a preference relation on F; denotes its asymmetric part, ∼ its symmetric part.

The subjective expected utility was developed by Savage in 1954 [START_REF] Savage | The Foundations of Statistics[END_REF] as follows:

Definition 1.2. Given a probabilistic distribution p over S and a utility function u on X, the subjective expected utility of an act f (denoted by SEU (f )) is defined by:

SEU (f ) = s i ∈S p(s i ) × u(f (s i )). (1.5) Example 1.3. Let S = {s 1 , s 2 , s 3 , s 4
} be a set of states of nature such that p(s 1 ) = 0.2, p(s 2 ) = 0.1, p(s 3 ) = 0.4 and p(s 4 ) = 0.3. Consider the two acts f and g given in Table 1.1.

The utility value associated to each consequence is defined as follows:

u(f (s 1 )) = u(g(s 2 )) = 5, Acts/States s 1 s 2 s 3 s 4 f f (s 1 ) f (s 2 ) f (s 3 ) f (s 4 ) g g(s 1 ) g(s 2 ) g(s 3 ) g(s 4 )
Table 1.1: Consequences of acts f and g

u(f (s 2 )) = u(g(s 3 )) = 10, u(f (s 3 )) = u(g(s 1 )) = 15, u(f (s 4 )) = u(g(s 4 )) = 20.
Using Equation 1.5, we have SEU (f ) = (0.2×5)+(0.1×10)+(0.4×15)+(0.3×20) = 14 and SEU (g) = (0.2 × 15) + (0.1 × 20) + (0.4 × 5) + (0.3 × 20) = 13. So, f is preferred to g.

The axiomatic system of Savage

Like VNM's framework, the preference relation between acts has to satisfy a certain number of axioms of rationality. Before addressing the axiomatic system relative to Savage's approach for subjective expected utility we need to define some basic notions [START_REF] Savage | The Foundations of Statistics[END_REF]: Definition 1.3. (Constant act) A constant act f x ∈ F provides the same consequence x ∈ X, whatever the state of the nature:

∀s ∈ S, f x (s) = x.
Definition 1.4. (Compound act) Giving two acts f and g ∈ F and an event E ⊆ S. The compound act f Eg is defined by:

f Eg(s) = f (s) if s ∈ E, g(s) if otherwise.
This notion (of compound acts) is illustrated by Figure 1.2. Axiom. (Sav2: Sure Thing Principle) For all acts f, g, h, h ∈ F and for every event E ⊆ S:

f Eh gEh iff f Eh gEh .

Axiom. (Sav3: Conditioning over constant acts) For any not null event E ⊆ S, and any constant acts f x , g y ∈ F it holds that:

∀E ⊆ S, f x E g y iff ∀h ∈ F, f x Eh g y Eh.
Axiom. (Sav4: Projection from acts over events) For any consequences x, y, x , y ∈ X, for any constant acts f x , g y , f x , g y ∈ F. If x y and x y , then ∀E, D ⊆ S we have:

f x Eg y f x Dg y iff f x Eg y f x Dg y .
Axiom. (Sav5: Non triviality) ∃ f, g ∈ F, such that f g.

The use of Axiom Sav5 avoids the case of having only one consequence or the case where all consequences are equally preferred.

The basic axiom of Savage approach is the Sure Thing Principle (Sav2) that can be interpreted as follows: The preference order between two compound acts does not depend on their common consequences in a subset of S. Thus, Savage has showed that if the decision maker's preference among acts satisfies axioms Sav1 to Sav5 as well as two technical axioms of continuity and monotonicity, then this preference relation can be represented by an expected utility from the set of acts to the reals. So, for any act f , SEU (f ) is the expected utility of the consequence of f in the sense of a probability distribution on S. This implies the existence of a probability distribution p on S and a utility function u on X such that an act f is preferred to an another act g iff the subjective utility of f is higher than the subjective utility of g (SEU (f ) SEU (g)).

Conclusion

The popularity of the expected utility models is essentially based on two strong axiomatic justifications: Von Neumann and Morgenstern's axiomatic system for decision making under risk and Savage's axiomatization for decision making under uncertainty. However, it have been proved that these formalisms cannot represent all decision makers' behaviors. Allais [2] and Ellsberg [START_REF] Ellsberg | Risk, ambiguity, and the savage axioms[END_REF] questioned the axiomatic foundations for respectively VNM's and Savage approaches for expected utility.

Many research contributions have been proposed to overcome these limits, most of them are based on the Choquet integral [START_REF] Choquet | Theory of capacities[END_REF] that is probably the most well known criterion. The latter is based on a generalized measure of uncertainty and has proven to be an important tool for decision making under risk and uncertainty. Besides, we can cite the Rank-Dependent Utility criterion [START_REF]A theory of anticipated utility[END_REF] for decision under risk and its variants [START_REF] Segal | The measure representation: A correction[END_REF][START_REF] Yaari | The dual theory of choice under risk[END_REF] that have received an axiomatic justification.

These criteria involve the use of a quantitative representation of uncertainty. However, when the agent is unable to express his uncertainty and preferences numerically and he can only give an order among different alternatives, the previous criteria remain inappropriate. To solve such problems, qualitative decision models have been introduced with the emergence of other decision rules such as Sugeno integral [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF] decision rule that is considered as an ordinal counterpart of Choquet integral. In particular, one may consider qualitative possibilistic decision rules that have emerged with the growth of Possibility theory. These alternatives are detailed in the next Chapter.

CHAPITRE 2

Decision Making under Possibilistic uncertainty

Introduction

Despite its success, it was proved that probability theory is appropriate only when numerical information are available and it presents some limits in regards to the representation of total ignorance and modeling qualitative uncertainty. Moreover, in decision theory, it has been proved that individuals reasoning does not necessarily conform to expected utility's assumptions.

Giving up the probabilistic quantification of uncertainty, yields to give up the EU criterion as well. Possibility theory presents an alternative model that offers a natural and simple framework to handle all kind of uncertainty, especially qualitative uncertainty and total ignorance. The development of possibilistic decision theory has lead to the proposition and the characterization of several possibilistic decision rules, namely, optimistic and pessimistic utilities that are qualitative counterparts of the EU criterion.

In this chapter, we will first give some basic elements of possibility theory in Section 2.2. Then in Section 2.3, we will present possibilistic decision rules, in particular pessimistic and optimistic utilities. Finally, in Section 2.4 we will focus on the axiomatization of pessimistic and optimistic utilities and we will detail their axiomatic systems in both VNM and Savage styles.

Basics on possibility theory

Possibility theory is a framework to handle uncertainty issued from Fuzzy Sets theory. It has been introduced by Zadeh [START_REF] Zadeh | Fuzzy sets as a basis for theory of possibility[END_REF] and further developed by Dubois and Prade [START_REF] Dubois | Possibility Theory: An Approach to Computerized Processing of Uncertainty (traduction revue et augmentée de Théorie des Possibilités)[END_REF][START_REF] Dubois | The treatment of uncertainty in knowledge-based systems using fuzzy sets and possibility theory[END_REF].

Possibility distribution

The concept of possibility distribution is the core of possibility theory and allows to represent qualitative knowledge about the real world. A possibility distribution π maps each state s in the universe of discourse S to a degree in a linearly ordered scale V , exemplified by [0, 1]. The values of this measure is interpreted as in table 2.1.

π(s) = 0 s is impossible π(s) = 1 s is totally possible π(s) > π(s ) s is preferred to s (or is more plausible) Table 2.

1: Possibility distribution π

The possibilistic scale V can be interpreted in two manners: -In the numerical or quantitative interpretation, the values of the possibility distribution make sense. -In the ordinal or qualitative interpretation, the possibility degrees reflect only an order between the possible values.

Independently of the used scale, the extreme cases of knowledge are complete knowledge and total ignorance. In the first case, we assign 1 to a state s 0 (totally possible) and 0 otherwise, i.e. ∃ s 0 , π(s 0 ) = 1 and ∀s = s 0 , π(s) = 0. In the second one, we assign 1 to all situations i.e. π(s) = 1, ∀s ∈ S.

A possibility distribution π is said to be normalized if there exists at least one element of S which is totally possible. max s∈S π(s) = 1.

(2.1)

Possibility and necessity measures

In probability theory, uncertain knowledge about any event E is represented by a single probability measure P. This measure is auto-dual i.e. we can deduce the probability degree assigned to E from the probability P of its complement (¬E):

P (E) = 1 -P (¬E).
In the contrary, possibility theory is characterized by the use of two dual measures: the possibility measure Π and necessity measure N .

• Possibility measure Π: Given a possibility distribution π, the possibility of any event E ⊆ S is defined by:

Π(E) = max s∈E π(s). (2.2)
Π(E) denotes the possibility degree evaluating at which level E is consistent with the knowledge represented by π.

• Necessity measure N : Given a possibility distribution π, the necessity measure of an event E ⊆ S is defined by:

N (E) = 1 -Π(¬E) = min s∈E (1 -π(s)). (2.3)
N (E) denotes the necessity degree evaluating at which level E is certainly implied by the knowledge.

Example 2.1. Let us consider the possibility distribution π describing the opinion of a doctor concerning the diagnosis of a patient. The universe of discourse related to this problem is the set of three diseases (d 1 , d 2 , d 3 ) and a healthy case (h):

S = {d 1 , d 2 , d 3 , h}. π(d 1 ) = 0.5, π(d 2 ) = 1, π(d 3 ) = 0.7, π(h) = 0.
Note that π is normalized since max(0.5, 1, 0.7, 0) = 1. For instance, the possibility degree that the patient has disease d 1 is 0.5.

Consider an event E = {d 1 , d 3 } i.e. the patient suffers from d 1 or d 3 . Then, the possibility and the necessity measures of this event are:

• Π(E) = max(0.5, 0.7) = 0.7.

• N (E) = 1 -max(1, 0) = 0.

Possibilistic lotteries

Following Dubois and Prade's possibilistic approach to decision making under uncertainty, a decision can be seen as a possibility distribution over a finite set of outcomes [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF]. A decision can be represented by a possibility distribution on a set of consequences X, called a (simple) possibilistic lottery, denoted by L = λ 1 /x 1 , . . . , λ n /x n ; where λ j = π(x j ) is the possibility that the decision leads to consequence x j . This degree is also denoted by L[x j ].The outcome relative to each consequence x j can be represented by a utility function u j . Thus, we can rewrite the possibilistic lottery by L = λ 1 /u 1 , . . . , λ n /u n .

Similar to the notion of probabilistic lottery (detailed in Chapter 1 Section 3), Dubois and Prade have defined the notion of possibilistic compound lottery. Such a lottery is a normalized possibility distribution over a set of (simple or compound) lotteries and it is denoted by L = λ 1 /L 1 , . . . , λ m /L m , where λ i being the possibility of getting lottery L i according to L. The possibility π i,j of getting consequence x j from one of sub lotteries L i depends on the possibility λ i of getting L i and on the conditional possibility λ j i = π(x j | L i ) of getting x j from L i . So, we shall say that π i,j = min(λ i , λ j i ). Hence, the possibility of getting x j from a a lottery L = λ 1 /L 1 , . . . , λ m /L m is simply the max, over all L i 's, of π i,j .

In Dubois and Prade's possibilistic decision theory [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF], a compound lottery is assumed to be indifferent according to the decision maker's preference to the simple lottery defined by: The reduction of a compound lottery is polynomial in the size of the lottery since the min and the max operators are polynomial.

Reduction (L) = max i=1..m min(λ i , λ 1 i )/

Possibilistic decision criteria

The development of possibility theory has led to the emergence of several possibilistic decision rules depending on the (quantitative or qualitative) nature of information describing the decision problem.

These decision criteria can be gathered into four classes that differ according to the interpretation of the used scale to encode uncertainty and utility (ordinal or numerical) as well as the commensurability between these scales i.e. if we are able or not to measure possibility and utility using a common standard:

• Utility and possibility scales are commensurate and purely ordinal: In this class, we have possibilistic qualitative criteria namely optimistic (denoted by U opt ) and pessimistic (denoted by U pes ) [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF] integrals as well as possibilistic binary utilities (denoted by P U ) [START_REF] Giang | A comparison of axiomatic approaches to qualitative decision making using possibility theory[END_REF].

• Utility and possibility scales are commensurate: This category concerns the Order of Magnitude Utility (denoted by OM EU ) [START_REF] Pearl | From conditional oughts to qualitative decision theory[END_REF][START_REF] Wilson | An order of magnitude calculus[END_REF]. In the sequel of this Chapter, we present the definition of each of the above possibilistic decision rules. Especially we detail the pessimistic and optimistic utilities and we focus on their axiomatization, that constitutes the basis of our contribution (Part 2).

•

Pessimistic utility

In a possibilistic framework, the evaluation of a lottery consists of the combination of possibility degrees π (encoding uncertainty) and utilities u(x) (relative to possible consequences). To ensure this combination, Dubois and Prade [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF] have proposed pessimistic and optimistic criteria under the assumption that the uncertainty and utility scales are commensurate and purely ordinal. These decision rules constitute a qualitative counterpart to the expected utility criterion and depend on the decision maker behavior (an optimistic or pessimistic person).

The pessimistic criterion was initially defined by Whalen [START_REF] Whalen | Decision making under uncertainty with various assumptions about available information[END_REF] and it generalizes the Wald criterion [START_REF] Wald | Statistical decision functions[END_REF]. This criterion supposes that the decision maker considers the bad and plausible consequences. It estimates to what extent it is certain (i.e. necessary according to measure N) that L reaches a good utility. Definition 2.1. Let L = λ 1 /x 1 , . . . , λ n /x n be a possibilistic lottery, the pessimistic utility of L, denoted by U pes is computed as follows:

U pes (L) = max i=1..n min(u(x i ), n(L[x i ])).
(2.5)

where n is an order reversing function (e.g. n(L[x]) = 1 -L [x]).

Particular values for U pes are as follows:

• If L assigns 1 to the worst utility (u ⊥ ) and 0 to all other utilities then U pes (L) = 0.

• If L assigns 1 to the best utility u and 0 to all other utilities then U pes (L) = 1.

Example 2.3. Let L = 1/0.2, 0.7/0.5, 0.4/0.6 and L = 1/0.8, 0.3/0.7, 0.5/0.9 be two possibilistic lotteries.

Using Equation 2.5 we have:

• U pes (L) = min(max(0.2,0),max(0.5,0.3),max(0.6,0.6)) = 0.2.

• U pes (L ) = min(max(0.8,0),max(0.7,0.7),max(0.9,0.5)) = 0.7.

⇒ U pes (L ) > U pes (L) so L Upes L.

Dubois and Prade have proposed an adaptation of the pessimistic utility to evaluate acts in style of Savage. The definition of this decision rule is as follows: Definition 2.2. Given a possibilistic distribution π over S and a utility function u on the set of consequences X, the pessimistic utility of an act f is defined by:

U pes (f ) = min s i ∈S max(u(f (s i )), 1 -π(s i )).
(2.6)

Optimistic utility

The optimistic criterion was initially proposed by Yager [START_REF] Yager | Possibilistic decision making[END_REF][START_REF] Yager | The Ordered Weighted Averaging Operators: Theory and Applications[END_REF] and it can be seen as a mild version of the maximax criterion. This criterion estimates to what extend it is possible that L reaches a good utility. It captures the optimistic behavior of the decision maker that makes at least one of the good consequences highly plausible.

Definition 2.3. Let L = λ 1 /x 1 , . . . , λ n /x n be a possibilistic lottery, the optimistic utility of L, denoted by U opt is computed as follows:

U opt (L) = max i=1..n min(u(x i ), L[x i ]). (2.7)
Example 2.4. Let L = 1/0.2, 0.7/0.5, 0.4/0.6 and L = 1/0.8, 0.3/0.7, 0.5/0.9 be two possibilistic lotteries.

Using Equation 2.7 we have:

• U opt (L) = max(min(0.2,1),min(0.5,0.7),min(0.4,0.6)) = 0.5.

• U opt (L ) = max(min(1,0.8),min(0.3,0.7),min(0.5,0.9)) = 0.8.

⇒ U opt (L ) > U opt (L) so L Uopt L.
Particular values for U opt are as follows:

• If L assigns 1 to the worst utility (u ⊥ ) and 0 to all other utilities then U opt (L) = 1.

• If L assigns 1 to the best utility (u ) and 0 to all other utilities then U opt (L) = 0.

Similar to its pessimistic counterpart, this criterion was also defined in Savage framework to choose among acts rather than lotteries. Its definition is as follows:

Definition 2.4. Given a possibilistic distribution π over a set S and a utility function u on a set of consequences X, the optimistic utility of an act f is defined by:

U opt (f ) = max s i ∈S min(u(f (s i )), π(s i )). (2.8)
It is important to note that the pessimistic and optimistic utilities represent particular cases of a more general criterion based on Sugeno integrals [START_REF] Dubois | The use of the discrete sugeno integral in decision-making: A survey[END_REF][START_REF]An axiomatic approach of the discrete sugeno integral as a tool to aggregate interacting criteria in a qualitative framework[END_REF][START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF]:

S γ,u (L) = max λ∈[0,1] min(λ, γ(F λ )). (2.9)
where F λ = {s i ∈ S, u(f (s i )) ≥ λ}, is a set of preferred states for act f. γ is a monotonic set-function that reflects the decision maker attitude toward uncertainty. U opt is recovered when γ is the possibility measure Π and U pes is recovered when γ corresponds to necessity measure N.

Other possibilistic decision rules Binary utilities (PU)

Binary possibilistic utility is a qualitative decision criterion that unifies the pessimistic and optimistic utilities. It has been proposed and axiomatized by Giang and Shenoy [START_REF] Giang | A comparison of axiomatic approaches to qualitative decision making using possibility theory[END_REF][START_REF] Giang | Two axiomatic approaches to decision making using possibility theory[END_REF] considering the importance of the best and the worst lotteries when making decision. In this bipolar model, the utility of an outcome is represented by a pair u = u, u where max(u, u) = 1. u is interpreted as the possibility of getting the ideal, good reward (denoted ) and u is interpreted as the possibility of getting the anti ideal, bad reward (denoted ⊥).

The lottery λ 1 /u 1 , . . . , λ n /u n can be seen as a compound lottery, where each u i = u i , u i is considered as a basic lottery u i / , u i /⊥ . Hence, the evaluation of this lottery comes down to the evaluation of its reduction such that: Definition 2.5. Let L = λ 1 /u 1 , . . . , λ n /u n be a possibilistic lottery, the binary utility of L denoted by P U is computed as follows:

P U ( λ 1 /u 1 , . . . , λ n /u n ) = Reduction(λ 1 / u 1 / , u 1 /⊥ , . . . , λ m ∧ u n / , u n /⊥ ) = max j=1..m (min(λ j , u j ))/ , max j=1..m (min(λ j , u j ))/⊥ (2.10)
As qualitative utilities and many other qualitative decision rules, binary utility suffers from a lack of decisiveness. However, a refinement has been proposed to obtain a more discriminating criterion [START_REF] Weng | An axiomatic approach to qualitative decision theory with binary possibilistic utility[END_REF][START_REF] Weng | Qualitative decision making under possibilistic uncertainty: Toward more discriminating criteria[END_REF].

The possibilistic likely dominance LN and LΠ

This criterion was proposed to make decisions when the utility and possibility scales are not commensurate [START_REF] Dubois | Qualitative decision theory with preference relations and comparative uncertainty: an axiomatic approach[END_REF][START_REF] Fargier | Qualitative models for decision under uncertainty without the commensurability assumption[END_REF]. It does not assign global utilities to decisions but compare them using a pairwise comparison between alternatives, hence the particularity of this decision rule. Possibilistic likely dominance can be defined in the ordinal setting by LN or in the numerical setting by LΠ.

Giving two possibilistic lotteries

L 1 = λ 1 1 /x 1 1 , . . . , λ 1 n /x 1 n and L 2 = λ 2 1 /x 2 1 , . . . , λ 2 n /x 2
n , we say that "L 1 is as least as good as L 2 " as soon as the possibility (in the case of LΠ) or the necessity (in the case of LN ) of the event "the utility of L 1 is as least as good as the utility of L 2 " is greater or equal to the likelihood (possibility or necessity) of the event "the utility of L 2 is as least as good as the utility of L 1 ". Formally: Definition 2.6. Let L = λ 1 /x 1 , . . . , λ n /x n be a possibilistic lottery, the possibility likely dominance relations LN and LΠ are defined as follows:

L 1 LN L 2 iff N (L 1 ≥ L 2 ) ≥ N (L 2 ≥ L 1 ).
(2.11)

where

N (L 1 ≥ L 2 ) = 1 - max u 1 i ,u 2 j s.t u 1 i <u 2 j (min(λ 1 i , λ 2 j )). L 1 LΠ L 2 iff Π(L 1 ≥ L 2 ) ≥ Π(L 2 ≥ L 1 ).
(2.12)

where

Π(L 1 ≥ L 2 ) = max u 1 i ,u 2 j s.t u 1 i ≥u 2 j (min(λ 1 i , λ 2 j )).

Order of Magnitude Expected Utility (OMEU)

Order of magnitude expected utility is based on "disbelief functions" or "Kappa-rankings" measures initially proposed by [START_REF] Spohn | Ordinal conditional functions : a dynamic theory of epistemic states[END_REF]. A measure κ : 2 S → Z + ∪ {+∞} is a kappa-ranking iff:

• min s∈S κ(s}) = 0 • κ(E) = min s∈E κ({s}) if ∅ = E ⊆ S, κ(∅) = +∞
This criterion have received an interpretation in term of order of magnitude of "small" probabilities. Hence, "κ(E) = i" is equivalent to P (E) is of the same order of ε i , for a given fixed infinitesimal ε. In this context, an event E is more likely than event D if and only if κ(E) < κ(D).

In [START_REF] Dubois | Possibilistic logic, preferential models, non-monotonicity and related issues[END_REF], authors have pointed out that there exists a close link between kappa-rankings and possibility measures, insofar as any kappa-ranking can be represented by a possibility measure, and vice versa. Thus, order of magnitude utilities have been defined in the same way to rank outcomes in term of dissatisfaction degrees [START_REF] Pearl | From conditional oughts to qualitative decision theory[END_REF][START_REF] Wilson | An order of magnitude calculus[END_REF].

Definition 2.7. Let L = λ 1 /x 1 , . . . , λ n /x n an order of magnitude lottery, the order of magnitude of the expected utility of L is computed as follows:

OM EU (L) = min i=1,n {λ i + u(x i )} (2.13)

Possibilistic Choquet integrals

When the decision problem is defined using heterogeneous information and the knowledge about states of nature is possibilistic and the utility degrees are cardinal, then Choquet integrals seem to be an appropriate decision rule to consider. This criterion allows the use of any monotonic set function µ, also called a capacity or fuzzy measure that may be a probability measure, necessity measure, possibility measure, or belief functions measure etc.

In the case of possibilistic decision problem and considering the decision maker behavior, we use the necessity-based Choquet integrals (µ = N) for cautious decision makers and the possibilitybased Choquet integrals (µ = Π) for adventurous ones. Hence the definition of possibilistic Choquet integrals is as follows: Definition 2.8. Let L = λ 1 /u 1 , . . . , λ n /u n a possibilistic lottery, the necessity-based Choquet integrals of L denoted by Ch N (L) is defined by:

Ch N (L) = u 1 + i=2..p (u i -u i-1 ) × N (L ≥ u i ).
(2.14)

The possibility-based Choquet integrals of L denoted by Ch Π (L) is defined by:

Ch Π (L) = u 1 + i=2..p (u i -u i-1 ) × Π(L ≥ u i ).
(2.15)

Axiomatization of pessimistic and optimistic utilities

Under the assumption that the utility and the possibility scales are commensurate and purely ordinal, Dubois and Prade [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF] have proposed pessimistic and optimistic utilities to evaluate decisions. Similar to their probabilistic counterpart, these criteria have received a theorical characterization in both VNM and Savage frameworks. These axiomatic systems are detailed in the remaining of this Section.

Axiomatization in the style of VNM Qualitative (pessimistic and optimistic) utilities have been axiomatized in the style of VNM [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF] to characterize preference relations between possibilistic lotteries.

Axiomatization of U pes in the style of VNM

Let be a preference relation on a set of possibilistic lotteries L. The axiomatic system relative to the pessimistic utility U pes , proposed by Dubois and Prade [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF] relies on the following axioms:

Axiom. (A1: Total pre-order) is complete and transitive.

Axiom.

(A2: Certainty equivalence) ∀Y ⊆ X, ∃x ∈ Y s.t. x (L[x] =1; L[y] = 0 ∀y = x) and Y (L[y] =1 ∀y ∈ Y ; L[y] = 0 otherwise) are equivalent for . Axiom. (A3 -:Risk aversion) ∀x ∈ X, if L[x] ≤ L [x] (L[x] is more specific than L [x]), then L L .
Axiom. (A4: Independence) If L and L are equivalents, then λ/L, µ/L and λ/L , µ/L are also equivalents, for any λ, µ s.t. max(λ, µ) = 1.

Axiom. (A5: Reduction of lotteries) For any (compound possibilistic lottery) L, L ∼ Reduction(L).

Axiom. (A6

-: Continuity) ∀x ∈ X, if L [x] ≤ L[x] then ∃λ s.t. L ∼ 1/L, λ/X .
In 1998, Dubois et al. [START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF] have performed a deeper study of this characterization and they have provided an axiomatizatic system with a lower number of axioms. Just four axioms are necessary and sufficient for the representation theorem of the pessimistic utility.

In fact, authors have shown that it is possible to ignore the use of Axiom A5 relative to reduction of compound lotteries since it is implicitly obtained by the definition of possibilistic lotteries. Besides, they have proved that Axiom A2 is also useless and redundant since it is a consequence of the use of Axiom A1, Axiom A4 and Axiom A6 -. Thus, a new axiomatic system was proposed for pessimistic utility. It encompasses Axiom A1, Axiom A3 -, Axiom A4 and a new form of the continuity axiom (Axiom A6 -') that is defined by:

Axiom. (A6 -': Continuity) ∀x ∈ X, ∀L[x], ∃λ ∈ [0, 1] s.t. L[x] ∼ 1/u , λ/u ⊥ .
Where u and u ⊥ are respectively the best and the worst utility. The detailed axiomatic system has allowed Dubois and Prade to provide a representation theorem relative to the pessimistic utility such that: Theorem 2.1. If a preference relation on L satisfies axioms A1 . . . A6 -(or axioms A1, A3 -, A4 and A6 -') then there exists a possibility distribution π: S → [0, 1], an order reversing and a utility function u: X → [0, 1] such that:

L L iff U pes (L) ≥ U pes (L ).
(2.16)

Axiomatization of U opt in the style of VNM

In their work [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF], Dubois et al. have defined the characterization of the optimistic utility U opt from the axiomatization relative to the pessimistic utility by replacing axioms A3 -and A6 -by their optimistic counterparts i.e. axioms A3 + and A6 + defined by:

Axiom. (A3 + : Uncertainty attraction) ∀x ∈ X, if L[x] ≥ L [x] (L [x] is more specific than L[x]), then L L. Axiom. (A6 + : Continuity) ∀x ∈ X, if L [x] ≤ L[x] then ∃λ s.t. L ∼ λ/L, 1/X .
Furthermore, in [START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF] they have provided an improved axiomatic system for the optimistic utility by resuming axioms A1 and A4 that are the same as the pessimistic case, replacing Axiom A3 -by Axiom A3 + and finally providing an optimistic counterpart of Axiom A6 -' such as:

Axiom. (A6 + ': Continuity) ∀x ∈ X, ∀L[x], ∃λ ∈ [0, 1] s.t. L[x] ∼ λ/u , 1/u ⊥ .
Where u and u ⊥ are respectively the best and the worst utility.

Considering those axioms, the representation theorem relative to the optimistic utility is defined as the following [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF]: Theorem 2.2. If a preference relation on L satisfies axioms A1 . . . A6 + (or axioms A1, A3 + , A4 and A6 + ') then there exists a possibility distribution π: S → [0, 1] and a utility function u:

L → [0, 1] such that: L L iff U opt (L) ≥ U opt (L ).
(2.17)

Axiomatization in the style of Savage

Axiomatization of U pes in the style of Savage

As mentioned before, in Savage framework, preference relations are defined over acts rather than lotteries. In this context, Dubois et al. have provided an axiomatic system for U pes [START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF][START_REF] Dubois | Qualitative decision theory with sugeno integrals[END_REF]. Considering a set of acts F and a set of consequences X, this axiomatic system is defined by the following axioms:

Axiom. (Sav1: Complete pre-order) The preference relation is reflexive, complete and transitive.

Axiom. (Sav5: Non triviality) ∃ f, g ∈ F, such that f g.

These axioms are the same axioms proposed by Savage. However, authors have proposed a weak version of Axiom Sav3 defined by: Axiom. (W Sav3: Weak coherence with constant acts) For any not null event E ⊆ S, f x and g y two constant acts, then

f x E g y ⇒ f x Eh g y Eh, ∀h ∈ F.
Besides, authors have proposed two additional axioms reflecting the decision maker behavior.

Axiom. (RDD: Restricted disjunctive dominance) Let f and g be any two acts and a constant act f x of value x: f g and f f x ⇒ f g ∨ f x (where g ∨ f x gives the best of the results of g(s) and f x (s) in each state s).

Axiom. (P es:

Pessimism) ∀f, g ∈ F and any event E ⊆ S. If f Eg f then f gEf .
Axiom RDD is interpreted as follows: if an act f is preferred to an act g and also preferred to a constant act f x , then f still preferred to g even if the worst consequences of g are improved to the value x. Axiom P es implies that if changing f into g may improve the expectation of act f when ¬E occurs then there is no way to improve the act by changing f into g when E occurs. On the basis of this axiomatic system, [START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF][START_REF] Dubois | Qualitative decision theory with sugeno integrals[END_REF] have proposed a representation theorem of the pessimistic utility as follows:

Theorem 2.3. If a preference relation on acts satisfies the axioms Sav1, Sav5, W Sav3, RDD and P es then there exists a utility function u: X → [0, 1] and a possibility distribution π: S → [0, 1] such that ∀f, g ∈ F:

f g iff U pes (f ) ≥ U pes (g).
(2.18)

Axiomatization of U opt in the style of Savage

The axiomatic system of U opt in the context of Savage shares some axioms with its pessimistic counterpart namely: axioms Sav1, Sav5 and W Sav3. The remaining axioms are:

Axiom. (RCD: Restricted conjunctive dominance) Let f and g be any two acts and [x] be a constant act of value x: g f and f x f ⇒ g ∧ f x f (where g ∧ f x gives the worst of the results of g(s) and f x (s) in each state s).

Axiom. (Opt

: Optimism) ∀f, g ∈ F and E ⊆ S. If f f Eg then gEf f .
Axiom RCD is the dual property of the restricted disjunctive dominance. It allows a partial decomposability of qualitative utility with respect to the conjunction of acts in the case where one of them is constant. Axiom Opt implies that changing f into g does not improve the expectation of act f when ¬E occurs. However, we can form a better act by changing f into g when E occurs.

Using the axioms presented above, Dubois and Prade [START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF][START_REF] Dubois | Qualitative decision theory with sugeno integrals[END_REF] have proposed the following representation theorem of optimistic utility: Theorem 2.4. If a preference relation on acts satisfies axioms Sav1, Sav5, W Sav3, RCD and Opt then there exists a utility function u: X → [0, 1] and a possibility distribution π: S → [0, 1] such that ∀f, g ∈ F:

f g iff U opt (f ) ≥ U opt (g). (2.19)
Note that in [START_REF] Bouyssou | Decision-making process -Concepts and Methods[END_REF], Dubois et al. have proposed to replace axioms RCD and RDD by a noncompensation assumption defined as follows:

Axiom. (N C: Non Compensation) Whatever E ⊆ S, f x , g y ∈ F: h Eg y ∼ g y or h Eg y ∼ h Eh ⊥ f x Eh ⊥ ∼ f x or f x Eh ⊥ ∼ h Eh ⊥
where h (resp. h ⊥ ) is the constant act that gives always the best (resp. worst) consequence (resp. ⊥).

Conclusion

In this chapter, we have presented an overview of possibility theory that offers a flexible and simple framework to represent uncertainty as well as the main possibilistic decision rules. We especially investigated qualitative utilities (U opt and U pes ) and their axiomatic systems in both VNM and Savage frameworks.

As mentioned before, these criteria present the qualitative counter part of the expected utility model and constitute the groundwork of our contribution (Part 2). We have chosen these decision rules among others because we are interested to make decisions in a purely ordinal context and assuming a certain form of commensurability between the plausibility and the utility scales. Besides, these criteria have received a solid axiomatic justification that guarantee the rationality of the decision making process considering the decision maker attitude.

CHAPITRE 3

Collective Decision Making

Introduction

A Multi-Agent System (MAS) includes several entities (called agents) interacting within a common environment. An agent can be a virtual or physical autonomous entity such as software programs, robots, or human beings. Each interacts with others in order to meet preset goals or objectives according to available resources and skills. This paradigm describes many situations in real world problems, especially, collective decision making where decisions involves a group of agents instead of a single one.

In this context, the main issue is how to make a decision that satisfies everybody. However, decision theory as presented in the previous chapters appears inappropriate to answer this question. So, it was necessary to provide an extension of this discipline to be able to handle not only the preferences of one decision maker but all concerned ones. Hence, the development of collective decision theory. This chapter focuses on the basics of collective decision theory and especially on Harsanyi's theorem and works relative to social choice theory. The remaining of this chapter is structured as follows: Section 3.2 defines utilitarian and egalitarian collective utility functions. Section 3.3 details Harsanyi's theorem regarding collective decision making under risk, in the style of VNM's expected utility framework. Finally, Section 3.4 is devoted to study the main proposed extensions and criticisms relative to Harsanyi's theory.

Collective utility functions

In collective decision problems, we suppose that agents are able to express their satisfaction over alternatives by a cardinal or ordinal preference relation. Then, the collective utility function (CUF) is the result of aggregating individual preferences (see [START_REF] Moulin | Axioms for Cooperative Decision making[END_REF] for more details).

Formally, we define a collective decision problem by a set A = {1, . . . , p} of agents, where each agent i ∈ A is supposed to express his preferences on a set of consequences X, by a ranking function or a utility function u i that associates to each element of X a value in a subset of R + (typically in the interval [0, 1]). Thus to solve this problem, we need to define for each x ∈ X a collective utility degree that reflects the collective preference.

When the collective preference depends only on individual utilities, it can be obtained by a collective utility function of the form Agg(x) = f (u 1 (x), . . . , u p (x)).

Utilitarian collective utility functions

Classical utilitarian utility theory prescribes that the best decisions are those which maximize the sum of individual utilities [START_REF] Fuhrken | Additive utility[END_REF][START_REF] Moulin | Axioms for Cooperative Decision making[END_REF]. This collective utility function that is also known as Benthamite social welfare function can be defined as follows: Definition 3.1. Given a set of agents A, a consequence x ∈ X and a set of utility functions u i (x), where u i (x) is the utility of x according to agent i, the additive collective utility function Agg sum is defined by:

Agg sum (x) = Σ i∈A u i (x) (3.1)
In the case where agents don't have the same importance (e.g. in an administration board or direction committee), an importance degree or a weight w i is associated to each i where the agent where the highest weight is the most important. This leads to the use of a weighted sum:

Agg sum (x) = Σ i∈A w i × u i (x) (3.2)
Example 3.1. Consider a consequence x ∈ X and two agents 1 and 2 where the utility of x relative to each agent is respectively u 1 (x) = 0.4 and u 2 (x) = 0.3. When agents have the same importance, their collective utilitarian utility can be computed using Equation 3.1 as follows:

Agg sum (x) = 0.4 + 0.3 = 0.7.
However in the case where agents are not equally important, example agent 1 is more important than agent 2 with w 1 = 0.5 and w 2 = 0.2. The collective weighted utilitarian utility is performed using Equation 3.2 as follows:

Agg sum (x) = 0.4 × 0.5 + 0.3 × 0.2 = 0.26.
This function has several good properties [START_REF] Gerard | Topological methods in cardinal utility theory[END_REF][START_REF] Gorman | The structure of utility functions[END_REF] but fails to ensure equity between agents.

Egalitarian collective utility functions

Contrary to the utilitarian approach, the egalitarian approach proposes to maximize the satisfaction of the least satisfied agent. This collective utility function is defined by: Definition 3.2. Given a set of agents A, a consequence x ∈ X and a set of utility functions u i (x), where u i (x) is the utility of x according to agent i, the egalitarian utility function is defined by:

Agg min (x) = min i∈A u i (x) (3.3)
When the agents are not equally important, a weight w i can be associated to each agent i. The collective utility is then defined in a conjunctive (cautious) way using a weighted minimum:

Agg min (x) = min i∈A max((1 -w i ), u i (x)) (3.4)
Example 3.2. Consider a consequence x ∈ X and two agents 1 and 2 where the utility of x relative to each agent is respectively u 1 (x) = 0.4 and u 2 (x) = 0.3. When these agents have the same importance, the egalitarian utility function can be computed using Equation 3.3 as follows:

Agg min (x) = min (0.4 , 0.3) = 0.3.
In the case where agents are not equally important, example agent 1 is more important than agent 2 such that w 1 = 0.5 and w 2 = 0.2, the weighted egalitarian utility can be computed using Equation 3.4 such that:

Agg min (x) = min(max((1 -0.5), 0.4), max((1 -0.2), 0.3)) = 0.5.
Notice that a non-egalitarian (max oriented) counterpart of the egalitarian utility can be used to aggregate agents' preferences using a disjunctive aggregation. This collective utility function can be defined for the case when agents have same importance (Equation 3.5) as well as the case when they are not equally important (Equation 3.6) as follows 1 :

Agg max (x) = max i∈A u i (x) (3.5) Agg max (x) = max i∈A min(w i , u i (x)) (3.6)

Harsanyi's Theorem and related concepts

In the presence of risk, i.e. when the information about states of nature is probabilistic, the most popular criterion to compare decisions is the expected utility. In this context, an elementary decision is modeled by a probabilistic lottery over a set X of its possible outcomes. The preferences of the decision maker are supposed to be captured by a utility function assigning a numerical value to each consequence. The evaluation of a lottery is performed through the computation of its expected utility (the higher is the better).

When several agents are involved, the aggregation of individual preferences under risk raises a particular problem depending on when the utility of the agents is to be evaluated, before or after the consideration of uncertainty. This yields two different approaches that are the ex-ante and ex-post aggregations.

ex-ante and ex-post aggregations

In collective decision making problem under risk, we have to specify the operator used to aggregate the individual utilities: the sum operator for the utilitarian approach or the min in the case of egalitarianism. However, it is necessary also to define the moment to consider uncertainty. Hence, the definition of the ex-ante and ex-post approaches:

• The ex-ante approach consists in computing separately the (EU i ) expected utility for each agent i considering the uncertainty and then perform the aggregation of these expected utilities.

• The ex-post approach combines the decision makers utilities and determines the collective utility function (CUF) for each consequence x by defining the collective utility Agg(x) and then considers the uncertainty. It comes down to a problem of mono-agent decision making under uncertainty (this agent being "the collectivity").

This terminology has been introduced in economics and social welfare theory and then it has been extended to several fields related to collective decision making such as cooperative multi-agent system and especially Bayesian coalitional games [START_REF] Ieong | Bayesian coalitional games[END_REF].

Timing effect

In the probabilistic context, utilitarianism comes down to calculating either the collective expected utility of each consequence (ex-ante), or the aggregation of the individual expected utilities (expost) however both give exactly the same result. Egalitarianism prescribes to maximize either the expectation of the minimum of the satisfaction degrees or to compute the minimum of the mathematical expectations. The two approaches do not always coincide: this phenomenon have been identified by Myerson [74] as "Timing Effect" and it can be observed in the following counterexample.

Counter-example 3.1. Consider two agents 1 and 2 and two lotteries L 1 and L 2 on X = {x 1 , x 2 } depicted in Figure 3.1. The probability degrees for consequence x 1 (resp. x 2 ) are respectively 0.7 (resp 0.3) for L 1 and 0.2 (resp 0.8) for L 2 . The utility functions relative to consequences x 1 and x 2 for agent 1 (resp. agent 2) are defined such that: u 1 (x 1 ) = 0.3 and u 1 (x 2 ) = 1 (resp. u 2 (x 1 ) = 0.5 and u 2 (x 2 ) = 0.4).

The expected value of the minimum of the utilities are:

0.7 × min(0.3, 0.5) + 0.3 × min(1, 0.4) = 0.33 f or L 1 0.2 × min(0.3, 0.5) + 0.8 × min(1, 0.4) = 0.38 f or L 2 So ex-post, L 2 L 1 .
On the contrary, using ex-ante, computing the minimum of the expected utilities leads to L 1 L 2 , since:

min(0.7 × 0.3 + 0.3 × 1, 0.7 × 0.5 + 0.3 × 0.4) = 0.47 f or L 1 min(0.2 × 0.3 + 0.8 × 1, 0.2 × 0.5 + 0.8 × 0.4) = 0.42 f or L 2 . 0.7 0.3 x 1 : <0.3, 0.5> L 1 x 2 : <1, 0.4> 0.2 0.8 x 1 : <0.3, 0.5> L 2
x 2 : <1, 0.4> It has been proved that in the case of egalitarian decision making under risk, the size of the problem may considerably affect the coincidence between ex-ante and ex-post aggregation [START_REF] Lumet | Modélisation, représentation et résolution de problèmes de partage équitable de biens invisibles soumis au risque[END_REF]. In other words, the greater the number of uncertain states of the world is, more the possibility of equity between the two approaches is rare.

Moreover, the author has proved in the same work that in an egalitarian context, the only way to obtain equity between ex-ante and ex-post collective expected utilities is to consider that the less satisfied agent is always the same and this for any consequence x ∈ X.

The timing effect is not present in the probabilistic utilitarian approach, it has been proved that utilitarianism is the only way to avoid this problem in presence of risk. This conclusion is due to Harsanyi's contribution to social welfare theory [START_REF] Harsanyi | Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility[END_REF], that has pervaded the literature until now. This result and related work are the subject of the remaining of this chapter.

Harsanyi's representation theorem

Following Fleming [START_REF] Fleming | A cardinal concept of welfare[END_REF], Harsanyi provided a representation theorem for collective decision making in the context of Von Neumann and Morgenstern's expected utility theory [START_REF] Harsanyi | Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility[END_REF]. This theorem is often interpreted as a justification of utilitarianism and it is based on three fundamental axioms, detailed in the following.

Agg(x) = i∈A λ i × u i (x) (3.7)
Under the assumption of anonymity, Harsanyi proved that Agg(x) can be written as the sum of individual utilities (Agg(x) = i∈A u i (x)). On the basis of Harsanyi's results, Myerson [START_REF] Myerson | Utilitarianism, egalitarianism, and the timing effect in social choice problems[END_REF] has proved that in presence of risk only the use of an affine collective aggregation function allows to overcome the Timing Effect problem. Conversely; in the probabilistic case; any attempt to introduce equity causes a divergence between the ex-post and ex-ante approaches.

Beyond Harsanyi's theorem

Many researches have surrounded Harsanyi's aggregation theorem by proposing several variants and criticisms. The main related works are detailed in the following.

Extension of Harsanyi's theorem

Harsanyi's aggregation theorem has been questioned w.r.t. weights λ i defined in Equation 3.7. In the initial contribution, these weights are not necessary positive. This problem was naturally solved by strengthening Pareto Indifference [START_REF] Meyer | A note on affine aggregation[END_REF] into Strong Pareto condition that is defined by: Axiom. (SP: Strong Pareto) If each agent weakly prefers L 1 to L 2 (∀j = i,L 1 j L 2 ) and at least one of them strictly prefers L 1 to L 2 (L 1 i L 2 ) then the collectivity strictly prefers lottery

L 1 to L 2 (L 1 L 2 ).
Moreover, the problem of negative weights can also be solved using a weak version of Pareto (i.e. Weak Pareto axiom) defined as follows:

Axiom. (WP: Weak Pareto) If each agent weakly prefers L 1 to L 2 (∀i,L 1 i L 2 ) then the collectivity weakly prefers lottery

L 1 to L 2 (L 1 L 2 ).
Further, Fishburn [START_REF] Fishburn | On harsanyi's utilitarian cardinal welfare theorem[END_REF] and Coulhon and Mongin [START_REF] Coulhon | Social choice theory in the case of von neumann-morgenstern utilities[END_REF] pointed out that weights may be not uniquely defined. In order to solve this problem, Mongin et al. [START_REF] Mongin | Consistent bayesian aggregation[END_REF] have proposed the following Independent Prospects assumption as an additional condition to ensure uniqueness.

Axiom. (Independent Prospects) For every agent i there exists a pair of lotteries for which he is not indifferent. Although, Domotor [START_REF] Domotor | Ordered sum and tensor product of linear utility structures[END_REF] and Border [START_REF] Border | More on harsanyi's utilitarian cardinal welfare theorem[END_REF] have considered that this condition is unnecessary and that it is implicitly used as structural assumption by Harsanyi.

Since its emergence a panoply of works have been proposed to extend Harsanyi's Theorem, more recent ones are [START_REF] Chambers | Preference aggregation with incomplete information[END_REF][START_REF] Fleurbaey | Social rationality, separability, and equity under uncertainty[END_REF][START_REF] Gajdos | Decisions with conflicting and imprecise information[END_REF] that have been developed to confirm Harsanyi's approach and to extend it to deal with the case of an infinite population or agents with incomplete information.

Criticisms and impossibility results

Diamond [START_REF] Diamond | Cardinal welfare, individualistic ethics, and interpersonal comparison of utility: Comment[END_REF] was the first to challenge Harsanyi's result, and especially the use of the VNM expected utility to express the collective preference. He proposed to abandon VNM's expected utility axioms in favor of the egalitarianism. He illustrated his argumentation on the basis of this classical example: Example 3.3. Consider two agents 1 and 2, and two equally probable situations; say tossing a fair coin. Let L and L two probabilistic lotteries (presented in Figure 3.2) describing two cases: In the first case (lottery L), whatever the result of tossing, agent 1 gets everything and agent 2 gets nothing. In the other case, agent 1 gets everything if head and agent 2 gets everything if tails. [START_REF] Diamond | Cardinal welfare, individualistic ethics, and interpersonal comparison of utility: Comment[END_REF] Considering Harsanyi's axioms these two decisions are equivalent, and the ex-ante and expost aggregations give the same results. In fact, for the ex-ante aggregation we have:

U (L 1 ) = [0.5 × (ee +0)] + [0.5 × (ee +0)] =ee U (L 2 ) = [0.5 × (ee +0)] + [0.5 × (0+ee)] =ee
The same result is also obtained using the ex-post aggregation such that:

U (L 1 ) = [(0.5×ee) + (0.5 × 0)] + [(0.5×ee) + (0.5 × 0)] =ee U (L 2 ) = [(0.5×ee) + (0.5 × 0)] + [(0.5 × 0) + (0.5×ee)] =ee
However, from an ethical point of view lottery L 2 is better than L 1 because in L 1 , for any situation (head or tail) agent 1 gets every thing U 1 (L 1 ) =ee and

U 2 (L 1 ) = 0. While, in L 2 each agent can have half reward U 1 (L 2 ) = U 2 (L 2 ) =e.
Diamond pointed out this problem and deduced from this example that social preference may violate axiom Hars2, and more precisely the independence axiom of VNM's approach.

The Harsanyi-Diamond debate about the compelling nature of expected utility theory for collective decision making spawned a large literature. Besides, researchers were also motivated by the notion of subjective beliefs, that is more realistic. So, they gave up the VNM's expected utility in favor of subjective expected theory.

Hylland and Zeckhauser [START_REF] Hylland | The impossibility of bayesian group decision making with separate aggregation of beliefs and values[END_REF], Hammond [START_REF] Hammond | Ex-ante and ex-post welfare optimality under uncertainty[END_REF], Broome [START_REF] Broome | Weighing Goods: Equality, Uncertainty and Time[END_REF], Seidenfeld et al. [START_REF] Seidenfeld | On the shared preferences of two bayesian decision makers[END_REF], Mongin [START_REF] Mongin | Consistent bayesian aggregation[END_REF], many others and recently [START_REF]Harsanyi's theorem without the sure-thing principle: On the consistent aggregation of monotonic bernoullian and archimedean preferences[END_REF] have followed this line. All these works have provided the same conclusion i.e. the aggregation of individual preferences into a collective subjective expected utility is not so easy to perform. In fact, replacing VNM's formalism with a subjective one and assuming that individuals as well as the collectivity obey subjective expected utility axioms while considering the Pareto condition, may lead to a negative result. In other words, when individuals are simultaneously heterogeneous in terms of tastes and beliefs, imposing the satisfaction of subjective utility axioms for collective as well as individual preference relations leads to an impossibility result [START_REF] Mongin | Utility theory and ethics[END_REF].

To meet this challenge, Weymark [START_REF] Weymark | A reconsideration of the harsanyi-sen debate on utilitarianism[END_REF] and Mongin [START_REF] Mongin | Consistent bayesian aggregation[END_REF] have provided variants of Harsanyi's theorem using subjective probabilities instead of VNM lotteries. But, these works are relevant only under the assumption that all the agents have the same beliefs, i.e. same probabilities which is a strong hypothesis.

The negative results are generally obtained due to technical assumptions considering subjective uncertainty. More recent works, have founded their arguments on the incompatibility between Pareto properties and axioms related to the subjective expected uncertainty models. Authors like Broome [START_REF] Broome | Weighing Goods: Equality, Uncertainty and Time[END_REF], Gilboa, Samet and Schmeidler [START_REF] Gilboa | Utilitarian aggregation of beliefs and tastes[END_REF] condemn the Pareto property while others like Chambers and Hayashi [START_REF] Chambers | Preference aggregation under uncertainty: Savage vs. pareto[END_REF] have proved, following Savage's axiomatization, that Sav3 and Sav4 are not compelling at a social level. Despite their differences, the common conclusion of all these works is that it is impossible to perform the aggregation of social preferences under probabilistic uncertainty rather than risk, except for some special cases where all agents have the same probabilities and/or same utility functions [START_REF] Aspremont | A Welfarist Version of Harsanyi's Aggregation Theorem[END_REF][START_REF] Mongin | Consistent bayesian aggregation[END_REF]. Making a step further, Gajdos, Tallon and Vergnaud [START_REF] Gajdos | Representation and aggregation of preferences under uncertainty[END_REF] have shown that even by considering agents sharing homogenous beliefs, the collective aggregation cannot be proceeded unless an additional assumption defining individuals as well as society as uncertainty neutral.

In addition to this impossibility result [START_REF] Broome | Weighing Goods: Equality, Uncertainty and Time[END_REF][START_REF] Chambers | Preference aggregation under uncertainty: Savage vs. pareto[END_REF][START_REF] Gilboa | Utilitarian aggregation of beliefs and tastes[END_REF], it has been proved that the use of the subjective framework leads to a gap between results obtained using ex-ante or ex-post aggregations. The choice of the former or the latter is until now controversial and it constitutes an attractive subject for future research.

Conclusion

In this chapter we have presented the problem of collective decision making, especially aggregating decision makers' preferences, in presence of probabilistic uncertainty. We have presented the Harsanyi's Theorem which proves that the weighted sum of individual expected utilities is the only way to avoid the difference between ex-ante and ex-post aggregation in presence of risk.

We have also considered collective aggregation in subjective frameworks of expected utilities: It appears that the majority of these studies have concluded to the existence of an impossibility result considering agents with subjective beliefs. However, it has been shown that it is possible to define a representation theorem by relaxing some constraints i.e. supposing that agents have same knowledge or same utilities.

CHAPITRE 4

Sequential decision making and decision trees

Introduction

In the previous chapters, we have been interested only in situations where just one decision has to be taken (one-stage decision making problems). However, in real world problems the decision maker is often facing a succession of decisions to be taken over time, i.e. sequential decision problems.

Graphical decision models such as decision trees [START_REF] Raiffa | Decision Analysis-Introductory lectures on choices under uncertainty[END_REF], influence diagrams [START_REF] Howard | Influence diagrams[END_REF], Valuation Based Systems [START_REF] Shenoy | Valuation-based systems for Bayesian decision analysis[END_REF] and Markov decision process [START_REF] Bellman | A Markovian Decision Process[END_REF], offer a clear description of sequential decision problems that allow an easy definition of optimal strategies. Within existing models, we are particularly interested to the most known models namely decision trees (DT s). This graphical representation is intuitive and constitutes a simple tool to represent decision problems at hand. This formalism is the core of this chapter that is organized as follows: In Section 4.2, we define the graphical and numerical (probabilistic and possibilistic) components of decision trees. Then, we detail the optimization of these graphical models with regards to a probabilistic quantification of uncertainty in Section 4.3 and considering the possibilistic representation in Section 4.4.

Definition of decision trees (DT and ΠDT )

The most popular graphical decision model is the decision tree (DT ) proposed by Raiffa in 1968 [START_REF] Raiffa | Decision Analysis-Introductory lectures on choices under uncertainty[END_REF]. These models encode the structure of the problem and represent all possible scenarios by several paths from the root to leaves of the tree. DT s are defined using a graphical component and a numerical one as detailed in what follows.

Graphical component

A graphical component of a decision tree T is composed of a set of nodes N and a set of edges E. The set of nodes is partitioned into three subsets C, D and LN :

• C = {C 1 ...C n }
is a set of chance nodes which represent states of the world. Chance nodes are depicted by circles.

• D = {D 1 ...D m } is the set of decision nodes which represent decision options, or alternatives. They are depicted by rectangles and the label of each decision node is coherent with its temporal order i.e. if D i is a descendant of D j , then i > j.

• LN = {LN 1 ...LN k } is a set of leaves in the tree, they are called also utility leaves since they represent utilities: ∀LN i ∈ LN, u(LN i ) is the utility of being eventually in the node LN i . In decision trees, leaves have no particular representation.

The root node is generally a decision node, denoted by D 0 . Let N i be a node that belongs to N :

• Ω N i denotes the set of possible values of the node N i .

• P ar(N i ) denotes the set of parents of N i , its predecessors.

• Succ(N i ) denotes the set of direct successors of N i , its children. If N i is a decision node

N i = D i ∈ D, Succ(D i ) ⊂ C i.e
. a decision node is followed by chance nodes.

If N i is a chance node N i = C i ∈ C, Succ(C i ) ⊂ D ∪ LN , i.e. Succ(C i )
is the set of outcomes of C i : either a leaf node is observed, or a decision node is reached (and then a new action should be executed). Leave nodes do not have successors.

A scenario (or "trajectory") is complete sequence of actions and observations that represents a path from the root to a leaf. The size |T | of a decision tree is the number of its edges which is equal to the number of its nodes minus 1.

Numerical component

The numerical component of decision trees consists on assigning utility values to leave nodes and labeling the edges outgoing from chance nodes. The quantification of the decision tree, i.e. the numerical component, depends essentially on the nature of uncertainty pertaining the problem and the theory used to represent it. In its classical version, decision trees are probabilistic. Hence, the uncertainty degrees following each C i ∈ C are represented by a conditional probability distribution

p i on Succ(C i ), such that ∀N i ∈ Succ(C i ), p i (N i ) = P (C i |P ar(C i )). The value of p i
depends in the values assigned to decision and chance nodes that depict the path from the root to

C i .
With the development of uncertainty theories, decision trees have been adapted to deal with other uncertainty models than the probabilistic one. Among these variants, we cite the possibilistic decision trees (ΠDT ) that propose to model uncertainty according to possibility theory [START_REF] Garcia | Possibilistic influence diagrams[END_REF].

Possibilistic decision models share the same graphical component as the classical probabilistic ones; namely a set of Chance nodes C, a set of decision nodes D, a set of leave nodes LN and a set of edges connecting these nodes. However, the numerical component is different. In fact, in ΠDT s the uncertainty pertaining to the possible outcome of each

C i ∈ C, is defined by a conditional possibility distribution π i on Succ(C i ), such that ∀N ∈ Succ(C i ), π i (C i ) = Π(C i |path(C i ))
where path (C i ) denotes all the value assignments to chance and decision nodes on the path from the root to C i . The utility value assigned to each leaf can be numerical (e.g. a currency gain) or ordinal (e.g. a satisfaction degree).

Strategy optimization problem

Solving a decision tree amounts to building a strategy that selects an action (i.e. a chance node) for each reachable decision node. Formally, we define a strategy as a function δ from D to C ∪ {⊥}. δ(D i ) is the action to be executed when a decision node D i is reached. δ(D i ) = ⊥ means that no action has been selected for D i (because either D i cannot be reached or the strategy is partially defined). Admissible strategies should be:

• sound: ∀D i ∈ D, δ(D i ) ∈ Succ(D i ) ∪ {⊥}. • complete: (i)δ(D 0 ) = ⊥ and (ii)∀D i s.t. δ(D i ) = ⊥, ∀N ∈ Succ(δ(D i )), either δ(N ) = ⊥ or N ∈ LN .
Let ∆ be the set of sound and complete strategies relative to a decision tree. Any strategy δ in ∆ can be seen as a connected sub-tree of the decision tree whose arcs are of the form

(D i ; δ(D i )).
The optimization of the decision tree amounts to finding the optimal strategy δ * within ∆ w.r.t a decision criterion O. Formally, δ * is optimal iff ∀δ i ∈ ∆ we have δ * O δ i (i.e. δ * is preferred to any strategy δ i ∈ ∆ w.r.t. a decision criterion O).

Since leave nodes LN are labeled with utility degrees, chance node can be seen as a simple probabilistic lottery (for the most right chance nodes) or as a compound lottery (for the inner chance nodes). Then, each strategy δ i can be seen as a compound lottery L i . So, for evaluating and comparing different strategies, we can use the principle of lottery reduction and reduce each compound lottery to an equivalent simple one.

In order to define the optimal strategy, we should be able to compare different strategies w.r.t a decision criterion (O). Formally, a strategy δ * ∈ ∆, is said to be optimal w.r.t. O iff:

∀δ ∈ ∆, Reduction(δ * ) O Reduction(δ ). (4.1)
Example 4.2. The decision trees presented in Figure 4.1 contains 5 different strategies i.e. ∆={δ 1 , δ 2 , δ 3 , δ 4 , δ 5 } where:

• δ 1 : δ 1 (D 0 ) = C 1 , δ 1 (D 1 ) = C 3 , δ 1 (D 2 ) = C 5 ; • δ 2 : δ 2 (D 0 ) = C 1 , δ 2 (D 1 ) = C 3 , δ 2 (D 2 ) = C 6 ; • δ 3 : δ 3 (D 0 ) = C 1 , δ 3 (D 1 ) = C 4 , δ 3 (D 2 ) = C 5 ; • δ 4 : δ 4 (D 0 ) = C 1 , δ 4 (D 1 ) = C 4 , δ 1 (D 2 ) = C 6 ; • δ 5 : δ 5 (D 0 ) = C 2 .
For the probabilistic decision tree ( The size |δ| of a strategy δ is the sum of its number of nodes and edges; it is obviously lower than the size of the decision tree. Besides, the set of potential strategies is combinatorial (i.e., its size increases exponentially with the size of the tree). In a decision tree with m decision nodes and a branching factor equal to 2, the number of potential strategies is in O( 2√ m ). Then, the determination of an optimal strategy for a given representation and a given decision criterion is an algorithmic issue.

Furthermore, the difficulty of the optimization problem depends on some properties of the decision criterion O, especially the satisfaction of monotonicity (or weak monotonicity) and the transitivity properties that are respectively defined as follows: Definition 4.1. A preference order is said to be transitive iff whatever L, L , L :

L O L and L O L ⇒ L O L ; (4.2)
L O L and L O L ⇒ L O L ; (4.3) L ∼ O L and L ∼ O L ⇒ L ∼ O L . ( 4.4)
Definition 4.2. A preference order is said to be weakly monotonic iff whatever L, L , L , whatever (α, β) such that max(α, β) = 1:

L O L ⇒ α/L, β/L O α/L , β/L (4.5)
The transitivity is interpreted as follows: if exists a preference relation between two lotteries L and L w.r.t a decision criterion and the same relation exists between L and L then this relation is also preserved between L and L . Weak Monotonicity states that the combination of L (resp. L ) with L , does not change the initial order induced by O between L and L . The satisfaction of these properties, is a necessary condition the use of dynamic programming Algorithm.

Optimization of probabilistic decision trees: Dynamic programming

Finding the optimal strategy in a decision tree may be performed via an exhaustive enumeration of ∆, that is a highly computational task. As an alternative method, Bellman proposed a recursive method; the so called Dynamic Programming algorithm; that builds the best strategy backwards, from leaves of the tree to its root [START_REF] Bellman | The theory of dynamic programming[END_REF]. However, the use of this algorithm is appealing only when the criterion to maximize is transitive and monotonic.

The optimization of standard probabilistic decision trees [START_REF] Raiffa | Decision Analysis-Introductory lectures on choices under uncertainty[END_REF] amounts to maximizing the expected utility criterion (detailed in Section 1.2). Since the latter satisfies the monotonicity and transitivity properties, an optimal strategy can be computed in polytime with respect to the size of the tree using Dynamic programming algorithm (denoted by DynProg).

The principle of the backward reasoning procedure can be described as follows: when a chance node C is reached, an optimal sub-strategy is built for each of its children. These sub-strategies are combined w.r.t. their uncertainty degrees. Then, the resulting compound strategy is reduced to an equivalent simple lottery representing the current optimal sub-strategy. When a decision node D is reached, we select a decision D * among all the possible ones D ∈ Succ(X) leading to an optimal sub-strategy w.r.t. O . The choice is performed by comparing the simple lotteries equivalent to each sub-strategy. This principle is implemented by Algorithm (Line 2). Line (2) performs the comparison of two simple (probabilistic) lotteries according to the criterion O to optimize that is the expected utility (EU). These simple lotteries are the result of reduction performed in Line [START_REF]Harsanyi's theorem without the sure-thing principle: On the consistent aggregation of monotonic bernoullian and archimedean preferences[END_REF] where Succ(N ) is the set of successors of N and γ is the probability of the current node. L[u i ] defines the probability degree to have the utility u i in the lottery L, ⊗ is the product operator and ⊕ is the sum operator. Note that in the case of probabilistic decision tree (for the optimization of the expected utility criterion) this algorithm performs in polytime and its complexity is polynomial w.r.t. the size of the tree.

Optimization of possibilistic decision trees

The evaluation of a possibilistic decision tree, like the probabilistic one consists in finding the optimal strategy δ * within ∆. As mentioned before, the optimization depends on the properties of the decision criterion O. If this criterion verifies the crucial properties of weak monotonicity and transitivity, an optimal strategy can be computed in polytime with respect to the size of the tree using the recursive method of Dynamic programming.

Such properties are satisfied by the qualitative possibilistic decision rules U opt , U pes and P U (they are monotonic and transitive). Thus, just like the case of the optimization of the expected utility, Algorithm (Line 2) may be used to obtain an optimal strategy in a possibilistic decision tree. In Line 1, the algorithm computes the reduction of the possibilistic lottery according to scale of evaluation: γ is the possibility measure for U opt and P U and the necessity measure for U pes , ⊕ is the max operator and ⊗ is the min operator. Line (2) allows the comparison of simple (probabilistic) lotteries according to the criterion O to optimize. Then, for these criteria the optimal strategy can be built in polytime in a recursive manner.

L[u i ] ← ⊕(L[u i ], (⊗(γ N (Y ), L Y [u i ]))); // Probabilistic lottery: ⊗ = product, ⊕ = sum // Possibilistic lottery: ⊗ = min, ⊕ = max // Decision nodes if N ∈ D then // Choose the best decision Y * ← Succ(N ).f irst; foreach Y ∈ Succ(N ) do L Y ← DynP rog(Y, δ); (Line 2) if L Y O L Y * then Y * ← Y ; δ(N ) ← Y * ; L ← L Y * ; return L;
For possibilistic likely dominance criteria which are monotonic but not fully transitive, an Extended Dynamic Programming algorithm (ExtDynProg) can be efficiently applied [START_REF] Kikuti | Sequential decision making with partially ordered preferences[END_REF]. Finally, concerning possibilistic Choquet integrals that are not monotonic, the optimization problem is NPhard and a Branch and bound algorithm (BB) has been proposed for binary possibilistic decision trees [START_REF] Ben Amor | Possibilistic sequential decision making[END_REF]. A detailed theoretical study on the problem of finding an optimal strategy in possibilistic decision trees has been proposed in [START_REF] Ben Amor | Possibilistic sequential decision making[END_REF][START_REF] Fargier | On the complexity of decision making in possibilistic decision trees[END_REF]. The main results of this study are summarized in table 4.1.

δ * : δ * (D 0 ) = C 1 , δ * (D 1 ) = C 4 , δ * (D 2 ) = C 6 .
Criterion

Conclusion

In this chapter we have recalled the foundations of sequential decision problems i.e. evaluating strategies in probabilistic as well as possibilistic decision trees. After defining standard decision trees, we have exposed a more recent version of this model that are possibilistic decision trees. This graphical model, allows a natural and explicit model to handle sequential decision problems where uncertainty and utility degrees are possibilistic. Then, we focused on finding an optimal strategy w.r.t. the decision criterion and its properties.

The most naive solving method is exhaustive enumeration of all possible strategies to find the best one. However, given a large number of strategies in big decision trees, this method becomes intractable. As alternative, we can use a Dynamic Programming algorithm for probabilistic decision trees (EU criterion) as well as possibilistic decision trees where the criterion to optimize is transitive and monotonic i.e. for U pes , U opt and P U . For these criteria the optimal strategy can be built in polytime w.r.t. the size of the tree. For other decision rules that are not monotonic and/or not transitive more complex procedures have to be performed.

Collective possibilistic decision making approach

Introduction

This chapter raises the question of collective decision making under possibilistic uncertainty. We propose a new qualitative decision rules to solve such problems depending on the decision makers' attitude with respect to uncertainty (i.e. optimistic or pessimistic) as well as the method performed to aggregate the decision makers' preferences relative to the different consequences; four ex-ante and four ex-post decision rules are defined and investigated.

We show that in context of a possibilistic representation of uncertainty, the use of an egalitarian collective utility function allows to get rid of the Timing Effect. Making a step further, we prove that if both the agents' preferences and the collective ranking of the decisions satisfy Pareto Unanimity and Dubois and Prade's axioms [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF], particularly risk aversion, then the egalitarian collective aggregation is compulsory. This result can be seen as an ordinal counterpart of Harsanyi's theorem [START_REF] Harsanyi | Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility[END_REF]. The picture is then completed by the proposition and the characterization of an optimistic counterpart of this pessimistic decision rule.

The next Section develops our proposition, defining four ex-ante and four ex-post aggregations, and shows that when the decision rules are either fully min-oriented or fully max-oriented, the ex-ante and the ex-post possibilistic aggregations provide the same result. Section 5.3 exposes our axiomatization system relative to the egalitarian pessimistic decision rule and propose our representation theorem. Finally, Section 5.4 presents a variant of this theorem adapted to the optimistic case.

Definition and properties of collective possibilistic decision rules

Harsanyi's theorem previously presented in Section 3.3 is strongly related to uncertainty modeling and is efficient only in a probabilistic view of uncertainty. In a possibilistic context, given a set X of consequences, a set A of agents we define a collective decision problem under possibilistic uncertainty as triplet L, w, u 1 where:

• L is a set of possibilistic lotteries;

• w ∈ [0, 1] p is a weighting vector: w i denotes the weight of agent i;

• u = u 1 , . . . , u p is a vector of p utility functions on X: u i (x j ) ∈ [0, 1] is the utility of x j according to agent i;

Our aim is to compare lotteries according to decision maker's preferences relative to their different consequences (captured by the utility functions) and the importance of each agent (captured by the weighting vector). To do this, we can proceed in two different ways namely ex-ante or ex-post:

• The ex-ante aggregation consists in computing the (optimistic or pessimistic) utilities relative to each agent i, and then perform the aggregation (U + or U -) using the agent's weights.

• The ex-post aggregation consists in first determining the aggregated utilities (Agg max or Agg min ) relative to each possible consequence x j of L and then combine them with the possibility degrees.

In the possibilistic framework, the decision maker's attitude with respect to uncertainty can be either optimistic (U + ) or pessimistic (U -) and the aggregation of the agents preferences can be either conjunctive, egalitarian (Agg min ) or disjunctive, non egalitarian (Agg max ), hence the definition of four approaches of CDM under uncertainty, namely U +max , U +min , U -max and U -min ; the first (resp. the second) sign denoting the attitude of the decision maker w.r.t. uncertainty (resp. agents preferences aggregation) [6].

Each of these utility functions can be computed either ex-ante or ex-post. Hence the definition of eight utilities:

1 Classical problems of decision under possibilistic uncertainty are recovered when |A| = 1 ; Classical collective decision making problems are recovered when all the lotteries in L associate possibility 1 to some x i and possibility 0 to all the other elements of X: L is identified to X, i.e. is a set of "alternatives" for the CDM problem. Definition 5.1. Given a possibilistic lottery L on X, a set of agents A, a vector of utility functions u and a weighting vector w, let:

U +max ante (L) = max i∈A min(w i , max x j ∈X min(u i (x j ), L[x j ])).
(5.1)

U -min ante (L) = min i∈A max((1 -w i ), min x j ∈X max(u i (x j ), (1 -L[x j ]))).
(5.2)

U +min ante (L) = min i∈A max((1 -w i ), max x j ∈X min(u i (x j ), L[x j ])).
(5.3)

U -max ante (L) = max i∈A min(w i , min x j ∈X max(u i (x j ), (1 -L[x j ]))).
(5.4)

U +max post (L) = max x j ∈X min(L[x j ], max i∈A min(u i (x j ), w i )).
(5.5)

U -min post (L) = min x j ∈X max((1 -L[x j ]), min i∈A max(u i (x j ), ( 1
-w i ))).
(5.6)

U +min post (L) = max x j ∈X min(L[x j ], min i∈A max(u i (x j ), (1 -w i ))).
(5.7)

U -max post (L) = min x j ∈X max((1 -L[x j ]), max i∈A min(u i (x j ), w i )). (5.8)
It is obviously possible to define in the same way a series of utilitarian possibilistic utilities (U -sum ante , U +sum ante , etc.) and a series of max-oriented ones (U -max post , U + max post , etc. ).

Example 5.1. As a matter of fact, consider two agents 1 and 2, the first one being less important than the second (w 1 = 0.6, w 2 = 1), and the simple lotteries L 1 , L 2 on X = {x 1 , x 2 , x 3 } depicted in Figure 5.1. Using the egalitarian aggregation we have:

L 2 1
x 3 : <0.8 ; 0.8> L 1 1 0.9

x 1 : <0.9 ; 0.1> • U -min post (L 1 ) = min(max(1 -0.6, min max(1 -1, 0.9), max(1 -0.9, 0.1)), max(1 -1, min max(1 -1, 0.1), max(1 -0.9, 0.8)))

= 0.1

• U -min ante (L 1 ) = min(max(1 -1, min(max(1 -0.6, 0.9), max(1 -1, 0.1))), max(1 -0.9, min(max(1 -0.6, 0.1), max(1 -1, 0.8)))) = 0.1

• U + min post (L 1 ) = min(max(1 -0.6, max(min(1, 0.9), min(0.9, 0.1))), max(1 -1, max(min(1, 0.1), min(0.9, 0.8)))) = 0.8

• U + min ante (L 1 ) = max(min(1, min(max(1 -0.6, 0.9), max(1 -1, 0.1))), min(0.9, min(max(1 -0.6, 0.1), max(1 -1, 0.8)))) = 0.4

• U -min ante (L 2 ) = U -min post (L 2 ) = U + min ante (L 2 ) = U + min post (L 2 ) = 0.8.
The pessimistic aggregations are related to their optimistic counterparts by duality as stated by the following proposition.

Proposition 5.1. Let P = L, w, u be a qualitative decision problem, let P τ = L, w, u τ be the inverse problem, i.e. the problem such that for any x j ∈ X, i ∈ A, u τ i (x j ) = 1 -u i (x j ). Then, for any L ∈ L: Interestingly it appears that the coincidence between ex-post and ex-ante approaches does not imply utilitarianism. Indeed it is easy to show that: Proposition 5.2.

U +max ante (L) = 1 -U τ -min ante (L) U +max post (L) = 1 -U τ -min post (L) U -min ante (L) = 1 -U τ +max ante (L) U -min post (L) = 1 -U τ +max post (L) U +min ante (L) = 1 -U τ -max ante (L) U +min post (L) = 1 -U τ -max post (L) U -max ante (L) = 1 -U τ +min ante (L) U -max post (L) = 1 -U τ +min
U -min ante (L) = U -min post (L) U + max ante (L) = U + max post (L)
Proof of Proposition 5.2.

In the following we provide the proof relative to decision rule U -min . The proof relative to U + max can be deduced by replacing min by max, max by min, (1 -L[x) by L [x] and (1 -w i ) by w i .

U -min post (L) = min x∈X max(1 -L[x], min i∈A max(1 -w i , u i (x))) = min x∈X min i∈A max(1 -L[x], max(1 -w i , u i (x))) = min i∈A min x∈X max(1 -L[x], max(1 -w i , u i (x))) = min i∈A min x∈X max(1 -w i , max(1 -L[x], u i (x))) = min i∈A max(1 -w i , min x∈X max(1 -L[x], u i (x))) = U -min ante (L)
We shall thus simply use the notation U -min (resp. U + max ) for the fully min-oriented (resp. max-oriented) aggregation. Such a coincidence happens neither in the case of U + min nor in the case of U -max ; with U + min post a lottery is good as soon as there exists a possible outcome satisfying all the agents; with U + min ante (resp. U -max post ), a lottery is good when each agent forecasts an outcome that is good for her (but it is not necessarily the same one for all): it may happen that U + min post (L) < U + min ante (L) (resp. U -max post (L) < U -max post (L)), as shown by Counter-example 5.1. Counter-example 5.1. Consider two equally important agents 1 and 2 (w 1 = w 2 = 1) and two lotteries L and L (cf. Figure 5.2) relative to three totally possible consequences x 1 , x 2 and x 3 such that x 1 is good for 1 and bad for 2, x 2 is bad for 1 and good for 2 and x 3 is average for both agents i.e. L[

x 1 ] = L[x 2 ] = L[x 3 ] = 1, u 1 (x 1 ) = u 2 (x 2 ) = 1, u 2 (x 1 ) = u 1 (x 2 ) = 0 and u 1 (x 3 ) = u 2 (x 3 ) = 0.5. We can check that U +min ante (L) = 1 = U +min post (L) = 0: L '
U +min ante (L) = min(max((1 -w 1 ), max(min(u 1 (x 1 ), L[x 1 ]), min(u 1 (x 2 ), L[x 2 ]))), max((1 -w 2 ), max(min(u 2 (x 1 ), L[x 1 ]), min(u 2 (x 2 ), L[x 2 ]
)))). = min(max((1 -1), max(min(1, 1), min(0, 1))), max((1 -1), max(min(0, 1), min(1, 1)))) = 1.

U +min post (L) = max(min(L[x 1 ], min(max(u 1 (x 1 ), (1 -w 1 )), max(u 2 (x 1 ), (1 -w 2 )))), min(L[x 2 ], min(max(u 1 (x 2 ), (1 -w 1 )), max(u 2 (x 2 ), (1 -w 2 ))))). = max(min(1, min(max(1, (1 -1)), max(0, (1 -1)))), min(1, min(max(0, (1 -1)), max(1, (1 -1))))) = 0.
The ex-ante and ex-post approaches may lead to different rankings of lotteries. Besides while L presents a constant act, we can check that U +min ante (L ) = U +min post (L ) = 0.5. So we can verify that U +min ante (L) > U +min ante (L ) while U +min post (L) < U +min post (L ).

Using these same lotteries L and L , we can show that: U -max ante (L) = 0 = U -max post (L) = 1 and that U -max ante (L ) = U -max post (L ) = 0.5; then U -max post (L ) < U -max post (L) while U -max ante (L ) > U -max ante (L): like U +min , U -max are subject to the timing effect.

In summary, U -max and U +min suffer from the timing effect, but U -min and U +max do not. It holds that:

Proposition 5.3. U + min ante (L) ≥ U + min post (L) U -max ante (L) ≤ U -max post (L)
Proof of Proposition 5.3.

Let us show that U + min ante (L) ≤ U + min post (L), the one relative to U -max can be obtained in the same way.

Let u i (x) = max(u i (x), 1 -w i ) U + min post (L) = max x∈X min(L[x], min i∈A max(1 -w i , u i (x))) = max x∈X min(L[x], min i∈A u i (x)) = max x∈X min i∈A min(L[x], u i (x)) U + min ante (L) = min i∈A max(1 -w i , max x∈X min(u i (x), L[x])) = min i∈A max x∈X max(1 -w i , min(u i (x), L[x])) = min i∈A max x∈X min(max(1 -w i , u i (x)), max(1 -w i , L[x])) = min i∈A max x∈X min(u i (x), max(1 -w i , L[x])) Besides since, ∀x ∈ X, ∀i ∈ A, max(1 -w i , L[x]) ≥ L[x] ; we have: (i) min i∈A max x∈X min(u i (x), max(1 -w i , L[x])) ≥ min i∈A max x∈X min(u i (x), L[x]) Let f(x,i) = min(u i (x), L[x]
), then we have:

∀x ∈ X, ∀i ∈ A, max x∈X f (x, i) ≥ f (x, i) min i∈A max x∈X f (x, i) ≥ min i∈A f (x, i) ; ∀x ∈ X min i∈A max x∈X f (x, i) ≥ max x∈X min i∈A f (x, i) Then we obtain min i∈A max x∈X min(u i (x), L[x]) ≥ max x∈X min i∈A min(u i (x), L[x])
From (i) and (ii) we can deduce that U + min ante (L) ≥ U + min post (L)

Axiomatization of egalitarian pessimistic decision rule in style of VNM axiomatic system

In this section, we propose an axiomatization of the pessimistic egalitarian utility. Consider a set A of p agents, a finite set of consequences X, a possibilistic scale V , the set of possibilistic lotteries L obtained from V and X. The preference profile 1 , . . . , p gathers the preference relations i of each agent i on L. denotes the collective preference on L.

Let us denote by x the "constant" lottery leading to consequence x for sure (s.t. L[x] = 1 and L[y] = 0 for each y = x ; e.g. L 2 in Figure 5.1): constant lotteries and elements of X are identified. In the same way, let Y be the lottery that represents a subset Y of X (it provides the possibility degree 1 to each y ∈ Y , and 0 otherwise). As we compute a globbal criterion, the values of this criterion are consequences in X So, we formulate first of all a completeness axiom on the set of consequences X:

Axiom (C, Completeness of X). ∀x, y ∈ X, ∀B ⊆ A, ∃z ∈ X such that: z ∼ i x if i ∈ B and z ∼ j y if j / ∈ B.
This axiom requires that there exists a z in X that is indifferent to x for agents in B and indifferent to y for the others. When two agents are involved, axiom C says that if x and y are two elements of X, then X contains an element z corresponding to the vector of satisfaction x i , y j . This axiom ensure the existence of a sort of "collective equivalence" that can be seen as a counterpart in the sens of social choice, of the certainty equivalence axiom (A2) defined by Dubois and Prade for the characterization of qualitative utility.

More generally, this axiom requires the set of lotteries to be rich enough to contain all the constant acts corresponding to all the vectors of satisfaction (in a sense, C deals more with L than with ). This implies in particular that X contains a consequence x * that is ideal for all the agents, and a consequence x * anti-ideal for all the agents. When the set of consequences X is too small, it is harmless to extend and enrich it in order to obtain all the z that we need: in the following, axiom C is supposed by construction (in Harsanyi's paper it is implicit: X is identified with the set of utility vectors).

We now introduce the axiom of Pareto unanimity, that is essential for collective choice:

Axiom (P, Pareto Unanimity). If ∀i ∈ A, L i L , then L L .

A representation theorem for agents with different weights

Let us study the pessimistic collective decision rules in the light of the axioms and show that they are consistent, namely obeyed by the pessimistic egalitarian utility (U -min ). Consider a set L of possibilistic lotteries built from a set X and a scale V ; a set u i , i ∈ A of utility functions on X taking their values in [0, 1]; and a weight vector w ∈ [0, 1] p (where w i is the weight of agent i).

Let us resume Dubois and Prade's axioms relative to qualitative utilities (see Section 2.4). It holds that:

Proposition 5.4. The relations and i defined by:

L L iff U -min (L) ≥ U -min (L ), L i L iff U - i (L) ≥ U - i (L )
satisfy Dubois and Prade's axioms (A1 -1 . . . A6 -of page 24) relative to the pessimistic utility, as well as the Pareto Unanimity axiom.

Proof of Proposition 5.4.

• The relation i defined by U - i satisfies axioms A1 -. . . A6 -: By definition, U - i is the pessimistic utility relative to each agent, then it is obvious that i satisfies axioms A1 -. . . A6 -.

• The relation defined by U -min satisfies axioms A1 -. . . A6 -:

By definition we have ∀i ∈ A, i satisfies axioms A1 -. . . A6 -. Besides, we have:

U -min post = min x∈X max(1 -L[x], min ∈A max(u i (x), 1 -w i )) Let u(x) = min i∈A max(u i (x), 1 -w i ) Then, U -min post = min x∈X max(1 -L[x], u(x))
Hence, U -min post can be seen as a pessimistic utility based on the utility function u(x). Since, U -min post = U -min ante = U -min , so U -min satisfies Dubois and Prade's axioms.

• The relation defined by U -min satisfies the Pareto unanimity axiom: Let: ∀i ∈ A, L i L By the definition of pessimistic utility we have:

L i L iff U - i (L) ≥ U - i (L ) Hence, ∀i ∈ A, max(1 -w i , U - i (L)) ≥ max(1 -w i , U - i (L)) Then, min i∈A max(1 -w i , U - i (L)) ≥ min i∈A max(1 -w i , U - i (L )) We obtain, U -min ante (L) ≥ U -min ante (L ); which implies that L L Since U -min ante = U -min post = U -min
, then U -min satisfies axiom P (Pareto Unanimity axiom).

Regarding the other (non egalitarian) pessimistic utility U -max the news are unfortunately very bad: not only they suffer from timing effect problem; but also due to the drowning effect we Counter-example 5.2. Consider two agents 1 and 2 with different importance such that w 1 = 1 and w 2 = 0.8 and consider the two lotteries presented in Figure 5.3 on X = {x 1 , x 2 , x 3 }. We get:

L 2 1
x 3 : <0.2 ; 0.2> L 1 1 0.9

x 1 : <0.1 ; 0.9> x 2 : <0.9 ; 0.2> • For Agent 1:

U -(L 1 ) = min(max((1 -1), 0.1), max((1 -0.9), 0.9)) = 0.1

U -(L 2 ) = max((1 -1), 0.2) = 0.2
• For Agent 2:

U -(L 1 ) = min(max((1 -1), 0.9), max((1 -0.9), 0.2)) = 0.2 U -(L 2 ) = max((1 -1), 0.2) = 0.2

While:

U -max post (L 1 ) = min(max((1 -1), max(min(1, 0.1), min(0.8, 0.9))), max((1 -0.9), max(min(1, 0.9), min(0.8, 0.2)))) = 0.8

U -max post (L 2 ) = max((1 -1), max(min(1, 0.2), min(0.8, 0.2))) = 0.2
Hence, we can verify that Agent 1 prefers L 2 to L 1 whereas lotteries L 1 and L 2 are equivalent for Agent 2. However, we can show that U -max post (L 1 ) > U -max post (L 2 ), which contradicts Pareto Unanimity.

Counter-example 5.3. Consider two agents 1 and 2, where Agent 2 is more important than Agent 1 such that w 1 = 0.5 and w 2 = 1, and consider the three lotteries on X = {x 1 , x 2 , x 3 } depicted in Figure 5.4. Let L and L be the lotteries defined by: L = 1/L 1 , 0.9/L 3 and L = 1/L 2 , 0.9/L 3 .

We can verify that L 1 and L 2 are equivalent: U -max ante (L 1 ) = U -max ante (L 2 ) = 0.5 whereas U -max ante (L) = 0.5 = U -max ante (L ) = 0.4, which proves that U -max ante does not satisfy the weak independence axiom. Let us now go back to our egalitarian pessimistic utility and show that the relation that satisfies Completeness, Pareto Unanimity and the axioms of pessimistic utility can be captured by U -min -thus providing a counterpart of Harsanyi's theorem that allows (weighted) equity. First, we sketch the proof in the general case, allowing more or less important agents: this provides a characterization of U -min in its full generality. Then, we impose equity between agents in a second step -and rule out the weights.

We have seen that the set of axioms is consistent since satisfied by U -min . Let us now go the reverse way. Consider a relation on L (built on X and V ) that satisfies axioms A1 -. . . A6 -, a set of relations i on the same L that also satisfy these axioms, and suppose that the axioms of Pareto Unanimity and Completeness of X hold.

First of all, since axioms A1 -. . . A6 -are satisfied by and i , these relations can be represented by pessimistic utilities -this is Dubois and Prade's theorem of representation. Let us now consider for any agent i ∈ A, the set i = {x ∈ X: ∀y, x i y} of the best consequences according to i (this set cannot be empty because the i 's are pre-orders). Thanks to Axiom C, there exists a consequence x * that belongs to all the i 's. By Pareto Unanimity, x * y, ∀y ∈ X. In the same way, there exists a x * such that y x * , ∀y ∈ X. Also, Axiom C allows us to define the constant act x i for any agent i, such as: Definition 5.2. ∀x ∈ X and any agent i, let x i be the constant lottery s.t. x i ∼ i x and x i ∼ j x * for each j = i.

x i will be identified with the utility of x according to agent i: the influence of the other agents is neutralized (they get their best outcome, which behaves as a neutral element in the pessimistic approach).

Let Σ i = {x i , x ∈ X}. (x * ) i (resp. (x * ) i
) is the best (resp. worst) consequence according to agent i belong to Σ i by definition. The union of the Σ i 's, that is to say Σ = {x i : x ∈ X, i ∈ A}, plays an important role in our proof -it allows the construction of a common evaluation scale. Σ is naturally ordered by and each Σ i is ordered by i . By construction, we have:

Proposition 5.5. ∀x ∈ X, (x * ) i i x i (x * ) i .
Proof of Proposition 5.5. By definition of x * according to Axiom C we have:

∀i ∈ A, ∀x ∈ X; x * i x.
Besides, by definition of (x * ) i we have: ∀i ∈ A ; (x * ) i ∼ i x * . Then, by transitivity of i we can obtain: (i) (x * ) i i x. In the same way, by definition of x * we have: ∀i ∈ A, ∀x ∈ X; x i x * . and by definition of (x * ) i we have: ∀i ∈ A; (x * ) i ∼ i x * . Also, by transitivity we can obtain: (ii) x i (x * ) i . From (i) and (ii) we can deduce that: ∀x ∈ X, (x * ) i i x i (x * ) i .

Moreover, we can show that:

Proposition 5.6. ∀x i ∈ Σ i , (x * ) i x i (x * ) i
Proof of Proposition 5.6.

By definition of x i , we have: ∀i ∈ A, ∀x ∈ X ;

x i ∼ i x.
According to Proposition 5.5, we have: ∀i ∈ A, ∀x ∈ X ; (x * ) i i x. Then, by transitivity we obtain:

(x * ) i i x i . Besides, (x * ) i k x i , for all k (because (x * ) i ∼ k x *
, whether k is equal to i or not). Then, (x * ) i k x i and i is transitive; by Pareto Unanimity we obtain (i) (x * ) i x i . In the same way, by definition of x i , we have: ∀i ∈ A, ∀x ∈ X ;

x i ∼ i x.
According to Proposition 5.5, we have: ∀i ∈ A, ∀x ∈ X ; x i (x * ) i . Then, by transitivity we obtain: x i i (x * ) i ; besides by Pareto Unanimity we obtain (ii)

x i (x * ) i .
From (i) and (ii) we can deduce that: ∀x i , (x * ) i x i (x * ) i . (x * ) i is one of the best consequences for i and (x * ) i is one of her worst ones. It may happen that one of the x i be indifferent w.r.t. to (x * ) i : i prefers x i to (x * ) i , but the collectivity does not; this is due to the fact that agent i is not so important, so the elements of X that are bad for her (e.g. (x * ) i ) are considered as not so bad for the collectivity.

Let us denote by

B i = {x i ∈ Σ i : x i ∼ (x * ) i }
the set of the elements of Σ i that are indifferent to (x * ) i according to the collectivity, and this even if agent i makes a difference; the elements of B i form an equivalence class according to -but, again, not necessarily according to i . Let denote m i the best element of B i (according to i ) 2 . It reflects the importance of the agent: the greater is m i , the less is the importance of i.

Formally3 , it can be defined as follows:

Definition 5.3. ∀i ∈ A, let m i = argmax i {x i : x i ∼ (x * ) i } be the discount degree of i.
We can now formulate the following two lemmas:

In order to show that a relation satisfying axioms A1 -. . . A6 -is a pessimistic utility, Dubois and Prade [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF] built the scale U = {[x]: x ∈ X} where [x] is the equivalence class of x according to . U is totally ordered by and these authors set u(x) = [x]. Here, we use the set Σ = {x i : x ∈ X, i ∈ A}, partially ordered by the relation ¤ defined by: Definition 5.4. ∀x, y ∈ X, i, j ∈ A:

x i ¤ y i iff x i i y i
x i ¤ y j iff x i i m i , y j j m j and x i y j , ∀i = j.

This relation is a partial pre-order (it is reflexive and transitive) but if x i ≺ m i or x j ≺ m j for all i = j, x i and y j are not comparable: neither x i ¤ y j nor y j ¤ x i hold, but this is harmless. What is important is that (i) the restriction of ¤ to each Σ i is a pre-order (on Σ i , ¤ = i ) and (ii) that any x i that is as least as good as m i (according to i) is comparable to any x j that is as least as good as m j (according to j) . Properties (i) and (ii) ensure that v(x) = min ¤ {max ¤ (m i , x i ): i ∈ A} exists.

Proposition 5.7. The relation ¤ is transitive.

Proof of Proposition 5.7.

• Case 1: ∀x, y, z ∈ X, ∀i ∈ A, if x i ¤ y i and y i ¤ z i then by definition of ¤ we have:

x i i y i and y i i z i . Since i is transitive then x i i z i so, x i ¤ z i .

• Case 2: ∀x, y, z ∈ X, if x i ¤ y i and y i ¤ z j (such as: i = j), by definition of ¤we can say that x i i y i , then by Pareto Unanimity we can deduce that: x i y i . Besides, by Definition 5.4 we have: (i) y i i m i , z j j m j and y i z j . We have x i y i and y i z j then by transitivity of we obtain: (ii) x i z j From (i) and (ii) we can deduce that x i i m i , z j j m j and x i z j besides by definition of ¤ we obtain x i ¤ z j .

• Case 3: ∀x, y, z ∈ X, if x i ¤ y j and y j ¤ z k (such as: i = j = k), by definition of ¤ we have x i i m i , y j j m j and x i y j (i) besides y j j m j , z k k m k and y j z k (ii). Then, from (i) and (ii) and by transitivity of we can conclude that

x i i m i , z k k m k and x i z k , besides by definition of ¤ obtain x i ¤ z k .
Then, ∀x, y ∈ X and for alli = j; we can deduce that ¤ is transitive.

Then from Corollary 5.1 and Definition 5.4 it follows that: x ∼ v(x). Let k be the agent for which the min is reached in the expression of v(x): v(x) = max ¤ (m k x k ) belongs to Σ k and is such that v(x) k m k . Hence v(x) and v(y) are comparable w.r.t. ¤, whatever x, y. This allows us to write:

Lemma 5.3. x y iff argmin ¤ {max ¤ (m i , x i ): i ∈ A} ¤ argmin ¤ {max ¤ (m i , y i ): i ∈ A}.
Proof of Lemma 5.3. By Lemma 5.1 we have: ∀x ∈ X, i ∈ A, x i ∼ max i (m i , x i ). Then, by Definition 5.4 we can say that: (i)

x i ∼ max ¤ (m i , x i ).
Besides, by Lemma 5.2 we have: ∀x ∈ X, x ∼ argmin {x i : i ∈ A}. In the same way, by Definition 5.4 we can say that: (ii) x ∼ argmin ¤ {x i , i ∈ A}. Using Corollary 5.1 and from (i) and (ii) we can obtain:

x ∼ argmin ¤ {max ¤ (m i , x i ), i ∈ A}.
Then we can deduce that:

x ∼ argmin ¤ {max ¤ (m i , x i ), i ∈ A} and y ∼ argmin ¤ {max ¤ (m i , y i ), i ∈ A} So, by Definition 5.4 we obtain: x y iff argmin ¤ {max ¤ (m i , x i ), i ∈ A} ¤ argmin ¤ {max ¤ (m i , y i ), i ∈ A}.
Because working with a partial preorder is not so convenient, we shall use any complete preorder ¤ on Σ such that x ¤ y =⇒ x ¤ y (there always exists one). Then we get:

Lemma 5.4. x y iff argmin ¤ {max ¤ (m i , x i ): i ∈ A} ¤ argmin ¤ {max ¤ (m i , y i ): i ∈ A}.
Proof of Lemma 5.4. The proof of this Lemma is similar to the proof relative to Lemma 5.3 since they express the same thing; with a partial pre-order (¤) on Σ for Lemma 5.3 and a complete pre-order (¤ ) for Lemma 5.4.

Since satisfies axioms A1 -. . . A6 -, Dubois and Prade's result applies: there exists an order reversing function n s.t.:

L L iff min x∈X max (n(L[x]), u(x)) min x∈X max (n(L [x]), u(x)). Let us denote u(x) = argmin ¤ {max ¤ (m i , x i ): i ∈ A} and n ext (v) = u(n(v)) (n(v)
is an element of Σ). By applying Lemma 5.4, we can write:

L L iff min ¤ x∈X max ¤ (n ext (L[x]), u(x)) ¤ min ¤ x∈X max ¤ (n ext (L [x]), u(x)).
n ext (v), m i and x i , u(x) belong to Σ. In order to get a total order, we consider the equivalence classes of Σ, i.e. the set U ext = {[x]: x ∈ X} where [x] is the equivalence class of x w.r.t. ¤ . Because x = argmin {x i : i ∈ A} (Lemma 5.2) U ext contains the equivalence classe of each x ∈ X to , in particular, the equivalence classe [x i ] of each x i ; U ext is ordered by ¤ and is equipped with a maximal and a minimal elements ([x * ] and [x * ], respectively).

Setting u i (x) = [x i ], nw i = [m i ] and n(v) = [n ext (v)], we get: L L iff min ¤ x∈X max ¤ (n(L[x]), min ¤ i∈A max ¤ (u i (x), nw i )) ¤ min ¤ x∈X max ¤ (n(L[x]), min ¤ i∈A max ¤ (u i (x), nw i )).
Hence the main result of this work: Theorem 5.1. If the collective preference and individual preference relations satisfy axioms A1 - . . . A6 -, Pareto Unanimity (axiom P) and the axiom of completeness of X (axiom C) then there exists a scale U ext totally ordered by ¤ , a distribution of weights nw: A → U ext , a series of functions u i : X → U ext , i = 1, n and an order reversing function n: V → U ext s.t. for each couple of lotteries L and L :

L L iff min x∈X max(n(L[x]), min i∈A max(nw i , u i (x))) ¤ min x∈X max(n(L [x]), min i∈A max(nw i , u i (x))).
This theorem can be interpreted as follows: If Dubois and Prade's axioms A1 -. . . A6 -relative to the pessimistic utility, as well as axioms P and C are satisfied by the collective preference relation and the individual preference relations i , then there exists a scale U ext totally ordered by ¤ , a distribution of weights, a set of functions u i (x) and an order reversing function such that for any pair of lotteries L and L , L is preferred by the collectivity to L iff the pessimistic egalitarian utility U -min (L) is better than U -min (L ). Using Definition 5.4 and since ¤ relative to each Σ i is a complete pre-ordre (on Σ i , ¤ = i ) and each x i is at least as good as m i (for i) is comparable to each x j that is at least as good as m j (for j) we can say that: u(x) = argmin ¤ {max ¤ (m i , x i ): i ∈ A}. Using Lemma 5.4 we can say that: u(x) = argmin ¤ {max ¤ (m i , x i ), i ∈ A} By applying Lemma 5.4 and using Dubois and Prade's definition relative to the pessimistic utility, we obtain:

L L ssi min ¤ x∈X max ¤ (n ext (L[x]), u(x)) ¤ min ¤ x∈X max ¤ (n ext (L [x]), u(x)).
n ext (v), m i and x i , u(x) belongs to Σ. In order to have a total order, we consider the equivalence classes of Σ, i.e. the set U ext = {[x]: x ∈ X} where [x] is an equivalence class of x for ¤ . Since x = argmin {x i : i ∈ A} (Lemma 5.2) U ext contain the equivalence class of each x ∈ X for , in particular, the equivalence class of [x i ] for each x i ; U ext is totally ordered by ¤ , where [x * ] and [x * ] are respectively the maximal and minimal elements.

Let u i (x) = [x i ], nw i = [m i ] and n(v) = [n ext (v)], then we obtain: L L ssi min ¤ x∈X max ¤ (n(L[x]), min ¤ i∈A max ¤ (u i (x), nw i )) ¤ min ¤ x∈X max ¤ (n(L [x]), min ¤ i∈A max ¤ (u i (x), nw i )).
A representation theorem for agents with the same importance (pure egalitarianism)

We can now add two axioms that leads to pure egalitarianism.

Axiom (E). ∀i, j, (x * ) i ∼ (x * ) j . Axiom (PW). ∀i, if x i y then x i y i .
By E, the dissatisfaction of one agent has no more power than the one of another agent. A direct consequence is that the agents have the same discount degree. By PW, each agent has some power (he makes the decision at least when every other one is totally happy with both x and y). It implies m i ∼ i x * , for each i. Because all i share the same discount m i , Pareto Unanimity implies that m i ∼ x * . This provides a characterization of the full egalitarian CUF: Theorem 5.2. If the collective preference and individual preference relations satisfy axioms A1 - . . . A6 -, P, C, E and PW then there exists a scale U ext totally ordered by ¤ , a series of functions u i : X → U ext and an order reversing function n: V → U ext such that:

L L iff min x∈X max(n(L[x]), min i∈A u i (x)) ¤ min x∈X max(n(L [x]), min i∈A u i (x)).
Proof of Theorem 5.2. From Lemma 5.1 we have: ∀x ∈ X, i ∈ A, x i ∼ max i (m i , x i ).

Then we can consider that m i is a particular x i such as:

x i ∼ (x * ) i , i.e. m i ∼ (x * ) i , ∀i ∈ A.
Using axiom E ((x * ) i ∼ (x * ) j ) we can say that m i ∼ (x * ) j (j = i). Then we can deduce that: ∀i, j; m i ∼ (x * ) i ∼ m j ∼ (x * ) j . Using Lemma 5.4 we have:

x y iff argmin ¤ {max ¤ (m i , x i ):i ∈ A} ¤ argmin ¤ {max ¤ (m i , y i ):i ∈ A}.
Besides, since each agent i have the possibility to decide for the collectivity when others are indifferent (axiom PW), Then we can rewrite Lemma 5.4 such as: This theorem shows that not only egalitarianism and decision under uncertainty are compatible and can escape the Timing Effect, but egalitarianism is compulsory when the decision is to be made on a possibilistic and cautious basis. This can be interpreted as a justification of egalitarianism just like Harsanyi's theorem that is interpreted as a justification of utilitarianism.

x y iff argmin ¤ {x i :i ∈ A} ¤ argmin ¤ {y i :i ∈ A}.

Axiomatization of non egalitarian optimistic decision rule in style of VNM axiomatic system

Let us now propose a representation theorem relative to homogeneous optimistic utility function U + max , which is an optimistic counterpart of the previous representation theorem.

We consider a preference relation on L that satisfies Dubois and Prade's axioms relative to the optimistic utility (presented in Section 2.3), a set of preference relations i on the same L satisfying the same axioms, and we suppose that Pareto Unanimity and the Completeness axioms are satisfied. Since Dubois and Prade's axioms (A1 + . . . A6 + ) are satisfied by and by any i , it is obvious that these relations may be represented by optimistic utility functions.

A representation theorem for agents with different weights

Consider a set L of possibilistic lotteries built from a set X and a scale V ; a set u i , i ∈ A of utility functions on X taking their values in [0, 1]; and a weight vector w ∈ [0, 1] p (where w i is the weight of agent i). Similar to U -min , the homogenous utility, it holds that: Proposition 5.8. The relations and i defined by:

L L iff U + max (L) ≥ U + max (L ), L i L iff U + i (L) ≥ U + i (L )
satisfy axioms A1 + . . . A6 + , as well as the Pareto Unanimity axiom.

Proof of Proposition 5. Counter-example 5.4. Consider two not equally important agents 1 and 2 such that w 1 = 1 and w 2 = 0.8 and consider the two lotteries resented in Figure 5.5 on X = {x 1 , x 2 , x 3 }. We get:

L 2 1
x 3 : <0.8 ; 0.8> L 1 1 0.9

x 1 : <0.9 ; 0.1> • For Agent 1:

U + (L 1 ) = max(min(1, 0.9), min(0.9, 0.1)) = 0.9

U + (L 2 ) = min(1, 0.8) = 0.8
• For Agent 2:

U + (L 1 ) = max(min(1, 0.1), min(0.9, 0.8)) = 0.8

U + (L 2 ) = min(1, 0.8) = 0.8
While: U + min post (L 1 ) = max(min(1, min(max((1 -1), 0.9), max((1 -0.8), 0.1))), min(0.9, min(max((1 -1), 0.1), max((1 -1), 0.8)))) = 0.1 U + min post (L 2 ) = max(min(1, min(max((1 -1), 0.8), max((1 -0.8), 0.8)))) = 0.8. Hence, we can verify that Agent 1 prefers L 1 to L 2 whereas lotteries L 1 and L 2 are equivalent for Agent 2. So, U + min post (L 2 ) > U + min post (L 1 ), which contradicts Pareto Unanimity.

Counter-example 5.5. Consider two agents 1 and 2 such that w 1 = 0.5 and w 2 = 1, and consider the three lotteries on X = {x 1 , x 2 , x 3 } depicted in Figure 5.6.

Let L and L be the lotteries defined by: L = 1/L 1 , 0.9/L 3 and L = 1/L 2 , 0.9/L 3 .

We can verify that L 1 and L 2 are equivalent: U + min ante (L 1 ) = U + min ante (L 2 ) = 0.5 whereas U + min ante (L) = 0.5 = U + min ante (L ) = 0.6, which proves that U + min ante does not satisfy the weak independence axiom.

In the previous section, we have seen that axiom C ensures the existence of a constant act x * ideal for all the agents and a constant act x * that is anti-ideal for all. We consider for each agent i, ⊥ i = {x ∈ X, ∀y, y i x} the set of the least appreciated (worst) consequences to i, where x * belongs obviously to all the ⊥ i 's.

For each agent i, we define the constant act x i ∈ X as follows: Definition 5.5. ∀x ∈ X, and any agent i, x i is the constant lottery such that: x i ∼ i x and x i ∼ j x * ; for each j = i x i will be identified with the utility of x according to agent i: the influence of the other agents is neutralized (they get their worst outcome, which behaves as a neutral element in the optimistic approach). Let Σ i = {x i , x ∈ X} be the set of constant acts relative to agent i. Σ i is ordered by i . We define Σ as the union of the Σ i 's, that is ordered by .

(x * ) i is one of the best consequences for i and (x * ) i is one of her worst ones. It may happen that one of the x i be indifferent w.r.t. to (x * ) i : i prefers (x * ) i to x i , but the collectivity does not; this is due to the fact that the agent i is not so important, so the consequences that are good for her, typically (x * ) i , as considered as not so good for the collectivity. So i is not so important to impose her preferences to the group.

Let us denote B

i = {x i ∈ Σ i , x i ∼ (x * ) i },
the set of elements of Σ i that are indifferent to (x * ) i for the collectivity, and this even if agent i makes a difference; the elements of B i form an equivalence class according to but not necessarily according to i .

Let m i denotes the worst element of B i according to i as follows:

Definition 5.6. ∀i ∈ A, m i = argmin i {x i : x i ∼ (x * ) i }
We can now propose the two following lemmas:

Lemma 5.5. ∀x ∈ X, i = 1, p, x i ∼ min i (m i , x i ) Proof of Lemma 5.5. • Case 1: m i i x i : then trivially min i (m i , x i ) = x i . Since is reflexive, x i ∼ min i (m i , x i ).
• Case 2: x i i m i : by definition of m i , we have:

m i = argmin i {x i : x i ∼ (x * ) i }, then m i is a particular x i such as x i ∼ (x * ) i . Then we can say that (i) m i ∼ (x * ) i .
Besides, from Proposition 5.6 we have (ii) (x * ) i x i . From (i) and (ii) and since is transitive and reflexive we can say that m i x i . Hence, we can deduce that

x i i m i involve x i ∼ min i (m i , x i ). Lemma 5.6. ∀x ∈ X, x ∼ argmax {x i , i ∈ A}.
Proof of Lemma 5.6.

We consider lottery L = 1/x 1 , . . . , 1/x p .

Since is an optimistic utility (it satisfies Dubois ans Prade's axioms) and x i s are constant acts; we have:

L ∼ argmax {x i , i ∈ A}. Let us show that L ∼ x.
Since i s are optimistic utilities (satisfy Dubois and Prade's axioms), for each agent i we have: From the previous lemmas we can deduce that:

L ∼ i argmax i {x k , k = 1, p}. Since ∀k = i, x k ∼ i x * ,
Corollary 5.2. ∀x ∈ X, x ∼ argmax {min i (m i , x i ), i ∈ A}.
Proof of Corollary 5.2. From Lemma 5.5 and Lemma 5.6, we have respectively:

(i) ∀x ∈ X, i ∈ A, x i ∼ min i (m i , x i ). (ii) ∀x ∈ X, x ∼ argmax {x i : i ∈ A}.
Then the proof of the corollary is trivial by replacing x i from (ii) by min i (m i , x i ) from (i).

Let us now define the relation ¤ o on Σ = {x i , x ∈ X, i ∈ A} such as: Definition 5.7. ∀x, y ∈ X, i, j ∈ A:

x i ¤ o y i iff x i i y i ∀i = j, x i ¤ o y j iff m i i x i , m j j y j and x i y j
This relation is reflexive and transitive but it defines a partial preorder on Σ; it may happens that m i ≺ x i or m j ≺ x j , for all i = j so, x i and y j are not comparable: but this is harmless since (i) the restriction of ¤ o to each Σ i is a pre-order (on Σ i , ¤ o = i ) and (ii) that any x i which is always equal or less than m i according to i, is comparable to any x j that is at most equal to m j according to j. Properties (i) and (ii) ensure that u(x) = max ¤o {min ¤ (m i , x i ): i ∈ A} exists. Proposition 5.9. ¤ o is transitive.

Proof of Proposition 5.9.

• Case 1: ∀x, y, z ∈ X, ∀i ∈ A, if x i ¤ o y i and y i ¤ o z i then by definition of ¤ o we have:

x i i y i and y i i z i . Since i is transitive then

x i i z i so, x i ¤ o z i .
• Case 2: ∀x, y, z ∈ X, if x i ¤ o y i and y i ¤ o z j (such as: i = j), by definition of ¤ o we can deduce that x i i y i , so by Pareto Unanimity we can write: x i y i . Besides, by Definition 5.7 we have: (i) m i i y i , m j j z j and y i z j . We have x i y i and y i z j then by transitivity of we obtain: (ii) x i z j From (i) and (ii) we can deduce that m i i x i , m j j z j and x i z j besides by definition of ¤ o we obtain x i ¤ o z j .

• Case 3: ∀x, y, z ∈ X, if x i ¤ o y j and y j ¤ o z k (such as: i = j = k), by definition of ¤ o we have m i i x i , m j j y j and x i y j (i) also m j j y j , m k k z k and y j z k (ii). From (i) and (ii), by transitivity of we can conclude that

m i i x i , m k k z k and x i z k , also by definition of ¤ o we obtain x i ¤ o z k .
So, ∀x, y ∈ X and for all i = j ; we can deduce that ¤ o is transitive.

From Corollary 5.2 and Definition 5.7, it follows that: Lemma 5.7.

x y iff argmax ¤o {min ¤o (m i , x i ), i ∈ A} ¤ argmax ¤o {min ¤o (m i , y i ), i ∈ A}.

Proof of Lemma 5.7. By Lemma 5.5 we have: ∀x ∈ X, i ∈ A, x i ∼ min i (m i , x i ). Then, by Definition 5.7 we can write:

x i ∼ min ¤o (m i , x i ) (i).
Besides, by Lemma 5.6 we have: ∀x ∈ X, x ∼ argmax {x i : i ∈ A}. In the same way, by Definition 5.7 we can write: (ii) x ∼ argmax ¤o {x i , i ∈ A}. Using Corollary 5.2 and from (i) and (ii) we obtain:

x ∼ argmax ¤o {min ¤o (m i , x i ), i ∈ A}.
Then we can deduce that: x ∼ argmax ¤o {min ¤o (m i , x i ), i ∈ A} and y ∼ argmax ¤o {min ¤o (m i , y i ), i ∈ A} Hence, by Definition 5.7 we obtain:

x y iff argmax ¤o {min ¤o (m i , x i ), i ∈ A} ¤ o argmax ¤o {min ¤o (m i , y i ), i ∈ A}.
Because working with a partial pre-order is not convenient, we shall use any complete preorder ¤ o on Σ, such that x ¤ o y ⇒ x ¤ o y (there always exists one). Then we get:

Lemma 5.8. x y iff argmax ¤ o {min ¤ o (m i , x i ), i ∈ A} ¤ o argmax ¤ o {min ¤ o (m i , y i ), i ∈ A}.
Proof of Lemma 5.8. The proof of this Lemma is similar to the proof of Lemma 5.7 since they express the same thing; using a partial pre-order (¤ o ) on Σ for Lemma 5.7 and a complete pre-order (¤ o ) for Lemma 5.8.

Since satisfies Dubois and Prade's axioms relative to the optimistic qualitative utility, we can resume their result: there exists a utility function u such that:

L L iff max x∈X min (L[x], u(x)) max x∈X min (L [x], u(x)). Let us denote u(x) = argmax ¤ o {min ¤ o (m i , x i ), i ∈ A}.
By applying Lemma 5.8, we can write:

L L iff max ¤ o x∈X min ¤ o (L[x], u(x)) ¤ o max ¤ o x∈X min ¤ o (L [x], u(x)).
Hence, an optimistic counter part of Theorem 5.1: Theorem 5.3. If the collective preference and individual preference relations i satisfy axioms A1 + . . . A6 + relative to the optimistic utility; Pareto Unanimity and the axiom of completeness of X are satisfied, then there exists a scale U ext totally ordered by ¤ o , a distribution of weights w: A → U ext , a series of functions u i : X → U ext such that for each couple of lotteries L and L :

L L iff max x∈X min(L[x], max i∈A min(u i (x), w i )) ¤ o max x∈X min(L [x], max i∈A min(u i (x), w i )).
Proof of Theorem 5.3. Since satisfies axioms A1 + . . . A6 + we can write:

L L iff max x∈X min (L[x], x) max x∈X min (L [x], x).
Using Definition 5.7 and since ¤ o for each Σ i is a complete pre-ordre (on Σ i , ¤ o = i ) and each x i that is equal or inferior m i (for i) is comparable to each x j that is inferior or equal to m j (for j) we can say that: u(x) = argmax ¤o {min ¤o (m i , x i ): i ∈ A}. Using Lemma 5.8 we can write:

u(x) = argmax ¤ o {min ¤ o (m i , x i ), i ∈ A}
By applying Lemma 5.8 and using Dubois and Prade's definition relative to the optimistic utility, we obtain:

L L ssi max ¤ o x∈X min ¤ o (L[x], u(x)) ¤ o max ¤ o x∈X min ¤ o (L [x], u(x)).
m i , x i and u(x) belongs to Σ. In order to have a total order, we consider the equivalence classes of Σ, i.e. the set U ext = {[x]: x ∈ X} where [x] is the equivalence class of x for ¤ o . Since x = argmax {x i : i ∈ A} (Lemma 5.6) U ext contains the equivalence class for each x ∈ X for , in particular, the equivalence class of [x i ] for each x i ; U ext is totally ordered by ¤ o , where [x * ] and [x * ] are respectively the maximal and minimal elements.

Let u i (x) = [x i ] and w i = [m i ], then we obtain: L L ssi max ¤ o x∈X min ¤ o (L[x], max ¤ o i∈A min ¤ o (u i (x), w i )) ¤ o max ¤ o x∈X min ¤ o (L [x], max ¤ o i∈A min ¤ o (u i (x), w i )).
A representation theorem for agents with same importance Now, to ensure the pure egalitarianism and to guarantee that all the agents have the same importance, we resume axiom PW presented previously, and we present an optimistic version of axiom E:

Axiom (E'). ∀i, j, (x * ) i ∼ (x * ) j .
Thanks to axioms E' and PW, we can provide an optimistic version of Theorem 5.2: Theorem 5.4. If the collective preference and individual preference relations i satisfy axioms A1 + . . . A6 + , C, P, E and PW then there exists a scale U ext totally ordered by ¤ o , a series of functions u i : X → U ext such that for each couple of lotteries L and L :

L L iff max x∈X min(L[x], max i∈A u i (x)) ¤ o max x∈X min(L [x], max i∈A u i (x)).
Proof of Theorem 5.4. From Lemma 5.5 we have: ∀x ∈ X, i ∈ A, x i ∼ min i (m i , x i ). Then we consider that m i is a particular x i such as: x i ∼ (x * ) i . In other words:

m i ∼ (x * ) i , ∀i ∈ A.
Using axiom E' ((x * ) i ∼ (x * ) j ) we can say that m i ∼ (x * ) j (j = i). Hence we can deduce that: ∀i, jm i ∼ (x * ) i ∼ m j ∼ (x * ) j . From Lemma 5.8 we have:

x y iff argmax ¤ o {min ¤ o (m i , x i ):i ∈ A} ¤ o argmax ¤ o {min ¤ o (m i , y i ):i ∈ A}.
In addition, since each agent i have the possibility to decide for the collectivity when others are indifferent (axiom PW), then we can rewrite Lemma 5.8 as the following:

x y iff argmax ¤ o {x i :i ∈ A} ¤ o argmax ¤ o {y i :i ∈ A}.
Resuming Dubois and's results relative to the optimistic utility and considering u(x) = argmax ¤ o x i then we can rewrite theorem 5.3 such as:

L L iff max x∈X min(L[x], max i∈A u i (x)) ¤ o max x∈X min(L [x], max i∈A u i (x)).

Conclusion

This chapter has provided a decision theoretical approach for evaluating collective decision problems under possibilistic uncertainty. The combination of the collectivity dimension, namely egalitarian and not egalitarian approach to aggregate agents preferences; and the decision maker's attitude with respect to uncertainty (i.e. optimistic utility or pessimistic utility) leads to four approaches of collective decision making under possibilistic uncertainty. Considering that each of these utilities can be computed either ex-ante or ex-post, we have proposed the definition of eight aggregations, that eventually reduce to six: U -min ante (resp. U +max ante ) has been shown to coincide with U -min post (resp. U +max post ) such a coincidence does not happen for U +min and U -max , that suffer from timing effect.

Under the assumption, that all the agents have the same knowledge, we have provided an axiomatic system for U -min and have shown that if both the collective preference and the individual preferences do satisfy Dubois and Prade's axioms, and in particular risk aversion, then an egalitarian CUF is mandatory. Finally, we have provided an optimistic counter part of this theorem relative to U +max .These results can be considered as an ordinal counterpart to Harsanyi's theorem.

CHAPITRE 6

Algorithms for multi-agent optimization in possibilistic decision trees

Introduction

In Chapter 4, we have presented an algorithmic study relative to the optimization in decision trees, where decisions concern one decision maker. In this Chapter we deal with qualitative decision trees representing collective sequential decision problems. We focus on the optimization of the collective qualitative decision rules presented in Chapter 5 in such trees and we propose algorithms dedicated to find optimal strategies. A Dynamic Programming algorithm is performed to optimize criteria that satisfy the property of monotonicity and a Multi-Dynamic programming or a Branch and Bound algorithm is proposed for those that are not monotonic. This Chapter is organized as follows: the next Section summarizes the adaptation of Dynamic Programming algorithm for the optimization of the ex-post decision rules. Section 6.2 details the adaptation of Dynamic Programming for the optimization of the U -max ante criterion and Section 6.3 is devoted to the optimization of the U +min ante using a Branch and Bound Algorithm.

Dynamic Programming algorithm for the optimization of "ex-post" decision rules

Let us now consider the strategy optimization in possibilistic (qualitative) decision trees represented in Section 4.4. As usual with decision trees, the set of potential strategies to compare, ∆, is exponential w.r.t. the size of the input, which means that an explicit evaluation of each strategy in ∆ is not realistic. Such a problem can nevertheless be solved efficiently (i.e. in polytime, without an explicit evaluation of each strategy in the set) by a Dynamic Programming algorithm, as soon as the decision rule leads to transitive preferences and satisfies the principle of weak monotonicity. Formally, for any decision rule O (e.g. any of the decision rules proposed in the previous Chapter) over possibilistic lotteries, O is said to be weakly monotonic iff whatever L, L and L , whatever (α,β) such that max(α, β) = 1:

L O L ⇒ α/L, β/L O α/L , β/L . ( 6.1)
This property ensures that each sub strategy of an optimal strategy is optimal in its sub-tree.

Hopefully, each of the ex-post criteria satisfies the weak monotonicity property (because they collapse to a classical pessimistic U -or optimistic U + utility, which are known to be monotonic [START_REF] Ben Amor | Possibilistic sequential decision making[END_REF][START_REF] Garcia | Possibilistic influence diagrams[END_REF]). Like each of the utilities used in the previous Chapter, these criteria take their values on R + and thus obviously define a transitive preference on strategies. This allows the use of a Dynamic Programming algorithm: the utility values pertaining to the leaves are aggregated; then an optimal strategy is built in an incremental way, from the last decision nodes to the root of the tree. The adaptation of this algorithm to the ex-post rules is detailed in Algorithm 2; which is not very different from its classical (probabilistic) version presented by Algorithm (Line 2) in Chapter 4, and polynomial in the number of edges and nodes in the tree, as usual.

Example 6.1. Let us consider two equally important agents 1 and 2 (w 1 = w 2 = 1) and consider the decision tree T represented in Figure 6.1. The optimization of the egalitarian pessimistic utility U -min post decision rule in this decision tree using Algorithm 2 can be performed in two main steps: • First of all, we calculate the aggregated utility relative to each leave node LN ∈ N and we transform each utility vector u N to an aggregated utility u N , as shown in Figure 6.2.

• Then, we perform the Dynamic Programing as for a possibilistic decision tree Π DT with a single agent. Concerning U -min ante and U + max ante , recall that U -min ante (resp. U + max ante ) = U -min post (resp. U + max post ): the optimization can thus simply be performed by the ex-post Dynamic Programming algorithm (Algorithm 2).

Dynamic Programming algorithm for the optimization of "ex-ante" decision rules

It is possible to propose an ex-ante variant of Dynamic Programming for the optimization of the ex-ante criteria-see Algorithm 3. It keeps at each decision node a possibility distribution over the utility vectors corresponding to the decision made in the future. This algorithm provides the same results as Algorithm 2 for U -min ante and U + max ante . However, Algorithm 3 may provide a good strategy for U -max ante and U + min ante , but without any guarantee of optimality. This is because these decision rules do not satisfy the monotonicity principle stricto sensu [6].

Y * ← Succ(N ).f irst ; foreach Y ∈ Succ(N ) do for i ∈ {1, . . . , p} do u Y [i] ← ( u Y [i] ⊗ ω i ) ; u Y ← (u N ⊕ u N [i]) ;
// where ⊗ = min (resp. max), ω i = w i (resp. 1 -w i ) and ⊕ = max (resp. min) in the case of disjunctive (resp. conjunctive) aggregation

if u Y o u Y * then Y * ← Y ; u * ← u Y * ; δ(N ) ← Y * ; return u * ;

Multi Dynamic Programming algorithm for the optimization of U -max ante

The lack of monotonicity is not as dramatic as it may seem, at least for U -max ante . In this case indeed, we are looking for a strategy that is good w.r.t. U -for at least one agent. This means that if it is possible to get for each agent i a strategy that optimizes U -according to this agent (and this can be done by Dynamic Programming, since U -does satisfy the principle of monotonicity), the one with the highest value for U -max ante (L) is globally optimal. Formally:

Proposition 6.1. U -max ante (L) = max i=1,p min(w i , U - i (L)) where U - i (L) = min x j ∈X max(1 -L[x j ], u i (x j ))
is the pessimistic utility of L according to the sole agent i.

It then follows that: Proposition 6.2. Let L be the set of lotteries that can be built on X and let:

• ∆ * = {L * 1 , . . . , L * p } s.t. ∀L ∈ L, U - i (L * i ) ≥ U - i (L); • L * ∈ ∆ * s.t. ∀L * j ∈ ∆ * : max i=1,p min(w i , U - i (L * )) ≥ max i=1,p min(w i , U - i (L * j )).
It holds that, for any L ∈ L, U -max ante (L * ) ≥ U -max ante (L).

Hence, it is enough to optimize w.r.t. each agent separately: First, we keep each of the p strategies returned by the calls (DynProg(T, i)) to a classical Dynamic Programming algorithm (Algorithm (Line 2)); presented in Section 4.3. Then, we to select among them the strategy with the higher U -max ante value. This is the principle of the Multi Dynamic Programming approach detailed by Algorithm 4.

Exact optimization of U +min ante : a Branch and Bound algorithm

Let us finally study the case of U + min ante . Since the preference order defined by this rule does not satisfy the principle of monotonicity, the use of the DynProgAnte algorithm (Algorithm 3) may be suboptimal . In this case like in the previous one, Dynamic Programming may provide a good strategy, but without any guarantee of optimality. value of the current strategy δ the algorithm backtracks, yielding the choice of another action for the last considered decision nodes. When δ is complete, U pperBound(D 0 , δ) = U + min ante (δ).

Algorithm 5: BB: A Branch and Bound algorithm for the optimization of U + min ante Data: A (possibly partial) strategy δ, the evaluation of its utility (U + min ) Result: U +minopt : the value of δ opt i.e. the best strategy found so far begin

if δ = ∅ then D pend ← {D 0 } ; else D pend ← {D i ∈ D s.t. δ(D i ) = ⊥ and ∃D j , δ(D j ) = ⊥ and D i ∈ Succ(δ(D j ))}; // Is δ a complete strategy ? if D pend = ∅ then if U + min > U +-opt then δ opt ← δ; U +minopt ← U + min ; else D next ← arg min D i ∈D pend i ; foreach C i ∈ Succ(D next ) do δ(D next ) ← C i ; U + min ← U pperBound(D 0 , δ); if U + min > U +minopt then U +minopt ← BB(U + min , δ) ;
return U +minopt ;

Conclusion

This Chapter focuses on the optimization of qualitative decision rules for collective decision making in context of possibilistic uncertainty. Since all the ex-post decision rules, as well as U +max ante and U -min ante satisfy the weak monotonicity property, we have proposed to use Dynamic Programming (Algorithm 2 for ex-post decision rules and Algorithm 3 for U +max ante and U -min ante ). For the remaining utilities, the optimization was carried out using exact algorithms: Multi-Dynamic Programming for U +max ante (Algorithm 4) and Branch and Bound for U -min ante (Algorithm 5). The quality of solutions provided by these algorithms is studied in the next Chapter.

CHAPITRE 7

Experimental study

Introduction

This chapter is dedicated to the experimental study of the algorithms presented in Chapter 6. It is organized as follows: Section 7.2 explains the experimental protocol and specifies the structure of the implemented problems, then Section 7.3 provides an empirical comparison of different algorithms in term of CPU time and in term of "quality" of the solutions.

Experimental protocol

In order to explore the feasibility of our algorithms (proposed in the previous chapter), we have implemented them using Java; the computational experiments described in this chapter were carried out on a dedicated PC with an Intel(R) Core(TM)i7-2670 QMCPU, 2.2Ghz processor, 64 bits architecture, 6Gb RAM memory and under Windows 7 operating system. The aim of the experiments is twofold: First of all, we would like to explore the "quality" of solutions, for the problematic cases of U -max ante and U + min ante , where Dynamical Programming can provide a suboptimal strategy and compare the performances of respectively the Multi-Dynamic Programming and the Branch and Bound approaches with those of the sole Dynamic Programming procedure. Secondly, we would like to compare the accuracy of results provided by the ex-post approach as an approximation of the ex-ante approach.

The experiments were performed on complete binary decision trees with different heights. We have considered four sets of problems, the number of decisions to be made in sequence (denoted seq) varying from 2 to 6, with an alternation of decision and chance nodes: at each decision level l (i.e. odd levels), the tree contains 2 l-1 decision nodes followed by 2 l chance nodes. The utility values as well as the weights degrees are randomly fired in the set U = W = {0, 0.1, 0.2, . . . , 0.9, 1} following an equiprobable distribution. Conditional possibilities are chosen randomly in [0, 1] and normalized. Each of the four samples of problems contains 1000 randomly generated trees.

Results and interpretation

Feasibility analysis and temporal performances Tables 7.1 and 7.2 present the execution CPU time of the proposed algorithms for the optimization of respectively the ex-post (Algorithm 2) and the ex-ante criteria (Algorithms 3, 4 and 5) in the case of 3 agents. Obviously, for any algorithm, the execution CPU time increases according to the size of the tree. But the times remains affordable in average even for big trees (341 and 1365 decision nodes). Unsurprisingly, we can check that the approximation performed using Dynamic Programming for U -max ante (resp. U + min ante ) are faster than the Multi-Dynamic Programming and the Branch and Bound algorithm, respectively, which are exact algorithms. Unsurprisingly also, the difference in CPU time between Branch and Bound and the approximation using Dynamic Programming is more important than the difference between Multi-Dynamic Programming and its approximation by Dynamic Programming. As mentioned above, the monotonicity principle does not apply for U -max ante and U + min ante and Dynamic Programming (Algorithm 3) can lead to suboptimal strategies. In order to get an optimal strategy for sure, we must use a complete algorithm, i.e. the Multi-Dynamic Programming (for U -max ante ) and Branch and Bound (for U + min ante ) which may be much slower.

On the other hand, Dynamic Programming may find good strategies, and even the optimal one. That is why we propose to estimate the quality of the approximations by comparing them to the values generated by the multi-Dynamic Programming (for U -max ante ) and Branch and Bound (for U + min ante ).

The comparisons are made as follows: we compute for different trees the number of cases for which the value provided by the approximation (Dynamical Programming) is the optimal one, and for the problems on which it fails, we report the closeness value equal to

V Approx
V Exact where V Approx is relative to the strategy provided by Dynamic Programming (Algorithm 3) and V Exact is the value provided by the exact Algorithms: Multi Dynamic Programming or Branch and Bound.

The results are presented in Tables 7.4 and 7.5: it appears that ex-ante Dynamic Programming provides a very good approximation for the U + min ante case: it provides the same optimal utility as the Branch and Bound Algorithm in about 70% of cases, with an average closeness value of 94%. This is not the case for the approximation of U -max ante , where in most of the time, Dynamic Programming fails to provide the optimal strategy. However, this is not so bad news since Multi-Dynamic Programming is a polynomial algorithm and its experimental CPU time is very affordable. Finally, we complete the picture by a comparison of the ex-post and ex-ante utilities; recall that they are strongly correlated: it holds that U -max post (L) ≥ U -max ante (L) and U + min ante (L) ≥ U + min post (L). It appears that in about 90% of the cases, U + min post (L) = U + min ante (L) but U -max post (L) = U -max ante (L) only in 15% of the cases. We have then repeated the experiment on decision tree (Tables 7.6 and 7.7).

Number of Decision

It appears that in 90% of the cases, the optimal value of U + min post is also optimal for U + min ante . Moreover, even when the ex-post approach fails to get a strategy optimal for the ex-ante one, the quality of the approximation is good, as shown in Table 7.7) . We can conclude that for U + min the ex-post approach is to be a good approximation of the ex-ante one. Since ex-post Dynamical Programming is faster than the Branch and Bound, we can think about using it as an approximate algorithm for getting good ex-ante strategies. Unfortunately this is not the case for U -max . For this rule, the optimal value of U -max post is equal to U -max ante in only 20% of the cases, and the quality of the approximation is low. Uante(δ) Uante * of the U ante value provided by the best ex-post approximation compared to the value of the globally best ex-ante strategy

Number of Decision

Conclusion

In this chapter, we have performed experiments on different decision trees built randomly in order to study the quality of solutions provided by the different algorithms provided in Chapter 6.

We have compared these algorithms w.r.t their execution CPU time, and then we have studied the percentage of accuracy between Dynamic Programming and the pertinent exact algorithms (Multi-dynamic programming and Branch and Bound), on one hand, and percentage of accuracy of the ex-post approach as an approximation of the ex-ante one, on the other hand.

For U +min ante , both approximations are good, and it should be possible to avoid a full Branch and Bound based enumeration. They are not so good for U +max ante , but this has a little impact, since we get a polynomial (and efficient in practice) algorithm for this rule.

CHAPITRE 8

Towards collective decision rules for agents with subjective knowledge

Introduction

In Chapter 5 we have proposed an axiomatic justification of the fully max-oriented and minoriented utilities (U +max and U -min ) in the style of Von Neuman and Morgenstern. In the present chapter, we are interested in a Savage like formalization.

In Section 8.2, we generalize Savage's framework to collective decision making by considering a new dimension relative to agents in addition to the two standard dimensions i.e. events and consequences. Then in Section 8.3, we focus our attention on the particular case of collective decision making under uncertainty by proposing axioms specific to agents and more precisely to their knowledge and their importance. Finally, we show in Section 8.4 that the qualitative collective decision rules U -min and U +max obey these axioms.

Extending Savage's framework for multi-agent decision making under uncertainty

In Savage's original setting [START_REF] Savage | The Foundations of Statistics[END_REF], an act is a function that maps any state to a consequence. In a multi-agent setting, each agent gets a consequence. Formally, let us use the following notations:

• X is the set of consequences,

• S is a set of states,

• A is a set of p agents,

• An act is a function f : S × A → X: f (s, i) denotes the utility of f (s) for agent i. We can also consider that f is a function from S to X p and denote f (s) ∈ X p the vector of elements of X associated by f to s. F is the set of such functions.

• a preference relation on F; denotes its asymmetric part, ∼ its symmetric part.

First of all, we recall the following basic axioms of Savage that apply to our context without any change:

Axiom. (Sav1: Weak order) is complete and transitive.

Axiom. (Sav5: Non triviality) ∃ f, g ∈ F such that f g.

The remaining axioms and definitions proposed by Savage need to be generalized.

Compound acts and the Sure Thing Principle

In Savage's framework, for any event E ⊆ S and any pair of acts f, g, the Compound act f Eg is the act that provides the same consequence as f for any state s ∈ E and the same consequence than g for any state s / ∈ E. In a multi-agent framework, the composition of acts can be generalized as follows: Definition 8.1 (Compound act).

Given two acts f and g and any P ⊆ S × A, the compound act f P g is defined by:

f P g(s, i) = f (s, i) if (s, i) ∈ P, g(s, i) otherwise.
Given two acts f and g and an agent i ∈ A, the f {i}g denotes the compound act f {i} × Sg that provides the same consequences as f for agent i and the same consequences as g for the other agents:

f {i}g(s, j) = f (s, j) if j = i, g(s, j) otherwise.
Given two acts f and g and any event E ⊆ S, the compound act f Eg denotes the compound act f E × Ag that provides the same consequences as f for the states in E and the same consequences as g for the other states: This generalization of the notion of compound acts allows us to straightforwardly extend Savage's Sure Thing Principle to multi-agent decision making under uncertainty as follows:

f Eg(s, i) = f (s, i) if s ∈ E, g(s, i) otherwise .
Axiom (Sav2: "Sure Thing Principle"). For any acts f, g, h, h ∈ F, for any P ⊆ S × A, f P h gP h iff f P h gP h .

Grant et al. [START_REF] Grant | Decomposable choice under uncertainty[END_REF][START_REF] Grant | Weakening the sure-thing principle: decomposable choice under uncertainty[END_REF] proposed a weak version of the Sure Thing Principle, which is mainly a principle of weak decomposability. Another weak form of the Sure Thing Principle has been defined by Dubois et al. [START_REF] Dubois | Qualitative decision theory with sugeno integrals[END_REF][START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF] as a weak independence axiom. They can be written as follows:

Axiom (wSTP: "Weak Decomposability"). For any acts f, g ∈ F, for any P ⊆ S × A, f P g g and gP f g =⇒ f g. Axiom (wSav2: "Weak Independence"). For any acts f, g, h, h ∈ F, for any P ⊆ S × A, f P h gP h =⇒ f P h gP h .

The classical axioms are recovered when A contains only one agent.

After generalizing compound acts, we can now consider the following generalization of the conditioning by restricting to a subset P of A × S: Definition 8.2. (Conditioning on P) ∀P ⊆ A × S, f P g iff ∀h, f P h gP h.

Like in Savage's work, it follows from this definition that P is a weak order: Proposition 8.1. Consider any P ⊆ A × S; we have:

• f ∼ P g iff ∀h ∈ F, f P h ∼ gP h.
• if Sav1 holds, then f P g iff ∀h ∈ F, f P h gP h and ∃ h, f P h gP h.

• P is transitive.

• if Sav1 and wSav2 holds, then P is complete.

Proof of Proposition 8.1.

• f ∼ P g writes ∀h ∈ F, f P h gP h and ∀h ∈ F, f P h gP h which is equivalent to ∀h ∈ F, f P h ∼ gP h

• f P g writes ∀h ∈ F, f P h gP h and ∃h ∈ F, (gP h f P h); Since is complete, we get f P g iff ∀h ∈ F, f P h gP h and ∃h ∈ F, f P h gP h.

• The transitivity of P is obvious: ∀h ∈ F, f P h gP h and ∀h ∈ F, gP h kP h implies ∀h ∈ F, f P h kP h.

• Consider any acts f ,g ∈ F. Three cases are considered (they are exclusive, and exhaustive thanks to Sav1):

-If f P h gP h then by wSav2 we have ∀h , f P h gP h , i.e. f P g;

-If gP h f P h then by wSav2 we have ∀h , gP h f P h , i.e. g P f ;

-If ∀h ∈ F, f P h ∼ gP h we get f ∼ P g. Hence the completeness of P .

We define the restriction of to a subset of I agents, its restriction to a single agent i and its restriction to an event E in a similar way: Definition 8.3.

• ∀E ⊆ S, f E g iff f A×E g. • ∀I ⊆ A, f I g iff f I×S g. • ∀i ∈ A, f i g iff f {i} g.
That is to say: f E g iff for any h, f Eh gEh, f I g iff for any h, f Ih gIh and f i g iff for any h, f {i}h g{i}h. As a corollary of the previous proposition, all these relations are complete and transitive. In Savage's work, an event is null whenever it does not make any difference between the acts; the same definition can be used to characterize null agents: Definition 8.4. (Null agents, null events)

• A set of agents I ⊆ A is null iff ∀f, g, h ∈ F, f Ih ∼ gIh. • An agent i ∈ A is null whenever {i} is null. • An event E ⊆ S is null iff ∀f, g, h ∈ F, f Eh ∼ gEh.
We will see in Section 8.2 how to derive the knowledge of the agents from the global preference relation . But to this extent, we need to develop the notion of constant act, which will allow us to derive from the individual preferences on X.

Constant acts, individual and global preferences of X

Up to this point, the generalization of compound acts and conditioning notions was straightforward; it is slightly more complex for constant acts. Recall that constant acts in the sense of Savage are acts that are constant over the set of states. In our context, we get three notions: acts that gives the same vector of consequences for any state (constant acts), acts that do not make any difference between the agents i.e. in a given state, all receive the same consequence (we call then common acts) and acts that give the same consequence for all agents and all states (we call them representative acts). Definition 8.5.

• A constant act f is an act that maps the same vector of utilities to any state: ∀s, s ∈ S, ∀i ∈ A, f (s, i) = f (s , i).

• A common act f is an act such that whatever f , state s maps the same utility to any agent: ∀s ∈ S,∀i, i ∈ A, f (s, i) = f (s, i ).

• ∀x ∈ X, the representative act of x (denoted by [x]) is the constant (and common) act that provides x to any state and any agent: Proof of Proposition 8.3. Suppose that ∀(s, i), f (s, i) g(s, i); then by wSav3 we have: In other terms, Pareto unanimity also guarantees that construction is well founded, since it allows us to get back the weak form of Axiom CS (Coherence of the scale). Another consequence of Pareto unanimity is that the scale contains an ideal and anti ideal consequence, which we will denote and ⊥. Proposition 8.5. If Pareto Unanimity holds, then there exists and ⊥ ∈ X such as, whatever i ∈ A, h ∈ F,

∀s ∈ S, ∀i ∈ A, f (s, i) = x.
∀(s, i), [f (s, i)] {(s,i)} [g(s, i)];
• if (s, i) ∈ P , then [x]P h(s, i) = x [y]P h(s, i) = y, • if (s, i) / ∈ P , then [x]P h(s, i) = [y]P h(s, i) = h(s, i).
• [ ] f [⊥]. • [ ] i f i [⊥].
Proof of Proposition 8.5. Consider two consequences and ⊥ ∈ X the best and worst consequences (Sav1 allows them to exist: the restriction of on representative acts is a weak order).

• For any f ∈ F, s ∈ S, i ∈ A, it holds that [ ](s, i) = f (s, i); then Pareto implies that [ ] f . In a similar way, it holds that f (s, i) [⊥](s, i) = ⊥; then Pareto implies that f [⊥]. • For any f, h ∈ F, s ∈ S, i ∈ A,
f . • The proof of f i [⊥] is similar to the above proof of [ ] i f .
Because Pareto is a consequence of Sav1, wSav2 and wSav3, we get: Corollary 8.2. If Sav1, wSav2 and wSav3, then there exists and ⊥ ∈ X such as, whatever i ∈ A, h ∈ F,

• [ ] f [⊥]. • [ ] i f i [⊥].
The proof of Corollary 8.2 is obvious and it is a direct consequence of Propositions 8.3 and 8.5.

Likelihood of the events

Classically, the relative likelihood of the events follows from the observation of binary acts, i.e. acts of the form [x]E [y]. This requires the satisfaction of the following axiom, which is a weak form of Savage's fourth axiom. influence of agents, but the axiom CS (Coherence of the scale) that was presented in the previous Section because strongly related to Pareto Unanimity. For the sake of brevity, we assume from this point, that Sav1, wSav2, wSav4, Sav5 are satisfied. Besides, we assume either the Pareto Unanimity axiom, that is a very weak and very natural assumption for collective decision making, or wSav3 that is equivalent to Pareto given Sav1 and Sav2. Let us now study additional axioms that are more related to the presence of several agents.

Additional axioms of collective decision making

The knowledge of an agent, i.e. the relative likelihood that each of them gives to events, may cohere or not. Of course, if ∀i ∈ A, E i D, the principle of Pareto Unanimity implies that E D, i.e. if all the agents share the same knowledge then this knowledge is common (for the collectivity). However, the reciprocal is not necessarily true, since at the present point, nothing forbids that the agents disagree with the likelihood of events. To overcome this, we explicitly assume the following axiom of common knowledge: Axiom (wCok: Weak Common Knowledge). For any events E, D ⊆ S, for any agent non null i ∈ A, E D implies E i D.

It may happen that E

D while E ∼ i D because agent i is not important enough: her preference is drowned when the likelihood of E and D is not high in the scale, and thus not revealed by i . When all the agents are decisive and share the same importance, a stronger axiom can be used: Axiom (Cok: Common Knowledge). For any events E, D ⊆ S, for any agent non null i ∈ A, E D iff E i D.

In some cases, all the agents are equally important; this corresponds to an axiom of anonymity, that guarantees the fairness of the decision: no agent is more important than another and the preference is always stable even by changing the role of any two agents. Formally, we write: Axiom (Ano: Anonymity). For any agents i, j ∈ A, for any acts f, f , g, g ∈ F such that f (s, i) = f (s, j), f (s, j) = f (s, i), g(s, i) = g (s, j), g(s, j) = g (s, i), f g iff f g .

Finally, we shall consider the following axiom that enables each agent to have some power to make decision when others are indifferent.

Axiom (Decision). For any agent

i ∈ A, ∃ f, g, h ∈ F such that f i h g i h.

Axioms of qualitative decision

We finally set Dubois et al's axioms relative to U opt and U pes [START_REF] Dubois | A survey of qualitave decision rules under uncertainty[END_REF][START_REF] Dubois | Qualitative decision theory with sugeno integrals[END_REF][START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF] to the multi-agent context:

Axiom. (RDD: Restricted disjunctive dominance) Let f and g be any two acts and [x] be a representative act of value x: f g and f x ⇒ f g ∨ [x] (where g ∨ [x] gives the best of the results of g(s, i) and x in each pair (s, i)).

Axiom. (RCD: Restricted conjunctive dominance) Let f and g be any two acts and [x] be a representative act of value x: g f and x f ⇒ g ∧ [x] f (where g ∧ [x] gives the worst of the results of g(s, i) and x in each pair (s, i)).

Axiom. (N C: Non compensation) Whatever E ⊆ S, x, y ∈ X:

• [ ]E[y] ∼ y or [ ]E[y] ∼ [ ]E[⊥]. • [x]E[⊥] ∼ x or [x]E[⊥] ∼ [ ]E[⊥].
The meaning of the axioms does not change when extended to the multi-agent context: Axiom RDD says that if an act f is preferred to an act g and also preferred to a representative act x, then f still preferred to g even if the worst consequences of g are improved to the value x. Axiom RCD is the dual property of the restricted disjunctive dominance. It allows a partial decomposability of qualitative utility with respect to the conjunction of acts in the case where one of them is constant.

The other axioms can be written without any modification:

Axiom. (DD: Disjunctive dominance) Let f ,g,h be any three acts: f g and f h ⇒ f g ∨ h.

Axiom. (RCD: Conjunctive dominance) Let f ,g,h be any three acts: f g and f h ⇒ f g ∧ h.

Axiom. (P es: Pessimism) ∀f, g ∈ F and E ⊆ S. If f Eg f then f gEf .

Axiom. (Opt: Optimism) ∀f, g ∈ F and E ⊆ S. If f f Eg then gEf f .

Properties of collective qualitative decision rules in style of Savage

We now study the fully min-oriented and max-oriented decision rules in light of the axioms presented above. Hence, we show that these axioms are consistent and obeyed by the pessimistic egalitarian utility (U -min ) and by its optimistic counterpart (U + max ). We suppose here, without loss of generality, that X is a subset of [0, 1] and consider a set of acts F built from S × A to X ⊆ [0, 1] (with {0, 1} ⊆ X); a possibility distribution of S and a set of weights w i . U -min and It holds that:

Proposition 8.8.

The relation defined by: f g iff U -min (f ) ≥ U -min (g), satisfies axioms Sav1, Sav5, wSav2, wSav3, wSav4, P aretoU nanimity, N C, RDD, P ES, wCS and wCoK.

If we suppose that we are in a pure egalitarian context (w i = 1, i = 1, p), we get: Proof of Proposition 8.8.

U -min (f ) = min

•

trivially satisfies Sav1 (each act is given by a global utility on [0, 1]).

• satisfies wSav2: Consider f, g, h ∈ F, P ∈ S × A such that U -min (f P h) U -min (gP h) and any fourth act h , Let: a = min • satisfies RDD because it satisfies N C, Sav1 and wSav3.

• satisfies P ES. This is due to the fact that U -min is an ex-post utility; actually, setting u( (f (s))) = min(max(1 -w i , f (s, i))), we get U -min (f ) = min s∈S max(1 -π(s), u( (f (s)))): U -min is a classical pessimistic utility (the sole agent being the collectivity) and thus satisfies P ES.

Proof of Proposition 8.9. Using Proposition 8.8, we have proved that axioms Sav1, Sav5, wSav2, wSav3, wSav4, Pareto Unanimity, N C, RDD and P ES are satisfied. For axioms CS , Cok, Ano and Decision the proof is performed as follows:

• The relation satisfies anonymity axiom (Ano):

Consider acts f , g, f and g ∈ F, and two agents i, j ∈ A f (s, i) = f (s, j), f (s, j) = f (s, i), g(s, i) = g (s, j), g(s, j) = g (s, i). We have: U -min (f ) = min min Since f (s, i) = f (s, j), f (s, j) = f (s, i) and let f (s, k) = f (s, k) for all k = i, j, we get U -min (f ) = U -min (f ). We obtain in the same way U -min (g) = U -min (g ). Hence, U -min (f ) ≥ U -min (g) iff U -min (f ) ≥ U -min (g ), which proves Ano. The same kind of result can be obtained for the optimistic case.

Proposition 8.10.

The relation defined by: f g iff U + max (f ) ≥ U + max (g), satisfies axioms Sav1, Sav5, wSav2, wSav3, wSav4, P aretoU nanimity, N C, RCD, OP T , wCS and wCoK.

If we suppose that we are in a pure egalitarian context (w i = 1, i = 1, p), we get: This shows the coherence and the relevance of our set of axioms.

U + max (f ) = max
Proof of Proposition 8.10. The proofs are very similar to the ones presented for the pessimistic utility.

•

trivially satisfies Sav1 (each act is given by a global utility on [0, 1]).

• satisfies wSav2: Consider f, g, h, P such that U -min (f P h) U -min (gP h) and any fourth act h U + max (f P h ) ≥ U + max (gP h ).

• Pareto unanimity follows from the fact that the max and min operators are monotonic.

• wSav3 follows from Sav1, wSav2 and Pareto Unanimity.

• The proof of wSav4 is similar to the one given for the pessimistic case, considering that U + max ([x]E[y]) = median(x, Π(E), y).

• Sav5 is satisfied by construction.

• The proof of wSav4 are similar to the ones given for the pessimistic case, considering that U + max ([x]E [y]) writes as a mono-agent optimistic utility.

• The proofs of wCoK and N C are similar to the ones given for the pessimistic case, considering that U + max ([x]E[y]) = median(x, Π(E), y) ∀E ⊆ S.

• wCS is a consequence of Pareto Unanimity and Sav1.

• satisfies RCD because it satisfies N C, Sav1 and wSav3.

• satisfies OP T since U + max is an ex-post utility; setting u( (f (s))) = max (min(w i , f (s, i)), we get U + max (f ) = max s∈S min(π(s), u( (f (s))): U + max is a classical optimistic utility and thus satisfies OP T .

Proof of Proposition 8.11. We only need to prove that axioms CS , Cok, Ano and Decision are satisfied. The remaining proofs are easy and similar to the ones given for the pessimistic case.

• The relation satisfies anonymity axiom (Ano):

Consider acts f , g, f and g ∈ F, and two agents i, j ∈ A f (s, i) = f (s, j), f (s, j) = f (s, i), g(s, i) = g (s, j), g(s, j) = g (s, i). We have: U + max (f ) = max max Since f (s, i) = f (s, j), f (s, j) = f (s, i) and let f (s, k) = f (s, k) for all k = i, j, we get U + max (f ) = U + max (f ).

We obtain in the same way U + max (g) = U + max (g ) Hence U + max (f ) ≥ U + max (g) iff U + max (f ) ≥ U + max (g ), which proves Ano. • The proofs of CoK is similar to the ones given for the pessimistic case, considering that U + max ([x]E[y]) = median(x, Π(E), y).

Conclusion

This Chapter makes a first attempt to propose an analysis of the possibilistic collective decision rules in the style of Savage. Some basic axioms (Sav1, Sav5, OP T , P ES) stand without any change. Others like wSav3 and wSav4 are extended thanks to the notion of representative act of a consequence (that plays the same role as the notion of constant act in Savage's framework).

We also extend or propose additional axioms specific to multi-agent context -e.g.

101

U + max satisfy our extension of [START_REF] Dubois | A survey of qualitave decision rules under uncertainty[END_REF][START_REF] Dubois | Qualitative decision theory with sugeno integrals[END_REF][START_REF] Dubois | Decision-theoretic foundations of qualitative possibility theory[END_REF]'s axioms for respectively U pes and U opt as well as additional axioms. This axiomatic opens the way to a Savage-like representation theorem for U -min and U + max in the style of Savage that may be proposed.

The framework presented here imposes that all agents have the same knowledge (as in VNM's framework) and share the same preference order on X. However, it is also important to consider the case where agents have different view on the environment (different knowledge). It has been proved, in the case of probabilistic context [START_REF] Broome | Weighing Goods: Equality, Uncertainty and Time[END_REF][START_REF] Chambers | Preference aggregation under uncertainty: Savage vs. pareto[END_REF][START_REF] Gilboa | Utilitarian aggregation of beliefs and tastes[END_REF], that subjective knowledge leads to an impossibility result but what about possibilistic uncertainty?

CONCLUSION General conclusion

Our contribution proposes new decision criteria for collective decision making under possibilistic uncertainty for cautious as well as adventurous decision makers. This approach offers to decision makers the possibility to find the best decision which satisfies the collectivity taking into account the uncertainty aspect of the problem, the decision makers attitude towards this uncertainty, and the method of aggregating the agents' preferences. These considerations as well as the manner to combine them (either ex-ante or ex-post aggregation), give rise to different decision criteria namely, eight qualitative collective decision rules. We have proved the coincidence between the ex-ante and ex-post homogenous utilities for both the fully min-oriented and max-oriented cases: it is worth noticing that the use of qualitative decision criteria allows to get rid of the timing effect even while being egalitarian.

On the basis of a set of rational axioms, we have provided a representation theorem for the fully pessimistic and optimistic utilities in the style of VNM for agents with identical or different weights. This result can be seen as an ordinal counterpart of Harsanyi's theorem. Making a step further, we have provided a first attempt to propose an analysis of the multi-agent qualitative decision making in the style of Savage. Furthermore, we have presented an algorithmic study relative to the optimization of the proposed collective qualitative decision rules in possibilistic decision trees. We have provided an adaptation of the Dynamic Programming algorithm for criteria that satisfy the monotonicity property, Multi-Dynamic Programing and Branch and Bound algorithms for those that are not monotonic. Finally, an experimental study has been performed to compare the different algorithms and to evaluate the quality of the solutions provided.

The seminal work of Harsanyi [START_REF] Harsanyi | Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility[END_REF] is generally interpreted as a justification of utilitarianism. However, our work may be seen as an ordinal counter part of Harsanyi's theorem and as a justification of egalitarianism when pessimistic agents have to make decisions that satisfy the collectivity. These results have true been presented under the assumption that all agents share the same knowledge, which is seldom in real world problem. This consideration has been the topic of several works, always in the probabilistic context (in style of Savage), that led to an impossibility theorem when agents have heterogeneous knowledge about states of world [START_REF] Aspremont | A Welfarist Version of Harsanyi's Aggregation Theorem[END_REF][START_REF] Mongin | Consistent bayesian aggregation[END_REF]. Thus, it is interesting to address this question in context of possibility theory. In this case, the definition of the decision rules must be revised especially for the ex-post aggregation when collectivity is first considered. Thus, we may consider only ex-ante decision rules or provide a new form of aggregation.

Moreover, in our formalism we suppose that all agents are either optimistic or pessimistic. But, it may happen that agents have different attitudes toward uncertainty: the group of decision makers may gather pessimistic as well as optimistic persons, then the study of such situations may be envisaged. Likewise, we shall extend our approach, considering that the importance of the decision makers is not absolute but may depend on the consequence of each decision.

Besides, the possibilistic aggregations used in this work are basically specializations of the Sugeno integral. So, we aim at generalizing the study of collective decision making under uncertainty through the development of double Sugeno Integrals. Also, on the basis of the pessimistic utility we have proved that egalitarianism is compulsory to avoid the timing effect problem. So, what about the use of other possibilistic decision rules (e.g. Binary possibilistic utility, Order of Magnitude Expected utility, Possibilistic likely dominance, etc.) or even the use of different uncertainty theories such evidence theory [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] or rough set theory [START_REF] Pawlak | Rough sets[END_REF].

Another line of research to consider is the refinement of the decision rules. In fact, since they are based on possibilistic utilities (U opt and U pes ) our criteria as many qualitative decision rules suffer from a lack of decisiveness, called the "drowning effect", due to the use of the idempotent operations max and min. So, it is interesting to consider the refinement of these criteria to more discriminating ones on the basis of existing works in the literature [START_REF] Fargier | Qualitative decision under uncertainty: back to expected utility[END_REF][START_REF] Weng | Qualitative decision making under possibilistic uncertainty: Toward more discriminating criteria[END_REF].

From an algorithmic point of view, the difference of attitude and/or knowledge of the agents may raise several difficulties. In these cases, the upcoming criteria may suffer from the lack of monotonicity and their optimization in possibilistic decision trees can not be performed using a Dynamic Programming algorithm anymore. An alternative idea is the deliberation of agents after each decision. In this case, the Dynamic Programing algorithm shall be used but it leads to an approach that is neither the ex-ante nor the ex-post aggregation.

Finally, we can notice that there is a growing interest in the literature to adapt graphical decision models (decision trees [START_REF] Raiffa | Decision Analysis-Introductory lectures on choices under uncertainty[END_REF], influence diagrams [START_REF] Howard | Influence diagrams[END_REF], Markov decision process [START_REF] Bellman | A Markovian Decision Process[END_REF] or Valuation Based Systems [START_REF] Shenoy | Valuation-based systems for Bayesian decision analysis[END_REF]) to handle more complex decision problems. In [START_REF] Garcia | Possibilistic influence diagrams[END_REF] for example, the authors propose qualitative counterpart of influence diagrams. An adaptation of Markov decision process to the possibilistic context has also been proposed by [START_REF] Sabbadin | Possibilistic markov decision processes[END_REF][START_REF] Sabbadin | Towards qualitative approaches to multistage decision making[END_REF]. Other works have been provided to consider other aspects such as multiple objective decision making in influence diagrams [START_REF] Diehl | Influence diagrams with multiple objectives and tradeoff analysis[END_REF][START_REF] Marinescu | Multi-objective influence diagrams[END_REF]. So, why not provide new graphical models for qualitative multi-criteria or multi-agent decision making problems.

  10, 0.3/20 and L 2 = 0.4/10, 0.6/20 be two probabilistic lotteries. Consider the compound lottery L = 0.5/L, 0.5/L . L can be reduced into the single stage lottery L = 0.55/10, 0.45/20 presented in Figure 1.1.

Figure 1 . 1 :

 11 Figure 1.1: A compound probabilistic lottery (a) and its reduction (b)

Figure 1 . 2 :

 12 Figure 1.2: Compound act f Eg

Figure 2 . 1 :

 21 Figure 2.1: A possibilistic compound lottery (a) and its reduction (b).

CHAPTER 3 .

 3 COLLECTIVE DECISION MAKING 29

Figure 3 . 1 :

 31 Figure 3.1: Two probabilistic lotteries in a bi-agent context.

  Axiom. (Hars1) The preference relation of each agent i over lotteries satisfies Von Neumann and Morgenstern's axioms. This axiom summarizes VNM's assumptions relative to expected utility for each individual utility u i (x) and enforces the representation of individual preferences by expected utilities. Axiom. (Hars2) The collective preference relation satisfies also Von Neumann and Morgenstern's axioms. Axiom Hars2 requires, again, the use of expected utility to represent the preference relation of the collectivity. In addition to these two axioms, Harsanyi imposes another condition relating collective preferences to individual ones, which is Pareto indifference axiom. Axiom. (PI: Pareto Indifference) If two decisions are indifferent for each agent they are considered as collectively indifferent. In [59], Harsanyi has shown that if the three assumptions (axioms Hars1, Hars2 and PI) are satisfied by individual as well as collective preferences i.e. (i) the collective preference satisfies Von Neumann and Morgenstern's axioms, (ii) the preferences of each agent also satisfy these axioms, and (iii) if two lotteries are indifferent for each agent they are considered as collectively indifferent (Pareto indifference axiom), then the only appropriate collective utility function (CUF) is the utilitarian one. Theorem 3.1. If axioms Hars1, Hars2 and PI are satisfied by the collective preference relation as well as individual ones and considering anonymity, there exists a set of individual utilities u i (x) relative to a consequence x ∈ X and weights λ i ∈ R such that:

Figure 3 . 2 :

 32 Figure 3.2: Example of Diamond[START_REF] Diamond | Cardinal welfare, individualistic ethics, and interpersonal comparison of utility: Comment[END_REF]

  Example 4.1.

  Figure 4.1 depicts an example of a probabilistic (a) and a possibilistic (b) decision tree. The two models share the same graphical component with three decision nodes D = {D 0 , D 1 , D 2 }, six chance nodes C = {C 1 , C 2 , C 3 , C 4 , C 5 , C 6 } and ten leave nodes C = {LN 1 , LN 2 , LN 3 , LN 4 , LN 5 , LN 6 , LN 7 , LN 8 , LN 9 , LN 10 } with U = {0.1, 0.2, 0.3, 0.4, 0.5}. However, the uncertainty degrees pertaining to chance nodes are defined with probability distributions in (a) and possibility distributions in (b).

Figure 4 . 1 :

 41 Figure 4.1: Example of a probabilistic decision tree (a) and a possibilistic decision tree (b).

Figure 4 .

 4 1 (a)), the strategy δ 1 corresponds to the lottery 0.6/L C 3 , 0.4/L C 5 where L C 3 = 0.8/1, 0.2/5 and L C 5 = 0.7/1, 0.3/4 . Then we have:Reduction(δ 1 ) = 0.76/1, 0.12/4, 0.12/5 . For the possibilistic decision tree (Figure4.1 (b)), the strategy δ 1 corresponds to the lottery 1/L C 3 , 0.5/L C 5 where L C 3 = 1/0.1, 0.2/0.5 and L C 5 = 1/0.1, 0.3/0.4 . The reduction is performed as follows: Reduction(δ 1 ) = 1/0.1, 0.3/0.4, 0.2/0.5 .

Example 4 . 3 .

 43 Let us consider the decision tree inFigure 4.1 (b). The optimal strategy relative to this possibilistic decision w.r.t. U opt returned by Dynamic Programing (Algorithm (Line 2)) is highlighted by bold lines in Figure 4.2, where:

Figure 4 . 2 :

 42 Figure 4.2: The optimal strategy δ * (D 0 ) = C 1 , δ * (D 1 ) = C 4 , δ * (D 2 ) = C 6 .

x 2 :Figure 5 . 1 :

 251 Figure 5.1: Two bi-agent possibilistic lotteries.

1 .

 1 Let us show that U + min ante (L) = 1 -U τ -max ante (L), (i.e. 1 -U + min post (L) = U τ -max post (L)), other utilities can be proved in the same way. 1 -U + min ante (L) = 1 -[min i∈A max((1 -w i ), max x∈X min(u i (x), L[x]))] = max i∈A min(w i , min min x∈X max(1 -u i (x), (1 -L[x]))) = max i∈A min(w i , min x∈X max(u τ i (x), (1 -L[x]))) = U τ -max ante (L).

Figure 5 . 2 :

 52 Figure 5.2: Lotteries L and L relative to counter-example 5.1

CHAPTER 5 .

 5 COLLECTIVE POSSIBILISTIC DECISION MAKING APPROACH 54 can show by the following counter-examples that Pareto unanimity axiom is violated by U -max post (counter-example 5.2) and that U -max ante may fail to satisfy weak independence (counter-example 5.3).

Figure 5 . 3 :

 53 Figure 5.3: A counter-example to pareto unanimity for U -max post criterion.

Figure 5 . 4 :

 54 Figure 5.4: A counter-example to weak independence for U -max ante criterion.

Proof of Theorem 5. 1 .

 1 According to Dubois and Prade's result relative to pessimistic utility, since satisfies axioms A1 -. . . A6 -it exists an order reversing function n: V → X such that: L L iff min x∈X max (n(L[x]), x) min x∈X max (n(L [x]), x).

  Summing up Dubois and Prade's result relative to the pessimistic utility and considering u(x) = argmin ¤ x i , we can rewrite Theorem 5.1 such as: L L ssi min x∈X max(n(L[x]), min i∈A u i (x)) ¤ min x∈X max(n(L [x]), min i∈A u i (x)).

CHAPTER 5 .

 5 COLLECTIVE POSSIBILISTIC DECISION MAKING APPROACH 62

8 .

 8 This proof relative to Proposition 5.8 is very similar to the one one relative to 5.4 by replacing the min operator by max, max by min, (1 -L[x]) by L[x], (1 -w i ) by w i and axioms A1 -. . . A6 - by axioms A1 + . . . A6 + . As shown by counter-example 5.4, U + min post fails to satisfy Pareto Unanimity. Likewise, U + min ante violates the weak independence axiom (counter-example 5.5).

x 2 :Figure 5 . 5 :

 255 Figure 5.5: A counter-example to Pareto Unanimity for U + min ante criterion.

Figure 5 . 6 :

 56 Figure 5.6: A counter-example to weak independence for U + min ante criterion.

Figure 6 . 1 :

 61 Figure 6.1: Possibilistic decision tree for Example 6.1.

Figure 6 . 2 :

 62 Figure 6.2: Possibilistic decision tree for Example 6.1 with aggregated utilities.

Algorithm 3 :

 3 DynProgAnte: An adaptation of Dynamic Programming algorithm for the optimization of "ex-ante" decision rules Data: a node N Result: An optimal strategy δ and its value u * begin// Chance nodes if X ∈ C then // (Optimistic / Pessimistic) utility foreach Y ∈ Succ(N ) do u Y ← DynP rogAnte(Y ) ; for i ∈ {1, . . . , p} do u N [i] = (u i ⊗ λ y ) ; u N [i] = ( u N [i] ⊕ u N [i]); // where ⊗ = min (resp. max), λ Y = π(Y ) (resp. 1 -π(Y )) and ⊕ = max (resp. min) in the case of optimistic (resp. pessimistic) utility // Decision nodes if X ∈ D then // Choice of the best decision

Figure 7 . 1 :

 71 Figure 7.1: Structure of the generated decision trees for seq = 2.

Figure 8 . 1 :Figure 8 . 1

 8181 Figure 8.1: Multi-agent compound act

  the repeated application of Proposition 8.2 leads to f g. Conversely, it is possible to show that wCond (and thus wSav3 and wCS) is a consequence of Pareto. Proposition 8.4. If Pareto Unanimity is satisfied then wCond holds. Proof of Proposition 8.4. Consider any P ⊆ A × S and let x and y be two consequences such that [x] [y] (and thus x y) and consider the compound acts [x]P h and [y]P h; it holds that ∀i ∈ A:

CHAPTER 8 . 95 U

 895 TOWARDS COLLECTIVE DECISION RULES FOR AGENTS WITH SUBJECTIVE KNOWLEDGE + max write:U -min (f ) = min i=1,p max(1 -w i , min s∈S max(f (s, i), 1 -π(s))). = min s∈S max(1 -π(s), min i=1,p max(1 -w i , f (s, i))). U + max = maxi=1,p min(w i , max s∈S min(f (s, i), π(s))). = max s∈S min(π(s), max i=1,p min(w i , f (s, i))).

  i=1,p min s∈S max(f (s, i), 1 -π(s))).In this case, the preference relation satisfies Ano and Decision. Since the agents' weights do not have a role anymore, CS and Cok are satisfied in their full strength: Proposition 8.9. The relation defined by:f g iff min i=1,p min s∈S max(f (s, i), 1 -π(s))) ≥ min i=1,p min s∈S max(g(s, i), 1 -π(s))),satisfies axioms Sav1, Sav5, wSav2, wSav3, wSav4, P aretoU nanimity, N C, RDD, P ES, CS, Cok, Ano as well as Decision.

s∈P max( 1

 1 -π(s), min i∈A max(1 -w i , f (s, i))), b = min s∈P max(1 -π(s), min i∈A max(1 -w i , g(s, i))), c = min s∈ P max(1 -π(s), min i∈A max(1 -w i , h(s, i))), c = min s∈ P max(1 -π(s), min i∈A max(1 -w i , h (s, i))).•satisfies N C because whatever x, y, E, U -min ([x]E[y]) = median(x, N (E), y).

  s∈S max(f (s, i), 1 -π(s)), min s∈S max(f (s, j), 1 -π(s)), min k =i,j;s∈S max(f (s, k)), 1 -π(s)).Besides, we have:U -min (f ) = min min s∈S max(f ( s, i), 1 -π(s)), min s∈S max(f (s, j), 1 -π(s)).min k =i,j;s∈S max(f (s, k)), 1 -π(s)).

• 98 --

 98 satisfies Dec, since U -min ([1]{i}[START_REF]Harsanyi's theorem without the sure-thing principle: On the consistent aggregation of monotonic bernoullian and archimedean preferences[END_REF]) = 1 > U -min ([0]{i}[START_REF]Harsanyi's theorem without the sure-thing principle: On the consistent aggregation of monotonic bernoullian and archimedean preferences[END_REF]) = 0.• satisfies CS: Suppose that [x] [y], i.e. U -min ([x]) = x > U -min ([y]) = y. It holds that: U -min ([x]{i}1) = x > U -min ([y]{i}1) = y. Hence, ∀h, U -min ([x]{i}h) ≥ U -min ([y]{i}h) (by wSav2) and ∃h, U -min ([x]{i}h) > U -min ([y]{i}h).Thus [x] i [y]. • satisfies CoK: CHAPTER 8. TOWARDS COLLECTIVE DECISION RULES FOR AGENTS WITH SUBJECTIVE KNOWLEDGE We know that wCok holds, thus E ∼ D implies E ∼ i D. Consider two events E, D such that E D, i.e. ∀x, y such that x > y, U -min (xEy) > U -min (xDy). Since U -min ([x]E[y]) = median(x, N (E), y) and U -min ([x]D[y]) = median(x, N (D), y). Thus for any x, y such that x > y, median(x, N (E), y) > median(x, N (D), y). Suppose now that there is a i such that D i E, which means that * ∀x > y, ∀h, U -min ([x]E×{i}[y] Ē×{i}h) ≥ U -min (([x]D×{i}[y] D×{i}h), This implies that U -min ([x]E ×{i}[y] Ē ×{i}1) ≥ U -min (([x]D ×{i}[y] D ×{i}1). Moreover, U -min ([x]E×{i}[y] Ē×{i}1) = median(x, N (E), y) and U -min ([x]D× {i}[y] D × {i}1) = median(x, N (D), y). So we get median(x, N (D), y) ≥ median(x, N (E), y), which contradicts median(x, N (E), y) > median(x, N (D), y). Hence there cannot be a i such that D i E, i.e. E i D. This shows that E D implies E i D: We thus get E D iff E i D: CoK is satisfied.

  (s, i), π(s))). and we recover Ano, Decision, CS and Cok: Proposition 8.11. The relation defined by:f g iff max i=1,p max s∈S min(f (s, i), π(s))) ≥ max i=1,p max s∈S min(g(s, i), π(s))),satisfies axioms Sav1, Sav5, wSav2, wSav3, wSav4, P aretoU nanimity, N C, RCD, OP T , CS, Cok, Ano as well as Decision.

  Let a = max s∈P min(π(s), maxi∈A min(w i , f (s, i))), b = max s∈P min(π(s), max i∈A min(w i , g(s, i))), c = max s∈ P min(π(s), max i∈A min(w i , h(s, i))), c = max s∈ P min(π(s), max i∈A min(w i , h (s, i))),It holds that:U + max (f P h) = max(a, c) U + max (gP h) = max(b, c) U + max (f P h ) = max(a, c ) U + max (gP h) = max(b, c )max(a, c) > max(b, c) implies that max(a, c ) ≥ max(b, c ) i.e.

  s∈S min(f (s, i)), π(s)),max s∈S min(f (s, j), π(s)). max k =i,j;s∈S min(f (s, k)), π(s)).Besides, we have:U + max (f ) = max max s∈S min(f (s, i)), π(s)), max s∈S min(f (s, j), π(s)).max k =i,j;s∈S min(f (s, k)), π(s)).

•

  satisfies Dec, since U + max ([1]{i}[0]) = 1 > U + max ([0]{i}[0]) = 0 • satisfies CS: Suppose that [x] [y] since U + max ([x]{i}0) = x > U + max ([y]{i}0) =y. Hence ∀h, U + max ([x]{i}h) ≥ U + max ([y]{i}h) (by wSav2) and ∃ h, U + max ([x]{i}h) > U + max ([y]{i}h). Thus [x] i [y].

  Utility and possibility scales are commensurate or not: We can find possibility-based likely dominance (denoted by LΠ) and necessity-based likely dominance (denoted by LN ) [23, 39]. • Utility and possibility scales are commensurate and utilities are quantitative: In this class we have possibility-based Choquet integrals (denoted by Ch Π ) and necessity-based Choquet integrals (denoted by Ch N ) [79].

Algorithm 1 :

 1 DynProg(N :Node, δ: Strategy) Data: O is the criterion to optimize.

	Result: A lottery L
	begin
	// Initialization
	for i ∈ {1, . . . , n} do L[u i ] ← 0;
	// Leaves
	if N ∈ LN then L[u(N )] ← 1;
	// Chance nodes
	if N ∈ C then
	// Reduce the compound lottery
	foreach Y ∈ Succ(N ) do
	L Y ← DynP rog(Y, δ);
	for i ∈ {1, . . . , n} do

(Line 1)

  O Weak monotonicity Transitivity Algorithm Complexity

	U pes	Yes	Yes	DynProg	P
	U opt	Yes	Yes	DynProg	P
	P U	Yes	Yes	DynProg	P
	OMEU	Yes	Yes	DynProg	P
	LN	Yes	No	ExtDynProg	P
	LΠ	Yes	No	ExtDynProg	P
	Ch N	No	Yes	BB	NP-hard
	Ch Π	No	Yes	BB	NP-hard
		Table 4.1: Optimization of possibilistic criteria

  and x i i x * , by transitivity we have ∀k = i, x i i x k . Then L ∼ i x i . Since x ∼ i x i and ∼ i is transitive, we obtain L ∼ i x, and this for each agent i. Using Pareto Unanimity, we can deduce that L ∼ x.

From L ∼ x and L ∼ argmax {x i , i ∈ A}, we can conclude by transitivity that: x ∼ argmax {x i , i ∈ A}.

Table 7 .

 7 2: Average CPU time (in milliseconds) for ex-ante utilities Furthermore, to study the effects of varying the number of agents, we consider the optimization of U -max ante , for reasonable trees (85 decision nodes) with p agents from 4 to 7, using the more timeconsuming algorithm (Branch and Bound). Clearly, as shown in Table7.3, the average CPU time with 4 agents, is about 2 milliseconds and the maximal CPU time for decision trees with 7 agent is less than 4 milliseconds. Thus, we can say that the results are good enough to allow the handling of real-size problems.

			U -min	U + max	U -max post	U + min post
	Decision nodes number\Algorithm DynProg DynProg DynProg DynProg 5 0.068 0.071 0.068 0.067 21 0.073 0.075 0.083 0.075 85 0.076 0.082 0.090 0.082 341 0.126 0.128 0.140 0.132 1365 0.215 0.207 0.235 0.211
	Table 7.1: Average CPU time (in milliseconds) for ex-post utilities
				U -max ante	U + min ante
	Decision nodes number\Algorithm DynProg MultiDynProg DynProg 5 0.079 0.172 0.074 21 0.096 0.203 0.084 85 0.120 0.247 0.097 341 0.147 0.295 0.139 1365 0.254 1.068 0.231	BB 0.576 1.012 1.252 1.900 5.054
			Number of agents
		4	5	6	7
	U -max ante	2.190 3.237 3.782 3.863

Table 7 .

 7 3: Average CPU time (in milliseconds) for U -max ante using Branch and Bound algorithms for trees with 85 decision nodes

	Quality of the approximations of U -max ante and U +min ante

Table 7 .

 7 4: Percentage of problems for which the Dynamical Programming value is correct

	Nodes

Table 7 .

 7 5: Average closeness value Uante(δapprox) Uante(δ optimal ) of the strategy provided by ex-ante Dynamical Programming

Table 7 .

 7 6: Percentage of problems for which the ex-post optimal strategy is also ex-ante optimal

	Nodes

Table 7 .

 7 7: Average closeness value

  Proposition 8.2. If Sav1 and wSav2 hold then for any disjoint subsets P, P of A × S, if f P g and f P g then f P ∪P g. Proof of Proposition 8.2. Suppose that f P g and f P g, i.e. that ∀h, f P h gP h and ∀h, f P h gP h. Then, thanks to wSav2 for any h we have: f P f P gP f P h and ∀h, gP f P h gP gP h; by transitivity we get ∀h, f P f P h gP gP h, i.e. f P ∪P g. Pareto Unanimity axiom; that is essential for collective decision making; is defined as follows: Axiom (Pareto Unanimity). If ∀i, s, f (s, i) g(s, i), then f g. Proposition 8.3. If Sav1, wSav2 and wSav3 then Pareto Unanimity holds.

	It holds that:

  consider the act [ ]{i}h and f {i}h. It holds that ∼ f {i}h(s, j) for any s, j = i. Then by Pareto unanimity we get [ ]{i}h f {i}h. Since we did not put any restriction on h, [ ]{i}h f {i}h for any h, i.e. [ ] i

[ ]ih(s, i) = f {i}h(s, i) = f (s, i) for any s besides [ ]ih(s, j) = h(s, j)

  Ano, Dec, Common Scale and Common Knowledge -. The last part of the Chapter shows that U -min and CHAPTER 8. TOWARDS COLLECTIVE DECISION RULES FOR AGENTS WITH SUBJECTIVE KNOWLEDGE

The min oriented and max oriented decision rules have received an interpretation in context of Multicriteria decision making to aggregate criteria rather than agents preferences[START_REF] Dubois | Weighted minimum and maximum operations in fuzzy set theory[END_REF].

If |B i | > 1, m ican be any one of its elements.

In the following, there are many relations (preorders). For the sake of clarity, we may indicate for each minimum or maximum operation the preorder it relies on.

Remerciements

Lemma 5.1. ∀x ∈ X, i = 1, p, x i ∼ max i (m i , x i ).

Proof of Lemma 5.1.

• Case 1: x i i m i : then trivially max i (m i , x i ) = x i . Since is reflexive, then x i ∼ max i (m i , x i ).

• Case 2: m i i x i : by definition of m i , we have: m i = argmax i {x i : x i ∼ (x * ) i }, then m i is a particular x i , such as x i ∼ (x * ) i . Then, we can say that (i) m i ∼ (x * ) i . Furthermore, from Proposition 5.6 we have (ii) x i (x * ) i . From (i) and (ii) and since is transitive and reflexive we can say that x i m i . Hence, we can deduce that m i i x i involve x i ∼ max i (m i , x i ).

Lemma 5.2. ∀x ∈ X, x ∼ argmin {x i : i ∈ A}.

Proof of Lemma 5.2.

We consider the lottery L = 1/x 1 , . . . , 1/x p . Since is a pessimistic utility (satisfies Dubois and Prade's axioms) and the x i s are constant acts; then we have:

Since i s relations are pessimistic utilities (satisfy Dubois and Prade's axioms), for each agent i have:

Since ∀k = i, x k ∼ i x * , and x * i x i , by transitivity we have ∀k = i, x k i x i . Then L ∼ i x i . Besides, since x ∼ i x i and ∼ i is transitive, we obtain L ∼ i x, for each agent i. Using Pareto Unanimity axiom, we can deduce that L ∼ x. From L ∼ x and L ∼ argmin {x i , i ∈ A}, we can deduce by transitivity that: x ∼ argmin {x i , i ∈ A}.

From Lemmas 5.1 and 5.2 we get:

Proof of Corollary 5.1. From Lemmas 5.1 and 5.2, we have respectively:

Then the proof of this corollary is trivial by replacing x i in (ii) by max i (m i , x i ) from (i).

As an alternative, we have chosen to proceed by an implicit enumeration via a Branch and Bound algorithm, following the approach proposed by Ben Amor et al. [START_REF] Ben Amor | Possibilistic sequential decision making[END_REF] for Possibilistic Choquet integrals and by Gildas and Spanjaard [START_REF] Gildas | Rank-dependent probability weighting in sequential decision problems under uncertainty[END_REF] for Rank Dependent Utility (both in the mono agent case). The Branch and Bound procedure (see Algorithm 5) takes as argument a partial strategy δ and an upper bound of the U + min ante value of its best extension. It returns the U + min ante value of the best strategy found so far, δ opt . As initial value for δ we retain the empty strategy (δ(D i ) = ⊥, ∀D i ). We initialize δ opt with the strategy provided by the Dynamic Programming: indeed, even not necessarily providing an optimal strategy, this algorithm generally provides a good one. At each step of the Branch and Bound algorithm, the current partial strategy, δ, is developed by the choice of an action for some unassigned decision node. When several decision nodes are candidate, the one with the minimal rank (i.e. the former one according to the temporal order) is developed. The recursive procedure backtracks when either the current strategy is complete (then δ opt and U +minopt ante may be updated) or proves to be worse than the current δ opt in any case.

In order to get an upper bound of the U + min ante utility of the best completion of δ, we call a function UpperBound(D 0 , δ) that computes the optimistic U + i utility w.r.t. each agent i separately and builds an optimal strategy δ i relative to each i. It then returns the p strategies obtained using classical optimization of U + i by Dynamic Programming, introduces the weights (computes min i∈A max((1 -w i ), U + i ) and then selects, among them, the one with the highest U + min ante .

Whenever the value U + min returned by UpperBound(D 0 , δ) is lower or equal to the U + min A constant act maps the same vector to any state: what an agent gets does not depend on the state of the world. The set of constant acts is ordered by . By identification of X p with the set of constant acts, any x ∈ X p , x also denotes the corresponding constant act. For any x, y ∈ X p we write x y whenever the constant act providing x for any s is at least as good (according to ) as the one providing y for any s: is the common preference order on X p .

A representative act [x] is a constant act that maps the same consequence, x, to any state and any agent: everybody receives x, and this for any state. X is ordered by (which is a weak order): we say that x is as least as good as y (and we denote x y) whenever the representative act [x] is preferred to [y].

In this work, (X, ) is interpreted as a scale of satisfaction common to all the agents. To this extend, we shall propose the following axiom:

For some decision rules, it may happen that an agent i is not important enough: his preference is drowned when x and y are not high in the scale, and thus not revealed by i . In this case, the following weak version of CS may be preferred:

Let us now go back to Savage's axioms. The third axiom of Savage states that the preference on X is not sensitive to the conditioning on non null events; we write it here in its classical version and in its weak variant: Axiom (Sav3). For any x, y ∈ X, for any non null event E ⊆ S,

Axiom (wSav3). For any x, y ∈ X, for any event E ⊆ S,

Axioms Sav3/wSav3 are very close to axioms CS/wCS; it can be possible to see them as two particular cases of a more general axiom ensuring the coherence on the conditioning of the preference over X on any P ⊆ A × S (and not only the subsets of the form {i} × S and the events A × E).

Axiom (Cond). For any x, y ∈ X, for any non null

Axiom (wCond). For any x, y ∈ X,for any P ⊆ A × S, [x] [y] =⇒ [x] P [y]. Hence U -min (f P h) U -min (gP h) implies U -min (f P h ) U -min (gP h ) for any h : wSav2 is satisfied.

• Pareto Unanimity follows from the fact that the max and min operators are monotonic (U -min do not decrease when one of the f (s, i) increases).

• wSav3 follows from Sav1, wSav2 and Pareto Unanimity.

• satisfies wSav4: When all the agents receive the same consequence, U -min writes as a classical, mono agent pessimistic utility. Gambles of the form [x]E [y] do assign the same consequence to all the agents (namely, whatever i,

-we recover the mono agent case, with U -min ([x]E[y]) = median(x, N (E), y). The satisfaction of wSav4 follows from its satisfaction in the mono-agent case.

• Sav5 is satisfied by construction. We thus get max(1 -w i , median(x, N (D), y)) > max(1 -w i , median(x, N (E), y)), which implies median(x, N (D), y)) > median(x, N (E), y)). This contradicts median(x, N (E), y) ≥ median(x, N (D), y). Hence there cannot be a i such that D i E, i.e. E i D. This shows that E D implies E i D: wCoK is satisfied.

• wCS is a consequence of Pareto Unanimity and Sav1.