<figure><img src="image_1.png" /></figure>

HAL
open science

# Decision-making with Sugeno integrals

Miguel Couceiro, Didier Dubois, Henri Prade, Tamas Waldhauser

► To cite this version:

Miguel Couceiro, Didier Dubois, Henri Prade, Tamas Waldhauser. Decision-making with Sugeno integrals: Bridging the gap between multicriteria evaluation and decision under uncertainty. Order, 2016, 33 (3), pp.517-535. 10.1007/s11083-015-9382-8. hal-01184340

HAL Id: hal-01184340

https://hal.science/hal-01184340

Submitted on 14 Aug 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
DECISION-MAKING WITH SUGENO INTEGRALS:
BRIDGING THE GAP BETWEEN MULTICRITERIA EVALUATION
AND DECISION UNDER UNCERTAINTY

MIGUEL COUCEIRO, DIDIER DUBOIS, HENRI PRADE, AND TAMÁS WALDHAUSER

ABSTRACT. This paper clarifies the connection between multiple criteria decision-making and decision under uncertainty in a qualitative setting relying on a finite value scale. While their mathematical formulations are very similar, the underlying assumptions differ and the latter problem turns out to be a special case of the former. Sugeno integrals are very general aggregation operations that can represent preference relations between uncertain acts or between multifactorial alternatives where attributes share the same totally ordered domain. This paper proposes a generalized form of the Sugeno integral that can cope with attributes which have distinct domains via the use of qualitative utility functions. It is shown that in the case of decision under uncertainty, this model corresponds to state-dependent preferences on act consequences. Axiomatizations of the corresponding preference functionals are proposed in the cases where uncertainty is represented by possibility measures, by necessity measures, and by general order-preserving set-functions, respectively. This is achieved by weakening previously proposed axiom systems for Sugeno integrals.

# 1. MOTIVATION

Two important chapters of decision theory are decision under uncertainty and multi-criteria evaluation [5]. Although these two areas have been developed separately, they entertain close relationships. On the one hand, they are not mutually exclusive; in fact, there are works dealing with multicriteria evaluation under uncertainty [31]. On the other hand, the structure of the two problems is very similar, see, e.g., [20, 22]. Decision-making under uncertainty (DMU), after Savage [37], relies on viewing a decision (called an *act*) as a mapping from a set of states of the world to a set of consequences, so that the consequence of an act depends on the circumstances in which it is performed. Uncertainty about the state of the world is represented by a set-function on the set of states, typically a probability measure.

In multicriteria decision-making (MCDM) an alternative is evaluated in terms of its (more or less attractive) features according to prescribed attributes and the relative importance of such features. Attributes play in MCDM the same role as states of the world in DMU, and this very fact highlights the similarity of alternatives and acts: both can be represented by tuples of ratings (one per state or objects). Moreover, importance coefficients in MCDM play the same role as the uncertainty function in DMU. A major difference between MCDM and DMU is that in the latter there is usually a unique consequence set, while in MCDM each attribute possesses its own domain. A similar setting is that of voting, where voters play the same role as attributes in MCDM.

There are several possible frameworks for representing decision problems that range from numerical to qualitative and ordinal. While voting problems are often cast in a purely ordinal setting (leading to the famous impossibility theorem of Arrow), decision under uncertainty adopts a numerical setting as it deals mainly with quantities (since its tradition comes from economics). The situation of MCDM in this respect is less

<footnote>The first named author wishes to warmly thank the Director of LAMSADE, Alexis Tsoukiàs, for his thoughtful guidance and constant support that contributed in a special way to the current manuscript. The fourth named author acknowledges that the present project is supported by the Hungarian National Foundation for Scientific Research under grant no. K104251 and by the János Bolyai Research Scholarship.</footnote>
clear: the literature is basically numerical, but many methods are inspired by voting theory; see [6].

In the last 15 years, the paradigm of qualitative decision theory has emerged in Artificial Intelligence in connection with problems such as webpage configuration, recommender systems, or ergonomics (see [19]). In such topics, quantifying preference in very precise terms is difficult but not crucial, as these problems require on-line inputs from humans and must be provided in a rather short period of time. As a consequence, the formal models are either ordinal (like in CP-nets, see [4]) or qualitative, that is, based on finite value scales. This paper is a contribution to evaluation processes in the finite value scale setting for DMU and MCDM. In such a qualitative setting, the most natural aggregation functions are based on the Sugeno integral. Theoretical foundations for them (in the scope of DMU) have been proposed in the setting of possibility theory [26], and assuming a more general representation of uncertainty [25]. The same aggregation functions have been used in [32] in the scope of MCDM, and applied in [34] to ergonomics. In these papers it is assumed that the domains of attributes are the same totally ordered set.

In the current paper, we remove this restriction, and consider an aggregation model based on compositions of Sugeno integrals with qualitative utility functions on distinct attribute domains, which we call Sugeno utility functionals. We propose an axiomatic approach to these extended preference functionals that enables the representation of preference relations over Cartesian products of, possibly different, finite chains (scales). We consider the cases when importance weights bear on individual attributes (the importance function is then a possibility or a necessity measure), and the general case when importance weights are assigned to groups of attributes, not necessarily singletons. We study this extended Sugeno integral framework in the DMU situation showing that it leads to the case of state-dependent preferences on consequences of acts. The new axiomatic system is compared to previous proposals in qualitative DMU: it comes down to deleting or weakening two axioms on the global preference relation.

The paper is organized as follows. Section 2 introduces basic notions and terminology, and recalls previous results needed throughout the paper. Our main results are given in Section 3, namely, representation theorems for multicriteria preference relations by Sugeno utility functionals. In Section 4, we compare this axiomatic approach to that previously presented in DMU. We show that this new model can account for preference relations that cannot be represented in DMU, i.e., by Sugeno integrals applied to a single utility function. This situation remains in the case of possibility theory.

This contribution is an extended and corrected version of [7] that was presented at ECAI'2012.

## 2. BASIC BACKGROUND

In this section, we recall basic background and present some preliminary results needed throughout the paper. For introduction on lattice theory see [35].

### 2.1. Preliminaries.
Throughout this paper, let $Y$ be a finite chain endowed with lattice operations $\wedge$ and $\vee$, and with least and greatest elements $0_Y$ and $1_Y$, respectively; the subscripts may be omitted when the underlying lattice is clear from the context; $[n]$ is short for $\{1, \dots, n\} \subset \mathbb{N}$.

Given finite chains $X_i$, $i \in [n]$, their Cartesian product $\mathbf{X} = \prod_{i \in [n]} X_i$ constitutes a bounded distributive lattice by defining

$$ \mathbf{a} \wedge \mathbf{b} = (a_1 \wedge b_1, \dots, a_n \wedge b_n), \text{ and } \mathbf{a} \vee \mathbf{b} = (a_1 \vee b_1, \dots, a_n \vee b_n). $$

In particular, $\mathbf{a} \leq \mathbf{b}$ if and only if $a_i \leq b_i$ for every $i \in [n]$. For $k \in [n]$ and $c \in X_k$, we use $\mathbf{x}_k^c$ to denote the tuple whose $i$-th component is $c$, if $i = k$, and $x_i$, otherwise.

Let $f: \mathbf{X} \to Y$ be a function. The range of $f$ is given by $\mathrm{ran}(f) = \{f(\mathbf{x}) : \mathbf{x} \in \mathbf{X}\}$. Also, $f$ is said to be *order-preserving* if, for every $\mathbf{a}, \mathbf{b} \in \prod_{i \in [n]} X_i$ such that $\mathbf{a} \leq \mathbf{b}$, we have $f(\mathbf{a}) \leq f(\mathbf{b})$. A well-known example of an order-preserving function is the *median*
function med: $Y^3 \to Y$ given by

$$\mathrm{med}(x_1, x_2, x_3) = (x_1 \wedge x_2) \vee (x_1 \wedge x_3) \vee (x_2 \wedge x_3).$$

**2.2. Basic background on polynomial functions and Sugeno integrals.** In this subsection we recall some well-known results concerning polynomial functions that will be needed hereinafter. For further background, we refer the reader to, e.g., [18, 28].

Recall that a (lattice) polynomial function on $Y$ is any map $p: Y^n \to Y$ which can be obtained as a composition of the lattice operations $\wedge$ and $\vee$, the projections $\mathbf{x} \mapsto x_i$ and the constant functions $\mathbf{x} \mapsto c$, $c \in Y$.

As shown by Goodstein [27], polynomial functions over bounded distributive lattices (in particular, over bounded chains) have very neat normal form representations. For $I \subseteq [n]$, let $\mathbf{1}_I$ be the characteristic vector of $I$, i.e., the $n$-tuple in $Y^n$ whose $i$-th component is 1 if $i \in I$, and 0 otherwise.

