Miguel Couceiro

Didier Dubois

Henri Prade

Tamas Waldhauser

Tamas Waldhauser Decision-Making With Sugeno

Decision-making with Sugeno integrals: DMU vs. MCDM

Decision-making with Sugeno integrals: DMU vs. MCDM Miguel Couceiro 1 and Didier Dubois 2 and Henri Prade 3 and Tamás Waldhauser 4 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. 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 monotonic set-functions, respectively. This is achieved by weakening previously proposed axiom systems for Sugeno integrals.

MOTIVATION

Two important chapters of decision theory are decision under uncertainty and multicriteria evaluation [START_REF]Decision-Making Process -Concepts and Methods[END_REF]. 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 [START_REF] Keeney | Decisions with Multiple Objectives: Preferences and Value Tradeoffs[END_REF]. On the other hand, the structure of the two problems is very similar, see, e.g., [START_REF] Dubois | Relating decision under uncertainty and multicriteria decision making models[END_REF][START_REF] Dubois | The Use of the Discrete Sugeno Integral in Decision-Making: a Survey[END_REF]. Decision-making under uncertainty (DMU), after Savage [START_REF] Savage | The Foundations of Statistics[END_REF], 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 1 University of Luxembourg, Luxembourg, email: miguel.couceiro@uni.lu 2 IRIT -Université Paul Sabatier, France, email: Dubois@irit.fr 3 IRIT -Université Paul Sabatier, France, email: Prade@irit.fr 4 University of Szeged, Hungary, email: twaldha@math.u-szeged.hu 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 clear: the literature is basically numerical, but many methods are inspired by voting theory; see [START_REF] Bouyssou | Social choice theory and multicriteria decision aiding In[END_REF].

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 [START_REF] Doyle | Background to qualitative decision theory[END_REF]). 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 CPnets, see [START_REF] Boutilier | CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF]) 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 qualitiative 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 [START_REF] Dubois | Decision theoretic foundations of qualitative possibility theory[END_REF], and assuming a more general representation of uncertainty [START_REF] Dubois | Qualitative decision theory with Sugeno integrals[END_REF]. The same aggregation functions have been used in [START_REF] Marichal | On Sugeno integral as an aggregation function[END_REF] in the scope of MCDM, and applied in [START_REF] Prade | Elicitating Sugeno Integrals: Methodology and a Case Study[END_REF] 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 attribute domains, 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 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. However there is no increase of expressive power in the case of possibility theory. Proofs are omitted due to space limitations.

In this section, we recall basic background and present some preliminary results needed throughout the paper. For introduction on lattice theory see [START_REF] Rudeanu | Lattice Functions and Equations[END_REF].

Preliminaries

Throughout this paper, let Y be a finite chain endowed with lattice operations ∧ and ∨, and with least and greatest elements 0Y and 1Y , respectively; the subscripts may be omitted when the underlying lattice is clear from the context; [n] is short for {1, . . . , n} ⊂ N. Let f : X → Y be a function. The range of f is given by ran(f ) = {f (x) : x ∈ X}. Also, f is said to be order-preserving if, for every a, b ∈ ∏ i∈ [n] Xi such that a ≤ b, we have f (a) ≤ f (b). A well-known example of an order-preserving function is the median function med :

Given finite chains

Y 3 → Y given by med(x1, x2, x3) = (x1 ∧ x2) ∨ (x1 ∧ x3) ∨ (x2 ∧ x3).

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., [START_REF] Davey | Introduction to Lattices and Order[END_REF][START_REF] Grätzer | General Lattice Theory[END_REF].

Recall that a (lattice) polynomial function on Y is any map p : Y n → Y which can be obtained as a composition of the lattice operations ∧ and ∨, the projections x → xi and the constant functions x → c, c ∈ Y .

As shown by Goodstein [START_REF] Goodstein | The Solution of Equations in a Lattice[END_REF], polynomial functions over bounded distributive lattices (in particular, over bounded chains) have very neat normal form representations. For I ⊆ [n], let 1I be the characteristic vector of I, i.e., the n-tuple in Y n whose i-th component is 1 if i ∈ I, and 0 otherwise.

Theorem 1. A function is a polynomial function if and only if

p(x1, . . . , xn) = ∨ I⊆[n] ( p(1I ) ∧ ∧ i∈I xi ) . ( 1
)
Equivalently, p : Y n → Y is a polynomial function if and only if p(x1, . . . , xn) = ∧ I⊆[n] ( p(1 [n]\I ) ∨ ∨ i∈I xi ) .
Remark 1. Observe that, by Theorem 1, every polynomial function p : Y n → 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(eI ) ≤ p(eJ ) whenever I ⊆ J. Moreover, a function f : {0, 1} n → Y can be extended to a polynomial function over Y if and only if it is orderpreserving.

Polynomial functions are known to generalize certain prominent fuzzy integrals, namely, so-called Sugeno integrals. A fuzzy measure on [n] is a mapping µ :

P([n]) → Y which is order-preserving (i.e., if A ⊆ B ⊆ [n], then µ(A) ≤ µ(B)
) and satisfies µ(∅) = 0 and µ([n]) = 1; such functions qualify to represent uncertainty.

The Sugeno integral associated with the fuzzy measure µ is the function qµ :

Y n → Y defined by qµ(x1, . . . , xn) = ∨ I⊆[n] ( µ(I) ∧ ∧ i∈I xi ) . ( 2
)
For further background see, e.g., [START_REF] Grabisch | Aggregation Functions[END_REF][START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF][START_REF] Sugeno | Fuzzy measures and fuzzy integrals-a survey[END_REF].

Remark 2.
As observed in [START_REF] Marichal | On Sugeno integral as an aggregation function[END_REF][START_REF] Marichal | Weighted Lattice Polynomials[END_REF], Sugeno integrals coincide exactly with those polynomial functions q : Y n → Y which are idempotent, that is, which satisfy q(c, . . . , c) = c, for every c ∈ Y . In fact, by (1) it suffices to verify this identity for c ∈ {0, 1}, that is,

q(1 [n] ) = 1 and q(1 ∅ ) = 0.
Remark 3. Note also that the range of a Sugeno integral q : Y n → Y is ran(q) = Y . Moreover, by defining µ(I) = q(1I ), we get q = qµ.

In the sequel, we shall be particularly interested in the following types of fuzzy measures. A fuzzy measure µ is called a possibility measure (resp. necessity measure) if for every

A, B ⊆ [n], µ(A ∪ B) = µ(A) ∨ µ(B) (resp. µ(A ∩ B) = µ(A) ∧ µ(B)).
Remark 4. In the finite setting, a possibility measure is completely characterized by the value of µ on singletons, namely

µ(i), i ∈ [n] (called a possibility distribution), since clearly, µ(A) = ∨i∈Aµ(i).
Likewise, a necessity measure is completely characterized by the value of µ on sets of the form Ni =

