Miguel Couceiro

Jean-Luc Marichal

DISCRETE INTEGRALS BASED ON COMONOTONIC MODULARITY

Keywords: June 6, 2013. 2010 Mathematics Subject Classification. Primary 39B22, 39B72; Secondary 26B35 Aggregation function, discrete Choquet integral, discrete Sugeno integral, functional equation, comonotonic additivity, comonotonic modularity, axiomatization

It is known that several discrete integrals, including the Choquet and Sugeno integrals as well as some of their generalizations, are comonotonically modular functions. Based on a recent description of the class of comonotonically modular functions, we axiomatically identify more general families of discrete integrals that are comonotonically modular, including signed Choquet integrals and symmetric signed Choquet integrals as well as natural extensions of Sugeno integrals.

Introduction

Aggregation functions arise wherever merging information is needed: applied and pure mathematics (probability, statistics, decision theory, functional equations), operations research, computer science, and many applied fields (economics and finance, pattern recognition and image processing, data fusion, etc.). For recent references, see Beliakov et al. [START_REF] Beliakov | Aggregation Functions: A Guide for Practitioners[END_REF] and Grabisch et al. [START_REF] Grabisch | Aggregation functions[END_REF].

Discrete Choquet integrals and discrete Sugeno integrals are among the best known functions in aggregation theory, mainly because of their many applications, for instance, in decision making (see the edited book [START_REF] Grabisch | Fuzzy measures and integrals -Theory and applications[END_REF]). More generally, signed Choquet integrals, which need not be nondecreasing in their arguments, and the Lovász extensions of pseudo-Boolean functions, which need not vanish at the origin, are natural extensions of the Choquet integrals and have been thoroughly investigated in aggregation theory. For recent references, see, e.g., [START_REF] Cardin | Axiomatizations of signed discrete Choquet integrals[END_REF][START_REF] Couceiro | Axiomatizations of Lovász extensions of pseudo-Boolean functions[END_REF].

The class of n-variable Choquet integrals has been axiomatized independently by means of two noteworthy aggregation properties, namely comonotonic additivity (see, e.g., [START_REF] De Campos | Characterization and comparison of Sugeno and Choquet integrals[END_REF]) and horizontal min-additivity (originally called "horizontal additivity", see [START_REF] Benvenuti | Monotone set functions-based integrals[END_REF]). Function classes characterized by these properties have been recently described by the authors [START_REF] Couceiro | Axiomatizations of Lovász extensions of pseudo-Boolean functions[END_REF]. Quasi-Lovász extensions, which generalize signed Choquet integrals and Lovász extensions by transforming the arguments by a 1-variable function, have also been recently investigated by the authors [START_REF] Couceiro | Axiomatizations of quasi-Lovász extensions of pseudo-Boolean functions[END_REF] through natural aggregation properties.

Lattice polynomial functions and quasi-Sugeno integrals generalize the notion of Sugeno integral [START_REF] Couceiro | Axiomatizations of quasi-polynomial functions on bounded chains[END_REF][START_REF] Couceiro | Quasi-polynomial functions over bounded distributive lattices[END_REF][START_REF] Couceiro | Characterizations of discrete Sugeno integrals as polynomial functions over distributive lattices[END_REF][START_REF] Couceiro | Representations and characterizations of polynomial functions on chains[END_REF][START_REF] Couceiro | Polynomial functions over bounded distributive lattices[END_REF]: the former by removing the idempotency requirement and the latter also by transforming arguments by a 1-variable function. Likewise, these functions have been axiomatized by means of well-known properties such as comonotonic maxitivity and comonotonic minitivity.

All of these classes share the feature that its members are comonotonically modular. These facts motivated a recent study that led to a description of comonotonically modular functions [START_REF] Couceiro | Axiomatizations of quasi-Lovász extensions of pseudo-Boolean functions[END_REF]. In this paper we survey these and other results and present a somewhat typological study of the vast class of comonotonically modular functions, where we identify several families of discrete integrals within this class using variants of homogeneity as distinguishing feature.

The paper is organized as follows. In Section 2 we recall basic notions and terminology related to the concept of signed Choquet integral and present some preliminary characterization results. In Section 3 we survey several results that culminate in a description of comonotonic modularity and establish connections to other well studied properties of aggregation functions. These results are then used in Section 4 to provide characterizations of the various classes of functions considered in the previous sections as well as of classes of functions extending Sugeno integrals.

We employ the following notation throughout the paper. The set of permutations on X = {1, . . . , n} is denoted by S X . For every σ ∈ S X , we define

R n σ = {x = (x 1 , . . . , x n ) ∈ R n ∶ x σ(1) ⩽ ⋯ ⩽ x σ(n) }. Let R + = [0, +∞[ and R -= ]-∞, 0]
. We let I denote a nontrivial (i.e., of positive Lebesgue measure) real interval, possibly unbounded. We also introduce the notation

I + = I ∩ R + , I -= I ∩ R -, and
I n σ = I n ∩ R n σ .
For every S ⊆ X, the symbol 1 S denotes the n-tuple whose ith component is 1, if i ∈ S, and 0, otherwise. Let also 1 = 1 X and 0 = 1 ∅ . The symbols ∧ and ∨ denote the minimum and maximum functions, respectively. For every x ∈ R n , let x + be the n-tuple whose ith component is x i ∨ 0 and let x -= (-x) + . For every permutation σ ∈ S X and every i ∈ X, we set

S ↑ σ (i) = {σ(i), . . . , σ(n)}, S ↓ σ (i) = {σ(1), . . . , σ(i)}, and S ↑ σ (n + 1) = S ↓ σ (0) = ∅.

Signed Choquet integrals

In this section we recall the concepts of Choquet integral, signed Choquet integral, and symmetric signed Choquet integral. We also recall some axiomatizations of these function classes. For general background, see [START_REF] Cardin | Axiomatizations of signed discrete Choquet integrals[END_REF][START_REF] Couceiro | Axiomatizations of Lovász extensions of pseudo-Boolean functions[END_REF][START_REF] Couceiro | Axiomatizations of quasi-Lovász extensions of pseudo-Boolean functions[END_REF] A capacity on X = {1, . . . , n} is a set function µ∶ 2 X → R such that µ(∅) = 0 and µ(S) ⩽ µ(T ) whenever S ⊆ T . Definition 1. The Choquet integral with respect to a capacity µ on X is the function

C µ ∶ R n + → R defined as C µ (x) = n ∑ i=1 x σ(i) (µ(S ↑ σ (i)) -µ(S ↑ σ (i + 1))) , x ∈ (R n + ) σ , σ ∈ S X .
The concept of Choquet integral can be formally extended to more general set functions and n-tuples of R n as follows. A signed capacity on X is a set function v∶ 2 X → R such that v(∅) = 0. Definition 2. The signed Choquet integral with respect to a signed capacity v on X is the function

C v ∶ R n → R defined as (1) C v (x) = n ∑ i=1 x σ(i) (v(S ↑ σ (i)) -v(S ↑ σ (i + 1))) , x ∈ R n σ , σ ∈ S X .
From (1) it follows that C v (1 S ) = v(S) for every S ⊆ X. Thus Eq. ( 1) can be rewritten as

(2) C v (x) = n ∑ i=1 x σ(i) (C v (1 S ↑ σ (i) ) -C v (1 S ↑ σ (i+1) )) , x ∈ R n σ , σ ∈ S X .
Thus defined, the signed Choquet integral with respect to a signed capacity v on X is the continuous function C v whose restriction to each region R n σ (σ ∈ S X ) is the unique linear function that coincides with v (or equivalently, the corresponding pseudo-Boolean function v∶ {0, 1} n → R) at the n+1 vertices of the standard simplex

[0, 1] n ∩ R n σ of the unit cube [0, 1] n . As such, C v is called the Lovász extension of v.
From this observation we immediately derive the following axiomatization of the class of n-variable signed Choquet integrals over a real interval I. A function f ∶ I n → R is said to be a signed Choquet integral if it is the restriction to I n of a signed Choquet integral.

Theorem 3 ( [3]). Assume that 0 ∈ I. A function f ∶ I n → R satisfying f (0) = 0 is a signed Choquet integral if and only if f (λ x + (1 -λ) x ′ ) = λ f (x) + (1 -λ) f (x ′ ), λ ∈ [0, 1], x, x ′ ∈ I n σ , σ ∈ S X .
The next theorem provides an axiomatization of the class of n-variable signed Choquet integrals based on comonotonic additivity, horizontal min-additivity, and horizontal max-additivity. Recall that two n-tuples x, x ′ ∈ I n are said to be comonotonic if there exists σ ∈ S X such that x, x

