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

HAL
open science

A concise axiomatization of a Shapley-type value for
stochastic coalition processes

Ulrich Faigle, Michel Grabisch

► To cite this version:

Ulrich Faigle, Michel Grabisch. A concise axiomatization of a Shapley-type value for stochastic coalition processes. 2013. halshs-00841259

HAL Id: halshs-00841259

https://shs.hal.science/halshs-00841259

Submitted on 4 Jul 2013

**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_2.png" /></figure>

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

A concise axiomatization of a Shapley-type value for
stochastic coalition processes

Ulrich FAIGLE, Michel GRABISCH

2013.52

<figure><img src="image_4.png" /></figure>
# A concise axiomatization of a Shapley-type value for stochastic coalition processes

Ulrich FAIGLE*

Michel GRABISCH†

June 13, 2013

## Abstract

The Shapley value is defined as the average marginal contribution of a player, taken over all possible ways to form the grand coalition $N$ when one starts from the empty coalition and adds players one by one. In a previous paper, the authors have introduced an allocation scheme for a general model of coalition formation where the evolution of the coalition of active players is ruled by a Markov chain and need not finish with the grand coalition. This note provides an axiomatization which is weaker than the one in the original paper but allows a much more transparent correctness proof. Moreover, the logical independence of the axioms is proved.

**Keywords:** coalitional game; coalition formation process; Shapley value

**JEL Classification:** C71

## 1 Introduction

The Shapley value (Shapley, 1953) is among the most popular solution concepts in cooperative game theory, and has been used in numerous applications. It is based on the following basic idea: considering any possible order for the players to enter the game, take the average of the marginal contribution of a player over all these orders. This rule can be seen as a particular way to form coalitions, that is, start from the empty coalition and add a player at each step until the grand coalition is reached. This simple view, however, is not suitable to all situations, and is quite restrictive from the point of view of coalition formation. So it is not surprising that the Shapley value would give counterintuitive results in some situations (see, e.g., Roth (1980), Shafer (1980), and Scafuri and Yannelis (1984)).

Faigle and Grabisch (2012) have developed a much more general framework for a value that is suited to coalition formation. It takes into account that several players may enter at any step of the coalition formation process and also some may leave the

<footnote>*Mathematisches Institut, Universität zu Köln, Weyertal 80, 50931 Köln, Germany. Email: faigle@zpr.uni-koeln.de</footnote>

<footnote>†Corresponding author. Paris School of Economics, University of Paris I, 106-112, Bd. de l'Hôpital, 75013 Paris, France. Tel. (33) 144-07-82-85, Fax (33)-144-07-83-01. Email: michel.grabisch@univ-paris1.fr</footnote>
current coalition. Moreover, the process is not assumed to stop when the grand coalition is formed but may continue to evolve. Indeed, the evolution is governed by a Markov chain or any kind of stochastic process. The authors have presented two values, called Shapley I and Shapley II, which define allocation schemes for this general situation. But cover the classical Shapley value as a particular case. It appears from the study of its properties that only Shapley II seems to be suitable. Faigle and Grabisch (2012) give an axiomatization of Shapley II (see a corrected version in (Faigle and Grabisch, to appear)), with a very complex proof, similar to the proof of Weber (1988) for the axiomatization of the classical Shapley value.

The aim of this note is to derive a slightly weaker axiomatization, together with a much more transparent correctness proof. In addition, the logical independence of the axioms is shown. We replace the anonymity axiom (invariance of the value under permutations of the players) by the weaker symmetry axiom (symmetric players receive the same payoff) and base our present proof on the decomposition of a game as a sum of unanimity games (as it is done, e.g., by van den Brink (2001); Faigle and Kern (1992)).

The paper is organized as follows. Section 2 describes coalition formation processes and the allocation scheme (value) we propose. Section 3 gives the new axiomatization with its proof for this value. Finally, in Section 4 we prove the logical independence of the axioms.

Throughout the paper, $N$ denotes a finite set of $n$ players. We often omit braces for singletons, writing, e.g., $S \cup i$, $S \setminus ij$ instead of $S \cup \{i\}$ and $S \setminus \{i, j\}$.

## 2 Values for coalition formation processes

We restrict our exposition to the minimum (see Faigle and Grabisch (2012, to appear) for full details and more examples).

