Influence and interaction indexes for pseudo-Boolean functions: a unified least squares approach

DOI10.1016/J.DAM.2014.05.039MaRDI QIDQ477327zbMATH OpenOpenAlexFDO

Authors Jean-Luc Marichal, Pierre Mathonet

Publication date 3 December 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.3543

zbMATH Keywords

cooperative gameleast squares approximationpseudo-Boolean functioninteraction indexpower indexinfluence index

Mathematics Subject Classification ID

Cooperative games (91A12) Boolean programming (90C09) Boolean functions (06E30)

Abstract: 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.

Recommendations

• Weighted Banzhaf power and interaction indexes through weighted approximations of games
• Symmetric approximations of pseudo-Boolean functions with applications to influence indexes
• Approximations of Lovász extensions and their induced interaction index
• The influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making
• Equivalent representations of set functions

Cites work

• scientific article; zbMATH DE number 4179164 (Why is no real title available?)
• scientific article; zbMATH DE number 4162686 (Why is no real title available?)
• scientific article; zbMATH DE number 5504150 (Why is no real title available?)
• scientific article; zbMATH DE number 3249560 (Why is no real title available?)
• An axiomatic approach to the concept of interaction among players in cooperative games
• Approximations of pseudo-Boolean functions; applications to game theory
• Axiomatic characterizations of generalized values
• Axiomatic characterizations of probabilistic and cardinal-probabilistic interaction indices
• Equivalent representations of set functions
• Multilinear Extensions of Games
• The influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making
• Transforms of pseudo-Boolean random variables
• Value Theory Without Efficiency
• Weighted Banzhaf power and interaction indexes through weighted approximations of games

Cited in

(7)

• Approximations of pseudo-Boolean functions; applications to game theory
• Measuring the interactions among variables of functions over the unit hypercube
• Approximations of Lovász extensions and their induced interaction index
• Symmetric approximations of pseudo-Boolean functions with applications to influence indexes
• Weighted Banzhaf power and interaction indexes through weighted approximations of games
• Equivalent representations of set functions
• The influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making

This page was built for publication: Influence and interaction indexes for pseudo-Boolean functions: a unified least squares approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477327)