′ ∈ I n σ . A function f ∶ I n → R is said to be comonotonically additive if, for every comonotonic n-tuples x, x ′ ∈ I n such that x + x ′ ∈ I n , we have f (x + x ′ ) = f (x) + f (x ′ ). A function f ∶ I n →
R is said to be horizontally min-additive (resp. horizontally max-additive) if, for every x ∈ I n and every c ∈ I such that xx ∧ c ∈ I n (resp.

xx ∨ c ∈ I n ), we have

f (x) = f (x ∧ c) + f (x -x ∧ c) (resp. f (x) = f (x ∨ c) + f (x -x ∨ c)). Theorem 4 ( [8]). Assume [0, 1] ⊆ I ⊆ R + or I = R. Then a function f ∶ I n → R
I = R). (ii) f (c x1 S ) = c f (x1 S )
for all x ∈ I and c > 0 such that c x ∈ I and all S ⊆ X.

Remark 1. It is easy to see that condition (ii) of Theorem 4 is equivalent to the following simpler condition:

f (x1 S ) = sign(x) x f (sign(x) 1 S ) for all x ∈ I and S ⊆ X.
We now recall the concept of symmetric signed Choquet integral. Here "symmetric" does not refer to invariance under a permutation of variables but rather to the role of the origin of R n as a symmetry center with respect to the function values.

Definition 5. Let v be a signed capacity on X. The symmetric signed Choquet integral with respect to v is the function Čv

∶ R n → R defined as (3) Čv (x) = C v (x + ) -C v (x -), x ∈ R n .
Thus defined, a symmetric signed Choquet integral is an odd function in the sense that Čv (-x) = -Čv (x). It is then not difficult to show that the restriction of Čv to R n σ is the function

Čv (x) = p ∑ i=1 x σ(i) (C v (1 S ↓ σ (i) ) -C v (1 S ↓ σ (i-1) )) + n ∑ i=p+1 x σ(i) (C v (1 S ↑ σ (i) ) -C v (1 S ↑ σ (i+1) )), x ∈ R n σ , ( 4
)
where the integer p ∈ {0, . . . , n} is given by the condition x σ(p) < 0 ⩽ x σ(p+1) , with the convention that x σ(0) = -∞ and x σ(n+1) = +∞.

The following theorem provides an axiomatization of the class of n-variable symmetric signed Choquet integrals based on horizontal median-additive additivity. Assuming that I is centered at 0, recall that a function f ∶ I n → R is said to be horizontally median-additive if, for every x ∈ I n and every c ∈ I + , we have ( 5)

f (x) = f (med(-c, x, c)) + f (x -x ∧ c) + f (x -x ∨ (-c)),
where med(-c, x, c) is the n-tuple whose ith component is the middle value of {-c, x i , c}. Equivalently, a function f ∶ I n → R is horizontally median-additive if and only if its restrictions to I n + and I n -are comonotonically additive and

f (x) = f (x + ) + f (-x -), x ∈ I n . A function f ∶ I n → R is said to be a symmetric signed Choquet integral if it is the restriction to I n of a symmetric signed Choquet integral. Theorem 6 ( [8]). Assume that I is centered at 0 with [-1, 1] ⊆ I. Then a func- tion f ∶ I n → R is a symmetric signed Choquet integral if

and only if the following conditions hold:

(i) f is horizontally median-additive.

(ii) f (c x1 S ) = c f (x1 S
) for all c, x ∈ I such that c x ∈ I and all S ⊆ X.

Remark 2. It is easy to see that condition (ii) of Theorem 6 is equivalent to the following simpler condition: f (x1 S ) = x f (1 S ) for all x ∈ I and S ⊆ X.

We end this section by recalling the following important formula. For every signed capacity v on X, we have

(6) C v (x) = C v (x + ) -C v d (x -), x ∈ R n ,
where v d is the capacity on X, called the dual capacity of v, defined as

v d (S) = v(X) -v(X ∖ S).

Comonotonic modularity

Recall that a function f ∶ I n → R is said to be modular (or a valuation) if ( 7)

f (x) + f (x ′ ) = f (x ∧ x ′ ) + f (x ∨ x ′ )
for every x, x ′ ∈ I n , where ∧ and ∨ are considered componentwise. It was proved [START_REF] Topkis | Minimizing a submodular function on a lattice[END_REF] that a function

f ∶ I n → R is modular if and only if it is separable, that is, there exist n functions f i ∶ I → R (i = 1, . . . , n) such that f = ∑ n i=1 f i . In particular, any 1-variable function f ∶ I → R is modular.
More generally, a function f ∶ I n → R is said to be comonotonically modular (or a comonotonic valuation) if [START_REF] Couceiro | Representations and characterizations of polynomial functions on chains[END_REF] holds for every comonotonic n-tuples x, x ′ ∈ I n ; see [START_REF] Couceiro | Axiomatizations of quasi-Lovász extensions of pseudo-Boolean functions[END_REF][START_REF] Mesiar | The ordered modular averages[END_REF]. It was shown [START_REF] Couceiro | Axiomatizations of quasi-Lovász extensions of pseudo-Boolean functions[END_REF] that a function f ∶ I n → R is comonotonically modular if and only if it is comonotonically separable, that is, for every σ ∈ S X , there exist functions

f σ i ∶ I → R (i = 1, . . . , n) such that f (x) = n ∑ i=1 f σ i (x σ(i) ) = n ∑ i=1 f σ σ -1 (i) (x i ), x ∈ I n σ .
We also have the following important definitions. For every x ∈ R n and every

c ∈ R + (resp. c ∈ R -) we denote by [x] c (resp. [x] c ) the n-tuple whose ith component is 0, if x i ⩽ c (resp. x i ⩾ c), and x i , otherwise. Recall that a function f ∶ I n → R,
where 0 ∈ I ⊆ R + , is invariant under horizontal min-differences if, for every x ∈ I n and every c ∈ I, we have ( 8)

f (x) -f (x ∧ c) = f ([x] c ) -f ([x] c ∧ c).
Dually, a function f ∶ I n → R, where 0 ∈ I ⊆ R -, is invariant under horizontal maxdifferences if, for every x ∈ I n and every c ∈ I, we have

(9) f (x) -f (x ∨ c) = f ([x] c ) -f ([x] c ∨ c).
The following theorem provides a description of the class of functions which are comonotonically modular.

Theorem 7 ( [9]

). Assume that I ∋ 0. For any function f ∶ I n → R, the following assertions are equivalent.

(i) f is comonotonically modular.

(ii) f | I n + is comonotonically modular (or invariant under horizontal min-differences), f | I n
-is comonotonically modular (or invariant under horizontal max-differences), and we have f

(x) + f (0) = f (x + ) + f (-x -) for every x ∈ I n . (iii) There exist g∶ I n + → R and h∶ I n -→ R such that, for every σ ∈ S X and every x ∈ I n σ , f (x) = f (0)+ p ∑ i=1 (h(x σ(i) 1 S ↓ σ (i) )-h(x σ(i) 1 S ↓ σ (i-1) ))+ n ∑ i=p+1 (g(x σ(i) 1 S ↑ σ (i) )-g(x σ(i) 1 S ↑ σ (i+1) )),
where p ∈ {0, . . . , n} is such that x σ(p) < 0 ⩽ x σ(p+1) , with the convention that x σ(0) = -∞ and x σ(n+1) = +∞. In this case, we can choose

g = f | I n + and h = f | I n -.
We finish this section with remarks on some properties subsumed by comonotonic modularity, namely the following relaxations of maxitivity and minitivity properties.

Recall that a function

f ∶ I n → R is said to be maxitive if (10) f (x ∨ x ′ ) = f (x) ∨ f (x ′ ), x, x ′ ∈ I n ,
and it is said to be minitive if

(11) f (x ∧ x ′ ) = f (x) ∧ f (x ′ ), x, x ′ ∈ I n .
As in the case of modularity, maxitivity and minitivity give rise to noteworthy decompositions of functions into maxima and minima, respectively, of 1-variable functions.

In the context of Sugeno integrals (see Section 4), de Campos et al. [START_REF] De Campos | Characterization and comparison of Sugeno and Choquet integrals[END_REF] proposed the following comonotonic variants of these properties. A function f ∶ I n → R is said to be comonotonic maxitive (resp. comonotonic minitive) if (10) (resp. [START_REF] De Campos | Characterization and comparison of Sugeno and Choquet integrals[END_REF]) holds for any two comonotonic n-tuples x, x ′ ∈ I n . It was shown in [START_REF] Couceiro | Representations and characterizations of polynomial functions on chains[END_REF] that any of these properties implies nondecreasing monotonicity, and it is not difficult to observe that comonotonic maxitivity together with comonotonic minitivity imply comonotonic modularity; the converse is not true (e.g., the arithmetic mean).