We call *scenario of coalition formation process* any sequence $S = \emptyset, S_1, S_2, \dots$ of coalitions in $N$ that start with the empty set. A scenario need not be finite and repetitions may occur. Also, it need not finish at the grand coalition. To avoid intricacies, we consider here only finite scenarios $\emptyset, S_1, \dots, S_q$.

**Example 1.** Take $N = \{1, 2, 3, 4\}$. Here is an example of scenario:

$$S = \emptyset, 12, 24, 3, 123, 1234, 12.$$

where $12$ stands for $\{1, 2\}$, etc. In this scenario, players 1 and 2 enter together, then 1 leaves and 4 enters, then both leave and 3 enters, then 1 and 2 enter again, then 4 enters, and finally 3 and 4 leave.

**Example 2.** Consider a permutation $\sigma$ on $N$. Then $\sigma$ induces the following scenario:

$$\emptyset, \{\sigma(1)\}, \{\sigma(1), \sigma(2)\}, \dots, \{\sigma(1), \dots, \sigma(n-1)\}, N.$$

Using all possible $\sigma$, we get the $n!$ scenarios used in the classical definition of the Shapley value.

The main idea of our value is very close to the original view of Shapley: compute the marginal contribution of the players who are *active* during one step $S_t \to S_{t+1}$ (i.e., those
who are entering or leaving), and then add these contributions for all steps forming the scenario. This gives a value for a given scenario $\mathcal{S}$, called a *scenario-value*. The final step is to consider all possible scenarios, supposing that the transitions between coalitions are governed by a stochastic process, typically a Markov chain. Then the (overall) value is obtained as the expected value over all possible scenarios of the scenario-values. More formally, for a Markov chain $\mathbf{U}$:

$$ \phi^{\mathbf{U}}(v) = \sum_{\mathcal{S} \leftarrow \mathbf{U}} p(\mathcal{S}) \phi^{\mathcal{S}}(v) $$

where $\mathcal{S} \leftarrow \mathbf{U}$ means “scenario $\mathcal{S}$ generated by $\mathbf{U}$”, and the scenario-value $\phi^{\mathcal{S}}$ is computed by

$$ \phi^{\mathcal{S}}(v) = \sum_{t=0}^{q-1} \phi^{S_t \to S_{t+1}}(v), \qquad (1) $$

with $\mathcal{S} = S_1, \dots, S_q$. Therefore it remains to define the scenario-value for a given transition $S_t \to S_{t+1}$. In the case of the classical Shapley value, since in a transition a single player enters and nobody leaves, the marginal contribution of the entering player is naturally defined as $v(S_{t+1}) - v(S_t)$. In our more general case, since several players may enter or leave, the situation is more complicated. One first idea leads to what we called the *Shapley I value*, and consists in using the principle of insufficient reason: divide $v(S_{t+1}) - v(S_t)$ equally among the active players:

$$ \tilde{\phi}_i^{S_t \to S_{t+1}}(v) = \begin{cases} \frac{1}{|S_t \Delta S_{t+1}|} (v(S_{t+1}) - v(S_t)), & \text{if } i \in S_t \Delta S_{t+1} \\ 0, & \text{otherwise,} \end{cases} \qquad (2) $$

where $S_t \Delta S_{t+1} = (S_t \setminus S_{t+1}) \cup (S_{t+1} \setminus S_t)$ is the set of active players. A less simple idea, which turned out to be much better, however, is the decomposition of a transition $S_t \to S_{t+1}$ into all possible elementary transitions, i.e., transitions where only one player can enter or leave at a time. We call this the *Shapley II value*.

**Example 3.** The transition $24 \to 3$ of the scenario given in Example 1 decomposes in 6 different ways, depending on the order of the active players 2, 4 and 3:

$$ \begin{aligned} 24 &\to 4 \to \emptyset \to 3 \\ 24 &\to 4 \to 34 \to 3 \\ 24 &\to 2 \to \emptyset \to 3 \\ 24 &\to 2 \to 23 \to 3 \\ 24 &\to 234 \to 34 \to 3 \\ 24 &\to 234 \to 23 \to 3 \end{aligned} $$

Since each transition is elementary, the marginal contribution is given to the entering/leaving player. Formally:

