References of "Discrete Applied Mathematics"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailSet-reconstructibility of Post classes
Couceiro, Miguel UL; Lehtonen, Erkko UL; Schölzel, Karsten UL

in Discrete Applied Mathematics (2015), 187

Detailed reference viewed: 36 (1 UL)
Full Text
Peer Reviewed
See detailInfluence and interaction indexes for pseudo-Boolean functions: a unified least squares approach
Marichal, Jean-Luc UL; Mathonet, Pierre UL

in Discrete Applied Mathematics (2014), 179

The Banzhaf power and interaction indexes for a pseudo-Boolean function (or a cooperative game) appear naturally as leading coefficients in the standard least squares approximation of the function by a ... [more ▼]

The Banzhaf power and interaction indexes for a pseudo-Boolean function (or a cooperative game) appear naturally as leading coefficients in the standard least squares approximation of the function by a pseudo-Boolean function of a specified degree. We first observe that this property still holds if we consider approximations by pseudo-Boolean functions depending only on specified variables. We then show that the Banzhaf influence index can also be obtained from the latter approximation problem. Considering certain weighted versions of this approximation problem, we introduce a class of weighted Banzhaf influence indexes, analyze their most important properties, and point out similarities between the weighted Banzhaf influence index and the corresponding weighted Banzhaf interaction index. We also discuss the issue of reconstructing a pseudo-Boolean function from prescribed influences and point out very different behaviors in the weighted and non-weighted cases. [less ▲]

Detailed reference viewed: 108 (6 UL)
Full Text
Peer Reviewed
See detailPivotal decompositions of functions
Marichal, Jean-Luc UL; Teheux, Bruno UL

in Discrete Applied Mathematics (2014), 174

We extend the well-known Shannon decomposition of Boolean functions to more general classes of functions. Such decompositions, which we call pivotal decompositions, express the fact that every unary ... [more ▼]

We extend the well-known Shannon decomposition of Boolean functions to more general classes of functions. Such decompositions, which we call pivotal decompositions, express the fact that every unary section of a function only depends upon its values at two given elements. Pivotal decompositions appear to hold for various function classes, such as the class of lattice polynomial functions or the class of multilinear polynomial functions. We also define function classes characterized by pivotal decompositions and function classes characterized by their unary members and investigate links between these two concepts. [less ▲]

Detailed reference viewed: 126 (9 UL)
Full Text
Peer Reviewed
See detailLocally monotone Boolean and pseudo-Boolean functions
Couceiro, Miguel UL; Marichal, Jean-Luc UL; Waldhauser, Tamás UL

in Discrete Applied Mathematics (2012), 160(12), 1651-1660

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 ... [more ▼]

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 p-permutable 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. [less ▲]

Detailed reference viewed: 75 (3 UL)
Full Text
Peer Reviewed
See detailThe arity gap of order-preserving functions and extensions of pseudo-Boolean functions
Couceiro, Miguel UL; Lehtonen, Erkko UL; Waldhauser, Tamás UL

in Discrete Applied Mathematics (2012), 160(4-5), 383-390

The aim of this paper is to classify order-preserving functions according to their arity gap. Noteworthy examples of order-preserving functions are the so-called aggregation functions. We first explicitly ... [more ▼]

The aim of this paper is to classify order-preserving functions according to their arity gap. Noteworthy examples of order-preserving functions are the so-called aggregation functions. We first explicitly classify the Lovász extensions of pseudo-Boolean functions according to their arity gap. Then we consider the class of order-preserving functions between partially ordered sets, and establish a similar explicit classification for this function class. [less ▲]

Detailed reference viewed: 57 (4 UL)
Full Text
Peer Reviewed
See detailWeighted lattice polynomials of independent random variables
Marichal, Jean-Luc UL

in Discrete Applied Mathematics (2008), 156(5), 685-694

We give the cumulative distribution functions, the expected values, and the moments of weighted lattice polynomials when regarded as real functions of independent random variables. Since weighted lattice ... [more ▼]