Explicit descriptions of each one of these properties was given in [START_REF] Couceiro | Axiomatizations of quasi-polynomial functions on bounded chains[END_REF] for functions over bounded chains. For the sake of self-containment, we present these descriptions here. To this end, we now assume that I = [a, b] ⊆ R, and for each S ⊆ X, we denote by e S the n-tuple in {a, b} n whose i-th component is b if i ∈ S, and a otherwise.

Theorem 8 ( [4]). Assume I = [a, b] ⊆ R. A function f ∶ I n → R is comonotonic maxitive (resp.

comonotonic minitive) if and only if there exists a nondecreasing function g∶ I

n → R such that f (x) = ⋁ S⊆X g(e S ∧ ⋀ i∈S x i ) (resp. f (x) = ⋀ S⊆X g(e X∖S ∨ ⋁ i∈S x i )).
In this case, we can choose g = f .

These descriptions are further refined in the following corollary. (i) f is comonotonic maxitive (resp. comonotonic minitive).

(ii) there are unary nondecreasing functions

φ S ∶ I → R (S ⊆ X) such that f (x) = ⋁ S⊆X φ S ( ⋀ i∈S x i ) (resp. f (x) = ⋀ S⊆X φ S ( ⋁ i∈S x i )).
In this case, we can choose φ S (x) = f (e S ∧ x) (resp. φ S (x) = f (e X∖S ∨ x)) for every S ⊆ X. (iii) for every σ ∈ S X , there are nondecreasing functions f σ i ∶ I → R (i = 1, . . . , n) such that, for every x ∈ I n σ ,

f (x) = ⋁ i∈X f σ i (x σ(i) ) (resp. f (x) = ⋀ i∈X f σ i (x σ(i) )).
In this case, we can choose

f σ i (x) = f (e S ↑ σ (i) ∧x) (resp. f σ i (x) = f (e S ↓ σ (i-1) ∨ x)).

Classes of comonotonically modular integrals

In this section we present axiomatizations of classes of functions that naturally generalize Choquet integrals (e.g., signed Choquet integrals and symmetric signed Choquet integrals) by means of comonotonic modularity and variants of homogeneity. From the analysis of the more stringent properties of comonotonic minitivity and comonotonic maxitivity, we also present axiomatizations of classes of functions generalizing Sugeno integrals.

Comonotonically modular integrals generalizing Choquet integrals.

The following theorem provides an axiomatization of the class of n-variable signed Choquet integrals.

Theorem 10. Assume [0, 1] ⊆ I ⊆ R + or [-1, 1] ⊆ I. Then a function f ∶ I n → R is a signed Choquet integral if

and only if the following conditions hold:

(i) f is comonotonically modular.

(ii) f (0) = 0 and f (x1 S ) = sign(x) x f (sign(x) 1 S ) for all x ∈ I and S ⊆ X.

(iii) If [-1, 1] ⊆ I, then f (1 X∖S ) = f (1) + f (-1 S ) for all S ⊆ X.
Proof. (Necessity) Assume that f is a signed Choquet integral, f = C v . Then condition (ii) is satisfied in view of Theorem 4 and Remark 1. If [-1, 1] ⊆ I, then by ( 6) we have

C v (-1 S ) = -C v d (1 S ) = C v (1 X∖S ) -C v (1),
which shows that condition (iii) is satisfied. Let us now show that condition (i) is also satisfied. For every σ ∈ S X and every x ∈ R n σ , setting p ∈ {0, . . . , n} such that x σ(p) < 0 ⩽ x σ(p+1) , by (2) and conditions (iii) and (ii), we have

C v (x) = n ∑ i=1 x σ(i) (C v (1 S ↑ σ (i) ) -C v (1 S ↑ σ (i+1) )) = p ∑ i=1 x σ(i) (C v (-1 S ↓ σ (i-1) ) -C v (-1 S ↓ σ (i) )) + n ∑ i=p+1 x σ(i) (C v (1 S ↑ σ (i) ) -C v (1 S ↑ σ (i+1) )) = p ∑ i=1 (C v (x σ(i) 1 S ↓ σ (i) ) -C v (x σ(i) 1 S ↓ σ (i-1) )) + n ∑ i=p+1 (C v (x σ(i) 1 S ↑ σ (i) ) -C v (x σ(i) 1 S ↑ σ (i+1) ))
which shows that condition (iii) of Theorem 7 is satisfied. Hence C v is comonotonically modular.

(Sufficiency) Assume that f satisfies conditions (i)-(iii). By condition (iii) of Theorem 7 and conditions (ii) and (iii), for every σ ∈ S X and every x ∈ R n σ we have

f (x) = p ∑ i=1 (f (x σ(i) 1 S ↓ σ (i) ) -f (x σ(i) 1 S ↓ σ (i-1) )) + n ∑ i=p+1 (f (x σ(i) 1 S ↑ σ (i) ) -f (x σ(i) 1 S ↑ σ (i+1) )) = p ∑ i=1 x σ(i) (f (-1 S ↓ σ (i-1) ) -f (-1 S ↓ σ (i) )) + n ∑ i=p+1 x σ(i) (f (1 S ↑ σ (i) ) -f (1 S ↑ σ (i+1) )) = n ∑ i=1 x σ(i) (f (1 S ↑ σ (i) ) -f (1 S ↑ σ (i+1) ))
which, combined with (2), shows that f is a signed Choquet integral. show that condition (i) is also satisfied. For every σ ∈ S X and every x ∈ R n σ , setting p ∈ {0, . . . , n} such that x σ(p) < 0 ⩽ x σ(p+1) , by (4) and condition (ii), we have

C v (x) = p ∑ i=1 x σ(i) (C v (1 S ↓ σ (i) ) -C v (1 S ↓ σ (i-1) )) + n ∑ i=p+1 x σ(i) (C v (1 S ↑ σ (i) ) -C v (1 S ↑ σ (i+1) )) = p ∑ i=1 (C v (x σ(i) 1 S ↓ σ (i) ) -C v (x σ(i) 1 S ↓ σ (i-1) )) + n ∑ i=p+1 (C v (x σ(i) 1 S ↑ σ (i) ) -C v (x σ(i) 1 S ↑ σ (i+1) ))
which shows that condition (iii) of Theorem 7 is satisfied. Hence C v is comonotonically modular.

(Sufficiency) Assume that f satisfies conditions (i) and (ii). By condition (iii) of Theorem 7 and condition (ii), for every σ ∈ S X and every x ∈ R n σ we have

f (x) = p ∑ i=1 (f (x σ(i) 1 S ↓ σ (i) ) -f (x σ(i) 1 S ↓ σ (i-1) )) + n ∑ i=p+1 (f (x σ(i) 1 S ↑ σ (i) ) -f (x σ(i) 1 S ↑ σ (i+1) )) = p ∑ i=1 x σ(i) (f (1 S ↓ σ (i) ) -f (1 S ↓ σ (i-1) )) + n ∑ i=p+1 x σ(i) (f (1 S ↑ σ (i) ) -f (1 S ↑ σ (i+1) ))
which, combined with (4), shows that f is a symmetric signed Choquet integral.

The authors [START_REF] Couceiro | Axiomatizations of quasi-Lovász extensions of pseudo-Boolean functions[END_REF] showed that comonotonically modular functions also include the class of signed quasi-Choquet integrals on intervals of the forms I + and I -and the class of symmetric signed quasi-Choquet integrals on intervals I centered at the origin. Definition 12. Assume I ∋ 0 and let v be a signed capacity on X. A signed quasi-Choquet integral with respect to v is a function f ∶ I n → R defined as f (x) = C v (φ(x 1 ), . . . , φ(x n )), where φ∶ I → R is a nondecreasing function satisfying φ(0) = 0.

We now recall axiomatizations of the class of n-variable signed quasi-Choquet integrals on I + and I -by means of comonotonic modularity and variants of homogeneity.

Theorem 13 ( [9]). Assume

[0, 1] ⊆ I ⊆ R + (resp. [-1, 0] ⊆ I ⊆ R -) and let f ∶ I n → R be a nonconstant function such that f (0) = 0.
Then the following assertions are equivalent.

(i) f is a signed quasi-Choquet integral and there exists S ⊆ X such that

f (1 S ) ≠ 0 (resp. f (-1 S ) ≠ 0). (ii) f | I n + is

comonotonically modular (or invariant under horizontal min-differences), f | I n

-is comonotonically modular (or invariant under horizontal max-differences), and there exists a nondecreasing function φ∶ I → R satisfying φ(0) = 0 such that f (x1 S ) = sign(x) φ(x) f (sign(x) 1 S ) for every x ∈ I and every S ⊆ X.

