1 Introduction

The Shapley value, introduced by Shapley (1953), is a well-known solution concept for cooperative games that has attracted enormous attention by scholars; see, for instance, Roth (1988), Monderer and Samet (2002), Winter (2002), and Moretti and Patrone (2008). It was defined following a deductive approach, as the unique function satisfying some axioms. From those axioms Shapley derived the explicit well-known formula for his value in terms of the marginal contributions of players. Other remarkable characterizations of the Shapley value are given in Young (1985) and Casajus (2014).

In section 6 of his work, Shapley describes a bargaining procedure that produces the value of the game as an expected outcome. In the bargain, players agree to play the game and form the grand coalition N in the following way: (1) starting with a single player, the coalition adds one player at a time until everyone has been admitted. (2) The order in which players join the coalition is determined by chance, with all arrangements equally probable. (3) Each player, on his admission, demands and is promised the amount his or her adherence to the group contributes to the value of the coalition (as determined by the characteristic function).

The Shapley–Shubik index, introduced in Shapley and Shubik (1954), restricts the Shapley value to simple games. Shapley and Shubik adapted the bargaining procedure proposed by Shapley (1953) for cooperative games to simple games. That method has been criticized rightly by several authors as highly artificial (see, for instance, Luce and Raiffa 1957 or Brams 1975). However, an alternative model was not proposed until 42 years later when Felsenthal and Machover (1996) published their work. The deductive approach instead had to wait for 21 years, until Dubey (1975) was able to replace the additivity axiom with the transfer axiom to characterize the Shapley–Shubik index uniquely for simple games.

In the seminal bargaining procedure for simple games by Shapley and Shubik, players, usually called voters therein, are willing to vote for some bill, they vote in a randomly chosen order and all n! orderings are equally likely. As soon as the proposal is approved, the last voter is the pivotal player who takes credit for having passed it. The Shapley–Shubik index is the ratio of the number of times the player is pivotal under that scheme to n! (the total number of orderings). The index indeed is the probability of each player being pivotal and, thus, it always is a number between 0 and 1. Moreover, Shapley and Shubik noticed that their index also is a measure of the power of players in blocking a resolution: if we suppose that players are queuing in all possible orderings to vote against the proposal, then the Shapley–Shubik index is the ratio of the number of times the player is the last needed in order to block the bill to n!.

However, in simple games it does not seem natural to expect all voters to vote in the same way (either all of them “yes” or all of them “no”). According to Felsenthal and Machover (1996), the natural bargaining procedure in such a context should allow voters to vote for any of the two options, while the idea of pivotal voter, as the one who clinches the outcome, should still be the same. They closed that gap in 1996 and established the appropriate bargaining procedure for simple games. Although their approach also is valid for cooperative games, it is simple games for which the bargaining model has the most trustworthy interpretation.

Felsenthal and Machover (1996) proved that their value for cooperative games satisfies the axioms of the Shapley value and the equivalence of the two values therefore followed. As they wrote in their paper, they avoided a “direct” proof by proving the equivalence of the two expressions derived from the two bargaining procedures for the Shapley–Shubik index. That direct approach, as noted by Felsenthal and Machover (1996), implies a “combinatorial fact that is certainly non-trivial, and may be of some independent interest”. In this paper, we provide a proof of the direct result.

The rest of the paper is organized as follows. Section 2 contains the preliminaries. Section 3 provides the two results of the paper with their respective proofs. Section 4, the Conclusion, highlights the findings of the paper.

2 Preliminaries

Let N be a finite fixed set of cardinality n. The elements of N are called players, while a subset of N is called coalition. A coalitional game is a function \(v{:}2^{N}\rightarrow {\mathbb {R}}\) such that \(v(\emptyset )=0.\) The dual \(v^{*}\) of a game v is defined as \(v^{*}(S)=v(N)-v(N\smallsetminus S)\). We denote the set of all coalitional games on the set N by \({{\mathcal {C}}}{{\mathcal {G}}}_{N}\). A simple voting game is a coalitional game that assumes values only in \(\{0,1\}\), is monotonic (that is, \(S\subset T\implies v(S)\le v(T)\)) and such that \(v(N)=1\). A coalition S is winning if \(v(S)=1\); otherwise it is losing.

