1 Introduction
Glove games have been introduced in Shapley (1959): players are divided in two groups L and R, players in L own one left glove and players in R one right glove. The worth of a coalition S is the number of pairs of gloves that can be formed by the members of S:Players of different type (i.e. owning different types of gloves) are perfectly complementary, whereas players of the same type (i.e. owning the same type of gloves) are perfectly interchangeable and in competition for doing business with players of the other type. Glove games are examples of market games (Shapley and Shubik 1969) where players own nonnegative bundles of goods and the value of a coalition is computed by redistributing the initial endowments of their members such that the sum of the individual (continuous and concave) utilities is maximal. To be more precise, glove games are glove-market games: market games where all utility functions are the same and given by \(u(a)=\min \{a_1,\ldots ,a_m\}\) for every \(a\in {\mathbb{R}}^m_+\). In other words, combinations of 1 unit of every good are valuable and can be sold at a selling price that is normalized to 1. The classes of glove-market games, market games, flow games (Kalai and Zemel 1982), linear production games (Owen 1975) and risk allocation games (Csóka et al. 2009) all coincide with the class of totally balanced games, as argued in Apartsin and Holzman (2003) and Csóka et al. (2009). Glove-market games where each player owns one unit of precisely one good (like in glove games) are called unitary glove-market games in Apartsin and Holzman (2003), T(ype-based)-market games in Brânzei et al. (2007) and ocean games in Rosenmüller and Sudhölter (2002). We will refer to these games as multi-glove games here.
$$\begin{aligned} v(S)=\min \{|L\cap S|, |R\cap S|\}. \end{aligned}$$
Multi-glove games are totally balanced, so core elements exist for the game and all its subgames. However, it is not always possible to choose such core elements in a monotonic way: allocations to players do not decrease if the coalitions to which they belong become larger. In other words multi-glove games do not have to admit a population monotonic allocation scheme (pmas). In Sprumont (1990) it is shown that the four-player glove game with two players owning a left glove and two players a right glove lacks a pmas. In this note we generalize multi-glove games in the sense that players are allowed to own more than one glove but only gloves of the same type. We will refer to these games as weighted multi-glove games. We will show that these games are totally balanced (a result that by the way also directly follows from the fact that the class of weighted multi-glove games fall within the class of glove-market games). We will characterize the class of pmas-admissible weighted multi-glove games and the class of convex or supermodular weighted multi-glove games. Finally, we will provide an explicit expression for the Shapley value of the supermodular and a large part of the pmas-admissible weighted multi-glove games.
Advertisement
2 Preliminaries and notation
A Transferable Utility (TU) game (or, simply, a game) is a pair (N, v), where \(N=\{1,\dots , n\}\) is the set of players and \(v:2^{N}\rightarrow {\mathbb{R}}\) the characteristic function. By convention \(v(\emptyset )=0\). For every coalition \(S\subseteq N\) the number v(S) represents the (monetary) worth or profit S can achieve by cooperation.
An allocation is a vector \(x \in {\mathbb{R}}^N\). An allocation x is in the core C(N, v) (Gillies 1959) of game (N, v) if it is efficient (i.e., \(\sum _{i \in N} x_i = v(N)\)) and stable (i.e., \(\sum _{i \in S} x_i \ge v(S)\) for every coalition \(S \in 2^N\backslash \{\emptyset \}\)). So,It is a classical result that a game has a nonempty core if and only if it is balanced. Therefore, we will refer to such games as balanced games. For a game (N, v) and a coalition \(S \in 2^N\backslash \{\emptyset \}\) the subgame \((S,v_{\mid S})\) of (N, v) restricted to coalition S is defined by \(v_{\mid S}(R)=v(R)\) for every \(R \in 2^S\). A game (N, v) with all subgames (i.e. including (N, v) itself) having a nonempty core is called totally balanced.
$$\begin{aligned} C(N,v)=\left\{ x \in {\mathbb{R}}^N: \sum _{i \in N} x_i = v(N), \sum _{i \in S} x_i \ge v(S), \text{ for } \text{ every } S \subseteq N, S \ne \emptyset \right\} . \end{aligned}$$
A population monotonic allocation scheme or pmas (Sprumont 1990) of the game (N, v) is a scheme \((x_{S,i})_{S\in 2^N\backslash \{\emptyset \}, i\in S}\) with the properties A pmas provides an allocation vector for every coalition in a monotonic way: the value allocated to some player increases if the coalition to which he belongs becomes larger. If a game (N, v) has a pmas, then it is said to be pmas-admissible. It is easy to check that a pmas \((x_{S,i})_{S\in 2^N\backslash \{\emptyset \}, i\in S}\) provides a core element for the game and all its subgames, i.e. the allocation \((x_{S,i})_{i\in S} \in C(S,v_{\mid S})\) for every \(S \in 2^N\backslash \{\emptyset \}\). Therefore, a pmas-admissible game is also totally balanced.
(i)
\(\sum _{i\in S} x_{S,i}=v(S)\) for every \(S\in 2^N\backslash \{\emptyset \}\) (efficiency);
(ii)
\(x_{S,i} \le x_{T,i}\) for every \(S,T\in 2^N\backslash \{\emptyset \}\) and \(i\in N\) with \(i\in S\subset T\) (monotonicity).
Advertisement
A game (N, v) is supermodular or convex (Shapley 1971) if for every \(i\in N\) and for every \(S,T\subseteq N\backslash \{i\}\) with \(S\subset T\) we have \(v(S\cup \{i\})-v(S)\le v(T\cup \{i\})-v(T)\). Supermodular games are pmas-admissible (Sprumont 1990) and hence totally balanced as well.
The Shapley value \(\Phi (N,v)\) (Shapley 1953) is defined byfor every \(i\in N\). An alternative formula for the Shapley value is obtained by writing a game (N, v) as linear combination of unanimity games. For \(T\in 2^N\backslash \{\emptyset \}\) the unanimity game \(u_T\) is defined by \(u_T(S)=1\) if \(T\subseteq S\) and \(u_T(S)=0\) otherwise. Now \(v=\sum _{T\in 2^N\backslash \{\emptyset \}}\alpha _T(v)u_T\), where \(\alpha _T(v)=\sum _{S\in 2^T\backslash \{\emptyset \}}(-1)^{|T|-|S|}v(S)\) for every \(T\in 2^N\backslash \{\emptyset \}\), and the Shapley value is given byfor every \(i\in N\).
$$\begin{aligned} \Phi _i(N,v)=\sum _{S\in 2^{N\backslash \{i\}}}\frac{(|S|)!(n-|S|-1)!}{n!}(v(S\cup \{i\})-v(S)) \end{aligned}$$
$$\begin{aligned} \Phi _i(N,v)=\sum _{T\in 2^N\backslash \{\emptyset \}:i\in T}\frac{\alpha _T(v)}{|T|} \end{aligned}$$
3 Weighted multi-glove games
We first provide the definition of weighted multi-glove games.
Definition 3.1
Let \(P=\{P_1,\ldots ,P_k\}\) \((k\ge 2)\) be a partition of the player set N and \(w\in {\mathbb{N}}^N\). The weighted multi-glove game \((N,v^{P,w})\) is defined byfor every \(S\in 2^N\) (with the usual convention that 0 is the result of an empty summation).
$$\begin{aligned} v^{P,w}(S)=\min \left\{ \sum _{i\in S\cap P_j}w_i\,:\,j\in \{1,\ldots ,k\}\right\} \end{aligned}$$
The context of weighted multi-glove games is the following: there are k different complementary goods, and the player set N is partitioned into k groups \(P_1,\ldots ,P_k\), each group containing players owning units of the same good. Every player \(i\in N\) owns \(w_i\) units of the good specified by the partition element to which he belongs. Combinations of 1 unit of every good are valuable and can be sold at a selling price that is normalized to 1. Standard glove games (Shapley 1959) refer to the situation of 2 complementary goods (left gloves and right gloves), where each player owns one unit of one of the two goods. Weighted multi-glove games generalize these games in two directions: (1) there can be more than two goods (justifying the adjective ‘multi’); (2) every player is allowed to have more than one unit of some good (justifying the adjective ‘weighted’). In order to define weighted multi-glove games we assume that the player set N is partitioned in at least two sets. Of course, the game \((N,v^{P,w})\) can also be defined in case \(k=1\) (i.e. if \(P=\{N\}\)). In this case the game is an additive game (\(v^{P,w}(S)=\sum _{i\in S}w_i\) for every \(S\in 2^N\)) which is totally balanced, supermodular and pmas-admissible anyhow. Also note that weighted multi-glove games are monotonic: if \(S,T\in 2^N\) with \(S\subset T\) then \(v^{P,w}(S)\le v^{P,w}(T)\).
Standard glove games are known to be totally balanced. This result can be generalized to weighted multi-glove games in an obvious way.
Theorem 3.2
Weighted multi-glove games are totally balanced.
Proof
Let \((N,v^{P,w})\) be the weighted multi-glove game corresponding to partition \(P=\{P_1,\ldots ,P_k\}\) and weight vector \(w\in {\mathbb{N}}^N\). Let \(S \in 2^N\backslash \{\emptyset \}\). Determine \(j^*\in \{1,\ldots ,k\}\) such that \(\sum _{i\in S\cap P_{j^*}}w_i=\min \{\sum _{i\in S\cap P_j}w_i\,:\,j\in \{1,\ldots ,k\}\}=v^{P,w}(S)\). Define the vector \(x\in {\mathbb{R}}^S\) by \(x_i=w_i\) if \(i\in S\cap P_{j^*}\) and \(x_i=0\) if \(i\in S\backslash P_{j^*}\). Then \(\sum _{i\in S}x_i=\sum _{i\in S\cap P_{j^*}}x_i=\sum _{i\in S\cap P_{j^*}}w_i=v^{P,w}(S)=(v^{P,w})_{\mid S}(S)\). Moreover, for every \(R\subseteq S\), \(R\ne \emptyset\), we have \(\sum _{i\in R}x_i=\sum _{i\in R\cap P_{j^*}}x_i=\sum _{i\in R\cap P_{j^*}}w_i\ge \min \{\sum _{i\in R\cap P_j}w_i\,:\,j\in \{1,\ldots ,k\}\}=v^{P,w}(R)=(v^{P,w})_{\mid S}(R)\). So \(x\in C(S,(v^{P,w})_{\mid S})\). Since S was chosen in an arbitrary way we conclude that \((N,v^{P,w})\) is totally balanced. \(\square\)
Weighted multi-glove games do not have to be pmas-admissible: in Sprumont (1990) it is shown that the standard glove game with two players owning a left glove and two players owning a right glove does not have a pmas. So these games do not have to be supermodular either. In this note we characterize the subclasses of weighted multi-glove games that are supermodular and pmas-admissible respectively. First we characterize the subclass of supermodular weighted multi-glove games.
Theorem 3.3
Let \((N,v^{P,w})\) be a weighted multi-glove game with weight vector \(w\in {\mathbb{N}}^N\) and partition \(P=\{P_1,\ldots , P_k\}\). Then \((N,v^{P,w})\) is supermodular if and only if there is a \(j^*\in \{1,\ldots ,k\}\) such that for every \(j\in \{1,\ldots ,k\}\backslash \{j^*\}\) partition element \(P_j\) contains precisely one player \(i_j\) and \(w_{i_j}\ge \sum _{i\in P_{j^*}}w_i\) for every \(j\in \{1,\ldots ,k\}\backslash \{j^*\}\).
Proof
“\(\Leftarrow\)”. Suppose there is a \(j^*\in \{1,\ldots ,k\}\) such that for every \(j\in \{1,\ldots ,k\}\backslash \{j^*\}\) partition element \(P_j\) contains precisely one player \(i_j\) and \(w_{i_j}\ge \sum _{i\in P_{j^*}}w_i\) for every \(j\in \{1,\ldots ,k\}\backslash \{j^*\}\). Let \(l\in N\) and \(S\subset T\subseteq N\backslash \{l\}\).
If \(l\notin P_{j^*}\) and \(\cup _{j\in \{1,\ldots ,k\}\backslash \{j^*\}}P_{j}\subseteq S\cup \{l\}\) then.
$$v^{P,w}(S\cup \{l\})-v^{P,w}(S)=\sum _{i\in (S\cup \{l\})\cap P_{j^*}}w_i-0=\sum _{i\in (S\cup \{l\})\cap P_{j^*}}w_i\le \sum _{i\in (T\cup \{l\})\cap P_{j^*}}w_i=\sum _{i\in (T\cup \{l\})\cap P_{j^*}}w_i-0=v^{P,w}(T\cup \{i\})-v^{P,w}(T)$$
If \(l\notin P_{j^*}\) and \(\cup _{j\in \{1,\ldots ,k\}\backslash \{j^*\}}P_{j}\nsubseteq S\cup \{l\}\) then by monotonicity of \(v^{P,w}\).
$$v^{P,w}(S\cup \{l\})-v^{P,w}(S)=0-0=0\le v^{P,w}(T\cup \{l\})-v^{P,w}(T)$$
If \(l\in P_{j^*}\) and \(\cup _{j\in \{1,\ldots ,k\}\backslash \{j^*\}}P_{j}\subseteq S\) then.
$$v^{P,w}(S\cup \{l\})-v^{P,w}(S)=w_l= v^{P,w}(T\cup \{l\})-v^{P,w}(T)$$
If \(l\in P_{j^*}\) and \(\cup _{j\in \{1,\ldots ,k\}\backslash \{j^*\}}P_{j}\nsubseteq S\) thenagain by monotonicity of \(v^{P,w}\).
$$v^{P,w}(S\cup \{l\})-v^{P,w}(S)=0-0=0\le v^{P,w}(T\cup \{l\})-v^{P,w}(T),$$
“\(\Rightarrow\)”. Suppose \((N,v^{P,w})\) is supermodular. First, assume that there are at least two partition elements with at least two players. Without loss of generality assume that \(|P_1|\ge 2\) and \(|P_2|\ge 2\). Choose \(a,b\in P_1\), \(a\ne b\), and \(c,d\in P_2\), \(c\ne d\). Choose \(i_j\in P_j\) for every \(j\in \{3,\ldots ,k\}\). By supermodularity we havesosoFrom (1) we getso \(\min \{w_a,w_c,w_{i_3},\ldots ,w_{i_k}\}=w_c\). In a similar way we get \(\min \{w_a,w_d,w_{i_3},\ldots ,w_{i_k}\}=w_d\). Now, again using (1), we have \(w_a\ge \min \{w_a,w_c+w_d,w_{i_3},\ldots ,w_{i_k}\}\ge \min \{w_a,w_c,w_{i_3},\ldots ,w_{i_k}\}+\min \{w_a,w_d,w_{i_3},\ldots ,w_{i_k}\}=w_c+w_d\). Using a symmetry argument, interchanging the roles of a and b, we get \(w_b\ge w_c+w_d\). Again using a symmetry argument, now interchanging the roles of a and c and the roles of b and d, we get \(w_c\ge w_a+w_b\) and \(w_d\ge w_a+w_b\) as well. Hence \(w_a\ge w_c+w_d>w_c\ge w_a+w_b>w_a\). A contradiction.
$$\begin{aligned}&v^{P,w}(\{a,c,d,i_3,\ldots ,i_k\})-v^{P,w}((\{a,d,i_3,\ldots ,i_k\})\\&\quad \ge v^{P,w}(\{a,c,i_3,\ldots ,i_k\})-v^{P,w}(\{a,i_3,\ldots ,i_k\}) \end{aligned}$$
$$\begin{aligned}&\min \{w_a,w_c+w_d,w_{i_3},\ldots ,w_{i_k}\}-\min \{w_a,w_d,w_{i_3},\ldots ,w_{i_k}\}\\&\quad \ge \min \{w_a,w_c,w_{i_3},\ldots ,w_{i_k}\}-0, \end{aligned}$$
$$\begin{aligned} \min \{w_a,w_c+w_d,w_{i_3},\ldots ,w_{i_k}\}\ge & {} \min \{w_a,w_c,w_{i_3},\ldots ,w_{i_k}\}\nonumber \\&+\min \{w_a,w_d,w_{i_3},\ldots ,w_{i_k}\}. \end{aligned}$$
(1)
$$\begin{aligned} \min \{w_a,w_{i_3},\ldots ,w_{i_k}\}\ge & {} \min \{w_a,w_c+w_d,w_{i_3},\ldots ,w_{i_k}\}\\\ge & {} \min \{w_a,w_c,w_{i_3},\ldots ,w_{i_k}\}+\min \{w_a,w_d,w_{i_3},\ldots ,w_{i_k}\}\\> & {} \min \{w_a,w_c,w_{i_3},\ldots ,w_{i_k}\}, \end{aligned}$$
So there is at most one partition element which is not singleton. Without loss of generality assume that \(|P_j|=1\) for every \(j\in \{1,\ldots ,k-1\}\). Let \(i_j\) be the unique player in \(P_j\) for every \(j\in \{1,\ldots ,k-1\}\). If \(|P_k|=1\) we are done (taking \(j^*\in \{1,\ldots ,k\}\) such that \(P_{j^*}\) contains the player with minimal weight) so assume that \(|P_k|\ge 2\). Let \(S=\cup _{j=1}^{k-1}P_j=\{i_1,\ldots ,i_{k-1}\}\) and let \(i^*\in P_k\) be such that \(w_{i^*}=\min _{i\in P_k}w_i\). Again, by supermodularity we havesosoRepeating the arguments above we getandNow (2) reads \(\min \{w_{i_1},\ldots ,w_{i_{k-1}},\sum _{i\in P_k}w_i\}\ge \sum _{i\in P_k}w_i\) from which we infer that \(w_{i_j}\ge \sum _{i\in P_k}w_i\) for every \(j\in \{1,\ldots ,k-1\}\). This finishes the proof. \(\square\)
$$\begin{aligned} v^{P,w}(N)-v^{P,w}(N\backslash \{i^*\})\ge v^{P,w}(S\cup \{i^*\})-v^{P,w}(S), \end{aligned}$$
$$\begin{aligned}&\min \left\{ w_{i_1},\ldots ,w_{i_{k-1}},\sum _{i\in P_k}w_i\right\} -\min \left\{ w_{i_1},\ldots ,w_{i_{k-1}},\sum _{i\in P_k\backslash \{i^*\}}w_i\right\} \\&\quad \ge \min \{w_{i_1},\ldots ,w_{i_{k-1}},w_{i^*}\}-0, \end{aligned}$$
$$\begin{aligned}&\min \left\{ w_{i_1},\ldots ,w_{i_{k-1}},\sum _{i\in P_k}w_i\right\} \nonumber \\&\quad \ge \min \left\{ w_{i_1},\ldots ,w_{i_{k-1}},\sum _{i\in P_k\backslash \{i^*\}}w_i\right\} +\min \{w_{i_1},\ldots ,w_{i_{k-1}},w_{i^*}\}. \end{aligned}$$
(2)
$$\begin{aligned} \min \left\{ w_{i_1},\ldots ,w_{i_{k-1}},\sum _{i\in P_k\backslash \{i^*\}}w_i\right\} =\sum _{i\in P_k\backslash \{i^*\}}w_i \end{aligned}$$
$$\begin{aligned} \min \{w_{i_1},\ldots ,w_{i_{k-1}},w_{i^*}\}=w_{i^*}. \end{aligned}$$
So, the supermodular weighted multi-glove games are characterized by the fact that all but possibly one of the partition elements are singleton sets and the weight of the player in these sets exceeds the total weight of the players in the partition element which is not singleton (if any). In particular this implies that weighted multi-glove games with only singleton partition elements are supermodular anyhow.
The characterization of the pmas-admissible weighted multi-glove games has a similar flavour. If there is a singleton partition element the weighted multi-glove games are pmas-admissible anyhow and, in case all partition elements contain at least two players, they are precisely pmas-admissible if there is one ‘dominated’ partition element in the sense that every individual player in a non-dominated partition element has a weight that exceeds the total weight of the players in the dominated partition element.
Theorem 3.4
Let \((N,v^{P,w})\) be a weighted multi-glove game with weight vector \(w\in {\mathbb{N}}^N\) and partition \(P=\{P_1,\ldots , P_k\}\). Then \((N,v^{P,w})\) is pmas-admissible if and only if either there is at least one singleton partition element or \(|P_j|\ge 2\) for every \(j\in \{1,\ldots ,k\}\) and there is a \(j^*\in \{1,\ldots ,k\}\) such that for every \(j\in \{1,\ldots ,k\}, j\ne j^*\) and every \(i\in P_{j}\) we have \(w_{i}\ge \sum _{l\in P_{j^*}}w_l\).
Proof
“\(\Leftarrow\)”. First, assume that there is at least one singleton partition element. Let \(j\in \{1,\ldots ,k\}\) be such that \(|P_j|=1\) and let \(i^*\) be the unique player in \(P_j\). It is obvious that \(v^{P,w}(S)=0\) if \(i^*\notin S\). Using monotonicity of \((N,v^{P,w})\) we find that the scheme \((x_{S,i})_{S\in 2^N\backslash \{\emptyset \}, i\in S}\) defined by \(x_{S,i}=v^{P,w}(S)\) if \(i=i^*\) and \(x_{S,i}=0\) if \(i\ne i^*\) is a pmas of \((N,v^{P,w})\). Second, assume that \(|P_j|\ge 2\) for every \(j\in \{1,\ldots ,k\}\) and there is a \(j^*\in \{1,\ldots ,k\}\) such that for every \(j\in \{1,\ldots ,k\}, j\ne j^*\) and every \(i\in P_{j}\) we have \(w_{i}\ge \sum _{l\in P_{j^*}}w_l\). It is obvious that for S with \(S\cap P_j\ne \emptyset\) for every \(j\in \{1,\ldots ,k\}, j\ne j^*\) we have \(v^{P,w}(S)=\sum _{i\in S\cap P_{j^*}}w_i\) and for other S we have \(v^{P,w}(S)=0\). Now the scheme \((x_{S,i})_{S\in 2^N\backslash \{\emptyset \}, i\in S}\) defined by \(x_{S,i}=w_i\) if \(i\in P_{j^*}\) and \(S\cap P_j\ne \emptyset\) for every \(j\in \{1,\ldots ,k\}, j\ne j^*\) and \(x_{S,i}=0\) otherwise is a pmas of \((N,v^{P,w})\).
“\(\Rightarrow\)”. Assume that \((N,v^{P,w})\) is pmas-admissible, let \((x_{S,i})_{S\in 2^N\backslash \{\emptyset \}, i\in S}\) be a pmas for \((N,v^{P,w})\). Suppose that \(|P_j|\ge 2\) for every \(j\in \{1,\ldots ,k\}\). Let \(i_1\in N\) be such that \(w_{i_1}=\min _{i\in N}w_i\). Without loss of generality we may assume that \(i_1\in P_1\). Let \(i_2\in \cup _{j=2}^kP_j\) be such that \(w_{i_2}=\min _{i\in \cup _{j=2}^kP_j}w_i\). We can also assume without loss of generality that \(i_2\in P_2\). Choose players \(i_j\in P_j\) for every \(j\in \{3,\ldots ,k\}\) in an arbitrary way. Define \(S=\{i_1,i_2,\ldots ,i_k\}\). Let \(j\in \{2,\ldots ,k\}\). As \(|P_j|\ge 2\) we can choose a player \(i^*\in P_j\), \(i^*\ne i_j\). Now \(v^{P,w}(S\cup \{i^*\})=v^{P,w}((S\cup \{i^*\})\backslash \{i_j\})=w_{i_1}\). Hence \(x_{S\cup \{i^*\},i_j}=\sum _{l\in S\cup \{i^*\}}x_{S\cup \{i^*\},l}-\sum _{l\in (S\cup \{i^*\})\backslash \{i_j\}}x_{S\cup \{i^*\},l}=v^{P,w}(S\cup \{i^*\})-\sum _{l\in (S\cup \{i^*\})\backslash \{i_j\}}x_{S\cup \{i^*\},l}\le v^{P,w}(S\cup \{i^*\})-\sum _{l\in (S\cup \{i^*\})\backslash \{i_j\}}x_{(S\cup \{i^*\})\backslash \{i_j\},l}=v^{P,w}(S\cup \{i^*\})-v^{P,w}((S\cup \{i^*\})\backslash \{i_j\})=w_{i_1}-w_{i_1}=0\). Now from monotonicity of a pmas it follows that \(x_{S,i_j}\le x_{S\cup \{i^*\},i_j}\le 0\) as well. On the other hand we have \(x_{S,i_j}\ge x_{\{i_j\},i_j}=v^{P,w}(\{i_j\})=0\). We conclude that \(x_{S,i_j}=0\) for every \(j\in \{2,\ldots ,k\}\). As \(v^{P,w}(S)=w_{i_1}\) we get \(x_{S,i_1}=w_{i_1}\). Now consider coalition \(T=P_1\cup \{i_2,\ldots ,i_k\}\). We have \(v^{P,w}(T)=\min \{\sum _{l\in P_1}w_l,w_{i_2}\}\) and \(v^{P,w}(T\backslash \{i_1\})=\min \{\sum _{l\in P_1\backslash \{i_1\}}w_l,w_{i_2}\}\). Now \(x_{T,i_1}=\sum _{l\in T}x_{T,l}-\sum _{l\in T\backslash \{i_1\}}x_{T,l}=v^{P,w}(T)-\sum _{l\in T\backslash \{i_1\}}x_{T,l}\le v^{P,w}(T)-\sum _{l\in T\backslash \{i_1\}}x_{T\backslash \{i_1\},l}=v^{P,w}(T)-v^{P,w}(T\backslash \{i_1\})\). As \(S\subset T\) we get \(w_{i_1}=x_{S,i_1}\le x_{T,i_1}\le v^{P,w}(T)-v^{P,w}(T\backslash \{i_1\})=\min \{\sum _{l\in P_1}w_l,w_{i_2}\}-\min \{\sum _{l\in P_1\backslash \{i_1\}}w_l,w_{i_2}\}\), so \(\min \{\sum _{l\in P_1}w_l,w_{i_2}\}\ge w_{i_1} + \min \{\sum _{l\in P_1\backslash \{i_1\}}w_l,w_{i_2}\}= \min \{\sum _{l\in P_1}w_l,w_{i_1}+w_{i_2}\}\). From this last inequality we derive that \(w_{i_2}\ge \sum _{l\in P_1}w_l\). So, for every \(j\in \{2,\ldots ,k\}\) and \(i\in P_j\) we have \(w_i\ge w_{i_2} \ge \sum _{l\in P_1}w_l\). This finishes the proof. \(\square\)
It is easy to see that pmas-admissible weighted multi-glove games without singleton partition elements have a unique dominated partition element. In this case, the following theorem shows that the core is a singleton (every player in the dominated partition element receives his weight, whereas the other players receive a zero payoff) which obviously can be extended to a pmas.
Theorem 3.5
Let \((N,v^{P,w})\) be a weighted multi-glove game with weight vector \(w\in {\mathbb{N}}^N\) and partition \(P=\{P_1,\ldots , P_k\}\) such that \(|P_j|\ge 2\) for every \(j\in \{1,\ldots ,k\}\) and there is a \(j^*\in \{1,\ldots ,k\}\) such that for every \(j\in \{1,\ldots ,k\}, j\ne j^*\) and every \(i\in P_{j}\) we have \(w_{i}\ge \sum _{l\in P_{j^*}}w_l\). Then \(C(N,v^{P,w})=\{z\}\), with \(z \in {\mathbb{R}}^N\) such that \(z_i=w_i\), if \(i \in P_{j^*}\) and \(z_i=0\), otherwise.
Proof
By Theorem 3.4, it immediately follows that \(C(N,v^{P,w}) \ne \emptyset\). Consider a core allocation \(x \in C(N,v^{P,w})\).
We first prove that \(x_i=0\) for all \(i \in N \setminus P_{j^*}\). Let \(i \in N \setminus P_{j^*}\). Notice that \(N \setminus \{i\}\) contains at least one member of each partition element different from \(P_{j^*}\) and \(\sum _{l \in P_{j^*} } w_l\) is smaller or equal than any weight of players not in \(P_{j^*}\). So, by Definition 3.1, we havewhere the inequality follows from the core stability of allocation x. Moreover, by the core efficiency of allocation x, we also haveSo, combining relations (3) and (4), we have \(x_i \le 0\). On the other hand, by the individual rationality of allocation x, we also have that \(x_i \ge v^{P,w}(\{i\})= 0\), and then it follows \(x_i=0\).
$$\begin{aligned} v^{P,w}(N \setminus \{i\})= \sum _{l \in P_{j^*} } w_l \le \sum _{l \in N \setminus \{i\} } x_l, \end{aligned}$$
(3)
$$\begin{aligned} v^{P,w}(N)=\sum _{l \in P_{j^*} } w_l= \sum _{l \in N } x_l . \end{aligned}$$
(4)
We now prove that \(x_i=w_i\) for all \(i \in P_{j^*}\). Let \(i \in P_{j^*}\). Again, notice thatwhere the equality follows from the definition of \(v^{P,w}\) and the fact that \(\sum _{l \in P_{j^*} \setminus \{i\} } w_l\) is still smaller or equal than any weight of players not in \(P_{j^*}\), and the inequality from the core stability of allocation x. So, combining relations (4) and (5), we have that \(x_i \le w_i\).
$$\begin{aligned} v^{P,w}(N \setminus \{i\})= \sum _{l \in P_{j^*} \setminus \{i\}} w_l \le \sum _{l \in N \setminus \{i\} } x_l, \end{aligned}$$
(5)
Then, by relation (4) and the fact that \(x_l=0\) for all \(l \in N \setminus P_{j^*}\), we finally conclude that \(x_i = w_i\) for all \(i \in P_{j^*}\).\(\square\)
So, for weighted multi-glove games considered in Theorem 3.5, all core elements can be extended to a pmas. This is however not necessarily true for core elements of pmas-admissible weighted multi-glove games with a singleton partition element, as the next example shows.
Example 3.6
Let \((N,v^{P,w})\) be the weighted multi-glove game with \(N=\{1,2,3,4,5\}\), \(P=\{\{1,2\},\{3,4\},\{5\}\}\) and \(w=(1,1,1,1,2)\). This game is an extension of the famous example in Sprumont (1990) (the standard glove game with two players owning a left glove and two players owning a right glove) with a fifth player in a new (singleton) partition element and weight 2. It is easy to show that \(y=(0.5,0.5,0.5,0.5,0)\) is a core element of this game. Suppose that \((x_{S,i})_{S\in 2^N\backslash \{\emptyset \}, i\in S}\) is a pmas that extends y, i.e. \((x_{N,i})_{i\in N}=y\). Let \(S_1=\{1,3,5\}\). As \(1=y_1+y_3+y_5\ge x_{S_1,1}+x_{S_1,3}+x_{S_1,5}=v^{P,w}(S_1)=1\) we get \(x_{S_1,1}=y_1=0.5\), \(x_{S_1,3}=y_3=0.5\) and \(x_{S_1,5}=y_5=0\). A similar argument with \(S_2= \{2,3,5\}\) yields \(x_{S_2,2}=y_2=0.5\), \(x_{S_2,3}=y_3=0.5\) and \(x_{S_2,5}=y_5=0\). Now for \(S_3= \{1,2,3,5\}\) we find \(0.5=x_{S_1,1}\le x_{S_3,1}\le x_{N,1}=y_1=0.5\), \(0.5=x_{S_2,2}\le x_{S_3,2}\le x_{N,2}=y_2=0.5\), \(0.5=x_{S_1,3}\le x_{S_3,3}\le x_{N,3}=y_3=0.5\), and \(0=x_{S_1,5}\le x_{S_3,5}\le x_{N,5}=y_5=0\). So, \(x_{S_3,1}=x_{S_3,2}=x_{S_3,3}=0.5\) and \(x_{S_3,5}=0\). So \(v^{P,w}(S_3)=x_{S_3,1}+x_{S_3,2}+x_{S_3,3}+x_{S_3,5}=1.5\). But \(v^{P,w}(S_3)=1\), a contradiction.
Consider weighted multi-glove games where there is a ‘dominated’ partition element: every individual player in the other partition elements has a weight that exceeds the total weight of the players in the dominated partition element. Note that this covers the supermodular weighted multi-glove games and the pmas-admissible weighted multi-glove games without singleton partition elements. Next, we show that the Shapley value of such weighted multi-glove games can be computed as a linear combination of some particular weights and using coefficients that only depend on the size of a restricted number of coalitions, avoiding the explicit (and computationally expensive) calculation of the characteristic function.
Theorem 3.7
Let \((N,v^{P,w})\) be a weighted multi-glove game with weight vector \(w\in {\mathbb{N}}^N\) and partition \(P=\{P_1,\ldots , P_k\}\). Assume there is a \(j^*\in \{1,\ldots ,k\}\) such that for every \(j\in \{1,\ldots ,k\}, j\ne j^*\) and every \(i\in P_{j}\) we have \(w_{i}\ge \sum _{l\in P_{j^*}}w_l\). Then for every \(t\in N\) we have
$$\begin{aligned} \Phi _t(N,v^{P,w})=\left\{ \begin{array}{ll}w_t\cdot { \sum _{T\in 2^{N\backslash P_{j^*}}:T\cap P_j\ne \emptyset \forall j\ne j^*}}(-1)^{|T|-(k-1)}\cdot \frac{1}{1+|T|}&{}\text{ if } t\in P_{j^*}\\ ({\sum _{i\in P_{j^*}}w_i})\cdot {\sum _{T\in 2^{N\backslash P_{j^*}}:T\cap P_j\ne \emptyset \forall j\ne j^*,t\in T}}(-1)^{|T|-(k-1)}\cdot \frac{1}{1+|T|}&{}\text{ if } t\notin P_{j^*}. \end{array}\right. \end{aligned}$$
Proof
We will show that \(v^{P,w}\) can be written as linear combination of unanimity games in the following way:The formula for the Shapley value then follows in a straightforward way. Let \(S\in 2^N\). We haveFor a finite nonempty set A the number of odd subsets equals the number of even subsets: \(\sum _{B:B\subseteq A}(-1)^{|B|-1}=0\). If we exclude the empty (even) subset from the summation we get \(\sum _{B:\emptyset \ne B\subseteq A}(-1)^{|B|-1}=1\). Therefore we get that if \(P_j\cap S\ne \emptyset\) then \(\sum _{A_j:\emptyset \ne A_j\subseteq P_j\cap S}(-1)^{|A_j|-1}=1\). Of course, if \(P_j\cap S=\emptyset\) then \(\sum _{A_j:\emptyset \ne A_j\subseteq P_j\cap S}(-1)^{|A_j|-1}=0\) (empty sum). SoThis finishes the proof. \(\square\)
$$\begin{aligned} v^{P,w}={\sum _{i\in P_{j^*}}}\left( w_i\cdot { \sum _{T\in 2^{N\backslash P_{j^*}}:T\cap P_j\ne \emptyset \forall j\ne j^*}}(-1)^{|T|-(k-1)}\cdot u_{\{i\}\cup T}\right) . \end{aligned}$$
$$\begin{aligned}&{\sum _{i\in P_{j^*}}}\left( w_i\cdot { \sum _{T\in 2^{N\backslash P_{j^*}}:T\cap P_j\ne \emptyset \forall j\ne j^*}}(-1)^{|T|-(k-1)}\cdot u_{\{i\}\cup T}(S)\right) \\&\quad ={\sum _{i\in P_{j^*}\cap S}}\left( w_i\cdot { \sum _{T\in 2^{S\backslash (P_{j^*}\cap S)}:T\cap P_j\ne \emptyset \forall j\ne j^*}}(-1)^{|T|-(k-1)}\right) \\&\quad ={\sum _{i\in P_{j^*}\cap S}}\left( w_i\cdot { \sum _{(A_j)_{j\ne j^*}:\emptyset \ne A_j\subseteq P_j\cap S\forall j\ne j^*}}(-1)^{\sum _{j\ne j^*}(|A_j|-1)}\right) \\&\quad ={\sum _{i\in P_{j^*}\cap S}}\left( w_i\cdot { \sum _{(A_j)_{j\ne j^*}:\emptyset \ne A_j\subseteq P_j\cap S\forall j\ne j^*}}\prod _{j\ne j^*}(-1)^{|A_j|-1}\right) \\&\quad ={\sum _{i\in P_{j^*}\cap S}}\left( w_i\cdot { \prod _{j\ne j^*}\sum _{A_j:\emptyset \ne A_j\subseteq P_j\cap S}}(-1)^{|A_j|-1}\right) . \end{aligned}$$
$$\begin{aligned} {\sum _{i\in P_{j^*}\cap S}}\left( w_i\cdot { \prod _{j\ne j^*}\sum _{A_j:\emptyset \ne A_j\subseteq P_j\cap S}}(-1)^{|A_j|-1}\right)= & {} \left\{ \begin{array}{cl}{\sum _{i\in P_{j^*}\cap S}}w_i&{}\text{ if } P_j\cap S\ne \emptyset \forall j\ne j^*\\ 0&{}\text{ otherwise }\end{array}\right. \\= & {} v^{P,w}(S). \end{aligned}$$
Note that according to the Shapley value players in the dominated partition element receive a payoff proportional to their weight, whereas players in dominating partition elements receive a share of the total revenue \(\sum _{i\in P_{j^*}}w_i\). In the supermodular case (so \(|P_j|=1\) for every \(j\ne j^*\)) it is easy to see that \(\Phi _t(N,v^{P,w})=\frac{1}{k}\cdot w_t\) if \(t\in P_{j^*}\) and \(\Phi _t(N,v^{P,w})=\frac{1}{k}\cdot \sum _{i\in P_{j^*}}w_i\) if \(t\notin P_{j^*}\), because the only set \(T\in 2^{N\backslash P_{j^*}}\) such that \(T\cap P_j\ne \emptyset\) for every \(j\ne j^*\) is the set \(N\backslash P_{j^*}\) with cardinality \(k-1\). So all players in the dominating partition elements get an equal share of the total revenue. In cases where not all dominating partition elements are singleton players in different dominating partition elements can get a different share of the total revenue. The following example illustrates this.
Example 3.8
Let \(N=\{1,2,3,4,5,6,7\}\) be partitioned into \(P_1=\{1,2\}\), \(P_2=\{3,4,5\}\) and \(P_3=\{6,7\}\). Let \(w\in {\mathbb{N}}^N\) be such that \(w_i\ge w_1+w_2\) for every \(i\in P_2\cup P_3\). So \(P_1\) is the dominated partition element. Applying Theorem 3.7 we get \(\Phi _t(N,v^{P,w})= \frac{7}{12} w_t\) if \(t\in P_1\), \(\Phi _t(N,v^{P,w})= \frac{1}{20}(w_1+w_2)\) if \(t\in P_2\) and \(\Phi _t(N,v^{P,w})= \frac{2}{15}(w_1+w_2)\) if \(t\in P_3\).
In absence of a dominated partition element we cannot expect to be able to compute the Shapley value in an efficient way, as suggested by the following example.
Example 3.9
Let \(N=\{1,2,3,4\}\) be partitioned into \(P_1=\{1,2\}\) and \(P_2=\{3,4\}\). Let \(w\in {\mathbb{N}}^N\) be given by \(w_1=2\), \(w_2=3\), \(w_3=4\) and \(w_4=5\). Note that \(P_1\) is not dominated by \(P_2\) because \(w_3<w_1+w_2\). One readily checks that \(v^{P,w}\) can be written as linear combination of unanimity games in the following way:From this we infer that \(\Phi (N,v^{P,w})=(\frac{15}{12},\frac{23}{12},\frac{9}{12},\frac{13}{12})\). Note that in none of the partition elements the allocation is proportional to the individual weights.
$$\begin{aligned} v^{P,w}=2u_{\{1,3\}}+2u_{\{1,4\}}+3u_{\{2,3\}}+3u_{\{2,4\}}-u_{\{1,2,3\}}-2u_{\{1,3,4\}}-3u_{\{2,3,4\}}+u_{\{1,2,3,4\}}. \end{aligned}$$
Let us finish this note by making a remark about the weight vector. We assumed the weights to be positive and integer-valued, in order to stay close to the context of gloves. However, all results in this note are valid as well when the weights are assumed to be positive and real-valued. If we would like to generalize our results to nonnegative weights (i.e. we allow for zero weights as well) we have to be careful. Of course, a player with zero weight is a null player and adding or removing such a player does not affect properties like totally balancedness, pmas-admissibility and supermodularity. The statement in Theorem 3.3 however should be rephrased into “\((N,v^{P,w})\) is supermodular if and only if there is a \(j^*\in \{1,\ldots ,k\}\) such that for every \(j\in \{1,\ldots ,k\}\backslash \{j^*\}\) partition element \(P_j\) contains precisely one player \(i_j\) with positive weight and \(w_{i_j}\ge \sum _{i\in P_{j^*}}w_i\) for every \(j\in \{1,\ldots ,k\}\backslash \{j^*\}\).”
Acknowledgements
The authors would like to thank an anonymous reviewer and the associate editor for their constructive and valuable comments on a previous version of this paper. S. Moretti acknowledges a financial support from the projects AMANDE ANR-13-BS02-0004 and THEMIS ANR-20-CE23-0018 of the French National Research Agency (ANR).
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.