**Theorem 2.1.** A function $p: Y^n \to Y$ is a polynomial function if and only if

$$ (1) \qquad p(x_1, \dots, x_n) = \bigvee_{I \subseteq [n]} (p(\mathbf{1}_I) \wedge \bigwedge_{i \in I} x_i). $$

Equivalently, $p: Y^n \to Y$ is a polynomial function if and only if

$$ p(x_1, \dots, x_n) = \bigwedge_{I \subseteq [n]} (p(\mathbf{1}_{[n] \setminus I}) \vee \bigvee_{i \in I} x_i). $$

**Remark 2.2.** Observe that, by Theorem 2.1, every polynomial function $p: Y^n \to Y$ is uniquely determined by its restriction to $\{0, 1\}^n$. Also, since every lattice polynomial function is order-preserving, the coefficients in (1) are monotone increasing as well, i.e., $p(\mathbf{1}_I) \le p(\mathbf{1}_J)$ whenever $I \subseteq J$. Moreover, a function $f: \{0, 1\}^n \to Y$ can be extended to a polynomial function over $Y$ if and only if it is order-preserving.

Polynomial functions are known to generalize certain prominent nonadditive integrals, namely, the so-called Sugeno integrals. A capacity on $[n]$ is a mapping $\mu: \mathcal{P}([n]) \to Y$ which is order-preserving (i.e., if $A \subseteq B \subseteq [n]$, then $\mu(A) \le \mu(B)$) and satisfies $\mu(\emptyset) = 0$ and $\mu([n]) = 1$; such functions qualify to represent uncertainty.

The Sugeno integral associated with the capacity $\mu$ is the function $q_\mu: Y^n \to Y$ defined by

$$ (2) \qquad q_\mu(x_1, \dots, x_n) = \bigvee_{I \subseteq [n]} (\mu(I) \wedge \bigwedge_{i \in I} x_i). $$

For further background see, e.g., [30, 38, 39].

**Remark 2.3.** As observed in [32, 33], Sugeno integrals coincide exactly with those polynomial functions $q: Y^n \to Y$ which are idempotent, that is, which satisfy $q(c, \dots, c) = c$, for every $c \in Y$. In fact, by (1) it suffices to verify this identity for $c \in \{0, 1\}$, that is, $q(\mathbf{1}_{[n]}) = 1$ and $q(\mathbf{1}_{\emptyset}) = 0$.

**Remark 2.4.** Note also that the range of a Sugeno integral $q: Y^n \to Y$ is $\mathrm{ran}(q) = Y$. Moreover, by defining $\mu(I) = q(\mathbf{1}_I)$, we get $q = q_\mu$.

In the sequel, we shall be particularly interested in the following types of capacities. A capacity $\mu$ is called a *possibility measure* (resp. *necessity measure*) if for every $A, B \subseteq [n]$, $\mu(A \cup B) = \mu(A) \vee \mu(B)$ (resp. $\mu(A \cap B) = \mu(A) \wedge \mu(B)$).

**Remark 2.5.** In the finite setting, a possibility measure is completely characterized by the value of $\mu$ on singletons, namely, $\mu(\{i\}), i \in [n]$ (called a possibility distribution), since clearly, $\mu(A) = \bigvee_{i \in A} \mu(\{i\})$. Likewise, a necessity measure is completely characterized by the value of $\mu$ on sets of the form $N_i = [n] \setminus \{i\}$ since clearly, $\mu(A) = \bigwedge_{i \notin A} \mu(N_i)$

Note that if $\mu$ is a possibility measure [40] (resp. necessity measure [24]), then $q_\mu$ is a weighted disjunction $\bigvee_{i \in I} \mu(i) \wedge x_i$ (resp. weighted conjunction $\mu(I) \wedge \bigwedge_{i \in I} x_i$) for some $I \subseteq [n]$ [23] (where $\mu(i)$, a shorthand notation for $\mu(\{i\})$, represents importance
of criterion $i$). The weighted disjunction operation is then permissive (it is enough that one important criterion be satisfied for the result to be high) and the weighted conjunction is demanding (all important criteria must be satisfied).

Polynomial functions and Sugeno integrals have been characterized by several authors, and in the more general setting of distributive lattices see, e.g., [9, 10, 30].

The following characterization in terms of median decomposability will be instrumental in this paper. A function $p: Y^n \to Y$ is said to be median decomposable if for every $\mathbf{x} \in Y^n$,

$$p(\mathbf{x}) = \text{med}(p(\mathbf{x}_k^0), x_k, p(\mathbf{x}_k^1)) \quad (k = 1, \dots, n),$$

where $\mathbf{x}_k^c$ denotes the tuple whose $i$-th component is $c$, if $i = k$, and $x_i$, otherwise.

**Theorem 2.6** ([8, 33]). Let $p: Y^n \to Y$ be a function on an arbitrary bounded chain $Y$. Then $p$ is a polynomial function if and only if $p$ is median decomposable.

**2.3. Sugeno utility functionals.** Let $X_1, \dots, X_n$ and $Y$ be finite chains. We denote (with no danger of ambiguity) the top and bottom elements of $X_1, \dots, X_n$ and $Y$ by 1 and 0, respectively.

We say that a mapping $\varphi_i: X_i \to Y, i \in [n]$, is a local utility function if it is order-preserving. It is a qualitative utility function as mapping on a finite chain. A function $f: X \to Y$ is a Sugeno utility functional if there is a Sugeno integral $q: Y^n \to Y$ and local utility functions $\varphi_i: X_i \to Y, i \in [n]$, such that

$$(3) \qquad f(\mathbf{x}) = q(\varphi_1(x_1), \dots, \varphi_n(x_n)).$$

Note that Sugeno utility functionals are order-preserving. Moreover, it was shown in [15] that the set of functions obtained by composing lattice polynomials with local utility functions is the same as the set of Sugeno utility functionals.

**Remark 2.7.** In [15] and [16] a more general setting was considered, where the inner functions $\varphi_i: X_i \to Y, i \in [n]$, were only required to satisfy the so-called “boundary conditions”: for every $x \in X_i$,

$$(4) \qquad \varphi_i(0) \le \varphi_i(x) \le \varphi_i(1) \quad \text{or} \quad \varphi_i(1) \le \varphi_i(x) \le \varphi_i(0).$$

The resulting compositions (3) where $q$ is a polynomial function (resp. Sugeno integral) were referred to as “pseudo-polynomial functions” (resp. “pseudo-Sugeno integrals”). As it turned out, these two notions are in fact equivalent.

**Remark 2.8.** Observe that pseudo-polynomial functions are not necessarily order-preserving, and thus they are not necessarily Sugeno utility functionals. However, Sugeno utility functionals coincide exactly with those pseudo-polynomial functions (or, equivalently, pseudo-Sugeno integrals) which are order-preserving, see [15].

Sugeno utility functionals can be axiomatized in complete analogy with polynomial functions by extending the notion of median decomposability. We say that $f: X \to Y$ is pseudo-median decomposable if for each $k \in [n]$ there is a local utility function $\varphi_k: X_k \to Y$ such that

$$(5) \qquad f(\mathbf{x}) = \text{med}(f(\mathbf{x}_k^0), \varphi_k(x_k), f(\mathbf{x}_k^1))$$

for every $\mathbf{x} \in X$.

**Theorem 2.9** ([15]). A function $f: X \to Y$ a Sugeno utility functional if and only if $f$ is pseudo-median decomposable.

**Remark 2.10.** In [15] and [16] a more general notion of pseudo-median decomposability was considered where the inner functions $\varphi_i: X_i \to Y, i \in [n]$, were only required to satisfy the boundary conditions.

Note that once the local utility functions $\varphi_i: X_i \to Y (i \in [n])$ are given, the pseudo-median decomposability formula (5) provides a disjunctive normal form of a polynomial function $p_0$ which can be used to factorize $f$. To this extent, let $\hat{1}_I$ denote the characteristic vector of $I \subseteq [n]$ in $X$, i.e., $\hat{1}_I \in X$ is the $n$-tuple whose $i$-th component is $1_{X_i}$ if $i \in I$, and $0_{X_i}$ otherwise.
**Theorem 2.11** ([16]). If $f: \mathbf{X} \to Y$ is pseudo-median decomposable w.r.t. local utility functions $\varphi_k: X_k \to Y$ ($k \in [n]$), then $f = p_0(\varphi_1, \dots, \varphi_n)$, where the polynomial function $p_0$ is given by

$$ (6) \qquad p_0(y_1, \dots, y_n) = \bigvee_{I \subseteq [n]} (f(\hat{1}_I) \wedge \bigwedge_{i \in I} y_i). $$