Remark 5. If I = [0, 1] (resp. I = [-1, 0
]), then the "nonconstant" assumption and the second condition in assertion (i) of Theorem 13 can be dropped off.

The extension of Theorem 13 to functions on intervals I centered at 0 and containing [-1, 1] remains an interesting open problem.

We now recall the axiomatization obtained by the authors of the class of nvariable symmetric signed quasi-Choquet integrals. Definition 14. Assume I is centered at 0 and let v be a signed capacity on X. A symmetric signed quasi-Choquet integral with respect to v is a function f ∶ I n → R defined as f (x) = Čv (φ(x 1 ), . . . , φ(x n )), where φ∶ I → R is a nondecreasing odd function.

Theorem 15 ( [9]). Assume that

I is centered at 0 with [-1, 1] ⊆ I and let f ∶ I n → R be a function such that f | I n + or f | I n -is
S µ (x) = ⋁ i∈X x σ(i) ∧ µ(S ↑ σ (i)), x ∈ I n σ , σ ∈ S X .
As the following proposition suggests, Sugeno integrals can be viewed as idempotent "lattice polynomial functions" (see [START_REF] Marichal | Weighted lattice polynomials[END_REF]). As mentioned, the properties of comonotonic maxitivity and comonotonic minitivity were introduced by de Campos et al. in [START_REF] De Campos | Characterization and comparison of Sugeno and Choquet integrals[END_REF] to axiomatize the class of Sugeno integrals. However, without further assumptions, they define a wider class of functions that we now define. (i) f is a quasi-Sugeno integral.

(ii) f is comonotonically maxitive and comonotonically minitive.

(iii) f is nondecreasing, and there exists a nondecreasing function φ∶ J → I such that for every x ∈ J n and r ∈ J, we have

(12) f (r ∨ x) = φ(r) ∨ f (x) and f (r ∧ x) = φ(r) ∧ f (x),
where r ∨ x (resp. r ∧ x) is the n-tuple whose ith component is r ∨ x i (resp. r ∧ x i ). In this case, φ can be chosen as φ(x) = f (x, . . . , x).

Remark 7. The two conditions given in ( 12) are referred to in [START_REF] Couceiro | Quasi-polynomial functions over bounded distributive lattices[END_REF] as quasi-max homogeneity and quasi-min homogeneity, respectively.

As observed at the end of the previous section, condition (ii) (and hence (i) or (iii)) of Theorem 19 implies comonotonic modularity. As the following result shows, the converse is true whenever f is nondecreasing and verifies any of the following weaker variants of quasi-max homogeneity and quasi-min homogeneity:

f (x ∨ e S ) = f (x, . . . , x) ∨ f (e S ), x ∈ J, S ⊆ X, (13) f (x ∧ e S ) = f (x, . . . , x) ∧ f (e S ), x ∈ J, S ⊆ X. ( 14
(i) f is a quasi-Sugeno integral, f (x) = S µ (φ(x 1 ), . . . , φ(x n )), where φ(x) = f (x, . . . , x). (ii) f is a quasi-Sugeno integral.
(iii) f is comonotonically modular, nondecreasing, and satisfies ( 13) or ( 14). (iv) f is nondecreasing and satisfies ( 13) and [START_REF] Marichal | Weighted lattice polynomials[END_REF].

Proof. (i) ⇒ (ii) Trivial.

(ii) ⇒ (iii) Follows from Theorem 19.

(iii) ⇒ (iv) Suppose that f is comonotonically modular and satisfies [START_REF] Grabisch | Fuzzy measures and integrals -Theory and applications[END_REF]. Then,

f (x ∧ e S ) = f (x, . . . , x) + f (e S ) -f (x ∨ e S ) = f (x, . . . , x) + f (e S ) -f (x, . . . , x) ∨ f (e S ) = f (x, . . . , x) ∧ f (e S ).
Hence f satisfies [START_REF] Marichal | Weighted lattice polynomials[END_REF]. The other case can be dealt with dually. (iv) ⇒ (i) Define φ(x) = f (x, . . . , x). By nondecreasing monotonicity and ( 14), for every S ⊆ X we have

f (x) ⩾ f (e S ∧ ⋀ i∈S x i ) = f (e S ) ∧ φ( ⋀ i∈S x i ) = f (e S ) ∧ ⋀ i∈S φ(x i )
and thus f (x) ⩾ ⋁ S⊆X f (e S ) ∧ ⋀ i∈S φ(x i ). To complete the proof, it is enough to establish the converse inequality. Let S * ⊆ X be such that f

(e S * ) ∧ ⋀ i∈S * φ(x i ) is maximum. Define T = {j ∈ X ∶ φ(x j ) ⩽ f (e S * ) ∧ ⋀ i∈S * φ(x i )}.
We claim that T ≠ ∅. Suppose this is not true, that is, φ(x j ) > f (e S * ) ∧⋀ i∈S * φ(x i ) for every j ∈ X. Then, by nondecreasing monotonicity, we have f (e X ) ⩾ f (e S * ), and since f (e

X ) ⩾ ⋀ i∈X φ(x i ), f (e X ) ∧ ⋀ i∈X φ(x i ) > f (e S * ) ∧ ⋀ i∈S * φ(x i )

Conclusion

In this paper we analyzed comonotonic modularity as a feature common to many well-known discrete integrals. In doing so, we established its relation to many other noteworthy aggregation properties such as comonotonic relaxations of additivity, maxitivity and minitivity. In fact, the latter become equivalent in presence of comonotonic modularity. As a by-product we immediately see that, e.g., the so-called discrete Shilkret integral lies outside the class of comonotonic modular functions since this integral is comonotonically maxitive but not comonotonically minitive.

Albeit such an example, the class of comonotonically modular functions is rather vast and includes several important extensions of the Choquet and Sugeno integrals. The results presented in Section 4 seem to indicate that suitable variants of homogeneity suffice to distinguish and fully describe these extensions. This naturally asks for an exhaustive study of homogeneity-like properties, which may lead to a complete classification of all subclasses of comonotonically modular functions.

Another question that still eludes us is the relation between the additive forms given by comonotonic modularity and the max-min forms. As shown in Theorem 20, the latter are particular instances of the former; in fact, proof of Theorem 20 provides a procedure to construct max-min representations of comonotonically modular functions, whenever they exist. However, we were not able to present a direct translation between the two. This remains as a relevant open question since its answer will inevitably provide a better understanding of the synergy between these intrinsically different normal forms.

Corollary 9 .

 9 Assume I = [a, b] ⊆ R. For any function f ∶ I n → R, the following assertions are equivalent.

Remark 3 .

 3 (i) Note that the expressions provided in Theorem 8 and Corollary 9 greatly differ from the additive form given in Theorem 7. (ii) An alternative description of comonotonic maxitive (resp. comonotonic minitive) functions was obtained in Grabisch et al. [12, Ch. 2].

Remark 4 .Theorem 11 .

 411 Condition (iii) of Theorem 10 is necessary. Indeed, the function f (x) = C v (x + ) satisfies conditions (i) and (ii) but fails to satisfy condition (iii).Assume I is centered at 0 with [-1, 1] ⊆ I. Then a function f ∶ I n → R is asymmetric signed Choquet integral if and only if the following conditions hold:(i) f is comonotonically modular.(ii) f (x1 S ) = x f (1 S ) for all x ∈ I and S ⊆ X.Proof. (Necessity) Assume that f is a symmetric signed Choquet integral, f = Čv . Then condition (ii) is satisfied in view of Theorem 6 and Remark 2. Let us now

4 . 2 .Definition 16 .

 4216 nonconstant and f (0) = 0. Then the following assertions are equivalent.(i) f is a symmetric signed quasi-Choquet integral and there exists S ⊆ X such that f (1 S ) ≠ 0. (ii) f is comonotonically modular and there exists a nondecreasing odd functionφ∶ I → R such that f (x1 S ) = φ(x) f (1 S )for every x ∈ I and every S ⊆ X. Remark 6. If I = [-1, 1], then the "nonconstant" assumption and the second condition in assertion (i) of Theorem 15 can be dropped off. Comonotonically modular integrals generalizing Sugeno integrals. In this subsection we consider natural extensions of the n-variable Sugeno integrals on a bounded real interval I = [a, b]. By an I-valued capacity on X we mean an order preserving mapping µ∶ 2 X → I such that µ(∅) = a and µ(X) = b. Assume that I = [a, b]. The Sugeno integral with respect to an I-valued capacity µ on X is the function S µ ∶ I n → I defined as

Proposition 17 .

 17 Assume that I = [a, b]. A function f ∶ I n → I is a Sugeno integral if and only if f (e ∅ ) = a, f (e X ) = b, and for every x ∈ I n f (x) = ⋁ S⊆X f (e S ) ∧ ⋀ i∈S x i .

Definition 18 .

 18 Assume that I = [a, b] and J = [c, d] are real intervals and let µ be an I-valued capacity on X. A quasi-Sugeno integral with respect to µ is a function f ∶ J n → I defined by f (x) = S µ (φ(x 1 ), . . . , φ(x n )), where φ∶ J → I is a nondecreasing function. Using Proposition 11 and Corollary 17 in [5], we obtain the following axiomatization of the class of quasi-Sugeno integrals. Theorem 19. Let I = [a, b] and J = [c, d] be real intervals and consider a function f ∶ J n → I. The following assertions are equivalent.

)

  Theorem 20. Let I = [a, b] and J = [c, d] be real intervals and consider a function f ∶ J n → I. The following conditions are equivalent.

