# Expected Shapley Value is Shapley Value for Expected Utility Game

Pratik Karmakar, Antoine Gauquier, Pierre Senellart

► To cite this version:

Pratik Karmakar, Antoine Gauquier, Pierre Senellart. Expected Shapley Value is Shapley Value for Expected Utility Game. ECSQARU 2025 - 18th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Sep 2025, Hagen, Germany. hal-05177852

HAL Id: hal-05177852

https://inria.hal.science/hal-05177852v1

Submitted on 23 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Expected Shapley Value is
Shapley Value for Expected Utility Game

Pratik Karmakar<sup>1,2[0009-0008-1111-8801]</sup>, Antoine Gauquier<sup>3[0009-0005-9573-6364]</sup>,
and Pierre Senellart<sup>2,3,4,5[0000-0002-7909-5369]</sup>

¹ National University of Singapore, Singapore

² CNRS@CREATE Ltd, Singapore

³ DI ENS, ENS, PSL University, CNRS, Inria, Paris, France

⁴ Institut Universitaire de France, France

⁵ IPAL, CNRS, Singapore

**Abstract.** The Shapley value provides a principled framework for attributing marginal contributions to players in coalitional games. While its axiomatic fairness guarantees have made it a cornerstone of value distribution in economics and multi-agent systems, recent computational advances have extended its applicability to data-driven domains. This paper bridges game-theoretic foundations with probabilistic reasoning by studying Shapley-like scores in stochastic environments. We prove that the *expected Shapley value (EShap)* – a player’s average impact in a game with an independent probabilistic setting – coincides with the Shapley value of the game whose utility is the expected utility of the original game (*ShapE*). This equality, however, *fails* for other power indices, such as the Banzhaf index, underscoring the Shapley value’s specificity of consistency in uncertain settings. We further identify that for a certain class of coefficients (including normalized Banzhaf indices) the equality persists, broadening the scope of reliable attribution mechanisms.

**Keywords:** Shapley value, probabilistic game, probabilistic database

# 1 Introduction

In coalitional games, the Shapley value [13] resolves a fundamental question: how to fairly distribute collective gains among players based on their marginal contributions. Its axiomatic foundation – efficiency, symmetry, linearity, and null-player invariance – has made it a gold standard for attribution in domains ranging from cost allocation in economics [12], to feature importance [9] and data valuation [5] in explainable AI. Central to its adoption is the ability to compute player-specific values that reflect their *average contribution* across all possible player orderings.

Modern applications increasingly demand reasoning under uncertainty, where players (or, in data-centric settings [2,7], data elements) participate stochastically. Consider a probabilistic coalitional game where each player *i* is available to join a coalition with independent probability *p*ᵢ. In such a stochastic setting, the
expected contribution of a player participating in a coalition can be estimated by the expected value (over all randomized subgames) of the Shapley value of this player, i.e., its *expected Shapley Value* [3,7] (EShap). Recent work [7] demonstrated that EShap and its Banzhaf variant (EBanz) can be computed in **polynomial time** when the utility of the game can be described by a Boolean function with specific characteristics (e.g., read-once, or admitting a deterministic and decomposable circuit decomposition), unlocking applications in scenarios ranging from reliability analysis in decentralized systems to responsibility attribution in probabilistic databases [14].

But another natural way of quantifying the contribution of a player in a stochastic environment is to compute the Shapley value of that player for the game whose utility function is the *expected utility* of that player in a coalition; we denote this alternate definition as ShapE. For example, in a probabilistic database setting such as that of [14,7], EShap is the expected Shapley value (over all possible sub-databases with their probabilities) of a tuple in making a query true, while ShapE represents the Shapley value of that tuple for the game whose utility is the probability a coalition satisfies the query.

While both EShap and ShapE measure influence, it is a *priori* unclear whether they are related – the former averages contributions across subgames, while the latter applies Shapley’s axioms directly to expected utility.

*Contributions.* We resolve this question as follows:

- **Equality for Shapley values:** We prove EShap = ShapE (Section 4). This equality validates the consistency of Shapley-based attribution in probabilistic environments, from cooperative games to data management.

- **Non-equality for Banzhaf values:** Interestingly, this result is not just a consequence of the linearity of expected value. Indeed, we show that for some other Shapley-like values, such as Banzhaf values [1], equality doesn't hold (Section 5). However, for *normalized* Banzhaf indices, equality does hold, with a different proof as for Shapley values (Section 6).

After briefly describing related work in Section 2, we introduce in Section 3 all relevant notions. In Section 4, we prove the equality. In Section 5, we show that the equality does not hold in general for arbitrary Shapley-like scores (and in particular for Banzhaf values). In Section 6, we discuss other cases where equality holds. Before concluding, we discuss in Section 7 the setting of non-independent probabilistic games.

## 2 Related Work

The Shapley value has been widely studied for fair attribution in cooperative games, with extensions to probabilistic settings gaining recent attention. Borko-tokey et al. [3] and Karmakar et al. [7] formally define the expected Shapley value in games where coalition participation is stochastic, showing it satisfies natural axioms and coincides with intuitive influence measures.
From a computational perspective, Deutch et al. [4] and Karmakar et al. [7] link Shapley value computation to probabilistic inference in databases, leveraging provenance circuits for tractable query evaluation. These approaches allow efficient computation of expected Shapley scores over some tractable Boolean functions under uncertainty.

Other game-theoretic works, such as those by Miranda and Montes [10] and Pongou and Tondji [11], reinterpret Shapley and Banzhaf values as expectations under different coalition distributions. In AI, Shapley values have been extended to uncertain environments for data and feature attribution [9], though such applications typically rely on sampling and heuristic methods.

Our work complements these by proving a formal equality: the expected Shapley value (EShap) equals the Shapley value of the expected utility (ShapE) (which, to the best of our knowledge has not been specifically studied so far). As a consequence, we inherit tractability results from [7].