[n] \ {i} since clearly, µ(A) = ∧ i ∈A µ(Ni)
Note that if µ is a possibility measure [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] (resp. necessity measure [START_REF] Dubois | Possibility theory[END_REF]), then qµ is a weighted disjunction [START_REF] Dubois | Weighted minimum and maximum operations in fuzzy set theory[END_REF] (where µ(i), a shorthand notation for µ({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).

∨ i∈I µ(i) ∧ xi (resp. weighted conjunction µ(I)∧ ∧ i∈I xi)) for some I ⊆ [n]
Polynomial functions and Sugeno integrals have been characterized by several authors, and in the more general setting of distributive lattices see, e.g., [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] Grabisch | Aggregation Functions[END_REF].

The following characterization in terms of median decomposability will be instrumental in this paper. A function p :

Y n → Y is said to be median decomposable if for every x ∈ Y n , p(x) = med ( p(x 0 k ), x k , p(x 1 k ) ) (k = 1, . . . , n).
ϕi : Xi → Y , i ∈ [n], such that f (x) = q(ϕ1(x1), . . . , ϕn(xn)).
(

) 3
Note that Sugeno utility functionals are order-preserving.

Remark 5. (i) In [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functionals[END_REF] it was shown that the set of functions obtained by composing lattice polynomials with local utility functions is the same as the set of Sugeno utility functionals. (ii) In [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functionals[END_REF] and [START_REF] Couceiro | Pseudo-polynomial functions over finite distributive lattices[END_REF] a more general setting was considered, where the inner functions ϕi : Xi → Y , i ∈ [n], were only required to satisfy the so-called "boundary conditions": for every

x ∈ Xi, ϕi(0) ≤ ϕi(x) ≤ ϕi(1) or ϕi(1) ≤ ϕi(x) ≤ ϕi(0). ( 4
)
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. (iii) Note that pseudo-polynomial functions are not necessarily orderpreserving, 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 [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functionals[END_REF].

Sugeno utility functionals can be axiomatized in complete analogy with polynomial functions by extending the notion of median decomposability. We say that f :

X → Y is pseudo-median decomposable if for each k ∈ [n] there is a local utility function ϕ k : X k → Y such that f (x) = med ( f (x 0 k ), ϕ k (x k ), f (x 1 k ) ) (5)
for every x ∈ X.

Theorem 3 ([13]

). A function f : X → Y a Sugeno utility functional if and only if f is pseudo-median decomposable.

Remark 6. In [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functionals[END_REF] and [START_REF] Couceiro | Pseudo-polynomial functions over finite distributive lattices[END_REF] a more general notion of pseudomedian decomposability was considered where the inner functions ϕi : Xi → Y , i ∈ [n], were only required to satisfy the boundary conditions.

Note that once the local utility functions ϕi : Xi → Y (i ∈ [n]) are given, the pseudo-median decomposability formula (5) provides a disjunctive normal form of a polynomial function p0 which can be used to factorize f . To this extent, let 1I denote the characteristic vector of I ⊆ [n] in X, i.e., 1I ∈ X is the n-tuple whose i-th component is 1X i if i ∈ I, and 0X i otherwise. ϕn), where the polynomial function p0 is given by

Theorem 4 ([14]). If f : X → Y is pseudo-median decompos- able w.r.t. local utility functions ϕ k : X k → Y (k ∈ [n]), then f = p0(ϕ1, . . . ,
p0 (y1, . . . , yn) = ∨ I⊆[n] ( f ( 1I ) ∧ ∧ i∈I yi ) . ( 6
)
This result naturally asks for a procedure to obtain local utility functions ϕi : Xi → Y (i ∈ [n]) which can be used to factorize a given Sugeno utility functional f : X → Y into a composition (3). In the more general setting of pseudo-polynomial functions, such procedures were presented in [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functionals[END_REF] when Y is an arbitrary chain, and in [START_REF] Couceiro | Pseudo-polynomial functions over finite distributive lattices[END_REF] when Y is a finite distributive lattice.

The following result provides a noteworthy axiomatization of Sugeno utility functionals which follows as a corollary of Theorem 19 in [START_REF] Couceiro | Pseudo-polynomial functions over finite distributive lattices[END_REF].

Theorem 5. A function f : X → Y is a Sugeno utility functional if and only if it is order-preserving and satisfies

f ( x 0 k ) < f (x a k ) and f (y a k ) < f ( y 1 k ) =⇒ f (x a k ) ≤ f (y a k ) for all x, y ∈ X and k ∈ [n], a ∈ X k .
Let us interpret this result in terms of multicriteria evaluation. Consider alternatives x and y such that

x k = y k = a. Then f ( x 0 k ) < f (x)
means that down-grading attribute k makes the corresponding alternative x 0 k strictly worse than x. Similarly, f (y

) < f ( y 1 k )
means that upgrading attribute k makes the corresponding alternative y 1 k strictly better than y. This behavior is due to a noncompensatory property of qualitative aggregation operators, which here takes the form of pseudo-median decomposibility. Indeed what this property expresses is that the value of x is either x 0 k , or x 1 k or x k . In such a situation, given another alternative y such that

y k = x k = a : f ( x 0 k ) < f (x) = med ( f (x 0 k ), ϕ k (a), f (x 1 k ) ) = ϕ k (a) ∧ f (x 1 k ) ≤ ϕ k (a), f ( y 1 k ) > f (y) = med ( f (y 0 k ), ϕ k (a), f (y 1 k ) ) = ϕ k (a) ∨ f (y 0 k ) ≥ ϕ k (a),
and so f (x) ≤ ϕ k (a) ≤ f (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) that the rating on attribute k. It also means that either attribute k can affect the value of y positively or it can affect it negatively, but not both. We shall further discuss these 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 Xi into a single scale Y in order to make the scales Xi commensurate. In other words, a Sugeno integral (7) cannot be defined if there is no common scale X such that Xi ⊆ X, for every i ∈ [n]. In particular, the situation in decision under uncertainty is precisely that where Xi = X, for every i ∈ [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 ϕi = ϕ, for every i ∈ [n], namely, a unique utility function is at work. In this sense, the Sugeno utility functional becomes a simple Sugeno integral of the form qµ(y1, . . . , yn) =

∨ I⊆[n] ( µ(I) ∧ ∧ i∈I yi ) . ( 7
)
where Y = ϕ(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 ϕ that equips X with a total order:

xi ≤ xj ⇐⇒ ϕ(xi) ≤ ϕ(xj).
The general case studied here corresponds to that of DMU but where the local utility functions ϕi : X → Y are state-dependent; this situation was already considered in the literature of expected utility theory [START_REF] Schervish | State-Dependent Utilities[END_REF], here adapted to the qualitative setting. Namely, an act is of the form x ∈ X n where the consequences xi of the act performed in state i belong to the same set X, and the evaluation of x is of the form (3), i.e. they are not evaluated in the same way in each state.

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.

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 = ∏ i∈ [n] Xi is a relation ⊆ X 2 that is reflexive, transitive, and complete (∀x, y ∈ X : x y or y x). Like quasi-orders (i.e., reflexive and transitive relations), weak orders do not necessarily satisfy the antisymmetry condition:

∀x, y ∈ X : x y, y x =⇒ x = y (AS)
This fact gives rise to an "indifference" relation which we denote by ∼, and which is defined by y ∼ x if x y and y x. Clearly, ∼ is an equivalence relation. Moreover, the quotient relation / ∼ satisfies (AS); in other words, / ∼ is a complete linear order (chain).

For notational ease, we shall denote / ∼ by ≤. By a preference relation on X we mean a weak order which satisfies the Pareto condition: ∀x, y ∈ X : x ≤ y =⇒ x y.

(P)

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 [START_REF]Decision-Making Process -Concepts and Methods[END_REF][START_REF] Grabisch | The application of fuzzy integrals in multicriteria decision making[END_REF] (for general background on aggregation functions, see [START_REF] Grabisch | Aggregation Functions[END_REF][START_REF] Beliakov | Aggregation Functions: A Guide for Practitioners[END_REF]).

In this approach, a relation on a set X = ∏ i∈ [n] Xi is represented by a so-called global utility function U (i.e., an orderpreserving mapping which assigns to each event in X an overall score in a possibly different scale Y ), under the rule: x y if and only if U (x) ≤ U (y). Such a relation is clearly a preference relation.

Conversely, if is a preference relation, then the canonical surjection r : X → X/ ∼, also referred to as the rank function of , is an order-preserving map from X to X/ ∼ (linearly ordered by ≤), and we have x y ⇐⇒ r (x) ≤ r (y). Thus, is represented by an order-preserving function if and only if it is a preference relation, and in this case is represented by r.

Axioms pertaining to preference modelling

In this subsection we recall some properties of relations used in the axiomatic approach discussed in [START_REF] Dubois | The Use of the Discrete Sugeno Integral in Decision-Making: a Survey[END_REF][START_REF] Dubois | Qualitative decision theory with Sugeno integrals[END_REF]; 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 ∈ X and A ⊆ [n], let xAy denote the tuple in X whose i-th component is xi if i ∈ A and yi otherwise. 0 and 1 denote the bottom and the top of X respectively.

We consider the following axioms. The optimism axiom

∀x, y ∈ X, ∀A ⊆ [n] : xAy ≺ x =⇒ x yAx, (OPT)
which subsumes 5 two instances of interest, namely,

∀x ∈ X, ∀A ⊆ [n] : xA0 ≺ x =⇒ x 0Ax, (OPT ) ∀x, y ∈ X, k ∈ [n] , a ∈ X k : x 0 k ≺ x a k =⇒ x a k y a k . (OPT1)
Note that under (P) the conclusion of (OPT ) is equivalent to x ∼ 0Ax. Similarly, the conclusion of (OPT1) could be replaced by x a k ∼ 0 a k . The name optimism is justified considering the case where X = 1 and Y = 0. Then (OPT) reads A c ≺ [n] implies A

[n] (full trust in A or A c , an optimistic approach to uncertainty).

Dual to optimism we have the pessimism axiom

∀x, y ∈ X, ∀A ⊆ [n] : xAy x =⇒ x yAx, (PESS)
which subsumes the two dual instances

∀x ∈ X, ∀A ⊆ [n] : xA1 x =⇒ x 1Ax, (PESS ) ∀x, y ∈ X, k ∈ [n] , a ∈ X k : x 1 k x a k =⇒ x a k y a k . (PESS1)
Again, under (P), the conclusions of (PESS ) and (PESS1) are equivalent to x ∼ 1Ax and x a k ∼ 1 a k , respectively. When X = 0 and Y = 1, (PESS) reads A c ∅ implies ∅ A (full distrust in A or A c , a pessimistic approach to uncertainty).

We will also consider the disjunctive and conjunctive axioms

∀y, z ∈ X : y ∨ z ∼ y or y ∨ z ∼ z, (∨) ∀y, z ∈ X : y ∧ z ∼ y or y ∧ z ∼ z. (∧)
Moreover, we have the so-called disjunctive dominance and strict disjunctive dominance Dually, we have the following result which establishes the pairwise equivalence between the remaining axioms.

∀x, y, z ∈ X : x y, x z =⇒ x y ∨ z, (DD ) ∀x, y, z ∈ X : x y, x z =⇒ x y ∨ z, (DD )
Theorem 7. If is a preference relation, then axioms (PESS), (PESS ), (PESS1), (∧), (CD ) and (CD ) are pairwise equivalent.

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 10). More precisely, we first obtain an axiomatization of relations represented by Sugeno utility functionals associated with possibility measures (weighted disjunction of utility functions). It is easy to see that µ is not a possibility measure, but the preference relation on X1 × X2 represented by f := qµ(ϕ1, ϕ2) clearly satisfies (∨), since (0, 0) ∼ (1, 0) ≺ (0, 1) ∼ (1, 1) . On the other hand, the same relation can be represented by the second projection (x1, x2) → x2 on {0, 1}6 , which is in fact a Sugeno integral with respect to a possibility measure satisfying 0 = µ(∅) = µ({1}) and µ({2}) = µ({1, 2}) = 1.

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

DMU vs. MCDM

In [START_REF] Dubois | Qualitative decision theory with Sugeno integrals[END_REF], Dubois, Prade and Sabbadin, considered the qualitative setting under uncertainty, and axiomatized those preference relations on X = X n that can be represented by special (state-independent) Sugeno utility functionals f : X → Y of the form

f (x) = p(ϕ(x1), . . . , ϕ(xn)), (9)
where p : Y n → Y is a polynomial function (or, equivalently, a Sugeno integral; see, e.g., [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]), and ϕ : X → Y is a utility function. To get it, two additional axioms (more stringent than (DD ) and (CD )) were considered, namely, the so-called restrictive disjunctive dominance and restrictive conjunctive dominance:

∀x, y, c ∈ X : x y, x c =⇒ x y ∨ c, (RDD) ∀x, y, c ∈ X : y x, c x =⇒ y ∧ c x, (RCD)
where c is a constant tuple.

Theorem 11 (In [START_REF] Dubois | Qualitative decision theory with Sugeno integrals[END_REF]). A preference relation on X = X n can be represented by a state-independent Sugeno utility functional [START_REF] Couceiro | Axiomatizations of Quasi-Polynomial Functions on Bounded Chains[END_REF] if and only if it satisfies (RDD) and (RCD).

Clearly, ( 9) is a particular form of (3), and thus every preference relation on X = X n which is representable by ( 9) is also representable by a Sugeno utility functional [START_REF] Boutilier | CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF]. In other words, we have that (RDD) and (RCD) imply condition [START_REF] Couceiro | Representations and Characterizations of Polynomial Functions on Chains[END_REF]. However, as the following example shows, the converse is not true. In the case of preference relations induced by possibility and necessity measures, Dubois, Prade and Sabbadin [START_REF] Dubois | Decision theoretic foundations of qualitative possibility theory[END_REF] obtained the following axiomatizations.

Theorem 13 (In [START_REF] Dubois | Decision theoretic foundations of qualitative possibility theory[END_REF]). Let be a preference relation on X = X n . Then the following assertions hold.

(i)

satisfies (OPT) and (RDD) if and only if there exist a utility function ϕ and a possibility measure µ, such that is represented by the Sugeno utility functional f = qµ(ϕ, . . . , ϕ). (ii) satisfies (PESS) and (RCD) if and only if there exist a utility function ϕ and a necessity measure µ, such that is represented by the Sugeno utility functional f = qµ(ϕ, . . . , ϕ). Again, every preference relation which is representable as in (i) or (ii) of Theorem 13, is representable as in Theorems 8 and 9, respectively. Surprisingly and unlike the comparison of those models arising from (3) and( 9) (where the latter was shown to be strictly subsumed by the former), every preference relation which is representable as in Theorems 8 and 9 (when X = X n ) is representable as in (i) or (ii) of Theorem 13, respectively.

To see this, suppose that is representable by a Sugeno utility functional f = qµ(ϕ1, . . . , ϕn), where ϕi : X → Y and µ is a possibility measure. Note that f (x) = ∨ i∈I µ({i}) ∧ ϕi(xi), for some I ⊆ [n]. We claim that satisfies (RDD); by Theorem 8, satisfies (OPT) (or, equivalently, all of the axioms in Theorem 6).

So let x, y, c ∈ X such that x y and x c, i.e., f (x) > f (y) and f (x) > f (c). Since Y is a chain, f (x) > f (y) ∨ f (c). Hence f (x) > f (y ∨ c), which shows that x y ∨ c. Dually, we can show that if is representable by a Sugeno utility functional f = qµ(ϕ1, . . . , ϕn), where ϕi : X → Y and µ is a necessity measure, then satisfies (RCD) and, by Theorem 9, satisfies (OPT) (or, equivalently, all of the axioms in Theorem 7).

In view of Theorem 13, we have just proved the following result which basically states that the DMU and MCDM settings have the same expressive power w.r.t. possibility and necessity measures. Theorem 14. Let be a preference relation on X = X n . Then the following assertions hold.

(i)

is represented by a Sugeno utility functional f = qµ(ϕ1, . . . , ϕn) for a possibility measure µ and utility functions ϕi if and only if there exist a utility function ϕ and a possibility measure µ , such that is represented by f = q µ (ϕ, . . . , ϕ).

(i)
is represented by a Sugeno utility functional f = qµ(ϕ1, . . . , ϕn) for a necessity measure µ and utility functions ϕi if and only if there exist a utility function ϕ and a necessity measure µ , such that is represented by f = q µ (ϕ, . . . , ϕ).

To obtain function ϕ from ϕ1, . . . , ϕn, we can use ϕ(x) = f (x, ..., x) = ∨ i∈I µ({i}) ∧ ϕi(x) [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].

CONCLUDING REMARKS

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. However , the fact that MCDM and DMU have the same expressive power when possibility and necessity measures are used should facilitate the transposition of the possibilistic logic counterpart of qualitative DMU [START_REF] Dubois | Logical representation and computation of optimal decisions in a qualitative setting[END_REF] to MCDM.

  as well as their dual counterparts, conjunctive dominance and strict conjunctive dominance, ∀x, y, z ∈ X : y x, z x =⇒ y ∧ z x, (CD ) ∀x, y, z ∈ X : y x, z x =⇒ y ∧ z x. (CD ) Theorem 6. If is a preference relation, then axioms (OPT), (OPT ), (OPT1), (∨), (DD ) and (DD ) are pairwise equivalent.

Theorem 8 .

 8 A preference relation satisfies one(or, equivalently, all) of the axioms in Theorem 6 if and only if there are local utility functions ϕi, i ∈ [n], and a possibility measure µ, such that is represented by the Sugeno utility functional f = qµ(ϕ1, . . . , ϕn). Remark 7. Note that the above theorem does not state that every Sugeno utility functional representing a preference relation that satisfies the conditions of Theorem 6 corresponds to a possibility measure. As an example, consider the case n = 2 with X1 = X2 = {0, 1} and Y = {0, a, b, 1}, where 0 < a < b < 1. Let us define local utility functions ϕi : Xi → Y (i = 1, 2) by ϕ1 (0) = 0, ϕ1 (1) = b, ϕ2 (0) = a, ϕ2 (1) = 1, and let µ be the fuzzy measure on {1, 2} given by µ (∅) = 0, µ ({1}) = a, µ ({2}) = b, µ ({1, 2}) = 1.

Example 12 .

 12 Let X = {1, 2, 3} = Y endowed with the natural ordering of integers, and the consider the preference relation on 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 x = (2, 3), y = (1, 3) and c = (2, 2) (similarly, it does not satisfy (RCD)), and thus it cannot be represented by a Sugeno utility functional[START_REF] Couceiro | Axiomatizations of Quasi-Polynomial Functions on Bounded Chains[END_REF]. However, withq(x1, x2) = (2 ∧ x1) ∨ (2 ∧ x2) ∨ (3 ∧ x1 ∧ x2),and ϕ1 = {(3, 3),[START_REF] Benvenuti | Monotone set functions-based integrals[END_REF][START_REF] Boutilier | CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF], (1, 1)} and ϕ2 = {(3, 3), (2, 1), (1, 1)}, we have that is represented by the Sugeno utility functional f (x1, x2) = q(ϕ1(x1), ϕ2(x2)).

  As observed, f (x) = ∨ i∈I µ({i}) ∧ ϕi(xi), and thusf (y) ∨ f (c) = ( ∨ i∈I µ({i}) ∧ ϕi(yi) ) ∨ ϕi(c) ) = f (y ∨ c).

  In particular, a ≤ b if and only if ai ≤ bi for every i ∈[n]. For k ∈ [n] and c ∈ X k , we use x ck to denote the tuple whose i-th component is c, if i = k, and xi, otherwise.

	∏	Xi, i ∈ [n], their Cartesian product X = i∈[n] Xi constitutes a bounded distributive lattice by defining
	a∧b = (a1 ∧b1, . . . , an ∧bn), and a∨b = (a1 ∨b1, . . . , an ∨bn).

  Theorem 9. A preference relation satisfies one (or, equivalently, all) of the axioms in Theorem 7 if and only if there are local utility functions ϕi, i ∈ [n], and a necessity measure µ, such that is represented by the Sugeno utility functional f = qµ(ϕ1, . . . , ϕn).Recall that is a preference relation if and only if is represented by an order-preserving function valued in some chain (for instance, by its rank function). The following result that draws from Theorem 5 (whose meaning is discussed above) axiomatizes those preference relations represented by general Sugeno utility functionals.

	3.4 Axiomatizations of preference relations
	represented by Sugeno utility functionals
	Theorem 10. A preference relation on X can be represented by a
	Sugeno utility functional if and only if
	x 0 k ≺ x a k and y a k ≺ y 1 k =⇒ x a k	y a k	(8)

holds for all x, y ∈ X and k ∈ [n], a ∈ X k .

For (OPT) =⇒ (OPT 1 ), just take x = x a k , y = y 0 k and A = [n] \ {k}.

Since X/ ∼ has two elements, this is essentially the same as the rank function r : X → X/ ∼.

ACKNOWLEDGEMENTS

The first author is supported by the internal research project F1R-MTH-PUL-12RDO2 of the University of Luxembourg. The third author acknowledges support 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).


Miguel Couceiro

Jean-Luc Marichal

Tam Ás Waldhauser

LOCALLY MONOTONE BOOLEAN AND PSEUDO-BOOLEAN FUNCTIONS

Keywords: Mathematics Subject Classification. 06E30, 94C10 Boolean function, pseudo-Boolean function, local monotonicity, discrete partial derivative, join and meet derivatives

We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on tuples which differ in less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions.

Local monotonicities are shown to be tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions are shown to have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classification of p-locally monotone functions, as well as of functions having ppermutable derivatives, in terms of certain forbidden "sections", i.e., functions which can be obtained by substituting constants for variables. This description is made explicit in the special case when p = 2.

Introduction

Throughout this paper, let [n] = {1, . . . , n} and B = {0, 1}. We are interested in the so-called Boolean functions f ∶ B n → B and pseudo-Boolean functions f ∶ B n → R, where n denotes the arity of f . The pointwise ordering of functions is denoted by ≤, i.e., f ≤ g means that f (x) ≤ g(x) for all x ∈ B n . The negation of x ∈ B is defined by x = x ⊕ 1, where ⊕ stands for addition modulo 2. For x, y ∈ B, we set x ∧ y = min(x, y) and x ∨ y = max(x, y).

For k ∈ [n], x ∈ B n , and a ∈ B, let x a k be the tuple in B n whose i-th component is a, if i = k, and x i , otherwise. We use the shorthand notation x ab jk for (x a j ) b k = (x b k ) a j . More generally, for S ⊆ [n], a ∈ B n , and x ∈ B S , let a x S be the tuple in B n whose i-th component is x i , if i ∈ S, and a i , otherwise.

Let i ∈ [n] and f ∶ B n → R. A variable x i is said to be essential in f , or that f depends on x i , if there exists a ∈ B n such that f (a 0 i ) ≠ f (a 1 i ). Otherwise, x i is said to be inessential in f . Let S ⊆ [n] and f ∶ B n → R. We say that g∶ B S → R is an S-section of f if there exists a ∈ B n such that g(x) = f (a x S ) for all x ∈ B S . By a section of f we mean an S-section of f for some S ⊆ [n], i.e., any function which can be obtained from f by replacing some of its variables by constants.

The (discrete) partial derivative of f ∶ B n → R with respect to its k-th variable is the function [START_REF] Foldes | Submodularity, supermodularity, and higher-order monotonicities of pseudo-Boolean functions[END_REF][START_REF] Grabisch | Equivalent representations of set functions[END_REF]. Note that ∆ k f does not depend on its k-th variable, hence it could be regarded as a function of arity n -1, but for notational convenience we define it as an n-ary function.

∆ k f ∶ B n → R defined by ∆ k f (x) = f (x 1 k )-f (x 0 k ); see
A pseudo-Boolean function f ∶ B n → R can always be represented by a multilinear polynomial of degree at most n (see [START_REF] Hammer | Boolean methods in operations research and related areas[END_REF]), that is, [START_REF]Decision-Making Process -Concepts and Methods[END_REF] f

(x) = ∑ S⊆[n] a S ∏ i∈S x i ,
where a S ∈ R. For instance, the multilinear expression for a binary pseudo-Boolean function is given by ( 2)

a 0 + a 1 x 1 + a 2 x 2 + a 12 x 1 x 2 .
This representation is very convenient for computing the partial derivatives of f . Indeed, ∆ k f can be obtained by applying the corresponding formal derivative to the multilinear representation of f . Thus, from (1), we immediately obtain

(3) ∆ k f (x) = ∑ S∋k a S ∏ i∈S∖{k} x i .
We say that f is isotone (resp. antitone) in its k-th variable if ∆ k f (x) ≥ 0 (resp. ∆ k f (x) ≤ 0) for all x ∈ B n . If f is either isotone or antitone in its k-th variable, then we say that f is monotone in its k-th variable. If f is isotone (resp. antitone, monotone) in all of its variables, then f is an isotone (resp. antitone, monotone) function. 1 It is clear that any section of an isotone (resp. antitone, monotone) function is also isotone (resp. antitone, monotone). Thus defined, a function f ∶ B n → R is monotone if and only if none of its partial derivatives changes in sign on B n .

Noteworthy examples of monotone functions include the so-called pseudo-polynomial functions [START_REF] Couceiro | Axiomatizations and factorizations of Sugeno utility functions[END_REF][START_REF] Couceiro | Pseudo-polynomial functions over finite distributive lattices[END_REF] which play an important role, for instance, in the qualitative approach to decision making; for general background see, e.g., [START_REF]Decision-Making Process -Concepts and Methods[END_REF][START_REF] Dubois | Qualitative decision theory with Sugeno integrals, Fuzzy measures and integrals[END_REF]. In the current setting, pseudo-polynomial functions can be thought of as compositions p ○ (φ 1 , . . . , φ n ) of (lattice

) polynomial functions p∶ [a, b] n → [a, b], a < b, with unary functions φ i ∶ B → [a, b], i ∈ [n]
. Interestingly, pseudo-polynomial functions f ∶ B n → R coincide exactly with those pseudo-Boolean functions that are monotone.

Theorem 1. A pseudo-Boolean function is monotone if and only if it is a pseudopolynomial function.

Proof. Clearly, every pseudo-polynomial function is monotone. For the converse, suppose that f ∶ B n → R is monotone and let a ∈ R be the minimum and b ∈ R the maximum of f . Constant functions are obviously pseudo-polynomial functions, therefore we assume a < b. Define

φ i ∶ B → {a, b} by φ i (0) = a and φ i (1) = b if f is isotone in its i-th variable and φ i (0) = b and φ i (1) = a otherwise. Let p∶ {a, b} n → [a, b] be given by p = f ○ (φ -1 1 , . . . , φ -1 n ).
Thus defined, p is isotone (i.e., order-preserving) in each variable and hence, by Theorem D in Goodstein [10, p. 237], there exists a polynomial function

p ′ ∶ [a, b] n → [a, b] such that p ′ | {a,b} n = p. Therefore f is the pseudo-polynomial function p ′ ○ (φ 1 , . . . , φ n ).
In the special case of Boolean functions, monotone functions are most frequent among functions of small (essential) arity. For instance, among binary functions f ∶ B 2 → B, there are exactly two non-monotone functions, namely the Boolean sum x 1 ⊕ x 2 and its negation x 1 ⊕ x 2 ⊕ 1. Each of these functions is in fact highly non-monotone in the sense that any of its partial derivatives changes in sign when negating its unique essential variable; this is not the case, e.g., with f (x 1 , x 2 , x 3 ) = x 1 -x 1 x 2 + x 2 x 3 which is non-monotone but none of its partial derivatives changes in sign when negating any of its variables (see Example 6 below).

This fact motivates the study of these "skew" functions, i.e., these highly nonmonotone functions. To formalize this problem we propose the following parameterized relaxations of monotonicity: a function f ∶ B n → R is p-locally monotone if none of its partial derivatives changes in sign when negating less than p of its variables, or equivalently, on tuples which differ in less than p positions. With this terminology, our problem reduces to asking which Boolean functions are not 2locally monotone. As we will see (Corollary 10), these are precisely those functions that have the Boolean sum or its negation as a binary section.

In this paper we extend this study to pseudo-Boolean functions and show that these parameterized relaxations of monotonicity are tightly related to the following lattice versions of partial derivatives. For

f ∶ B n → R and k ∈ [n], let ∧ k f ∶ B n → R and ∨ k f ∶ B n → R be the partial lattice derivatives defined by ∧ k f (x) = f (x 0 k ) ∧ f (x 1 k ) and ∨ k f (x) = f (x 0 k ) ∨ f (x 1 k
). The latter, known as the k-th join derivative of f , was proposed by Fadini [START_REF] Fadini | Operatori che estendono alle algebre di Boole la nozione di derivata. (Italian)[END_REF] while the former, known as the k-th meet derivative of f , was introduced by Thayse [START_REF] Thayse | Disjunctive and conjunctive operators for Boolean functions[END_REF]. In [START_REF] Thayse | Meet and join derivatives and their use in switching theory[END_REF] these lattice derivatives were shown to be related to so-called prime implicants and implicates of Boolean functions which play an important role in the consensus method for Boolean and pseudo-Boolean functions. For further background and applications see, e.g., [START_REF] Crama | Boolean Functions: Theory, Algorithms, and Applications (Encyclopedia of Mathematics and its Applications)[END_REF][START_REF] Davio | Discrete and switching functions[END_REF][START_REF] Foldes | Disjunctive and conjunctive normal forms of pseudo-Boolean functions[END_REF][START_REF] Posthoff | Logic functions and equations: binary models for computer science[END_REF][START_REF] Thayse | Boolean Calculus of Differences[END_REF].

Observe that, just like in the case of the partial derivative ∆ k f , the k-th variable of each of the lattice derivatives ∧ k f and ∨ k f is inessential.

The following proposition assembles some basic properties of lattice derivatives.

Proposition 2. For any pseudo-Boolean functions f, g∶ B n → R and j, k ∈ [n], j ≠ k, the following hold:

(i) ∧ k ∧ k f = ∧ k f and ∨ k ∨ k f = ∨ k f ; (ii) if f ≤ g, then ∧ k f ≤ ∧ k g and ∨ k f ≤ ∨ k g; (iii) ∧ j ∧ k f = ∧ k ∧ j f and ∨ j ∨ k f = ∨ k ∨ j f ; (iv) ∨ k ∧ j f ≤ ∧ j ∨ k f .
From equations (1) and (3) it follows that every function is (up to an additive constant) uniquely determined by its partial derivatives. As it turns out, this does not hold when lattice derivatives are considered. However, as we shall see (Theorem 22), there are only two types of such exceptions. Now, if an n-ary pseudo-Boolean function is 2-locally monotone, then for every Lemma 11 below). This motivates the notion of permutable lattice derivatives. As it turns out, p-local monotonicity of f implies permutability of p of its lattice derivatives (see Theorem 21). However the converse does not hold (see Example 24).

j, k ∈ [n], j ≠ k, we have ∨ k ∧ j f = ∧ j ∨ k f (see
The structure of this paper goes as follows. In Section 2 we formalize the notion of p-local monotonicity and show that it gives rise to a hierarchy of monotonicities whose largest member is the class of all n-ary pseudo-Boolean functions (this is the case when p = 1) and whose smallest member is the class of n-ary monotone functions (this is the case when p = n). We also provide a characterization of p-locally monotone functions in terms of "forbidden" sections; as mentioned, this characterization is made explicit in the special case when p = 2. In Section 3 we introduce the notion of permutable lattice derivatives. Similarly to local monotonicity, the notion of permutable lattice derivatives gives rise to nested classes, each of which is also described in terms of its sections. In the Boolean case and for p = 2, these two parameterized notions are shown to coincide; this does not hold for pseudo-Boolean functions even when p = 2 (see Example 13). (At the end of Section 3 we also provide some game-theoretic interpretations of p-local monotonicity and p-permutability of lattice derivatives.) However, in Section 4, we show that a symmetric function is p-locally monotone if and only if it has p-permutable lattice derivatives. In the last section we discuss directions for future research.

Local monotonicities

The following definition formulates a local version of monotonicity given in terms of Hamming distance between tuples. In what follows we assume that p ∈ [n].

Definition 3. We say that f ∶ B n → R is p-locally monotone if, for every k ∈ [n]
and every x, y ∈ B n , we have

∑ i∈[n]∖{k} |x i -y i | < p ⇒ ∆ k f (x) ∆ k f (y) ≥ 0.
Any p-locally monotone pseudo-Boolean function is also p ′ -locally monotone for every p ′ ≤ p. Every function f ∶ B n → R is 1-locally monotone, and f is n-locally monotone if and only if it is monotone. Thus p-local monotonicity is a relaxation of monotonicity, and the nested classes of p-locally monotone functions for p = 1, . . . , n provide a hierarchy of monotonicities for n-ary pseudo-Boolean functions. The weakest nontrivial condition is 2-local monotonicity, therefore we will simply say that f is locally monotone whenever f is 2-locally monotone. 2 If f is p-locally monotone for some p < n but not (p + 1)-locally monotone, then we say that f is exactly p-locally monotone, or that the degree of local monotonicity of f is p.

If f ∶ B n → B is a Boolean function, then ∆ k f (x) ∈ {-1, 0, 1} for all x ∈ B n , hence the condition ∆ k f (x) ∆ k f (y) ≥ 0 in the definition of p-local monotonicity is equivalent to (4) |∆ k f (x) -∆ k f (y)| ≤ 1.
From this it follows that a Boolean function

f ∶ B n → B is locally monotone if and only if (5) |∆ k f (x) -∆ k f (y)| ≤ ∑ i∈[n]∖{k} |x i -y i |.
(see [START_REF] Marichal | Aggregation on finite ordinal scales by scale independent functions[END_REF]Lemma 5.1] for a proof of ( 5) in a slightly more general framework). In a sense, the latter identity means that ∆ k f is "1-Lipschitz continuous".

The following proposition is just a reformulation of the definition of p-local monotonicity.

Proposition 4. A function f ∶ B n → R is p-locally monotone if and only if, for every k ∈ [n], S ⊆ [n] ∖ {k}, with |S| = p -1,
and every a ∈ B n , x, y ∈ B S , we have

(6) ∆ k f (a x S ) ∆ k f (a y S ) ≥ 0.
Equivalently, a pseudo-Boolean function is p-locally monotone if and only if none of its partial derivatives changes in sign when negating less than p of its variables.

As a special case, we have that f ∶ B n → R is locally monotone if and only if, for every j, k ∈ [n], j ≠ k, and every x ∈ B n , we have

(7) ∆ k f (x 0 j ) ∆ k f (x 1 j ) ≥ 0.
Equivalently, a pseudo-Boolean function is locally monotone if and only if none of its partial derivatives changes in sign when negating any of its variables.

By [START_REF] Crama | Boolean Functions: Theory, Algorithms, and Applications (Encyclopedia of Mathematics and its Applications)[END_REF] we see that, for Boolean functions f ∶ B n → B, inequality ( 7) can be replaced with

|∆ jk f (x)| ≤ 1, where ∆ jk f (x) = ∆ j ∆ k f (x) = ∆ k ∆ j f (x).
Example 5. As observed, the binary Boolean sum

f 1 (x 1 , x 2 ) = x 1 ⊕ x 2 = x 1 + x 2 -2x 1 x 2
and the binary Boolean equivalence

f 2 (x 1 , x 2 ) = f 1 (x 1 , x 2 ) = x 1 ⊕ x 2 ⊕ 1 = 1 -x 1 -x 2 + 2x 1 x 2
are not locally monotone. Indeed, we have Proof. We just need to observe that the inequality ( 6) is equivalent to ∆ k g(x)∆ k g(y) ≥ 0, where g is the p-ary section of f defined by g(x) = f (a x S∪{k} ), where S is a (p-1)subset of [n] ∖ {k}. Thus f is p-locally monotone if and only if ∆ k g(x)∆ k g(y) ≥ 0 holds for every x, y ∈ B S∪{k} , and for every S ∪ {k}-section g of f .

|∆ 12 f 1 (x 1 , x 2 )| = |∆ 12 f 2 (x 1 , x 2 )| = 2.

Example 6. Consider the ternary Boolean function

f ∶ B 3 → B given by f (x 1 , x 2 , x 3 ) = x 1 -x 1 x 2 + x 2 x 3 . Since ∆ 2 f may change in sign (∆ 2 f (x) = x 3 -x 1 ), the function f is not monotone. However, f is locally monotone since |∆ 12 f (x)| = 1, |∆ 13 f (x)| = 0,
By combining [START_REF] Foldes | Disjunctive and conjunctive normal forms of pseudo-Boolean functions[END_REF] with Theorem 8, we can easily verify the following corollary.

Corollary 9. A function f ∶ B n → R is locally monotone if and only if every binary section (2) of f satisfies a 1 (a 1 + a 12 ) ≥ 0 and a 2 (a 2 + a 12 ) ≥ 0.
Since every binary Boolean function is monotone except for x ⊕ y and x ⊕ y ⊕ 1, we also obtain the following corollary.

Corollary 10. A Boolean function f ∶ B n → B is locally monotone if and only if neither x ⊕ y nor x ⊕ y ⊕ 1 is a section of f .

Permutable lattice derivatives

The aim of this section is to relate commutation of lattice derivatives to plocal monotonicity. The starting point is the characterization of locally monotone Boolean functions given in Theorem 12 below.

Lemma 11. If f ∶ B n → R is locally monotone, then ∨ k ∧ j f = ∧ j ∨ k f for all j, k ∈ [n], j ≠ k. Proof. Let f ∶ B n → R be a locally monotone function, and let j, k ∈ [n], j ≠ k. Setting a = f (x 00 jk ), b = f (x 01 jk ), c = f (x 10 jk ), and d = f (x 11 jk ), the desired equality ∨ k ∧ j f (x) = ∧ j ∨ k f (x) takes the form (8) (a ∧ c) ∨ (b ∧ d) = (a ∨ b) ∧ (c ∨ d).
Since f is 2-locally monotone, the binary section g(u, v) = f (x uv jk ) is monotone, according to Theorem 8. If g is isotone in u, then a ≤ c and b ≤ d, while if g is antitone in u, then a ≥ c and b ≥ d. Similarly, we have either a ≤ b and c ≤ d or a ≥ b and c ≥ d, depending on whether g is isotone or antitone in v. Thus we need to consider four cases, and in each one of them it is straightforward to verify [START_REF] Foldes | Submodularity, supermodularity, and higher-order monotonicities of pseudo-Boolean functions[END_REF].

Theorem 12. A Boolean function f ∶ B n → B is locally monotone if and only if ∨ k ∧ j f = ∧ j ∨ k f holds for all j, k ∈ [n], j ≠ k. Proof. If f is locally monotone, then ∨ k ∧ j f = ∧ j ∨ k f by Lemma 11. If f is not locally monotone, then Corollary 10 implies that there exists a ∈ B n and j, k ∈ [n], j ≠ k, such that the binary section g(u, v) = f (a uv jk ) is of the form g(u, v) = u ⊕ v or g(u, v) = u ⊕ v ⊕ 1. Then we have ∨ k ∧ j f (a) = (g(0, 0) ∧ g(1, 0)) ∨ (g(0, 1) ∧ g(1, 1)) = 0, ∧ j ∨ k f (a) = (g(0, 0) ∨ g(0, 1)) ∧ (g(1, 0) ∨ g(1, 1)) = 1, showing that ∨ k ∧ j f ≠ ∧ j ∨ k f .
As the next example shows, Theorem 12 is not valid for pseudo-Boolean functions.

Example 13. Let f be the binary pseudo-Boolean function defined by f (0,

0) = 1, f (0, 1) = 4, f (1, 0) = 2 and f (1, 1) = 3. Then we have ∨ 2 ∧ 1 f = ∧ 1 ∨ 2 f = 3 and ∨ 1 ∧ 2 f = ∧ 2 ∨ 1 f = 2. However, f is not locally monotone since ∆ 1 f (x 0 2 )∆ 1 f (x 1 2 ) = -1.
Lemma 11 and Theorem 12 motivate the following notion of permutability of lattice derivatives, and its relation to local monotonicities. Definition 14. We say that a pseudo-Boolean function f ∶ B n → R has p-permutable lattice derivatives if, for every p-subset {k 1 , . . . , k p } ⊆ [n], every choice of the operators O ki ∈ {∧ ki , ∨ ki } (i = 1, . . . , p), and every permutation π ∈ S p , the following identity holds:

O k1 ⋯ O kp f = O k π(1) ⋯ O k π(p) f. If f ∶ B n → R has n-
permutable lattice derivatives, then we simply say that f has permutable lattice derivatives.

Every function f ∶ B n → R has 1-permutable lattice derivatives. We will see in Theorem 23 that if a function f ∶ B n → R has p-permutable lattice derivatives, then it also has p ′ -permutable lattice derivatives for every p ′ ≤ p. Fact 15. A function f ∶ B n → R has p-permutable lattice derivatives if and only if so has αf + β for every α, β ∈ R, with α ≠ 0. The same holds for any function obtained from f by negating some of its variables. Fact 16. A function f ∶ B n → R has p-permutable lattice derivatives if and only if every p-ary section of f has permutable lattice derivatives.

In the particular case when p = 2, we have the following description of functions having 2-permutable lattice derivatives. The proof is a straightforward verification of cases.

Proposition 17. A function f ∶ B n → R has 2-permutable lattice derivatives if and only if every binary section (2) of f satisfies a 1 a 12 ≥ 0 or a 2 a 12 ≥ 0 or |a 12 | ≤ |a 1 | ∨ |a 2 |.
Lemma 11 shows that the class of 2-locally monotone pseudo-Boolean functions is a subclass of that of pseudo-Boolean functions which have 2-permutable lattice derivatives. Example 13 then shows that this inclusion is strict. On the other hand, according to Theorem 12, a Boolean function is 2-locally monotone if and only if it has 2-permutable lattice derivatives. Example 24 below shows that the analogous equivalence does not hold for p > 2. However, p-local monotonicity implies p-permutability of lattice derivatives of any pseudo-Boolean function (see Theorem 21 below). To this extent, let us first study how the degree of local monotonicity is affected by taking lattice derivatives.

Lemma 18. If f ∶ B n → R is monotone, then ∧ j f and ∨ j f are also monotone for all j ∈ [n]. Proof. Clearly, if f is monotone, then so are f 0 j (x) = f (x 0 j ) and f 1 j (x) = f (x 1 j ), for all j ∈ [n].
Moreover, if f is isotone (resp. antitone) in x k , then both f 0 j and f 1 j are also isotone (resp. antitone) in x k . Since ∧ and ∨ are isotone functions, we have that for every j ∈

[n], both ∧ j f (x) = f 0 j (x) ∧ f 1 j (x) and ∨ j f (x) = f 0 j (x) ∨ f 1 j (x) are monotone.
Theorem 19. If f ∶ B n → R is p-locally monotone, then ∧ j f and ∨ j f are (p -1)locally monotone for all j ∈ [n].

Proof. Suppose that f ∶ B n → R is p-locally monotone. By Theorem 8, it suffices to show that all (p -1)-ary sections of ∧ j f and ∨ j f are monotone. We consider only ∨ j f , the other case can be dealt with in a similar way.

Let h be a (p -1)-ary section of ∨ j f defined by h(x) = ∨ j f (a x S ) for all x ∈ B S , where a ∈ B n and S ⊆ [n] is a (p -1)-subset. Let T = S ∪ {j}, and let us define g∶ B T → R by g(y) = f (a y T ) for all y ∈ B T . Clearly, g is a section of f , and the arity of g is either p -1 or p , depending on whether j belongs to S or not. A simple calculation shows that h(y| S ) = ∨ j g(y) for all y ∈ B T , where y| S stands for the restriction of y to S. This means that if j ∉ S, then h can be obtained from ∨ j g by deleting its inessential j-th variable, and h = ∨ j g if j ∈ S. Since f is p-locally monotone, g is monotone by Theorem 8, thus we can conclude with the help of Lemma 18 that h is monotone as well.

Corollary 20. Let 0 ≤ ℓ < p ≤ n. If f ∶ B n → R is p-locally monotone, then, for every ℓ-subset {k 1 , . . . , k ℓ } ⊆ [n] and every choice of the operators O ki ∈ {∨ ki , ∧ ki } (i = 1, . . . , ℓ), the function O k1 ⋯ O k ℓ f is (p -ℓ)-locally monotone. In particular, if ℓ ≤ p -2, then O k1 ⋯ O k ℓ f is locally monotone.
Remark 1. We will see in Example 26 of Section 4 that Theorem 19 cannot be sharpened, i.e., the lattice derivatives of a p-locally monotone function are not necessarily p-locally monotone, not even in the case of Boolean functions.

With the help of Corollary 20 we can now prove the promised implication between p-local monotonicity and p-permutability of lattice derivatives, thus generalizing Lemma 11.

Theorem 21. If f ∶ B n → R is p-locally monotone, then it has p-permutable lattice derivatives.

Proof. Let f ∶ B n → R be a p-locally monotone function, let {k 1 , . . . , k p } be a psubset of [n], and let O ki ∈ {∧ ki , ∨ ki } for i = 1, . . . , p. We need to show that for any permutation π ∈ S p the following identity holds:

O k1 ⋯ O kp f = O k π(1) ⋯ O k π(p) f.
Since S p is generated by transpositions of the form (i i + 1), it suffices to prove that

O k1 ⋯ O ki-1 O ki O ki+1 O ki+2 ⋯ O kp f = O k1 ⋯ O ki-1 O ki+1 O ki O ki+2 ⋯ O kp f,
and for this it is sufficient to verify that ( 9)

O ki O ki+1 g = O ki+1 O ki g,
where g stands for the function O ki+2 ⋯ O kp f . From Corollary 20 it follows that g is locally monotone, and then Lemma 11 proves (9) if one of O ki , O ki+1 is a meet and the other is a join derivative. (If both are meet or both are join, then ( 9) is trivial.)

A natural question regarding lattice derivatives is whether a function can be reconstructed from its derivatives. As the next theorem shows, the answer is positive for almost all functions.

Theorem 22. Let f, g∶ B n → R be pseudo-Boolean functions such that for all k ∈ [n] we have ∨ k f = ∨ k g and ∧ k f = ∧ k g. Then either f = g or there exists a one-to-one

function α∶ B → R such that f (x) = α(x 1 ⊕ ⋯ ⊕ x n ) and g(x) = α(x 1 ⊕ ⋯ ⊕ x n ⊕ 1) for all x ∈ B n .
Proof. To make the proof more vivid, we present it through the analysis of the following game. Alice picks a secret function f ∶ B n → R, and Bob tries to identify this function by asking the values of its lattice derivatives. If he can do this, then he wins, otherwise Alice is the winner. We show that Bob has a winning strategy unless f is a function of the special form in the statement of the theorem.

Let us regard B n as the set of vertices of the n-dimensional cube, and let Alice write the values of f to the corresponding vertices. Now the possible winning strategy for Bob is based on the following four basic observations. 1. Bob can determine the unordered pair of numbers written to the endpoints of any edge of the cube. Indeed, the endpoints of an edge are of the form

x 0 k , x 1 k , and it is clear that {∧ k f (x), ∨ k f (x)} = {f (x 0 k ), f (x 1 k )}.

If Bob can find the value of f at one point, then he can win. According

to the previous observation, knowing the value at one vertex of the cube, Bob can figure out the values written to the neighboring vertices. Since the graph of the cube is connected, he can determine all values of f this way.

If

f (x 0 k ) = f (x 1 k ) for some x ∈ B n , k ∈ [n]
, then Bob can win. This follows immediately from the first two observations. 4. If the range of f contains at least three elements, then Bob can win. We can suppose that the previous observation does not apply, i.e., for every edge Bob detects a two-element set. If f takes on at least three different values, then, by the connectedness of the cube, there exists a vertex x and two edges incident with this vertex such that the two-element sets E 1 and E 2 corresponding to these edges are different. Then E 1 ∩ E 2 must be a one-element set3 containing the value of f (x), and then Bob can win as explained in the second observation. From these observations we can conclude that Bob has a winning strategy unless the range of f contains exactly two numbers and f

(x 0 k ) ≠ f (x 1 k ), for all x ∈ B n , k ∈ [n].
This means that f is of the following form for some u ≠ v ∈ R:

f (x) = { u , if |x| is even ; v , if |x| is odd , where |x| = ∑ n i=1 x i . In other words, f (x) = α(x 1 ⊕⋯⊕x n ), where α(0) = u, α(1) = v.
In this case Bob can determine f only up to interchanging u and v, i.e., he cannot distinguish f from g(x) = α(x 1 ⊕ ⋯ ⊕ x n ⊕ 1), so he has only 50% chance to win. (Indeed, f and g have the same lattice derivatives, namely their meet derivatives are all constant u ∧ v, while their join derivatives are all constant u ∨ v.)

The following theorem shows that, as in the case of local monotonicity, the classes of functions having permutable lattice derivatives form a chain under inclusion.

Theorem 23. If f ∶ B n → R has (p + 1)-permutable lattice derivatives, then f has p-permutable lattice derivatives.

Proof. Let f ∶ B n → R be a function that has (p + 1)-permutable lattice derivatives. Using the same notation as in the proof of Theorem 21, it suffices to prove that

O k1 ⋯ O ki-1 O ki O ki+1 O ki+2 ⋯ O kp f = O k1 ⋯ O ki-1 O ki+1 O ki O ki+2 ⋯ O kp f.
Let g 1 and g 2 be the (n -p)-ary functions obtained from the left-hand side and from the right-hand side of this equality by deleting their inessential variables

x k1 , . . . , x kp . If O ki = ∧ ki , O ki+1 = ∧ ki+1 or O ki = ∨ ki , O ki+1 = ∨ ki+1 , then g 1 = g 2 holds trivially. Let us now assume that O ki = ∨ ki , O ki+1 = ∧ ki+1 ; the remaining case O ki = ∧ ki , O ki+1 = ∨ ki+1 is similar.
By Proposition 2, we have g 1 ≤ g 2 . Since the two (types of) functions given in Theorem 22 are order-incomparable, if g 1 ≠ g 2 , then the lattice derivatives of g 1 and g 2 cannot all coincide. Thus there exists j ∈

[n] ∖ {k 1 , . . . , k p } and O j ∈ {∧ j , ∨ j } such that O j g 1 ≠ O j g 2 .
Taking into account the definition of g 1 and g 2 , we can rewrite this inequality as

O j O k1 ⋯ O ki-1 O ki O ki+1 O ki+2 ⋯ O kp f ≠ O j O k1 ⋯ O ki-1 O ki+1 O ki O ki+2 ⋯ O kp f,
which contradicts the fact that f has (p + 1)-permutable lattice derivatives.

If f ∶ B n → B is a Boolean function with p-permutable lattice derivatives for some p ≥ 2, then f has 2-permutable lattice derivatives by Theorem 23, and then Theorem 12 implies that f is 2-locally monotone. Unfortunately, nothing more can be said about the degree of local monotonicity of a Boolean function with ppermutable lattice derivatives. Indeed, the next example shows that there exist n-ary Boolean functions with n-permutable lattice derivatives that are exactly 2locally monotone.

Example 24. Let f n ∶ B n → B be the function that takes the value 1 on all tuples of the form x = ( m 1, . . . , 1, 0, . . . , 0) with 0 ≤ m ≤ n, and takes the value 0 everywhere else. Using Corollary 10, it is not difficult to verify that f n is 2-locally monotone. However, if n ≥ 3, then f n is not 3-locally monotone, since

∆ 2 f (0, 0, 0, 0, . . . , 0) = -1, ∆ 2 f (1, 0, 1, 0, . . . , 0) = 1.
Thus f n is exactly 2-locally monotone.

We will show by induction on n that f n has n-permutable lattice derivatives. First we compute the meet derivatives

∧ k f n (x) = { 1 , if x 1 = ⋯ = x k-1 = 1 and x k+1 = ⋯ = x n = 0 ; 0 , otherwise .
Since ∧ k f takes the value 1 only at one tuple, it is monotone. The join derivative ∨ k f n is essentially the same as the function

f n-1 (up to the inessential k-th variable of ∨ k f n ), that is, (10)
∨ k f n (x) = f n-1 (x 1 , . . . , x k-1 , x k+1 , . . . , x n ). Now it follows that if {k 1 , . . . , k n } = [n] and O ki ∈ {∧ ki , ∨ ki } (i = 1, . . . , n), then (11)
O k1 ⋯ O kn-1 O kn f = O k π(1) ⋯ O k π(n-1) O kn f
holds for every permutation π ∈ S n-1 . (If O kn = ∧ kn , then we use Theorem 21 and the fact that ∧ kn f is monotone, and if O kn = ∨ kn , then we use [START_REF] Goodstein | The solution of equations in a lattice[END_REF] and the induction hypothesis.) On the other hand, from the 2-local monotonicity of f we can conclude that

(12) O k1 ⋯ O kn-2 O kn-1 O kn f = O k1 ⋯ O kn-2 O kn O kn-1 f
with the help of Theorem 12. Since S n is generated by S n-1 and the transposition (n -1 n), we see from [START_REF] Gotsman | Spectral properties of threshold functions[END_REF] and ( 12) that f has n-permutable lattice derivatives.

We finish this section with game-theoretic interpretations of the parameterized notions of local monotonicity and permutability of lattice derivatives. Identifying B n with the power set of The partial derivative ∆ k f (C) gives the (marginal) contribution of the k-th player to coalition C. Note that the same player might have a positive contribution to some coalitions and a negative contribution to other coalitions. Such a setting can model situations where some players have conflicts, which prevents them from cooperating. The lattice derivative ∨ k f (C) gives the outcome if the k-th player acts benevolently and joins (or leaves) the coalition C only if this increases the worth. Similarly, ∧ k f (C) represents the outcome if the k-th player acts malevolently.

Games corresponding to locally monotone functions have the property that if two coalitions are close to each other, then any given player relates in the same way to these coalitions. More precisely, f is p-locally monotone if and only if whenever two coalitions differ in less than p players, then the contribution of any player is either nonnegative to both coalitions or it is nonpositive to both.

Finally, let us interpret permutability of lattice derivatives. Let P be a p-subset of [n], and let C ⊆ [n] ∖ P . Suppose that some players of P are benevolent and some of them are malevolent, and they are asked one by one to join coalition C if they want to. We obtain the least possible outcome if the malevolent players are asked first, and we get the greatest outcome if the benevolent players make their choices first. The function f has p-permutable lattice derivatives if and only if these extremal outcomes coincide, i.e., if the order in which the players make their choices is irrelevant for every p-subset of [n].

Symmetric functions

In the previous sections we saw that both notions of local monotonicity and of permutable lattice derivatives lead to two hierarchies of pseudo-Boolean functions which are related by the fact that each p-local monotone class is contained in the corresponding class of functions having p-permutable lattice derivatives. Now, in general this containment is strict. However, under certain assumptions (see, e.g., Theorem 12), p-local monotonicity is equivalent to p-permutability of lattice derivatives. Hence it is natural to ask for conditions under which these two notions are equivalent.

In this section we provide a partial answer to this problem by focusing on symmetric pseudo-Boolean functions, i.e., functions f ∶ B n → R that are invariant under all permutations of their variables. Quite surprisingly, in this case the notions of p-local monotonicity and p-permutability of lattice derivatives become equivalent.

Symmetric functions of arity n are in a one-to-one correspondence with sequences of real numbers of length n + 1, where the function corresponding to the sequence α = α 0 , . . . , α n is given by f (x) = α |x| (x ∈ B n ). Clearly, f is isotone if and only if the corresponding sequence is nondecreasing, i.e., α 0 ≤ α 1 ≤ ⋯ ≤ α n . Similarly, f is antitone if and only if α 0 ≥ α 1 ≥ ⋯ ≥ α n , and f is monotone if and only if f is either isotone or antitone. 4It is easy to see that if f is symmetric, then every section of f is also symmetric; moreover, if f corresponds to the sequence α = α 0 , . . . , α n , then the p-ary sections of f are precisely the symmetric functions corresponding to the subsequences5 α i , α i+1 , . . . , α i+p of α of length p + 1. This observation and Theorem 8 lead to the following description of p-locally monotone symmetric pseudo-Boolean functions.

Proposition 25. Let f ∶ B n → R be a symmetric function corresponding to the sequence α = α 0 , . . . , α n . Then f is p-locally monotone if and only if each subsequence of length p + 1 of α is either nondecreasing or nonincreasing.

Unlike in the previous sections, here it will be more convenient to discard the inessential k-th variable of the lattice derivatives ∧ k f and ∨ k f , and regard the latter as (n -1)-ary functions. Clearly, if f is symmetric, then so are its lattice derivatives. Moreover, if f corresponds to the sequence α = α 0 , . . . , α n , then ∧ k f and ∨ k f correspond to the sequences

α 0 ∧ α 1 , α 1 ∧ α 2 , . . . , α n-1 ∧ α n and α 0 ∨ α 1 , α 1 ∨ α 2 , . . . , α n-1 ∨ α n ,
respectively, for all k ∈ [n]. Since these sequences do not depend on k, we will write ∧f and ∨f instead of ∧ k f and ∨ k f , and we will abbreviate where n = 2p + 4 and p ≥ 2. It follows from Proposition 25 that f is exactly p-locally monotone. To compute ∧f , it is handy to construct a table whose first row contains the sequence α, and in the second row we write α i ∧ α i+1 between α i and α i+1 :

f ∶ 0 0 1 1 ⋯ 1 1 0 0 ⋯ 0 0 1 1 ∧f ∶ 0 0 1 1 ⋯ 1 1 0 0 0 ⋯ 0 0 0 1
Thus ∧f corresponds to the sequence 0, 0, Remark 2. Example 26 shows that the degree of local monotonicity can decrease, when taking lattice derivatives, and Theorem 19 states that it can decrease by at most one. Other examples can be found to illustrate the cases when this degree stays the same, or even increases. For instance, consider the function f (x) = x 1 ⊕ ⋯ ⊕ x n , which is not even 2-locally monotone, but its lattice derivatives are constant.

We conclude this section by proving that for symmetric functions the notions of p-local monotonicity and p-permutability of lattice derivatives coincide.

Theorem 27. If f ∶ B n → R is symmetric, then f is p-locally monotone if and only if f has p-permutable lattice derivatives. Proof. By Theorem 21, it is enough to show that if a symmetric function f ∶ B n → R is not p-locally monotone, then it does not have p-permutable lattice derivatives. So suppose that f is a symmetric function which is not p-locally monotone, and which corresponds to the sequence α = α 0 , . . . , α n . Let α i , . . . , α i+ℓ be a shortest subsequence of α that is neither nondecreasing nor nonincreasing. Proposition 25 implies that there is indeed such a subsequence for ℓ + 1 ≤ p + 1. From the minimality of ℓ it follows that the subsequence α i , . . . , α i+ℓ-1 is either nondecreasing or nonincreasing. We may assume without loss of generality that the first case holds; the second case is the dual of the first one. Then we must have α i+ℓ-1 > α i+ℓ , since otherwise the whole subsequence α i , . . . , α i+ℓ would be nondecreasing. Thus we have the following inequalities: [START_REF] Hammer | Boolean methods in operations research and related areas[END_REF] α i ≤ α i+1 ≤ ⋯ ≤ α i+ℓ-1 > α i+ℓ .

From the minimality of ℓ, we can also conclude that the subsequence α i+1 , . . . , α i+ℓ is either nondecreasing or nonincreasing. As α i+ℓ-1 > α i+ℓ , the first case is impossible, therefore α i+1 , . . . , α i+ℓ is nonincreasing, and we must have α i < α i+1 since otherwise the whole subsequence α i , . . . , α i+ℓ would be nonincreasing:

(14) α i < α i+1 ≥ ⋯ ≥ α i+ℓ-1 ≥ α i+ℓ .
Comparing ( 13) and ( 14), we obtain

α i < α i+1 = ⋯ = α i+ℓ-1 > α i+ℓ .
To simplify notation, we set β ∶= α i , γ ∶= α i+1 , δ ∶= α i+ℓ . With this notation we have that α contains the subsequence β, γ, . . . , γ, δ of length ℓ + 1 with β, δ < γ. In the following we will use this observation to prove that f does not have ℓ-permutable lattice derivatives. Let us compute the sequence corresponding to ∨∧ ℓ-1 f . We can construct a table as in Example 26, but this time the table has ℓ + 1 rows (in the last row µ stands for β ∨ δ):

f ∶ α 0 ⋯ β γ γ γ ⋯ γ γ γ δ ⋯ α n ∧f ∶ ⋯ β γ γ ⋯ γ γ δ ⋯ ∧ 2 f ∶ ⋯ β γ ⋯ γ δ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ∧ ℓ-2 f ∶ ⋯ β γ δ ⋯ ∧ ℓ-1 f ∶ ⋯ β δ ⋯ ∨ ∧ ℓ-1 f ∶ ⋯ µ ⋯
A similar table can be constructed for ∧ ℓ-1 ∨ f :

f ∶ α 0 ⋯ β γ γ γ ⋯ γ γ γ δ ⋯ α n ∨f ∶ ⋯ γ γ γ ⋯ γ γ γ ⋯ ∧ ∨ f ∶ ⋯ γ γ ⋯ γ γ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ∧ ℓ-3 ∨ f ∶ ⋯ γ γ γ ⋯ ∧ ℓ-2 ∨ f ∶ ⋯ γ γ ⋯ ∧ ℓ-1 ∨ f ∶ ⋯ γ ⋯
Since β, δ < γ, we have µ < γ, and this means that the sequences corresponding to ∨ ∧ ℓ-1 f and ∧ ℓ-1 ∨ f differ in at least one position, therefore f does not have ℓ-permutable lattice derivatives. As ℓ ≤ p, this implies that f does not have ppermutable lattice derivatives either, according to Theorem 23.

Remark 3. As a consequence of Theorem 27, we can observe that any exactly p-locally monotone symmetric function (for instance, the functions considered in Example 26) has p-permutable but not (p + 1)-permutable lattice derivatives.

  and |∆ 23 f (x)| = 1. Thus f is exactly 2-locally monotone. Example 26 in Section 4 provides, for each p ≥ 2, examples of exactly p-locally monotone functions. Fact 7. A function f ∶ B n → R is p-locally monotone if and only if so is αf + β for every α, β ∈ R, with α ≠ 0. The same holds for any function obtained from f by negating some of its variables. The next theorem gives a characterization of p-locally monotone functions in terms of their sections. Theorem 8. A function f ∶ B n → R is p-locally monotone if and only if every p-ary section of f is monotone.

  [n], we can regard a pseudo-Boolean function f ∶ B n → R as a cooperative game, where [n] is the set of players and f (C) is the worth of coalition C ⊆ [n].

  ℓ f and ∨ ℓ f , respectively. The next example shows that Theorem 19 cannot be sharpened. Example 26. Let f ∶ B n → B be the symmetric function corresponding to the sequence α = 0, 0, p 1, . . . , 1, p 0, . . . , 0, 1, 1

  . . , 0, 1, 1. Now Proposition 25 shows that ∧f and ∨f are exactly (p -1)-locally monotone.

In[START_REF] Gotsman | Spectral properties of threshold functions[END_REF], local monotonicity is used to refer to Boolean functions which are monotone (i.e., isotone or antitone in each variable).

If E 1 ∩ E 2 is empty, then Alice is cheating!

Since if f is isotone (resp. antitone) in one variable, then it is isotone (resp. antitone) in all variables.

Here by a subsequence we mean a sequence of consecutive entries of the original sequence.

Acknowledgments

Miguel Couceiro and Jean-Luc Marichal are supported by the internal research project F1R-MTH-PUL-12RDO2 of the University of Luxembourg. Tamás Waldhauser is supported by the T ÁMOP-4.2.1/B-09/1/KONV-2010-0005 program of National Development Agency of Hungary, by the Hungarian National Foundation for Scientific Research under grant nos K77409 and K83219, by the National Research Fund of Luxembourg, and by the Marie Curie Actions of the European Commission (FP7-COFUND).


Miguel Couceiro

Jean-Luc Marichal

Mikhail Volkov

ACZ ÉLIAN n-ARY SEMIGROUPS

Keywords: Mathematics Subject Classification. Primary 20N15, 39B22; Secondary 20M14 n-ary semigroup, Aczélian semigroup, cancellativity, continuity

come

Introduction

Let I be a nontrivial real interval (i.e., nonempty and not a singleton) and let n ⩾ 2 be an integer. Recall that an n-ary function f ∶ I n → I is said to be associative if it solves the following system of n -1 functional equations: f (x 1 , . . . , f (x i , . . . , x i+n-1 ), x i+n , . . . , x 2n-1 ) = f (x 1 , . . . , x i , f (x i+1 , . . . , x i+n ), . . . , x 2n-1 ), i = 1, . . . , n -1.

The pair (I, f ) is then called an n-ary semigroup (see Dörnte [START_REF] Dörnte | Untersuchengen über einen verallgemeinerten Gruppenbegriff[END_REF] and Post [START_REF] Post | Polyadic groups[END_REF]).

A function f ∶ I n → I is said to be cancellative if it is one-to-one in each variable; that is, for every k ∈ [n] = {1, . . . , n} and every x = (x 1 , . . . , x n ) ∈ I n and x ′ = (x ′ 1 , . . . , x ′ n ) ∈ I n , (x i = x ′ i for all i ∈ [n] ∖ {k} and f (x) = f (x ′ )) ⇒ x k = x ′ k . Also, a function f ∶ I n → I is said to be symmetric if, for every permutation σ on [n], we have f (x 1 , . . . , x n ) = f (x σ(1) , . . . , x σ(n) ).

In this paper we present a complete description of those associative functions f ∶ I n → I which are continuous, symmetric, and cancellative. Our main result can be stated as follows.

Main Theorem. A function f ∶ I n → I is continuous, symmetric, cancellative, and associative if and only if there exists a continuous and strictly monotonic function φ∶ I → J such that

(1) f (x) = φ -1 ( n ∑ i=1 φ(x i )) ,
where J is a real interval of one of the forms

]-∞, b[, ]-∞, b], ]a, ∞[, [a, ∞[ or R = ]-∞, ∞[ (b ⩽ 0 ⩽ a).
For such a function f , I is necessarily open at least on one end. Moreover, φ can be chosen to be strictly increasing. In other words, the n-ary semigroup (I, f ) is topologically order-isomorphic to the n-ary semigroup (J, +).

The binary case (n = 2) of the Main Theorem, for which symmetry is not needed, was first stated and proved by J. Aczél [START_REF] Aczél | Sur les opérations définies pour nombres réels[END_REF]. A shorter, more technical proof of Aczél's result was then provided by Craigen and Páles [START_REF] Craigen | The associativity equation revisited[END_REF] (see also [START_REF] Aczél | The associativity equation re-revisited[END_REF] for a recent survey). The corresponding binary semigroups are called Aczélian (see Ling [START_REF] Ling | Representation of associative functions[END_REF]Section 3.2]).

We say that an n-ary semigroup is Aczélian if it satisfies the assumptions of the Main Theorem. Thus the Main Theorem provides an explicit description of the class of Aczélian n-ary semigroups. Although this result is not a trivial derivation of the binary case, we prove it by following more or less the same steps as in [START_REF] Craigen | The associativity equation revisited[END_REF].

The following example shows that the symmetry assumption is necessary for every odd integer n ⩾ 3.

Example 1.1. Let n ⩾ 3 be an odd integer. The function f ∶ R n → R, defined by

f (x) = n ∑ i=1 (-1) i-1 x i ,
is continuous, cancellative, and associative. However, it cannot be of the form [START_REF] Aczél | Sur les opérations définies pour nombres réels[END_REF] with a continuous and strictly monotonic function φ. Indeed, if the latter would be the case, then by identifying the variables, we would have f

(x n ) = x and hence φ(x) = φ(f (x n )) = n φ(x), a contradiction.
This paper is organized as follows. In Section 2 we show how n-ary associative functions can be extended to associative functions of certain higher arities. In Section 3 we provide the proof of the Main Theorem.

To avoid cumbersome notation, we henceforth regard tuples x in I n as n-strings over I and we write |x| = n. The 0-string or empty string is denoted by ε so that I 0 = {ε}. We denote by I * the set of all strings over I, that is, I * = ⋃ n∈N I n , where N = {0, 1, 2, . . .}. Moreover, we consider I * endowed with concatenation for which we adopt the juxtaposition notation. For instance, if x ∈ I n , y ∈ I, and z ∈ I m , then xyz ∈ I n+1+m . Remark 1. Using this notation, we immediately see that a function f ∶ I n → I is associative if and only if we have f (x f (y)z) = f (x ′ f (y ′ )z ′ ) for every xyz, x ′ y ′ z ′ ∈ I 2n-1 such that y, y ′ ∈ I n and xyz = x ′ y ′ z ′ . Similarly, f is cancellative if and only if, for every xz ∈ I n-1 and every y, y ′ ∈ I, the equality f (xyz) = f (xy ′ z) implies y = y ′ . For x ∈ I, we also use the short-hand notation x m = x⋯x ∈ I m . Given a function g∶ I * → I, we denote by g m the restriction of g to I m , i.e. g m ∶= g| I m . We convey that g 0 is defined by g 0 (ε) = ε.

Associative extensions

Recall that a binary function f ∶ I 2 → I is said to be associative if

f (f (xy)z) = f (xf (yz))
for all x, y, z ∈ I.

Using an infix notation, we can also write this property as

(x ◇ y) ◇ z = x ◇ (y ◇ z)
for all x, y, z ∈ I.

Since associativity expresses that the order in which variables are bracketed is not relevant, it can be easily extended to functions g∶ I * → I by defining

g m (x 1 ⋯x m ) = x 1 ◇ ⋯ ◇ x m
for every integer m ⩾ 2. The latter definition can be reformulated in prefix notation as g 2 = f and

(2)

g m (x 1 ⋯x m ) = g 2 (g 2 (⋯g 2 (g 2 (g 2 (x 1 x 2 )x 3 )x 4 )⋯)x m )
for every m > 2. Equivalently, we may write g 2 = f and

g m (x 1 ⋯x m ) = g 2 (g m-1 (x 1 ⋯x m-1 )x m )
for every m > 2.

Note that the unary function g 1 is not involved in this construction and so it could be chosen arbitrarily. However, as we will see in Proposition 2.2, it is convenient to ask g 1 to satisfy the following condition:

(3) 2) holds for every m > 2 and every x 1 , . . . , x m ∈ I, and (iii) condition ( 3) holds.

g 1 ○ g = g and g(x g 1 (y)z) = g(xyz) for all xyz ∈ I * . Definition 2.1. A function g∶ I * → I is said to be associative if (i) g 2 is associative, (ii) condition (
By definition, an associative function g∶ I * → I can always be constructed from a binary associative function f ∶ I2 → I by defining g 2 = f , using (2), and choosing a unary function g 1 satisfying (3) (e.g., the identity function).1 Such a function g, which is completely determined by g 1 and g 2 = f , will be called an associative extension of f .

The following proposition provides concise reformulations of associativity of functions g∶ I * → I and justifies condition (3). We will prove a more general statement in Proposition 2.5. The equivalence of assertions (ii)-(iv) was proved in [START_REF] Couceiro | Associative polynomial functions over bounded distributive lattices[END_REF]. Proposition 2.2. Let g∶ I * → I be a function. The following assertions are equivalent.

(i) g is associative.

(ii) g(x g(y)z) = g(x ′ g(y ′ )z ′ ) for every xyz, x ′ y ′ z ′ ∈ I * such that xyz = x ′ y ′ z ′ . (iii) g(x g(y)z) = g(xyz) for every xyz ∈ I * . (iv) g(g(x)g(y)) = g(xy) for every xy ∈ I * .
For any integer n ⩾ 2, define the sets

A n = {m ∈ N ∶ m ≡ 1 (mod n -1)} and I (n) = ⋃ m∈An I m = I × (I n-1 ) * .
Just as associativity for binary functions can be extended to functions g∶ I * → I, one can also extend the associativity of n-ary functions to functions g∶ I (n) → I as follows. 2 Given an associative function f ∶ I n → I, we define g∶ I (n) → I as g n = f and (4)

g m (x 1 ⋯x m ) = g n (g n (⋯g n (g n (x 1 ⋯x n )x n+1 ⋯x 2n-1 )⋯)x m-n+2 ⋯x m )
for every m ∈ A n and m > n. Equivalently, we may write g n = f and

g m (x 1 ⋯x m ) = g n (g m-n+1 (x 1 ⋯x m-n+1 )x m-n ⋯x m )
for every m ∈ A n and m > n.

Once again, the unary function g 1 can be chosen arbitrarily. However, we ask g 1 to satisfy the following condition:

(5) 4) holds for every m ∈ A n , m > n, and every x 1 , . . . , x m ∈ I, and (iii) condition ( 5) holds.

g 1 ○ g = g and g(x g 1 (y)z) = g(xyz) for all xyz ∈ I (n) . Definition 2.3. A function g∶ I (n) → I is said to be n-associative if (i) g n is associative, (ii) condition (
By definition, an n-associative function g∶ I (n) → I can always be constructed from an n-ary associative function f ∶ I n → I by defining g n = f , using (4), and choosing a unary function g 1 satisfying (5) (e.g., the identity function). Such a function g, which is completely determined by g 1 and g n = f , will be called an n-associative extension of f . Example 2.4. From the ternary associative function

f ∶ R 3 → R, defined by f (x 1 x 2 x 3 ) = x 1 -x 2 + x 3 , we can construct the 3-associative extension g∶ R (3) → R as g m (x 1 ⋯x m ) = m ∑ i=1 (-1) i-1 x i (m ⩾ 3, odd),
for which [START_REF] Dörnte | Untersuchengen über einen verallgemeinerten Gruppenbegriff[END_REF] provides the unique solution g 1 = id.

The following proposition generalizes Proposition 2.2 and provides concise reformulations of n-associativity of functions g∶ I (n) → I and justifies condition (5). (i) g is n-associative.

(ii) g 1 ○ g = g and g(x g(y)z) = g(x ′ g(y ′ )z ′ ) for every xyz, x ′ y ′ z ′ ∈ I (n) such that y, y ′ ∈ I (n) and xyz = x ′ y ′ z ′ . (iii) g(x g(y)z) = g(xyz) for every xyz ∈ I (n) such that y ∈ I (n) . (iv) g 1 ○ g = g and g(g(x 1 )⋯g(x n )) = g(x 1 ⋯x n ) for every x 1 , . . . , x n ∈ I (n) .

Proof. Implications (iii) ⇒ (i), (iii) ⇒ (ii), and (iii) ⇒ (iv) are easy to verify.

To prove (ii) ⇒ (iii) simply take y ′ = xyz (i.e., x ′ z ′ = ε).

Let us now prove that (iv) ⇒ (iii). Let xyz ∈ I (n) such that y ∈ I (n) . We write x g(y)z = t 1 ⋯t m , with t k = g(y). By (iv) we have

g(x g(y)z) = g(t 1 ⋯t m ) = g(g(t 1 )⋯g(t n-1 )g(t n ⋯t m )). If k ⩽ n -1, then g(x g(y)z) = g(g(t 1 )⋯g(t k )⋯g(t n-1 )g(t n ⋯t m )) = g(g(t 1 )⋯g(y)⋯g(t n-1 )g(t n ⋯t m )) = g(xyz).
If k ⩾ n, we proceed similarly with g(t n ⋯t m ), unless n = m in which case the result follows immediately.

Let us establish that (i) ⇒ (iii). We only need to prove that g(x g(y)z) = g(xyz) for every xyz ∈ I (n) such that |y| ⩾ 2 and |xz| ⩾ 1. Using (4) twice and the associativity of g n , we can rewrite the function xyz ↦ g(x g(y)z) in terms of nested g n 's only. Then, using the associativity of g n again, we can move all the g n 's to the left to obtain the right-hand side of (4), which reduces to g(xyz).

To illustrate, consider the following example with n = 3:

g(x 1 x 2 x 3 g(x 4 x 5 x 6 x 7 x 8 )x 9 ) = g(x 1 g(x 2 x 3 g(x 4 g(x 5 x 6 x 7 )x 8 ))x 9 )
= g(g(g(g(x 1 x 2 x 3 )x 4 x 5 )x 6 x 7 )x 8 x 9 )

= g(x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 ).

Remark 2. Proposition 2.2 follows from Proposition 2.5. Note that the condition g 1 ○ g = g is not needed in assertions (ii) and (iv) of Proposition 2.2 since I * is used instead of I (n) , thus allowing the use of the empty string ε.

Proof of the Main Theorem

It is easy to show that the condition in the Main Theorem is sufficient. To show that the condition is necessary, let I be a nontrivial real interval, let f ∶ I n → I be a continuous, symmetric, cancellative, and associative function, and let g∶ I (n) → I be the unique n-associative extension of f such that g 1 = id (see the observation following Definition 2.3).

Claim 1. f is strictly increasing in each variable.

Proof. Since f is continuous and cancellative, it must be strictly monotonic in each variable. Suppose it is strictly decreasing in the first variable. Then, by associativity, for every y ∈ I n-1 , u ∈ I, and v ∈ I n-2 , the unary function x ↦ f (f (xy)uv) = f (x f (yu)v) is both strictly increasing and strictly decreasing, which leads to a contradiction. Thus f must be strictly increasing in the first variable and hence in every variable by symmetry.

An element e ∈ I is said to be an idempotent for f if f (e n ) = e. For instance, any real number is an idempotent for the function defined in Example 1.1.

Claim 2. There cannot be two distinct idempotents for f . Proof. Otherwise, if d and e were distinct idempotents, we would have

f (d e n-1 ) = f (f (d n ) e n-1 ) = f (d f (d n-1 e) e n-2 )
and hence (by cancellation), e = f (d n-1 e) = f (e d n-1 ). Similarly, d = f (e n-1 d) = f (d e n-1 ). Now, if e < d, then d = f (d e n-1 ) < f (d n-1 e) = e (by Claim 1), a contradiction. We arrive at a similar contradiction if d < e.

Because of Claim 2, there is a c ∈ I such that either c < f (c n ) or c > f (c n ). We assume w.l.o.g. that the former holds and fix such a c. The latter case can be dealt with similarly. Claim 3. For all fixed x ∈ I, we have x < f (x c n-1 ). Thus the sequence x m = f (x m-1 c n-1 ) strictly increases, and lim x m ∉ I (hence lim x m = sup I and I is open from above).

Proof. Since c < f (c n ), we have f (c x n-1 ) < f (f (c n ) x n-1 ) = f (c f (c n-1 x) x n-2 ) and hence (by strict monotonicity) x < f (c n-1 x) = f (x c n-1 ). Thus x m = f (x m-1 c n-1 ) > x m-1 . If lim x m = x ′
and x ′ ∈ I, continuity gives the following:

x ′ = lim x m = lim f (x m-1 c n-1 ) = f (lim x m-1 c n-1 ) = f (x ′ c n-1 ), a contradiction. Thus x ′ ∉ I, so lim x m = sup I.
Hereinafter we work on the extended real line so that suprema of arbitrary sets exist and all monotone sequences converge. Claim 4. Let x ∈ I and let j, k, p, q ∈ N such that j + 1, k, p, q + 1 ∈ A n . Then we have

g(c p ) > g(x c q ) ⇔ g(c kp ) > g(x k c kq ) ⇔ g(c p+j ) > g(x c q+j ).
The same equivalence holds if "<" or "=" replaces ">".

Proof. Assume that g(c p ) > g(x c q ). Then, by Proposition 2.5(iv), Claim 1, and symmetry, we have g(c kp ) = g(g(c p ) k ) > g(g(x c q ) k ) = g(x k c kq ), which proves the first equivalence (since the same conclusion clearly holds if "<" or "=" replaces ">"). For the second equivalence, assume again that g(c p ) > g(x c q ). Then, as before, we have g(c p+j ) = g(g(c p ) c j ) > g(g(x c q ) c j ) = g(x c q+j ).

Let x be any fixed element of I. Define S x to be the subset of all rational numbers r for which there exist k, p, q ∈ N such that k, p, q + 1 ∈ A n , g(c p ) > g(x k c q ), and

r = (p -q)/k. Now, if r = (p -q)/k = (p ′ -q ′ )/k ′ , then we have pk ′ + q ′ k = p ′ k + qk ′ and it follows from Claim 4 that g(c p ) > g(x k c q ) ⇔ g(c pk ′ ) > g(x kk ′ c qk ′ ) ⇔ g(c pk ′ +q ′ k ) > g(x kk ′ c qk ′ +q ′ k ) ⇔ g(c p ′ k+qk ′ ) > g(x kk ′ c q ′ k+qk ′ ) ⇔ g(c p ′ k ) > g(x kk ′ c q ′ k ) ⇔ g(c p ′ ) > g(x k ′ c q ′ ).
Hence S x is in fact the subset of rational numbers r for which every representation r = (p -q)/k with k, p, q

+ 1 ∈ A n satisfies g(c p ) > g(x k c q ). Claim 5. The set S = { p-q k ∶ k, p, q + 1 ∈ A n } is dense in R. Proof. For every a, b ∈ N, the sequence x m = 1 ± a m (n -1) 1 + b m (n -1)
of S converges to ±a/b. Thus S is dense in Q and hence (by transitivity) in R.

Claim 6. Any two numbers r, r ′ ∈ S may be written r = (p -q)/k, r ′ = (p ′ -q)/k for suitable k, p, p ′ , q + 1 ∈ A n .

Proof. Let r = (p-q)/k and r ′ = (p ′ -q ′ )/k ′ , with k, k ′ , p, p ′ , q +1, q ′ +1 ∈ A n . Assume w.l.o.g. that r ′ > r. Setting k = k k ′ , q = | k r -1|, p = k r + q, and p′ = k r ′ + q, we have r = (p -q)/ k, r ′ = (p ′ -q)/ k with k, p, p′ , q + 1 ∈ A n .

Claim 7. S x is a nonempty, proper, and upper subset of S ("upper" means that if r ∈ S x and r ′ ∈ S, r ′ > r, then r ′ ∈ S x ).

Proof. To show that S x is an upper subset, let r = (p-q)/k ∈ S x and r ′ = (p ′ -q)/k > r (cf. Claim 6). Then p ′ > p and, since p, p ′ ∈ A n , we have p ′ = p + j(n -1) for some integer j ⩾ 1. Using the definition of S x and the first part of Claim 3, we obtain

g(x k c q ) < g(c p ) < g(g(c p ) c n-1 ) = g(c p c n-1 ) < g(g(c p c n-1 ) c n-1 ) = g(c p c 2(n-1) ) < ⋯ < g(c p c j(n-1) ) = g(c p ′ ).
Hence r ′ ∈ S x . Now, by Claim 3, lim f (c m(n-1)+1 ) = sup I > g(x c n-1 ), and hence there is some p ∈ A n with g(c p ) > g(x c n-1 ). Hence r = (p -(n -1))/1 ∈ S x , and so S x is nonempty. Similarly, since lim g(x c m(n-1) ) = sup I, there must a q such that q + 1 ∈ A n and g(c) < g(x c q ), and so (1 -q)/1 ∉ S x . Now, by Claim 7, S x is precisely the set of elements in S which are greater than (and possibly equal to) inf S x . Using this fact, let φ∶ I → R be the function given by φ(x) ∶= inf S x .

Claim 8. If g(c p ) = g(x k c q ), then φ(x) = (p -q)/k. In particular, φ(c) = 1.

Proof. Note that g(c p ) = g(x k c q ) implies r = (p -q)/k ∉ S x . Moreover, by Claim 7 it follows that if

r ′ = (p ′ -q)/k > r (resp. r ′ < r), then g(c p ′ ) > g(c p ) = g(x k c q ) (resp. g(c p ′ ) < g(c p ) = g(x k c q ))
, and hence r ′ ∈ S x (resp. r ′ / ∈ S x ). Thus inf S x = (p -q)/k by Claim 5. For the last claim just note that g(c q+1 ) = g(c c q ). Claim 9. We have φ(g(x

1 ⋯x n )) = ∑ n i=1 φ(x i ) for every x 1 , . . . , x n ∈ I. Proof. Let r i = (p i -q)/k > φ(x i ) for all i ∈ [n]. Then g(c pi ) > g(x k i c q )
, and by Proposition 2.5(iv), Claim 1, and symmetry, we have

g(c ∑ n i=1 pi ) = g(g(c p1 )⋯g(c pn )) > g(g(x k 1 c q )⋯g(x k n c q )) = g(g(x 1 ⋯x n ) k c nq ). By Claim 8, (∑ n i=1 p i -nq)/k ∈ S g(x1⋯xn) . Thus ∑ n i=1 r i > φ(g(x 1 ⋯x n )). Similarly, if r i ⩽ φ(x i ) for all i ∈ [n], then ∑ n i=1 r i ⩽ φ(g(x 1 ⋯x n )).
The result then follows from Claim 5.

Claim 10. φ is nondecreasing.

Proof. Suppose y > x and (p -q)/k ∈ S y . Then g(c p ) > g(y k c q ) > g(x k c q ) and hence S y ⊆ S x and so φ(y) = inf S y ⩾ inf S x = φ(x).

Claim 11. φ is continuous.

Proof. Since φ is nondecreasing, the only possible sort of discontinuity is a gap discontinuity. Hence, if φ is discontinuous, there must exist x, y ∈ I, say x < y, and an interval, and thus a rational r ∉ φ(I), such that φ(x) < r < φ(y). Now if r = (p -q)/k, then g(x k c q ) < g(c p ) ⩽ g(y k c q ). By continuity of g k+q , there is t ∈ ]x, y] such that g(c p ) = g(t k c q ). By Claim 8 it then follows that φ(t) = r, which yields the desired contradiction.

Claim 12. φ is strictly increasing.

Proof. For the sake of contradiction, suppose that there are x, y ∈ I such that x < y and φ(x) = φ(y) = a. Since φ is nondecreasing, there is an interval I ′ containing x and y, and such that φ(z) = a, for all z ∈ I ′ . Let I ′ be the largest interval having this property, and set t = sup I ′ . If t ∉ I, then for every z > x, φ(z) = a. Now g(x c n-1 ) > x (by Claim 3) and hence a = φ(g(x c n-1 )) = a + (n -1) > a (by Claim 9), a contradiction. Thus t ∈ I, and φ(t) = a by Claim 11. We have g(x t n-1 ) < g(t n ) and, by Claim 3, there exists q such that q + 1 ∈ A n and g(t n ) < g(x c q(n-1) ) = g(x g(c q ) n-1 ) and g(c q ) > t. By continuity of g n , there is z ∈ I such that t < z < g(c q ) (and so z ∉ I ′ ) and g(x z n-1 ) = g(t n ). Thus a + (n -1) φ(z) = φ(x) + (n -1) φ(z) = φ(g(x z n-1 )) = φ(g(t n )) = n φ(t) = n a , and we obtain φ(z) = a, so z ∈ I ′ , a contradiction.

Thus φ is a continuous strictly increasing n-ary semigroup homomorphism and, by Claim 9, its range J is a connected real additive n-ary semigroup. Hence the only possibilities for J are ]-∞, b[, ]-∞, b], ]a, ∞[, [a, ∞[ or ]-∞, ∞[ (b ⩽ 0 ⩽ a); see final comments in [START_REF] Craigen | The associativity equation revisited[END_REF]. This completes the proof of the Main Theorem.

Remark 3. The function φ is determined up to a multiplicative constant, that is, with φ all functions ψ = r φ (r ≠ 0) belong to the same function f , and only these; see the "Uniqueness" section in [START_REF] Aczél | The associativity equation re-revisited[END_REF]. Remark 4. An n-ary semigroup (I, f ) is said to be reducible to (or derived from) a binary semigroup (I, ◇) if there is an associative extension g∶ I * → I of ◇ such that g n = f ; that is, f (x 1 ⋯x n ) = x 1 ◇ ⋯ ◇ x n (see [START_REF] Dörnte | Untersuchengen über einen verallgemeinerten Gruppenbegriff[END_REF][START_REF] Post | Polyadic groups[END_REF]). Dudek and Mukhin [START_REF] Dudek | On n-ary semigroups with adjoint neutral element[END_REF] showed that an n-ary semigroup is reducible if and only if we can adjoint an n-ary neutral element to it. This shows that the n-ary semigroup given in Example 1.1 is not reducible since we cannot adjoint any n-ary neutral element (for an alternative proof, see [START_REF] Marichal | A description of n-ary semigroups polynomial-derived from integral domains[END_REF]). However, the Main Theorem shows that every Aczélian n-ary semigroup is reducible and hence we can always adjoint an n-ary neutral element to it (if 0 ∈ J, then the neutral element is e = φ -1 (0); otherwise fix e ∉ I and extend φ to φ ′ ∶ I ∪ {e} → J ∪ {0} by the rule φ ′ (x) = φ(x) if x ∈ I and φ ′ (e) = 0).

Proposition 2 . 5 .

 25 Let g∶ I (n) → I be a function. The following assertions are equivalent.

Note that g 1 necessarily solves the idempotency equation g 1 ○ g 1 = g 1 .

This construction is inspired from Dörnte[START_REF] Dörnte | Untersuchengen über einen verallgemeinerten Gruppenbegriff[END_REF] and Post[START_REF] Post | Polyadic groups[END_REF].

Acknowledgments

The authors wish to thank Judita Dascȃl, Pierre Mathonet, and Michel Rigo for helpful comments and suggestions. We would also like to thank the referee for bringing to our attention reference [6], which provides a necessary and sufficient condition for an n-ary semigroup to be reducible. This research is supported by the internal research project F1R-MTH-PUL-09MRDO of the University of Luxembourg.