Remark 8 .

 8 which contradicts the definition of S * . Thus T ≠ ∅. Now, by nondecreasing monotonicity and (13) we havef (x) ⩽ f (e X∖T ∨ ⋁ j∈T x j ) = f (e X∖T )∨φ( ⋁ j∈T x j ) = f (e X∖T )∨ ⋁ j∈T φ(x j ) = f (e X∖T ).Indeed, we have φ(x j ) ⩽ f (x) for every j ∈ T and x ⩽ e X∖T ∨ ⋁ j∈T x j .Note that f (e X∖T ) ⩽ f (e S * ) ∧ ⋀ i∈S * φ(x i ) since otherwise, by definition of T , we would havef (e X∖T ) ∧ ⋀ i∈X∖T φ(x i ) > f (e S * ) ∧ ⋀ i∈S * φ(x i ),again contradicting the definition of S * . Finally,f (x) ⩽ f (e S * ) ∧ ⋀ i∈S * φ(x i ) = ⋁ S⊆X f (e S ) ∧ ⋀ i∈S φ(x i ),and the proof is thus complete. An axiomatization of the class of Sugeno integrals based on comonotonic modularity can be obtained from Theorems 19 and 20 by adding the idempotency property.

Acknowledgments

This research is partly supported by the internal research project F1R-MTH-PUL-12RDO2 of the University of Luxembourg.


R L Goodstein

Miguel Couceiro
email: miguel.couceiro@uni.lu

Tam Ás Waldhauser

INTERPOLATION BY POLYNOMIAL FUNCTIONS OF DISTRIBUTIVE LATTICES: A GENERALIZATION OF A THEOREM OF

Keywords: 2010 Mathematics Subject Classification. Primary: 06D99; Secondary: 08A40, 06E99, 28B15, 90B50 distributive lattice, polynomial function, interpolation, disjunctive normal form, Sugeno integral

We consider the problem of interpolating functions partially defined over a distributive lattice, by means of lattice polynomial functions. Goodstein's theorem solves a particular instance of this interpolation problem on a distributive lattice L with least and greatest elements 0 and 1, resp.: Given a function f : {0, 1} n → L, there exists a lattice polynomial function p : L n → L such that p| {0,1} n = f if and only if f is monotone; in this case, the interpolating polynomial p is unique.

We extend Goodstein's theorem to a wider class of partial functions f : D → L over a distributive lattice L, not necessarily bounded, and where D ⊆ L n is allowed to range over n-dimensional rectangular boxes

and determine the class of such partial functions which can be interpolated by lattice polynomial functions. In this wider setting, interpolating polynomials are not necessarily unique; we provide explicit descriptions of all possible lattice polynomial functions which interpolate these partial functions, when such an interpolation is available.

Introduction

Let L be a distributive lattice and let f : D → L (D ⊆ L n ) be an n-ary partial function on L. In this paper we are interested in the problem of extending such partial functions to the whole domain L n by means of lattice polynomial functions, i.e., functions that can be represented as compositions of the lattice operations ∧ and ∨ and constants. More precisely, we aim at determining necessary and sufficient conditions on the partial function f that guarantee the existence of a lattice polynomial function p : L n → L which interpolates f , that is, p| D = f . An instance of this problem was considered by Goodstein [START_REF] Goodstein | The Solution of Equations in a Lattice[END_REF] in the case when L is a bounded distributive lattice, and the functions to be interpolated were of the form f : {0, 1} n → L. Goodstein showed that such a function f can be interpolated by lattice polynomial functions if and only if it is monotone. Furthermore, if such an interpolating polynomial function exists, then it is unique.

The general solution to the above mentioned interpolation problem eludes us. However, we are able to generalize Goodstein's result by allowing L to be an arbitrary (possibly unbounded) distributive lattice and considering functions f : D → L, where

D = {a 1 , b 1 } × • • • × {a n , b n } with a i , b i ∈ L and a i < b i .
More precisely, we furnish necessary and sufficient conditions for the existence of an interpolating polynomial function. As it will become clear, in this more general setting, uniqueness is not guaranteed, and thus we determine all possible interpolating polynomial functions.

The structure of the paper is as follows. In Section 2 we recall basic background on polynomial functions over distributive lattices (see [START_REF] Davey | Introduction to Lattices and Order[END_REF][START_REF] Grätzer | General Lattice Theory[END_REF]) and formalize the interpolation problem that we are interested in. In Section 3 we state and prove the characterization of those functions that can be interpolated by polynomial functions and we describe the set of all solutions of the interpolation problem. We discuss variations of the interpolation problem in Section 4 and relate our work to earlier results obtained for finite chains in [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF]. Finally, in Section 5 we consider potential applications of our results in mathematical modeling of decision making.

Preliminaries

Let L be a bounded distributive lattice with least element 0 and greatest element 1. It can be shown that a function p : L n → L is a lattice polynomial function if and only if there exist c I ∈ L(I ⊆ [n] := {1, . . . , n}) such that p can be represented in disjunctive normal form (DNF for short) by

(2.1) p(x) = I⊆[n] c I ∧ i∈I x i , for all x = (x 1 , . . . , x n ) ∈ L n .
It is easy to verify that taking c I = J⊆I c J , we also have

p(x) = I⊆[n] c I ∧ i∈I x i ,
and hence the coefficients c I can be assumed to be monotone in the sense that I ⊆ J implies c I ≤ c J . This monotonicity assumption allows us to recover the coefficients of the DNF from certain values of the polynomial function p. Indeed, denoting by 1 I the characteristic vector of I ⊆ [n] (i.e., the tuple

1 I ∈ L n whose i-th component is 1 if i ∈ I and 0 if i / ∈ I), we then have that p(1 I ) = c I .
Thus each polynomial function p has a unique DNF with monotone coefficients. We call such a DNF a maximal disjunctive normal form, as the coefficients of this DNF are the greatest among all DNF's representing the same polynomial function p (see [START_REF] Behrisch | Commuting polynomial operations of distributive lattices[END_REF]). In the sequel we will always consider lattice polynomial functions in maximal DNF. These observations contain the essence of Goodstein's theorem. Let us note that this result is implicit in the proof of [START_REF] Grätzer | Boolean functions on distributive lattices[END_REF]Corollary 2].

Theorem 2.1 (Goodstein [START_REF] Goodstein | The Solution of Equations in a Lattice[END_REF]). Let L be a bounded distributive lattice, and let f be a function f : {0, 1} n → L. There exists a polynomial function p over L such that p| {0,1} n = f if and only if f is monotone. In this case p is uniquely determined, and can be represented by the maximal DNF

p(x) = I⊆[n] f (1 I ) ∧ i∈I x i .
Remark 2.2. The notion dual to disjunctive normal form is that of conjunctive normal form. Every polynomial function over a bounded distributive lattice has a unique minimal conjunctive normal form whose coefficients satisfy

I ⊆ J =⇒ c I ≥ c J . The minimal conjunctive normal form of the polynomial function p in Theorem 2.1 is p(x) = I⊆[n] f (1 I ) ∨ i / ∈I x i .
Informally, Goodstein's theorem asserts that polynomial functions of distributive lattices are uniquely determined by their restrictions to the hypercube {0, 1} n , and a function on the hypercube extends to a polynomial function if and only if it is monotone.

Let us now consider a distributive lattice L without least and greatest elements. (We omit the analogous discussion of the cases where L has one boundary element.) Polynomial functions over L can still be given in DNF of the form (2.1) by allowing the coefficients c I to take also the values 0 and 1, which are considered as external boundary elements (see, e.g., [START_REF] Behrisch | Commuting polynomial operations of distributive lattices[END_REF][START_REF] Couceiro | Self-commuting lattice polynomial functions on chains[END_REF]). For example, a polynomial function p(x, y) = a ∨ x ∨ (b ∧ x ∧ y) can be rewritten as p(x, y)

