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

The Banzhaf power and interaction indexes for a pseudo-Boolean function
(or a cooperative game) appear naturally as leading coefficients in the stan-
dard least squares approximation of the function by a pseudo-Boolean func-
tion 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 cer-
tain 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.