key: cord-0044786-2nqdmunr
authors: Horanská, Ľubomíra
title: On Compatibility of Two Approaches to Generalization of the Lovász Extension Formula
date: 2020-05-15
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50143-3_33
sha: a71c772cbd63e255bc480a963bfb2ab4f655f595
doc_id: 44786
cord_uid: 2nqdmunr

We present a method of generalization of the Lovász extension formula combining two known approaches - the first of them based on the replacement of the product operator by some suitable binary function F and the second one based on the replacement of the minimum operator by a suitable aggregation function A. We propose generalization by simultaneous replacement of both product and minimum operators and investigate pairs (F, A) yielding an aggregation function for all capacities.

Aggregation of several values into a single value proves to be useful in many fields, e.g., multicriteria decision making, image processing, deep learning, fuzzy systems etc. Using the Choquet integral [3] as a mean of aggregation process allows to capture relations between aggregated data through so-called fuzzy measures [9] . This is the reason of the nowadays interest in generalizations of the Choquet integral, for a recent state-of-art see, e.g., [4] .

In our paper we focus on generalizations of the Choquet integral expressed by means of the so-called Möbius transform, which is also known as Lovász extension formula, see (2) below. Recently, two different approaches occured -in the first one the Lovász extension formula is modified by replacing of the product operator by some suitable binary function F and the second one is based on the replacement of the minimum operator by a suitable aggregation function A. We study the question, when these two approaches can be used simultaneously and we investigate the functional I m F,A obtained in this way. The paper is organized as follows. In the next section, some necessary preliminaries are given. In Sect. 3, we propose the new functional I m F,A and exemplify the instances, when the obtained functional is an aggregation function for all capacities and when it is not. Section 4 contains results concerning the binary case. Finally, some concluding remarks are given.

In this section we recall some definitions and results which will be used in the sequel. We also fix the notation, mostly according to [5] , wherein more information concerning the theory of aggregation functions can be found.

Let n ∈ N and N = {1, · · · , n}. We denote the class of all n-ary aggregations functions by A (n) . Möbius transform is invertible by means of the so-called Zeta transform:

for every A ⊆ N . Denote R n R the range of the Möbius transform. The bounds of the Möbius transform have recently been studied by Grabisch et al. in [6] . Then the Choquet integral of x with respect to m is given by

where the integral on the right-hand side is the Riemann integral. 

Formula (2) is also known as the Lovász extension formula [8] . Now we recall two approaches to generalization of the formula (2). The first one is due to Kolesárová et al. [7] and is based on replacing the minimum operator in (2) by some other aggregation function in the following way:

Let m ∈ M (n) be a capacity, A ∈ A (n) be an aggregation function. Define

where 

x i is the product copula, we obtain the well-known Owen multilinear extension (see [10] ).

The second approach occured recently in [2] and is based on replacing the product of M m (A) and minimum operator in the formula (2) by some function F : R × [0, 1] → R in the following way:

The authors focused on functions F yielding an aggregation function I F m for all capacities m ∈ M (n) .

It was shown in [2] that all functions F yielding for all m ∈ M (n) aggregation functions I F m with a given diagonal section δ ∈ A (1) are exactly those of the form

where h :

However, there is no full characterization of all functions F yielding an aggregation function I F m for every m ∈ M (n) in [2] .

where (

.

Consequently, one can consider F (0, 0) = 0 with no loss of generality (compare with Proposition 3.1 in [2] ). Let us define

Note that, according to Remark 1, the product operator Π(u, v) = uv is Icompatible with every copula. Next, according to Remark 2, all binary functions of the form (5) are I-compatible with A = min.

Clearly, it is a monotone function and I m F,A (1) = 1. Moreover, conjunctivity of A gives I m F,A (0) = 0. Thus, I m F,A is an aggregation function for all capacities m ∈ M (n) and therefore F is I-compatible with every conjunctive aggregation function A ∈ A (n) .

Example 2. Let f : [0, 1] → [0, 1] be a nondecreasing function such that f (0) = 0 and f (1) = 1, i.e., f ∈ A (1) . Let F (u, v) = (2 − 2 n )u + f (v). Then F is Icompatible with every disjunctive aggregation function A ∈ A (n) . Indeed, disjunctivity of A implies A(x B ) = 1 for all x ∈ [0, 1] n , ∅ = B N . Then, using (1), we obtain 

which is an aggregation function for all m ∈ M (2) , thus F is I-compatible with A. However, taking a disjunctive aggregation function in rôle of A, we obtain

which is not an aggregation function for all capacities up to the minimal one (a = b = 0). Hence, F is not I-compatible with any disjunctive aggregation function.

Let n = 2. Then the function I m F,A defined by (6) can be expressed as A(1, y) ) + F (1 − a − b, A(x, y) ).