= a ∨ (1 ∧ x) ∨ (0 ∧ y) ∨ (b ∧ x ∧ y).
We can still assume monotonicity of the coefficients, and any such system c I ∈ L ∪{0, 1}(I ⊆ [n]) of coefficients gives rise to a polynomial function p over L, provided that c ∅ = 1 and c [n] = 0. (The cases c ∅ = 1 and c [n] = 0 correspond to the constant 1 and constant 0 functions.) Again, such DNF's will be called maximal disjunctive normal forms. Just like in the case of bounded lattices, there is a one-to-one correspondence between maximal DNF's and polynomial functions (cf. [START_REF] Behrisch | Commuting polynomial operations of distributive lattices[END_REF]). To see this, let us choose elements a < b from L to play the role of 0 and 1, and let e I be the "characteristic vector" of I ⊆ [n] (i.e., the tuple e I ∈ L n whose i-th component is b if i ∈ I and a if i / ∈ I). If a is sufficiently small (less than all non-zero coefficients in the maximal DNF of p) and b is sufficiently large (greater than all non-one coefficients in the maximal DNF of p), then a routine computation shows that

p(e I ) =      c I if c I ∈ L, a if c I = 0, b if c I = 1.
This means that we can recover the coefficients c I of the maximal DNF of p from certain values of p, namely we need to consider p on larger and larger cubes {a, b} n by letting a decrease and b increase indefinitely. As the next example shows, this does not imply that there is only one polynomial function that takes prescribed values on a fixed cube {a, b} n .

Example 2.3. Let L be the lattice of open subsets of a topological space X, and let a, b ∈ L with a ⊂ b. Since L is a bounded distributive lattice, in view of (2.1), every unary polynomial function p over L can be represented by a unique maximal DNF of the form p

(x) = c 0 ∪ (c 1 ∩ x) with c 0 , c 1 ∈ L, c 0 ⊆ c 1 . It is straightforward to verify that such a polynomial function satisfies p(a) = p(b) = b if and only if b \ a ⊆ c 0 ⊆ b and b ⊆ c 1 ⊆ X.
Thus, there may be infinitely many polynomial functions p whose restriction to the "one-dimensional cube" {a, b} is constant b (for instance, let X be the real line, and let a and b be open intervals).

Let us go one step further, and choose a "zero" and "one", possibly different in each coordinate: Let a i , b i ∈ L with a i < b i for each i ∈ [n], and let e I be the "characteristic vector" of I ⊆ [n] (i.e., the tuple e

I ∈ L n whose i-th component is b i if i ∈ I and a i if i / ∈ I).
The task of finding a polynomial function (or rather all polynomial functions) that takes prescribed values on the tuples e I can be regarded as an interpolation problem. Note that here f is given on the vertices of a rectangular box (cuboid) instead of a cube as in Theorem 2.1. We will solve this problem in Section 3, thereby generalizing Goodstein's theorem. Let us note that the problem can be interesting also in the case of bounded lattices, for instance, if we do not have access to the values of the polynomial function on {0, 1} n , but only on some "internal" points. We will discuss such applications in Section 5.

Main results

Throughout this section we assume that L is a distributive lattice and that D = { e I : I ⊆ [n]} and f : D → L are given. Our goal is to find (the maximal DNF of) all n-ary polynomial functions p over L that satisfy p| D = f . Clearly, monotonicity of f is a necessary condition for the existence of a solution of Problem 2.4, but, in contrast with Goodstein's theorem, monotonicity is not always sufficient in this more general setting. We will prove that the extra condition that we need is the following:

( ) f ( e I∪{k} ) ∧ a k ≤ f ( e I ) ≤ f ( e I\{k} ) ∨ b k for all I ⊆ [n], k ∈ [n].
Observe that the first inequality holds obviously if k ∈ I, and the second inequality is also clear if k / ∈ I. Our first lemma shows how to obtain inequalities between f ( e S ) and f ( e T ) for S ⊆ T by repeated applications of ( ). Proof. We only prove the first inequality; the second one follows similarly. Let T \ S = {k 1 , . . . , k r }, and let us apply (the first inequality of) condition ( ) with

I = S ∪ {k 1 , . . . , k m-1 } and k = k m for m = 1, . . . , r: f ( e S∪{k1} ) ∧ a k1 ≤ f ( e S ), f ( e S∪{k1,k2} ) ∧ a k2 ≤ f ( e S∪{k1} ), . . . f ( e S∪{k1,...,kr} ) ∧ a kr ≤ f ( e S∪{k1,...,kr-1} ).
Combining these r inequalities, we get

f ( e S∪{k1,...,kr} ) ∧ a k1 ∧ • • • ∧ a kr ≤ f ( e S ).
Let us now show that ( ) is a necessary condition for the existence of a solution of Problem 2.4. Lemma 3.2. If there is a polynomial function p over L such that p| D = f , then f is monotone and satisfies ( ).

Proof. Assume that p is a polynomial function that extends f . Since p is monotone, f is also monotone. To show that ( ) holds, let us fix I ⊆ [n] and k ∈ [n], and let us assume that k / ∈ I (the case k ∈ I can be dealt with similarly). Let ( e I ) x k ∈ L n denote the n-tuple obtained from e I by replacing its k-th component by the variable x. We can define a unary polynomial function u over L by u(x) := p(( e I ) x k ). Using this notation, ( ) takes the form u(b k ) ∧ a k ≤ u(a k ). The maximal DNF of u is of the form u(x) = c 0 ∨ (c 1 ∧ x), where c 0 , c 1 ∈ L ∪ {0, 1}. Using distributivity and the fact that a k < b k , we can now easily prove the desired inequality:

u(b k ) ∧ a k = (c 0 ∨ (c 1 ∧ b k )) ∧ a k = (c 0 ∧ a k ) ∨ (c 1 ∧ b k ∧ a k ) = (c 0 ∧ a k ) ∨ (c 1 ∧ a k ) ≤ c 0 ∨ (c 1 ∧ a k ) = u(a k ).
To find all polynomial functions p satisfying p| D = f , we will make use of the the fact that every distributive lattice can be embedded into a Boolean algebra. Moreover, if L is a distributive lattice, then there is a Boolean algebra B(L) containing L as a sublattice of the lattice reduct of B(L) such that the boundary elements of L (if they exist) coincide with the boundary elements of B(L), and L generates B(L) (as a Boolean algebra). This Boolean algebra B(L) is determined uniquely up to isomorphism (see [START_REF] Peremans | Embedding of a distributive lattice into a Boolean algebra[END_REF]). Note that whenever we consider polynomial functions over B(L) in the sequel, we will always mean lattice polynomial functions (not Boolean algebra polynomial functions).

The complement of an element a ∈ B(L) is denoted by a . Given a function f : D → L, we define the following two elements in B(L) for each I ⊆ [n]:

(3.1) c - I := f ( e I ) ∧ i / ∈I a i , c + I := f ( e I ) ∨ i∈I b i .
Observe that c - I ≤ c + I , and if f is monotone, then I ⊆ J implies c - I ≤ c - J and c + I ≤ c + J . Let p -and p + be the lattice polynomial functions over B(L) that are represented by the (maximal) DNF's corresponding to these two systems of coefficients as in (2.1). We will see that p -and p + are the least and greatest lattice polynomial functions over B(L) whose restriction to D coincides with f (whenever there exists such a polynomial function). Recall that although B(L) is a Boolean algebra, we will only consider polynomial functions over the lattice reduct of B(L); complements will appear only in coefficients of DNF's of these lattice polynomials. Proof. Let us fix J ⊆ [n] and consider the value of p + at e J :

p + ( e J ) = I⊆[n] c + I ∧ j∈I ( e J ) j = I⊆[n] c + I ∧ j∈I\J a j ∧ j∈I∩J b j .
It is sufficient to verify that each joinand is at most f ( e J ). Taking into account the definition of c + I , this amounts to showing that (3.2)

f ( e I ) ∨ i∈I b i ∧ j∈I\J a j ∧ j∈I∩J b j ≤ f ( e J )
holds for all I ⊆ [n]. Distributing meets over joins, the left hand side of (3.2) becomes

(3.3) f ( e I ) ∧ j∈I\J a j ∧ j∈I∩J b j ∨ i∈I b i ∧ j∈I\J a j ∧ j∈I∩J b j .
Let us examine each joinand of this expression. For each i ∈ I, the joinand involving b i equals 0, since

b i ∧ j∈I\J a j ∧ j∈I∩J b j ≤ b i ∧ j∈I\J b j ∧ j∈I∩J b j = b i ∧ j∈I b j ≤ b i ∧ b i = 0.
The joinand of (3.3) that involves f ( e I ) can be estimated using ( ) and Lemma 3.1 (with T = I and S = I ∩ J):

