Jean-Joseph-Xavier Bidauld (1758-1846) was a French painter.
The principle of monotonicity for cooperative games states that if a game changes so that some player’s contribution to all coalitions increases or stays the same then the player’s allocation should not decrease. Monotonicity is a general principle of fair division which states that as the underlying data of a problem change, the solution should change in parallel fashion. It is particularly germane to applications in which allocations are not made once and for all, but are reassessed periodically as new information emerges. This is the case, for example, in dividing the joint benefits or costs of a cooperative enterprise fairly among the partners when the underlying structure of the enterprise is evolving over time. Such a situation can be modelled by a cooperative game. We give several formulations of the monotonicity principle for cooperative games and characterize different solution concepts via this property (Young \cite[p.65]{you85}).
Aggregate Monotonicity.
A frequently encountered form of monotonicity is the aggregate monotonicity. This principle states that if the value of the coalition of the whole increases, while the worth of all other coalitions remains fixed, then no player should get less than before:
\[\mbox{if \(v(N)\geq u(N)\) and \(v(S)=u(S)\) for all \(S\subseteq N\), then \(\phi_{i}(v)\geq\phi_{i}(u)\) for all \(i\).}\]
It also has the following natural interpretation in the cost allocation context. Suppose that all players agree to cooperate and undertake an investment project most efficient for the whole group with a specified allocation of estimated costs. If a cost overrun occurs, how should it be allocated? Since the alternative project were not tried, the available data are the cost of the project actually undertaken and the previously estimated costs of those not undertaken. In other words, only the datum \(v(N)\) has changed. Aggregate monotonicity says that, however the overrun may be allocated, no one should benifit by having his assessment reduced. In the context of cost allocation in a firm, it says that an in aggregate overhead costs should not benefit any division. Several well-known allocation procedures obey this principle (Young \cite[p.66-67]{you85}).
The egalitarian rule divides the savings from the grand coalition equally among the players irrespective of the value of other coalitions:
\[\phi_{i}(v)=\frac{v(N)}{|N|}.\]
This method is obviously monotonic in the aggregate Another method that is monotonic in the aggregate is the Shapley value:
\[\phi_{i}(v)=\sum_{\{S:i\in S\}}\frac{(|S|-1)!(|N|-|S|)!}{|N|!}v_{i}(S),\]
where \(v_{i}(S)\) represents the marginal contribution of \(i\) to \(S\) given by
\begin{equation}{\label{young85eq3}}\tag{1}
v_{i}(S)=\left\{\begin{array}{ll}
v(S)-v(S\setminus\{i\}) & \mbox{if \(i\in S\)}\\
v(S\cup\{i\})-v(S) & \mbox{if \(i\not\in S\)}.
\end{array}\right .
\end{equation}
However the nucleolus is not monotonic (Young \cite[p.67-68]{you85}).
Coalitional Monotonicity.
A method satisfies coalitional monotonicity if an increase in the worth of a particular coalition implies no decrease in the allocation to any member of that coalition:
\[\mbox{if \(v(T)\geq u(T)\) for some \(T\) and \(v(S)=u(S)\) for all \(S\neq T\), then \(\phi_{i}(v)\geq\phi_{i}(u)\) for all \(i\in T\).}\]
It is equivalent to:
\begin{equation}{\label{young85eq5}}\tag{2}
\begin{array}{l}
\mbox{if \(v(S)\geq u(S)\) for all \(S\) containing \(i\) and \(v(S)=u(S)\)
for all \(S\) not containing \(i\),}\\
\mbox{then \(\phi_{i}(v)\geq\phi_{i}(u)\)}.
\end{array}
\end{equation}
Therefore, the coalitional monotonicity can also be understood as saying that if a particular player gains in the strength of his claim because the alternatives available to him increase in value whereas the value of the alternative not involving him stay fixed, then he does not lose (Young \cite[p.68]{you85}).
Monotonicity in the sense of (\ref{young85eq5}) is particularly relevant to cost allocation in the firm. Since a division manager’s control is essentially over the costs of his production process, increasing the efficiency of his operations (by lowering the common costs of all coalitions containing him) should never damage his individual profit statement. Otherwise “individual rational actions based on the cost assignment may add up to corporate idiocy”. The Shaply value satisfies (\ref{young85eq5}) and so does the egalitarian rule (Young \cite[p.69]{you85}).
Let us recall that the core solution is given in the sense
\[\left\{{\bf x}:\sum_{i\in N}x_{i}=v(N)\mbox{ and }\sum_{i\in S}\geq v(S)\mbox{ for all }S\right\}.\]
Theorem. (Young \cite[p.69]{you85}). For \(|N|\geq 5\), no core allocation rule is coalitionally monotonic. \(\sharp\)
Strong Monotonicity.
Coalitional monotonicity refers to monotonic changes in the absolute value of the coalitions containing a given player. More likely to occur in practice are situations where the worth of the coalitions containing a given player \(i\) increase relative to the worth of the coalitons not
containing \(i\). In these cases, player \(i\)’s allocation should certainly not decrease either. For example, if several division managers simultaneously take steps to increase efficiency by decreasing joint costs, but one division makes a greater relative improvement in the sense that its marginal contribution to all possible coalition increases, then that division should not be penalized. A solution function \(\boldsymbol{\phi}\) satisfies strong monoitonicity if and only if
\[\mbox{$v_{i}(S)\geq u_{i}(S)$ for all \(S\) implies \(\phi_{i}(v)\geq\phi_{i}(u)\)},\]
where the marginal contribution \(v_{i}\) and \(u_{i}\) are shown in (\ref{young85eq3}). Recall that the solution function \(\boldsymbol{\phi}\) is {\bf symmetric} if and only if, for all permutation \(\pi\) of \(N\), \(\pi_{\pi (i)}(\pi v)=\phi_{i}(v)\), where \(\pi v(S)=v(\pi (S))\) for all \(S\subseteq N\) (Young \cite[p.69]{you85}).
Theorem. (Young \cite[p.70]{you85}). The Shapley value is strongly monotonic. If \(\boldsymbol{\phi}\) is a
symmetric and strongly monotonic solution function, then \(\boldsymbol{\phi}\) is a Shapley value. In other words, the Shapley value is the unique symmetric solution that is strongly monotonic. \(\sharp\)
The above theorem also holds true if it stays entirely within the class of superadditive games by slightly modifying the proof.
Population Monotonic Allocation Schemes.
Recall the PMAS in Definition \ref{sprd300} and the extended marginal contribution in (\ref{ga31}). We can similarly define the extended Shapley value in the obvious way, and show that the extended Shapley value is the arithmetic average of the extended marginal contribution. The extended Shapley value of the cooperative game \((N,v)\) is the vector \(\bar{\boldsymbol{\phi}}(v)\) defined componentwise as follows. For \(S\subseteq N\) and \(i\in S\), \(\bar{\phi}_{i}^{S}(v)=\phi_{i}(v^{S})\), where \(\boldsymbol{\phi}(v^{S})=(\phi_{i}(v^{S}))_{i\in S}\) is the Shapley value of the subgame \((S,v^{S})\). (Sprumont \cite[p.389]{spr})
\begin{equation}{\label{sprpa}}\tag{3}\mbox{}\end{equation}
Proposition \ref{sprpa}. (Sprumont \cite[p.389]{spr}). Given a cooperative game \((N,v)\), the following equality holds true
\[\bar{\phi}_{i}^{S}(v)=\frac{1}{|N|!}\sum_{\pi\in\Pi (N)}x_{i}^{\pi ,S}. \sharp\]
From Propositions \ref{sprp3} and \ref{sprpa}, we have the following corollary.
Corollary. (Sprumont \cite[p.383]{spr}). If the cooperative game \((N,v)\) is convex, then its extended Shapley value is a PMAS
of \((N,v)\). \(\sharp\)
We point out that the convexity assumption may be slightly weakened without jeopardizing the existence of a PMAS. We say that a player \(i\in N\) is convex with respect to the game \((N,v)\) if and only if
\[v(S)-v(S\setminus\{i\})\leq v(T)-v(T\setminus\{i\})\]
whenever \(S\subseteq T\subseteq N\). We may check that adding a convex player to a game preserves the existence of a PMAS. That is to say, if the subgame \((N,v^{N\setminus\{i\}})\) has a PMAS and \(i\) is convex with respect to \((N,v)\), then \((N,v)\) possesses a PMAS as well. As a consequence, it is not necessary that all players be convex to ensure that a PMAS exists. For instance, every totally balanced game with at least \(n-3\) convex players \((n\geq 3\)) has a PMAS (Sprumont \cite[p.383]{spr}).
For any coalition \(T\), let \(\boldsymbol{\phi}(v^{T})\) be the Shapley value of the subgame \((T,v^{T})\). We define a vector \(\boldsymbol{\psi}=(\psi_{i}^{T})_{i\in T,T\subseteq N}\) recursively as follows:
\begin{equation}{\label{spreqc}}\tag{4}
\psi_{i}^{T}=\frac{1}{|T|}\cdot\left [v(T)-v(T\setminus\{i\})+\sum_{\{S:S\subseteq T,|S|=|T|-1,i\in S\}}\psi_{i}^{S}\right ]
\end{equation}
with the convention that \(\psi_{i}^{\emptyset}=0\) for all \(i\in N\).
\begin{equation}{\label{sprl1}}\tag{5}\mbox{}\end{equation}
Proposition \ref{sprl1}. For all \(T\subseteq N\), we have \(\boldsymbol{\psi}^{T}\equiv (\psi_{i}^{T})_{i\in T}=\boldsymbol{\phi}(v^{T})\). \(\sharp\)
Proposition \ref{sprl1} shows that the Shapley value \(\boldsymbol{\phi}(v)\) of \((N,v)\) can be computed according to the
recursive formula (\ref{spreqc}), since \(\boldsymbol{\phi}(v)=\boldsymbol{\psi}^{N}\). The cooperative game \((N,v)\) is {\bf quasiconvex} if and only if, for all \(S,T\subseteq N\), we have
\[\sum_{i\in S}\left [v(S)-v(S\setminus\{i\})\right ]\leq\sum_{i\in S}\left [v(T)-v(T\setminus\{i\})\right ]\]
whenever \(S\subseteq T\). The class of quasiconvex games includes, and is strictly larger than, the class of convex games (Sprumont \cite[p.387]{spr}).
Proposition. (Sprumont \cite[p.387]{spr}). If the cooperative game \((N,v)\) is quasiconvex, then its core contains its Shapley value. In other words, the Shapley value is in the core of every quasiconvex game.
Proof. By induction and using Proposition \ref{sprl1}. \(\blacksquare\)