Proposition 2. Let F ∈ F 0 , A ∈ A (2) . Then F is I-compatible with A iff the following conditions are satisfied (i) There exist constants k, κ ∈ R such that for any u ∈ R 2 = [−1, 1] it holds F (u, A(0, 1)) = F (u, A(1, 0)) = k(u − 1 2 ) F (u, 0) = ku, F (u, 1) = κu + 1−κ 3 .

(ii) For all x, x , y, y ∈ [0, 1] such that x ≤ x and y ≤ y it holds

Proof. It can easily be checked that conditions (i) ensure boundary conditions I m F,A (0, 0) = 0 and I m F,A (1, 1) = 1. To show necessity, let us consider the following equation:

for all a, b ∈ [0, 1]. Following techniques used for solving Pexider's equation (see [1] ), we can put a = 0 and b = 0 respectively, obtaining

Thus, for any t ∈ [0, 1], we have

Consequently

Therefore, formula (8) turns into

which is the Cauchy equation. Taking a = b = 0, we get ϕ(0) = 0. Therefore, putting a = t, b = −t, we get ϕ(t) = −ϕ(−t), i.e., ϕ is an odd function. Since we suppose F to be bounded on [0, 1] 2 , according to Aczél [1] , all solutions of the Eq. (11) on the interval [−1, 1] can be expressed as ϕ(t) = kt, for some k ∈ R. Therefore,

for all t ∈ [−1, 1], which for t = 0 gives f (0) = h(0). Denoting f (0) = c, by (9) and (10) we obtain

Since by assumption g(0) = F (0, 0) = 0, we have c = − k 2 and consequently,

for all t ∈ [−1, 1] as asserted.

The second boundary condition for I m F,A gives

for all a, b ∈ [0, 1]. Similarly as above, this equation can be transformed into the Cauchy equation (see also [2] ) having all solutions of the form ψ(t) = κt + 1−κ 3 , for κ ∈ R and t ∈ [−1, 1].

The conditions (ii) are equivalent to monotonicity of I m F,A , which completes the proof.

Considering aggregation functions satisfying A(0, 1) = A(1, 0) = 0 (e.g., all conjunctive aggregation functions are involved in this subclass), the conditions in Proposition 2 ensuring the boundary conditions of I m F,A can be simplified in the following way. (2) be an aggregation function with A(0, 1) = A(1, 0) = 0. Then the following holds:

Proof. We have F (u, A(0, 1)) = F (u, A(1, 0)) = F (u, 0) for all u ∈ R n . The conditions (i) in Proposition 2 yield k(u − 1 2 ) = ku, and consequently k = 0, thus F (u, 0) = 0 for all u ∈ R n as asserted.

Supposing that F is I-compatible with A and considering nondecreasingness of I m F,A in the first variable, we obtain A(0, 1)) − F (a, A(1, 1) ) + F (1 − a − b, A(0, 0) a − b, A(1, 0) 

for all a ∈ [0, 1].

Hence,

for all u ∈ [0, 1] and consequently − 1 2 ≤ κ ≤ 1, which completes the proof.

Considering aggregation functions satisfying A(0, 1) = A(1, 0) = 1 (e.g., all disjunctive aggregation functions are involved in this subclass), the conditions in Proposition 2 ensuring the boundary conditions of I m F,A can be simplified in the following way. (2) be an aggregation function with A(0, 1) = A(1, 0) = 1. Then the following holds: 

We have introduced a new functional I m F,A generalizing the Lovász extension formula (or the Choquet integral expressed in terms of Möbius transform) using simultaneously two known approaches. We have investigated when the obtained functional is an aggregation function for all capacities and exemplified positive and negative instances. In case of the binary functional we have found a characterization of all pairs (F, A) which are I-compatible, i.e., yielding an aggregation function I m F,A for all capacities m. In our future reasearch we will focus on the characterization of all I-compatible pairs (F, A) in general n-ary case. Another interesting unsolved problem is the problem of giving back capacity, i.e., characterization of pairs (F, A) satisfying I m F,A (1 E ) = m(E) for all E ⊆ N .

Lectures on Functional Equations and Their Applications

A generalization of the Choquet integral defined in terms of the Möbius transform

Theory of capacities

The state-of-art of the generalizations of the Choquet integral: from aggregation and pre-aggregation to ordered directionally monotone functions

Exact bounds of the Möbius inverse of monotone set functions

Aggregation-based extensions of fuzzy measures

Mathematical Programming: The State of the Art

Non-monotonic fuzzy measures and the Choquet integral

Multilinear extensions of games

Acknowledgments. The support of the grant VEGA 1/0614/18 and VEGA 1/0545/20 is kindly acknowledged.