This result naturally asks for a procedure to obtain local utility functions $\varphi_i: X_i \to Y$ ($i \in [n]$) which can be used to factorize a given Sugeno utility functional $f: \mathbf{X} \to Y$ into a composition (3). In the more general setting of pseudo-polynomial functions, such procedures were presented in [15] when $Y$ is an arbitrary chain, and in [16] when $Y$ is a finite distributive lattice; we recall the latter in Appendix I.

The following result provides a noteworthy axiomatization of Sugeno utility functionals which follows as a corollary of Theorem 19 in [16]. For the sake of self-containment, we present its proof in Appendix II.

**Theorem 2.12.** A function $f: \mathbf{X} \to Y$ is a Sugeno utility functional if and only if it is order-preserving and satisfies

$$ f(\mathbf{x}_k^0) < f(\mathbf{x}_k^a) \quad \text{and} \quad f(\mathbf{y}_k^0) < f(\mathbf{y}_k^1) \quad \implies \quad f(\mathbf{x}_k^a) \le f(\mathbf{y}_k^a) \\ \text{for all } \mathbf{x}, \mathbf{y} \in \mathbf{X} \text{ and } k \in [n], a \in X_k. $$

Let us interpret this result in terms of multicriteria evaluation. Consider alternatives $\mathbf{x}$ and $\mathbf{y}$ such that $x_k = y_k = a$. Then $f(\mathbf{x}_k^0) < f(\mathbf{x})$ means that down-grading attribute $k$ makes the corresponding alternative $\mathbf{x}_k^0$ strictly worse than $\mathbf{x}$. Similarly, $f(\mathbf{y}) < f(\mathbf{y}_k^1)$ means that upgrading attribute $k$ makes the corresponding alternative $\mathbf{y}_k^1$ strictly better than $\mathbf{y}$. Then pseudo-median decomposibility expresses the fact that the value of $\mathbf{x}$ is either $f(\mathbf{x}_k^0)$, or $f(\mathbf{x}_k^1)$ or $\varphi_k(x_k)$. In such a situation, given another alternative $\mathbf{y}$ such that $y_k = x_k = a$:

$$ f(\mathbf{x}_k^0) < f(\mathbf{x}) = \operatorname{med} (f(\mathbf{x}_k^0), \varphi_k(a), f(\mathbf{x}_k^1)) = \varphi_k(a) \wedge f(\mathbf{x}_k^1) \le \varphi_k(a), $$

$$ f(\mathbf{y}_k^1) > f(\mathbf{y}) = \operatorname{med} (f(\mathbf{y}_k^0), \varphi_k(a), f(\mathbf{y}_k^1)) = \varphi_k(a) \vee f(\mathbf{y}_k^0) \ge \varphi_k(a), $$

and so $f(\mathbf{x}) \le \varphi_k(a) \le f(\mathbf{y})$. Hence, if maximally downgrading (resp. upgrading) attribute $k$ makes the alternative worse (resp. better) it means that its overall rating was not more (resp. not less) than the rating on attribute $k$. We shall further discuss this and other facts in Section 5.

It is also interesting to comment on Sugeno utility functionals as opposed to Sugeno integrals applied to a single local utility function. First, the role of local utility functions is clearly to embed all the local scales $X_i$ into a single scale $Y$ in order to make the scales $X_i$ commensurate. In other words, a Sugeno integral (2) cannot be defined if there is no common scale $X$ such that $X_i \subseteq X$, for every $i \in [n]$. In particular, the situation in decision under uncertainty is precisely that where $X_i = X$, for every $i \in [n]$, that is, the utility of a consequence resulting from implementing an act does not depend on the state of the world in which the act is implemented. Then it is clear that $\varphi_i = \varphi$, for every $i \in [n]$, namely, a unique utility function is at work. In this sense, the Sugeno utility functional becomes a simple Sugeno integral of the form

$$ (7) \qquad q_{\mu}(y_1, \dots, y_n) = \bigvee_{I \subseteq [n]} (\mu(I) \wedge \bigwedge_{i \in I} y_i). $$

where $Y = \varphi(X)$. This is the case for DMU, where $[n]$ is the set of states of nature, and $X$ is the set of consequences (not necessarily ordered). It is the utility function $\varphi$ that equips $X$ with a total order: $x_i \le x_j \iff \varphi(x_i) \le \varphi(x_j)$. The general case studied here corresponds to that of DMU but where the local utility functions $\varphi_i: X \to Y$ are state-dependent; this situation was already considered in the literature of expected utility theory [36], here adapted to the qualitative setting. Namely, an act is of the form $\mathbf{x} \in X^n$ where the consequences $x_i$ of the act performed in state $i$ belong to the same set $X$, and the evaluation of $\mathbf{x}$ is of the form (3), i.e. they are not evaluated in the same way in each state.
### 3. PREFERENCE RELATIONS REPRESENTED BY SUGENO UTILITY FUNCTIONALS

In this section we are interested in relations which can be represented by Sugeno utility functionals. In Subsection 3.1 we recall basic notions and present preliminary observations pertaining to preference relations. We discuss several axioms of MCDM in Subsection 3.2 and present several equivalences between them. In Subsections 3.3 and 3.4 we present axiomatizations of those preference relations induced by possibility and necessity measures, and of more general preference relations represented by Sugeno utility functions.

**3.1. Preference relations on Cartesian products.** One of the main areas in decision making is the representation of preference relations. A weak order on a set $X = \prod_{i \in [n]} X_i$ is a relation $\preceq \subseteq X^2$ that is reflexive, transitive, and complete ($\forall x, y \in X : x \preceq y$ or $y \preceq x$). Like quasi-orders (i.e., reflexive and transitive relations), weak orders do not necessarily satisfy the antisymmetry condition:

$$ (AS) \qquad \forall x, y \in X : x \preceq y, y \preceq x \implies x = y. $$

This fact gives rise to an “indifference” relation which we denote by $\sim$, and which is defined by $y \sim x$ if $x \preceq y$ and $y \preceq x$. Clearly, $\sim$ is an equivalence relation. Moreover, the quotient relation $\preceq / \sim$ satisfies (AS); in other words, $\preceq / \sim$ is a complete linear order (chain).

By a preference relation on $X$ we mean a weak order $\preceq$ which satisfies the Pareto condition:

$$ (P) \qquad \forall x, y \in X : x \le y \implies x \preceq y. $$

In this section we are interested in modeling preference relations, and in this field two problems arise naturally. The first deals with the representation of such preference relations, while the second deals with the axiomatization of the chosen representation. Concerning the former, the use of aggregation functions has attracted much attention in recent years, for it provides an elegant and powerful formalism to model preference [5, 29] (for general background on aggregation functions, see [30, 2]).

In this approach, a weak order $\preceq$ on a set $X = \prod_{i \in [n]} X_i$ is represented by a so-called global utility function $U$ (i.e., an order-preserving mapping which assigns to each event in $X$ an overall score in a possibly different scale $Y$), under the rule: $x \preceq y$ if and only if $U(x) \le U(y)$. Such a relation is clearly a preference relation.

Conversely, if $\preceq$ is a preference relation, then the canonical surjection $r: X \to X/\sim$, also referred to as the *rank function of* $\preceq$, is an order-preserving map from $X$ to $X/\sim$ (linearly ordered by $\sqsubseteq:=\preceq/\sim$), and we have $x \preceq y \iff r(x) \sqsubseteq r(y)$. Thus, $\preceq$ is represented by an order-preserving function if and only if it is a preference relation, and in this case $\preceq$ is represented by $r$.

**3.2. Axioms pertaining to preference modelling.** In this subsection we recall some properties of relations used in the axiomatic approach discussed in [22, 25]; here we will adopt the same terminology even if its motivation only makes sense in the realm of decision making under uncertainty. We also introduce some variants, and present connections between them.

First, for $x, y \in X$ and $A \subseteq [n]$, let $xAy$ denote the tuple in $X$ whose $i$-th component is $x_i$ if $i \in A$ and $y_i$ otherwise. Moreover, let **0** and **1** denote the bottom and the top of $X$, respectively.

We consider the following axioms. The *optimism* axiom [26] is

$$ (OPT) \qquad \forall x, y \in X, \forall A \subseteq [n] : xAy \prec x \implies x \preceq yAx, $$

which subsumes<fnref n="1" /> two instances of interest, namely,