## 3 Definitions

We begin by introducing the notion of marginal contribution through a class of player scoring functions based on coefficients, which we call Shapley-like scores as in [7]. Let $c: \mathbb{N} \times \mathbb{N} \to \mathbb{Q}$ be a function, referred to as a coefficient function, and let $v: 2^{\mathbb{N}} \to \mathbb{R}$ be a utility function defined on coalitions of a finite set $N$ of players, with $i \in N$. We define the score of player $i$ with coefficients $c$ in the game as:

$$ \text{Score}_c(v, N, i) \stackrel{\text{def}}{=} \sum_{C \subseteq N \setminus \{i\}} c(|N|, |C|) \times [v(C \cup \{i\}) - v(C)] $$

This generic formulation encompasses well-known coefficient functions from cooperative game theory:

- When $c(k, \ell) = c_{\text{Shapley}}(k, \ell) \stackrel{\text{def}}{=} \frac{\ell!(k-\ell-1)!}{k!} = \left[ \binom{k-1}{\ell} \cdot k \right]^{-1}$, $\text{Score}_c(v, N, i)$ corresponds to the classical Shapley value.

- When $c(k, \ell) = c_{\text{Banzhaf}}(k, \ell) \stackrel{\text{def}}{=} 1$, $\text{Score}_c(v, N, i)$ corresponds to the Banzhaf value.

- The Penrose-Banzhaf index (a standard normalization of the Banzhaf value $[8]$) corresponds to $c(k, \ell) = 2^{-k+1}$.

In the context of this work, we consider a player-independent probabilistic game $G = (N, (p_i)_{i \in N})$, where $p_i$ is the probability that player $i$ participates in a random instance of the game. See Section 7 for a discussion of the non-independent setting.

We also use the following notation: $\Pi_Z(C) \stackrel{\text{def}}{=} \prod_{j \in C} p_j \prod_{j \in Z \setminus C} (1 - p_j)$ for $C$ and $Z$ two sets of players.

For $i \in N$ and some utility function $v$ (i.e., a function from coalitions of players to $\mathbb{R}$ indicating the utility of this coalition), EShap($v, G, i$) is the expected
Shapley value of player $i$ for utility $v$ in $\mathcal{G}$. The expectation is taken over all possible participating coalitions $Z$:

$$
\begin{align*}
\mathrm{EShap}(v, \mathcal{G}, i) &\stackrel{\text{def}}{=} \sum_{Z \subseteq N, i \in Z} (\Pi_N(Z) \times \mathrm{Score}_{c_{\mathrm{Shapley}}}(v, Z, i)) \\
&= \sum_{Z \subseteq N, i \in Z} \left( \Pi_N(Z) \times \sum_{C \subseteq Z \setminus \{i\}} c_{\mathrm{Shapley}}(|Z|, |C|) \times [v(C \cup \{i\}) - v(C)] \right) \\
&= p_i \times \sum_{Z \subseteq N \setminus \{i\}} \left( \Pi_{N \setminus \{i\}}(Z) \times \sum_{C \subseteq Z} c_{\mathrm{Shapley}}(|Z| + 1, |C|) \times [v(C \cup \{i\}) - v(C)] \right) \\
&= p_i \times \sum_{C \subseteq N \setminus \{i\}} (v(C \cup \{i\}) - v(C)) \left( \sum_{C \subseteq Z \subseteq N \setminus \{i\}} c_{\mathrm{Shapley}}(|Z| + 1, |C|) \Pi_{N \setminus \{i\}}(Z) \right)
\end{align*}
$$

For a utility function $v$, a probabilistic game $\mathcal{G} = (N, (p_i)_{i \in N})$ and a player $i$, we now define $\mathrm{ShapE}(v, \mathcal{G}, i)$ as the Shapley value of $i$ in $N$ with a value function that maps a coalition $Z$ to the expected value (under $\mathcal{G}$) of the utility $v$:

