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

DOI10.1016/J.DAM.2014.05.039zbMATH Open1312.91010arXiv1201.3543OpenAlexW2048314759MaRDI QIDQ477327FDOQ477327

Authors: Jean-Luc Marichal, Pierre Mathonet 

Publication date: 3 December 2014

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

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.

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

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

zbMATH Keywords

cooperative gameleast squares approximationpseudo-Boolean functioninteraction indexpower indexinfluence index

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• 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
• Approximations of pseudo-Boolean functions; applications to game theory

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)