$$ (OPT') \qquad \forall x \in X, \forall A \subseteq [n] : xA0 \prec x \implies x \preceq 0Ax, $$

$$ (OPT_1) \qquad \forall x, y \in X, k \in [n], a \in X_k : x_k^0 \prec x_k^a \implies x_k^a \preceq y_k^a. $$

<footnote n="1">¹For (OPT) $\implies$ (OPT₁), just take $x = x_k^a$, $y = y_k^0$ and $A = [n] \setminus \{k\}$.</footnote>
Note that under (P) the conclusion of (OPT') is equivalent to $x \sim 0Ax$. Similarly, the conclusion of (OPT₁) could be replaced by $x_k^a \sim 0_k^a$. The name optimism is justified considering the case where $x = 1$ and $y = 0$. Then (OPT) reads $A \prec [n]$ implies $[n] \preceq [n] \setminus A$ (full trust in A or $[n] \setminus A$, an optimistic approach to uncertainty).

Dual to optimism we have the *pessimism* axiom

$$ (\text{PESS}) \qquad \forall x, y \in \mathbf{X}, \forall A \subseteq [n] : xAy \succ x \implies x \succsim yAx, $$

which subsumes the two dual instances

$$ (\text{PESS}') \qquad \forall x \in \mathbf{X}, \forall A \subseteq [n] : xA1 \succ x \implies x \succsim 1Ax, $$

$$ (\text{PESS}_1) \qquad \forall x, y \in \mathbf{X}, k \in [n], a \in X_k : x_k^1 \succ x_k^a \implies x_k^a \succsim y_k^a. $$

Again, under (P), the conclusions of (PESS') and (PESS₁) are equivalent to $x \sim 1Ax$ and $x_k^a \sim 1_k^a$, respectively. When $x = 0$ and $y = 1$, (PESS) reads $[n] \setminus A \succ \emptyset$ implies $\emptyset \succsim A$ (full distrust in A or $[n] \setminus A$, a pessimistic approach to uncertainty).

We will also consider the *disjunctive* and *conjunctive* axioms

$$ (\lor) \qquad \forall y, z \in \mathbf{X} : y \lor z \sim y \text{ or } y \lor z \sim z, $$

$$ (\land) \qquad \forall y, z \in \mathbf{X} : y \land z \sim y \text{ or } y \land z \sim z. $$

Moreover, we have the so-called *disjunctive dominance* and *strict disjunctive dominance*

$$ (\mathrm{DD}_{\sim}) \qquad \forall x, y, z \in \mathbf{X} : x \succsim y, x \succsim z \implies x \succsim y \lor z, $$

$$ (\mathrm{DD}_{\succ}) \qquad \forall x, y, z \in \mathbf{X} : x \succ y, x \succ z \implies x \succ y \lor z, $$

as well as their dual counterparts, *conjunctive dominance* and *strict conjunctive dominance*

$$ (\mathrm{CD}_{\sim}) \qquad \forall x, y, z \in \mathbf{X} : y \succsim x, z \succsim x \implies y \land z \succsim x, $$

$$ (\mathrm{CD}_{\succ}) \qquad \forall x, y, z \in \mathbf{X} : y \succ x, z \succ x \implies y \land z \succ x. $$

**Theorem 3.1.** If $\simeq$ is a preference relation, then axioms (OPT), (OPT'), (OPT₁), $(\lor)$, $(\mathrm{DD}_{\sim})$ and $(\mathrm{DD}_{\succ})$ are pairwise equivalent.

*Proof.* We prove the theorem by establishing the following six implications:

$$ \begin{align*} (\mathrm{OPT}') &\implies (\mathrm{OPT}) \implies (\mathrm{OPT}_1) \implies (\lor) \\ &\implies (\mathrm{DD}_{\sim}) \implies (\mathrm{DD}_{\succ}) \implies (\mathrm{OPT}') \end{align*} $$

Note that the implication $(\lor) \implies (\mathrm{DD}_{\sim})$ is trivial, and recall that $(\mathrm{OPT}_1)$ is just a special case of (OPT). Thus, we only need to prove the four implications below.

(OPT') $\implies$ (OPT): Suppose that $xAy \prec x$. By the Pareto property we have $xA0 \preceq xAy$, and then $xA0 \prec x$ follows by the transitivity of $\preceq$. Applying (OPT') and (P), we obtain $x \preceq 0Ax \preceq yAx$, and then $x \preceq yAx$ follows again from transitivity.

(OPT₁) $\implies$ $(\lor)$: Let us suppose that $y \lor z \sim z$; we will prove using (OPT₁) that $y \lor z \sim y$. From (P) we see that $z \preceq y \lor z$, hence we have $z \prec y \lor z$ by our assumption. If $A = \{i \in [n] : y_i > z_i\}$, then obviously $yAz = y \lor z$. Let $\ell$ denote the cardinality of A, let $A = \{i_1, \dots, i_\ell\}$, and define the sets $A_j := \{i_1, \dots, i_j\}$ for $j = 1, \dots, \ell$. Using the Pareto property, we obtain the following chain of inequalities:

$$ z \preceq yA_1z \preceq \dots \preceq yA_\ell z = y \lor z. $$

Since $z \prec y \lor z$, at least one of the above inequalities is strict. If the s-th inequality is the last strict one, then

$$ (8) \qquad z \preceq yA_1z \preceq \dots \preceq yA_{s-1}z \prec yA_s z \sim \dots \sim yA_\ell z = y \lor z. $$

To simplify notation, let us put $x = yA_{s-1}z$, $k = i_s$ and $a = y_k$. Then we have $x_k^0 \preceq x = yA_{s-1}z \prec yA_s z = x_k^a$, hence $x_k^a \preceq y_k^a$ follows from (OPT₁). On the other hand, we see from (8) that $yA_s z \sim y \lor z$, therefore

$$ y \lor z \sim yA_s z = x_k^a \preceq y_k^a = y \preceq y \lor z, $$
where the last inequality is justified by (P). Since $\lesssim$ is a weak order, we can conclude that $\mathbf{y} \vee \mathbf{z} \sim \mathbf{y}$.

(DD$_{\sim}$) $\implies$ (DD$_{\succ}$): Assume that $\mathbf{x} \succ \mathbf{y}, \mathbf{x} \succ \mathbf{z}$. Since $\lesssim$ is complete, we can suppose without loss of generality that $\mathbf{y} \gtrsim \mathbf{z}$. By reflexivity, we also have $\mathbf{y} \gtrsim \mathbf{y}$, hence it follows from (DD$_{\sim}$) that $\mathbf{y} \gtrsim \mathbf{y} \vee \mathbf{z}$. Since $\mathbf{x} \succ \mathbf{y}$, we obtain $\mathbf{x} \succ \mathbf{y} \vee \mathbf{z}$ by transitivity.

(DD$_{\succ}$) $\implies$ (OPT$'$): Putting $\mathbf{y} = \mathbf{x}A0$ and $\mathbf{z} = 0A\mathbf{x}$, we clearly have $\mathbf{y} \vee \mathbf{z} = \mathbf{x}$. If $\mathbf{x} \succ \mathbf{y}$ and $\mathbf{x} \succ \mathbf{z}$, then (DD$_{\succ}$) implies $\mathbf{x} \succ \mathbf{y} \vee \mathbf{z}$, which is a contradiction. Therefore, we must have $\mathbf{x} \not\succ \mathbf{y}$ or $\mathbf{x} \not\succ \mathbf{z}$. This shows that $\mathbf{x} \succ \mathbf{y} \implies \mathbf{x} \not\succ \mathbf{z} \implies \mathbf{x} \gtrsim \mathbf{z}$, where the second implication holds because $\lesssim$ is complete. Thus we have $\mathbf{y} \prec \mathbf{x} \implies \mathbf{x} \gtrsim \mathbf{z}$, and this is exactly what (OPT$'$) asserts. $\square$

Dually, we have the following result which establishes the pairwise equivalence between the remaining axioms.

**Theorem 3.2.** If $\lesssim$ is a preference relation, then axioms (PESS), (PESS'), (PESS$_1$), $(\wedge)$, $(CD_{\sim})$ and $(CD_{\succ})$ are pairwise equivalent.

**3.3. Preference relations induced by possibility and necessity measures.** In this subsection we present some preliminary results towards the axiomatization of preference relations represented by Sugeno utility functionals (see Theorem 3.6). More precisely, we first obtain an axiomatization of relations represented by Sugeno utility functionals associated with possibility measures (weighted disjunction of utility functions).

**Theorem 3.3.** A preference relation $\lesssim$ satisfies one (or, equivalently, all) of the axioms in Theorem 3.1 if and only if there are local utility functions $\varphi_i$, $i \in [n]$, and a possibility measure $\mu$, such that $\lesssim$ is represented by the Sugeno utility functional $f = q_\mu(\varphi_1, \dots, \varphi_n)$.

*Proof.* First let us assume that $\lesssim$ is represented by a Sugeno utility functional $f = q_\mu(\varphi_1, \dots, \varphi_n)$, where $\mu$ is a possibility measure. As observed in Subsection 2.2, $f$ can be expressed as a weighted disjunction:

$$f(\mathbf{x}) = \bigvee_{i \in [n]} (\mu(i) \wedge \varphi_i(x_i)).$$

Using the fact that each $\varphi_i$ is order-preserving and $Y$ is a chain, we can verify that $f$ commutes with the join operation of the lattice $\mathbf{X}$:

$$ \begin{align*} f(\mathbf{y} \vee \mathbf{z}) &= \bigvee_{i \in [n]} (\mu(i) \wedge \varphi_i(y_i \vee z_i)) \\ &= \bigvee_{i \in [n]} (\mu(i) \wedge (\varphi_i(y_i) \vee \varphi_i(z_i))) \\ &= \bigvee_{i \in [n]} (\mu(i) \wedge \varphi_i(y_i)) \vee \bigvee_{i \in [n]} (\mu(i) \wedge \varphi_i(z_i)) = f(\mathbf{y}) \vee f(\mathbf{z}). \end{align*} $$

Since the ordering on $Y$ is complete, we have $f(\mathbf{y} \vee \mathbf{z}) \in \{f(\mathbf{y}), f(\mathbf{z})\}$, and this implies that $\mathbf{y} \vee \mathbf{z} \sim \mathbf{y}$ or $\mathbf{y} \vee \mathbf{z} \sim \mathbf{z}$ for all $\mathbf{y}, \mathbf{z} \in \mathbf{X}$, i.e., $\lesssim$ satisfies $(\vee)$.

Now let us assume that $\lesssim$ satisfies $(\vee)$, and let $Y = \mathbf{X}/\sim$. Using the rank function $r$ of $\lesssim$, we define a set function $\mu: \mathcal{P}([n]) \to Y$ by $\mu(I) = r(1I0)$ and a unary map $\varphi_i: X_i \to Y$ by $\varphi_i(a) = r(\mathbf{0}_i^a)$ for each $i \in [n]$. The Pareto condition ensures that $\mu$ and each $\varphi_i$, $i \in [n]$, are all order-preserving; moreover, $\mu$ is a capacity, since 0 and 1 have the least and greatest rank, respectively.

Condition $(\vee)$ can be reformulated in terms of the rank function as

$$(9) \qquad \forall \mathbf{y}, \mathbf{z} \in \mathbf{X} : r(\mathbf{y} \vee \mathbf{z}) = r(\mathbf{y}) \vee r(\mathbf{z}),$$

and this immediately implies that $\mu$ is a possibility measure. Therefore, as observed in Subsection 2.2, the Sugeno utility functional $f := q_\mu(\varphi_1, \dots, \varphi_n)$ can be written as

$$f(\mathbf{x}) = \bigvee_{i \in [n]} (\mu(i) \wedge \varphi_i(x_i)) = \bigvee_{i \in [n]} (r(\mathbf{0}_i^1) \wedge r(\mathbf{0}_i^{x_i})),$$
since $\mu(i) = r(\mathbf{1}\{i\}\mathbf{0}) = r(\mathbf{0}_i^1)$. By the Pareto condition, we have $\mathbf{0}_i^1 \gtrsim \mathbf{0}_i^{x_i}$, hence $r(\mathbf{0}_i^1) \wedge r(\mathbf{0}_i^{x_i}) = r(\mathbf{0}_i^{x_i})$, and thus $f(\mathbf{x})$ takes the form

$$f(\mathbf{x}) = \bigvee_{i \in [n]} r(\mathbf{0}_i^{x_i}).$$

Applying (9) repeatedly, and taking into account that $\mathbf{x} = \bigvee_{i \in [n]} \mathbf{0}_i^{x_i}$, we conclude that $f(\mathbf{x}) = r(\mathbf{x})$. As observed in Subsection 3.1, $r$ represents $\gtrsim$, and thus $\gtrsim$ is represented by the Sugeno utility function $f$ corresponding to the possibility measure $\mu$. $\square$

**Remark 3.4.** Note that the above theorem does not state that every Sugeno utility functional representing a preference relation that satisfies the conditions of Theorem 3.1 corresponds to a possibility measure. As an example, consider the case $n = 2$ with $X_1 = X_2 = \{0,1\}$ and $Y = \{0, a, b, 1\}$, where $0 < a < b < 1$. Let us define local utility functions $\varphi_i: X_i \to Y$ ($i = 1, 2$) by

$$\varphi_1(0) = 0, \quad \varphi_1(1) = b, \quad \varphi_2(0) = a, \quad \varphi_2(1) = 1,$$

and let $\mu$ be the capacity on $\{1,2\}$ given by

$$\mu(\emptyset) = 0, \quad \mu(\{1\}) = a, \quad \mu(\{2\}) = b, \quad \mu(\{1,2\}) = 1.$$

It is easy to see that $\mu$ is not a possibility measure, but the preference relation $\gtrsim$ on $X_1 \times X_2$ represented by $f := q_\mu(\varphi_1, \varphi_2)$ clearly satisfies $(\vee)$, since $(0,0) \sim (1,0) \prec (0,1) \sim (1,1)$. On the other hand, the same relation can be represented by the second projection $(x_1, x_2) \mapsto x_2$ on $\{0,1\}^2$, which is in fact a Sugeno integral with respect to a possibility measure satisfying $0 = \mu(\emptyset) = \mu(\{1\})$ and $\mu(\{2\}) = \mu(\{1,2\}) = 1$.

Concerning necessity measures, by duality, we have the following characterization of the weighted conjunction of utility functions.

**Theorem 3.5.** A preference relation $\gtrsim$ satisfies one (or, equivalently, all) of the axioms in Theorem 3.2 if and only if there are local utility functions $\varphi_i$, $i \in [n]$, and a necessity measure $\mu$, such that $\gtrsim$ is represented by the Sugeno utility functional $f = q_\mu(\varphi_1, \dots, \varphi_n)$.

**3.4. Axiomatizations of preference relations represented by Sugeno utility functionals.** Recall that $\gtrsim$ is a preference relation if and only if $\gtrsim$ is represented by an order-preserving function valued in some chain (for instance, by its rank function). The following result that draws from Theorem 2.12 (and whose interpretation was given immediately after) axiomatizes those preference relations represented by general Sugeno utility functionals.

**Theorem 3.6.** A preference relation $\gtrsim$ on $\mathbf{X}$ can be represented by a Sugeno utility functional if and only if

$$(10) \qquad \mathbf{x}_k^0 \prec \mathbf{x}_k^a \quad \text{and} \quad \mathbf{y}_k^a \prec \mathbf{y}_k^1 \implies \mathbf{x}_k^a \gtrsim \mathbf{y}_k^a$$

holds for all $\mathbf{x}, \mathbf{y} \in \mathbf{X}$ and $k \in [n]$, $a \in X_k$.

*Proof.* From Theorem 2.12 it follows that $r$ is a Sugeno utility functional if and only if (10) holds. Thus, to prove Theorem 3.6, it is enough to verify that $\gtrsim$ can be represented by a Sugeno utility functional if and only if $r$ is a Sugeno utility functional.

The sufficiency is obvious. For the necessity, let us assume that $\gtrsim$ is represented by a Sugeno utility functional $f: \mathbf{X} \to \mathbf{Y}$ of the form $f = q_\mu(\varphi_1, \dots, \varphi_n)$. Furthermore, we may assume that $f$ is surjective.

Since $r$ also represents $\gtrsim$, we have $f(\mathbf{x}) \le f(\mathbf{y}) \iff r(\mathbf{x}) \subseteq r(\mathbf{y})$, and hence the mapping $\alpha: \mathbf{Y} \to \mathbf{X}/\sim$ given by $\alpha(f(\mathbf{x})) = r(\mathbf{x})$ is a well-defined order-isomorphism between $\mathbf{Y}$ and $\mathbf{X}/\sim$. As $\alpha$ is order-preserving, it commutes with the lattice operations $\vee$ and $\wedge$, and hence

$$r(\mathbf{x}) = \alpha(f(\mathbf{x})) = \bigvee_{I \subseteq [n]} (\alpha(\mu(I)) \wedge \bigwedge_{i \in I} \alpha(\varphi_i(x_i)))$$

<footnote n="2">²Since $\mathbf{X}/\sim$ has two elements, this is essentially the same as the rank function $r: \mathbf{X} \to \mathbf{X}/\sim$.</footnote>
for all $\mathbf{x} \in \mathbf{X}$. Since $\alpha$ is an order-isomorphism, each composition $\alpha\varphi_i$, $i \in [n]$, is a local utility function, and the composition $\alpha\mu$ is a capacity on $[n]$. Thus $r$ is indeed a Sugeno utility functional, namely, $r = \alpha f = q_{\alpha\mu}(\alpha\varphi_1, \dots, \alpha\varphi_n)$. $\square$

## 4. DMU vs. MCDM

In [25], Dubois, Prade and Sabbadin, considered the qualitative setting under uncertainty, and axiomatized those preference relations on $\mathbf{X} = X^n$ that can be represented by special (state-independent) Sugeno utility functionals $f: \mathbf{X} \to \mathbf{Y}$ of the form

$$ (11) \qquad f(\mathbf{x}) = p(\varphi(x_1), \dots, \varphi(x_n)) $$

where $p: Y^n \to \mathbf{Y}$ is a polynomial function (or, equivalently, a Sugeno integral; see, e.g., [11, 12]), and $\varphi: X \to \mathbf{Y}$ is a utility function. To get it, two additional axioms (more restrictive than $(DD_{\sim})$ and $(CD_{\sim})$) were considered, namely, the so-called *restrictive disjunctive dominance* and *restrictive conjunctive dominance*:

$$ (RDD) \qquad \forall \mathbf{x}, \mathbf{y}, \mathbf{c} \in \mathbf{X} : \mathbf{x} \succ \mathbf{y}, \mathbf{x} \succ \mathbf{c} \implies \mathbf{x} \succ \mathbf{y} \lor \mathbf{c}, $$

$$ (RCD) \qquad \forall \mathbf{x}, \mathbf{y}, \mathbf{c} \in \mathbf{X} : \mathbf{y} \succ \mathbf{x}, \mathbf{c} \succ \mathbf{x} \implies \mathbf{y} \land \mathbf{c} \succ \mathbf{x}, $$

where $\mathbf{c}$ is a constant tuple.

**Theorem 4.1** (In [25]). A preference relation $\preceq$ on $\mathbf{X} = X^n$ can be represented by a state-independent Sugeno utility functional (11) if and only if it satisfies (RDD) and (RCD).

Clearly, (11) is a particular form of (3), and thus every preference relation $\preceq$ on $\mathbf{X} = X^n$ which is representable by (11) is also representable by a Sugeno utility functional (3). In other words, we have that (RDD) and (RCD) imply condition (10). However, as the following example shows, the converse is not true.

**Example 4.2.** Let $X = \{1, 2, 3\} = \mathbf{Y}$ endowed with the natural ordering of integers, and the consider the preference relation $\preceq$ on $\mathbf{X} = X^2$ whose equivalence classes are

$$ [(3, 3)] = \{(3, 3), (2, 3)\}, $$

$$ [(3, 2)] = \{(3, 2), (3, 1), (1, 3), (2, 2), (2, 1)\}, $$

$$ [(1, 2)] = \{(1, 2), (1, 1)\}. $$

This relation does not satisfy (RDD), e.g., take $\mathbf{x} = (2, 3)$, $\mathbf{y} = (1, 3)$ and $\mathbf{c} = (2, 2)$ (similarly, it does not satisfy (RCD)), and thus it cannot be represented by a Sugeno utility functional (11). However, with $q(x_1, x_2) = (2 \land x_1) \lor (2 \land x_2) \lor (3 \land x_1 \land x_2)$, and $\varphi_1 = \{(3, 3), (2, 3), (1, 1)\}$ and $\varphi_2 = \{(3, 3), (2, 1), (1, 1)\}$, we have that $\preceq$ is represented by the Sugeno utility functional $f(x_1, x_2) = q(\varphi_1(x_1), \varphi_2(x_2))$.

In the case of preference relations induced by possibility and necessity measures, Dubois, Prade and Sabbadin [26] obtained the following axiomatizations.

**Theorem 4.3** (In [26]). Let $\preceq$ be a preference relation on $\mathbf{X} = X^n$. Then the following assertions hold.

(i) $\preceq$ satisfies (OPT) and (RCD) if and only if there exist a utility function $\varphi$ and a possibility measure $\mu$, such that $\preceq$ is represented by the Sugeno utility functional $f = q_\mu(\varphi, \dots, \varphi)$.

(ii) $\preceq$ satisfies (PESS) and (RDD) if and only if there exist a utility function $\varphi$ and a necessity measure $\mu$, such that $\preceq$ is represented by the Sugeno utility functional $f = q_\mu(\varphi, \dots, \varphi)$.

Again, every preference relation which is representable as in (i) or (ii) of Theorem 4.3, is representable as in Theorems 3.3 and 3.5, respectively. In other words, MCDM is at least as expressive as DMU.

Now one could think that in these more restrictive possibility and necessity frameworks the expressive power of DMU and MCDM would coincide. As the following example shows, MCDM is again strictly more expressive than DMU.
**Example 4.4.** Let once again $X = \{1, 2, 3\} = Y$ endowed with the natural ordering of integers, and the consider the preference relation $\preceq$ on $X = X^2$ whose equivalence classes are

$$[(3,3)] = \{(3,3), (3,2), (3,1), (1,3), (2,3)\}, \\ [(2,2)] = \{(2,2), (2,1)\}, \\ [(1,2)] = \{(1,2), (1,1)\}.$$

This relation does not satisfy (RCD), e.g., take $\mathbf{x} = (1,2)$, $\mathbf{y} = (1,3)$ and $\mathbf{c} = (2,2)$, and thus it cannot be represented by a Sugeno utility functional $f = q_{\mu}(\varphi, \dots, \varphi)$ where $\mu$ is possibility measure. However, with $q(x_1, x_2) = (3 \wedge x_1) \vee (3 \wedge x_2)$, and $\varphi_1 = \{(3,3), (2,2), (1,1)\}$ and $\varphi_2 = \{(3,3), (2,1), (1,1)\}$, we have that $\preceq$ is represented by the Sugeno utility functional $f(x_1, x_2) = q(\varphi_1(x_1), \varphi_2(x_2))$.

Dually, we can easily construct an example of a preference relation representable in the necessity setting of MCDM, but not in that of DMU.

## 5. CONCLUDING REMARKS AND OPEN PROBLEMS

In the numerical setting, utility functions play a crucial role in the expressive power of the expected utility approach, introducing the subjective perception of (real-valued) consequences of acts and expressing the attitude of the decision-maker in the face of uncertainty. In the qualitative and finite setting, the latter point is taken into account by the choice of the monotonic set-function in the Sugeno integral expression.

So one might have thought that a direct appreciation of consequences is enough to describe a large class of preference relations. This paper questions this claim by showing that even in the finite qualitative setting, the use of local utility functions increases the expressive power of Sugeno integrals, thus proving that the framework of qualitative MCDM is formally more general that the one of state-independent qualitative DMU. In fact, the same holds in the more restrictive frameworks dealing with possibility and necessity measures.

## 6. APPENDIX I: FACTORIZATION OF SUGENO UTILITY FUNCTIONALS

In this appendix we recall the procedure given in [16] to obtain all possible factorizations of a given Sugeno utility functional into a composition of a Sugeno integral (or, more generally, a polynomial function) with local utility functions. Note that Theorem 2.11 provides a canonical polynomial function $p_0$ that can be used in such a factorization.

First, we provide all possible inner functions $\varphi_k: X_k \to Y$ which can be used in the factorization of any Sugeno utility functional. To this extent, we need to recall the basic setting of [16], and in what follows we take advantage of Birkhoff's Representation Theorem [1] to embed $Y$ into $\mathcal{P}(U)$, the power set of a finite set $U$. Identifying $Y$ with its image under this embedding, we will consider $Y$ as a sublattice of $\mathcal{P}(U)$ with $0 = \emptyset$ and $1 = U$. The complement of a set $S \in \mathcal{P}(U)$ will be denoted by $\bar{S}$. Since $Y$ is closed under intersections, it induces a closure operator $cl$ on $U$, and since $Y$ is closed under unions, it also induces a dual closure operator int (also known as “interior operator”):

$$\mathrm{cl}(S) := \bigwedge_{\substack{y \in Y \\ y \geq S}} y, \quad \mathrm{int}(S) := \bigvee_{\substack{y \in Y \\ y \leq S}} y.$$

(Recall that $Y$ is thought of as a sublattice of $\mathcal{P}(U)$.

Now given an order-preserving function $f: X \to Y$, we define for each $k \in [n]$ two auxiliary functions $\Phi_k^-, \Phi_k^+$: $X_k \to Y$ as follows:

$$(12) \quad \Phi_k^-(a_k) := \bigvee_{x_k=a_k} \mathrm{cl}(f(\mathbf{x}) \wedge \overline{f(\mathbf{x}_k^0)}), \quad \Phi_k^+(a_k) := \bigwedge_{x_k=a_k} \mathrm{int}(f(\mathbf{x}) \vee \overline{f(\mathbf{x}_k^1)}).$$

Since $f$ is order-preserving, both $\Phi_k^-$ and $\Phi_k^+$ are also order-preserving.
With the help of these two mappings, we can determine all possible local utility functions $\varphi_i: X_i \to Y, i \in [n]$, which can be used to factorize a Sugeno utility functional $f: X \to Y$ as a composition

$$f(\mathbf{x}) = p(\varphi_1(x_1), \dots, \varphi_n(x_n)),$$

where $p: Y^n \to Y$ is a polynomial function.

**Theorem 6.1 (In [16]).** For any order-preserving function $f: X \to Y$ and order-preserving mappings $\varphi_k: X_k \to Y (k \in [n])$, the following conditions are equivalent:

(1) $\Phi_k^- \le \varphi_k \le \Phi_k^+$ holds for all $k \in [n]$;

(2) $f(\mathbf{x}) = p_0(\varphi(\mathbf{x}))$;

(3) there exists a polynomial function $p: Y^n \to Y$ such that $f(\mathbf{x}) = p(\varphi(\mathbf{x}))$.

In particular, $\Phi_k^-$ and $\Phi_k^+$ are the minimal and maximal, respectively, local utility functions (w.r.t. the usual pointwise ordering of functions), which can be used to factorize a Sugeno utility functional. Moreover, we have the following corollary.

**Corollary 6.2.** An order-preserving function $f: X \to Y$ is a Sugeno utility functional if and only if

$$(13) \qquad \Phi_k^- \le \Phi_k^+, \quad \text{for all } k \in [n].$$

As mentioned, $p_0$ can be used in any factorization of a Sugeno utility functional, but there may be other suitable polynomial functions. To find all such polynomial functions, let us fix local utility functions $\varphi_k: X_k \to Y (k \in [n])$, such that $\Phi_k^- \le \varphi_k \le \Phi_k^+$ for each $k \in [n]$. To simplify notation, let $a_k = \varphi_k(0), b_k = \varphi_k(1)$, and for each $I \subseteq [n]$ let $\mathbf{1}_I \in Y^n$ be the n-tuple whose i-th component is $a_i$ if $i \notin I$ and $b_i$ if $i \in I$. If $p: Y^n \to Y$ is a polynomial function such that $f(\mathbf{x}) = p(\varphi(\mathbf{x}))$, then

$$(14) \qquad p(\mathbf{1}_I) = f(\hat{\mathbf{1}}_I) \quad \text{for all } I \subseteq [n],$$

since $\mathbf{1}_I = \varphi(\hat{\mathbf{1}}_I)^3$. As shown in [16], (14) is not only necessary but also sufficient to establish the factorization $f(\mathbf{x}) = p(\varphi(\mathbf{x}))$.

To make this description explicit, let us define the following two polynomial functions first presented in [17], namely,

$$p^{-}(\mathbf{y}) = \bigvee_{I \subseteq [n]} (c_{I}^{-} \wedge \bigwedge_{i \in I} y_{i}), \quad \text{where } c_{I}^{-} = \text{cl}(f(\hat{\mathbf{1}}_{I}) \wedge \bigwedge_{i \notin I} \overline{a_{i}}),$$

and

$$p^{+}(\mathbf{y}) = \bigvee_{I \subseteq [n]} (c_{I}^{+} \wedge \bigwedge_{i \in I} y_{i}), \quad \text{where } c_{I}^{+} = \text{int}(f(\hat{\mathbf{1}}_{I}) \vee \bigvee_{i \in I} \overline{b_{i}}).$$

As it turned out, a polynomial function $p$ is a solution of (14) if and only if $p^{-} \le p \le p^{+}$. Since, by Theorem 2.1, $p$ is uniquely determined by its values on the tuples $\mathbf{1}_I$, this is equivalent to

$$c_I^- = p^{-}(\mathbf{1}_I) \le p(\mathbf{1}_I) \le p^{+}(\mathbf{1}_I) = c_I^{+} \quad \text{for all } I \subseteq [n].$$

These observations are reassembled in the following theorem which provides the description of all possible factorizations of Sugeno utility functionals.

**Theorem 6.3 (In [16]).** Let $f: X \to Y$ be an order-preserving function, for each $k \in [n]$ let $\varphi_k: X_k \to Y$ be a local utility function, and let $p: Y^n \to Y$ be a polynomial function. Then $f(\mathbf{x}) = p(\varphi(\mathbf{x}))$ if and only if $\Phi_k^- \le \varphi_k \le \Phi_k^+$ for each $k \in [n]$, and $p^{-} \le p \le p^{+}$.

<footnote n="3">³Recall that $\hat{\mathbf{1}}_I$ denotes the characteristic vector of $I \subseteq [n]$ in $X$, i.e., $\hat{\mathbf{1}}_I \in X$ is the n-tuple whose i-th component is $1_{X_i}$ if $i \in I$, and $0_{X_i}$ otherwise.</footnote>
## 7. APPENDIX II: PROOF OF THEOREM 2.12

As before, $Y$ can be thought of as a sublattice of $\mathcal{P}(U)$ for some finite set $U$. In fact, $U$ can be chosen as $U = [m] = \{1, 2, \dots, m\}$, and $Y = \{[0], [1], \dots, [m]\}$, where $[0] = \emptyset$. In this case the two operators given in the Appendix I, become rather simple: for every $S \subseteq U$, we have

$$ \mathrm{cl}(S) = [\max S], \quad \mathrm{int}(S) = [\min \overline{S} - 1]. $$

Let us now consider an order-preserving function $f: \mathbf{X} \to Y$. Then $f(\mathbf{x}_k^0) = [u], f(\mathbf{x}) = [v], f(\mathbf{x}_k^1) = [w]$ with $u \le v \le w$, hence we have

$$ \begin{aligned} f(\mathbf{x}) \wedge \overline{f(\mathbf{x}_k^0)} &= \{u+1, \dots, v\}, \\ f(\mathbf{x}) \vee \overline{f(\mathbf{x}_k^1)} &= \{1, \dots, v, w+1, \dots, m\}. \end{aligned} $$

Therefore the terms in the definition of $\Phi_k^-$ and $\Phi_k^+$ can be determined as follows:

$$ (15) \qquad \mathrm{cl}(f(\mathbf{x}) \wedge \overline{f(\mathbf{x}_k^0)}) = \begin{cases} f(\mathbf{x}), & \text{if } f(\mathbf{x}_k^0) < f(\mathbf{x}); \\ \emptyset, & \text{if } f(\mathbf{x}_k^0) = f(\mathbf{x}); \end{cases} $$

$$ (16) \qquad \mathrm{int}(f(\mathbf{x}) \vee \overline{f(\mathbf{x}_k^1)}) = \begin{cases} f(\mathbf{x}), & \text{if } f(\mathbf{x}_k^1) > f(\mathbf{x}); \\ U, & \text{if } f(\mathbf{x}_k^1) = f(\mathbf{x}). \end{cases} $$

By making use of these observations we can now prove Theorem 2.12:

**Theorem 7.1 (In [16]).** A function $f: \mathbf{X} \to Y$ is a Sugeno utility functional if and only if it is order-preserving and satisfies

$$ (17) \qquad f(\mathbf{x}_k^0) < f(\mathbf{x}_k^a) \quad \text{and} \quad f(\mathbf{y}_k^a) < f(\mathbf{y}_k^1) \implies f(\mathbf{x}_k^a) \le f(\mathbf{y}_k^a) $$

for all $\mathbf{x}, \mathbf{y} \in \mathbf{X}$ and $k \in [n], a \in X_k$.

*Proof.* Suppose first that $f$ is a Sugeno utility functional. As observed, $f$ is order-preserving, and thus we only need to verify that (17) holds. For a contradiction, suppose that there is $k \in [n]$ such that for some $a \in X_k$ and $\mathbf{x}, \mathbf{y} \in \mathbf{X}$, we have $f(\mathbf{x}_k^0) < f(\mathbf{x}_k^a)$ and $f(\mathbf{y}_k^a) < f(\mathbf{y}_k^1)$, but $f(\mathbf{x}_k^a) > f(\mathbf{y}_k^a)$. Then

$$ \mathrm{cl}(f(\mathbf{x}_k^a) \wedge \overline{f(\mathbf{x}_k^0)}) > \mathrm{int}(f(\mathbf{y}_k^a) \vee \overline{f(\mathbf{y}_k^1)}), $$

and thus $\Phi_k^-(a) > \Phi_k^+(a)$. This contradicts Corollary 6.2 as $f$ is a Sugeno utility functional. Hence both conditions are necessary.

To see that these conditions are also sufficient, suppose that $f$ is order-preserving and satisfies (17). Then, for every $k \in [n], a \in X_k$, and every $\mathbf{x}, \mathbf{y} \in \mathbf{X}$,

$$ \mathrm{cl}(f(\mathbf{x}_k^a) \wedge \overline{f(\mathbf{x}_k^0)}) \le \mathrm{int}(f(\mathbf{y}_k^a) \vee \overline{f(\mathbf{y}_k^1)}). $$

Thus, for every $k \in [n]$, we have $\Phi_k^- \le \Phi_k^+$ and, by Corollary 6.2, $f$ is a Sugeno utility function. $\square$

## REFERENCES

[1] G. Birkhoff, On the combination of subalgebras. Proc. Camb. Phil. Soc. 29, 441–464 (1933)

[2] G. Beliakov, A. Pradera and T. Calvo, *Aggregation Functions: A Guide for Practitioners*, Studies in Fuzziness and Soft Computing vol. 221 (Springer, Berlin, 2007).

[3] P. Benvenuti, R. Mesiar and D. Vivona, “Monotone set functions-based integrals”, in *Handbook of measure theory* (North-Holland, Amsterdam, 2002) pp. 1329–1379.

[4] C. Boutilier, R. I. Brafman, C. Domshlak, H. H. Hoos and D. Poole. CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. *J. Artif. Intell. Res.* **21** (2004) 135–191.

[5] D. Bouyssou, D. Dubois, H. Prade and M. Pirlot (eds), *Decision-Making Process - Concepts and Methods* (ISTE/John Wiley, 2009).

[6] D. Bouyssou, T. Marchant, P. Perny, Social choice theory and multicriteria decision aiding In [5] (ISTE/John Wiley, 2009), 779-810.

[7] M. Couceiro, D. Dubois, H. Prade, T. Waldhauser. Decision making with Sugeno integrals: DMU vs. MCDM. *20th European Conference on Artificial Intelligence* (ECAI2012), 288–293, 2012.

[8] M. Couceiro and J.-L. Marichal, Polynomial Functions over Bounded Distributive Lattices, *J. Mult.-Valued Logic Soft Comput.* 18 (2012): 247-256.
[9] M. Couceiro and J.-L. Marichal, Characterizations of Discrete Sugeno Integrals as Polynomial Functions over Distributive Lattices, *Fuzzy Sets and Systems* **161**:5 (2010) 694-707.

[10] M. Couceiro and J.-L. Marichal, Representations and Characterizations of Polynomial Functions on Chains, *J. Mult.-Valued Logic Soft Comput.* **16**:1-2 (2010) 65-86.

[11] M. Couceiro and J.-L. Marichal, Axiomatizations of Quasi-Polynomial Functions on Bounded Chains, *Aequ. Math.* **396**:1 (2009) 195-213.

[12] M. Couceiro, J.-L. Marichal. Quasi-polynomial functions over bounded distributive lattices, *Aequ. Math.* **80** (2010) 319-334.

[13] M. Couceiro and T. Waldhauser, Sugeno Utility Functions I: Axiomatizations, *Lecture Notes in Artificial Intelligence* vol. 6408, (Springer, Berlin, 2010) 79-90.

[14] M. Couceiro and T. Waldhauser, Sugeno Utility Functions II: Factorizations, *Lecture Notes in Artificial Intelligence* vol. 6408, (Springer, Berlin, 2010) 91-103.

[15] M. Couceiro and T. Waldhauser, Axiomatizations and factorizations of Sugeno utility functionals. *Int. J. Uncertain. Fuzziness Knowledge-Based Systems* **19**:4 (2011) 635-658.

[16] M. Couceiro and T. Waldhauser, Pseudo-polynomial functions over finite distributive lattices, *Fuzzy Sets and Systems* **239** (2014) 21-34

[17] M. Couceiro, T. Waldhauser, Interpolation by polynomial functions of distributive lattices: a generalization of a theorem of R. L. Goodstein, *Algebra Universalis* **69**:3 (2013) 287-299

[18] B. A. Davey, H. A. Priestley. *Introduction to Lattices and Order*, Cambridge University Press, New York, 2002.

[19] J. Doyle and R. Thomason. Background to qualitative decision theory, *The AI Magazine* **20**:2 (1999) 55-68.

[20] D. Dubois, M. Grabisch, F. Modave, H. Prade. Relating decision under uncertainty and multicriteria decision making models, *Int. J. Intelligent Systems* **15**:10 (2000) 967-979.

[21] D. Dubois, D. Le Berre, H. Prade, R. Sabbadin. Logical representation and computation of optimal decisions in a qualitative setting. AAAI-98, 588-593, 1998.

[22] D. Dubois, J.-L. Marichal, H. Prade, M. Roubens and R. Sabbadin. The Use of the Discrete Sugeno Integral in Decision-Making: a Survey, *Int. J. Uncertain. Fuzziness Knowledge-Based Systems* **9**:5 (2001) 539-561.

[23] D. Dubois and H. Prade. Weighted minimum and maximum operations in fuzzy set theory, *Information Sciences* **39**:2 (1986) 205-210.

[24] D. Dubois and H. Prade. *Possibility theory*, Plenum Press, N. Y., 1988.

[25] D. Dubois, H. Prade and R. Sabbadin. Qualitative decision theory with Sugeno integrals, *Fuzzy measures and integrals*, 314-332, Stud. Fuzziness Soft Comput., 40, Physica, Heidelberg, 2000

[26] D. Dubois, H. Prade and R. Sabbadin. Decision theoretic foundations of qualitative possibility theory, *EJOR* **128** (2001) 459-478.

[27] R. L. Goodstein, The Solution of Equations in a Lattice, *Proc. Roy. Soc. Edinburgh Section A* **67** (1965/1967) 231-242.

[28] G. Grätzer. *General Lattice Theory* (Birkhäuser Verlag, Berlin, 2003).

[29] M. Grabisch. The application of fuzzy integrals in multicriteria decision making, *Eur. J. Oper. Res.* **89** (3) (1996) 445-456.

[30] M. Grabisch, J.-L. Marichal, R. Mesiar and E. Pap. *Aggregation Functions*, Encyclopedia of Mathematics and its Applications vol. 127 Cambridge University Press, Cambridge, 2009.

[31] R. L. Keeney and H. Raiffa. *Decisions with Multiple Objectives: Preferences and Value Tradeoffs*, Wiley, New York, 1976.

[32] J.-L. Marichal, On Sugeno integral as an aggregation function, *Fuzzy Sets and Systems* **114** (2000) 347-365.

[33] J.-L. Marichal. Weighted Lattice Polynomials, *Discrete Math.* **309** (4) (2009) 814-820.

[34] H. Prade, A. Rico, M. Serrurier, E. Raufaste. Eliciting Sugeno Integrals: Methodology and a Case Study, *Lecture Notes in Computer Science* vol. 5590 (Springer, Berlin, 2009) 712-723.

[35] S. Rudeanu. *Lattice Functions and Equations*, Springer Series in Discrete Math. and Theor. Comp. Sci. (Springer-Verlag, London, 2001).

[36] M. J. Schervish, T. Seidenfeld, J. B. Kadane. State-Dependent Utilities *J. Amer. Statist. Assoc.*, 85, No. 411. (1990), 840-847.

[37] L.J. Savage. *The Foundations of Statistics*, New York, Dover, 1972.

[38] M. Sugeno. Theory of fuzzy integrals and its applications, Ph.D. Thesis, Tokyo Institute of Technology, Tokyo, 1974.

[39] M. Sugeno. Fuzzy measures and fuzzy integrals—a survey, in *Fuzzy automata and decision processes*, eds. M. M. Gupta, G. N. Saridis, and B. R. Gaines (North-Holland, New York, 1977) pp. 89-102.

[40] L. A. Zadeh. Fuzzy sets as a basis for a theory of possibility, *Fuzzy Sets and Systems* **1** (1978) 3-28.
(M. Couceiro) LORIA (CNRS - INRIA NANCY GRAND EST - UNIVERSITÉ DE LORRAINE) ÉQUIPE ORPAILLEUR - BAT. B, CAMPUS SCIENTIFIQUE B.P. 239, 54506 VANDŒUVRE-LÈS-NANCY, FRANCE
*E-mail address: miguel.couceiro@inria.fr*

(D. Dubois) IRIT - UNIVERSITÉ PAUL SABATIER, 31062 TOULOUSE CEDEX, FRANCE
*E-mail address: Dubois@irit.fr*

(H. Prade) IRIT - UNIVERSITÉ PAUL SABATIER, 31062 TOULOUSE CEDEX, FRANCE
*E-mail address: Prade@irit.fr*

(T. Waldhauser) BOLYAI INSTITUTE, UNIVERSITY OF SZEGED, ARADI VÉRTANÚK TERE 1, H-6720 SZEGED, HUNGARY
*E-mail address: twaldha@math.u-szeged.hu*