f ( e I ) ∧ j∈I\J a j ∧ j∈I∩J b j ≤ f ( e I ) ∧ j∈I\(I∩J) a j ≤ f ( e I∩J ).
Since f is monotone, we have f ( e I∩J ) ≤ f ( e J ), and this proves (3.2).

The following lemma is the dual of Lemma 3.3, and it can be proved by using the minimal conjunctive normal form of p -(cf. Remark 2.2). The estimates obtained in the previous two lemmas allow us to find all solutions of our interpolation problem over B(L), whenever a solution exists. Theorem 3.5. Let L be a distributive lattice and let D = { e I : I ⊆ [n]} and f : D → L be given, as in Problem 2.4. Suppose that f is monotone and satisfies ( ), and let c - I and c + I be the coefficients computed from f as in (3.1), and let p -and p + be lattice polynomial functions over B(L) given by the DNF's corresponding to these coefficients. Furthermore, let p be an n-ary lattice polynomial function over B(L) given by a maximal DNF with coefficients c I ∈ B(L)(I ⊆ [n]). Then the following three conditions are equivalent:

(i) p| D = f ; (ii) for all I ⊆ [n] the inequalities c - I ≤ c I ≤ c + I hold; (iii) for all x ∈ L n we have p -(x) ≤ p(x) ≤ p + (x).
Proof. Implication (ii) =⇒ (iii) is trivial. To prove (i) =⇒ (ii), assume that p| D = f , i.e., p( e J ) = f ( e J ) for all J ⊆ [n]. Then we can replace f ( e J ) by p( e J ) in the definition of c - J , and we can compute its value by substituting e J into the maximal DNF of p:

c - J = f ( e J ) ∧ j / ∈J a j = p( e J ) ∧ j / ∈J a j = I⊆[n] c I ∧ i∈I ( e J ) i ∧ j / ∈J a j = I⊆[n] c I ∧ i∈I\J a i ∧ i∈I∩J b i ∧ j / ∈J a j .
If there exists i ∈ I \ J, then a i ∧ a i = 0 appears in the joinand corresponding to I, hence we can omit each of these terms from the join, and keep only those where

I \ J = ∅: c - J = I⊆J c I ∧ i∈I\J a i ∧ i∈I∩J b i ∧ j / ∈J a j ≤ I⊆J c I = c J .
This proves c - J ≤ c J . The inequality c J ≤ c + J can be proved by a dual argument. Finally, to prove (iii) =⇒ (i), let us assume that p -≤ p ≤ p + holds in the pointwise ordering of functions. Applying Lemma 3.3 and Lemma 3.4, we get the following chain of inequalities for every I ⊆ [n]:

f ( e I ) ≤ p -( e I ) ≤ p( e I ) ≤ p + ( e I ) ≤ f ( e I ).
This implies p( e I ) = f ( e I ) for all I ⊆ [n], therefore we have p| D = f . Note that in Lemma 3.2 we did not make use of the fact that p is a polynomial function over L: the proof works also for lattice polynomial functions over B(L). This fact together with Theorem 3.5 shows that monotonicity and property ( ) of f are necessary and sufficient for the existence of a solution of our interpolation problem over B(L) (regarded as a lattice). This observation leads us to the following result. Let us note that if L is bounded and a i = 0, b i = 1 for all i ∈ [n], then Theorem 3.6 reduces to Goodstein's theorem. Indeed, in this case ( ) holds trivially, hence a solution exists if and only if f is monotone. Moreover, we have c - I = c + I = f ( e I ), hence p 0 (which is the same as the polynomial function p given in Theorem 2.1) is the only solution of Problem 2.4.

Variations

We have seen that monotonicity and property ( ) are necessary and sufficient to guarantee the existence of a solution of Problem 2.4. The following example shows that these two conditions are independent, hence neither of them can be dropped. Considering lattice polynomial functions over B(L), Problem 2.4 has a least and a greatest solution, namely p -and p + , whenever a solution exists (see Theorem 3.5). On the other hand, the instance of Problem 2.4 considered in Example 2.3 has no least solution over L itself (since usually there is no least open set containing b \ a), and a dual example shows that in general there is no greatest solution over L. However, if L is complete, then such extremal solutions exist over L. To describe these, let us introduce the following notation. Completeness of L ensures that these (possibly infinite) meets and joins exist, and one can verify that cl is a closure operator on B(L) (the closed elements being exactly the elements of L), while int is the dual closure operator on B(L) (also called as "interior operator"). ). Problem 2.4 was solved in [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF] in the particular case of finite chains. That paper deals with Sugeno integrals (cf. Section 5) instead of lattice polynomials; here we reformulate the criterion for the existence of a solution ([13, Theorem 3]) in the language of lattice theory. Let us explore the relationship between Theorem 4.3 and Theorem 3.6. Our condition ( ) is defined only for sets D of the form D = { e I : I ⊆ [n]}, whereas (4.1) can be interpreted for any set D ⊆ L n for any distributive lattice L. Hence it is natural to ask whether Theorem 4.3 remains valid for arbitrary distributive lattices. As the following example shows, if L is not a chain, then it can be the case that (4.1) is neither sufficient nor necessary for the existence of a solution of Problem 2.4, not even for the special kind of sets D that we considered in this paper. Observe that if L is a chain, then (4.1) implies that f is monotone (of course, this follows from Theorem 4.3, but it is also easy to verify directly). As we have seen in Example 4.4, this is not true for arbitrary distributive lattices. Thus we may want to require that f is a monotone function satisfying (4.1). We will prove below that if D is of "rectangular" shape, then monotonicity of f and condition (4.1) are sufficient to ensure that f extends to a polynomial function (although (4.1) is not necessary, as we have seen in Example 4.4). Proof. Let f : D → L be a monotone function satisfying (4.1). By Theorem 3.6, we only have to prove that f also satisfies ( ). Let us assume that k / ∈ I; the other case is similar. Then only f ( e I∪{k} )∧a k ≤ f ( e I ) needs to be verified, as the second inequality of ( ) is trivial in this case. Since f is monotone, we have f ( e I ) ≤ f ( e I∪{k} ), and if equality holds here, then we are done. On the other hand, if f ( e I ) < f ( e I∪{k} ), then (4.1) implies that there is an i ∈

[n] such that (4.2) ( e I ) i ≤ f ( e I ) < f ( e I∪{k} ) ≤ ( e I∪{k} ) i .
This is clearly impossible for i = k, since then the i-th component of e I and e I∪{k} is the same. Thus we must have i = k, and then (4.2) reads as

a k ≤ f ( e I ) < f ( e I∪{k} ) ≤ b k .
From this we immediately obtain the desired inequality:

f ( e I∪{k} ) ∧ a k ≤ a k ≤ f ( e I ).
Finally, we give an example that shows that monotonicity and condition (4.1) together do not guarantee the existence of a solution of Problem 2.4 if L is an arbitrary distributive lattice and D is an arbitrary subset of L n . Thus it remains as a topic of further research to find an appropriate criterion for the existence of an interpolating lattice polynomial function in this general setting.

Example 4.6. Let L be the same lattice as in Example 4.4 (see Figure 1), and let D = {a, b}. Then the function f : D → L defined by f (a) = b, f (b) = a is monotone and satisfies (4.1), but it is not the restriction of a polynomial function. (This can be verified by a brute-force method, as there are only five nonconstant unary polynomial functions over L.)

Application in decision making

The original motivation for considering Problem 2.4 lies in the following mathematical model of multicriteria decision making. Let us assume that we have a set of alternatives from which we would like to choose the best one (e.g., a house to buy). Several properties of these alternatives could be important in making the decision (e.g., the size, price, etc., of a house), and this very fact can make the decision difficult (for instance, maybe it is not clear whether a cheap and small house is better than a big and expensive one). To overcome this difficulty, the values corresponding to the various properties of each alternative should be combined to a single value, which can then be easily compared.

To formalize this situation, let us assume that there are n criteria along which the alternatives are evaluated, and these take their values in linearly ordered sets L 1 , . . . , L n . These linearly ordered sets could be quantitative scales (e.g., L 1 could be the real interval [40,200], measuring the size of a house in square meters) or qualitative scales (e.g., L 1 could be the finite chain {very small < small < big < very big}). Thus, to each alternative corresponds a profile x ∈ L 1 × • • • × L n . Since this product is usually not a linearly ordered set, some alternatives may be incomparable. Therefore, we choose a common scale L, and monotone functions ϕ i : L i → L(i ∈ [n]) to translate general case is of interest not only to qualitative decision making, but it is also both natural and pertinent in the theory of distributive lattices. This constitutes a topic of current research being developed by the authors.

Problem 2 . 4 .

 24 Let L be a distributive lattice. Given D := { e I : I ⊆ [n]} and f : D → L, find all polynomial functions p : L n → L such that p| D = f .