$$
\begin{align*}
\mathrm{ShapE}(v, \mathcal{G}, i) &\stackrel{\text{def}}{=} \sum_{Z \subseteq N \setminus \{i\}} c_{\mathrm{Shapley}}(|N|, |Z|) \times (\mathbb{E}_{\mathcal{G}}(v(Z \cup \{i\})) - \mathbb{E}_{\mathcal{G}}(v(Z))) \\
&= \sum_{Z \subseteq N \setminus \{i\}} c_{\mathrm{Shapley}}(|N|, |Z|) \left( \sum_{C_1 \subseteq Z \cup \{i\}} \Pi_{Z \cup \{i\}}(C_1) v(C_1) - \sum_{C_2 \subseteq Z} \Pi_{Z}(C_2) v(C_2) \right) \\
&= \sum_{Z \subseteq N \setminus \{i\}} c_{\mathrm{Shapley}}(|N|, |Z|) \left( \sum_{C_1' \subseteq Z} p_i \Pi_{Z}(C_1') v(C_1' \cup \{i\}) \right. \\
&\qquad \left. + \sum_{C_1'' \subseteq Z} (1-p_i) \Pi_{Z}(C_1'') v(C_1'' - \sum_{C_2' \subseteq Z} p_i \Pi_{Z}(C_2') v(C_2') \right) \\
&= \sum_{Z \subseteq N \setminus \{i\}} c_{\mathrm{Shapley}}(|N|, |Z|) \left( \sum_{C_1' \subseteq Z} p_i \Pi_{Z}(C_1') v(C_1' \cup \{i\}) - \sum_{C_1'' \subseteq Z} p_i \Pi_{Z}(C_1'') v(C_1'' - \sum_{C_2'' \subseteq Z} p_i \Pi_{Z}(C_2'') v(C_2'') \right) \\
&\qquad + \sum_{C_1'' \subseteq Z} \Pi_{Z}(C_1'') v(C_1'' - \sum_{C_2'' \subseteq Z} \Pi_{Z}(C_2'') v(C_2'') \right) \\
&= \sum_{Z \subseteq N \setminus \{i\}} c_{\mathrm{Shapley}}(|N|, |Z|) \left( \sum_{C \subseteq Z} p_i \Pi_{Z}(C) v(C \cup \{i\}) - \sum_{C \subseteq Z} p_i \Pi_{Z}(C) v(C) \right) \\
&= p_i \times \sum_{Z \subseteq N \setminus \{i\}} c_{\mathrm{Shapley}}(|N|, |Z|) \left( \sum_{C \subseteq Z} \Pi_{Z}(C) (v(C \cup \{i\}) - v(C)) \right) \\
&= p_i \times \sum_{C \subseteq N \setminus \{i\}} (v(C \cup \{i\}) - v(C)) \left( \sum_{C \subseteq Z \subseteq N \setminus \{i\}} c_{\mathrm{Shapley}}(|N|, |Z|) \times \Pi_{Z}(C) \right)
\end{align*}
$$
## 4 Equality between EShap and ShapE

We prove in this section that EShap and ShapE are actually equal. We note that this is non-trivial, and in particular not a simple consequence of the linearity of the expected value, but critically relies on the combinatorial structure of the Shapley coefficients $c_{\text{Shapley}}$. For arbitrary score functions (e.g., Banzhaf), this equality fails, as shown in Section 5. Formally:

**Proposition 1.** For any probabilistic game $\mathcal{G} = (N, (p_i)_{i \in N})$, any utility function $v$ over $N$, and any player $i \in N$, we have:

$$ \text{EShap}(v, \mathcal{G}, i) = \text{ShapE}(v, \mathcal{G}, i) $$

*Proof.* To prove the equality of EShap and ShapE we have to show:

$$ \begin{aligned} & p_i \times \sum_{C \subseteq N \setminus \{i\}} (v(C \cup \{i\}) - v(C)) \left( \sum_{C \subseteq Z \subseteq N \setminus \{i\}} c_{\text{Shapley}}(|Z| + 1, |C|) \times \prod_{N \setminus \{i\}} (Z) \right) \\ & \stackrel{?}{=} p_i \times \sum_{C \subseteq N \setminus \{i\}} (v(C \cup \{i\}) - v(C)) \left( \sum_{C \subseteq Z \subseteq N \setminus \{i\}} c_{\text{Shapley}}(|N|, |Z|) \times \prod_{Z}(C) \right) \end{aligned} $$

For any fixed coalition $C$, it suffices to show that the coefficients of $(v(C \cup \{i\}) - v(C))$ in both expressions are equal, that is:

$$ \underbrace{\sum_{C \subseteq Z \subseteq N \setminus \{i\}} c_{\text{Shapley}}(|Z| + 1, |C|) \times \prod_{N \setminus \{i\}} (Z)}_{\text{LHS}} \stackrel{?}{=} \underbrace{\sum_{C \subseteq Z \subseteq N \setminus \{i\}} c_{\text{Shapley}}(|N|, |Z|) \times \prod_{Z}(C)}_{\text{RHS}} \quad (1) $$

To show the equality of the above-mentioned coefficients, we view the expressions on the left-hand side (LHS) and right-hand side (RHS) as polynomials over the $(p_j)_{j \in N}$ variables. Consider the expansion of these polynomials into sums of monomials; it is clear that all monomials involved will be factors of $\prod_{j \in C} p_j$. We can thus rewrite LHS and RHS as sums of monomials with corresponding coefficients, in the form:

$$ \text{LHS} = \sum_{C \subseteq X \subseteq N \setminus \{i\}} C_{C,X}^{(1)} \times \text{Prod}(X) $$

and

$$ \text{RHS} = \sum_{C \subseteq X \subseteq N \setminus \{i\}} C_{C,X}^{(2)} \times \text{Prod}(X) $$

where $\text{Prod}(X) = \prod_{j \in X} p_j$, and $C_{C,X}^{(1)}$ and $C_{C,X}^{(2)}$ are the coefficients of $\text{Prod}(X)$

in LHS and RHS, respectively. We now show that $C_{C,X}^{(1)} = C_{C,X}^{(2)}$, for any fixed coalition $C$ and any $X \supseteq C$.
Computing $C_{C,X}^{(1)}$.

$$ \text{LHS} = \sum_{C \subseteq Z \subseteq N \setminus \{i\}} c_{\text{Shapley}}(|Z| + 1, |C|) \Pi_{N \setminus \{i\}}(Z) = \sum_{C \subseteq X \subseteq N \setminus \{i\}} C_{C,X}^{(1)} \times \text{Prod}(X) $$

Let us expand $\Pi_{N \setminus \{i\}}(Z)$ as a sum of monomials over the $(p_j)_{j \in N}$:

$$ \Pi_{N \setminus \{i\}}(Z) = \prod_{j \in Z} p_j \times \prod_{j \in N \setminus \{i\} \setminus Z} (1 - p_j) = \sum_{Z \subseteq X \subseteq N \setminus \{i\}} (-1)^{|X|-|Z|} \times \text{Prod}(X) $$

Thus, for any $X$, the coefficient of $\text{Prod}(X)$ in LHS is:

$$ \begin{aligned} C_{C,X}^{(1)} &= \sum_{C \subseteq Z \subseteq X} (-1)^{|X|-|Z|} \times c_{\text{Shapley}}(|Z| + 1, |C|) \\ &= \sum_{k=|C|}^{|X|} (-1)^{|X|-k} \times \binom{|X|-|C|}{k-|C|} \times c_{\text{Shapley}}(k+1, |C|) \end{aligned} $$

We then compute:

$$ \begin{aligned} & \binom{|X| - |C|}{k - |C|} \times c_{\text{Shapley}}(k + 1, |C|) \\ &= \frac{(|X| - |C|)!}{(k - |C|)! (|X| - k)!} \times \frac{(k - |C|)! |C|!}{k!} \times \frac{1}{k + 1} \\ &= \frac{|X|! (|X| - |C|)! |C|!}{k! (|X| - k)! |X|!} \times \frac{1}{k + 1} \\ &= \frac{\binom{|X|}{k}}{\binom{|X|}{|C|}} \times \frac{1}{k + 1} \end{aligned} $$

Thus:

$$ \begin{aligned} C_{C,X}^{(1)} &= \sum_{k=|C|}^{|X|} (-1)^{|X|-k} \times \binom{|X|}{k} \times \frac{1}{k+1} \\ &= \frac{(-1)^{|X|}}{\binom{|X|}{|C|}} \sum_{k=|C|}^{|X|} (-1)^k \binom{|X|}{k} \times \frac{1}{k+1} \\ &= \frac{(-1)^{|X|}}{\binom{|X|}{|C|}} \sum_{k=|C|}^{|X|} (-1)^k \frac{|X|!}{k! (|X|-k)!} \times \frac{1}{k+1} \\ &= \frac{(-1)^{|X|}}{\binom{|X|}{|C|} (|X|+1)} \sum_{k=|C|}^{|X|} (-1)^k \frac{(|X|+1)!}{(k+1)! (|X|-k)!} \\ &= \frac{(-1)^{|X|}}{\binom{|X|}{|C|}} \times \frac{1}{|X|+1} \sum_{k=|C|}^{|X|} (-1)^k \binom{|X|+1}{k+1} \end{aligned} $$
Then:

$$
\begin{align*}
\sum_{k=|C|}^{|X|} (-1)^k \binom{|X|+1}{k+1} &= \sum_{j=|C|+1}^{|X|+1} (-1)^{j-1} \binom{|X|+1}{j} = - \sum_{j=|C|+1}^{|X|+1} (-1)^j \binom{|X|+1}{j} \\
&= \sum_{j=0}^{|C|} (-1)^j \binom{|X|+1}{j} \quad \left[ \text{Using the binomial expansion of } (1+x)^{|X|+1} \right]_{x=-1} \\
&= \binom{|X|}{0} + \sum_{j=1}^{|C|} (-1)^j \left( \binom{|X|}{j-1} + \binom{|X|}{j} \right) \quad \left[ \therefore \binom{n}{r} + \binom{n}{r-1} = \binom{n+1}{r} \right] \\
&= \binom{|X|}{0} - \left( \binom{|X|}{0} + \binom{|X|}{1} \right) + \left( \binom{|X|}{1} + \binom{|X|}{2} \right) - \left( \binom{|X|}{2} + \binom{|X|}{3} \right) \\
&\quad + \dots + (-1)^{|C|-1} \left( \binom{|X|}{|C|-2} + \binom{|X|}{|C|-1} \right) + (-1)^{|C|} \left( \binom{|X|}{|C|-1} + \binom{|X|}{|C|} \right) \\
&= (-1)^{|C|} \binom{|X|}{|C|}
\end{align*}
$$

Therefore, we get:

$$
\begin{align}
C_{C,X}^{(1)} &= \frac{(-1)^{|X|}}{\binom{|X|}{|C|}} \times \frac{1}{|X|+1} \times (-1)^{|C|} \binom{|X|}{|C|} = (-1)^{|X|+|C|} \frac{1}{|X|+1} \nonumber \\
&= (-1)^{|X|-|C|} \frac{1}{|X|+1} \quad [\because (|X| + |C|) \bmod 2 = (|X| - |C|) \bmod 2] \tag{2}
\end{align}
$$

Computing $C_{C,X}^{(2)}$.

$$
\text{RHS} = \sum_{C \subseteq Z \subseteq N \setminus \{i\}} c_{\text{Shapley}}(|N|, |Z|) \times \Pi_Z(C) = \sum_{C \subseteq X \subseteq N \setminus \{i\}} C_{C,X}^{(2)} \times \text{Prod}(X)
$$

Let us expand $\Pi_Z(C)$ as a sum of monomials over the $(p_j)_{j \in N}$:

$$
\Pi_Z(C) = \prod_{j \in C} p_j \times \prod_{j \in Z} (1 - p_j) = \sum_{C \subseteq X \subseteq Z} (-1)^{|X|-|C|} \times \text{Prod}(X)
$$

Thus, for any $X$, the coefficient of $\text{Prod}(X)$ in LHS is:

$$
\begin{align*}
C_{C,X}^{(2)} &= \sum_{X \subseteq Z \subseteq N \setminus \{i\}} (-1)^{|X|-|C|} \times c_{\text{Shapley}}(|N|, |Z|) \\
&= (-1)^{|X|-|C|} \sum_{t=|X|}^{|N|-1} \binom{|N|-1-|X|}{t-|X|} \times c_{\text{Shapley}}(|N|, t)
\end{align*}
$$
We then compute:

$$ 
\begin{aligned}
& \binom{|N|-1-|X|}{t-|X|} \times c_{\text{Shapley}}(|N|, t) \\
&= \frac{(|N|-1-|X|)!}{(t-|X|)!(|N|-1-t)!} \times \frac{t!(|N|-1-t)!}{(|N|-1)!} \times \frac{1}{|N|} \\
&= \frac{(|N|-1-|X|)! \times t! \times |X|!}{(t-|X|)!(|N|-1)! \times |X|!} \times \frac{1}{|N|} \\
&= \frac{\binom{t}{|X|}}{\binom{|N|-1}{|X|}} \times \frac{1}{|N|}
\end{aligned}
$$

Thus:

$$ 
\begin{aligned}
C_{C,X}^{(2)} &= (-1)^{|X|-|C|} \sum_{t=|X|}^{|N|-1} \frac{\binom{t}{|X|}}{\binom{|N|-1}{|X|}} \times \frac{1}{|N|} \\
&= (-1)^{|X|-|C|} \times \frac{1}{\binom{|N|-1}{|X|}} \times \frac{1}{|N|} \sum_{t=|X|}^{|N|-1} \binom{t}{|X|} \\
&= (-1)^{|X|-|C|} \times \frac{1}{\binom{|N|-1}{|X|}} \times \frac{1}{|N|} \times \binom{|N|}{|X|+1} \quad [\text{Hockey-stick identity}] \\
&= (-1)^{|X|-|C|} \frac{1}{|X|+1} \qquad (3)
\end{aligned}
$$

From Equations (2) and (3) we have that $C_{C,X}^{(1)} = C_{C,X}^{(2)}$ for any $X \supseteq C$, which shows that LHS = RHS in Equation (1), and concludes the proof. □

**Example 1.** Let us inspect a simple example with set of players $N = \{1, 2, 3\}$ associated with probabilities $p_1 = 0.3$, $p_2 = 0.6$, $p_3 = 0.7$. Define the utility function $v$ such that: $v(\emptyset) = 0$, $v(\{1\}) = 1$, $v(\{2\}) = 2$, $v(\{3\}) = 3$, $v(\{1, 2\}) = 7$, $v(\{1, 3\}) = 9$, $v(\{2, 3\}) = 11$, and $v(\{1, 2, 3\}) = 14$. We compute for player 1:

$$ 
\begin{aligned}
\text{EShap}(v, \mathcal{G}, 1) &= p_1 \left[ \begin{aligned}
& \Pi_{\{2,3\}}(\emptyset) c_{\text{Shapley}}(1,0)(v(\{1\}) - v(\emptyset)) \\
& + \Pi_{\{2,3\}}(\{2\}) (c_{\text{Shapley}}(2,0)(v(\{1\}) - v(\emptyset)) + c_{\text{Shapley}}(2,1)(v(\{1,2\}) - v(\{2\}))) \\
& + \Pi_{\{2,3\}}(\{3\}) (c_{\text{Shapley}}(2,0)(v(\{1\}) - v(\emptyset)) + c_{\text{Shapley}}(2,1)(v(\{1,3\}) - v(\{3\}))) \\
& + \Pi_{\{2,3\}}(\{2,3\}) (c_{\text{Shapley}}(3,0)(v(\{1\}) - v(\emptyset))c_{\text{Shapley}}(3,1)(v(\{1,2\}) - v(\{2\}))) \\
& + c_{\text{Shapley}}(3,1)(v(\{1,3\}) - v(\{3\})) + c_{\text{Shapley}}(3,2)(v(\{1,2,3\}) - v(\{2,3\}))
\end{aligned} \right]
\end{aligned}
$$
$$
\begin{align*}
\text{ShapE}(v, \mathcal{G}, 1) &= p_1 \left[ c_{\text{Shapley}}(3, 0) \left( \Pi_{\emptyset}(\emptyset)(v(\{1\}) - v(\emptyset)) \right. \right. \\
&\qquad \left. + c_{\text{Shapley}}(3, 1) \left( \Pi_{\{2\}}(\emptyset)(v(\{1\}) - v(\emptyset)) + \Pi_{\{2\}}(\{2\})(v(\{1, 2\}) - v(\{2\})) \right. \right. \\
&\qquad \left. + c_{\text{Shapley}}(3, 1) \left( \Pi_{\{3\}}(\emptyset)(v(\{1\}) - v(\emptyset)) + \Pi_{\{3\}}(\{3\})(v(\{1, 3\}) - v(\{2\})) \right) \right. \\
&\qquad \left. + c_{\text{Shapley}}(3, 2) \left( \Pi_{\{2,3\}}(\emptyset)(v(\{1\}) - v(\emptyset)) + \Pi_{\{2,3\}}(\{2\})(v(\{1, 2\}) - v(\{2\})) \right. \right. \\
&\qquad \left. + \Pi_{\{2,3\}}(\{3\})(v(\{1, 3\}) - v(\{3\})) + \Pi_{\{2,3\}}(\{2, 3\})(v(\{1, 2, 3\}) - v(\{2, 3\})) \right] \\
&= 0.891
\end{align*}
$$

We then inherit the tractability results about EShap from [7] (Corollary 3.7):

**Corollary 1.** Let $\mathcal{G} = (N, (p_i)_{i \in N})$ be a probabilistic game, and let $v$ be a Boolean utility function over $N$ in any class of Boolean functions whose probability can be computed in polynomial time (e.g., read-once functions, or functions given by a deterministic and decomposable circuits). Then $\text{ShapE}(v, \mathcal{G}, i)$ can also be computed in polynomial time.

## 5 Inequality for Unnormalized Banzhaf Values

Note that Proposition 1 is specific to Shapley value, it does not hold for arbitrary other common score functions such as Banzhaf values:

**Proposition 2.** Proposition 1 does not hold when the Shapley coefficient function is replaced with the Banzhaf coefficient function $((k, \ell) \mapsto 1)$.

*Proof.* Consider a simple setting where $N$ is formed of three players $f, g, h$ with probabilities $p_f, p_g$, and $1$, respectively, and $v$ returns $1$ if and only if at least two among the players $\{f, g, h\}$ are in the coalition, $0$ otherwise. We compute $\text{EBanz}(v, \mathcal{G}, h)$ and $\text{BanzE}(v, \mathcal{G}, h)$ for the Banzhaf coefficient function and show they differ.

$$
\begin{align*}
\text{EBanz}(v, \mathcal{G}, h) &= \Pi_N(\{f, g, h\}) \times \text{Score}_{c_{\text{Banzhaf}}}(v, \{f, g, h\}, h) \\
&\quad + \Pi_N(\{f, h\}) \times \text{Score}_{c_{\text{Banzhaf}}}(v, \{f, h\}, h) \\
&\quad + \Pi_N(\{g, h\}) \times \text{Score}_{c_{\text{Banzhaf}}}(v, \{g, h\}, h) \\
&= p_f p_g \times 2 \times c(3, 1) + (p_f(1 - p_g) + p_g(1 - f)) \times c(2, 1)
\end{align*}
$$

$$ \text{BanzE}(v, \mathcal{G}, h) = c(3, 2) \times (p_f(1 - p_g) + p_g(1 - p_f)) + c(3, 1) \times (p_f + p_g) $$

Let us fix $p_f = \frac{1}{4}$ and $p_g = \frac{1}{2}$. Then, for the Banzhaf coefficient function, $\text{EBanz}(v, \mathcal{G}, h)$ and $\text{BanzE}(v, \mathcal{G}, h)$ evaluate, respectively, to $\frac{1}{4} + \frac{1}{8} + \frac{3}{8} = \frac{3}{4}$ and to $\frac{1}{8} + \frac{3}{8} + \frac{1}{4} + \frac{1}{2} = \frac{5}{4} \neq \frac{3}{4}$. $\square$
# 6 Equality for Normalized Banzhaf Values

In the previous section, we demonstrated that the equality EShap = ShapE is specific to the classical Shapley value and does not extend to the Banzhaf index. However, a natural question arises: can this equality exist for other power indices that, similarly to Banzhaf values, can be expressed as Shapley-like values with a specific coefficient function? In this section, we show that it is indeed the case for the standard normalization of the Banzhaf value, sometimes called the Penrose-Banzhaf index [8], i.e., with coefficient function $c'(k, \ell) = 2^{-k+1}$. Note that, in a probabilistic setting, the number of available players is not constant, so the expected score EScore for this coefficient function is not a constant normalization of EBanz (however, ScoreE is a normalization of BanzE!). We show that Proposition 1 holds for this index too.

Though the details of the proof are different, we follow the same coefficient comparison strategy as in Section 4. First, we compute the coefficient $C_{C,X}^{(1)}$ of the monomial Prod($X$) in the expansion of the LHS expression (expected score under the probabilistic model), using the modified coefficient $c'(k, \ell) = 2^{-k+1}$.

Computing $C_{C,X}^{(1)}$. The expression of $C_{C,X}^{(1)}$ for $c'$ index is as follows:

$$
\begin{align*}
C_{C,X}^{(1)} &= \sum_{C \subseteq Z \subseteq X} (-1)^{|X|-|Z|} \times c'(|Z| + 1, |C|) \\
&= \sum_{k=|C|}^{|X|} (-1)^{|X|-k} \times \binom{|X|-|C|}{k-|C|} \times c'(k+1, |C|) \\
&= (-1)^{|X|} \sum_{k=|C|}^{|X|} (-1)^{-k} \times \binom{|X|-|C|}{k-|C|} \times 2^{-k} \\
&= (-1)^{|X|} \sum_{k=|C|}^{|X|} \left(-\frac{1}{2}\right)^k \times \binom{|X|-|C|}{k-|C|} \\
&= (-1)^{|X|} \sum_{j=0}^{|X|-|C|} \left(-\frac{1}{2}\right)^{j+|C|} \times \binom{|X|-|C|}{j} \quad [j = k - |C|] \\
&= (-1)^{|X|-|C|} \times 2^{-|C|} \sum_{j=0}^{|X|-|C|} \left(-\frac{1}{2}\right)^j \times \binom{|X|-|C|}{j} \\
&= (-1)^{|X|-|C|} \times 2^{-|C|} \left(1 - \frac{1}{2}\right)^{|X|-|C|} \\
&= (-1)^{|X|-|C|} \times 2^{-|C|} \times 2^{|C|-|X|} \\
&= (-1)^{|X|-|C|} \times 2^{-|X|}
\end{align*}
$$
Next, we compute the corresponding coefficient $C_{C,X}^{(2)}$ in the RHS expression, that is, the monomial coefficient in the Normalized Banzhaf index applied to the expected utility function.

Computing $C_{C,X}^{(2)}$. The expression of $C_{C,X}^{(2)}$ for $c'$ index is as follows:

$$
\begin{align*}
C_{C,X}^{(2)} &= \sum_{X \subseteq Z \subseteq N \setminus \{i\}} (-1)^{|X|-|C|} \times c'(|N|, |Z|) \\
&= (-1)^{|X|-|C|} \sum_{t=|X|}^{|N|-1} \binom{|N|-1-|X|}{t-|X|} \times c'(|N|, t) \\
&= (-1)^{|X|-|C|} \sum_{t=|X|}^{|N|-1} \binom{|N|-1-|X|}{t-|X|} \times 2^{-|N|+1} \\
&= (-1)^{|X|-|C|} \times 2^{-|N|+1} \sum_{t=|X|}^{|N|-1} \binom{|N|-1-|X|}{t-|X|} \\
&= (-1)^{|X|-|C|} \times 2^{-|N|+1} \sum_{r=0}^{|N|-1-|X|} \binom{|N|-1-|X|}{r} \quad [r = t - |X|] \\
&= (-1)^{|X|-|C|} \times 2^{-|N|+1} \times 2^{|N|-1-|X|} \\
&= (-1)^{|X|-|C|} \times 2^{-|X|}
\end{align*}
$$

Thus, $C_{C,X}^{(1)} = C_{C,X}^{(2)}$. Consequently, the expected index of players in a probabilistic game for $c'$ is identical to the index of the game success-probability score function for $c'$.

*Generalization.* Motivated by the previous findings, we now investigate more generalized coefficient functions of the form $c(k, \ell) = a^{-k+m}$, where $a, m \in \mathbb{R}$ is a parameter. This allows us to analyze under what values of $a$ the Proposition 1 holds.

We again follow the coefficient comparison approach and derive necessary conditions on $a$ for the equality $EScore_c = ScoreE_c$.

$$
\begin{align*}
C_{C,X}^{1} &= \sum_{C \subseteq Z \subseteq X} (-1)^{|X|-|Z|} \times c(|Z| + 1, |C|) \\
&= \sum_{k=|C|}^{|X|} (-1)^{|X|-k} \binom{|X|-|C|}{k-|C|} \times c(k+1, |C|) \\
&= \sum_{s=0}^{|X|-|C|} (-1)^{|X|-s-|C|} \binom{|X|-|C|}{s} \times c(s+|C|+1, |C|)
\end{align*}
$$
$$
\begin{align*}
C_{C,X}^2 &= \sum_{X \subseteq Z \subseteq N \setminus \{f\}} (-1)^{|X|-|C|} \times c(|N|, |Z|) \\
&= (-1)^{|X|-|C|} \sum_{t=|X|}^{|N|-1} \binom{|N|-1-|X|}{t-|X|} \times c(|N|, t) \\
&= (-1)^{|X|-|C|} \sum_{r=0}^{|N|-1-|X|} \binom{|N|-1-|X|}{r} \times c(|N|, r+|X|)
\end{align*}
$$

For equality between $C_{C,X}^1$ and $C_{C,X}^2$, now we write:

$$
\begin{align*}
& \sum_{s=0}^{|X|-|C|} (-1)^{|X|-s-|C|} \binom{|X|-|C|}{s} \times c(s+|C|+1, |C|) \\
&= (-1)^{|X|-|C|} \sum_{r=0}^{|N|-1-|X|} \binom{|N|-1-|X|}{r} \times c(|N|, r+|X|) \\
\iff & (-1)^{|X|-|C|} \sum_{s=0}^{|X|-|C|} (-1)^{-s} \binom{|X|-|C|}{s} \times c(s+|C|+1, |C|) \\
&= (-1)^{|X|-|C|} \sum_{r=0}^{|N|-1-|X|} \binom{|N|-1-|X|}{r} \times c(|N|, r+|X|) \\
\iff & \sum_{s=0}^{|X|-|C|} (-1)^{-s} \binom{|X|-|C|}{s} a^{-s-|C|-1+m} = \sum_{r=0}^{|N|-1-|X|} \binom{|N|-1-|X|}{r} a^{-|N|+m} \\
\iff & a^{-|C|-1+m} \sum_{s=0}^{|X|-|C|} \left(-\frac{1}{a}\right)^s \binom{|X|-|C|}{s} = a^{-|N|+m} \sum_{r=0}^{|N|-1-|X|} \binom{|N|-1-|X|}{r} \\
\iff & a^{-|C|-1+m} \mu \times \left(1-\frac{1}{a}\right)^{|X|-|C|} = a^{-|N|+m} \times 2^{|N|-1-|X|} \\
\iff & a^{|N|-1-|X|} \times (a-1)^{|X|-|C|} = 2^{|N|-1-|X|} \\
\iff & \left(\frac{a}{2}\right)^{|N|-1-|X|} \times (a-1)^{|X|-|C|} = 1
\end{align*}
$$

For this equation to hold, the only possible value of $a$ is 2, and $m$ can take
any arbitrary value.

7 Non-Independent Players

We have assumed so far (see Section 3) that probabilistic games are *player-independent*, i.e., that the participation of a player *i* in a probabilistic game is independent of the participation of every other player. The proof of equality between EShap and ShapE crucially relies on the form of $\Pi_Z(C)$ for independent
probability distributions; it is unclear whether it could be extended to (some) dependent settings. We leave this as exploration for future work.

However, we note that arbitrary dependencies between players can be captured in the utility function, on which we made no assumption. This observation is analogous to the observation made in [6] in the settings of probabilistic databases, where views defined by arbitrary queries over tuple-independent databases can represent any arbitrary correlations. In other words, any player-dependent probabilistic game can be transformed into an equivalent player-independent probabilistic game, and even into an equivalent non-probabilistic game.

**Proposition 3.** Consider an arbitrary probabilistic game $\mathcal{G} = (N, \mathrm{Pr})$, where $N$ is a finite set of players and $\mathrm{Pr} : 2^N \to [0, 1]$ is an arbitrary probability distribution over $2^N$. Let $v : 2^N \to \mathbb{R}$ be some utility function. Then there exists a player-independent probabilistic game $\mathcal{G}' = (N, (p'_i)_{i \in N})$ over $N$ and a utility function $v' : 2^N \to \mathbb{R}$ such that, for any $Z \subseteq N$, $\mathbb{E}_{\mathcal{G}}(v(Z)) = \mathbb{E}_{\mathcal{G}'}(v'(Z))$.

Furthermore, one can choose $p'_i$ to be all equal to some constant $\alpha > 0$, including $\alpha = 1$ (which means the game becomes non-probabilistic and $\mathbb{E}_{\mathcal{G}'}(v'(Z)) = v'(Z)$).

*Proof.* Let $Z \subseteq N$. We have:

$$ \mathbb{E}_{\mathcal{G}}(v(Z)) = \sum_{C \subseteq N} \mathrm{Pr}(C) \times v(C \cap Z) = \sum_{C \subseteq Z} v(C) \left( \sum_{X \subseteq N-Z} \mathrm{Pr}(C \cup X) \right) $$

We need to define $v'(C)$ for any $C \subseteq N$ such that, for any $Z \subseteq N$:

$$ \sum_{C \subseteq Z} v'(C) \prod_{j \in C} p'_j \prod_{j \in Z \setminus C} (1 - p'_j) = \sum_{C \subseteq Z} v(C) \left( \sum_{X \subseteq N-Z} \mathrm{Pr}(C \cup X) \right) $$

We pose $p'_i \stackrel{\mathrm{def}}{=} \alpha$ for all $i \in N$, yielding:

$$ \sum_{C \subseteq Z} v'(C) \alpha^{|Z|} = \sum_{C \subseteq Z} v(C) \left( \sum_{X \subseteq N-Z} \mathrm{Pr}(C \cup X) \right) $$

This holds if we define $v'(Z)$ inductively by:

$$ \left\{ \begin{array}{l} v'(\emptyset) \stackrel{\mathrm{def}}{=} v(\emptyset) \\ v'(Z) \stackrel{\mathrm{def}}{=} \alpha^{-|Z|} \sum_{C \subseteq Z} v(C) \left( \sum_{X \subseteq N-Z} \mathrm{Pr}(C \cup X) \right) - \sum_{C \subseteq Z} v'(C) \quad \text{for } Z \neq \emptyset \quad \Box \end{array} \right. $$

This transformation, however, loses most of the structure of the game; for instance, if the utility function is a Boolean utility function given in a simple form, the transformed game will generally not be of the same nature and Corollary 1 cannot be applied.
# 8 Conclusion

We have proven that the Expected Shapley value (EShap) for player-independent probabilistic games equals the Shapley value of the expected utility game (ShapE), illustrating the robustness of Shapley's axioms under uncertainty. We contrasted this result with the unnormalized Banzhaf index, where the equality fails, and showed it is restored only after normalizing it.

Our findings help apply game-theoretic fairness principles to probabilistic reasoning confirming expected Shapley value (and Shapley value of the expected game) as a principled attribution tool in stochastic settings beyond the Boolean settings studied in the probabilistic database literature. Future directions include finding a complete characterization of the coefficient family that preserves the $EScore = ScoreE$ equality and investigating the case of games that are not player-independent.

Miranda et al. [10] show that Shapley and normalized Banzhaf values can serve as probability transformations under imprecise probabilities, providing fairness and consistency under certain conditions. Exploring connections with our results is a direction for future work.

# Acknowledgment

We are grateful to Benny Kimelfeld for suggesting investigating the connection between EShap and ShapE and to Stefano Moretti for discussions on this problem. This research is part of the DesCartes program and is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) program. It is also supported by the French government under management of Agence Nationale de la Recherche as part of the PRAIRIE-PSAI project.

# References

1. Banzhaf III, J.F.: Weighted voting doesn't work: A mathematical analysis. Rutgers Law Review **19**, 317 (1964)

2. Bertossi, L.E., Kimelfeld, B., Livshits, E., Monet, M.: The Shapley value in database management. CoRR abs/2401.06234 (2024). https://doi.org/10.48550/ARXIV.2401.06234

3. Borkotokey, S., Gowala, S., Kumar, R.: The expected Shapley value on a class of probabilistic games. arXiv abs/2308.03489 (2023), http://arxiv.org/abs/2308.03489

4. Deutch, D., Frost, N., Kimelfeld, B., Monet, M.: Computing the shapley value of facts in query answering. In: Ives, Z.G., Bonifati, A., Abbadi, A.E. (eds.) SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022. pp. 1570-1583. ACM (2022). https://doi.org/10.1145/3514221.3517912
5. Ghorbani, A., Zou, J.Y.: Data Shapley: Equitable valuation of data for machine learning. In: Chaudhuri, K., Salakhutdinov, R. (eds.) Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, CA, USA. Proceedings of Machine Learning Research, vol. 97, pp. 2242-2251. PMLR (2019), http://proceedings.mlr.press/v97/ghorbani19c.html

6. Jha, A.K., Suciu, D.: Probabilistic databases with MarkoViews. Proc. VLDB Endow. 5(11), 1160-1171 (2012). https://doi.org/10.14778/2350229.2350236, http://vldb.org/pvldb/vol5/p1160_abhayjha_vldb2012.pdf

7. Karmakar, P., Monet, M., Senellart, P., Bressan, S.: Expected Shapley-like scores of Boolean functions: Complexity and applications to probabilistic databases. Proc. ACM Manag. Data 2(2), 92 (2024). https://doi.org/10.1145/3651593, https://doi.org/10.1145/3651593

8. Kirsch, W., Langner, J.: Power indices and minimal winning coalitions. CoRR abs/0806.3906 (2008), http://arxiv.org/abs/0806.3906

9. Lundberg, S.M., Lee, S.: A unified approach to interpreting model predictions. In: Guyon, I., von Luxburg, U., Bengio, S., Wallach, H.M., Fergus, R., Vishwanathan, S.V.N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA. pp. 4765-4774 (2017), https://proceedings.neurips.cc/paper/2017/hash/8a20a8621978632d76c43dfd28b67767-Abstract.html

10. Miranda, E., Montes, I.: Shapley and Banzhaf values as probability transformations. Int. J. Uncertain. Fuzziness Knowl. Based Syst. 26(6), 917-947 (2018). https://doi.org/10.1142/S0218488518500411

11. Pongou, R., Tondji, J.: Valuing inputs under supply uncertainty: The Bayesian Shapley value. Games Econ. Behav. 108, 206-224 (2018). https://doi.org/10.1016/J.GEB.2017.08.005

12. Roth, A.E., Verrecchia, R.E.: The Shapley value as applied to cost allocation: A reinterpretation. Journal of Accounting Research pp. 295-303 (1979)

13. Shapley, L.S.: A value for n-person games. Annals of Mathematics Study (28), 307-317 (1953)

14. Suciu, D., Olteanu, D., Ré, C., Koch, C.: Probabilistic Databases. Synthesis Lectures on Data Management, Morgan & Claypool Publishers (2011). https://doi.org/10.2200/S00362ED1V01Y201105DTM016