Approximations of Lovász extensions and their induced interaction index

The Lovász extension of a pseudo-Boolean function f:{0,1}n→Rf:{0,1}n→R is defined on each simplex of the standard triangulation of [0,1]n[0,1]n as the unique affine function f^:[0,1]n→R that interpolates f   at the n+1n+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 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 [Approximations of pseudo-Boolean functions; applications to game theory, Z. Oper. Res. 36(1) (1992) 3–21] and then solved explicitly by Grabisch et al. [Equivalent representations of set functions, Math. Oper. Res. 25(2) (2000) 157–178], giving rise to an alternative definition of Banzhaf interaction index. Similarly we introduce a new interaction index from approximations of 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 [How to improve acts: an alternative representation of the importance of criteria in MCDM, Internat. J. Uncertain. Fuzziness Knowledge-Based Syst. 9(2) (2001) 145–157].