Abstract
The problem of fair division of payoff is one of the key issues when considering cooperation of strategic individuals. It arises naturally in a number of applications related to operational research, including sharing the cost of transportation or dividing the profit among supply chain agents. In this paper, we consider the problem of extending the Shapley Value—a fundamental payoff division scheme—to cooperative games with externalities. While this problem has raised a lot of attention in the literature, most works focused on developing alternative axiomatizations for an extension. Instead, in this paper we focus on the coalition formation process that naturally leads to an extended payoff division scheme. Specifically, building upon recent literature, we view coalition formation as a discrete-time stochastic process, characterized by the underlying family of probability distributions on the set of partitions of players. Given this, we analyse how various properties of the probability distributions that underlie the stochastic processes relate to the game-theoretic properties of the corresponding payoff division scheme. Finally, we prove that the Stochastic Shapley value—a known payoff division scheme from the literature—is the only one that satisfies all aforementioned axioms.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The problem of fair division of payoff is one of the fundamental problems when considering cooperation of strategic individuals. It arises naturally in various applications related to operational research, including sharing transportation costs between customers (Goel and Gruhn 2008), dividing the profit from cooperation among supply chain agents (Nagarajan and Sošić 2008), and measuring the distribution of the power in legislative bodies (Algaba et al. 2007).
One of the well-known solutions to this problem is the Shapley value (Shapley 1953). It divides the payoff from cooperation in a way that satisfies various fundamental properties (or axioms). Mathematically, according to the Shapley value, the share of a player in the overall outcome from cooperation equals to her average marginal contribution to this outcome, taken over all possible permutations of players. Shapley (1953) argued that his payoff division scheme can be rationalized by the following deterministic coalition formation process: assume that players create the grand coalition sequentially in a random order. A new player receives the payoff that equals her marginal contribution to the group of players that she joins. Now, the Shapley Value is the player’s expected such payoff given all possible orders of players.
The Shapley value is used not only to divide costs or share profits in cooperative scenarios, but also as an advanced tool in various other settings, such as assessing the role of a criterion in multi-criteria decision making (Grabisch et al. 2008), attributing risk in public health applications (Cox 1985), and evaluating centrality of nodes in networks (Gómez et al. 2003; Skibski et al. 2018a).
The standard version of the Shapley value was developed for games in the characteristic function form, i.e., when it is simplistically assumed that the value of a coalition depends solely on its members. However, many real-life scenarios involve externalities, i.e., partitions of outside players may affect the value of a coalitions. Externalities occur, for instance, in supply chains (Netessine and Zhang 2005), oligopolistic markets (De Clippel and Serrano 2008), and in the international agreements (Finus 2003; Plasmans et al. 2006).
Unfortunately, the Shapley value for games with no externalities cannot be immediately extended to such richer settings. This is because a direct translation of Shapleys original axiom system to games with externalities is too weak to yield a unique value.
Addressing this issue has been a subject of an intense debate in the literature (see (Kóczy 2018) for a recent overview). Two orthogonal approaches can be distinguished. The first approach, followed by the majority of authors, is focused on developing a new axiomatization by either modifying Shapley’s original axiom system, extending it by additional axioms, or proposing completely different one (De Clippel and Serrano 2008; Myerson 1977; Maskin 2003; Hafalir 2007). In contrast, in the second approach, the focus in shifted from axioms to the coalition formation processes that may occur in games with externalities. The key idea is to study such processes and analyse the values that they yield. The axiomatic characterisation of any value is then typically built upon the coalition formation process that yields this value.
In this vein, Grabisch and Funaki (2012) proposed three values for games with externalities, supported by particular coalition formation processes. These values, however, do not satisfy the Null-player Axiom—Shapley’s fundamental requirements that says that a player who does not contribute anything to any coalition should not obtain any payoff. More recently, Skibski et al. (2018b) proposed a general approach to extend the Shapley value to games with externalities in which the coalition formation process is viewed as the discrete-time stochastic process characterized by an arbitrary family of quasi-probability distributions \(p = (p_1, p_2, \ldots )\). The authors showed that all values that satisfy the direct translation of Shapleys axioms to games with externalities can be obtained using such a process approach. We refer to such values as p-Process (Shapley) values.
The Chinese Restaurant Process—one of the key stochastic processes in probability theory—turns out to be of particular importance in the context of games with externalities. In more detail, Skibski et al. (2018b) showed that using the Chinese Restaurant Process in the process approach leads to well-known value from the literature; moreover, it can be uniquely characterized by the strengthening of the Null-Player Axiom and the direct translation of Shapley’s remaining axioms. This value, now termed the Stochastic Shapley Value (Skibski et al. 2018b), had been previously derived by Feldman (1996) and Macho-Stadler et al. (2007) based on two specific axiom systems.
While the work by Skibski et al. (2018b) forged the link between cooperative game theory and probability theory in the context of extending the Shapley value to games with externalities, this link has not been yet thoroughly explored. Interestingly, however, as we show in this article, there exist a plethora of results in probability theory that may shed a new light on our understanding of payoff division in games with externalities.
In particular, we study the relation between the properties of the probability distributions that underline stochastic processes and the corresponding values. We begin our analysis by considering two well-known properties—exchangeability and consistency. In more detail, we first show that if distributions from the family p satisfy the property of exchangeability, then the p-Process Shapley Value satisfies a property called Strong Symmetry. We then show that if, in addition to exchangeability, the family p satisfies the property of consistency, then the p-Process Shapley Value satisfies a property called the Null-player Out Axiom.
Next, we discuss two further properties of probability distributions. The first one, called in the literature conditional independence, means that the partitions formed by latter elements is independent from the partition of earlier ones. When combined with exchangeability and consistency, conditional independence characterizes the class of the celebrated Ewens probability distribution. We show how this property of p leads to a new, natural axiom, called Condition Independence in Games, met by the resulting p-Process Shapley value. The second property, which we call 2-partition equality, says that probability distribution on two partitions of two-element set should be uniform, i.e., both partitions are equally likely. This is because both elements involved can be either together or apart. We show that it is possible to translate this property to Embedded Coalition Anonymity—an axiom proposed by Albizuri et al. (2005), but now focused solely on 3-player games. Intuitively, this axiom says that in a 3-player game, swapping the values of a (singleton) coalition embedded in two partitions does not affect the payoffs of players.
Our key result is that the Stochastic Shapley value is a unique extension for which the underlying probability distribution satisfies all four properties, i.e., exchangeability, consistency, conditional independence, and 2-partition equality. Thus, through our analysis, we provide a new axiomatization of the Stochastic Shapley value.
The remainder of this article is organized as follows. In the next section, we present basic definitions and notation. In Sect. 3, we consider properties of the probability distribution and show how they translated to the properties of the corresponding values for games with externalities. In Sect. 4, we discuss existing values that can be obtained using the process approach. Conclusions follows.
2 Preliminary definitions
Let \(N = \{1, 2, \ldots , n\}\) be a set of players. A coalition, S, is any subset of N. A partition, denoted P, is any set of disjoint coalitions whose union is N. The set of all partitions over N is denoted by \({\mathscr {P}}(N)\). An embedded coalition is a pair (S, P), where S is a coalition and P is a partition such that \(S \in P\). The set of all embedded coalitions over N is denoted by EC(N). When there is no risk of confusion, we will write \({\mathscr {P}}\) and EC instead of \({\mathscr {P}}(N)\) and EC(N).
A game (in a partition-function form) is a mapping \(v: EC(N) \rightarrow {\mathbb {R}}\) that associates a real number with every embedded coalition. The outcome of the game (or the value of the game) is a function \(\varphi \) that, for a given game, associates a vector of n real numbers, one for each player, i.e., \(\varphi : {\mathbb {R}}^{EC(N)} \rightarrow {\mathbb {R}}^N\). Thus, \(\varphi _i(v)\) denotes the value \(\varphi \) of player i in game v. As is customary in the literature, we assume that the grand coalition, N, forms. In result, the value of the game distributes the value of the grand coalition.
A permutation of set S is a bijection \(\pi : S \rightarrow \{{{\mathbb {1}}, {\mathbb {2}}, \ldots , |\mathbb {S}|}\}\) that assigns positions to players. We use text decoration to distinguish the set of positions from the set of players. The set of all permutations of S is denoted by \(\varOmega (S)\). For a permutation \(\pi \) and a player i, \(C_i^{\pi }\) denotes the set of players that appear in \(\pi \) after i: \(C_i^{\pi } = \{j \mid \pi (j) > \pi (i)\}\). A permutation obtained from \(\pi \in \varOmega (S)\) by adding \(i \not \in S\) at the end is denoted by \(\pi _{+i}\). In addition, for \(S = \{1,2,\ldots ,|S|\}\), we define the identity permutation \(\pi _{id} \in \varOmega (S)\) as \(\pi _{id}(k) = {\mathbb {k}}\) for every \(k \in S\).
For an arbitrary function \(f: N \rightarrow X\), \(f(S) = \{f(i) \mid i \in S\}\) for \(S \subseteq N\), and \(f(P) = \{f(S) \mid S \in P\}\) for \(P \in {\mathscr {P}}(N)\). Consequently, \(f(S, P) = (f(S), f(P))\). Moreover, for a bijection \(f: N \rightarrow N\), we define \((f(v))(S,P) = v(f(S,P))\) and \(f(\varphi _i) = \varphi _{f(i)}\).
A probability distribution on the set of partitions of \(\{{{\mathbb {1}},\ldots ,\mathbb {n}}\}\) is a mapping \(p_n: {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}) \rightarrow {\mathbb {R}}\) that satisfies \(\sum _{P \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\})} p_n(P) = 1\) and \(0 \le p_n(P) \le 1\) for every \(P \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\})\). A quasi-probability distribution allows for negative values, i.e., it is any mapping \(p_n: {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}) \rightarrow {\mathbb {R}}\) that satisfies \(\sum _{P \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\})} p_n(P) = 1\). For \(P_k \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {k}}}\})\), \(k < n\), we define \(p_n\) on \(P_k\) as the sum of probabilities of the partitions that cover \(P_k\):
A family of (quasi-)probability distribution on the set of partitions of \({{\mathbb {1}}},{{\mathbb {2}}},\ldots \) is an ordered list \(p = (p_1, p_2, \ldots )\), where each \(p_n\) is a (quasi-)probability distribution.
Fix \((S, P) \in EC\). The Dirac game\(e^{(S,P)}\) is a game in which only coalition S in partition P has non-zero value: \(e^{(S, P)}(S,P) = 1\) and \(e^{(S, P)}({\tilde{S}}, {\tilde{P}}) = 0\), otherwise. We use a shorthand notation for adding/excluding a player to/from a coalition or a partition: \(S_{-i} = S {\setminus } \{i\}\), \(S_{+i} = S \cup \{i\}\) and \(P_{-i} = \{T {\setminus } \{i\} : T \in P\}\). Analogously, for a set of players, \(T \subseteq N\), we define \(P_{-T} = \{T' {\setminus } T : T' \in P\}\). Furthermore, to denote the partition obtained by the transfer of player i to coalition T in partition P, we introduce the following notation:
In particular, if \(T = \emptyset \), then i forms a singleton coalition \(\{i\}\).
A game has no externalities if the value of every coalition is independent from the partition of other players, i.e., \(v(S,P_1) = v(S, P_2)\) for every \(S \subseteq N\), \((S, P_1), (S, P_2) \in EC(N)\). Such a game can be represented in the characteristic-function form, \({\hat{v}}: 2^N \rightarrow {\mathbb {R}}\) with \({\hat{v}}(\emptyset ) = 0\). A well-known value of games without externalities is the Shapley value (Shapley 1953).
Definition 1
(Shapley value) For a game, \({\hat{v}}\), and a player, \(i \in N\), the Shapley value is defined by the following equation:
which can be rewritten as:
The Shapley value can be viewed as the following coalition formation process. Assume that players leave the grand coalition one by one in a random order and, as a player leaves, he receives a payoff that equals his marginal contribution to the group of players that he left. Now, the Shapley value is the expected outcome of the player’s contributions over all orders.
Shapley (1953) proved that the Shapley value is a unique payoff distribution scheme that satisfies four desirable axioms: Efficiency, Symmetry, Additivity, and the Null-player Axiom. For games with externalities, Shapley’s axioms are translated as follows:
Efficiency (EFF)—the total payoff is distributed among the players: \(\sum _{i \in N} \varphi _i(v) = v(N, \{N\})\) for every game v;
Symmetry (SYM)—payoffs do not depend on the players’ names: \(\varphi (f(v)) = f(\varphi )(v)\) for every game v and every bijection \(f: N \rightarrow N\);
Additivity (ADD)—if two games are combined, then the payoffs should be equal to the sum of payoffs of both games considered separately: \(\varphi (\beta _1 v_1 + \beta _2 v_2) = \beta _1 \varphi (v_1) + \beta _2 \varphi (v_2)\) for all the games \(v_1, v_2\) and scalars \(\beta _1, \beta _2 \in {\mathbb {R}}\), where \((v_1 + v_2)(S, P) = v_1(S, P) + v_2(S, P)\) and \((\beta v)(S, P) = \beta \cdot v(S, P)\); this condition is sometimes called Linearity (Macho-Stadler et al. 2007);
Null-player Axiom (NP)—the payoff of a null-player, i.e., player without the impact on the value of any coalition, is zero: if for every (S, P) such that \(i \in S\), and every \(T \in (P {\setminus } \{S\}) \cup \{\emptyset \}\) it holds that \(v(S, P) - v(S_{-i}, \tau _i^T(P)) = 0\), then \(\varphi _i(v) = 0\), for every game v and player \(i \in N\).
Unlike in games without externalities, when externalities are present, these axioms do not imply a unique value. In result, a number of extensions have been proposed (De Clippel and Serrano 2008; Macho-Stadler et al. 2007; Bolger 1989). A number of such values can be obtained using the process approach, i.e., are equal to a p-Process Shapley value for a family of quasi-probability distributions p.
Definition 2
(Thep-Process Shapley value) For a game, v, and a player, \(i \in N\), the p-Process Shapley value is defined as follows:
where \(P_{[S]} = P_{-S} \cup \{S\}\); this can be rewritten as follows:
Formula (4) sums over all possible permutations and partitions of players. As the position of the last player does not matter, it is assumed that he forms a singleton coalition. Also, note that for \(S = \{i\}\) formula (5) does not depend on the specific values of \(p_{n-1}\) for partitions of size n but only on their sum. This is because we have \(v(S_{-i}, P) = 0\) for \(S = \{i\}\) and every \(P \in {\mathscr {P}}(N)\).
For a family of probability distributions, p, the p-Process Shapley value can be viewed as the following coalition formation process. Assume that players leave the grand coalition N in a random order \(\pi \) and divide themselves into groups outside. Assume that after k steps, partition \(P_{k}\) has been formed outside of the remainder of the grand coalition. In the \((k+1)\)-th step, one player departs and joins one of the coalitions (or forms a new coalition) with probability \(p_{n-1}(\pi (P_{k+1}))/p_{n-1}(\pi (P_{k}))\), where \(P_{k+1}\) is the partition obtained by this transfer. As the result of his leaving, the player is assigned a payoff that equals his elementary marginal contribution, i.e., the loss of a coalition he left. Finally, in the n-th step, the last player, independently of which coalitions he joins, is assigned the remaining value of the grand coalition. Now, the p-Process Shapley value is his expected payoff over all orders.
Skibski et al. (2018b) proved that every value that satisfies Shapley’s axioms is the p-Process Shapley value for some family of quasi-probability distributions \(p = (p_1, p_2, \ldots )\). This result is the starting point of our further analysis.
Theorem 1
Skibski et al. (2018b) If the value satisfies EFF, SYM, ADD, NP if and only if it is a p-Process Shapley value for some quasi-probability distribution p.
Let us introduce the axiom of Monotonicity.
Monotonicity (MON)—increase of a player’s contributions does not decrease his payoff: if \(v_1(S_{+i}, \tau _i^S(P)) - v_1(S, P) \ge v_2(S_{+i},\tau _i^S(P)) - v_2(S, P)\) holds for every \((S, P) \in EC\), such that \(i \not \in S\), then \(\varphi _i(v_1) \ge \varphi _i(v_2)\).
Skibski et al. (2018b) proved that if the value additionally satisfies Monotonicity, then we can limit ourselves to probability distributions.
Example 1
(the Stochastic Shapley value) Consider the probability distribution \(p_n\) that results from the following process. At time \(t=1\), partition \(\{{\mathbb {1}}\}\) is obtained. At time \(t = k\) the element \({\mathbb {k}}\) either forms a new block, \(\{{\mathbb {k}}\}\), with the probability \(\frac{1}{k}\) or is added to one of the existing blocks with the probability \(\frac{b}{k}\), where b is the size of this block. The p-Process Shapley value based on this probability distribution is the Stochastic Shapley value (Feldman 1996; Macho-Stadler et al. 2007; Skibski et al. 2018b).
The process described in Example 1 is the famous Chinese restaurant process (Aldous 1985). The name attributed to Jim Pitman comes from the following analogy. Imagine a fictional Chinese restaurant with a large number of empty large tables. Assume customers arrive sequentially: the first customer sits at the first table and every new customer either sits directly next to someone at one of the already occupied tables or at the first unoccupied table, where each of those seats is chosen with the same probability. In result, k-th customer has k choices and sits at the empty table with the probability \(\frac{1}{k}\) and at the table with b customers with the probability \(\frac{b}{k}\).
The Chinese restaurant process leads to the following probability distribution on the set of partitions of \({\{{{\mathbb {1}}},\dots ,{\mathbb {n}}\}}\):
for every \(P \in {\mathscr {P}}({\{{{\mathbb {1}}},\dots ,{\mathbb {n}}\}})\). In particular, for \(n=3\) we have:
The Chinese restaurant process has several desirable properties, such as exchangeability and consistency the details of which we discuss in the next section. In result, the Chinese restaurant process is used in many applications; some more recent include data clustering (Teh et al. 2005), gene expression analysis (Qin 2006) and natural language processing (Blei et al. 2010).
3 Properties
We consider the following four properties of probability distributions: exchangeability, consistency, conditional independence and 2-partition equality. Our goal is to study how the satisfiability of these properties by a given family p translates to the properties of the corresponding p-Process Shapley value. We will show how each new property limits the space of feasible values. Our key result is that the Stochastic Shapley value is the only p-Process Shapley value in which p satisfies all the properties under consideration.
3.1 Exchangeability
We say that a (quasi-)probability distribution is exchangeable if relabelling elements does not change the distribution of the partition. Thus, the probability of the partition depends only on the sizes of blocks, and not by their members. Formally, \(p_n(P) = p_n(f(P))\) for every \(P \in {\mathscr {P}}(\{{\mathbb {1}},\ldots ,{\mathbb {n}}\})\) and bijection \(f: \{{\mathbb {1}},\ldots ,{\mathbb {n}}\} \rightarrow \{{\mathbb {1}},\ldots ,{\mathbb {n}}\}\).
Example 2
(the Bolger value) Let us consider the probability distribution \(p_n\) that results from the following process. At time \(t=1\), partition \(\{{\mathbb {1}}\}\) is obtained. At time \(t = k\) the element \({\mathbb {k}}\) is added to one of the existing blocks or forms a new block, each option with the same probability. Now, \(p_n(\{\{{\mathbb {1}}\}\}) = 1\), and \(p_n(\{\{{{\mathbb {1}},{\mathbb {2}}}\}\}) = p_n(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) = \frac{1}{2}\). However, \(p_n(\{\{{{\mathbb {1}},{\mathbb {2}}}\}, \{{\mathbb {3}}\}\}) = \frac{1}{4}\) and \(p_n(\{\{{{\mathbb {1}},\mathbb {3}}\}, \{{\mathbb {2}}\}\}) = \frac{1}{6}\). Thus, this probability distribution is not exchangeable. The p-Process Shapley value based on this probability distribution is the Bolger value (Bolger 1989).
In probability theory, exchangeability is the necessary condition for de Finetti’s theorem (Lehner 2006). While de Finetti’s theorem concerns an infinite sequence of Bernoulli random variables, in our work we consider exchangeability of random partitions. This notion was proposed by Kingman (1978) who proved an analogous of de Finetti’s theorem for random partitions where the role of i.i.d. sequences is player by “paintbox processes” [see (Aldous 1985) for details].
In what follows, we will show that the property of exchangeability translates to Strong Symmetry—a strengthening of the axiom of Symmetry proposed by Macho-Stadler et al. (2007). To better understand this concept, let us consider a game \(e^{(S, P)}\) (recall that in this game only a particular coalition S embedded in a certain P has a non-zero value). Symmetry says that all players from coalition S should have the same payoff. In turn, payoffs of players from \(N {\setminus } S\) may differ between them. This may, however, seem unfair, as they all have the same role in the game: they must form a specific partition \(P{\setminus } S\) for the coalition S in P to be able to generate a value.
Strong Symmetry is intended to tackle the above problem. In particular, let us consider a bijection \(f: N {\setminus } S \rightarrow N {\setminus } S\) and let \(f_{(S, P)}(v)\) be a game obtained by exchanging the value of (S, P) and \((S, S \cup f(P {\setminus } \{S\}))\) in v (formally, \((f_{(S, P)}(v))(S,P) = v(S, S \cup f(P {\setminus } \{S\}))\), \((f_{(S, P)}(v))(S, S \cup f(P {\setminus } \{S\})) = v(S, P)\) and \((f_{(S, P)}(v))({\tilde{S}}, {\tilde{P}}) = v({\tilde{S}}, {\tilde{P}})\), otherwise). The axiom of Strong Symmetry states that the value satisfies two conditions: (i) Symmetry; and (ii) that the payoffs from game \(f_{(S, P)}(v)\) are equal to the payoffs from game v:
Strong Symmetry (SSYM)—the value of a coalition affects the payoffs of outside players symmetrically:
- (i)
\(\varphi (f(v)) = f(\varphi )(v)\) for every game v and bijection \(f: N \rightarrow N\);
- (ii)
\(\varphi (f_{(S, P)}(v)) = \varphi (v)\) for every game v, embedded coalition (S, P) and bijection \(f: N {\setminus } S \rightarrow N {\setminus } S\).
The latter condition is equivalent to the condition \(\varphi _i(e^{(S,P)}) = \varphi _j(e^{(S, P)})\) for every \(i, j \not \in S\) for additive values. In other words, all players, whose coalitions in all partitions have the value of zero, are assigned the same payoff.
The following theorem shows that a p-Process Shapley value satisfies Strong Symmetry if and only if p is a family of exchangeable quasi-probability distributions.
Theorem 2
A p-Process Shapley value satisfies SSYM if and only if p is a family of exchangeable quasi-probability distribution.
Proof
Let \(p_{n-1}\) be a quasi-probability distribution. First, we show that Strong Symmetry implies that \(p_{n-1}\) is exchangeable. Assume otherwise and let \(P_k \!\in \! {\mathscr {P}}(\{\!{{{\mathbb {1}}},\ldots ,{\mathbb {k}}}\!\}\!)\) be a minimal partition such that \(p_{n-1}(P_k) \!\not =\! p_{n-1}(f(P_k))\) for a bijection \(f\!:\! \{\!{{{\mathbb {1}}},\ldots ,{\mathbb {k}}}\!\} \!\rightarrow \{{{{\mathbb {1}}},\ldots ,{\mathbb {k}}}\}\). From the fact that k is minimal, we know that \(f({\mathbb {k}}) = {\mathbb {l}} \not = {\mathbb {k}}\). Also, we can arbitrary reorder previous elements, as \(p_{n-1}(P_{k-1}) = p_{n-1}(f(P_{k-1}))\) for every \(f: \{{{\mathbb {1}},\ldots ,\mathbb {k}-{\mathbb {1}}}\} \rightarrow \{{{\mathbb {1}},\ldots ,\mathbb {k}-{\mathbb {1}}}\}\). Now, we construct a game \(e^{(S, P)}\) for n players with \(S = \{k+1,\ldots ,n\}\) and players \(\{1,\ldots ,k\}\) partitioned according to \(P_k\):
From formula (5) we have:
and analogously \(\varphi _l(w(f(P_k))) = - \frac{|S|! (|N|-|S|-1)!}{|N|!} p_{n-1}(f(P_k))\). As both probabilities are different, both players get different payoffs, and Strong Symmetry is violated.
Now, we prove the other direction of the theorem. Assume that \(p_{n-1}\) is exchangeable. Then, for \(e^{(S, P)}\) with \(i \not \in S\), formula (5) simplifies to
for arbitrary \(\pi \in \varOmega (N {\setminus } S)\). Thus, it does not depend on i and Strong Symmetry is satisfied. This concludes our proof. \(\square \)
If we consider the values that satisfy Strong Symmetry, then \(p_n(\pi (P_k))\), for every partition \(P_k \in {\mathscr {P}}(S)\) with \(S \subseteq N\), does not depend on permutation \(\pi \in \varOmega (S)\). In such scenarios, we define \(p_n(P_k)\) on partition of players \(P_k\) as \(p_n(\pi (P_k))\) with \(\pi \in \varOmega (S)\) defined as a natural order of S: \(\pi (i) = \mathbb {m}\) if \(|\{j \in S: j \le i\}| = m\).
Now, the general formula (5) can be simplified as follows:
Observe that \(v(S_{-i}, \tau _i^T(P))\) in the above formula is multiplied by \(p_{n-1}(\tau _i^T(P) {\setminus } S_{-i})\). Also, observe that v(S, P) is multiplied by \(\sum _{T \in (P {\setminus } \{S\}) \cup \{\emptyset \}} p_{n-1}(\tau _i^T(P) {\setminus } S_{-i}) = p_{n-1}(P {\setminus } \{S\})\). In other words, the value of a coalition in a given partition is always preceded by the probability that this partition forms. This suggests the following algorithm for evaluating a fair division in a game with externalities:
first, we create from a game with externalities v an average game \({\tilde{v}}\) with no externalities. This is done by calculating the value of every coalition as the average of its values in the game with externalities:
$$\begin{aligned} {\tilde{v}}(S) = \sum _{P \ni S} a(S, P) \cdot v(S, P), \end{aligned}$$where \(\sum _{P \ni S} a(S, P) = 1\) for every S;
then, we calculate the Shapley value for the average game \({\tilde{v}}\):
$$\begin{aligned} \varphi (v) = SV({\tilde{v}}). \end{aligned}$$
This approach, called the average approach, was introduced by Macho-Stadler et al. (2007), who proved that the value that satisfies Shapley’s axioms can be constructed using the average approach if and only if it satisfies Strong Symmetry [see Theorem 1 in the work by Macho-Stadler et al. (2007)].
Theorem 3
The average approach is equivalent to the process approach with a family of exchangeable quasi-probability distributions.
Proof
From Theorem 1, we know that process approach can produce every value that satisfies Shapley’s axiom: EFF, SYM, ADD, and NP. Moreover, Theorem 2 shows that the resulting value satisfies SSYM if and only if family p consists of exchangeable quasi-probability distributions. Thus, these two theorems combined with the result from Macho-Stadler et al. (2007) imply that a value can be obtained using the average approach if and only if it can be obtained using the process approach with exchangeable quasi-probability distributions. \(\square \)
Hu and Yang (2010) proved that every value obtained using the average approach with positive weights can be obtained using the process approach. Their result is a special case of our precise characterization from Theorem 3.
3.2 Consistency
Recall that, in our definition of a family of probability distributions, we did not require any relation between \(p_n\) and \(p_{n+1}\). This means, in particular, that probability distributions from the same family can be arbitrarily different. For instance, probability distribution \(p_2\) can assign a non-zero value only to partition \(\{\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}\}\), while probability distribution \(p_3\) can assign a non-zero value only to partition \(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}, \{{\mathbb {3}}\}\}\). As a result, given that the p-Process Shapley value for the n-player game depends only on \(p_{n-1}\), the values for games with different number of players can be arbitrarily defined and no relation between such values can be assumed. To address this issue, we analyze in this section the condition of consistency.
A family of probability distribution \(p = (p_1, p_2, \ldots )\) is said to be (Kołmogorov) consistent (or projective) if \(p_{n}(P_k) = p_k(P_k)\) for every \(P_k \in {\mathscr {P}}(\{{{{\mathbb {1}}},{{\mathbb {2}}},\ldots ,{\mathbb {k}}}\})\) and \(k < n\). Thus, the sum of probabilities according to distribution \(p_n\) of the partitions that cover \(P_k\) (i.e., such partitions that are obtained by inserting elements \(\{{{\mathbb {k}}+{{\mathbb {1}}}, \ldots , {\mathbb {n}}}\}\) into partition \(P_k\)) equals the probability of \(P_k\) according to distribution \(p_k\).
Example 3
(the Hu-Yang value) Consider family \(p = (p_1, p_2, \ldots )\) of uniform probability distributions \(p_n(P) = 1/|{\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\})|\) for every \(P \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\})\). Now, the sum of probabilities of all partitions in which element \({\mathbb {1}}\) is in the same set as element \({\mathbb {2}}\) equals \(p_n(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) = \frac{|{\mathscr {P}}(\{{{{\mathbb {1}}},{{\mathbb {2}}},\ldots ,{\mathbb {n}}-{{\mathbb {1}}}}\})|}{|{\mathscr {P}}(\{{{{\mathbb {1}}},{{\mathbb {2}}},\ldots ,{\mathbb {n}}}\})|}\). Thus, \(p_n(\{\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}\}) \ne p_2(\{\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}\}) = \frac{1}{2}\) for \(n > 2\) (e.g., \(p_3(\{\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}\}) = \frac{2}{5}\)) and p is not consistent. The p-Process Shapley value based on this family of probability distributions but shifted by one position, i.e., \((p_2, p_3, \ldots )\), is the Hu-Yang value (Hu and Yang 2010).
In terms of our coalition formation process for p-Process Shapley value, consistency requires that the probability of joining a coalition by a player should depend only on the coalitions to choose from and not on the coalition that the player is leaving.
Now, we will show that if p is a family of exchangeable probability distribution, then consistency translates to the Null-player Out Axiom proposed by Derks and Haller (1999) and vice versa, i.e., the family of exchangeable probability distributions p is consistent if and only if the p-Process Shapley value satisfies the Null-player Out Axiom.
Let us first explain the concept of this axiom. In particular, let us consider a game v in which i is a null-player in the strict sense, i.e., i does not have an impact on the game whatsoever. In such a case, the Null-player Axiom requires that player i has zero payoff. However, it does not mean that player i cannot have an impact on the payoffs of others. In other words, removing a null-player from the game may affect the payoffs of the remaining players. The Null-player Out Axiom rules out such situations. Specifically:
Null-player Out Axiom (NPO)—a null-player does not have an impact on the payoffs of others: if i is a null-player then \(\varphi _j(v) = \varphi _j(v_{-i})\) for every \(j \in N {\setminus } \{i\}\), where \(v_{-i}\) denotes the game without player i: \(v_{-i}(S_{-i},P_{-i}) = v(S, P)\) for every (S, P) such that \(i \in S\).
Note that the combination of the standard Null-player Axiom and the Null-player Out Axiom is equivalent to the Strong Null-player Axiom proposed by Macho-Stadler et al. (2007).
When i is not a null-player, constructing the game \(v_{-i}\) can be challenging. However, the situation is much simpler when i is a null-player. This is because the value of embedded coalition \((S, P)\in EC(N{\setminus }\{i\})\) can be obtained by inserting player i to an arbitrary coalition in partition P. Regardless which coalition is chosen, we will obtain the same value.
The following theorem states that if p-Process Shapley value satisfies Strong Symmetry, then consistency of family p is necessary and sufficient to obtain the Null-player Out Axiom.
Theorem 4
Assume that p is a family of exchangeable quasi-probability distributions. Then, a p-Process Shapley value satisfies NPO if and only if p is consistent.
Proof
Consider the class of games \(\{ v_{null(j)}^{(S, P)} \mid (S, P) \in EC, j \in S \}\) defined as follows:
Note that player j is a null-player in this game. Thus, the Null-player Out Axiom implies that the payoff of arbitrary player \(i \in N {\setminus } \{j\}\) does not change if we remove null-player j from this game, i.e.,
holds for every \(i \in N {\setminus } \{j\}\) and \((S, P) \in EC\) such that \(j \in S\). Now, we argue that this condition is also sufficient to imply the Null-player Out Axiom. This is because the class of games \(v_{null(j)}^{(S, P)}\) forms a basis of all games in which j is a null-player. Thus, if the payoff of player \(i \in N {\setminus } \{j\}\) in game \(v_{null(j)}^{(S, P)}\) for every (S, P) does not change when we remove player j, then it does not change for arbitrary game in which j is a null-player.
Now, consider this condition for the p-Process Shapley value, where p is a family of exchangeable quasi-probability distributions. Let i be a player, and \((S, P) \in EC\) an embedded coalition such that \(j \in S\). From formula (6) for values with exchangeable probability distributions we get:
Furthermore, from exchangeability of \(p_{n-1}\) we know that the sum \(\sum _{T \in (P {\setminus } \{S\}) \cup \{\emptyset \}} p_{n-1}(\tau _j^T(P) {\setminus } S_{-j})\) equals \(p_{n-1}(P {\setminus } \{S\})\). Thus,
Formula (6) applied to game \(v_{null(j)}^{(S, P)}\) without player j equals
Since \(P {\setminus } \{S\}\) can be chosen arbitrarily, we get that \(p_{n-1}(P_k) = p_{n-2}(P_k)\) for every \(P_k \in {\mathscr {P}}(S)\) for \(S \subseteq \{1,\ldots ,n-2\}\) which is equivalent to consistency. \(\square \)
Consistency yields another simplification of the formula (6) for the p-Process Shapley value. In particular, we can omit index in \(p_n\) because the elements of family p are consistent and \(p_i(P_k) = p_j(P_k)\), for every \(i, j \ge k\) and every \(P_k \in {\mathscr {P}}(\{{{{\mathbb {1}}},{{\mathbb {2}}},\ldots ,{\mathbb {k}}}\})\).
In the next two sections we will consider two further properties of stochastic processes, called conditional independence and 2-partition equality.
3.3 Conditional independence
Let us divide set \(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}\) into two parts: \(A=\{{{{\mathbb {1}}},\ldots ,{\mathbb {k}}}\}\) and \(B=\{{{\mathbb {k}}+{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}\). Next, let us consider the set of partitions in which both sets A and B are separated: \({\mathscr {P}}^{\star } = \{ P_1 \cup P_2 \mid P_1 \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {k}}}\}), P_2 \in {\mathscr {P}}(\{{{\mathbb {k}}+{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\})\}\). Now, it is natural to ask whether the probabilities of both partitions are independent, i.e., whether an event \(P_1 \in P\) affects the probability distribution of \(P_2\) and vice versa. Formally, a family of probabilistic distribution \(p = (p_1,\ldots ,p_n)\) is said to be conditionally independent (or, in other words, satisfy subset deletion), if for each \(k < n\) the probability distribution of partitions of N that contains \(\{{{\mathbb {k}}+{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}\) is \(p_k\). Formally,
where f(k, n) do not depend on \(P_k\). The fact that this condition can be applied multiple times implies that an arbitrary partition of the latter elements does not depend on the former ones (unless they mix). Thus, it can be considered as a “lack-of-memory property”.
Let us translate this property to an axiom for games with externalities. As in the case of Strong Symmetry, let us assume that there is only one coalition S with a non-zero value in the game. However, this time we require that it has a non-zero value not only in a particular partition P but in (possibly all) partitions in which there exist another coalition, T. More formally, let \(v_{S|T}\) be a game, where only coalition S in partitions P, such that \(T \in P{\setminus } \{S\}\), has non-zero values.
Furthermore, let us consider game \(v_{S|.}\) obtained from \(v_{S|T}\) by removing players from T. Formally, let \(v_{S|.}(S, P) = v_{S|T}(S, P \cup \{T\})\), and \(v_{S|.}(S^*, P) = 0\) for \(S^* \not = S\). Now, intuitively, conditional independence translated to an axiom means that, in both the above games, \(v_{S|T}\) and \(v_{S|.}\), the relations between how different partitions affect the payoff of player i are the same, i.e., the general structure of the value is preserved.
Conditional Independence in Games (CI)—when only one coalition in partitions with another one has non-zero values we can consider a smaller game: \(\varphi _i(v_{S|T}) = \varphi _i(v_{S|.}) \cdot f(|T|, |N|, |S|)\), where f does not depend on \(v_{S|T}\), for every \(S, T \subseteq N\), \(i \in S\), and every game \(v_{S|T}\).
Theorem 5
Assume p is family of exchangeable quasi-probability distributions. Then, the p-Process Shapley value satisfies CI if and only if p is conditionally independent.
Proof
Let \(v_{S|T}\) be the game, where only coalition S has non-zero values in the partitions P such that \(\{S,T\} \in P\). Consider the payoff of player \(i \in S\) in this game. From formula (6) for the p-Process Shapley value based on family of exchangeable probability distributions p we have:
Let game \(v_{S|.}\) be defined as follows: \(v_{S|.}(S, P) = v_{S|T}(S, P \cup \{T\})\), and \(v_{S|.}(S^*, P) = 0\) for \(S^* \not = S\). Then, the payoff of player i in game \(v_{S|.}\) equals:
Now, if p satisfies conditional independence, i.e., if \(p_n(P_k \cup \{{{\mathbb {k}}+{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}) = p_k(P_k) \cdot f(k, n)\) holds for every \(P_k \in {\mathscr {P}}(\{{{{\mathbb {1}}},{{\mathbb {2}}},\ldots ,{\mathbb {k}}}\})\), then we have
for every \(P \in {\mathscr {P}}(N)\) such that \(S, T \in P\). This is because, from formula (1), we know that \(p_{n-1}(P {\setminus } \{S\})\) is the sum of probabilities \(p_{n-1}(R)\) over all partitions R of size \(n-1\) covering \(P {\setminus } \{S\}\). However, each such probability translates to the corresponding probability \(p_{n-|T|}(R {\setminus } T)\) multiplied by f(k, n), and the sum of such probabilities equals \(p_{n-|T|-1}(P {\setminus } \{S, T\}) \cdot f(k, n)\). As a result,
Thus, Conditional Independence in Games is satisfied.
On the other hand, assume that \(\varphi ^p\) satisfies Conditional Independence in Games, i.e., for every coalition S, T it holds that:
for some function g which does not depend on \(v_{S|T}\). Next, consider the set of players \(\{1,\ldots ,n,n+1\}\) and an arbitrary partition \(P_k \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {k}}}\})\). Now, consider a payoff of player \(n+1\) in game \(e^{(S, P)}\) for \(S = \{n+1\}\) and \(P = \pi _{id}^{-1}(P_k) \cup \{k+1,\ldots ,n\} \cup \{\{n+1\}\}\). From formula (6) and Conditional Independence in Games applied to \(v_{S|T} = e^{(S, P)}\), we have that:
Thus, by putting \(f(k, n) = \frac{n+1}{k+1} \cdot g(n-k,n+1,1)\) we obtain the property of conditional independence. \(\square \)
Aldous (1996) proved that a family of probability distributions p satisfies exchangeability, consistency, and conditional independence if and only if it follows Ewens sampling formula, defined as follows:
for some \(\theta \in {\mathbb {R}}_+\). The Ewens distribution arises naturally from the following parameterization of the Chinese Restaurant Process. At time \(t=1\), partition \(\{{\mathbb {1}}\}\) is obtained. Now, assume that forming a new block has weight \(\theta \) instead of 1. At time \(t=n\), element \({\mathbb {n}}\) forms a new block with probability \(\frac{\theta }{(n-1)+\theta }\) or is added to one of the existing blocks with probability \(\frac{b}{(n-1)+\theta }\), where b is the size of this block.
Note that the result of Aldous applies only to probability distribution. Let us first extend the result of Aldous also to quasi-probability distributions.
Theorem 6
Family of quasi-probability distributions p satisfies exchangeability, consistency, and conditional independence if and only if follows Ewens distribution (i.e., formula 8) for some \(\theta \in {\mathbb {R}} {\setminus } \{-1, -2, \ldots \}\).
See the Appendix A for the proof of Theorem 6.
In result, we get the following corollary.
Theorem 7
A value satisfies EFF, ADD, SSYM, NP, NPO, and CI if and only if it is a p-Process Shapley value, where p is the Ewens distribution (i.e., formula 8) for some \(\theta \in {\mathbb {R}} {\setminus } \{-1, -2, \ldots \}\).
Proof
By combining Theorems 2 and 4 with Theorems 5 and 6 from this section we get the result. \(\square \)
Finally, in the next section we consider the property of 2-partition equality.
3.4 2-Partition equality
We focus in this section on such p-Process Shapley values in which the probability distribution results from the parameterized Chinese Restaurant Process. We start by presenting two extensions of the Shapley value from the literature that can be obtained by parametrizing the Chinese Restaurant Process with \(\theta \) set to two opposite extreme values.
Example 4
(the McQuillin value) Consider the parameterized Chinese Restaurant Process with \(\theta =0\), i.e., the probability of forming a new coalition equals 0; hence, all elements form a single coalition outside. Thus, \(p_n(P) = 1\) for \(P=\{\{{{{\mathbb {1}}},{{\mathbb {2}}},\ldots ,{\mathbb {n}}}\}\}\), and \(p_n(P)=0\), otherwise. The p-Process Shapley value based on this family of probability distributions p leads to the McQuillin value (McQuillin 2009).
Example 5
(the externality-free value) Consider the parameterized Chinese Restaurant Process with \(\theta \rightarrow \infty \), i.e., the probability of joining an existing coalition approaches zero. Thus, in the limit, \(p_n(P) = 1\) for \(P = \{\{{\mathbb {k}}\} \mid {\mathbb {k}} \in \{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}\}\}\), and \(p_n(P) = 0\), otherwise. Using this definition of p in a construction of the p-Process Shapley value results in the externality-free value, proposed by Pham Do and Norde (2007), and later studied by De Clippel and Serrano (2008).
Next, consider set \(\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}\) and let us focus on the parametrized Chinese Restaurant Process. When element \({\mathbb {2}}\) joins \({\mathbb {1}}\), two partitions can possibly emerge: either element \({\mathbb {2}}\) creates a new block (with probability \(p_2(\{\{{\mathbb {1}}\},\{{\mathbb {2}}\}\})\)) or it joins the block of element \({\mathbb {1}}\) (with probability \(p_2(\{\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}\})\)). Since no extra information is available, it is reasonable to assume that both cases are equally likely:
We call this property of a family of probability distribution 2-partition equality.
We will now translate 2-partition equality to the property of the value in games with externalities. To this end, we use the Embedded Coalition Anonymity condition proposed by Albizuri et al. (2005). Let \(S \subseteq N\) be an arbitrary coalition. For a bijection \(g_S: \{P \in {\mathscr {P}}(N) \mid S \in P\} \rightarrow \{P \in {\mathscr {P}}(N) \mid S \in P\}\) of partitions with coalition S, we define a game, denoted \(g_S(v)\), in which values of S are swapped according to \(g_S\): \(g_S(v)(S, P) = v(S, g_S(P))\) for every \(P \in {\mathscr {P}}(N)\) such that \(S \in P\), and \(g_S(v)(S', P') = v(S', P')\) for \(S' \not = S\).
Embedded Coalition Anonymity in 3-Player Games (3-ECA)—in a 3-player game, swapping the values of a coalition S between partitions P containing S does not affect the payoffs: \(\varphi _i(g_S(v)) = \varphi _i(v)\) for every \(S \subseteq N\), \(g_S: \{P \in {\mathscr {P}}(N) \mid S \in P\} \rightarrow \{P \in {\mathscr {P}}(N) \mid S \in P\}\), and every game v with \(N = \{1,2,3\}\).
Albizuri et al. (2005) proposed a value built upon the Embedded Coalition Anonymity for arbitrary number of players. The resulting value, however, violates the Null-player Axiom. Thus, we limit this axiom to games with three players—the smallest game with externalities. In a 3-player game, i.e., for \(N = \{1,2,3\}\), externalities affect only the values of singleton coalitions. In particular, \(v(\{i\}, \{\{i\}, \{j\}, \{k\}\})\) and \(v(\{i\}, \{\{i\}, \{j, k\}\})\) may differ for \(\{i, j, k\} = \{1,2,3\}\). Thus, we argue that the values of the coalition in both partitions should have the same impact on the payoffs of players. Note that this approach can be considered as a “golden mean” between two extreme cases considered above—the externality-free value (which only takes into account \(v(\{i\}, \{\{i\}, \{j\}, \{k\}\})\)) and the McQuillin’s value (which only accounts for \(v(\{i\}, \{\{i\}, \{j, k\}\})\)).
We show the equivalence of 2-partition equality and 3-ECA in the following theorem.
Theorem 8
The p-Process Shapley value satisfies 3-ECA if and only if p satisfies 2-partition equality.
Proof
Let \(N = \{1,2,3\}\). From formula (5) for player 1, we have that:
For every \(i,j,k \in \{1,2,3\}\), \(i \ne j \ne k\), the value \(v(\{i\}, \{\{i\}, \{j,k\}\})\) is multiplied by \(p_2(\{\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}\})\); also, the value \(v(\{i\}, \{\{i\}, \{j\}, \{k\}\})\) is multiplied by \(p_2(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\})\). Thus, both values affect the payoff equally if and only if both probabilities are equal: \(p_2(\{\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}\}) = p_2(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\})\). This concludes the proof. \(\square \)
In result, only the family of probability distributions obtained from the (non-parametrised) Chinese Restaurant Process satisfies all four properties.
Theorem 9
There exists a unique value which satisfies EFF, ADD, SSYM, NP, NPO, CI, and 3-ECA and it is the Stochastic Shapley value.
Proof
Based on Theorem 7 we know that value satisfies EFF, ADD, SSYM, NP, NPO, and CI if and only if it is a p-Process Shapley value where p is the Ewens distribution (i.e., formula (8) for some \(\theta \in {\mathbb {R}} {\setminus } \{-1,-2,\ldots \}\). From Theorem 8 we know that 3-ECA implies 2-partition equality, which for formula (8) is equivalent to \(p_2(\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}) = \theta /(\theta +1) = 1/2\), which means that \(\theta = 1\), and \(p_n(P) = 1/(n!) \prod _{S \in P} (|S|-1)!\). Thus, p-Process Shapley value based on this probability distribution is the only value that satisfies all axioms from theorem’s statement. This value is the Stochastic Shapley value. \(\square \)
Table 1 summarizes our results on the relationship between properties of the process and axioms of the corresponding values. In the next section, we collate the values for games with externalities from the literature that can be obtained using the process approach and discuss which properties are satisfied by the probability distributions they rely on.
4 Comparison with other values in the process approach.
In the literature, there exist five values for games with externalities that can be obtained with the process approach for probability distributions (i.e., following (Skibski et al. 2018b), that satisfy Shapley’s axioms and Monotonicity). We already presented them in Examples 1–5. In this section, we formally introduce these values and discuss which properties/axioms they satisfy.
Stochastic Shapley value (Feldman 1996; Macho-Stadler et al. 2007; Skibski et al. 2018b) (introduced in Example 1) is a p-Process Shapley value for the family \(p^{CRP} = (p_1^{CRP}, p_2^{CRP}, \ldots )\) with \(p^{CRP}_n\) defined as follows:
$$\begin{aligned} p^{CRP}_n(P) = \frac{\prod _{T \in P} (|T|-1)!}{|N|!}. \end{aligned}$$As proven in Theorem 9, \(p^{CRP}\) satisfies exchangeability, consistency, conditional independence, and 2-partition equality and the Stochastic Shapley value satisfies SSYM, NPO, CI, and 3-ECA.
Bolger value (Bolger 1989) (introduced in Example 2) is a p-Process Shapley value for the family \(p^{B} = (p_1^{B}, p_2^{B}, \ldots )\) with \(p^{B}_n\) defined as follows:
$$\begin{aligned} p_n^{B}(P) = \prod _{{\mathbb {k}} \in \{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}} \frac{1}{|P_{-\{{{\mathbb {k}},{\mathbb {k}}+{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}}|+1}. \end{aligned}$$This family of probability distributions was already introduced as an example of non-exchangeable distribution, i.e., it violates SSYM. While \(p^B\) is consistent, it violates the NPO (see the work by Macho-Stadler et al. (2007) for details). Also, we note that it does not satisfy conditional independence, as \(p^B_n(P_k \cup \{{{\mathbb {k}}+{{\mathbb {1}}}, \ldots , {\mathbb {n}}}\}) / p^B_k(P_k) = \frac{1}{(|P_k|+1)(|P_k|+2)^{n-k-1}}\), i.e., depends on \(P_k\); hence, the value does not satisfy the corresponding axiom—CI. Finally, \(p^{B}\) satisfies 2-partition equality, so from Theorem 8 the Bolger value satisfies 3-ECA.
Hu-Yang value (Hu and Yang 2010) (introduced in Example 3) is a p-Process Shapley value for the family \(p^{HY} = (p_1^{HY}, p_2^{HY}, \ldots )\) with \(p^{HY}_n\) defined as follows:
$$\begin{aligned} p_n^{HY}(P) = \frac{|P|+1}{|{\mathscr {P}}(\{1,\ldots ,n,n+1\})|}. \end{aligned}$$We showed in Example 3 that this family of probability distributions is not consistent. Also, it does not have the property of conditional independence, due to the fact that:
$$\begin{aligned} p^{HY}_n(P_k \cup \{{{\mathbb {k}}+{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}) / p^{HY}_k(P_k) = \frac{|P_k|+2}{|P_k|+1} \cdot \frac{|{\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}+{{\mathbb {1}}}}\})|}{|{\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {k}}+{{\mathbb {1}}}}\})|} \end{aligned}$$Finally, this family does not satisfy 2-partition equality. Thus, based on Theorems 4, 5 and 8, the Hu-Yang value violates the Null-player Out Axiom, Conditional Independence in Games and 3-ECA. On the other hand, \(p^{HY}\) is exchangeable and the corresponding value satisfies Strong Symmetry.
McQuillin’s value (McQuillin 2009) (introduced in Example 4) is a p-Process Shapley value for the family \(p^{full} = (p_1^{full}, p_2^{full}, \ldots )\) with \(p^{full}_n\) defined as follows:
$$\begin{aligned} p_n^{full}(P) = {\left\{ \begin{array}{ll} 1 &{} \text{ if } P = \{\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}\}\\ 0 &{} \text{ otherwise }. \end{array}\right. } \end{aligned}$$As we discussed before, \(p^{full}\) satisfies exchangeability, consistency and conditional independence; hence, the McQuillin’s value satisfies Strong Symmetry, the Null-player Out Axiom, and Conditional Independence for Games. However, \(p^{full}\) violates 2-partition equality and the McQuillin value violates 3-ECA.
externality-free value (Pham Do and Norde 2007; De Clippel and Serrano 2008) (introduced in Example 5) is a p-Process Shapley value for the family \(p^{free} = (p_1^{free}, p_2^{free}, \ldots )\) with \(p^{free}_n\) defined as follows:
$$\begin{aligned} p_n^{free}(P) = {\left\{ \begin{array}{ll} 1 &{} \text{ if } P = \{\{{\mathbb {k}}\} \mid {\mathbb {k}} \in \{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\}\}\\ 0 &{} \text{ otherwise }. \end{array}\right. } \end{aligned}$$\(p^{free}\) satisfies the same properties as the \(p^{full}\)—exchangeability, consistency, conditional independence, but violates 2-partition equality. Thus, the externality-free value satisfies Strong Symmetry, the Null-player Out Axiom, Conditional Independence for Games, but violates 3-ECA.
We summarise all the above observations in Table 2. As we can see, each property is met by majority of the probability distributions under consideration. The same applies to axioms, except Embedded Coalition Anonymity for 3-Player Game, which is not satisfied by 3 out of 5 values. Note that the Bolger value satisfies consistency and does not satisfy the Null-player Out Axiom—this is because our Theorem 4 applies only to exchangeable distributions. As argued in Theorem 9, the Stochastic Shapley value is the unique value that satisfies all four axioms.
There exists in the literature yet another value for games with externalities proposed by Myerson (1977) that satisfies Shapley’s axioms. However, this value does not meet Monotonicity. Thus, it can be obtained with the process approach, but for a family of quasi-probability distributions, \(p^M = (p^M_1, p^M_2, \ldots )\). In result, this family does not satisfy any of the properties discussed above. In particular, it violates 3-ECA, since \(p^M_2(\{\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}\}) = -1\) and \(p^M_2(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) = 2\).
Finally, let us discuss the coalition formation process proposed by Grabisch and Funaki (2012). This process can be interpreted as the following stochastic process: The starting point is the partition of singleton coalitions. In each step, two coalitions chosen at random are merged. Ultimately, the grand coalition is formed after \(n-1\) steps. Now, the value of player i is defined by looking how the values of all coalitions change when they are merged with coalitions containing player i in this process.
Note that, unlike our approach, in the process by Grabisch and Funaki all considered partitions have n players. In result, this approach can be considered orthogonal to our approach—a partition is formed not from a partition with less players, but from a partition with the same number of players, but with more coalitions. The resulting probability distribution is very different from those studied in this paper.
5 Conclusions
In this paper, we studied the link between cooperative game theory and probability theory in the context of extending the Shapley value to games with externalities. We analyzed various properties of the probability distributions that underline the stochastic processes that strengthens the Null-player Axiom and how these properties relate to the game-theoretic properties of the corresponding extensions of the Shapley value. In particular, we showed that the property of exchangeability from probability theory corresponds to Strong Symmetry—a well-known axiom in cooperative game theory. Furthermore, we showed that consistency corresponds to Null-player Out property, conditional independence to the new axiom—Conditional Independence in Games and 2-partitions equality—to Embedded Coalition Anonymity in 3-Player Games. Finally, we proved that the Stochastic Shapley value is the only one that satisfies all aforementioned axioms.
In our future work, it would be interesting to analyze whether the choice of the suitable value for a given application can be driven by the specific probabilities of merging groups in a given environment. Also, in the spirit of the recent literature on game-theoretic network centralities, it would be interesting to study how values developed using the process approach can be used to rank nodes in networks.
References
Albizuri MJ, Arin J, Rubio J (2005) An axiom system for a value for games in partition function form. Int Game Theory Rev 7(01):63–72
Aldous D (1996) Probability distributions on cladograms. In: Random discrete structures. Springer, Berlin, pp 1–18
Aldous DJ (1985) Exchangeability and related topics. Springer, Berlin
Algaba E, Bilbao JM, Fernández JR (2007) The distribution of power in the European Constitution. Eur J Oper Res 176(3):1752–1766
Blei DM, Griffiths TL, Jordan MI (2010) The nested chinese restaurant process and bayesian nonparametric inference of topic hierarchies. J ACM 57(2):7
Bolger EM (1989) A set of axioms for a value for partition function games. Int J Game Theory 18(1):37–44
Cox LA Jr (1985) A new measure of attributable risk for public health applications. Manag Sci 31(7):800–813
De Clippel G, Serrano R (2008) Marginal contributions and externalities in the value. Econometrica 76(6):1413–1436
Derks JJ, Haller HH (1999) Null players out? Linear values for games with variable supports. Int Game Theory Rev 1(03n04):301–314
Feldman BE (1996) Bargaining, coalition formation, and value. Ph.D. Thesis, State University of New York at Stony Brook
Finus M (2003) New developments in coalition theory: an application to the case of global pollution. In: Marsiliani L, Rauscher M, Withagen C (eds) Environmental policy in an international perspective. Kluwer Academic Publishers, Dordrecht, pp 19–49
Goel A, Gruhn V (2008) A general vehicle routing problem. Eur J Oper Res 191(3):650–660
Gómez D, González-Arangüena E, Manuel C, Owen G, del Pozo M, Tejada J (2003) Centrality and power in social networks: a game theoretic approach. Math Soc Sci 46(1):27–54
Grabisch M, Funaki Y (2012) A coalition formation value for games in partition function form. Eur J Oper Res 221(1):175–185
Grabisch M, Kojadinovic I, Meyer P (2008) A review of methods for capacity identification in Choquet integral based multi-attribute utility theory: applications of the Kappalab R package. Eur J Oper Res 186(2):766–785
Hafalir IE (2007) Efficiency in coalition games with externalities. Games Econ Behav 61(2):242–258
Hu C-C, Yang Y-Y (2010) An axiomatic characterization of a value for games in partition function form. SERIEs 1(4):475–487
Kingman J (1978) The representation of partition structures. J Lond Math Soc 2(2):374–380
Kóczy L Á (2018) The Shapley-value. In Partition function form games: coalitional games with externalities. Springer, pp 173–200
Lehner F (2006) Cumulants in noncommutative probability theory IV. Noncrossing cumulants: De Finetti’s theorem and -inequalities. J Funct Anal 239(1):214–246
Macho-Stadler I, Pérez-Castrillo D, Wettstein D (2007) Sharing the surplus: an extension of the Shapley value for environments with externalities. J Econ Theory 135(1):339–356
Maskin E (2003) Bargaining, coalitions, and externalities. Presidential address to the Econometric Society, Institute for Advanced Study, Princeton University
McQuillin B (2009) The extended and generalized Shapley value: simultaneous consideration of coalitional externalities and coalitional structure. J Econ Theory 144(2):696–721
Myerson RB (1977) Values of games in partition function form. Int J Game Theory 6:23–31
Nagarajan M, Sošić G (2008) Game-theoretic analysis of cooperation among supply chain agents: review and extensions. Eur J Oper Res 187(3):719–745
Netessine S, Zhang F (2005) Positive vs. negative externalities in inventory management: implications for supply chain design. Manuf Serv Oper Manag 7(1):58–73
Pham Do KH, Norde H (2007) The Shapley value for partition function form games. Int Game Theory Rev 9(02):353–360
Plasmans JE, Engwerda J, Van Aarle B, Di Bartolomeo G, Michalak T (2006) Dynamic modeling of monetary and fiscal cooperation among nations, vol 8. Springer Science & Business Media, Berlin
Qin ZS (2006) Clustering microarray gene expression data using weighted Chinese restaurant process. Bioinformatics 22(16):1988–1997
Shapley LS (1953) A value for n-person games. In: Kuhn H, Tucker A (eds) Contributions to the theory of games, vol II. Princeton University Press, Princeton, pp 307–317
Skibski O, Michalak TP, Rahwan T (2018a) Axiomatic characterization of game-theoretic centrality. J Artif Intell Res 62:33–68
Skibski O, Michalak TP, Wooldridge M (2018b) The Stochastic Shapley value for games with externalities. Games Econ Behav 108:65–80
Teh YW, Jordan MI, Beal MJ, Blei DM (2005) Sharing clusters among related groups: Hierarchical Dirichlet processes. In: Advances in neural information processing systems (NIPS), pp 1385–1392
Acknowledgements
Oskar Skibski and Tomasz Michalak were supported by the Polish National Science Centre Grant 2015/19/D/ST6/03113.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
A Proof of Theorem 6
Theorem 10
Family of quasi-probability distributions p satisfies exchangeability, consistency, and conditional independence if and only if follows Ewens distribution (i.e., formula 8) for some \(\theta \!\in \! {\mathbb {R}} \!{\setminus }\! \{-1, -2, \ldots \}\).
Proof
Let p be a family of exchangeable, consistent, and conditionally independent quasi-probability distributions. In the first part of the proof, we will assume that \(p_2(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) \not \in \{0,1\}\). Next, we will consider these special cases.
Let us specify \(\theta \) as follows:
We will prove using an induction on n that \(p_n\) has the following form:
for every \(P \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\})\), and that \(\theta \not \in \{-1, -2, \ldots , n-1\}\).
For \(n = 1\), the result is trivial, and for \(n = 2\) it follows from the definition of \(\theta \) (formula (9)). Assume it holds for every \(n \le k\). We prove it holds also for \(n = k + 1\).
We will first prove that formula (10) works for the partition of singletons, i.e., \(P \!=\! \{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}, \ldots , \{{\mathbb {k}}\}\}\). From formula (1) we have that
Note that all partition in the sum above have \(k-1\) singleton coalitions and exactly one coalition with two elements. Thus, from exchangeability, they all have the same probability, equal to \(p_{k+1}(\{\{{{{\mathbb {1}}}, {{\mathbb {2}}}}\}, \{{\mathbb {3}}\}, \ldots , \{{{\mathbb {k}}+{{\mathbb {1}}}}\}\})\):
From conditional independence, we know that the probability that an element \(k+1\) forms a singleton coalition does not depend on the partition. Formally,
for some constant \(\beta \). Thus,
Now, using consistency, we replace \(p_{k+1}\) with \(p_k\) in \(p_{k+1}(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}, \ldots , \{{\mathbb {k}}\}\})\), and, by applying inductive assumption, we get:
Since \(\theta \not = 0\), the above formula simplifies to
If \(\theta = -k\), then formula (12) yields a contradiction: the right-hand side equal zero while the left-hand side does not, where the latter follows from our assumption. In other cases, formula (12) yields \(\beta = \frac{\theta }{\theta + k}\), and, from formula (11):
After deriving the formula for a partition with \(k+1\) coalitions, we will prove that \(p_{k+1}(P)\) can be derived using \(p_{k+1}\) for bigger partitions. Formally, we will use a recursive induction on the size of P. To this end, consider a partition P with the size smaller than \(k+1\), but larger than one: \(2 \le |P| \le k\). As stated before, in such a case, P contains at least two coalitions \(\{S, T\}\), one of which (say T) is bigger than a singleton coalition. Let \(T = \{T_1, T_2\}\) be a partition of T into two non-empty coalitions. From conditional independence we have that
Applying the inductive assumption for \(n \le k\) yields:
If \(p_{k+1}(P {\setminus } \{T\} \cup \{T_1, T_2\})\) follows formula (10), then \(p_{k+1}(P)\) follows it as well:
The remaining case when \(P = \{{{\mathbb {1}},{\mathbb {2}},\ldots ,{\mathbb {k}}+{\mathbb {1}}}\}\) follows from the fact that the probabilities of all partitions sum up to one. This concludes the main part of the proof.
Next, consider two special cases: \(p_2(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) = 1\) and \(p_2(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) = 0\).
Assume that \(p_2(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) = 1\). We will prove using induction that \(p_n(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}, \ldots , \{{\mathbb {n}}\}\}) = 1\), and \(p_n(P) = 0\) for different partitions \(P \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\})\). This probability distribution is Ewens distribution with \(\theta \rightarrow \infty \). This is trivial for \(n=1,2\). Assume this statement holds for \(n \le k\) (with \(k \ge 2\)). We will prove that it holds also for \(n = k+1\).
Consider partition \(P \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {k}},{\mathbb {k}}+1}\})\). If \(|P| \not = k+1\) and \(|P| \not = 1\), then P contains at least two coalitions \(\{S, T\}\), one of which (assume T) is bigger than singleton coalition. From exchangeability, we can assume that \(S = \{{{\mathbb {k}}-{\mathbb {s}}+{{\mathbb {1}}}, \ldots , {\mathbb {k}},{\mathbb {k}}+{{\mathbb {1}}}}\}\). Now, from conditional independence we have that \(p_n(P) = p_{n-s}(P {\setminus } \{S\}) \cdot \beta \) for some \(\beta \). But from the inductive assumption we have that \(p_{n-s}(P {\setminus } \{S\}) = 0\), thus \(p_n(P) = 0\). As \(p_n(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) = p_2(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) = 1\) is the sum of probabilities of partitions with at least 2 partitions, we get that \(p_n(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}, \ldots , \{{{\mathbb {k}}+{{\mathbb {1}}}}\}\}) = 1\). Analogously, \(p_n(\{\{{{{\mathbb {1}}},{{\mathbb {2}}}}\}\}) = 0\) is the sum of probabilities of partitions with at most k partitions, thus \(p_n(\{\{{{{\mathbb {1}}},\ldots ,{\mathbb {k}},{\mathbb {k}}+1}\}\}) = 0\). This concludes the proof of the case \(p_2(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) = 1\).
Assume \(p_2(\{\{{\mathbb {1}}\}, \{{\mathbb {2}}\}\}) = 0\). We will prove that \(p_n(\{\{{{{\mathbb {1}}},{{\mathbb {2}}},\ldots ,{\mathbb {n}}}\}\}) = 1\), and \(p_n(P) = 0\) for different partitions \(P \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {n}}}\})\), i.e., \(p_n\) is the Ewens probability distribution with \(\theta = 0\). For \(n=1\), and 2, it is trivial. Similarly to (i), we will use an induction. In particular, assume that our statement holds for \(n \le k\) (with \(k \ge 2\)). We will prove that it holds also for \(n = k+1\).
If \(P \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {k}}+{{\mathbb {1}}}}\})\) contains more than two coalitions, then, from conditional independence, the probability of P equals zero, as \(p_{k+1}(P) = p_{k+1-|S|}(P {\setminus } \{S\}) \cdot \beta = 0\) for \(S \in P\). Since \(k+2 \ge 4\), at least one coalition in every partition \(P \in {\mathscr {P}}(\{{{{\mathbb {1}}},\ldots ,{\mathbb {k}}+{{\mathbb {2}}}}\})\) with \(|P| > 2\) must be of size 2 or more, and we get also that \(p_{k+2}(P) = 0\). We will prove that if P contains two coalitions, then it also has zero probability. Our proof is based on formula (1) and the property of consistency. Specifically, we obtain:
$$\begin{aligned} p_k([a, k-a]) = p_{k+1}([a+1, k-a]) + p_{k+1}([a, k-a+1]), \end{aligned}$$(13)for every \(a > 0\), as we know that \(p_{k+1}([a,k-a,1]) = 0\). From the fact that \(p_k([a, k-a]) = 0\) for every \(a > 0\), we have that series
$$\begin{aligned} \langle p_{k+1}([k+1-\left\lfloor (k+1)/2 \right\rfloor , \left\lfloor (k+1)/2 \right\rfloor ]), \ldots , p_{k+1}([k, 2]), p_{k+1}([k+1, 1])\rangle \end{aligned}$$is equal to \(\langle \alpha , -\alpha , \alpha , \ldots , \pm \alpha \rangle \) for some \(\alpha \in {\mathbb {R}}\). Now, if k is even, i.e., \(k = 2m\) for some m, we get from formula (13) that \(0 = p_k([m,m]) = 2 p_{k+1}([m+1,m])\), so \(\alpha = 0\), and all probabilities equal zero. Otherwise, i.e., \(k = 2m+1\), by applying formula (13) for \(p_{k+1}\), we obtain that the series
$$\begin{aligned} \langle p_{k+2}([m+2, m+1]), \ldots , p_{k+2}([2m+1, 2]), p_{k+2}([2m+2, 1])\rangle \end{aligned}$$is equal to \(\langle \frac{1}{2} \alpha , -\frac{3}{2} \alpha , \frac{5}{2} \alpha , \ldots , \pm \frac{2m+1}{2} \alpha \rangle \). However, from conditional independence we get that \(0 = p_{k+2}([2m+1, 1, 1]) = p_{k+1}([2m+1, 1]) \cdot \beta \), and \(p_{k+2}([2m+2, 1]) = p_{k+1}([2m+1]) \cdot \beta \) for some \(\beta \). Thus, either \(p_{k+1}([2m+1, 1]) = 0\), or \(\beta = 0\). Both cases imply that \(\alpha = 0\), which concludes the proof. \(\square \)
B Summary of notation
- N :
-
The set of players \(N = \{1,2,\dots ,n\}\).
- S :
-
A coalition, i.e., subset of N.
- P :
-
A partition, i.e., any set of disjoint coalitions whose union is N.
- \({\mathscr {P}}(N)\) :
-
The set of all partitions over N. Also denoted \({\mathscr {P}}\).
- (S, P):
-
An embedded coalition: S is a coalition and P is a partition such that \(S \in P\).
- EC(N):
-
The set of all embedded coalitions over N. Also denoted EC.
- v :
-
A game (in a partition-function form), i.e., a mapping \(EC(N) \rightarrow {\mathbb {R}}\).
- \(\varphi \) :
-
A value of the game, i.e., a mapping from \({\mathbb {R}}^{EC(N)} \rightarrow {\mathbb {R}}^N\).
- \(\varphi _i(v)\) :
-
The value of player i in game v.
- \(\pi \) :
-
A permutation, i.e., a bijection \(S \rightarrow \{{{{\mathbb {1}}},{{\mathbb {2}}},\dots ,|{\mathbb {S}}|}\}\).
- \({{{\mathbb {1}}},{{\mathbb {2}}},\dots }\) :
-
The set of positions in a permutation.
- \(\varOmega (S)\) :
-
The set of all permutations of set S.
- \(C_i^{\pi }\) :
-
The set of players that appear in \(\pi \) after i, i.e., \(C_i^{\pi } = \{j \mid \pi (j) > \pi (i)\}\).
- \(\pi _{+i}\) :
-
A permutation obtained from \(\pi \in \varOmega (S)\) by adding player \(i \not \in S\) at the end.
- \(\pi _{id}\) :
-
An identity permutation—\(\pi _{id}(k) = {\mathbb {k}}\) for every \(k \in S\) where \(S = \{1,\dots ,|S|\}\).
- \(p_n\) :
-
A (quasi-)probability distribution on the set of all partitions of \(\{{{{\mathbb {1}}},\dots ,{\mathbb {n}}}\}\).
- \(p = (p_1,p_2,\dots )\) :
-
A family of (quasi-)probability distribution.
- \(e^{(S,P)}\) :
-
A game in which only (S, P) has non-zero value.
- \(S_{-i}, S_{+i}\) :
-
A shorthand notation for \(S {\setminus } \{i\}\), and \(S \cup \{i\}\).
- \(P_{-i}, P_{-T}\) :
-
A shorthand notation for \(\{S {\setminus } \{i\} \mid S \in P\}\) and \(\{S {\setminus } T \mid S \in P\}\).
- \(\tau _i^T(P)\) :
-
A shorthand notation for \(P_{-(T \cup \{i\})} \cup \{T \cup \{i\}\}\).
- \((S_{-i}, \tau _i^T(P))\) :
-
An embedded coalition obtained from (S, P) by moving player i from S to T.
- \({\hat{v}}\) :
-
A game (in a characteristic-function form), i.e., a mapping \(2^{N} \rightarrow {\mathbb {R}}\).
- \(SV_i({\hat{v}})\) :
-
The Shapley value of player i in game \({\hat{v}}\).
- \(\varphi _i^p(v)\) :
-
The p-Process Shapley value of player i in game v.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Skibski, O., Michalak, T. Fair division in the presence of externalities. Int J Game Theory 49, 147–172 (2020). https://doi.org/10.1007/s00182-019-00682-4
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-019-00682-4