The influence of variables on pseudo-Boolean functions with applications to game theory and multicriteria decision making (Q1841886): Difference between revisions

The paper analyzes situations in which each of \(n\) participants can make a binary (``yes''-``no'') decision \(x_i\), and the outcome \(f(x)\) of these decisions \(x=(x_1,\ldots,x_n)\) is characterized by a real number. The function \(f\) that maps Boolean vectors \(x\) into real numbers is called a pseudo-Boolean function. In such a situation, how can we gauge the influence of a coalition \(S\subseteq\{1,\ldots,n\}\)? For each selection \(x_{-S}\) of decisions \(x_j\), \(j\not\in S\), it is natural to characterize the influence as the width of the interval \(\Delta(x_{-S}) =[\min_{x_S} f(x_S,x_{-S}), \max_{x_S} f(x_S,x_{-S})]\) of possible values of \(f\). If we do not know the decisions of the participants outside \(S\), it is reasonable to consider all these \(2^{n-s}\) possible decisions \(x_{-S}\) and define the influence \(I_f(S)\) of the coalition \(S\) as the arithmetic average of the corresponding widths \(\Delta(x_{-S})\). For a cooperative game in which the decision \(x_i\) is whether to join the coalition or not, the outcome \(f(x)\) can be defined as the guaranteed gain \(v(S)\) corresponding to the resulting coalition \(S=\{i\mid x_i=1\}\); then, the above ``influence'' coincides with the Banzhaf power index. Instead of describing the function \(f\) by its values \(f(x)\), we can describe it by the coefficients \(a(T)\) of its Taylor series expansion \(f(x)=\sum a(T)\cdot \prod_{i\in T}x_i\); these coefficients \(a(T)\) form a Möbius transform of \(f\). It turns out that the influence can be explicitly described in terms of this Möbius transform: \(I_f(S)= \sum_{T\cap S\neq\emptyset}a(T)\cdot 2^{-|T\backslash S|}.\) Every function \(f:\{0,1\}^n\to R\) can be extended to \([0,1]^n\) (e.g., as a multi-linear function). For this extension, we can also define the influence as the average range. The authors show how the resulting influence is related to the influence of the original pseudo-Boolean function. As an interesting practical application, they consider the design of a voting system in which all coalition have influence. It is worth mentioning that from this viewpoint, majority voting is not optimal -- because minority has no influence.