$$ \phi_i^{S_t \to S_{t+1}}(v) = \begin{cases} \frac{1}{|S_t \Delta S_{t+1}|!} \sum_{\mathcal{P} \text{ from } S_t \text{ to } S_{t+1}} (v(S'_{\mathcal{P}}) - v(S_{\mathcal{P}})), & \text{if } i \in S_t \Delta S_{t+1} \\ 0, & \text{otherwise,} \end{cases} \qquad (3) $$

<footnote n="1">¹We omit here the case of infinite scenarios for brevity. See full details in Faigle and Grabisch (2012).</footnote>
where "P from $S_t$ to $S_{t+1}$" is any path from $S_t$ to $S_{t+1}$ in $2^N$ (like in Example 3), and $S_P \to S'_P$ is the unique transition in P such that either $\{i\} = S_P \setminus S'_P$ or $\{i\} = S'_P \setminus S_P$.

**Example 4.** (Example 3 ct'd) Computing $\phi^{24 \to 3}(v)$ gives:

$$ \phi_1^{24 \to 3}(v) = 0 $$

$$ \phi_2^{24 \to 3}(v) = \frac{1}{6}(2(v(4) - v(24)) + (0 - v(2)) + 2(v(3) - v(23)) + (v(34) - v(234))) $$

$$ \phi_3^{24 \to 3}(v) = \frac{1}{6}(2(v(3) - 0) + (v(34) - v(4)) + (v(23) - v(2)) + 2(v(234) - v(24))) $$

$$ \phi_4^{24 \to 3}(v) = \frac{1}{6}((0 - v(4)) + 2(v(3) - v(34)) + 2(v(2) - v(24)) + (v(23) - v(234))). $$

**Example 5.** (Example 2 ct'd) The application of the Shapley II value on the $n!$ scenarios induced by permutations yields exactly the classical Shapley value, as is easy to check.

# 3 Axiomatization of the Shapley II value

We briefly recapitulate the six axioms used in (Faigle and Grabisch, to appear) to characterize the Shapley II value.

We denote by $\psi: \mathcal{G} \to \mathbb{R}^{n \times \mathcal{G}}$ a scenario-value, where $\mathcal{G}$ is the set of games on $N$, and $\mathcal{G}$ is the set of finite sequences of coalitions (not necessarily starting with $\emptyset$).

Two sequences $S = S_1, \dots, S_q, S' = S'_1, \dots, S'_r$ are said to be *concatenable* if $S_q = S'_1$, in which case their *concatenation* is the sequence

$$ S \oplus S' := S_1, \dots, S_q, S'_2, \dots, S'_r. $$

**Concatenation (C):** Let $S, S'$ be two concatenable sequences. Then

$$ \psi^{S \oplus S'} = \psi^S + \psi^{S'}. $$

Axiom (C) allows us to restrict our attention to transitions. Indeed,

$$ \psi^S = \sum_{t=1}^{q-1} \psi^{S_t \to S_{t+1}} $$

holds for every sequence $S = S_1, S_2, \dots, S_q$.

**Inactive players in transitions (IP):** If $i$ is inactive in $S \to T$, i.e., $i \notin S \Delta T$, then $\psi_i^{S \to T}(v) = 0$ for any game $v$.

**Efficiency for transitions (E):** For any transition $S \to T$ and game $v$, we have

$$ \sum_{i \in N} \psi_i^{S \to T}(v) = v(T) - v(S). $$

**Linearity for transitions (L):** $v \mapsto \psi^{S \to T}(v)$ is a linear operator over $\mathcal{G}$ for any transition $S \to T$.
**Symmetry for transitions (S')**: For any $i \in N$, any transition $S \to T$ and any permutation $\sigma$ on $N$, one has

$$ \psi_{i}^{S \to T}(v) = \psi_{\sigma(i)}^{\sigma(S) \to \sigma(T)}(v \circ \sigma^{-1}). $$

$i \in N$ is a null player for $v$ if $v(S \cup i) = v(S)$ for all $S \subseteq N \setminus i$.

**Null axiom for transitions (N)**: Every null player $i$ for $v$ obtains $\psi_{i}^{S \to T}(v) = 0$ relative to every transition $S \to T$.

Two players $i, j$ are antisymmetric if $v(K \cup \{i, j\}) = v(K)$ for every $K \subseteq N \setminus \{i, j\}$.

**Antisymmetry for entering/leaving players (ASEL)**: if $i \in S \setminus T$ and $j \in T \setminus S$ are antisymmetric for $v$, then $\psi_{i}^{S \to T}(v) = \psi_{j}^{S \to T}(v)$.

Antisymmetric players have in some sense a counterbalancing effect: they annihilate each other when entering together a coalition, which can be interpreted by saying that they bring the same contribution but of opposite sign. Therefore, if one is leaving and the other entering, their contribution in the scenario becomes equal and of same sign.

Now, we replace (S') (symmetry by permutation, a.k.a. anonymity) by the weaker classical symmetry property as follows. We say that $i, j \in N$ are symmetric for $v$ if $v(S \cup i) = v(S \cup j)$ for any $S \subseteq N \setminus ij$.

**Symmetry axiom (S)**: For any transition $S \to T$, any $i, j$ both in $S \setminus T$ or in $T \setminus S$, $\psi_{i}^{S \to T}(v) = \psi_{j}^{S \to T}$ whenever $i, j$ are symmetric for $v$.

As pointed out in the Introduction, our proof of the axiomatization relies on the decomposition of games into unanimity games. We recall that for each $K \subseteq N, K \neq \emptyset$, the unanimity game centered at $K$ is defined by

$$ u_K(S) = \begin{cases} 1, & \text{if } S \supseteq K \\ 0, & \text{otherwise.} \end{cases} $$

It is well known that any game $v$ on $N$ can be written as

$$ v = \sum_{K \subseteq N, K \neq \emptyset} m^v(K)u_K $$

where $m^v(K)$, the coefficients of $v$ in the basis of unanimity games, is known to be the Möbius transform of $v$ (Rota, 1964), a.k.a. *Harsanyi dividends* (Harsanyi, 1963). It follows from the above that

$$ v(S) = \sum_{T \subseteq S} m^v(T) \quad (S \subseteq N). \qquad (4) $$

The following lemma characterizes games with antisymmetric players in terms of the Möbius transform.

**Lemma 1.** Distinct players $i, j$ are antisymmetric for the game $v$ if and only if

$$ m^v(K \cup ij) = -m^v(K \cup i) - m^v(K \cup j), \quad \forall K \subseteq N \setminus ij, $$

where $m^v$ is the Möbius transform of $v$.
Proof. If i, j are antisymmetric for v and m^v is the Möbius transform of v, one deduces from (4):

$$
\begin{align*}
0 = v(L \cup ij) - v(L) &= \sum_{K \subseteq L \cup ij} m^v(K) - \sum_{K \subseteq L} m^v(K) \\
&= \sum_{K \subseteq L} (m^v(K \cup i) + m^v(K \cup j) + m^v(K \cup ij))
\end{align*}
$$

for any $L \subseteq N \setminus ij$. For $L = \emptyset$, establishes $m^v(i) + m^v(j) + m^v(ik) = 0$. Now, for $L = \{k\}$, we deduce $m^v(ik) + m^v(jk) + m^v(ijk) = 0$, etc. until we finally arrive at

$$
m^v(K \cup i) + m^v(K \cup j) + m^v(K \cup ij) = 0.
$$

□

**Theorem 1.** A scenario-value satisfies (C), (L), (IP), (E), (S), (N) and (ASEL) if and only if it is the Shapley II scenario-value.

*Proof.* The “if part” has already been shown in Faible and Grabisch (2012, to appear).

We use the decomposition of games on the basis of unanimity games. By (L) and (C), it suffices to prove that for any unanimity game $u_K$, any transition $S \to T$, the quantities $\psi_i^{S \to T}(u_K)$, $i \in N$, are uniquely determined.

1. Supposing $S \subseteq T$, consider the unanimity game $u_K$ for some $K \subseteq N$. Observe that any $i \in K$ is a non-null player while any other player is null. Therefore, by (E), (N) and (IP), we obtain

$$
u_K(T) - u_K(S) = \sum_{i \in (T \setminus S) \cap K} \psi_i^{S \to T}(u_K).
$$

Assuming $|(T \setminus S) \cap K| > 1$, any two players in this set are symmetric for $u_K$. By (S), we therefore have

$$
\psi_i^{S \to T}(u_K) = \frac{u_K(T) - u_K(S)}{|(T \setminus S) \cap K|}, \quad i \in (T \setminus S) \cap K,
$$

and $\psi_i^S \to T(u_K) = 0$ for any other $i$ by (N) and (IP). Finally,

$$
u_K(T) - u_K(S) = \begin{cases} 1, & \text{if } K \subseteq T \text{ and } K \not\subseteq S \\ 0, & \text{otherwise.} \end{cases}
$$

In summary, we find

$$
\psi_i^{S \to T}(u_K) = \begin{cases} \frac{1}{|K \setminus S|}, & \text{if } K \subseteq T \text{ and } i \in K \setminus S \\ 0, & \text{otherwise.} \end{cases}
$$

2. The case $T \subseteq S$ is analyzed similarly. We find

$$
\psi_i^{S \to T}(u_K) = \begin{cases} \frac{1}{|K \setminus T|}, & \text{if } K \subseteq S \text{ and } i \in K \setminus T \\ 0, & \text{otherwise.} \end{cases}
$$
3. We consider the case where $S \setminus T \neq \emptyset$ and $T \setminus S \neq \emptyset$ hold. From (N), (IP) and (E), we get

$$u_K(T) - u_K(S) = \sum_{i \in (S \Delta T) \cap K} \psi_i^{S \to T}(u_K). \quad (5)$$

Observe that

$$u_K(T) - u_K(S) = \begin{cases} 1, & \text{if } K \subseteq T \text{ and } K \not\subseteq S \cap T \\ -1, & \text{if } K \subseteq S \text{ and } K \not\subseteq S \cap T \\ 0, & \text{otherwise.} \end{cases}$$

Clearly, if $K \cap (S \Delta T) = \emptyset$, $\psi_i^{S \to T}(u_K) = 0$ for all $i \in N$ by (IP). We assume hereafter that $K \cap (S \Delta T) \neq \emptyset$, which excludes $K \subseteq S \cap T$. The above considerations give us three cases.

3.1. Suppose that $K \subseteq T$. Eq. (5) becomes

$$\sum_{i \in K \setminus S} \psi_i^{S \to T}(u_K) = 1,$$

and by (S), (N) and (IP) we obtain

$$\psi_i^{S \to T}(u_K) = \begin{cases} \frac{1}{|K \setminus S|}, & \text{if } i \in K \setminus S \\ 0, & \text{otherwise.} \end{cases} \quad (6)$$

3.2. The case $K \subseteq S$ proceeds similarly and yields

$$\psi_i^{S \to T}(u_K) = \begin{cases} -\frac{1}{|K \setminus T|}, & \text{if } i \in K \setminus T \\ 0, & \text{otherwise.} \end{cases} \quad (7)$$

3.3. Suppose $K \not\subseteq T$ and $K \not\subseteq S$. Eq. (5) becomes

$$\sum_{i \in (S \Delta T) \cap K} \psi_i^{S \to T}(u_K) = \sum_{i \in (S \setminus T) \cap K} \psi_i^{S \to T}(u_K) + \sum_{i \in (T \setminus S) \cap K} \psi_i^{S \to T}(u_K) = 0.$$

All players in $(S \setminus T) \cap K$ being symmetric, and similarly for $(T \setminus S) \cap K$, (S) yields

$$|(S \setminus T) \cap K|\psi_i^{S \to T}(u_K) + |(T \setminus S) \cap K|\psi_j^{S \to T}(u_K) = 0, \quad (8)$$

for arbitrary $i \in S \setminus T$ and $j \in T \setminus S$, provided they exist. If $(S \setminus T) \cap K = \emptyset$, we obtain from (8) for $k \in K \cap T$ and from (N), (IP) otherwise

$$\psi_k^{S \to T}(u_K) = 0, \quad \forall k \in N. \quad (9)$$

Similarly, (9) is valid also if $(T \setminus S) \cap K = \emptyset$.

It remains to consider the case $K_1 := (S \setminus T) \cap K \neq \emptyset$ and $K_2 := (T \setminus S) \cap K \neq \emptyset$. We proceed in a recursive way on the cardinality of $K_2$, and start from $|K_2| = 1$, letting $K_2 = \{j\}$.
Consider the game $v := u_K - u_{K \setminus j}$. From Lemma 1, we see that $i, j$ are antisymmetric for $v$, for any $i \in K_1$. Applying (ASEL) we find $\psi_i^{S \to T}(v) = \psi_j^{S \to T}(v)$ for any $i \in K_1$, which yields by (L):

$$ \psi_i^{S \to T}(u_K) - \psi_i^{S \to T}(u_{K \setminus j}) = \psi_j^{S \to T}(u_K) - \underbrace{\psi_j^{S \to T}(u_{K \setminus j})}_{=0 \text{ by (N)}}. \quad (10) $$

Observe that $K' = K \setminus j$ is such that $(T \setminus S) \cap K' = \emptyset$. Therefore, either (7) or (9) applies, and we find

$$ \psi_i^{S \to T}(u_{K \setminus j}) = \begin{cases} -\frac{1}{|K \setminus T|}, & \text{if } K \setminus j \subseteq S \\ 0, & \text{otherwise.} \end{cases} $$

This yields

$$ \psi_i^{S \to T}(u_K) - \psi_j^{S \to T}(u_K) = \begin{cases} -\frac{1}{|K \setminus T|}, & \text{if } K \setminus j \subseteq S \\ 0, & \text{otherwise.} \end{cases} \quad (11) $$

Observe that the system of equations (8) and (11) yields a unique solution for $\psi_i^{S \to T}(u_K)$, $\psi_j^{S \to T}(u_K)$.

Suppose that $\psi_i^{S \to T}(u_K)$ is known till $|K_2| = \ell < |T \setminus S|$, and let us determine $\psi_i^{S \to T}(u_K)$, $\psi_j^{S \to T}(u_K)$ for $|K_2| = \ell + 1$. Choose some $j \in K_2$ and consider the game $v := u_K - u_{K \setminus j}$. Since $i, j$ are antisymmetric for $v$, for all $i \in K_1$, the same reasoning as above applies, and (10) is valid. Now, $\psi_i^{S \to T}(u_{K \setminus j})$ is determined by induction hypothesis. Therefore, $\psi_i^{S \to T}(u_K)$, $\psi_j^{S \to T}(u_K)$ are uniquely determined. $\square$

# 4 Independence of the axioms

We prove in this section that all seven axioms are logically independent.

Consider axiom (C). All six remaining axioms determine $\phi^{S \to T}(v)$ for a given transition $S \to T$. Hence the value $\psi^S$ for a scenario $S = S_1, \dots, S_q$ defined by

$$ \psi^S(v) = f(\phi^{S_1 \to S_2}(v), \phi^{S_2 \to S_3}(v), \dots, \phi^{S_{q-1} \to S_q}(v)) $$

where $f$ is an operator different from the sum, satisfies all axioms but (C).

The situation of axiom (L) is similar: Our proof of axiomatization of $\phi^{S \to T}(v)$ is based on the unique determination of $\phi^{S \to T}(u_K)$ for any unanimity game $u_K$, using the five remaining axioms (IP), (E), (S), (N) and (ASEL). Hence the value $\psi^S(v)$ defined by

$$ \psi^S(v) = \sum_{t=1}^{q-1} \left( \bigoplus_{K \subseteq N} m^v(K) \phi^{S_t \to S_{t+1}}(u_K) \right) $$

with $v = \sum_{K \subseteq N} m^v(K) u_K$, and $\oplus$ is an operator different from the sum, satisfies all axioms but (L).

Therefore, it remains to show that (IP), (E), (S), (N) and (ASEL) are independent for the axiomatization of $\phi^{S \to T}(u_k)$, for any transition $S \to T$ and any unanimity game $u_K$.

(i) **Axiom (E):** removing the normalization constant $\frac{1}{|S \Delta T|}$ in (3) gives a value satisfying (IP), (S), (N), (ASEL) but not (E).
(ii) **Axiom (IP):** consider the value defined by $\psi^{S \to T} = \phi^{S \to T}$ if $1 \in S \Delta T$, and otherwise

$$ \psi_i^{S \to T}(v) = \begin{cases} \frac{1 - v((S \Delta T) \cup 1) + v(S \Delta T)}{|S \Delta T|!} \sum_{\mathcal{P} \text{ from } S \text{ to } T} (v(S'_{\mathcal{P}}) - v(S_{\mathcal{P}})), & \text{if } i \in S \Delta T \\ (v((S \Delta T) \cup 1) - v(S \Delta T))(v(T) - v(S)), & \text{if } i = 1 \\ 0, & \text{otherwise,} \end{cases} $$

Clearly (IP) is not satisfied, but it can be checked that all other axioms are.

(iii) **Axiom (N):** consider the value defined by

$$ \psi_i^{S \to T}(v) = \begin{cases} \frac{v(T) - v(S)}{|S \Delta T|}, & \text{if } i \in S \Delta T \\ 0, & \text{otherwise.} \end{cases} $$

Then $\psi^{S \to T}$ then all axioms but (N) are satisfied.

(iv) **Axiom (S):** consider $\psi^{S \to T}(v)$ defined as follows: if $S \subseteq T$, then $\psi^{S \to T}(v)$ is defined as a weighted Shapley value instead of a classical Shapley value<fnref n="2" />, i.e., weights are assigned to players. Otherwise, $\psi^{S \to T}$ coincides with $\phi^{S \to T}$. Then, unless all weights are equal, this value is not symmetric, although it will satisfy all other axioms. In particular, (ASEL) is satisfied because (ASEL) concerns only transitions $S \to T$ where $S \not\subseteq T$ and $T \not\subseteq S$.

(v) **Axiom (ASEL):** let us come back to the proof of Theorem 1. Axiom (ASEL) is used only in case 3.3 where $(S \setminus T) \cap K \neq \emptyset$ and $(T \setminus S) \cap K \neq \emptyset$ hold; it yields Equation (11), which together with (8) determines the value uniquely. It suffices then to take any solution of (8) not satisfying (11). For example:

$$ \psi_i^{S \to T}(u_K) = - \frac{|(T \setminus S) \cap K|}{|(S \setminus T) \cap K|}, \quad \psi_j^{S \to T}(u_K) = 1 $$

for every $i \in S \setminus T$, $j \in T \setminus S$, and $S, T, K$ satisfy the above condition.

## References

U. Faigle and M. Grabisch. Values for Markovian coalition processes. *Economic Theory*, 51:505–538, 2012. DOI: 10.1007/s00199-011-0617-7.

U. Faigle and M. Grabisch. A note on values for Markovian coalition processes. *Economic Theory Bulletin*, to appear. DOI: 10.1007/s40505-013-0003-7.

U. Faigle and W. Kern. The Shapley value for cooperative games under precedence constraints. *Int. J. of Game Theory*, 21:249–266, 1992.

<footnote n="2">²It is shown in Faigle and Grabisch (to appear) that $\phi^{S \to T}(v)$ corresponds to the classical Shapley value of the game $v_{S,T}$, defined by $v_{S,T}(K) = v(K \Delta S) - v(S)$ for any $K \subseteq S \Delta T$.</footnote>
J. C. Harsanyi. A simplified bargaining model for the *n*-person cooperative game. *International Economic Review*, 4:194–220, 1963.

G. C. Rota. On the foundations of combinatorial theory I. Theory of Möbius functions. *Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete*, 2:340–368, 1964.

A. E. Roth. Values for games without sidepayments: some difficulties with current concepts. *Econometrica*, 48:457–465, 1980.

A. Scafuri and N. Yannelis. Non-symmetric cardinal value allocations. *Econometrica*, 52: 1365–1368, 1984.

W. Shafer. On the existence and interpretation of value allocation. *Econometrica*, 48: 467–476, 1980.

L. S. Shapley. A value for *n*-person games. In H. W. Kuhn and A. W. Tucker, editors, *Contributions to the Theory of Games, Vol. II*, number 28 in Annals of Mathematics Studies, pages 307–317. Princeton University Press, 1953.

R. van den Brink. An axiomatization of the Shapley value using a fairness property. *Int. J. of Game Theory*, 30:309–319, 2001.

R. J. Weber. Probabilistic values for games. In A. E. Roth, editor, *The Shapley Value. Essays in Honor of Lloyd S. Shapley*, pages 101–119. Cambridge University Press, 1988.