Lemma 3 . 1 .

 31 If the function f satisfies ( ), then for all S ⊆ T ⊆ [n] we have f ( e T ) ∧ k∈T \S a k ≤ f ( e S ) and f ( e T ) ≤ f ( e S ) ∨ k∈T \S b k .

Lemma 3 . 3 .

 33 If f is monotone and satisfies ( ), then p + ( e J ) ≤ f ( e J ) for all J ⊆ [n].

Lemma 3 . 4 .

 34 If f is monotone and satisfies ( ), then p -( e J ) ≥ f ( e J ) for all J ⊆ [n].

Theorem 3 . 6 .

 36 Let L be a distributive lattice and let D = { e I : I ⊆ [n]} and f : D → L be given, as in Problem 2.4. Let c - I and c + I be the coefficients computed from f as in (3.1), and let p -and p + be the lattice polynomial functions over B(L) given by the DNF's corresponding to these coefficients. A polynomial function p : L n → L with p| D = f exists if and only if f is monotone and satisfies ( ). In this case a polynomial function p over L verifies p| D = f if and only if c - I ≤ c I ≤ c + I holds for coefficients c I ∈ L ∪ {0, 1} of the maximal DNF of p for all I ⊆ [n]. In particular, p can be chosen as the polynomial function p 0 given by the DNF corresponding to the coefficients c I = f ( e I ): p 0 (x) = I⊆[n] f ( e I ) ∧ i∈I x i . Proof. The necessity of the conditions has been established in Lemma 3.2. To prove the sufficiency, we just need to observe that if f is monotone and satisfies ( ), then the polynomial function p 0 is a solution of Problem 2.4 by Theorem 3.5, as c - I ≤ f ( e I ) ≤ c + I follows immediately from the definition of c - I and c + I . Since f ( e I ) ∈ L for all I ⊆ [n], the polynomial function p 0 is actually a polynomial function over L. The description of the set of all solutions over L also follows from Theorem 3.5.

Example 4 . 1 .

 41 Let L be a distributive lattice, let a, b, c ∈ L such that a < b < c, and let D = {a, b}. Then the function f : D → L defined by f (a) = b, f (b) = a satisfies ( ) but it is not monotone, while the function g : D → L defined by g(a) = a, g(b) = c is monotone but it does not satisfy ( ).

  For an arbitrary b ∈ B(L), we define the elements cl(b) and int(b) of L by cl(b) := a∈L a≥b a and int(b) := a∈L a≤b a.

Theorem 4 . 2 .

 42 Let L be a complete distributive lattice; let D = { e I : I ⊆ [n]} and f : D → L be given, as in Problem 2.4, and let us assume that f is monotone and satisfies ( ). Let c - I and c + I be the coefficients computed from f as in (3.1), and let p - and p + be the lattice polynomial functions over B(L) given by the DNF's corresponding to these coefficients. Then a polynomial function p over L is a solution of Problem 2.4 if and only if cl(c - I ) ≤ c I ≤ int(c + I ) holds for the coefficients c I of the maximal DNF of p, for all I ⊆ [n]. Proof. Theorem 4.2 follows directly from Theorem 3.6, since, by the very definition of cl and int, we have that c - I ≤ c I ≤ c + I holds for a given c I ∈ L if and only if cl(c - I ) ≤ c I ≤ int(c + I

Theorem 4 . 3 (

 43 [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF]). Let L be a finite chain, and let D be an arbitrary subset of L n . A function f : D → L extends to a lattice polynomial function on L if and only if

( 4 . 1 )

 41 ∀a, b ∈ D : f (a) < f (b) =⇒ ∃i ∈ [n] : a i ≤ f (a) < f (b) ≤ b i .

Example 4 . 4 .

 44 Let L = {0, 1, a, b} be the lattice shown on Figure1. Let n = 1 and D = {0, b}, and define f :D → L by f (0) = b, f (b) = a and g : D → L by g(0) = a, g(b) = 1.Then f trivially satisfies (4.1), but f is not monotone, hence it is not the restriction of any polynomial function. On the other hand, g does not satisfy (4.1), although it is the restriction of the polynomial function p(x) = x ∨ a to D.

Proposition 4 . 5 .

 45 Let L be a distributive lattice and D = { e I : I ⊆ [n]} as in Problem 2.4. If f : D → L is monotone and satisfies (4.1), then there exists a polynomial function p over L such that p| D = f .

0 a b 1 Figure 1 .

 11 Figure 1. The lattice L considered in Examples 4.4 and 4.6

Acknowledgments. The authors would like to thank Gábor Czédli for helpful discussions as well as the referees and the editor for their valuable comments that helped improving the paper.

The first named author is supported by the internal research project F1R-MTH-PUL-12RDO2 of the University of Luxembourg. The second named author acknowledges that the present project is supported by the T ÁMOP-4.2.1/B-09/1/KONV-2010-0005 program of the National Development Agency of Hungary, by the Hungarian National Foundation for Scientific Research under grants no. K77409 and K83219, by the National Research Fund of Luxembourg, and cofunded under the Marie Curie Actions of the European Commission (FP7-COFUND).

the values corresponding to the different criteria (which may have different units of measure, e.g., square meters, euros, etc.) to this common scale, and which are then combined into a single value (for each alternative) by a so-called aggregation function p : L n → L. In this way we obtain a function U : L 1 × • • • × L n → L defined by (5.1) U (x) = p(ϕ 1 (x 1 ), . . . , ϕ n (x n )), and we can choose the alternative that maximizes U . The function U is called a global utility function, whereas the maps ϕ i are called local utility functions. The relevance of such functions is attested by their several applications in decision making, in particular, in representing preference relations [START_REF]Decision-Making Process-Concepts and Methods[END_REF].

It is common to choose the real interval [0, 1] for L, and consider ϕ i (x i ) as a kind of "score" with respect to the i-th criterion. In this case, simple aggregation functions p are for instance the weighted arithmetic means, but there are of course other, more elaborate ways of aggregating the scores such as the so-called Choquet integrals. However, in the qualitative approach, where only the ordering between scores is taken into account (for instance, when L = {bad < OK < good < excellent}), such operators are of little use since they rely heavily on the arithmetic structure of the real unit interval. In the latter setting, one of the most prominent class of aggregation functions is that of discrete Sugeno integrals, which coincides with the class of idempotent lattice polynomial functions (see [START_REF] Marichal | Weighted lattice polynomials[END_REF]).

In [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] and [START_REF] Couceiro | Pseudo-polynomial functions over finite distributive lattices[END_REF] a more general situation was considered: L is an arbitrary finite distributive lattice, the lattice polynomial functions are not assumed to be idempotent, and the local utility functions are not assumed to be monotone (instead they have to satisfy the boundary conditions ϕ i (0 i ) ≤ ϕ i (x i ) ≤ ϕ i (1 i ) for all x i ∈ L i , where 0 i and 1 i denote the least and greatest element of L i ). The corresponding compositions (5.1) were called pseudo-polynomial functions, and several axiomatizations were given for this class of functions. Besides axiomatization, another noteworthy problem is the factorization of such functions: given a function U :

find all factorizations of U in the form (5.1). Such a factorization can be useful in real-life applications, when only the function U is available (from empirical observations), and an analysis of the behavior of the local utility functions ϕ i and of the aggregation function p could give valuable information about the decision maker's attitude.

Suppose that we have already found the local utility functions ϕ i (see [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF] and [START_REF] Couceiro | Pseudo-polynomial functions over finite distributive lattices[END_REF] for a method to find them), and let

. Thus, if we know the global utility function U , then we have information about p| D , and we can use Theorem 3.6 to find all possible lattice polynomial functions p that can appear in a factorization (5.1) of U . (Of course, one also has to take into account the other values of U , but this can be done by using the boundary conditions; see [START_REF] Couceiro | Pseudo-polynomial functions over finite distributive lattices[END_REF].)

The factorization procedure outlined above can be applied only if we have complete information about the global utility function U . However, in practical situations this is rarely the case: either U is not defined everywhere (e.g., there do not exist houses with all possible combinations of sizes, prices, etc.) or we do not know all of its values (e.g., the decision maker did not express his/her preferences about all the alternatives). This fact gives rise to the following problem. Problem 5.1. Let L 1 , . . . , L n be bounded posets and L a distributive lattice. Given

Considering polynomials instead of pseudo-polynomials we have the following analogous problem, which was already outlined in Section 1.

Problem 5.2. Let L be a distributive lattice. Given D ⊆ L n and f : D → L, find all polynomial functions p : L n → L such that p| D = f . As mentioned in Section 4, Problem 5.2 was solved in [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF] in the case of finite chains, which is the most common setting in the qualitative theory of decision making. The