In the following we mainly use the notation from Felsenthal and Machover (1996). Let s and d (short for sinister and dexter) denote the left-hand and right-hand projections from the Cartesian product of two finite sets \(A\times B\), that is, \(s(a,b)=a\) and \(d(a,b)=b\). A roll-call is a map \(R{:}N\rightarrow \{1,2,\dots ,n\}\times \{-1,1\}\), such that sR is a bijection from N to \(\{1,2,\dots ,n\}\). Thus, sR induces a total order on N and \(sR(a)=i\) means that a is the \(i^{th}\) to vote. If \(dR(a)=1\) we say that a is positive in R, meaning that a votes “yes” in R; if \(dR(a)=-1\) we say that a is negative in R, meaning that a votes “no”.

Let \({\mathcal {R}}\) be the set of all roll-calls, \({\mathcal {R}}^{+}\) be the set of roll-calls for which all players are positive, and \({\mathcal {R}}^{-}\) be the set of roll-calls for which all players are negative. It holds that \(|{\mathcal {R}}|=2^{n}n!\) and \(|{\mathcal {R}}^{+}|=|{\mathcal {R}}^{-}|=n!\).

Given a roll-call R, the sets of positive and negative players in R are the following: \({\mathcal {Y}}(R)=\{x\in N{:}dR(x)=1\}\) and \({\mathcal {N}}(R)=\{x\in N{:}dR(x)=-1\}.\) For any player a, we also will use the sets of positive and negative players who do not vote after a: \({\mathcal {Y}}(R,a)=\{x\in N{:}dR(x)=1\wedge sR(x)\le sR(a)\}\) and \({\mathcal {N}}(R,a)=\{x\in N{:}dR(x)=-1\wedge sR(x)\le sR(a)\}\). Given a roll-call R and a player a, the marginal contribution of a to \(v({\mathcal {Y}}(R))\) is defined as

