On Shapley Values and Threshold Intervals

Abstract

Let $f:\{0,1{\}}^n\to \{0,1\}$ be a monotone Boolean functions, let $\ddot{I}{ˆ}_k(f)$ denote the Shapley value of the $k$th variable and $b_k(f)$ denote the Banzhaf value (influence) of the $k$th variable. We prove that if we have $\ddot{I}{ˆ}_k(f)\le t$ for all $k$, then the threshold interval of $f$ has length $O\left(\frac{1}{\log (1/t)}\right)$. We also prove that if $f$ is balanced and $b_k(f)\le t$ for every $k$, then $\underset{k}{\max }\ddot{I}{ˆ}_k(f)\le O\left(\frac{\log \log (1/t)}{\log (1/t)}\right)$.