On Shapley Values and Threshold Intervals
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929706377412608 |
|---|---|
| author | Kalai, Gil Lifshitz, Noam |
| author_facet | Kalai, Gil Lifshitz, Noam |
| contents | Let $f\colon \{0,1\}^n\to \{0,1\}$ be a monotone Boolean functions, let $ψ_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 $ψ_k(f) \le t$ for all $k$, then the threshold interval of $f$ has length $\displaystyle 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 $\displaystyle \max_{k} ψ_k(f) \le O\left(\frac {\log \log (1/t)}{\log(1/t)}\right) $. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05990 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Shapley Values and Threshold Intervals Kalai, Gil Lifshitz, Noam Combinatorics Probability Let $f\colon \{0,1\}^n\to \{0,1\}$ be a monotone Boolean functions, let $ψ_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 $ψ_k(f) \le t$ for all $k$, then the threshold interval of $f$ has length $\displaystyle 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 $\displaystyle \max_{k} ψ_k(f) \le O\left(\frac {\log \log (1/t)}{\log(1/t)}\right) $. |
| title | On Shapley Values and Threshold Intervals |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2502.05990 |