$$\begin{aligned} M(v,R,a)={\left\{ \begin{array}{ll} v({\mathcal {Y}}(R,a))-v({\mathcal {Y}}(R,a){\setminus} \{a\}) &{}\quad \text {if }\ dR(a)=1\\ v^{*}({\mathcal {N}}(R,a))-v^{*}({\mathcal {N}}(R,a){\setminus} \{a\}) &{}\quad \text {if }\ dR(a)=-1. \end{array}\right. } \end{aligned}$$
(1)

The basic idea behind Eq. (1) is that a positive player a expects to receive his marginal contribution to the coalition formed by those positive players preceding him, while a negative player a expects to receive his marginal contribution to the coalition formed by the union of those positive players preceding him and all players voting after him, no matter if they are positive or negative players. If we regard v(N) as the total gain players can get by being positive players or as the total blocking ability that negative players can exert, then M(v, R, a) is the marginal contribution a player expects in his turn in the queue according to his yes/no choice.

2.1 The Shapley value

The Shapley value is a function \(\phi{:}{{\mathcal {C}}}{{\mathcal {G}}}_{N}\rightarrow {\mathbb {R}}^{n}\), that assigns to each player a real number \(\phi _{a}(v)\). Shapley (1953) and Shubik (1962) defined this function following a deductive procedure, by showing that it is uniquely characterized by the axioms of efficiency, null player, symmetry and additivity. In Section 6 of the former paper, he also showed that \(\phi _{a}(v)\) is the expected value of M(v, R, a) in the space of positive roll-calls, \({\mathcal {R}}^{+}\).

Theorem 1

(Shapley 1953) For any player \(a\in N\),

$$\begin{aligned} \phi _{a}(v)=\sum _{R\in {\mathcal {R}}^{+}}\frac{M(v,R,a)}{n!}. \end{aligned}$$
(2)

On the other hand, Felsenthal and Machover (1996) proved that \(\phi _{a}(v)\) is the expected value of M(v, R, a) in the space of roll-calls, \({\mathcal {R}}\).

Theorem 2

(Felsenthal and Machover 1996) For any player \(a\in N\),

$$\begin{aligned} \phi _{a}(v)=\sum _{R\in {\mathcal {R}}}\frac{M(v,R,a)}{2^{n}n!}. \end{aligned}$$
(3)

The new interpretation given by Felsenthal and Machover is particularly interesting in the context of simple games modeling a voting situation. Observe that for each \(R\in {\mathcal {R}}\) a unique voter a exists such that \(M(v,R,a)=1\), while \(M(v,R,x)=0\) for all \(x\ne a\). This player a is pivotal in R for the game v and we write \(a=piv(v,R)\). The pivotal player likewise can be characterized as the first player a such that if \({\mathcal {Y}}(R)\) wins in v then \({\mathcal {Y}}(R,a)\) wins in v, and if \({\mathcal {Y}}(R)\) loses in v then \(N{\smallsetminus} {\mathcal {N}}(R,a)\) loses in v.

From Theorem 1 and the definition of pivotal player it follows:

Corollary 1

For any simple game v and player \(a\in N\)

$$\begin{aligned} \phi _{a}(v)=\frac{|\{R\in {\mathcal {R}}^{+}{:}a=piv(v,R)\}|}{n!}. \end{aligned}$$
(4)

From Theorem 2, Felsenthal and Machover (1996) deduced the following:

Corollary 2

For any simple game v and player \(a\in N\)

$$\begin{aligned} \phi _{a}(v)=\frac{|\{R\in {\mathcal {R}}{:}a=piv(v,R)\}|}{2^{n}n!}. \end{aligned}$$
(5)

They remarked that formulas (3) and (5) are not useful from a practical computational point of view, while their value is conceptual. Formula (2) has an equivalent expression, in terms of the marginal contributions of the characteristic function, which is used widely to compute the Shapley value:

$$\begin{aligned} \phi _{a}(v)=\sum _{S\subseteq {N\smallsetminus \{a\}}}\rho ^{n}(s)[v(S\cup \{a\})-v(S)], \end{aligned}$$
(6)

where \(s=|S|\) and \(\rho ^{n}(s)=\frac{s!(n-s-1)!}{n!}\). The coefficient \(\rho ^{n}(s)\), for each coalition \(S\subseteq N\setminus \{a\}\), is the rate of positive roll-calls that assign to player a the marginal contribution \(v(S\cup \{a\})-v(S)\). The expression (6) is more compact and thus more suitable for the computation of the value.

Theorem 3

(Shapley 1953) The explicit formula (6) for \(\phi\) is equivalent to (2) for cooperative games and to (4) for simple games.

It would be interesting to derive an expression analogous to (6) in terms of marginal contributions equivalent to (3). Of course, if such an expression exists, it should be equivalent to (6) since as proved by Felsenthal and Machover (1996) expressions (2) and (3) are equivalent. This equivalent expression also would be useful to deduce (5) and would constitute an alternative proof of the Felsenthal and Machover (1996) result, not requiring reference to axioms.

A second interest in obtaining that potential formula is the following. As (3) is generalizable to ternary voting games (see Felsenthal and Machover 1997), it would be convenient to get a handy equivalent expression in terms of marginal contributions for it. Actually, the formula we propose in the next section provides the clue for getting an extension to ternary games, (j, 2)-simple games and multichoice cooperative games, while as far as we know, no generalizable expression exists to these broader contexts from (6).

3 A new explicit formula for the Shapley value

In this Section we introduce a value \(\Phi\) for any \(a\in N\) as follows

$$\begin{aligned} \Phi _{a}(v)=\sum _{S\subseteq {N\smallsetminus \{a\}}}\varGamma ^{n}(s)[v(S\cup \{a\})-v(S)], \end{aligned}$$
(7)

where \(s=|S|\) and for any \(s=0,\dots ,n-1\):

$$\begin{aligned} \varGamma ^{n}(s)=\frac{s!}{2^{n}n!}\sum _{k=0}^{s}\frac{(n-k-1)!}{(s-k)!}2^{k}+\frac{(n-s-1)!}{2^{n}n!}\sum _{k=0}^{n-s-1}\frac{(n-k-1)!}{(n-s-1-k)!}2^{k}. \end{aligned}$$
(8)

In the same way that the explicit formula (6) is equivalent to (2) for cooperative games and to (4) for simple games, we have the following.

Theorem 4

The explicit formula (7), which describes a value \(\Phi\) is equivalent to (3) for cooperative games and to (5) for simple games.

Proof

If a is a positive player in a roll-call R, then \(dR(a)=1\) and the marginal contribution for player a is \(M(v,R,a)=v({\mathcal {Y}}(R,a))-v({\mathcal {Y}}(R,a)\smallsetminus \{a\})\). Consider the coalition \(S={\mathcal {Y}}(R,a)\). Then the marginal contribution \(v(S)-v(S{\setminus} \{a\})\) is accounted for all roll-calls with either:

  • a being positive and S being the set of positive players preceding a, or

  • a being negative and S being the union of the sets of positive players preceding a and all subsequent players to a.

Thus, \(v(S)-v(S{\setminus} \{a\})\) is multiplied by the sum of the rates with respect to the total number of roll-calls, i.e., \(2^{n}n!\) of the cardinalities of these two subsets of roll-calls.

We start by calculating the rate of roll-calls in which a is positive and that are associated with a given coalition S containing a. Let j be the number of negative players preceding a in a roll-call, then j varies between 0 and \(n-s\) and thus:

$$\begin{aligned} \dfrac{1}{2^{n}n!}\left[ \sum _{j=0}^{n-s}\overbrace{\left( {\begin{array}{c}n-s\\ j\end{array}}\right) }^{\begin{array}{c} \text {combinations}\\ \text {of players }\notin S\\ \text { before a} \end{array} }\underbrace{(s-1+j)!}_{\begin{array}{c} \text {orderings of players}\\ \text {before }a \end{array} }\overbrace{(n-s-j)!}^{\begin{array}{c} \text {orderings}\\ \text {of players}\\ \text {after }a \end{array} }\underbrace{2^{n-s-j}}_{\begin{array}{c} \text {ways to vote }\\ \text { for players}\\ \text {after }a \end{array} }\right] \overset{\text {def}}{=}\gamma ^{n}(n-s) \end{aligned}$$

Now we calculate the rate of roll-calls in which a is negative and that are associated to a given coalition S containing a. Let j be the number of positive players preceding a in a roll-call, then j varies between 0 and \(s-1\) and thus:

$$\begin{aligned} \dfrac{1}{2^{n}n!}\left[ \sum _{j=0}^{s-1}\overbrace{\left( {\begin{array}{c}s-1\\ j\end{array}}\right) }^{\begin{array}{c} \text {combinations}\\ \text {of players }\in S\\ \text { before a} \end{array} }\underbrace{(n-s+j)!}_{\begin{array}{c} \text {orderings of players}\\ \text {before }a \end{array} }\overbrace{(s-1-j)!}^{\begin{array}{c} \text {orderings}\\ \text {of players}\\ \text {after }a \end{array} }\underbrace{2^{s-1-j}}_{\begin{array}{c} \text {ways to vote }\\ \text { for players}\\ \text {after }a \end{array} }\right] \overset{\text {def}}{=}\gamma ^{n}(s-1). \end{aligned}$$

As the coefficient \(\gamma ^{n}(s)+\gamma ^{n}(n-s-1)\) coincides with \(\varGamma ^{n}(s)\) for all positive integers n and \(s=0,1,\dots ,n-1\), we have

$$\begin{aligned} \begin{array}{rcl} \phi _{a}(v) &{} = &{} \sum \limits _{S\subseteq {N\smallsetminus \{a\}}}[\gamma ^{n}(s)+\gamma ^{n}(n-s-1)][v(S\cup \{a\})-v(S)]\\ &{} = &{} \sum \limits _{S\subseteq {N\smallsetminus \{a\}}}\varGamma ^{n}(s)[v(S\cup \{a\})-v(S)]=\varPhi _{a}(v) \end{array} \end{aligned}$$

\(\square\)

From Theorem 4 and the result by Felsenthal and Machover (1996) establishing equivalence between (3) and (2), one may directly deduce the following Corollary. However, Felsenthal and Machover (1996) gave an indirect proof of the coincidence of (3) and (2), by proving that the value defined in (3) satisfies Shapley’s axioms. They did not prove the coincidence of those two expressions directly. Nevertheless, in the last paragraph of their work, they wrote:

If one attempts to prove (3) by showing directly that the right-hand side of (5) is equal to that of (4), one encounters rather formidable combinatorial difficulties. This suggests that our Theorem and Corollary are a disguised form of a combinatorial fact that is certainly non-trivial, and may be of some independent interest.

The direct proof for the next Corollary 3 solves that combinatorial problem.

Corollary 3

The values \(\Phi\) and \(\phi\) for cooperative games coincide.

To prove Corollary 3 it is enough to deduce the equality of the coefficients \(\rho ^{n}(s)\) and \(\varGamma ^{n}(s)\) for all positive integers n and \(0\le s\le n-1\), which is a direct consequence of the next lemma since the equality \(\rho ^{n}(s)=\varGamma ^{n}(s)\) can be converted into Eq. (9) by taking \(m=n-s-1\) and rearranging the terms.

The proof for Lemma 1 below is deduced by using the technique of generating functions. However, we want to remark that the equality of coefficients also can be derived by induction, which constitutes another intuitive alternative proof.

Let us recall the results on formal series and generating functions we are going to use. Given a sequence \(\{u_{n}\}_{n}\) the formal series of \(\{u_{n}\}_{n}\) is

$$\begin{aligned} U(t)=\sum _{n\ge 0}u_{n}t^{n}=u_{0}+u_{1}t+u_{2}t^{2}+\dots \end{aligned}$$

The multiplication of two formal series U(t) and V(t) is given by

$$\begin{aligned} U(t)\cdot V(t)=\left( \sum _{n\ge 0}u_{n}t^{n}\right) \cdot \left( \sum _{n\ge 0}v_{n}t^{n}\right) =\sum _{n\ge 0}\left( \sum _{k=0}^{n}u_{k}v_{n-k}\right) t^{n}. \end{aligned}$$

Moreover, differentiating k times the geometric series \(\frac{1}{1-t}=\sum _{n\ge 0}t^{n}\), we get the following identity:

$$\begin{aligned} \frac{1}{(1-t)^{k+1}}=\sum _{n\ge 0}\left( {\begin{array}{c}n+k\\ k\end{array}}\right) t^{n}. \end{aligned}$$

The previous identities are used to prove the next Lemma from which Corollary 3 is derived.

Lemma 1

Let m and s be non-negative integers, then

$$\begin{aligned} \sum _{k=0}^{s}\left( {\begin{array}{c}m+s-k\\ m\end{array}}\right) 2^{k}+\sum _{k=0}^{m}\left( {\begin{array}{c}m+s-k\\ s\end{array}}\right) 2^{k}=2^{m+s+1}. \end{aligned}$$
(9)

Proof

Let us consider the sequence \(a_{m,s}=\sum _{k=0}^{s}\left( {\begin{array}{c}m+s-k\\ m\end{array}}\right) 2^{k}\), the formal series of \(a_{m,s}\) is

$$\begin{aligned} \begin{aligned}\sum _{m\ge 0}\left\{ \sum _{s\ge 0}\left[ \sum _{k=0}^{s}\left( {\begin{array}{c}m+s-k\\ m\end{array}}\right) 2^{k}t^{s}\right] u^{m}\right\}&=\sum _{m\ge 0}\left[ \sum _{s\ge 0}2^{s}t^{s}\sum _{s\ge 0}\left( {\begin{array}{c}m+s\\ m\end{array}}\right) t^{s}\right] u^{m}\\&=\sum _{m\ge 0}\left[ \frac{1}{1-2t}\cdot \frac{1}{(1-t)^{m+1}}\right] u^{m}\\&=\frac{1}{1-2t}\sum _{m\ge 0}\frac{1}{(1-t)^{m+1}}u^{m}\\&=\frac{1}{1-2t}\cdot \frac{1}{1-t-u}. \end{aligned} \end{aligned}$$

The two addends on the left-hand side of Eq. (9) are symmetrical; thus,

$$\begin{aligned} \frac{1}{1-2t}\cdot \frac{1}{1-t-u}+\frac{1}{1-2u}\cdot \frac{1}{1-t-u}=\frac{2}{(1-2t)(1-2u)}. \end{aligned}$$

On the other hand, the formal series of the sequence \(b_{m,s}=2^{m+s+1}\) is

$$\begin{aligned} \begin{aligned} \sum _{m\ge 0}\left\{ \sum _{s\ge 0}\left[ 2^{m+s+1}t^{s}\right] u^{m}\right\}&=2\sum _{m\ge 0}\left[ \sum _{s\ge 0}2^{s}t^{s}2^{m}u^{m}\right] \\&=2\frac{1}{1-2t}\cdot \sum _{m\ge 0}2^{m}u^{m}\\&=2\frac{1}{1-2t}\frac{1}{1-2u} \end{aligned} \end{aligned}$$

and this completes the proof of the lemma. \(\square\)

4 Conclusion

Felsenthal and Machover (1996) provided a new interpretation of the Shapley value in the probability space of roll-calls, not necessarily positive roll-calls, as the expected value of the marginal contributions in that space. As a corollary, they obtained a pivotal scheme for simple games, which becomes much more natural than the one proposed by Shapley and Shubik (1954). For completeness, as themselves indicated in the last paragraph of their paper, it lacked a combinatorial expression for the explicit formula for computing the Shapley value on the probability space of roll-calls. In this paper we report such a formula.

This new formula is not simpler than the classical one, but it allows one to derive the equivalence between (4) and (5) without the use of axioms and to solve the combinatorial problem quoted in Felsenthal and Machover (1996).

In addition, formula (5) has been extended to voting models with abstention and several levels of approval, while no extensions of formula (4) are known to those contexts. Therefore, we consider that the formula (7) obtained in this article has great potential for extension to larger cooperative models.