We give the cumulative distribution functions, the expected values, and the moments of weighted lattice polynomials when regarded as real functions of independent random variables. Since weighted lattice polynomial functions include ordinary lattice polynomial functions and, particularly, order statistics, our results encompass the corresponding formulas for these particular functions. We also provide an application to the reliability analysis of coherent systems. [less ▲]

Detailed reference viewed: 49 (3 UL)
Full Text
Peer Reviewed
See detailApproximations of Lovász extensions and their induced interaction index
Marichal, Jean-Luc UL; Mathonet, Pierre UL

in Discrete Applied Mathematics (2008), 156(1), 11-24

The Lovász extension of a pseudo-Boolean function f : {0,1}^n --> R is defined on each simplex of the standard triangulation of [0,1]^n as the unique affine function \hat f : [0,1]^n --> R that ... [more ▼]

The Lovász extension of a pseudo-Boolean function f : {0,1}^n --> R is defined on each simplex of the standard triangulation of [0,1]^n as the unique affine function \hat f : [0,1]^n --> R that interpolates f at the n+1 vertices of the simplex. Its degree is that of the unique multilinear polynomial that expresses f. In this paper we investigate the least squares approximation problem of an arbitrary Lovász extension \hat f by Lovász extensions of (at most) a specified degree. We derive explicit expressions of these approximations. The corresponding approximation problem for pseudo-Boolean functions was investigated by Hammer and Holzman and then solved explicitly by Grabisch, Marichal, and Roubens, giving rise to an alternative definition of Banzhaf interaction index. Similarly we introduce a new interaction index from approximations of \hat f and we present some of its properties. It turns out that its corresponding power index identifies with the power index introduced by Grabisch and Labreuche. [less ▲]

Detailed reference viewed: 46 (0 UL)
Full Text
Peer Reviewed
See detailAxiomatic characterizations of generalized values
Marichal, Jean-Luc UL; Kojadinovic, Ivan; Fujimoto, Katsushige

in Discrete Applied Mathematics (2007), 155(1), 26-43

In the framework of cooperative game theory, the concept of generalized value, which is an extension of that of value, has been recently proposed to measure the overall influence of coalitions in games ... [more ▼]

In the framework of cooperative game theory, the concept of generalized value, which is an extension of that of value, has been recently proposed to measure the overall influence of coalitions in games. Axiomatizations of two classes of generalized values, namely probabilistic generalized values and generalized semivalues, which extend probabilistic values and semivalues, respectively, are first proposed. The axioms we utilize are based on natural extensions of axioms involved in the axiomatizations of values. In the second half of the paper, special instances of generalized semivalues are also axiomatized. [less ▲]

Detailed reference viewed: 62 (2 UL)
Full Text
Peer Reviewed
See detailThe influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making
Marichal, Jean-Luc UL

in Discrete Applied Mathematics (2000), 107(1-3), 139-164

The power of players in a collective decision process is a central issue in game theory. For this reason, the concept of influence of players on a simple game has been introduced. More generally, the ... [more ▼]

The power of players in a collective decision process is a central issue in game theory. For this reason, the concept of influence of players on a simple game has been introduced. More generally, the influence of variables on Boolean functions has been defined and studied. We extend this concept to pseudo-Boolean functions, thus making it possible to appraise the degree of influence of any coalition of players in cooperative games. In the case of monotone games, we also point out the links with the concept of interaction among players. Although they do not have the same meaning at all, both influence and interaction functions coincide on singletons with the so-called Banzhaf power index. We also define the influence of variables on continuous extensions of pseudo-Boolean functions. In particular, the Lovász extension, also called discrete Choquet integral, is used in multicriteria decision making problems as an aggregation operator. In such problems, the degree of influence of decision criteria on the aggregation process can then be quite relevant information. We give the explicit form of this influence for the Choquet integral and its classical particular cases. [less ▲]

Detailed reference viewed: 66 (4 UL)