Solution Concepts In Transferable Utility Games

Jean-Leon Gerome (1824-1904) was a French painter.

The topics are

\begin{equation}{\label{a}}\tag{A}\mbox{}\end{equation}

The Cores.

Definition. For a cooperative game $(N,v)$, let $S$ be a coalition and let ${\bf x}$ be a payoff vector (not necessarily an imputation). The excess of $S$ with respect to ${\bf x}$ is given by
\begin{equation}{\label{ga24}}\tag{1}
e(S,{\bf x})=v(S)-\sum_{i\in S}x_{i}.
\end{equation}
For $i,j\in N$ with $i\neq j$, the surplus of $i$ againts $j$ is
\begin{equation}{\label{ga15}}\tag{2}
s_{ij}({\bf x})=\max_{\{S:i\in S,j\not\in S\}}e(S;{\bf x}). \sharp
\end{equation}

The quantity $s_{ij}$ represents the most that $i$ could hope to gain without the cooperation of $j$ (Owen \cite[p.319]{owe}).

The core of a game $(N,v)$ is defined by
\begin{align*}
{\cal C}(v) & =\left\{{\bf x}\in\mathbb{R}^{N}:\sum_{i\in N}x_{i}=v(N)
\mbox{ and }\sum_{i\in S}x_{i}\geq v(S)\mbox{ for all }S\subseteq N\right\}\\
& =\left\{{\bf x}\in\mathbb{R}^{N}:\sum_{i\in N}x_{i}=v(N)\mbox{ and }\sum_{i\in S}x_{i}\geq v(S)\mbox{ for all }
S\subset N\mbox{ and }S\neq N\right\}\label{tij04eq300}\tag{3}.
\end{align*}
The core ${\cal C}(v)$ is a closed convex set, since it is characterized by a set of inequalities. We also see that
\begin{align*}
{\cal C}(v) & =\left\{{\bf x}\in {\cal I}(v):e(S,{\bf x})\leq 0\mbox{ for all }S\subseteq N\right\}\\
& =\left\{{\bf x}\in {\cal I}^{*}(v):e(S,{\bf x})\leq 0\mbox{ for all }S\subseteq N\right\};
\end{align*}
that is, the core of the game $(N,v)$ is the set of all imputations (or pre-imputations) that give rise only to non-positive excesses.

The idea behind the definition of the core is that an imputation ${\bf x}$ is in ${\cal C}(v)$ if no matter which coalition $S$ is formed, the total payoff given to the members of $S$, i.e., $\sum_{i\in S}x_{i}$, must be at least as large as $v(S)$, the maximum possible benefit of forming coaliton. If $e(S,{\bf x})>0$, this says that the maximum possible benefits of joining the coalition $S$ are greater than the total allocation to the members of $S$ using the imputation ${\bf x}$. In this case, the members of $S$ will not be happy with ${\bf x}$, since the available amount is not actually allocated. Therefore, if ${\bf x}\in {\cal C}(v)$, then we must have $e(S,{\bf x})\leq 0$. In other words, the imputation ${\bf x}$ is acceptable to all coalitions. The excess $e(S,{\bf x})$ can be interpreted as a measure of the satisfaction of coalition $S$ if ${\bf x}$ were suggested as final payoff.

Some authors define the core as follows:
\[{\cal C}_{0}(v)=\left\{{\bf x}\in\mathbb{R}^{N}:\sum_{i\in N}x_{i}\leq v(N),
\sum_{i\in S}x_{i}\geq v(S)\mbox{ for all }S\subseteq N\right\}.\]
Since the inequalities $x_{i}\geq v(i)$ are included, the core ${\cal C}_{0}(v)$ is bounded. Thus, ${\cal C}_{0}(v)$ is a compact convex polyhedron, possibly empty, of dimension at most $n-1$ (Shapley \cite[p.16]{sha71}).

\begin{equation}{\label{ga39}}\tag{4}\mbox{}\end{equation}

Example \ref{ga39}. Consider a three-person game with characteristic function given by
\begin{align*}
v(1)=1,\quad v(2)=2,\quad v(3)=3,\quad v(12)=4,\quad v(13)=5,\quad v(23)=6\mbox{ and }v(N)=8
\end{align*}
The excess function for ${\bf x}=(x_{1},x_{2},x_{3})\in {\cal C}(v)$ must satisfy
\begin{align*}
& e(1,{\bf x})=1-x_{1}\leq 0,\quad e(2,{\bf x})=2-x_{2}\leq 0,\quad e(3,{\bf x})=3-x_{3}\leq 0\\
& e(12,{\bf x})=4-x_{1}-x_{2}\leq 0,\quad e(13,{\bf x})=5-x_{1}-x_{3}\leq 0,\quad e(23,{\bf x})=6-x_{2}-x_{3}\leq 0.
\end{align*}
we must have
\[x_{1}+x_{2}+x_{3}=8.\]
These inequalities imply
\begin{align*}
& x_{1}\geq 1,\quad x_{2}\geq 2,\quad x_{3}\geq 3\\
& x_{1}+x_{2}\geq 4,\quad x_{1}+x_{3}\geq 5,\quad x_{2}+x_{3}\geq 6.
\end{align*}
After some algebraic calculations, we obtain
\[{\cal C}(v)=\left\{(x_{1},x_{2},8-x_{1}-x_{2}):1\leq x_{1}\leq 2,2\leq x_{2}\leq 3,4\leq x_{1}+x_{2}\leq 5\right\}. \sharp\]

Theorem (Bondareva-Shapley Theorem). Let $(N,v)$ be a cooperative game. Then ${\cal C}(v)\neq\emptyset$ if and only if $(N,v)$ is a balanced game.

Proof. Recall that ${\cal P}(N)$ denotes the collection of all nonempty subsets of $N$. We consider the following linear primal programming problem (P)
\[\begin{array}{lll}
\mbox{(P)} & \min & {\displaystyle \sum_{i\in N}x_{i}}\\
& \mbox{subject to} & {\displaystyle \sum_{i\in S}x_{i}\geq v(S)\mbox{ for all }S\in{\cal P}(N)}\\
&& x_{i}\in\mathbb{R}\mbox{ (unrestricted) for }i\in N.
\end{array}\]
Let $\gamma$ be a balanced map defined on ${\cal P}(N)$. We write $\gamma(S)=\gamma_{S}\in\mathbb{R}_{+}$. Then, the dual problem of (P) is given by
\[\begin{array}{lll}
\mbox{(D)} & \max & {\displaystyle \sum_{S\in{\cal P}(N)}\gamma_{S}\cdot v(S)}\\
& \mbox{subject to} & {\displaystyle \sum_{S\in{\cal P}(N)}\gamma_{S}{\bf 1}_{S}={\bf 1}_{N}}\\
&& \gamma_{S}\geq 0\mbox{ for all }S\in{\cal P}(N).
\end{array}\]
Suppose that ${\cal C}(v)\neq\emptyset$. For ${\bf x}^{*}\in {\cal C}(v)$, it means
\[\sum_{i\in N}x_{i}^{*}=v(N)\mbox{ and }\sum_{i\in S}x_{i}^{*}\geq v(S)\mbox{ for all }S\in {\cal P}(N),\]
which says that ${\bf x}^{*}$ is an optimal solution of primal problem (P) with optimal objective value $v(N)$. Conversely, let ${\bf x}^{\circ}$ be an optimal solution of problem (P) with optimal objective value $v(N)$, i.e.,
\[\sum_{i\in N}x_{i}^{\circ}=v(N).\]
Using the feasibility of ${\bf x}^{\circ}$, we also have
\begin{equation}{\label{ga47}}\tag{5}
\sum_{i\in S}x_{i}^{\circ}\geq v(S)\mbox{ for all }S\in {\cal P}(N),
\end{equation}
which shows that ${\bf x}^{\circ}\in {\cal C}(v)$. Therefore, we conclude that ${\cal C}(v)\neq\emptyset$ if and only if $v(N)$ is the optimal objective value of primal problem (P).

Let $\mbox{Obj}_{D}$ denote the optimal objective value of the dual problem (D). Suppose that $(N,v)$ is a balanced game. Then, by definition,
\begin{equation}{\label{ga48}}\tag{6}
v(N)\geq\sum_{S\in{\cal P}(N)}\gamma_{S}\cdot v(S)
\end{equation}
for each balanced map $\gamma$ defined on ${\cal P}(N)$, which says that $\mbox{Obj}_{D}\leq v(N)$. We take $\bar{\gamma}(N)=1$ and $\bar{\gamma}(S)=0$ for $N\neq S\in {\cal P}(N)$. Then $\bar{\gamma}$ is a balanced map such that, for any $S\in {\cal P}(N)$, $\bar{\gamma}_{S}\equiv\bar{\gamma}(S)$ forms a feasible solution of dual problem (D) with objective value $v(N)$. Using the maximality regrading the objective value, it follows $v(N)\leq\mbox{Obj}_{D}$, which implies $v(N)=\mbox{Obj}_{D}$. Conversely, suppose that $v(N)=\mbox{Obj}_{D}$. Then (\ref{ga48}) is satisfied for each balanced map $\gamma$, which also says that $(N,v)$ is a balanced game. Therefore we conclude that $(N,v)$ is a balanced game if and only if $v(N)$ is the optimal objective value of dual problem
(D). Finally, using the strong duality theorem for linear programming problem. This completes the proof. $\blacksquare$

Definition. Let $(N,v)$ be a cooperative game. The reasonable allocation set of $(N,v)$ is a set of imputations defined by
\[{\cal R}(v)=\left\{{\bf x}\in {\cal I}(v):x_{i}\leq\max_{T\in {\cal S}^{(i)}}\left [v(T)-v(T\setminus\{i\})\right ]\right\},\]
where ${\cal S}^{(i)}$ denotes the set of all coalitions containing player $i$ as a member. $\sharp$

The reasonable allocation set is the set of imputations so that the amount allocated to each player is no greater than the maximum benefit that the player brings to any coalition of which the player is a member. The difference $v(T)-v(T\setminus\{i\})$ is the measure of the rewards for coalition $T$ due to player $i$.

Proposition. Let $(N,v)$ be a cooperative game. Then ${\cal C}(v)\subset {\cal R}(v)$.

Proof. Suppose that ${\bf x}\not\in {\cal R}(v)$. Then, there exists a player $j$ satisfying
\[x_{j}>\max_{T\in {\cal S}^{(j)}}\left [v(T)-v(T\setminus\{j\})\right ].\]
Taking $T=N$, we must have
\[x_{j}>v(N)-v(N\setminus\{j\})=\sum_{i\in N}x_{i}-v(N\setminus\{j\}),\]
which implies
\[v(N\setminus\{j\})>\sum_{i\in N}x_{i}-x_{j}=\sum_{i\in N\setminus\{j\}}x_{i}.\]
Therefore, we obtain
\[e(N\setminus\{j\},{\bf x})=v(N\setminus\{j\})-\sum_{i\in N\setminus\{j\}}x_{i}>0,\]
which says that ${\bf x}\not\in {\cal C}(v)$. This completes the proof. $\blacksquare$

\begin{equation}{\label{ga42}}\tag{7}\mbox{}\end{equation}

Example \ref{ga42}. We consider a three-person cooperative game with characteristic function given by
\[v(i)=0,\quad v(123)=1,\quad v(12)=\frac{7}{15},\quad v(13)=\frac{4}{15},\quad v(23)=\frac{7}{15}.\]
Then, we have
\begin{align*}
& {\cal I}(v)=\left\{{\bf x}=\left (x_{1},x_{2},x_{3}\right )\in\mathbb{R}^{3}_{+}:x_{1}+x_{2}+x_{3}=1\right\}\\
& {\cal C}(v)={\cal R}(v)=\left\{\left (x_{1},x_{2},1-x_{1}-x_{2}\right ):0\leq x_{1}\leq\frac{8}{15},
0\leq x_{2}\leq\frac{11}{15},\frac{7}{15}\leq x_{1}+x_{2}\leq 1\right\}. \sharp
\end{align*}

We are going to present an example with empty core.

Example. We consider a three-person cooperative game with characteristic function given by
\[v(1)=v(2)=v(3)=0\mbox{ and }v(123)=1=v(12)=v(13)=v(23)1.\]
Then, we have
\[{\cal I}(v)=\left\{{\bf x}=\left (x_{1},x_{2},x_{3}\right )\in\mathbb{R}^{3}_{+}:x_{1}+x_{2}+x_{3}=1\right\}={\cal R}(v).\]
If ${\bf x}\in {\cal C}(v)$, we calculate
\begin{align*}
& e(i,{\bf x})=v(i)-x_{i}=-x_{i}\leq 0\mbox{ for }i=1,2,3\\
& e(12,{\bf x})=1-(x_{1}+x_{2})\leq 0\\
& e(13,{\bf x})=1-(x_{1}+x_{3})\leq 0\\
& e(23,{\bf x})=1-(x_{2}+x_{3})\leq 0.
\end{align*}
Then, we have
\[{\cal C}(v)=\left\{\left (x_{1},x_{2},x_{3}\right )\in\mathbb{R}^{3}_{+}:
x_{1}+x_{2}\geq 1,x_{1}+x_{3}\geq 1,x_{2}+x_{3}\geq 1,x_{1}+x_{2}+x_{3}=1.\right\}=\emptyset. \sharp\]

\begin{equation}{\label{ga45}}\tag{8}\mbox{}\end{equation}

Proposition \ref{ga45}. Given a game $(N,v)$, let $\delta_{i}=v(N)-v(N\setminus\{i\})$. If $\delta_{1}+\delta_{2}+\cdots +\delta_{n}<v(N)$, then ${\cal C}(v)=\emptyset$. $\sharp$

Proposition. Given a game $(N,v)$, ${\cal C}(v)\neq\emptyset$ if and only if
\[\begin{array}{ll}
\min & z=x_{1}+x_{2}+\cdots +x_{n}\\
\mbox{subject to} & {\displaystyle v(S)\leq\sum_{i\in S}x_{i}\mbox{ for every }S\subset N
\mbox{ with }S\neq N}
\end{array}\]
has a finite minimum $z^{*}$ with $z^{*}\leq v(N)$. $\sharp$

Suppose the players in the cooperative game $(N,v)$ have come to an agreement on distribution of a payoff to the whole coalition $N$, the imputation ${\bf x}^{*}$, under which none of the imputation dominates ${\bf x}^{*}$. Then such a distribution is stable in that it is disadvantageous for any coalition $S$ to separate from other players and distribute a payoff $v(S)$ among its members. This suggest that it may be wise to examine the set of nondominant imputations. We recall that the imputation ${\bf x}$ is said to dominate imputation ${\bf y}$, denoted by ${\bf x}\succ {\bf y}$, if and only if there is a coalition $S$ for which ${\bf x}\succ_{S}{\bf y}$ given in (\ref{ga43}). The set of nondominant imputations in the cooperative game $(N,v)$ is called its dominance core and is denoted by ${\cal DC}(v)$.

Definition. A stable set ${\cal S}(v)$ of a game $(N,v)$ is a nonempty set $K$ of imputations satisfying the following properties.

(Internal Stability). Given any ${\bf x},{\bf y}\in K$, ${\bf x}$ does not dominate ${\bf y}$ and ${\bf y}$ does not dominate ${\bf x}$.
(External Stability) Given any imputation ${\bf z}\not\in K$, there is an imputation ${\bf x}\in K$ such that ${\bf x}$ dominates ${\bf z}$. $\sharp$

The dominance core ${\cal DC}(v)$ always satisfies the internal stability. Therefore, if ${\cal DC}(v)\neq\emptyset$ and at least one stable set exists, then ${\cal DC}(v)$ is included in all stable sets. When the dominance core also satisfies the external stability (i.e., it is a stable set,) it is called the stable core. In this case, the stable core is the unique stable set. The stable core has a very strong stability since it is not dominated by any imputation, and every imputation outside it, is dominated by some imputation belonging to it.
(Tijs et al. \cite[p.287]{tij04} and Muto et al. \cite[p.304]{mut88}).

\begin{equation}{\label{ga44}}\tag{9}\mbox{}\end{equation}

Proposition \ref{ga44}. (Tijs et al. \cite[p.289]{tij04}). Given a game $(N,v)$, we have ${\cal C}(v)\subseteq{\cal DC}(v)$, and, for each stable set ${\cal S}(v)$, we have ${\cal DC}(v)\subseteq {\cal S}(v)$.

Proof. The inclusions are obvious if ${\cal I}(v)=\emptyset$. Therefore, we assume ${\cal I}(v)\neq\emptyset$. For ${\bf x}\in{\cal I}(v)\setminus {\cal DC}(v)$, there exists ${\bf y}\in{\cal I}(v)$ dominating ${\bf x}$, i.e., there exists a coslition $S$ satisfying $y_{i}>x_{i}$ for each $i\in S$ and $\sum_{i\in S}y_{i}\leq v(S)$. Therefore, we obtain
\[\sum_{i\in S}x_{i}<\sum_{i\in S}y_{i}\leq v(S),\]
which says that ${\bf x}\in{\cal I}(v)\setminus {\cal C}(v)$. Therefore, we conclude that ${\cal C}(v)\subseteq {\cal DC}(v)$. Since ${\cal DC}(v)$ consists of nondominated imputation and each imputation in ${\cal I}(v)\setminus{\cal S}(v)$ is dominated by some imputation by the external stability property of ${\cal S}(v)$, it follows that ${\cal DC}(v)\subseteq {\cal S}(v)$. This completes the proof. $\blacksquare$

\begin{equation}{\label{ga156}}\tag{10}\mbox{}\end{equation}

Proposition \ref{ga156} (Tijs et al. \cite[p.289]{tij04}). Given a game $(N,v)$, if
\begin{equation}{\label{ga153}}\tag{11}
v(N)\geq v(S)+\sum_{i\in N\setminus S}v(i)
\end{equation}
for each $S\subset N$ with $S\neq N$ and $S\neq\{i\}$ for $i=1,\cdots ,n$, then we have ${\cal C}(v)={\cal DC}(v)$.

Proof. If ${\cal I}(v)=\emptyset$, then ${\cal C}(v)={\cal DC}(v)=\emptyset$. Therefore, we assume ${\cal I}(v)\neq\emptyset$. Proposition \ref{ga44} says that ${\cal C}(v)\subseteq{\cal DC}(v)$. Therefore, we remain to show that if ${\bf x}\in{\cal I}(v) \setminus {\cal C}(v)$, then ${\bf x}\in{\cal I}(v)\setminus {\cal DC}(v)$. In this case, there exists a coalition $S\neq N$ satisfying $\sum_{i\in S}x_{i}<v(S)$. Therefore, there exists $\epsilon_{i}>0$ for $i\in S$ satisfying
\begin{equation}{\label{ga152}}\tag{12}
\sum_{i\in S}(x_{i}+\epsilon_{i})=v(S)
\end{equation}
We are going to find an imputation ${\bf y}\in\mathbb{R}^{N}$ such that ${\bf y}$ dominates ${\bf x}$ via $S$. Since $S\neq N$, for $i\in N$, we define
\[y_{i}=\left\{\begin{array}{ll}
x_{i}+\epsilon_{i}, & \mbox{if $i\in S$}\\
{\displaystyle v(i)+\frac{1}{|N\setminus S|}\left (v(N)-\sum_{i\in N\setminus S}v(i)-v(S)\right )}, & \mbox{if $i\not\in S$}.
\end{array}\right .\]
Then, we have $\sum_{i\in N}y_{i}=v(N)$ and, by (\ref{ga152}),
\[\sum_{i\in S}y_{i}=\sum_{i\in S}(x_{i}+\epsilon_{i})=v(S).\]
Since ${\bf x}\in {\cal I}(v)$, for each $i\in S$, we have $y_{i}>x_{i}\geq v(i)$. For $i\not\in S$, from (\ref{ga153}), we also see that
\[y_{i}=v(i)+\frac{1}{|N\setminus S|}\left (v(N)-\sum_{i\in N\setminus S}v(i)-v(S)\right )\geq v(i).\]
Therefore, we conclude that ${\bf y}\in {\cal I}(v)$ and ${\bf y}$ dominates ${\bf x}$ via $S$. This also says ${\bf x}\in {\cal I}(v) \setminus {\cal DC}(v)$, and the proof is complete. $\blacksquare$

Remark. According (\ref{ga155}), we see that if the game $(N,v)$ is supera-dditive, then (\ref{ga153}) is satisfied automatically. Indeed, we have
\[v(N)\geq v(S)+v(N\setminus S)\geq v(S)+\sum_{i\in N\setminus S}v(i). \sharp\]

Under the pre-imputation $I^{*}(v)$, we can similarly define the pre-core $C^{*}(v)$ and dominance pre-core $DC^{*}(v)$.

Proposition. We have ${\cal DC}^{*}(v)\subseteq {\cal C}^{*}(v)$.

Proof. Proposition \ref{ga44} says that ${\cal C}^{*}(v)\subseteq{\cal DC}^{*}(v)$. Therefore, we remain to show that if ${\bf x}\in{\cal I}^{*}(v)\setminus {\cal C}^{*}(v)$, then ${\bf x}\in{\cal I}^{*}(v)\setminus {\cal DC}^{*}(v)$. In this case, there exists a coalition $S$ satisfying $\sum_{i\in S}x_{i}<v(S)$. We define
\[y_{i}=\left\{\begin{array}{ll}
{\displaystyle x_{i}+\frac{v(S)-\sum_{i\in S}x_{i}}{|S|}}, & \mbox{if $i\in S$}\\
{\displaystyle \frac{v(N)-v(S)}{|N\setminus S|}}, & \mbox{if $i\in N\setminus S$}.
\end{array}\right .\]
It is obvious that $y_{i}>x_{i}$ for $i\in S$ and
\[\sum_{i\in S}y_{i}=v(S)\mbox{ and }\sum_{i\in N}y_{i}=v(N).\]
${\bf y}\succ_{S}{\bf x}$. Then it follows that ${\bf x}$ does not belong to the dominance pre-core. $\blacksquare$

We present some other proofs of Proposition \ref{ga156}.

\begin{equation}{\label{pert3121}}\tag{13}\mbox{}\end{equation}

Proposition \ref{pert3121}. (Petrosjan and Zenkevich \cite[p.174]{pet} and Owen \cite[p.219]{owe}). If the game $(N,v)$ is super-additive, then ${\cal DC}(v)={\cal C}(v)$.

Proof. The result is straightforward for inessential games, and, by Proposition \ref{ga40}, it suffices to prove it for the games in $(0,1)$-reduced form. Suppose that the following condition
\begin{equation}{\label{pereq3121}}\tag{14}
v(S)\leq\sum_{i\in S}x_{i}
\end{equation}
holds for the imputation ${\bf x}$. We are going to show that ${\bf x}$ is in the dominance core. Suppose that it is not so. Then there is an imputation ${\bf y}$ such that ${\bf y}\succ_{S}{\bf x}$, i.e., $v(S)\geq\sum_{i\in S}y_{i}>\sum_{i\in S}x_{i}$ which contradicts (\ref{pereq3121}). Conversely, for any imputation ${\bf x}$, which does not satisfy (\ref{pereq3121}), there exists a coalition $S$ for which $\sum_{i\in S}x_{i}<v(S)$. Let
\[y_{i}=\left\{\begin{array}{ll}
{\displaystyle x_{i}+\frac{v(S)-\sum_{i\in S}x_{i}}{|S|}} & \mbox{if $i\in S$}\\
{\displaystyle \frac{1-v(S)}{|N|-|S|}} & \mbox{if $i\not\in S$}.
\end{array}\right .\]
It can be easily seen that $\sum_{i\in N}y_{i}=1$, $y_{i}\geq 0$ and ${\bf y}\succ_{S}{\bf x}$. Then it follows that ${\bf x}$ does not belong to the dominance core. $\blacksquare$

\begin{equation}{\label{ga46}}\tag{15}\mbox{}\end{equation}

Example \ref{ga46}. Suppose that there are $150$ sinks to give away to whomever shows up to take them away. Players A, B and C simultaneously show up with their trucks to take as many of the sinks as their trucks can haul. Players A, B and C can haul $45$, $60$ and $75$, respectively, which are totally more than $150$. The wrinkle in this problem is that the sinks are too heavy for any one person to load onto the trucks so they must cooperate in loading the sinks. We define the characteristic function $v(S)$ as the number of sinks that can be loaded by the coalition $S$. Since they must cooperate to receive the sinks, it means that $v(i)=0$ for $i=1,2,3$. We also have $v(\{1,2\})=105$, $v(\{1,3\})=120$, $v(\{2,3\})=135$ and $v(\{1,2,3\})=150$. The set of imputation is
\[{\cal I}(v)=\left\{(x_{1},x_{2},x_{3})\in\mathbb{R}_{+}^{3}:x_{1}+x_{2}+x_{3}=150\right\}.\]
The core is given by
\[{\cal C}(v)=\left\{(x_{1},x_{2},x_{3})\in\mathbb{R}_{+}^{3}:x_{1}+x_{2}+x_{3}=150,
x_{1}+x_{2}\geq 105, x_{2}+x_{3}\geq 135, x_{1}+x_{3}\geq 120\right\}.\]
Since $2(x_{1}+x_{2}+x_{3})=300\geq 360$ which is impossible, it follows that ${\cal C}(v)=\emptyset$. We can also apply Proposition \ref{ga45} to obtain ${\cal C}(v)=\emptyset$ as follows. We calculate $\delta_{1}=15$, $\delta_{2}=30$ and $\delta_{3}=45$, which implies $\delta_{1}+\delta_{2}+\delta_{3}=90<150$. Therefore, we have ${\cal C}(v)=\emptyset$. Since ${\cal C}(v)=\emptyset$, we know that no matter what allocation ${\bf x}$ we use, there will be some coalition $S$ and some allocation ${\bf y}$ satisfying ${\bf y}\succ_{S}{\bf x}$. For example, if ${\bf x}=(45,50,55)$, then we can take $S=\{2,3\}$ and ${\bf y}=(43,51,56)$. $\sharp$

Proposition (Petrosjan and Zenkevich \cite[p.175]{pet}). If the game $(N,v)$ is super-additive, then the core ${\cal C}(v)$ is a closed and convex subset of ${\cal I}(v)$. $\sharp$

Proposition (Petrosjan and Zenkevich \cite[p.175]{pet}). If the game $(N,v)$ is superadditive, then, for any ${\bf x}\in {\cal I}(v)$, ${\bf x}\in {\cal DC}(v)$ if and only if the inequality
\begin{equation}{\label{pereq3122}}\tag{16}
\sum_{i\in S}x_{i}\leq v(N)-v(N\setminus S)
\end{equation}
holds for all coalitions $S\subseteq N$.

Proof. Since $\sum_{i\in N}x_{i}=v(N)$, inequality (\ref{pereq3122}) can be rewritten as $v(N\setminus S)\leq\sum_{i\in N\setminus S}x_{i}$. Then the result follows from (\ref{pereq3121}). $\blacksquare$

Proposition (Curiel \cite[p.6]{cur} and Maschler et al. \cite[p.323]{mas79}). A game $(N,v)$ has a nonempty core if and only if it is balanced. $\sharp$

\begin{equation}{\label{tij04p1}}\tag{17}\mbox{}\end{equation}

Proposition \ref{tij04p1}. (Tijs et al. \cite[p.287]{tij04}). Given a game $(N,v)$, we have the following properties.

(i) We have ${\cal C}(v)\subseteq {\cal DC}(v)$ and both ${\cal C}(v)$ and ${\cal DC}(v)$ are convex sets. If ${\cal DC}(v)=\emptyset$, then ${\cal C}(v)={\cal DC}(v)=\emptyset$.

(ii) Each stable set contains ${\cal DC}(v)$.

(iii) If the game $(N,v)$ is convex, there is only one stable set that coincides with ${\cal DC}(v)$.

(iv) If ${\cal C}(v)\neq {\cal DC}(v)$ then ${\cal C}(v)=\emptyset$. Equivalently, if ${\cal C}(v)\neq\emptyset$ then ${\cal C}(v)={\cal DC}(v)$. $\sharp$

Let us recall the concept of cover $\widehat{v}$ in Definition \ref{gad13}.

Proposition (Maschler et al. \cite[p.323]{mas79}). Let $(N,v)$ be a balanced game, and let $(N,\bar{v})$ satisfy $v(S)\leq\bar{v}(S)\leq\widehat{v}(S)$ for all $S\subseteq N$. Then

\[{\cal I}(v)={\cal I}(\bar{v})={\cal I}(\widehat{v})\mbox{ and }{\cal C}(v)={\cal C}(\bar{v})={\cal C}(\widehat{v}). \sharp\]

It is apparent that the core is relative invariant under the strategic equivalence; that is, if $a$ is an additive set function, then the core
of $(N,v+a)$ is obtained from the core of $(N,v)$ by the transformation $x_{i}\rightarrow x_{i}+a(i)$ for all $i\in N$. We also have invariance under multiplication of $v$ by a positive constant. When relation among such invariant concept is discussed, there will be no loss of generality in assuming that the underlying game $(N,v)$ is zero-normalized, i.e., $v(i)=0$ for all $i\in N$. We shall assume this whenever convenient. A cooperative game $(N,v)$ is called zero-monotonic if and only if the unique zero-normalized game that is strategically equivalent to $(N,v)$ is monotonic. Note that every superadditive game is zero-monotonic (Maschler et al. \cite[p.309]{mas79}).

We denote by $\mbox{Dom}(L)$ the set of imputations which are dominated by at least one imputation in $L$.

\begin{equation}{\label{gad15}}\tag{18}\mbox{}\end{equation}

Definition \ref{gad15}. A subsolution of a cooperative game $(N,v)$ is a nonempty set $L$ of imputations satisfying the following conditions:

(a) for all ${\bf x},{\bf y}\in L$, ${\bf x}$ does not dominate ${\bf y}$ and ${\bf y}$ does not dominate ${\bf y}$;

(b) if ${\bf x}\in L$ and ${\bf y}$ dominates ${\bf x}$, then there exists a ${\bf z}\in L$ such that ${\bf z}$ dominates ${\bf y}$;

(c) if ${\bf x}\not\in L\cup\mbox{Dom}(L)$, then there is an imputation ${\bf y}\not\in L\cup\mbox{Dom}(L)$ such that ${\bf y}$ dominates ${\bf x}$. $\sharp$

It is known that if the dominance core ${\cal DC}(v)\neq\emptyset$, then a subsolution exists, and further that the intersection of all subsolutions is also a subsolution; the intersection is called the super core. The dominance core always satisfies conditions (a) and (b). When the dominance core also satisfies condition (c), it is the super core. If the dominance core is a super core, it has a strong stability than the usual dominance core in the sense that all imputations outside the dominance core and further not dominated by the dominance core must be dominated by some imputation having the same property. Hence, in the region ${\cal I}(v)\setminus ({\cal DC}(v)\cup\mbox{dom}({\cal DC}(v)))$, there is no stable subset of imputations (Muto et al. \cite[p.305]{mut88}).

Least Cores.

Let $\epsilon$ be a real number. The strong $\epsilon$-core of the cooperative game $(N,v)$, denoted by ${\cal C}^{*}_{\epsilon}(v)$, is defined by
\[{\cal C}^{*}_{\epsilon}(v)=\left\{{\bf x}\in {\cal I}^{*}(v):e(S,{\bf x})
\leq\epsilon\mbox{ for all }S\subset N\mbox{ with }S\neq N\mbox{ and }S\neq\emptyset\right\}.\]
Then, we have the following observations.

It is clear to see ${\cal C}^{*}_{0}(v)={\cal C}^{*}(v)$.
If $\epsilon_{1}>\epsilon_{2}$, then ${\cal C}^{*}_{\epsilon_{1}}(v)\supseteq {\cal C}^{*}_{\epsilon_{2}}(v)$. The strict inclusion holds if ${\cal C}^{*}_{\epsilon_{1}}(v)\neq\emptyset$.
We see that ${\cal C}^{*}_{\epsilon}(v)\neq\emptyset$ if $\epsilon$ is large enough.

The least-core of the cooperative game $(N,v)$, denoted by ${\cal LC}^{*}(v)$, is the intersection of all nonempty strong $\epsilon$-cores. Equivalently, let $\epsilon_{0}(v)$ be the smallest $\epsilon$ satisfying ${\cal C}^{*}_{\epsilon}(v)\neq\emptyset$, i.e.,
\[\epsilon_{0}(v)=\min_{{\bf x}\in {\cal I}^{*}(v)}\max_{S\neq N,\emptyset}e(S,{\bf x});\]
this critical value may be negative. Then ${\cal LC}^{*}(v)={\cal C}^{*}_{\epsilon_{0}(v)}(v)$. In other words, the least-core is the set of all pre-imputation that minimizes the maximum excess (Maschler et al. \cite[p.306]{mas79}).

The strong $\epsilon$-cores, including the least-core and the core itself, are compact convex polyhedral bounded by no more than $2^{n}-2$ hyperplanes of the form
\[H_{S}^{\epsilon}=\left\{{\bf x}\in {\cal I}^{*}(v):\sum_{i\in S}x_{i}=v(S)-\epsilon\right\}\]
for $S\neq N,\emptyset$. We shall write $H_{S}$ for $H_{S}^{0}$. Except for the least-core, all nonempty strong $\epsilon$-cores have dimension $n-1$, i.e., the dimension of ${\cal I}^{*}(v)$. The dimension of ${\cal LC}^{*}(v)$ is always $n-2$ or less (Maschler et al. \cite[p.306-307]{mas79}).

Proposition (Maschler et al. \cite[p.309]{mas79}). If the cooperative game $(N,v)$ is zero-monotonic, then ${\cal LC}^{*}(v)\subseteq {\cal I}(v)$. $\sharp$

For $\epsilon\in\mathbb{R}$, the $\epsilon$-core of the cooperative game $(N,v)$ is defined by
\[{\cal C}_{\epsilon}(v)=\left\{{\bf x}\in {\cal I}(v):e(S,{\bf x})\leq\epsilon\mbox{ for all }S\subset N\mbox{ with }S\neq N
\mbox{ and }S\neq\emptyset\right\}.\]

Let $\epsilon^{*}\in\mathbb{R}$ be the first $\epsilon$ for which ${\cal C}_{\epsilon}(v)\neq\emptyset$. Then ${\cal C}_{\epsilon^{*}}(v)$ is called the least core of $(N,v)$. It is possible for $\epsilon^{*}$ to be positive, negative or zero.

For any ${\bf x}\in {\cal I}(v)$, we must have $v(N)=\sum_{i\in N}x_{i}$, which also says that $e(N,{\bf x})=0$. This will force $\epsilon$ to be nonnegative, which is too strict a requirement on $\epsilon$ in order for ${\cal C}_{\epsilon}(v)$ to be nonempty. Therefore, we exclude the grand coalition $N$ in the definition of least core. Since $e(\emptyset ,{\bf x})=0$, we also exclude $S=\emptyset$. Recall that the excess $e(S,{\bf x})$ can be interpreted as a measure of the satisfaction of coalition $S$ if ${\bf x}$ were suggested as final payoff. If ${\bf x}\in {\cal C}_{\epsilon}(v)$, then the measure of satisfaction of a allocation ${\bf x}$ is limited to $\epsilon$. Since $e(S,{\bf x})\leq\epsilon$, the size of $\epsilon$ determines the measure of satisfaction.

Example. Continued from Example \ref{ga39}, we shall show that $\epsilon^{*}=-1/3$. Since $e(S,{\bf x})\leq\epsilon$ for all $S\neq N$, we have the following inequalities
\[1-\epsilon\leq x_{1}\leq 2+\epsilon,\quad 2-\epsilon\leq x_{2}\leq 3+\epsilon ,\quad
4-\epsilon\leq x_{1}+x_{2}\leq 5+\epsilon ,\]
Adding , we the inequalities involving pnly $x_{1}$ and $x_{2}$, we obtain $4-\epsilon\leq x_{1}+x_{2}\leq 5+2\epsilon$, which implies that $\epsilon\geq -1/3$. We can check that $\epsilon^{*}=-1/3$. For $\epsilon\geq -1/3$,it follows that
\[x_{1}+x_{2}=\frac{13}{3}, \quad x_{1}\leq\frac{5}{3}\mbox{ and }x_{2}\leq\frac{8}{3},\]
which implies that $x_{1}=5/3$ and $x_{2}=8/3$. Therefore, the least core is given by
\[{\cal C}_{\epsilon^{*}}(v)=\left\{\left (\frac{5}{3},\frac{8}{3},\frac{11}{3}\right )\right\}. \sharp\]

Example. Continued from Example \ref{ga42}, we have
\begin{align*}
{\cal C}_{\epsilon}(v)
& =\left\{\left (x_{1},x_{2},1-x_{1}-x_{2}\right )\in\mathbb{R}_{+}^{3}:
\frac{7}{15}\leq x_{1}+x_{2}+\epsilon ,x_{2}\leq\frac{11}{15}+\epsilon ,\right .\\
& \quad\left .x_{1}\leq\frac{8}{15}+\epsilon ,-x_{1}\leq\epsilon ,-x_{2}\leq\epsilon ,x_{1}+x_{2}\leq 1+\epsilon\right\}.
\end{align*}
By adding the inequality for $x_{2}$ with the one for $x_{1}$ and then use the first inequality, we obtain
\[-\frac{11}{15}+x_{2}-\frac{8}{15}+x_{1}=-\frac{19}{15}+x_{1}+x_{2}\leq 2\epsilon.\]
Since $x_{1}+x_{2}+\epsilon\geq 7/15$, we also have
\[-\frac{12}{15}-\epsilon =-\frac{19}{15}+\frac{7}{15}-\epsilon\leq-\frac{19}{15}+x_{1}+x_{2}\leq 2\epsilon,\]
which can be satisfied if and only if
\[\epsilon\geq -\frac{4}{15}=\epsilon^{*}.\]
In this case, the least core is given by
\[{\cal C}_{\epsilon^{*}}(v)=\left\{\left (x_{1},x_{2},1-x_{1}-x_{2}\right ):
0\leq x_{1}\leq\frac{4}{15},0\leq x_{2}\leq\frac{7}{15},x_{1}+x_{2}=\frac{11}{15}\right\}
=\left\{\left (\frac{4}{15},\frac{7}{15},\frac{4}{15}\right )\right\}. \sharp\]

Example. Continued from Example \ref{ga46}, we see that ${\cal C}(v)=\emptyset$. Therefore, we want to find ${\cal C}_{\epsilon^{*}}(v)$. Now, we have
\begin{align*}
{\cal C}_{\epsilon}(v) & =\left\{{\bf x}\in {\cal I}(v):v(S)-\sum_{i\in S}x_{i}\leq\epsilon\mbox{ for }S\neq N\right\}\\
& =\left\{{\bf x}\in {\cal I}(v):105\leq x_{1}+x_{2}+\epsilon ,120\leq x_{1}+x_{3}+\epsilon ,
135\leq x_{2}+x_{3}+\epsilon ,-x_{i}\leq\epsilon\mbox{ for }i=1,2,3\right\}.
\end{align*}
Since $x_{1}+x_{2}+x_{3}=150$, by replacing $x_{3}=150-x_{1}-x_{2}$, we obtain
\[120\leq 150-x_{2}+\epsilon,\quad 135\leq 150-x_{1}+\epsilon\mbox{ and }105\leq x_{1}+x_{2}+\epsilon ,\]
which implies
\[45\geq x_{1}+x_{2}-2\epsilon\geq 105-3\epsilon .\]
Therefore, we must have $\epsilon\geq 20$, which also says that $\epsilon^{*}=20$ and the least core
\[{\cal C}_{\epsilon^{*}}(v)=\left\{(x_{1},x_{2},x_{3})=(35,50,65)\right\}.\]
We see that each player in this fair allocation ${\cal C}_{\epsilon^{*}}(v)$ gets $10$ less than the capacity of his truck. It seems that this is a reasonable way to allocate the sinks, since there is an under-supply of $30$ sinks so that each player will receive $30/3=10$ less than his truck can haul. $\sharp$

Proposition. Given a cooperative game $(N,v)$, let
\[\epsilon_{0}=\min_{{\bf x}\in {\cal I}(v)}\max_{S\subsetneqq N}e(S,{\bf x}).\]
If $\epsilon <\epsilon_{0}$, then ${\cal C}_{\epsilon}(v)=\emptyset$. If $\epsilon >\epsilon_{0}$, then ${\cal C}_{\epsilon_{0}}(v)\subsetneqq {\cal C}_{\epsilon}(v)$. In other words, ${\cal C}_{\epsilon_{0}}(v)$ is the least core, i.e., $\epsilon^{*}=\epsilon_{0}$.

Proof. Since the imputation is compact (closed and bounded) and the function
\[{\bf x}\mapsto\max_{S\subsetneqq N}e(S,{\bf x})\]
is lower semicontinuous, the minimum is attained; that is, there exists ${\bf x}_{0}$ such that
\[\epsilon_{0}=\max_{S\subsetneqq N}e(S,{\bf x}_{0})\geq e(S,{\bf x})\mbox{ for all }S\subsetneqq N,\]
which says that ${\bf x}_{0}\in {\cal C}_{\epsilon_{0}}(v)$, i.e., ${\cal C}_{\epsilon_{0}}(v)\neq\emptyset$. Now, if
\[\epsilon <\epsilon_{0}=\min_{{\bf x}\in {\cal I}(v)}\max_{S\subsetneqq N}e(S,{\bf x}),\]
then, for any ${\bf x}\in {\cal I}(v)$, we have $\epsilon <\max_{S\subsetneqq N}e(S,{\bf x})$, which says that there exists a coalition $S_{0}\subsetneqq N$ satisfying $\epsilon <e(S_{0},{\bf x})$. This shows that ${\cal C}_{\epsilon}(v)=\emptyset$. Therefore, we conclude that the least core is ${\cal C}_{\epsilon_{0}}(v)$. This completes the proof. $\blacksquare$

The calculation of the least core is equivalent to the following linear programming problem:
\[\begin{array}{ll}
\min & z\\
\mbox{subject to} & v(S)-\sum_{i\in S}x_{i}\leq z\mbox{ for all }S\subsetneqq N\\
& {\bf x}\in {\cal I}(v).
\end{array}\]
If $z^{*}$ is the optimal objective value, then the least core is ${\cal C}_{z^{*}}(v)$.

Cores of Convex Games.

The Shapley value of a cooperative game $(N,v)$ is the payoff vector $\boldsymnol{\phi}\in\mathbb{R}^{N}$ defined by
\[\phi_{i}=\sum_{\{S\subseteq N:i\in S\}}\frac{(|S|-1)!(|N|-|S|)!}{|N|!}\cdot\left [v(S)-v(S\setminus\{i\})\right ]\]
for all $i\in N$. A set $X$ of feasible payoff vectors is said to be stable (or von Neumann-Morgenstern solution) when every feasible payoff vector is either a member of $X$ or dominated by a member of $X$, but not both (Shapley \cite[p.24]{sha71}). Note that the cores ${\cal C}(v)$ and ${\cal C}_{0}$ have a little difference.

Theorem. (Shapley \cite[p.21]{sha71}). The core ${\cal C}_{0}(v)$ of a convex game $(N,v)$ is not empty. $\sharp$

Theorem (Shapley \cite[p.23]{sha71}). The Shapley value of a convex game $(N,v)$ is an element of the core ${\cal C}_{0}(v)$. $\sharp$

Theorem (Shapley \cite[p.24]{sha71}). The core ${\cal C}_{0}(v)$ of a convex game $(N,v)$ is stable. $\sharp$

Cores of Clan Games.

Theorem (Potters et al. \cite[p.279]{pot89}). Let $(N,v)$ be a clan game with clan $C$. Then, the core is
\[{\cal C}(v)=\left\{{\bf x}\in {\cal I}(v):x_{i}\leq m_{i}(v)\mbox{ for all }\in N\setminus C\right\}. \sharp\]

Proposition (Potters et al. \cite[p.280]{pot89}). Let $(N,v)$ be a cooperative game with $v\geq 0$. The game $(N,v)$ is a clan game with clan $C$ if and only if the following conditions are satisfied:

$v(N){\bf e}_{j}\in {\cal C}(v)$ for all $j\in C$;
there is at least one element ${\bf x}\in {\cal C}(v)$ satisfying $x_{i}=m_{i}(v)$ for all $i\in N\setminus C$. $\sharp$

Proposition (Potters et al. \cite[p.280]{pot89}). For a monotonic cooperative game $(N,v)$, we have the following properties.

(i) $(N,v)$ is a clan game.

(ii) There is a subset $C\subseteq N$, and for each $i\in C$ and a nonnegative number $\zeta_{i}$ such that $\sum_{i\in C}\zeta_{i}\leq v(N)$ and
\[{\cal C}(v)=\left\{{\bf x}\in {\cal I}(v):x_{i}\leq\zeta_{i}\mbox{ for all }i\in C\mbox{ and }\sum_{i\in N}x_{i}=v(N)\right\}. \sharp\]

Theorem (Potters et al. \cite[p.288]{pot89}). Let $(N,v)$ be a clan game with clan $C$. Then, the following statements are equivalent.

(a) $(N,v)$ is convex.

(b) $v(S)+\sum_{i\in N\setminus S}m_{i}(v)=v(N)$ for all $S\supseteq C$.

Theorem (Potters et al. \cite[p.290]{pot89}). The core ${\cal C}(v)$ of a clan game $(N,v)$ is a subsolution. $\sharp$

Cores of Games on Convex Geometry.

The games on convex geometry are presented in \S\ref{bil98}. Let $(N,v)$ be a cooperative games on convex geometry ${\cal L}$. The core of $(N,v)$ is defined by
\[{\cal C}({\cal L},v)=\left\{{\bf x}\in\mathbb{R}^{N}:\sum_{i\in N}x_{i}=v(N)\mbox{ and }
\sum_{i\in S}x_{i}\geq v(S)\mbox{ for all }S\in {\cal L}\right\}.\]
The positive core of $(N,v)$ is defined by
\[{\cal C}^{+}({\cal L},v)=\{{\bf x}\in{\cal C}({\cal L},v):x_{i}\geq 0\mbox{ for all }i\in N\}.\]
We recall that the vector ${\bf e}^{S}$ for the coalition $S$ is given by $e^{S}_{i}=1$ if $i\in S$ and $e^{S}_{i}=0$ otherwise.

Proposition (Bilbao and Jim\'{e}nez \cite[p.367]{bil99}). Let ${\cal L}\subseteq 2^{N}$ be a family such that $\emptyset ,N\in {\cal L}$, and let $(N,v)$ be a cooperative games on convex geometry ${\cal L}$. Then ${\cal C}({\cal L},v)\neq\emptyset$ if and only if, for all $S_{1},\cdots ,S_{n}\in {\cal L}\setminus\{\emptyset\}$ and $m\in\mathbb{N}$, we have that
\[\frac{1}{m}\sum_{i=1}^{n}{\bf e}^{S_{i}}={\bf e}^{N}\mbox{ implies }\frac{1}{m}\sum_{i=1}^{n}v(S_{i})\leq v(N).\]
Furthermore, ${\cal C}({\cal L},v)\neq\emptyset$ if and only if
\[\min\left\{\langle {\bf e}^{N},{\bf x}\rangle :\langle {\bf e}^{S},{\bf x}
\rangle\geq v(S)\mbox{ for all }S\in {\cal L}\right\}\leq v(N). \sharp\]

Proposition (Bilbao and Jim\'{e}nez \cite[p.367]{bil99}). Let ${\cal L}\subseteq 2^{N}$ be a family such that $\emptyset ,N\in {\cal L}$, and let $(N,v)$ be a cooperative games on convex geometry ${\cal L}$. Then ${\cal C}({\cal L},v)\neq\emptyset$ if and only if, for ${\bf y}^{S}\geq {\bf 0}$ and for all $S\in {\cal L}\setminus\{\emptyset\}$, we have that
\[\sum_{S\in {\cal L}\setminus\{\emptyset\}}{\bf y}^{S}{\bf e}^{S}={\bf e}^{N}
\mbox{ implies }\sum_{S\in {\cal L}\setminus\emptyset}{\bf y}^{S}v(S)\leq v(N). \sharp\]

Proposition (Bilbao and Jim\'{e}nez \cite[p.367]{bil99}). The core ${\cal C}({\cal L},v)$ of a cooperative game $(N,v)$ on a convex geometry ${\cal L}$ is either empty or a pointed polyhedron. $\sharp$

Theorem (Bilbao and Jim\'{e}nez \cite[p.368]{bil99}). Let $v$ be a cooperative game on a convex geometry ${\cal L}$ satisfying ${\cal C}({\cal L},v)\neq\emptyset$ and $v(S)\geq 0$. Then, the following statements are equivalent.

(a) The core ${\cal C}({\cal L},v)$ is a polytope.

(b) The atom $\{i\}\in {\cal L}$ for all $i\in N$.

A compatible ordering of a convex geometry ${\cal L}\subseteq 2^{N}$ is a total ordering of the elements of $N$, $i_{1}<i_{2}<\cdots <i_{n}$ satisfying $\{i_{1},i_{2},\cdots ,i_{k}\}\in {\cal L}$ for all $1\leq k\leq n$. A compatible ordering of ${\cal L}$ corresponds exactly to a maximal chain in ${\cal L}$. We denote by ${\cal R}({\cal L})$ the set of all the maximal chains of ${\cal L}$. Given an element $i\in N$ and a maximal chain $C$, we let $C(i)=\{j\in N:j\preceq i\mbox{ in the chain }C\}$ (Bilbao and Jim\'{e}nez \cite[p.368]{bil99}).

Definition (Bilbao and Jim\'{e}nez \cite[p.368]{bil99}). Let $v\in CGG^{\cal L}$ and $C\in {\cal R}({\cal L})$. The marginal worth vector ${\bf a}^{C}\in\mathbb{R}^{N}$ with respect to the chain $C$ in the game $v$ is given by
\[a^{C}_{i}=v(C(i))-v(C(i)\setminus\{i\})\]
for all $i\in N$. $\sharp$

The $i$th coordinate $a^{C}_{i}$ represents the marginal contribution of player $i$ to the coalition of his/her predecessors with respect to the chain $C$ (Bilbao and Jim\'{e}nez \cite[p.368]{bil99}).

Proposition (Bilbao and Jim\'{e}nez \cite[p.368]{bil99}). Let $v\in CGG^{\cal L}$ and $C\in {\cal R}({\cal L})$. For all $S\in C$, we have $\sum_{j\in S}a^{C}_{j}=v(S)$. $\sharp$

Definition (Bilbao and Jim\'{e}nez \cite[p.369]{bil99}). The Weber set of a game $v\in CGG^{\cal L}$ is the convex hull of the marginal worth vectors, ${\cal W}({\cal L},v)=\mbox{conv}\{{\bf a}^{C}:C\in {\cal R}({\cal L})\}$. $\sharp$

If ${\cal L}$ is the Boolean algebra $2^{N}$ and $v$ is an $n$-person cooperative game, then the core of $v$ is contained in the Werber set. However, the inclusion ${\cal C}({\cal L},v)\subseteq {\cal W}({\cal L},v)$ does not hold when $v$ is a game on a convex geometry ${\cal L}\neq 2^{N}$ (Bilbao and Jim\'{e}nez \cite[p.369]{bil99}).

Proposition (Bilbao and Jim\'{e}nez \cite[p.370]{bil99}). Let $v\in CGG^{\cal L}$ and $C\in {\cal R}({\cal L})$. If the vector ${\bf a}^{C}\in{\cal C}({\cal L},v)$, then ${\bf a}^{C}$ is a vertex of ${\cal C}({\cal L},v)$. $\sharp$

Let us recall that a convex geometry ${\cal L}$ is a lattice with the meet and join operations given in (\ref{bil99eq30}).

Definition (Bilbao and Jim\'{e}nez \cite[p.370]{bil99}). A game $v\in CGG^{\cal L}$ is said to be convex or supermodular when, for all $S,T\in {\cal L}$, we have

\[v(S\vee T)+v(S\wedge T)\geq v(S)+v(T),\]

and $v$ is called {\bf quasi-convex} if, for all $S,T\in {\cal L}$ with $S\cup T\in {\cal L}$, we have

\[v(S\cup T)+v(S\cap T)\geq v(S)+v(T). \sharp\]

It is obvious that convex implies quasi-convex. Note that if there is only a maximal chain in ${\cal L}$, all games defined on ${\cal L}$ are convex (Bilbao and Jim\'{e}nez \cite[p.370]{bil99}).

Proposition (Bilbao and Jim\'{e}nez \cite[p.370]{bil99}). A game $v\in CGG^{\cal L}$ is quasi-convex if and only if, for all $S,T\in {\cal L}$ such that $T\subseteq S$ and for all $i\in T\cap\mbox{ext}(S)$, we have

\[v(S)-v(S\setminus\{i\})\geq v(T)-v(T\setminus\{i\}). \sharp\]

Theorem (Bilbao and Jim\'{e}nez \cite[p.371]{bil99}). A game $v$ on a convex geometry ${\cal L}$ is quasi-convex if and only if ${\bf a}^{C}\in{\cal C}({\cal L},v)$ for all $C\in {\cal R}({\cal L})$. $\sharp$

Corollary (Bilbao and Jim\'{e}nez \cite[p.371]{bil99}). A game $v$ on a convex geometry ${\cal L}$ is quasi-convex if and only if ${\cal W}({\cal L},v)\subseteq{\cal C}({\cal L},v)$. $\sharp$

A game $v\in CGG^{\cal L}$ is {\bf monotone} if $S\subseteq T$ implies $v(S)\leq v(T)$. Note that if $v$ is monotone, then $v(S)\geq v(\emptyset )=0$ for all $S\in {\cal L}$ (Bilbao and Jim\'{e}nez \cite[p.371]{bil99}).

Theorem (Bilbao and Jim\'{e}nez \cite[p.371]{bil99}). Let $v\in CGG^{\cal L}$ be a monotone game. Then, the game is convex if and
only if ${\cal W}({\cal L},v)\subseteq{\cal C}({\cal L},v)$. $\sharp$

Cores of Restricted Games.

We recall that a {\bf constrained game} is a game $(N,v,X)$, where the payoff vectors are taken in the set $X\subseteq\mathbb{R}^{N}$. The core of the game $(N,v,X)$ is defined by
\[{\cal C}(N,v,X)=\{{\bf x}\in X:\sum_{i\in S}x_{i}\geq v(S)\mbox{ for all }S\subseteq N\}.\]
For a coalition structure ${\cal B}$, we define ${\cal C}(N,v,{\cal B})={\cal C}(N,v,X_{\cal B})$, where the constrained set is given in (\ref{aum74eqa}). Let us also recall the concept of section in Definition \ref{aum74d4} (Aumann and Dreze \cite[p.224]{aum74}).

Theorem (Aumann and Dreze \cite[p.224]{aum74}). Let $(N,v)$ be a zero-normalized game, and let ${\bf x}\in {\cal C}(N,v,{\cal B})$. Then the section of ${\cal C}(N,v,{\cal B})$ at ${\bf x}|_{N\setminus B_{k}}$ is ${\cal C}(B_{k},v_{\bf x}^{*},X_{k})$, where the game $v_{\bf x}^{*}$ is given in $(\ref{aum74eqc})$ and the constrained set $X_{k}$ is given in (\ref{aum74eqb}). $\sharp$

Let the cooperative game $(N,v)$ be superadditive. The super-additive cover of $(N,v)$ is the game $(N,\widehat{v})$ defined by
\[\widehat{v}(S)=\max\left\{\sum_{i=1}^{p}v(S_{i}):\mbox{$(S_{1},\cdots ,S_{p})$ is a partition of $S$}\right\}.\]
Note that the super-additive cover is itself super-additive (Aumann and Dreze \cite[p.229]{aum74}).

Theorem (Aumann and Dreze \cite[p.229]{aum74}). If ${\cal C}(N,v,{\cal B})\neq\emptyset$, then ${\cal C}(N,v,{\cal B})={\cal C}(\widehat{v})$. $\sharp$

We recall that game with restricted cooperation $\Gamma =(N,{\cal F},v,\lambda )$ in Definition \ref{gad17}. As usual, we define the core ${\cal C}(\Gamma )$ of the game $\Gamma$ as
\[{\cal C}(\Gamma )=\left\{{\bf x}\in\mathbb{R}^{N}:
\sum_{i\in S}x_{i}\geq v(S)\mbox{ for all }S\in {\cal F}\mbox{ and }\sum_{i\in N}x_{i}=\lambda\right\}.\]
The {\bf positive core} of the game $\Gamma $latex is defined as
\[{\cal C}^{+}(\Gamma )=\left\{{\bf x}\in {\cal C}(\Gamma ):{\bf x}\geq {\bf 0}\right\}.\]

\begin{equation}{\label{gat16}}\tag{19}\mbox{}\end{equation}

Theorem \ref{gat16}. (Faigle \cite[p.413]{fai89}). The game $\Gamma =(N,{\cal F},v,\lambda )$ is balanced if and only if ${\cal C}(\Gamma )\neq\emptyset$. $\sharp$

Based on Theorem \ref{gat16}, we call $\Gamma$ completely balanced when ${\cal C}^{+}(\Gamma )\neq\emptyset$.

Theorem (Faigle \cite[p.413]{fai89}). The game $\Gamma =(N,{\cal F},v,\lambda )$ is completely balanced if and only if, for all $S_{1},\cdots ,S_{k}\in {\cal F}\cup\{\emptyset\}$ and a positive integer $m\in\mathbb{N}$, we have that
\[\frac{1}{m}\sum_{i=1}^{k}1_{S_{i}}\leq 1_{N}\mbox{ implies }\frac{1}{m}\sum_{i=1}^{k}v(S_{i})\leq\lambda .\sharp\]

It is also apparent that ${\cal C}(\Gamma )={\cal C}^{+}(\Gamma )$ if each player of the game $\Gamma$ can form a feasible coalition without including any other player. For a large class of games, a certain converse also holds (Faigle \cite[p.414]{fai89}).

Theorem (Faigle \cite[p.414]{fai89}). Let $\Gamma =(N,{\cal F},v,\lambda )$ be a positive balanced game such that $S\cap T\in {\cal F}$ whenever $S,T\in {\cal F}$. Then ${\cal C}(\Gamma )={\cal C}^{+}(\Gamma )$ if and only if $\{i\}\in {\cal F}$ for all $i\in N$. $\sharp$

We consider the game $\Gamma =(N,{\cal F},v,\lambda )$ with $N\in {\cal F}$ and $v(N)=\lambda$. Let $\bar{\cal F}$ consists of all those subsets $S\subseteq N$ with $S=S_{1}\cup\cdots\cup S_{k}$, where $S_{1},\cdots ,S_{k}$ are pairwise disjoint feasible coalitions of $\Gamma$. We define the set function $\bar{v}$ on $\bar{\cal F}$ via
\[\bar{v}(S)=\max\sum_{i}v(S_{i})\]
where the maximum is taken over all representations of $S$ as a union of pairwise disjoint feasible coaliitions. Setting $\bar{\lambda}=\bar{v}(N)$, we obtain a new game $\bar{\Gamma}=(N,\bar{\cal F},\bar{v},\bar{\lambda})$ (Faigle \cite[p.415]{fai89}).

Proposition (Faigle \cite[p.415]{fai89}). We have the following properties.

(i) $\bar{\cal F}$ is closed under taking disjoint unions of coalitions and $\bar{v}$ is superadditive, i.e., for all $S,T\in\bar{\cal F}$ with $S\cap T=\emptyset$, $\bar{v}(S)+\bar{v}(T)\leq\bar{v}(S\cup T)$.

(ii) If $\lambda =\bar{\lambda}$, then ${\cal C}(\Gamma )={\cal C}(\bar{\Gamma})$. $\sharp$

Cores of Multi-Choice Cooperative Games.

Given a multi-choice game $(N,v)$, let ${\bf s}\in\prod_{i\in N}M_{i}$ and ${\bf x},{\bf y}\in {\cal MI}(v)$. The imputation ${\bf y}$ dominates the imputation ${\bf x}$ via coalition ${\bf s}$, denoted by ${\bf y}\geq_{\bf s}{\bf x}$, if and only if $\sum_{i\in N}Y_{is_{i}}\geq v({\bf s})$ and $Y_{is_{i}}\geq X_{is_{i}}$ for all $i\in c(i)$, where $c(i)=\{i\in N:s_{i}>0\}$ is the {\bf carrier} of ${\bf s}$, i.e., the set of players who participate in ${\bf s}$. We say that the imputation ${\bf y}$ dominates the imputation ${\bf x}$ if and only if there exists an coalition ${\bf s}$ such that ${\bf y}\geq_{\bf s}{\bf x}$. The core ${\cal MC}(v)$ of muti-choice game $(N,v)$ is defined by
\begin{equation}{\label{van95d12}}\tag{20}
{\cal MC}(v)=\left\{{\bf x}\in {\cal MI}(v):\sum_{i\in N}X_{is_{i}}\geq v({\bf s})\mbox{ for all coalitions}
{\bf s}\in\prod_{i\in N}M_{i}\right\}.
\end{equation}
The dominance core ${\cal MDC}(v)$ of multi-choice game $(N,v)$ is defined by
\[{\cal MDC}(v)=\left\{{\bf x}\in {\cal MI}(v):\mbox{ there exists no ${\bf y}\in {\cal MI}(v)$
such that ${\bf y}$ dominates ${\bf x}$}\right\}.\]
(van den Nouweland et al. \cite[p.291-292]{van95}).

Proposition (van den Nouweland et al. \cite[p.292-293]{van95}). For each multi-choice game $(N,v)$, we have the following properties.

(i) We have ${\cal MC}(v)\subseteq {\cal MDC}(v)$.

(ii) If $(N,v)$ is additive defined in (\ref{ga18}), then we have
\[{\cal MC}(v)={\cal MDC}(v)={\cal MI}(v)=\{{\bf x}\},\]
where $x_{ij}=v(j{\bf e}^{\{i\}})-v((j-1){\bf e}^{\{i\}})$ for all $i\in N$ and $j\in M_{i}\setminus\{0\}$. $\sharp$

Proposition (van den Nouweland et al. \cite[p.293-295]{van95}). Let $(N,v)$ be a multi-choice game. We have the following properties.

(i) If ${\cal MDC}(v)\neq\emptyset$, then ${\cal MC}(v)={\cal MDC}(v)$ if and only if the zero-normalization $v_{0}$ of $v$ defined in Definition \ref{gad20} satisfies $v_{0}({\bf s})\leq v_{0}({\bf m})$ for all coalitions ${\bf s}$.

(ii) If ${\cal MC}(v)\neq\emptyset$, then ${\cal MC}(v)={\cal MDC}(v)$.

(iii) ${\cal MC}(v)$ and ${\cal MDC}(v)$ are convex.

(iv) The core ${\cal MC}(v)\neq\emptyset$ if and only if $v$ is balanced in Definition \ref{gad20}. $\sharp$

\begin{equation}{\label{b}}\tag{B}\mbox{}\end{equation}

Bargaining Set.

Let $(N,v)$ be a game with ${\cal I}(v)\neq\emptyset$. For $i,j\in N$, we define $\Gamma_{ij}$ as
\[\Gamma_{ij}=\left\{S:i\in S\subseteq N\setminus\{j\}\right\}.\]

If ${\bf x}\in {\cal I}(v)$, then an objection of player $i$ against player $j$ with respect to the imputation ${\bf x}$ is a pair $(S,{\bf y})$ with $S\in\Gamma_{ij}$ and ${\bf y}\in\mathbb{R}^{S}$ satisfying
\begin{equation}{\label{ga21}}\tag{21}
\sum_{i\in S}y_{i}\leq v(S)
\end{equation}
and $y_{k}>x_{k}$ for all $k\in S$.
If we have an imputation ${\bf x}$ and an objection $(S,{\bf y})$ of player $i$ against player $j$ with respect to the imputation ${\bf x}$, then $(T,{\bf z})$ is a counter objection when $T\in\Gamma_{ji}$ and ${\bf z}\in\mathbb{R}^{T}$ satisfying
\begin{equation}{\label{ga22}}\tag{22}
\sum_{i\in T}z_{i}\leq v(T),
\end{equation}
$z_{k}\geq y_{k}$ for all $k\in S\cap T$ and $z_{k}\geq x_{k}$ for $k\in T\setminus S$.

An imputation ${\bf x}\in {\cal I}(v)$ is an element of the bargaining set ${\cal M}_{0}(v)$ for the grand coalition when, for any objection of one player against another with respect to ${\bf x}$, there exists a counter objection. If the inequalities in (\ref{ga21}) and (\ref{ga22}) are taken to be the equalities, then the bargaining set is denoted by ${\cal M}_{1}(v)$. Note that the core elements in ${\cal C}(v)$ admit no objection, since if ${\bf x}\in {\cal C}(v)$ and $(S,{\bf y})$ is an objection, then $\sum_{i\in S}y_{i}> \sum_{i\in S}x_{i}\geq v(S)$ which violates the definition. Therefore, for any game $(N,v)$, we have ${\cal C}(v)\subseteq {\cal M}_{0}(v)$. (Potters et al. \cite[p.279]{pot89} and Maschler et al. \cite[p.91]{mas72}).

Theorem (Maschler et al. \cite[p.91]{mas72}). If the cooperative game $(N,v)$ is convex, then ${\cal M}_{1}(v)={\cal C}(v)$. $\sharp$

Theorem (Potters et al. \cite[p.279]{pot89}). If $(N,v)$ is a clan game with clan $C$, then ${\cal C}(v)={\cal M}_{0}(v)$. $\sharp$

Bargaining Set for the Games with Coalition Structure.

We recall that a constrained game is a game $(N,v,X)$, where the payoff vectors are taken in the set $X\subseteq\mathbb{R}^{N}$. Let $(N,v,X,{\cal B})$ be a constrained game with a coalition structure ${\cal B}=\{B_{1},\cdots ,B_{m}\}$. If $i$ and $j$ are elements of $B_{k}$ and ${\bf x}\in X$, an objection of $i$ against $j$ with respect to ${\bf x}$ consists of payoff vector ${\bf y}\in\mathbb{R}^{N}$ and a coalition $S\in\Gamma_{ij}$ satisfying
\[y_{i}>x_{i}, y_{k}\geq x_{k}\mbox{ for all }k\in S\setminus\{i\}\mbox{ and }\sum_{k\in S}y_{k}\leq v(S).\]
A counter objection of $j$ to such an objection consists of payoff vector ${\bf z}\in\mathbb{R}^{N}$ and a coalition $T\in\Gamma_{ji}$ satisfying
\[z_{k}\geq x_{k}\mbox{ for all }k\in T\setminus S, z_{k}\geq y_{k}\mbox{ for all }
k\in S\cap T\mbox{ and }\sum_{k\in T}z_{k}\leq v(T).\]
The bargaining set ${\cal M}(N,v,X,{\cal B})$ is the set of payoff vectors ${\bf x}\in X$ such that for all $k$ and all $i,j\in B_{k}$, player $j$ has a counter objection to every objection of $i$ against $j$ with respect to ${\bf x}$. We also define ${\cal M}_{0}(N,v,{\cal B})={\cal M}(N,v,X_{\cal B},{\cal B})$, where $X_{\cal B}$ is given in (\ref{aum74eqa}). Let us recall the concept of section in Definition \ref{aum74d4} (Aumann and Dreze \cite[p.227]{aum74}).

Theorem (Aumann and Dreze \cite[p.227]{aum74}). Let $(N,v)$ be a zero-normalized game and ${\bf x}\in {\cal M}(N,v,{\cal B})$. Then the section of ${\cal M}_{0}(N,v,{\cal B})$ at ${\bf x}|_{N\setminus B_{k}}$ is included in ${\cal M}(B_{k},v_{\bf x}^{*},X_{k})$, where the game $v_{\bf x}^{*}$ is given in (\ref{aum74eqc}) and the constrained set $X_{k}$ is given in (\ref{aum74eqb}). $\sharp$

Let $({\bf x};{\cal B})$ be a coalitionally rational payoff configuration for a cooperative game $(N,v)$ defined in (\ref{oweeq1313}). Let us recall the concept of parters defined in (\ref{ga23}).

Given two nonempty disjoint subsets $K$ and $L$ of some $B_{k}\in {\cal B}$, an objection of $K$ against $L$ with respect to $({\bf x};{\cal B})$ is a coalitionally rational payoff configuration $({\bf y},{\cal U})$ satisfying $P(K;{\cal U})\cap L=\emptyset$, $y_{i}>x_{i}$ for all $i\in K$ and $y_{k}\geq x_{k}$ for all $k\in P(K;{\cal U})$.
Let $({\bf y};{\cal U})$ be an objection of $K$ against $L$ with respect to $({\bf x};{\cal B})$. A counter objection of $L$ against $K$ with respect to $({\bf x};{\cal B})$ is a coalitionally rational payoff configuration $({\bf z};{\cal V})$ satisfying $K\not\subseteq P(L;{\cal V})$, $z_{k}\geq x_{k}$ for $k\in P(L;{\cal V})$ and $z_{k}\geq y_{k}$ for $k\in P(L;{\cal V})\cap P(K;{\cal U})$.

Briefly, the members of $K$, in their objection against $L$, claim that they can obtain more by changing to a new coalitionally rational payoff configuration, and that their new partners will agree to this. The members of $L$ can counter object if it is possible for them to find a third coalitionally rational payoff configuration in which they and all their partners receive at least their original shares. If they need some of $K$’s partners for this, they give these players at least as much as in the objection coalitionally rational payoff configuration. Note that it may be necessary for $L$ to use some members of $K$ as partners. However, they may not use them all (Owen \cite[p.315]{owe}).

A coalitionally rational payoff configuration $({\bf x};{\cal B})$ is called stable when, for every objection of a $K$ against $L$ with respect to $({\bf x};{\cal B})$, $L$ has a counter objection.
The bargaining set ${\cal M}_{1}(N,v,{\cal B})$ is the set of all stable coalitionally rational payoff configurations.
The bargaining set ${\cal M}_{2}(N,v,{\cal B})$ with respect to $({\bf x};{\cal B})$ is the set of all coalitionally rational payoff configuration $({\bf x};{\cal B})$ such that, whenever any set $K$ has an objection against a set $L$, at least one member of $L$ has a
counter objection.
The bargaining set ${\cal M}_{3}(N,v,{\cal B})$ with respect to $({\bf x};{\cal B})$ is the set of all coalitionally rational payoff configuration $({\bf x};{\cal B})$ such that, if any single player $i$ has an objection against a set $L$, then $L$ has a counter objection against $i$.

It is easy to see that
\[{\cal M}_{1}(N,v,{\cal B})\subseteq {\cal M}_{2}(N,v,{\cal B})\mbox{ and }
{\cal M}_{1}(N,v,{\cal B})\subseteq {\cal M}_{3}(N,v,{\cal B}).\]
The relationship between ${\cal M}_{2}(N,v,{\cal B})$ and ${\cal M}_{3}(N,v,{\cal B})$ is not clear. Instead of coalitionally rational payoff configuration, we deal with individually rational payoff configuration. This will give rise to the three sets ${\cal M}_{1}^{(i)}(N,v,{\cal B})$, ${\cal M}^{(i)}_{2}(N,v,{\cal B})$ and ${\cal M}^{(i)}_{3}(N,v,{\cal B})$, derived from ${\cal M}_{1}(N,v,{\cal B})$, ${\cal M}_{2}(N,v,{\cal B})$ and ${\cal M}_{3}(N,v,{\cal B})$, respectively (Owen \cite[p.315-316]{owe}).

Theorem (Owen \cite[p.316]{owe}). Given a cooperative game $(N,v,{\cal B})$ with coalition structure ${\cal B}$, there is at least one vector ${\bf x}$ satisfying $({\bf x};{\cal B})\in {\cal M}^{(i)}_{2}(N,v,{\cal B})$. $\sharp$

\begin{equation}{\label{c}}\tag{C}\mbox{}\end{equation}

The Kernel

Closely related to the bargaining set is the concept of the kernel. This is mainly based on the ideas of excess and surplus defined in (\ref{ga24}) and (\ref{ga15}), respectively.

A pre-imputation ${\bf x}$ is said to belong to the pre-kernel of a cooperative game $(N,v)$ when $s_{ij}({\bf x})=s_{ji}({\bf x})$ for $i,j\in N$ with $i\neq j$, where $s_{ij}$ is defined in (\ref{ga15}).
An imputation ${\bf x}$ is said to belong to the kernel of a cooperative game $(N,v)$ when $s_{ij}({\bf x})\leq s_{ji}({\bf x})$ or $x_{j}=v(\{j\})$ for all $i,j\in N$ with $i\neq j$. (Maschler et al. \cite[p.74-75]{mas72}).

We consider another concept of pre-kernel and kernel. For each pre-imputation ${\bf x}$ in ${\cal I}^{*}(v)$ and $i,j\in N$ with $i\neq j$, we say that $i$ outweighs $j$ at ${\bf x}$ when $s_{ij}({\bf x})>s_{ji}({\bf x})$, and that $i$ and $j$ are in equilibrium at ${\bf x}$ when neither of these players outweighs the other, i.e.,
\begin{equation}{\label{mas79eq33}}\tag{23}
s_{ij}({\bf x})=s_{ji}({\bf x}).
\end{equation}
However, these concepts are based on ${\cal I}^{*}(v)$. More generally, let $Y$ be any closed and convex polyhedron in ${\cal I}^{*}(v)$ and let ${\bf x}$ be any member of $Y$. Then, we say that $i$ outweighs $j$ at ${\bf x}$ with respect to $Y$ when $s_{ij}({\bf x})>s_{ji}({\bf x})$ and, for all sufficiently small $\delta >0$, $x_{j}-\delta\in Y$ and $\delta +x_{i}\in Y$. In particular, for ${\bf x}\in {\cal I}(v)$, $i$ outweighs $j$ with respect to ${\cal I}(v)$ if and only if $s_{ij}({\bf x})>s_{ji}({\bf x})$ and $x_{j}>v(\{j\})$. Therefore, the equilibrium condition for the case $Y={\cal I}(v)$ is defined to be neither of these players outweighs the other with respect to ${\cal I}(v)$, which can be written as
\[\left (s_{ij}({\bf x})\leq s_{ji}({\bf x})\mbox{ or }x_{j}\leq v(\{j\})\right )\mbox{ and }
\left (s_{ji}({\bf x})\leq s_{ij}({\bf x})\mbox{ or }x_{i}\leq v(i)\right ),\]
by the imputation, which is equivalent to
\begin{equation}{\label{ga56}}\tag{24}
\left (s_{ij}({\bf x})\leq s_{ji}({\bf x})\mbox{ or }x_{j}=v(\{j\})\right )\mbox{ and }
\left (s_{ji}({\bf x})\leq s_{ij}({\bf x})\mbox{ or }x_{i}=v(i)\right ).
\end{equation}
Let $Y\subseteq {\cal I}^{*}(v)$. The {\bf kernel} for $Y$ of the game $(N,v)$ is the set of ${\bf x}\in Y$ at which every two players are in equilibrium with respect to $Y$. It is denoted by ${\cal K}_{Y}(v)$. The kernel for ${\cal I}(v)$ is called simply the kernel of game $(N,v)$ and is denoted by ${\cal K}(v)$, while the kernel for ${\cal I}^{*}(v)$ is called the pre-kernel of game $(N,v)$ and is denoted by ${\cal K}^{*}(v)$. From (\ref{ga56}), we see that an imputation is in the kernel if and only if it satisfies the following inequalities
\begin{equation}{\label{mas79eq35}}\tag{25}
\left [s_{ij}({\bf x})-s_{ji}({\bf x})\right ]\cdot\left [x_{j}-v(\{j\})
\right ]\leq 0\mbox{ and }\left [s_{ji}({\bf x})-s_{ij}({\bf x})\right ]\cdot\left [x_{i}-v(i)\right ]\leq 0.
\end{equation}
for all $i,j\in N$ with $i\neq j$. Also the pre-imputation is in the pre-kernel if and only if it satisfies the simpler requirement (\ref{mas79eq33}) for all $i,j\in N$ with $i\neq j$. It is known that the kernel and pre-kernel are always nonempty. We note that condition (\ref{ga37}) is essential for a nonempty kernel, since otherwise ${\cal I}(v)$ itself is empty (Maschler et al. \cite[p.314]{mas79}).

Proposition (Maschler et al. \cite[p.75]{mas72}). Let the game $(N,v)$ be zero-monotonic game. If ${\bf x}$ belongs to the pre-kernel for the grand coalition, then ${\bf x}$ is an imputation. $\sharp$

Proposition (Maschler et al. \cite[p.76]{mas72}). The kernel and the pre-kernel for the grand coalition coincide for zero-monotonic games (and hence in particular for super-additive games). $\sharp$

A pseudo-imputation ${\bf x}$ is said to belong to the pseudo-kernel of a game $(N,v)$ for the grand coalition when $s_{ij}({\bf x})\leq s_{ji}({\bf x})$ or $x_{j}=0$ for all $i,j\in N$ with $i\neq j$.

Proposition (Maschler et al. \cite[p.77]{mas72}). Let the cooperative game $(N,v)$ satisfy
\begin{equation}{\label{mas72eq212}}\tag{26}
\mbox{$v(S)\leq v(T)$ for $\emptyset\neq S\subseteq T\neq N$ $($quasi-monotonicity$)$}
\end{equation}
and
\begin{equation}{\label{mas72eq213}}\tag{27}
v(i)+v(N)\geq v(N\setminus\{i\})\mbox{ for all }i\in N.
\end{equation}
If ${\bf x}$ belongs to the pre-kernel for the grand coalition, then ${\bf x}$ is a pseudo-imputation. Moreover, under the conditions (\ref{mas72eq212}) and (\ref{mas72eq213}), the pre-kernel and pseudo-kernel for grand coalition coincide. $\sharp$

We can interpret the pre-kernel for the grand coalition as follows. We take a game $v^{*}$ which is monotonic, satisfies $v(\emptyset )\geq 0$, and is strategically equivalent to $v$. The “inverse image” of the pseudo-kernel of $v^{*}$ for the grand coalition under this equivalence is the pre-kernel of $v$ for the grand coalition. Thus, loosely speaking, up to strategic equivalence, the pre-kernel for the grand coalition is one of many pseudo-kernels a game may have (Maschler et al. \cite[p.77]{mas72}).

Let us recall that the cooperatuve game $(N,v)$ is convex when the following condition is satisfied:
\[v(S)+v(T)\leq v(S\cup T)+v(S\cap T)\]
for all $S,T\subseteq N$, which is equivalent to
\[e(S,{\bf x})+e(T,{\bf x})\leq e(S\cup T,{\bf x})+e(S\cap T,{\bf x})\]
for all $S,T\subseteq N$ and for any ${\bf x}\in\mathbb{R}^{n}$ (Maschler et al. \cite[p.83]{mas72}).

Theorem (Maschler et al. \cite[p.83]{mas72}). If the cooperative game $(N,v)$ is convex, then the kernel and pre-kernel for the grand coalition coincide. If $(N,v)$ is a convex game with $v\geq 0$, then the kernel and pseudo-kernel for the grand coalition coincide. $\sharp$

Theorem. (Maschler et al. \cite[p.89]{mas72}). The kernel of a convex game for the grand coalition consists of a single point. $\sharp$

Theorem (Maschler et al. \cite[p.314]{mas79}). Give any cooperative game $(N,v)$, we have ${\cal K}(v)\cap {\cal C}(v)={\cal K}^{*}(v)\cap {\cal C}(v)$. $\sharp$

Proposition (Maschler et al. \cite[p.316]{mas79}). If $(N,v_{1})$ and $(N,v_{2})$ are two cooperative games having the same cores, i.e., ${\cal C}(v_{1})={\cal C}(v_{2})$, then we have ${\cal K}(v_{1})\cap {\cal C}(v_{1})={\cal K}(v_{2})\cap {\cal C}(v_{2})$. $\sharp$

Proposition (Maschler et al. \cite[p.316]{mas79}). Given two cooperative games $(N,v_{1})$ and $(N,v_{2})$ and any $\epsilon_{1}$ and $\epsilon_{2}$, we have the following properties.

(i) If ${\cal C}_{\epsilon_{1}}(v_{1})={\cal C}_{\epsilon_{2}}(v_{2})$, then ${\cal K}^{*}(v_{1})\cap {\cal C}_{\epsilon_{1}}(v_{1})={\cal K}^{*}(v_{2})\cap {\cal C}_{\epsilon_{2}}(v_{2})$.

(ii) If $I(v_{1})=I(v_{2})$ and ${\cal C}_{\epsilon_{1}}(v_{1})={\cal C}_{\epsilon_{2}}(v_{2})$, then ${\cal K}(v_{1})\cap {\cal C}_{\epsilon_{1}}(v_{1})={\cal K}(v_{2})\cap {\cal C}_{\epsilon_{2}}(v_{2})$. $\sharp$

Given a cooperative game $(N,v)$, let
\[r_{i}=\max_{\{S:i\in S\}}\left [v(S)-v(S\setminus\{i\})\right ].\]
We define a real number $\epsilon^{*}(v)$ by
\[\epsilon^{*}(v)=\max_{S\neq N,\emptyset}\min\left\{v(S)-\sum_{i\in S}v(i), v(S)+\sum_{i\in N\setminus S}r_{i}-v(N)\right\}.\]

Theorem. (Maschler et al. \cite[p.320-321]{mas79}). Given a cooperative game $(N,v)$, we have the following properties.

(i) We have ${\cal K}(v)\subseteq {\cal C}_{\epsilon}(v)$ for all $\epsilon\geq\epsilon^{*}(v)$.

(ii) If $(N,v)$ is zero-monotonic, then ${\cal K}^{*}(v)\subseteq {\cal C}_{\epsilon}(v)$ for all $\epsilon\geq\epsilon^{*}(v)$.

(iii) Given two cooperative games $(N,v_{1})$ and $(N,v_{2})$ and any $\epsilon_{1}$ and $\epsilon_{2}$ with $I(v_{1})=I(v_{2})$ and ${\cal C}_{\epsilon_{1}}(v_{1})={\cal C}_{\epsilon_{2}}(v_{2})$, if $\epsilon\geq\epsilon^{*}(v_{1})$ and $\epsilon_{1}\geq\epsilon^{*}(v_{2})$, then ${\cal K}(v_{1})={\cal K}(v_{2})$. $\sharp$

The Kernel for Veto-Rich Games.

We recall that the veto-rich game $(N,v)$ has at least one veto player $i$. If $i$ is a veto player and $j$ is another player
in a veto-rich game $(N,v)$, then
\[e(S,{\bf x})=-\sum_{k\in S}x_{k}\leq -x_{j}=e(\{j\},{\bf x})\]
for all imputations ${\bf x}$ and all coalitions $S$ containing player $j$ but not the veto player $i$. Hence, we have $s_{ji}({\bf x})=-x_{j}$.

\begin{equation}{\label{aril31}}\tag{28}\mbox{}\end{equation}

Proposition \ref{aril31}. (Arin and Feltkamp \cite{ari97}). Let ${\bf x}$ lie in the kernel of the veto-rich game $(N,v)$. Then $x_{i}-v(i)\geq x_{j}$ for any veto player $i$ and any player $j$. $\sharp$

Note that in an essential veto-rich game, any veto player $i$ is allocated strictly more than his individual worth $v(i)$ in a kernel element ${\bf x}$. This is easily seen: by Proposition \ref{aril31}, $x_{i}-v(i)$ is larger than or equal to $x_{j}$ for any other player $j$ and if $i$ gets a payoff $v(i)$, then all other players get $0$. But then
\[v(N)=x(N)=v(i)=\sum_{j\in N}v(\{j\}),\]
so the game is inessential. Hence, it holds that $s_{ij}({\bf x})\geq s_{ji}({\bf x})$ for all other players $j$. Second, if $v(i)>0$ in a veto-rich game $(N,v)$ with veto player $i$, then this veto player gets strictly more than any other player in a kernel element. Third, if there are two or more veto players, their payoffs are equal in a kernel element. Obviously, in this case, the individual worths of the veto players are zero. It can also happen that though there is only one veto player, there is another player who gets the same payoff the same payoff as the veto player.

\begin{equation}{\label{aril33}}\tag{29}\mbox{}\end{equation}

Proposition \ref{aril33}. (Arin and Feltkamp \cite{ari97}). If ${\bf x}$ lies in the kernel of the veto-rich game $(N,v)$ and $v(S)\geq v(N)$ for a oalition $S$ containing a veto player $i$, then $e(S,{\bf x})\geq 0$ and $x_{j}=0$ for all players $j$ in the complement of $S$. $\sharp$

Proposition. (Arin and Feltkamp \cite{ari97}). If ${\bf x}$ lies in the kernel of the veto-rich game $(N,v)$ with veto player $i$, and $v(S)<v(N)$ for a coalition $S$ containing vetor player $i$, then $e(S,{\bf x})<0$. $\sharp$

The next corollary asserts that in an essential veto-rich game with veto player $i$ the player other than veto player $i$ whose payoffs were not determined in Proposition \ref{aril33} get positive payoffs in any kernel element.

\begin{equation}{\label{aric35}}\tag{30}\mbox{}\end{equation}

Corollary \ref{aric35}. (Arin and Feltkamp \cite{ari97}). If ${\bf x}$ lies in the kernel of the game $(N,v)$ with veto player $i$, and if, for another player $j$, there is no coalition $S\subset N\setminus\{j\}$ with $i\in S$ and $v(S)\geq v(N)$, then $x_{j}>0$. $\sharp$

Theorem. (Arin and Feltkamp \cite{ari97}). The kernel of a veto-rich game $(N,v)$ consists of a unique element. $\sharp$

We now compute the kernel of a veto-rich game that arises an auctioneer when sells an indivisible object in an auction with many bidders.

Example. Let $N=\{0,1,\cdots ,n\}$ and let the auctioneer (player 0) valuate the object at $a_{0}=0$, while this value is $a_{j}\geq 0$ to the other players $j\in N$. The worth $v(S)$ of a coalition $S$ is zero if this coalition does not contain the auctioneer, and $v(S)=\max\{a_{j}:j\in S\}$ otherwise. Let a player with the highest valuation be called $h$ and let a player with the highest remaining valuation after $h$ has been eliminated be called $s$. (i.e. the second highest valuation). Suppose $a_{h}\geq a_{s} \geq 0$ and $a_{h}>0$. Now $v(\{0,h\})=v(N)$, so Proposition \ref{aril33} implies that a kernel element ${\bf x}$ has to satisfy $x_{j}=0$ if $j\not\in\{0,h\}$. If $a_{s}=a_{h}$, then also $x_{h}=0$, and the seller gets all, i.e., $x_{0}=a_{h}$. On the other hand, if $a_{s}<a_{h}$, then there is no coalition $S$ not containing player $h$ with $v(S)\geq v(N)$, so by Corollary \ref{aric35}, $x_{h}>0$. Remembering the remark after the corollary, we obtain $-x_{h}=s_{h0}({\bf x})=s_{0h}({\bf x})$. Any coalition $S$ containing the auctioneer but not player $h$ has excess $E(S,{\bf x})=v(S)-x_{0}$, which is highest if player $s$ is an element of $S$. Hence $s_{0h}({\bf x})=E(\{0,s\},{\bf x})=a_{s}-x_{0}$, which implies $x_{h}=x_{0}-a_{s}$. Together with efficiency $(x_{0}+x_{h}=v(N)=a_{h}$), this implies $x_{0}=(a_{h}+a_{s})/2$ and $x_{h}=(a_{h}-a_{s})/2$. So according to the kernel, the object is sold to the bidder with highest valuation and the price is the average of the highest and second highest valuation. $\sharp$

The Kernel for Coalition Structures.

Original Treatment.

Let $(N,v)$ be a cooperative game with $v(i)=0$ for each $i\in N$. Let ${\cal B}=\{B_{1},\cdots ,B_{m}\}$ be a coalition structure. Then $({\bf x};{\cal B})$ will be called an individually rational payoff configuration when the following conditions are satisfied:

$x_{i}\geq 0=v(i)$ for all $i\in N$;
$\sum_{i\in B_{j}}x_{i}=v(B_{j})$ for all $j=1,\cdots ,m$.

If we fix the coalition structure ${\cal B}$, then the set of payoff ${\bf x}$ satisfying the above two conditions is a Cartesian product of $m$ simplices:
\[X({\cal B})\equiv S_{1}\times S_{2}\times\cdots\times S_{m},\]
where
\[S_{j}=\left\{(x_{i})_{i\in B_{j}}:x_{i}\geq 0\mbox{ and }v(B_{j})=\sum_{i\in B_{j}}x_{i}\right\}\]
for all $j=1\cdots ,m$. The excess of $S$ with respect to the individually rational payoff configuration $({\bf x};{\cal B})$ is also defined by
\[e(S)=v(S)-\sum_{i\in S}x_{i}.\]
The excess of $S$ represents the total amount that the members of $S$ gain (or lose, if $e(S)<0$), if they withdraw from $({\bf x};{\cal B})$ and form the coalition $S$. Clearly, $e(B_{j})=0$ for all $j=1,\cdots ,m$ (Davis and Maschler \cite[p.224-225]{dav65}).

Let $k$ and $l$ be two distinct players in a coalition $B_{j}$. We denote by ${\cal B}_{kl}$ the set of all the coalition which conatins player $k$ but do not contain player $l$, i.e., ${\cal B}_{kl}=\{S\subseteq N:k\in S,l\not\in S\}$. Let $({\bf x};{\cal B})$ be an individually rational payoff configuration. Then the maximum surplus of $k$ over $l$ with respect to $({\bf x},{\cal B})$ is
\[s_{kl}=\max_{S\in {\cal B}_{kl}}e(S).\]
Therefore, the maximum surplus represents the maximal amount player $k$ can gain (or the minimal amount that he/she must lose), by withdrawing from $({\bf x};{\cal B})$ and joining a coalition $S$ which does not require the consent of $l$ (since $l\not\in S$), with the understanding that the other members of $S$ will be satisfied with getting the same amount they had in $({\bf x};{\cal B})$ (Davis and Maschler \cite[p.225]{dav65}).

Let $({\bf x};{\cal B})$ be an individually rational payoff configuration for a game $v$, and let $k,l$ be two distinct players in a coalition $B_{j}$. Player $k$ is said to {\bf outweigh} player $l$ with respect to $({\bf x};{\cal B})$, and this is denoted by $k\gg l$, if and only if $s_{kl}>s_{lk}$ and $x_{l}\neq 0$. If neither $k\gg l$ nor $l\gg k$, we say that $k$ and $l$ are in equilibrium. For the sake of completeness we define each player to be in equilibrium with himself/herself. Similarly, we also regard any two players, who belong to disjoint coalitions of ${\cal B}$, as being in equilibrium. We write $k\sim l$ if and only if $k$ and $l$ are in equilibrium (Davis and Maschler \cite[p.225]{dav65}).

Proposition. (Davis and Maschler \cite[p.226]{dav65}). It is easy to verify that $k\gg l$ if and only if $(s_{kl}-s_{lk})\cdot x_{l}>0$ and that $k\sim l$ if and only if $(s_{kl}-s_{lk})\cdot x_{l}\leq 0$ and $(s_{lk}-s_{kl})\cdot x_{k}\leq 0$. $\sharp$

Let $({\bf x};{\cal B})$ be an individually rational payoff configuration for a cooperative game $(N,v)$. A coalition $B_{j}$ of ${\cal B}$ is said to be balanced with respect to $({\bf x};{\cal B})$, if each two players of $B_{j}$ are in equilibrium. The kernel ${\cal K}(v)$ of a cooperative game $(N,v)$ is the set of all the individually rational payoff configurations having only balanced coalitions. Or, equivalently, $({\bf x};{\cal B})\in {\cal K}(v)$ if and only if each two players are in equilibrium with respect to $({\bf x};{\cal B})$ (Davis and Maschler \cite[p.226]{dav65}).

It is clear from the definition that the kernel does not depend on the labeling of the players. If $(N,v_{1})$ and $(N,v_{2})$ are strategically equivalent games, and if $({\bf x};{\cal B})$ and $({\bf y};{\cal B})$ are corresponding individually rational payoff configurations in $v_{1}$ and $v_{2}$, respectively, then the corresponding excesses of the various coalitions, with respect to the two games, are proportional (with a positive factor of proportion). Therefore, $({\bf x};{\cal B})$ belongs to the kernel of $v_{1}$ if and pnly if $({\bf y};{\cal B})$ belongs to the kernel of $v_{2}$. Thus, the kernel if invariant under strategic equivalence (Davis and Maschler \cite[p.226]{dav65}).

Theorem. (Davis and Maschler \cite[p.233]{dav65}). The kernel of a game is contained in the bargaining set ${\cal M}_{1}(v)$. $\sharp$

Theorem. (Davis and Maschler \cite[p.235]{dav65})(Existence Theorem). Let ${\cal B}$ be a coalition structure for cooperative game $(N,v)$. Then, there exists a payoff vector ${\bf x}$ such that $({\bf x};{\cal B})\in {\cal }K(v)$. $\sharp$

Alternative Treatment.

Let $({\bf x};{\cal B})$ be an individually rational payoff configuration, and let $i,j$ be distinct members of some $B_{k}\in {\cal B}$. We shall say $i$ outweighs $j$, denoted by $i\succ j$, if and only if $s_{ij}({\bf x})>s_{ji}({\bf x})$ and $x_{j}>v(\{j\})$. It seems that if $i\succ j$, then $i$ can make a demand on $j$ which, in some sense, $j$ cannot contest. Thus, if $i\succ j$, there is a certain instability. We now define the kernel as the set of individually rational payoff configurations for which no such instability occurs (Owen \cite[p.320]{owe}).

Definition. (Owen \cite[p.320]{owe}). The kernel of a game $(N,v)$ is the set ${\cal K}$ of all individually rational payoff configurations $({\bf x};{\cal B})$ such that, for $B_{k}\in {\cal B}$, there are no $i,j\in B_{k}$ with $i\succ j$. $\sharp$

Theorem. (Owen \cite[p.320]{owe}). For any game, we have ${\cal K}\subseteq{\cal M}^{(i)}_{2}$. $\sharp$

We recall that a constrained game is a game $(N,v,X)$, where the payoff vectors are taken in the set $X\subseteq\mathbb{R}^{N}$. Let ${\cal B}$ be a coalition structure. We define
\[{\cal K}(N,v,X,{\cal B})=\left\{{\bf x}\in X:\mbox{for all $k$ and for all $i,j\in B_{k}$, we have
$s_{ij}({\bf x})\geq s_{ji}({\bf x})$ or $x_{i}=v(i)$}\right\}\]
and ${\cal K}(N,v,{\cal B})={\cal K}(N,v,X_{\cal B},{\cal B})$, where $X_{\cal B}$ is given in (\ref{aum74eqa}). Then ${\cal K}(N,v,{\cal B})$ is called the kernel of the game $(N,v,{\cal B})$. Let us recall the concept of section in Definition \ref{aum74d4} (Aumann and Dreze \cite[p.228]{aum74}).

Theorem. (Aumann and Dreze \cite[p.228]{aum74}). Let $(N,v)$ be a $0$-normalized game and let ${\bf x}\in {\cal K}(N,v,{\cal B})$. Then the section of ${\cal K}(N,v,{\cal B})$ at ${\bf x}|_{N\setminus B_{k}}$ is ${\cal K}(B_{k},v_{\bf x}^{*},X_{k})$, where the game $v_{\bf x}^{*}$ is given in (\ref{aum74eqc}) and the constrained set $X_{k}$ is given in (\ref{aum74eqb}). $\sharp$

The game $(N,v)$ is decomposable with partition ${\cal B}$ is defined in Definition \ref{aum74d3}. Then we have the following corollary.

Corollary (Aumann and Dreze \cite[p.228]{aum74}). Let $(N,v)$ be a $0$-normalized game and decomposable with partition ${\cal B}=\{B_{1},\cdots ,B_{p}\}$. Then, we have ${\cal K}(N,v,{\cal B})=\prod_{k=1}^{p}{\cal N} (B_{k},v|_{B_{k}},X_{k})$, where $v_{B_{k}}$ is the game on $B_{k}$ defined for all $T\subseteq B_{k}$ by $v|_{B_{k}}(T)=v(T)$. $\sharp$

\begin{equation}{\label{d}}\tag{D}\mbox{}\end{equation}

The Nucleolus.

If the core ${\cal C}(v)$ is not empty, then it may contain more than one point. For the nonempty $\epsilon$-core ${\cal C}_{\epsilon}(v)$, we can possibly shrink it down to one point. The following example shows that how to shrink the $\epsilon$-core.

Example. We consider a three-person game with characteristic function defined by $v(i)=0$ for $i=1,2,3$, $v(\{1,2,3\})=1$, $v(\{1,2\})=4/5$, $v(\{1,3\})=2/5$ and $v(\{2,3\})=1/5$. We first calculate the least core. Now, we have
\[{\cal C}_{\epsilon}(v)=\left\{\left (x_{1},x_{2},1-x_{1}-x_{2}\right ):
-\epsilon\leq x_{1}\leq\frac{4}{5}+\epsilon ,-\epsilon\leq x_{2}\leq\frac{3}{5}+\epsilon ,
-\epsilon\leq x_{1}+x_{2}\leq 1+\epsilon\right\}.\]
We can obtain the first least core ${\cal C}_{\epsilon_{1}}(v)$ for $\epsilon_{1}=1-/10$ given by
\[{\cal C}_{\epsilon^{*}}(v)=\left\{\left (x_{1},x_{2},1-x_{1}-x_{2}\right ):
\frac{2}{5}\leq x_{1}\leq\frac{7}{10},\frac{1}{5}\leq x_{2}\leq\frac{1}{2},x_{1}+x_{2}=\frac{9}{10}\right\},\]
which does not contain only one point. Next, restricted to the allocation in the first least core ${\cal C}_{\epsilon_{1}}(v)$, we shall calculate the next least core ${\cal C}_{\epsilon_{2}}(v)$; that is to say, we want to minimize the maximum excesses over ${\cal C}_{\epsilon_{1}}(v)$. Given any ${\bf x}\in {\cal C}_{\epsilon_{1}}(v)$, we need to calculate the excesses for each coalition
\[\begin{array}{lll}
e(\{1\},{\bf x})=-x_{1}, & e(\{2\},{\bf x})=-x_{2}, & e(\{3\},{\bf x})=-x_{3}=-\frac{1}{10},\\
e(\{1,3\},{\bf x})=x_{2}-\frac{3}{5}, & e(\{2,3\},{\bf x})=x_{1}-\frac{4}{5},
& e(\{1,2\},{\bf x})=\frac{4}{5}-x_{1}-x_{2}=-\frac{1}{10}.
\end{array}\]
Now, we set
\[\Sigma_{1}=\left\{S\subsetneqq N:e(S,{\bf x})<\epsilon_{1}\mbox{ for some }{\bf x}\in {\cal C}_{\epsilon_{1}}(v)\right\}.\]
Then, we can obtain
\[\Sigma_{1}=\{\{1\},\{2\},\{1,3\},\{2,3\}\}.\]
Let $X_{1}={\cal C}_{\epsilon_{1}}(v)$. We define
\[\epsilon_{2}=\min_{{\bf x}\in X_{1}}\max_{S\in\Sigma_{1}}e(S,{\bf x}),\]
which is the first maximum excess over all ${\cal C}_{\epsilon_{1}}(v)$ Now, we define
\[X_{2}=\left\{{\bf x}\in X_{1}:e(S,{\bf x})<\epsilon_{2}\mbox{ for all }S\in\Sigma_{1}\right\},\]
which is the subset of allocation from $X_{1}$ that are preferred by the coalitions in $\Sigma_{1}$. If $X_{2}$ contains exactly one imputation, then this point is the fair allocation, i.e., the solution of this problem. Therefore, the next least core is
\begin{align*}
C_{\epsilon_{2}}(v) & =X_{2}=\left\{{\bf x}\in X_{1}:e(\{1\},{\bf x})\leq\epsilon_{2},
e(\{2\},{\bf x})\leq\epsilon_{2},e(\{1,3\},{\bf x})\leq\epsilon_{2},e(\{2,3\},{\bf x})\leq\epsilon_{2}\right\}\\
& =\left\{{\bf x}\in X_{1}:-x_{1}\leq\epsilon_{2},-x_{2}\leq\epsilon_{2},
x_{2}-\frac{3}{5}\leq\epsilon_{2},x_{1}-\frac{4}{5}\leq\epsilon_{2}\right\}.
\end{align*}
We can find the first $\epsilon_{2}=-\frac{5}{20}=-\frac{1}{4}$ for which $X_{2}$ is nonempty. Therefore, we have
\begin{align*}
C_{\epsilon_{2}}(v) & =X_{2}=\left\{{\bf x}\in X_{1}:-x_{1}\leq -\frac{1}{4},-x_{2}\leq -\frac{1}{4},
x_{2}-\frac{3}{5}\leq -\frac{1}{4},x_{1}-\frac{4}{5}\leq -\frac{1}{4}\right\}\\
& =\left\{{\bf x}\in X_{1}:\frac{1}{4}\leq x_{1}\leq\frac{11}{20},
\frac{1}{4}\leq x_{2}\leq\frac{7}{20},x_{1}+x_{2}=\frac{18}{20}\right\}.
\end{align*}
The last equality gives us
\[0=\left (\frac{11}{20}-x_{1}\right )+\left (\frac{7}{20}-x_{2}\right ),\]
which implies
\[x_{1}=\frac{11}{20}, x_{2}=\frac{7}{20}\mbox{ and }x_{3}=\frac{2}{20}.\]
In other words, we obtain
\[C_{\epsilon_{2}}(v)=X_{2}=\left\{\left (\frac{11}{20},\frac{7}{20},\frac{2}{20}\right )\right\}.\]
Since $X_{2}$ contains exactly one point, it is the solution of this problem, and is also called the nucleolus of this problem.
}\end{Ex}

In general, we need to continue this procedure if $X_{2}$ contains more than one point in the above example. The computational algorithm is given below.

Step 1 (Initialization). We start with the set of all possible imputation ${\cal I}(v)$ and the coalitions excluding $N$ and $\emptyset$. Set
\[X_{0}={\cal I}(v)\mbox{ and }\Sigma_{0}=\left\{S\subsetneqq N:S\neq\emptyset\right\}.\]

Step 2 (Successive Calculation).
The minimum of the maximum dissatisfaction is
\[\epsilon_{k}=\min_{{\bf x}\in X_{k-1}}\max_{S\in\Sigma_{k-1}}e(S,{\bf x}).\]

The set of allocations achieving the minimax dissatisfaction is
\begin{align*}
X_{k} & \equiv\left\{{\bf x}\in X_{k-1}:\epsilon_{k}=
\min_{{\bf x}\in X_{k-1}}\max_{S\in\Sigma_{k-1}}e(S,{\bf x})=\max_{S\in\Sigma_{k-1}}e(S,{\bf x})\right\}\\
& =\left\{{\bf x}\in X_{k-1}:e(S,{\bf x})\leq\epsilon_{k}\mbox{ for all }S\in\Sigma_{k-1}\right\}.
\end{align*}
Alternatively, calculate the first $\epsilon_{k}$ so that
\[{\cal C}_{\epsilon_{k}}(v)=\left\{{\bf x}\in X_{k-1}:e(S,{\bf x})\leq\epsilon_{k}
\mbox{ for all }S\in\Sigma_{k-1}\right\}\neq\emptyset .\]
Then, set $X_{k}={\cal C}_{\epsilon_{k}}(v)$.
The set of coalitions achieving the minimax dissatisfaction is
\[\Sigma_{k}^{*}=\left\{S\in\Sigma_{k-1}:e(S,{\bf x})=\epsilon_{k}\mbox{ for all }{\bf x}\in X_{k}\right\}.\]
Delete these coalitions from the previous set
\[\Sigma_{k}=\Sigma_{k-1}\setminus\Sigma_{k}^{*}.\]

Step 3 (Done). If $\Sigma_{k}=\emptyset$, we are done; otherwise, set $k\leftarrow k+1$ and go to the successive step. $\sharp$

When this algorithm stops at $k=m$, we see that $X_{m}$ is the nucleolus of the core and will satisfy the inclusions
\[X_{m}\subset X_{m-1}\subset\cdots\subset X_{1}={\cal C}_{\epsilon_{1}}(v)\subset X_{0}={\cal I}(v).\]
We also have
\[\emptyset =\Sigma_{m}\subset\Sigma_{m-1}\subset\cdots\subset\Sigma_{2}\subset\Sigma_{1}\subset\Sigma_{0}.\]
The allocation sets decrease down to a single point, i.e., the nucleolus, and the unhappiest coalition decrease down to the empty set.

Theorem. The algorithm for calculating the nucleolus stops in a finite number of steps $m<+\infty$. For each $k=1,2,\cdots ,m$, we also have the following results.

(i) We have $-\infty <\epsilon_{k}<+\infty$.

(ii) $X_{k}\neq\emptyset$ are convex, closed and biunded.

(iii) $\Sigma_{k}\neq\emptyset$ for $k=1,2,\cdots ,m-1$.

(iv) $\epsilon_{k+1}<\epsilon_{k}$.

In addition, $X_{m}$ is a single point given by
\[X_{m}=\bigcap_{k=1}^{m}X_{k}.\sharp\]

For an imputation ${\bf x}\in {\cal I}(v)$, we define the excess of a coalition $S\subset N$ at ${\bf x}$ as $E(S,{\bf x})=v(S)-x(S)$ and let $\theta ({\bf x})$ be the vector of all excesses at ${\bf x}$ arranged in nonincreasing order of magnitude. The lexicographic order $\prec_{L}$ between two vectors ${\bf x}$ and ${\bf y}$ is defined by ${\bf x}\prec_{L}{\bf y}$ if there exists an index $k$ satisfying $x_{l}=y_{l}$ for all $l<k$ and $x_{k}<y_{k}$, and the weak lexicographic order $\preceq_{L}$ by ${\bf x}\preceq_{L}{\bf y}$ if ${\bf x}\prec_{L}{\bf y}$ or ${\bf x}={\bf y}$

Given a game $(N,v)$ and a payoff vector ${\bf x}\in\mathbb{R}^{N}$, we define the $2^{|N|}$-vector $\boldsymbol{\theta}}({\bf x})$ as the vector whose components are the excesses of the $2^{|N|}$ subsets $S\subseteq N$ arranged in nonincreasing order, i.e., $\theta_{k}({\bf x})=e(S_{k},{\bf x})$, where $S_{1},S_{2},\cdots ,S_{2^{|N|}}$ are the subsets of $N$ arranged by $e(S_{k},{\bf x})\geq e(S_{k+1},{\bf x})$ (Owen \cite[p.323]{owe}).

We shall order the several vectors $\boldsymbol{\theta}}({\bf x})$ by the lexicographic order. Generally speaking, if we are given two vectors $\boldsymbol{\alpha}=(\alpha_{1},\cdots .\alpha_{q})$ and $\boldsymnol{\beta}=(\beta_{1},\cdots .\beta_{q})$, we say that $\boldsymbol{\alpha}$ is lexicographically smaller than $\boldsymbol{\beta}$ if and only if there is some integer $k$ with $1\leq k\leq q$ such that $\alpha_{l}=\beta_{l}$ for $1\leq l<k$ and $\alpha_{k}<\beta_{k}$. We shall write $\boldsymbol{\alpha}<_{L}\boldsymbol{\beta}$ for this relation, and $\boldsymbol{\alpha}\leq_{L} \boldsymbol{\beta}$ if either $\boldsymbol{\alpha}<_{L} \boldsymbol{\beta}$ or $\boldsymbol{\alpha}=\boldsymbol{\beta}$. Now the lexicographic ordering on $\boldsymbol{\theta}({\bf x})$ can be used to induce an order on the payoff vectors ${\bf x}$, i.e., we shall write ${\bf x}\preceq {\bf y}$ if and only if $\boldsymbol{\theta}({\bf x})\leq_{L}\boldsymbol{\theta}({\bf y})$ and ${\bf x}\prec {\bf y}$ if and only if $\boldsymbol{\theta}({\bf x})<_{L}\boldsymbol{\theta}({\bf y})$ (Owen \cite[p.323]{owe}).

Schmeidler \cite{sch69} introduced the nucleolus of a game $(N,v)$ as the unique imputation that lexicographically minimizes the vector of nonincreasingly ordered excesses over the set of imputations ${\cal I}(v)$, i.e.,
\begin{equation}{\label{ga55}}\tag{31}
{\cal N}_{0}(v)=\left\{{\bf x}\in {\cal I}(v):\boldsymbol{\theta}({\bf x})\leq_{L}{\bf y}\mbox{ for all }{\bf y}\in {\cal I}(v)\right\}.
\end{equation}
It is well known that the nucleolus ${\cal N}_{0}(v)$ lies in the core ${\cal C}(v)$ of the game $(N,v)$ provided that this core is nonempty. We also have that the kernel of a game $(N,v)$ always contains the nucleolus ${\cal N}_{0}(v)$ (Arin and Feltkamp \cite{ari97}).

In general, let $X$ be a subset of $\mathbb{R}^{N}$. The nucleolus of $(N,v)$ over the set $X$ is the set ${\cal N}(X)$ defined by
\[{\cal N}(X)=\left\{{\bf x}\in X:{\bf x}\preceq {\bf y}\mbox{ for all }{\bf y}\in X\right\}=\left\{{\bf x}\in X:
\boldsymbol{\theta}({\bf x})\leq_{L}\boldsymbol{\theta}({\bf y})\mbox{ for all }{\bf y}\in X\right\}.\]
The nucleolus consists of those points ${\bf x}$ which minimize the function $\boldsymbol{\theta}({\bf x})$ over the set $X$ in the sense of lexicographic order. Thus the nucleolus depends, not only on the game $(N,v)$ but also on the particular set $X$ which has been chosen. Usually, $X$ is chosen to be the set of all imputations; more generally, for a given coalition structure ${\cal B}$, $X$ may be taken as $X({\cal B})$, the set of all ${\bf x}$ satisfying conditions (\ref{oweeq1311}) and (\ref{oweeq1312}), so that $({\bf x},{\cal B})$ is an individually rational payoff configuration. Other choice may be possible for $X$. If $X$ is the imputation set ${\cal I}(v)$, then ${\cal N}({\cal I}(v))\equiv {\cal N}(v)$ is called the nucleolus of game $(N,v)$. If $X$ is the pre-imputation set ${\cal I}^{*}(v)$, then ${\cal N}({\cal I}^{*}(v))\equiv {\cal N}^{*}(v)$ is called the pre-nucleolus of game $(N,v)$ (Owen \cite[p.323]{owe}).

Theorem. (Owen \cite[p.323]{owe}). If $X$ is a nonempty compact set, then ${\cal N}(X)$ is also nonempty and compact. $\sharp$

Theorem. (Owen \cite[p.326]{owe}). If $X$ is nonempty compact and convex set, then ${\cal N}(X)$ consists of a single point. $\sharp$

Theorem. (Kohlberg \cite[p.64]{koh71}). If $X$ is the set of all pseudo-imputation, then ${\cal N}(X)$ consists of a single point. (However, we have to note that this result is true under the assumption $v(i)=0$ for all $i\in N$). $\sharp$

Theorem. (Maschler et al. \cite[p.91]{mas72}). Let $X$ be the set of all pseudo-imputation. For convex games, the kernel for the grand coalition and the nucleolus ${\cal N}(X)$ coincide. $\sharp$

Theorem. (Owen \cite[p.327]{owe}). Given a cooperative game $(N,v)$ and a coalition structure ${\cal B}$, let $X({\cal B})$ be the set of all vectors satisfying (\ref{oweeq1311}) and (\ref{oweeq1312}), and let $\widehat{\bf x}$ be the nucleolus of $(N,v)$ over $X({\cal B})$. Then $(\widehat{\bf x};{\cal B})\in {\cal K}$. $\sharp$

Given a cooperative game $(N,v)$, we shall construct a nested sequence $X_{0}\supseteq X_{1}\supseteq\cdots\supseteq X_{p}$ of sets of payoff vectors, and a nested sequence $\Sigma_{0}\supseteq\Sigma_{1}\supseteq\cdots\supseteq\Sigma_{p}$ of sets of coalitions. To initiate these sequences, we define $X_{0}= {\cal I}(v)$ and $\Sigma_{0}=\{S\subseteq N:S\neq N,\emptyset\}$. For $k=1,2,\cdots ,p$, we define recursively
\begin{align*}
& \epsilon_{k}=\min_{{\bf x}\in X_{k-1}}\max_{S\in\Sigma_{k-1}}e(S,{\bf x})\\
& X_{k}=\left\{{\bf x}\in X_{k-1}:\max_{S\in\Sigma_{k-1}}e(S,{\bf x})=\epsilon_{k}\right\}\\
& \Psi_{k}=\left\{S\in\Sigma_{k-1}:e(S,{\bf x})=\epsilon_{k}\mbox{ for all }{\bf x}\in X_{k}\right\}\\
& \Sigma_{k}=\Sigma_{k-1}\setminus\Psi_{k},
\end{align*}
where $p$ is the first value of $k$ for which $\Sigma_{k}=\emptyset$. The set $X_{p}$ will be called the {\bf lexicographic center} of $v$ (Maschler et al. \cite[p.332]{mas79}).

Theorem. (Maschler et al. \cite[p.334]{mas79}). If the cooperative game $(N,v)$ satisfies condition $(\ref{ga37})$, then the lexicographic center of a $(N,v)$ consists of a single point. $\sharp$

Theorem (Maschler et al. \cite[p.335]{mas79}). If the cooperative game $(N,v)$ satisfies condition $(\ref{ga37})$, then the nucleolus ${\cal N}(v)$ coincides with the lexicographic center, and hence consists of a single point. $\sharp$

Corollary (Maschler et al. \cite[p.335]{mas79}). Suppose that the cooperative game $(N,v)$ satisfies condition (\ref{ga37}). For any $\epsilon$, if ${\cal C}_{\epsilon}(v)\cap {\cal I}(v)\neq\emptyset$, then it contains ${\cal N}(v)$. In particular, if $v$ is zero-monotonic, then ${\cal N}(v)$ is contained in every nonempty strong $\epsilon$-core, and hence in the least-core. $\sharp$

Theorem. (Maschler et al. \cite[p.335]{mas79}). If the cooperative game $(N,v)$ satisfies condition $(\ref{ga37})$, then we have ${\cal N}(v)\subseteq {\cal K}(v)$. $\sharp$

Reduced game properties study the invariance of a solution when viewed by any sub-coalition of players. The Davis-Maschler reduced game property is defined as follows: Let $(N,v)$ be a game, $T\subseteq N$ with $T\neq\emptyset ,N$ and ${\bf x}\in\mathbb{R}^{T}$. Then the reduced game with respect to $N\setminus T$ and ${\bf x}$ is the game $(N\setminus T,v_{T,{\bf x}})$ defined by
\[v_{T,{\bf x}}=\left\{\begin{array}{ll}
0 & \mbox{if $S=\emptyset$}\\
v(N)-\sum_{i\in T}x_{i} & \mbox{if $S=N\setminus T$}\\
\max_{U\subseteq T}\left\{v(S\cup U)-\sum_{i\in U}x_{i}\right\} & \mbox{if $S\subseteq N\setminus T$}.
\end{array}\right .\]
The total worth in the reduced game is equal to the total worth in the original game minus the payoff allocated to the removed players. The worth of a coalition in the reduced game is the most profitable of the possibilities of cooperating with the removed players assuming that these players are paid according ${\bf x}$ (Arin and Inarra \cite[p.14]{ari98}).

The pre-nucleolus of a game $v$ satisfies the Davis-Maschler reduced game property: For every game $v$ and every $T\subseteq N$ if ${\bf x}={\cal N}^{*}(v)$, then ${\bf x}^{T}={\cal N}^{*}(T,v_{T,{\bf x}})$. For balanced game, and hence, in particular, for convex games, the nucleolus coincides with the pre-nucleolus (Arin and Inarra \cite[p.14]{ari98}).

Theorem. (Arin and Inarra \cite[p.15]{ari98} and Kohlberg \cite{koh71}). Let $v$ be a game and ${\cal D}_{1},{\cal D}_{2},\cdots$ be the sets of coalitions $S\neq\emptyset ,N$ of highest excess at ${\bf x}$, second highest, third highest, rtc. Let ${\cal B}_{t}={\cal D}_{1}\cup\cdots\cup {\cal D}_{t}$. A necessary and sufficient condition for ${\bf x}$ to be the pre-nucleolus is that each ${\cal B}_{t}$ be a balanced collection of sets. $\sharp$

Theorem. (Arin and Inarra \cite[p.15]{ari98}). For any convex game $v$, $T\subseteq N$ and core element ${\bf x}$, the reduced game $(T,v_{T,{\bf x}})$ is convex. $\sharp$

For a game $v$ and any pre-imputation ${\bf x}$, we denote by ${\cal D}({\bf x})$ the set of coalitions of maximal excess other than $\emptyset$ and $N$, i.e.,
\[{\cal D}({\bf x})=\left\{S\subseteq N:S\neq\emptyset ,N\mbox{ and }
e(S,{\bf x})\geq e(T,{\bf x})\mbox{ whenever }T\neq\emptyset ,N\right\}.\]
We denote by ${\cal P}$ a non-trivial partition and by $|{\cal P}|$ the cardinal of partition ${\cal P}$. The collection of sets ${\cal A}({\cal P})=\left\{S\subseteq N:N\setminus\in {\cal P}\right\}$ is called anti-partition and its cardinal is also $|{\cal P}|$.

\begin{equation}{\label{ari98t31}}\tag{32}\mbox{}\end{equation}

Proposition \ref{ari98t31}. (Arin and Inarra \cite[p.16]{ari98}) For any convex game $v$, at least one of the following statement is true:

(i) ${\cal D}({\cal N}(v))$ contains a non-trivial partition;

(ii) ${\cal D}({\cal N}(v))$ contains an anti-partition. $\sharp$

Fro any game $v$, the excess of a minimal balanced collection ${\cal B}$ with weights $\{\lambda^{S}\}_{S\in {\cal B}}$ is defined by
\[e({\cal B})=\frac{\sum_{S\in {\cal B}}\lambda^{S}v(S)-v(N)}{\sum_{S\in {\cal B}}\lambda^{S}}.\]

\begin{equation}{\label{ari98t32}}\tag{33}\mbox{}\end{equation}

Proposition \ref{ari98t32}. (Arin and Inarra \cite[p.17]{ari98}). For any game $v$ and any pre-imputation ${\bf x}$, if a collection of sets with the same excess contains a minimal balanced collection ${\cal B}$, then $e(S,{\bf x})=e({\cal B})$ for all $S$ belonging to the collection of sets. $\sharp$

For a game $(N,v)$ and for all $S\in {\cal D}({\cal N}^{*}(v))$, we have $e(S,{\cal N}(v))=\max_{{\cal B}\in\widehat{\cal B}}e({\cal B})$, where $\widehat{\cal B}$ is the set of minimal balanced families formed with the set $N$ and excluding partition $N$ (Arin and Inarra \cite[p.17]{ari98}).

By Proposition \ref{ari98t31}, convex games contain at least one partition ${\cal P}$ or one anti-partition ${\cal A}({\cal P})$. Note that
\[e({\cal P})=\frac{\sum_{S\in {\cal P}}v(S)-v(N)}{|{\cal P}|}\mbox{ and }
e({\cal A}({\cal P})=\frac{\sum_{S\in {\cal P}}v(S)-(|{\cal P}|-1)v(N)}{|{\cal P}|}.\]
Therefore, by Proposition \ref{ari98t32}, we have $e(S,{\bf x})=e({\cal P})$ for all $S\in {\cal P}$ and $e(S,{\bf x})=e({\cal A}({\cal P})$ for all $S\in {\cal A}({\cal P}$ (Arin and Inarra \cite[p.17]{ari98}).

A game $(N,v)$ is {\bf zero-monotonic} if $v(S)\geq v(T)+\sum_{i\in S\setminus T}v(i)$ whenever $T\subseteq S$. The zero-normalization of a game is defined by $v'(S)=v(S)-\sum_{i\in S}v(i)$ for all coalitions $S\subseteq N$. A game $v$ is zero-monotonic if and only if its zero-normalization $v’$ is monotonic (Potters \cite[p.366]{pot91}).

For $t\in\mathbb{R}$, we write ${\cal B}_{t}({\bf x})=\{S\subseteq N:e(S,{\bf x})\geq t\mbox{ for }S\neq\emptyset ,N\}$ (i.e., the collection of coalitions with excess greater than or equal to $t$). The collection of coalition ${\cal B}$ is called {\bf balanced on $C\subseteq N$} if there are positive real numbers $\{y^{S}\}_{S\in {\cal B}}$ satisfying $\sum_{S\in {\cal B}}y^{S}{\bf e}^{S}\leq {\bf e}^{N}$ and $\sum_{S\in {\cal B}}y^{S}{\bf e}^{S\cap C}={\bf e}^{C}$ (Potters \cite[p.367]{pot91}).

We summarize some properties (or axioms) of the nucleolus.

(One Point Concept). The nucleolus of a game $v$ with ${\cal I}(v)\neq\emptyset$ and the pre-nucleolus of a game $v$ consist of one point (Potters \cite[p.367]{pot91}).

(Characterization by Balancedness). A point ${\bf x}\in {\cal I}(v)$ belongs to the nulceolus of $v$ if and only if the collections ${\cal B}_{t}({\bf x})$ is balanced on $C({\bf x})\equiv\{i\in N:x_{i}>v(i)\}$ for all $t\in\mathbb{R}$ with ${\cal B}_{t}({\bf x})\neq\emptyset$. A point ${\bf x}\in {\cal I}^{*}(v)$ belongs to the pre-nucleolus of $v$ if and only if ${\cal B}_{t}({\bf x})$ is balanced for all $t\in\mathbb{R}$ with ${\cal B}_{t}({\bf x})\neq\emptyset$ (Potters \cite[p.367]{pot91}).

(Anonimity). The nucleolus and pre-nucleolus are anonimous in the following sense. Let $v$ be a game and let $\pi$ be a permutation of $N$. Then $v^{\pi}$ is the game defined by $v^{\pi}(S)=v(\pi^{-1}(S))$. Furthermore, for each vector ${\bf x}\in\mathbb{R}^{N}$, the vector ${\bf x}^{\pi}$ is defined by $x^{\pi}_{i}=x_{\pi^{-1}(i)}$ for all $i\in N$. If ${\bf x}$ is the nucleolus (resp. pre-nucleolus) of $v$, then ${\bf x}^{\pi}$ is the nucleolus (resp. pre-nucleolus) of $v^{\pi}$ (Potters \cite[p.368]{pot91}).

(Covariance). The nucleolus and pre-nucleolus are covariant, i.e., if $v$ is a game, $\lambda >0$ and ${\bf a}\in\mathbb{R}^{N}$, then ${\cal N}(\lambda v+\bar{a})=\lambda {\cal N}(v)+{\bf a}$ and ${\cal N}^{*}(\lambda v+\bar{a})=\lambda {\cal N}^{*}(v)+{\bf a}$ (i.e the pre-nucleolus), where $\bar{a}$ is the additive game generated by ${\bf a}$ (Potters \cite[p.368]{pot91}).

(Reduced Game Property for the Pre-Nucleolus). Let $(N,v)$ be a game and ${\bf x}$ an pre-imputation of $v$. For every coalition $\emptyset\neq T\subseteq N$, we define the reduced game $v_{T,{\bf x}}$ as the game with player set $T$ and values
\[v_{T,{\bf x}}(S)=\left\{\begin{array}{ll}
0 & \mbox{if $S=\emptyset$}\\
\max\{v(S\cup Q)-\sum_{i\in Q}x_{i}:Q\subseteq N\setminus T\} &
\mbox{if $S\subseteq T$ with $S\neq\emptyset ,T$}\\
v(N)-\sum_{i\in N\setminus T}x_{i} & \mbox{if $S=T$}.
\end{array}\right .\]
If ${\bf x}$ is the pre-nucleolus of $v$, then ${\bf x}|_{T}$ is the pre-nucleolus of $v_{T,{\bf x}}$ for all $\emptyset\neq T\subseteq N$.
This property is called the reduced game property. The pre-nucleolus is the unique one-point solution concept satisfying covariance, anonimity and the reduced game property (Potters \cite[p.368]{pot91}).

(Coincidence of the Nucleolus and Pre-Nucleolus for a Large Class of Games). The nucleolus and pre-nucelolus coincide if and only if the pre-nucleolus is an imputation. Therefore, if $v$ is zero-monotonic or $v$ has a nonempty core, then the nucleolus and pre-nucleolus coincide (Potters \cite[p.368]{pot91}).

(Restricted Reduced Game Property). For the nucleolus, we do not have, in general, the reduced game property. The only reason is that the imputation set does not have the reduced game property (i.e., ${\cal I}(v)\neq\emptyset$ and ${\bf x}\in {\cal I}(v)$ does not imply that ${\bf x}|_{T}\in I(v_{T,{\bf x}})$, since the imputation set $I(v_{T,{\bf x}})$ may even happen to be empty). The restricted reduced game property says that if ${\bf x}|_{T}$ is an imputation of the reduced game, then we can show that the reduced game property holds: If ${\cal I}(v)\neq\emptyset$, ${\bf x}$ the nucleolus of $v$ and $\emptyset\neq T\subseteq N$ such that ${\bf x}|_{T}\in I(v_{T,{\bf x}})$, then ${\bf x}|_{T}$ is the nucleolus of $v_{T,{\bf x}}$. We remark that if $v$ has a nonempty core, then the nucleolus ${\bf x}$ is in the core of $v$ and ${\bf x}|_{T}$ is also in the core of $v_{T,{\bf x}}$ for every nonempty coalition $T$ (the core has the reduced game property). Hence, for balanced games, the reduced game property holds also for the nucelolus (Potters \cite[p.369]{pot91}).

(Limit Property). We define the game $u_{0}$ by $u_{0}(S)=1$ if $S\neq\emptyset ,N$ and $u_{0}(\emptyset )=u_{0}(N)=0$. The limit property describes the behavior of the nucleolus on the set of games $\{v-tu_{0}:t\geq\epsilon_{0}(v)\}$. A solution rule $\boldsymbol{\Phi}$ which assigns to every game $v$ with ${\cal I}(v)\neq\emptyset$ a subset $\boldsymbol{\Phi}(v)\subseteq {\cal I}(v)$ has the limit property if the following conditions are satisfied:

for every game $v$, there is a real number $\epsilon (v)\geq\epsilon_{0}(v)$ such that $\boldsymbol{\Phi}(v-tu_{0})$ is not
dependent on $t$ if $t\geq\epsilon (v)$;
if we define $\boldsymbol{\Phi}^{*}(v)=\boldsymbol{\Phi}(v-tu_{0})$ for $t\geq\epsilon (v)$, then $\boldsymbol{\Phi}^{*}(v)\cap {\cal I}(v)\subseteq\boldsymbol{\Phi}(v)$ for all $v$ with ${\cal I}(v)\neq\emptyset$.

Notice that the limit property gives a pre-solution concept $\boldsymbol{\Phi}^{*}$ defined for all games $v$. We can show that the nucleolus has the limit property (Potters \cite[p.370]{pot91}).

(Alternative Reduced Game Property). Let $v$ be a game with ${\cal I}(v)\neq\emptyset$ and $\emptyset\neq S\subseteq N$. Let ${\bf a}\in\mathbb{R}^{N}$ with $a_{i}=v(i)$ for all $i\in N$. Then the alternative reduced game property reads as: If ${\bf x}$ is a nucleolus of $v$ and $S$ is the carrier of $\{i\in N:x_{i}>v(i)\}$, then ${\bf x}|_{S}$ is the pre-nucelolus of the reduced game $v_{S,{\bf a}}$. We can show that the nucleolus of a game satisfies the alternative reduced game property (Potters \cite[p.370]{pot91}).

Theorem. (Potters \cite[p.370]{pot91}). The nucleolus of a cooperative game satisfies anonimity, covariance, limit property, restricted reduced game property and alternative reduced game property. $\sharp$

Theorem. (Potters \cite[p.371]{pot91}). If $\boldsymbol{\Phi}$ is a rule which assigns to every game $v$ with ${\cal I}(v)\neq\emptyset$ an element $\boldsymbol{\Phi}(v)\in {\cal I}(v)$ with the following properties:

(Anonimity). $\boldsymbol{\Phi}(v^{\pi})=(\boldsymbol{\Phi}(v))^{\pi}$ for all games $v$ with ${\cal I}(v)\neq \emptyset$ and all permutations $\pi$ of $N$;
(Covariance). $\boldsymbol{\Phi}(\lambda v+\bar{a})=\lambda\boldsymbol{\Phi}(v)+{\bf a}$ for all $\lambda >0$ and all ${\bf a}\in\mathbb{R}^{N}$;
(Restricted Reduced Game Property). If $\boldsymbol{\Phi}(v)={\bf x}$ and ${\bf x}|_{T}\in I(v_{T,{\bf x}})$, then $\boldsymbol{\Phi}(v_{T,{\bf x}})={\bf x}|_{T}$;
(Limit Property). For every game $v$, there exists a real number $\epsilon (v)$ such that $\boldsymbol{\Phi}(v-tu_{0})$ is independent on $t$ for $t\geq\epsilon (v)$ and if this constant vector $\boldsymbol{\Phi}^{*}(v)\equiv\boldsymbol{\Phi}(v-tu_{0})$ is an element of the imputation set ${\cal I}(v)$, then $\boldsymbol{\Phi}(v)=\boldsymbol{\Phi}^{*}(v)$.

then $\boldsymbol{\Phi}(v)$ is the nucleolus of $v$ for all games $v$ with the pre-nucleolus of $v$ belonging to the imputation set ${\cal I}(v)$. $\sharp$

Theorem. (Potters \cite[p.372]{pot91}). Let $v$ be a game with ${\cal I}(v)\neq\emptyset$. Then the kernel satisfies limit property, restricted reduced game property and alternative reduced game property. $\sharp$

The Nucleolus for the Big Boss Games.

We recall that the marginal contribution of player $i$ to the grand coalition $N$ is given by $m_{i}(v)=v(N)-v(N\setminus\{i\})$. Let ${\bf m}(v)=(m_{i}(v))_{i\in N}$. For each coalition $S\subseteq N$ with $i\in S$, we define
\[r(S,i)=v(S)-\sum_{j\in S\setminus\{i\}}m_{j}(v)\mbox{ and }\widehat{m}_{i}(v)=\max_{i\in S\subseteq N}r(S,i).\]
Let $\widehat{\bf m}(v)=(\widehat{m}_{i}(v))_{i\in N}$. If the cooperative game $(N,v)$ has a nonempty dominance core, then the $\tau$-value $\boldsymbol{\tau}(v)=(\tau_{i}(v))_{i\in N}$ is given by the convex combination of ${\bf m}(v)$ and $\widehat{\bf m}(v)$ satisfying $\sum_{i\in N}\tau_{i}(v)=v(N)$ (Muto et al. \cite[p.305]{mut88}).

\begin{equation}{\label{mut88p31}}\tag{34}\mbox{}\end{equation}

Proposition \ref{mut88p31}. (Muto et al. \cite[p.306]{mut88}) Given a big boss game $(N,v)$, we have the following properties:

$m_{i}(v)\geq 0$ for all $i\in N\setminus\{1\}$;
$m_{1}(v)=v(N)$;
$\widehat{\bf m}(v)=\left (v(N)-\sum_{i\in N\setminus\{1\}}m_{i}(v),0,\cdots ,0\right )$;
${\bf m}(v)\geq\widehat{\bf m}(v)\geq {\bf 0}$. $latex \sharp

We define a set ${\cal H}(v)$ by
\[{\cal H}(v)=\left\{{\bf x}\in\mathbb{R}^{N}:\sum_{i\in N}x_{i}=v(N)\mbox{ and }
0\leq x_{i}\leq m_{i}(v)\mbox{ for all }i\in N\setminus\{1\}\right\}.\]
We see that ${\cal H}(v)$ is nonempty if $v$ is monotonic, since part (i) of Proposition \ref{mut88p31} says that $(v(N),0,\cdots ,0)$ is always contained in ${\cal H}(v)$. (Muto et al. \cite[p.306]{mut88}).

\begin{equation}{\label{mut88t32}}\tag{35}\mbox{}\end{equation}

Theorem \ref{mut88t32}. (Muto et al. \cite[p.306]{mut88}). $(N,v)$ is a big boss game if and only if ${\cal DC}(v)={\cal H}(v)$. $\sharp$

Therefore, the dominance core of an $n$-person big boss game is an $(n-1)$-dimensional parallelotope with $2^{n-1}$ vertices of the form $(u_{1},\cdots ,u_{n})$ where $u_{i}=0$ or $m_{i}(v)$ for $i=2,\cdots ,n$ and $u_{1}=v(N)-\sum_{i\in N\setminus\{1\}}u_{i}$. Hence, in the dominance core, each of the weak players $2,\cdots ,n$ gains at most this marginal contribution to the grand coalition; but it might also occur that they are completely exploited by the big boss (Muto et al. \cite[p.307]{mut88}).

The core cover ${\cal CC}(\bar{v})$ is given by
\[{\cal CC}(\bar{v})=\left\{{\bf x}\in\mathbb{R}^{N}:\sum_{i\in N}x_{i}=v(N)\mbox{ and }
\widehat{m}_{i}(v)\leq x_{i}\leq m_{i}(v)\mbox{ for all }i\in N\right\}.\]

Proposition. (Muto et al. \cite[p.307]{mut88}). If $(N,v)$ is a big boss game, then ${\cal H}(v)={\cal CC}(\bar{v})$. $\sharp$

\begin{equation}{\label{mut88p34}}\tag{36}\mbox{}\end{equation}

Proposition \ref{mut88p34}. (Muto et al. \cite[p.307]{mut88}). If $(N,v)$ is a big boss game with player $1$ as a big boss, then the following assertions are equivalent.

(a) $(N,v)$ is convex.

(b) Equality holds in every inequality in condition (ii) in Definition \ref{mut88d1}, i.e., $v(N)-v(S)=\sum_{i\in N\setminus S} m_{i}(v)$ for all $S\subseteq N$ and $1\in S$.

(d) We have $v(S)-v(S\setminus\{i\})=m_{i}(v)$ for all $S\subseteq N$ with $\{1\}\subset S$, $\{1\}\neq S$, and for all $i\in S\setminus\{1\}$. $\sharp$

Theorem. (Muto et al. \cite[p.307]{mut88}). If $(N,v)$ is a big boss game, then the dominance core ${\cal DC}(v)$ is a stable set; that is, it is the stable core if and only if $(N,v)$ is convex. $\sharp$

Recall the concept of subsolution in Definition \ref{gad15}.

Theorem. (Muto et al. \cite[p.309]{mut88}). If $(N,v)$ is a big boss game, then the dominance core ${\cal DC}(v)$ is a subsolution, i.e., it is the super core. $\sharp$

\begin{equation}{\label{mut88t41}}\tag{37}\mbox{}\end{equation}

Proposition \ref{mut88t41}. (Muto et al. \cite[p.309]{mut88}). If $(N,v)$ is a big boss game, then the $\tau$-value $\boldsymbol{\tau}(v)$ of $(N,v)$ is given by
\[\boldsymbol{\tau}(v)=\left (v(N)-\frac{1}{2}\sum_{i\in N\setminus\{1\}}
m_{i}(v),\frac{m_{2}(v)}{2},\cdots ,\frac{m_{n}(v)}{2}\right ).\]
i.e., $\boldsymbol{\tau}(v)$ is the center of the dominnace core ${\cal DC}(v)$. $\sharp$

In big boss games, the $\tau$-value coincides with the nucleolus and both are the center of the dominance core (Muto et al. \cite[p.309]{mut88}).

\begin{equation}{\label{mut88t42}}\tag{38}\mbox{}\end{equation}

Proposition \ref{mut88t42}. (Muto et al. \cite[p.309]{mut88}). If $(N,v)$ is a big boss game, then the nucleolus $\boldsymbol{\nu}(v)$ of $v$ is given by
\[\boldsymbol{\nu}(v)=\boldsymbol{\tau}(v)=\left (v(N)-\frac{1}{2}\sum_{i\in N\setminus\{1\}}
m_{i}(v),\frac{m_{2}(v)}{2},\cdots ,\frac{m_{n}(v)}{2}\right ).\ sharp\]

From Propositions \ref{mut88t41} and \ref{mut88t42}, we notice that the $\tau$-value and the nucleolus possess the additivity property in big boss games. Namely, for all $v,w\in \mbox{BBTU}(N)$, $\boldsymbol{\tau}(v+w)=\boldsymbol{\tau}(v)+\boldsymbol{\tau}(w)$ and $\boldsymbol{\nu}(v+w)=\boldsymbol{\nu}(v)+\boldsymbol{\nu}(w)$ (where $v+w\in \mbox{BBTU}(N)$, since $\mbox{BBTU}(N)$ forms a cone in $\mbox{TU}(N)$) (Muto et al. \cite[p.310]{mut88}).

In the $\tau$-value and the nucleolus, each of the weak players $2,\cdots ,n$ gets exactly half of his/her marginal contribution to the grand coalition and the rest goes to the big boss $1$ (Muto et al. \cite[p.310]{mut88}).

We analyze the following economic systems by using the obtained results.

Example. (Muto et al. \cite[p.313-314]{mut88}). (An Indivisible Good Market with One Seller and Many Buyers). We consider a market consisting of $n$ traders and two kinds of goods; an indivisible good and money. Let $N=\{1,2,\cdots ,n\}$ be a set of traders where $1$ is a seller and $2,\cdots ,n$ are buyers. The seller $1$ initially holds $w>0$ units of the indivisible good. Each of the buyers does not hold any of the good. Each trader $i$ has a utility unction $u_{i}$ measured in terms of money. Let $u_{i}(k)$ denote $i$’s utility for $k$ units of the good. As for the seller $1$, we assume $u_{1}(0)=0$. We further assume $u_{1}(k)\geq u_{1}(k-1)$ for all $k\geq 1$, and $u_{1}(k)-u_{1}(k-1)\geq u_{1}(k+1)-u_{1}(k)$ for all $k\geq 1$; the former implies the monotone nondecreasing of $u_{1}$, and the latter implies the concavity of $u_{1}$. Let $a_{k}= u_{1}(w-k+1)-u_{1}(w-k)$ for $k=1,\cdots ,w$. Then we have $0\leq a_{1}\leq a_{2}\leq\cdots\leq a_{w}$. For each buyer $i=2,\cdots ,n$, we assume $u_{i}(0)=0$ and $u_{i}(k)=h_{i}>0$ for all $k\geq 1$. This expresses that each buyer demand essentially only one unit of good. We assume for simplicity that $h_{2}\geq h_{3}\geq\cdots\geq h_{n}$ (Muto et al. \cite[p.313]{mut88}).

The characteristic function $v$ is given by, for $S\subseteq N$,

if $1\not\in S$, then $v(S)=0$;
if $S=\{1\}$, then $v(S)=\sum_{k=1}^{w}a_{k}$;
if $\{1\}\subseteq S$ with $\{1\}\neq S$, then letting $S=\{1\}\cup\{i_{1},\cdots ,i_{|S|-1}\}$ with $i_{1}<i_{2}<\cdots i_{|S|-1}$, and $\eta (S)=\max\left\{t\in {\bf N}:1\leq t\leq\min\{|S|-1,w\},h_{i_{t}}>a_{t}\right\}$, $v(S)=h_{i_{1}}+\cdots +h_{i_{\eta (S)}}+a_{\eta (S)+1}+\cdots +a_{w}$. For convenience, we let $\eta (S)=0$ in case $h_{i_{1}}\leq a_{1}$. Note that $\eta (S)$ is the units of goods traded in the coalition (Muto et al. \cite[p.313]{mut88}).

We can show that this game is a strong big boss game. Therefore, the dominance core ${\cal DC}(v)$ is given by
\begin{align*}
{\cal DC}(v) & =\{{\bf x}\in {\cal I}(v):0\leq x_{i}\leq m_{i}(v)=h_{i}-
\max\{h_{\eta (N)+1},a_{\eta (N)}\}\mbox{ for }2\leq i\leq\eta (N)\\
&\mbox{ and }x_{i}=0\mbox{ for }i\geq\eta (N)+1\}.
\end{align*}
from Theorem \ref{mut88t32}. The $\tau$-value and nucleolus are
\[\boldsymbol{\tau}(v)=\boldsymbol{\nu}(v)=\left (
v(N)-\sum_{i=2}^{\eta (N)}m_{i}(v)/2,m_{2}(v)/2,\cdots ,m_{\eta (N)}/2,0,\cdots 0\right )\]
from Propositions \ref{mut88t41} and \ref{mut88t42}. $\sharp$

Example. (Muto et al. \cite[p.315]{mut88}). (A Bankruptcy Problem with One Big Claimant). A bankcruptcy problem with a claimant set $N=\{1,2,\cdots ,n\}$ consists of $E$ and $(d_{1},\cdots ,d_{n})$; $E\geq 0$ is the estate which has to be divided among the claimanrs, and $d_{i}\geq 0$ is the amount of the claim of $i$ for $i=1,\cdots ,n$. Suppose that $d_{1}\geq\cdots\geq d_{n}$ and $E\leq\sum_{i\in N}d_{i}$. A bankcruptcy game is given by
\[v(S)=\max\left\{E-\sum_{i\in N\setminus S}d_{i},0\right\}\]
for all $S\subseteq N$. Here we consider a class of bankcruptcy games which have one big claimant. Namely, we assume $d_{1}\geq E$ and $\sum_{i\in N\setminus\{1\}}d_{i}\leq E$. We can show that it is a strong big boss game, and further, from Proposition \ref{mut88p34}, we notice that the game $v$ is convex. Noting that $m_{i}(v)=d_{i}$ for all $i\in N\setminus\{1\}$ and $v(N)=E$, we get
\[{\cal DC}(v)=\left\{{\bf x}\in {\cal I}(v):0\leq x_{i}\leq d_{i}\mbox{ for all }i\in N\setminus\{1\}\right\}\]
and
\[\boldsymbol{\tau}(v)=\boldsymbol{\nu}(v)=\left (
E-\sum_{i\in N\setminus\{1\}}d_{i}/2,d_{2}/2,\cdots ,d_{n}/2,\right )\]
from Theorem \ref{mut88t32}, Propositions \ref{mut88t41} and \ref{mut88t42}. $\sharp$

Example. (Muto et al. \cite[p.315-316]{mut88}). (A Production Economy with One Landowner and Many Peasants). We consider a production economy with one landowner and several landless peasants. Let $N=\{1,2,\cdots ,n\}$ be a set of agents where $1$ is a landowner who cannot produce anything by himself, and $2,\cdots ,n$ are landless peasants. The landowner $1$ hires peasants to cultivate his/her land. The monetary value of the corp of the land depends only on the number of the peasants hired by the landowner, and is denoted by $f(t)$ where $t$ is the number of hired peasants. The real-valued function $f:\{0,1,\cdots ,n-1\}\rightarrow\mathbb{R}$ with $f(0)=0$ is called a production function. $f$ is supposed to be monotone nondecreasing and concave, i.e., $f(t)\geq f(t-1)$ for all $t=1,\cdots ,n-1$ and $f(t+1)-f(t)\leq f(t)-f(t-1)$ for all $t=1,\cdots n-2$. The characteristic function of this production economy is given by
\[v(S)=\left\{\begin{array}{ll}
f(|S|-1) & \mbox{if $1\in S$}\\ 0 & \mbox{if $1\not\in S$}.
\end{array}\right .\]
Notice that the game is symmetric with respct to players $2,\cdots ,n$. We can show that the game is a strong big boss game. Since $m_{i}(v)=v(N)-v(N\setminus\{i\})=f(n-1)-(n-2)\equiv M$ for all $i\in N\setminus\{1\}$, we obtain
\[{\cal DC}(v)=\left\{{\bf x}\in {\cal I}(v):0\leq x_{i}\leq M\mbox{ for all }i\in N\setminus\{1\}\right\}\]
and
\[\boldsymbol{\tau}(v)=\boldsymbol{\nu}(v)=\left (f(n-1)-(n-1)M/2,M/2,\cdots ,M/2,\right )\]
from Theorem \ref{mut88t32}, Propositions \ref{mut88t41} and \ref{mut88t42}. $\sharp$

Example. (Muto et al. \cite[p.317]{mut88}). (A Market of an Informtuion Good with Symmetric Externalities). We consider a market of an information good consisting of a trader set $N=\{1,2,\cdots ,n\}$ and two kinds of goods; an information good and money. An information good is initially owened only by trader 1, and traders $2,\cdots ,n$ are demanders of the information. The monetary value of the information good, i.e., the profit gained by utilizing the information, depends only on the numbers of its possessors. Let $E(s)$ be the value of the information for each possessor when the information is shared by $s$ traders. We suppose that the value of information never increases as the number of its possessors increases, but the possessors can gain a positive profit even if the information is shared by all traders. Hence $E(1)\geq\cdots\geq E(n)>0$. Nonpossessors of the information are supposed to gain no profit. Assuming a perfect patent protection on the information, we analyze this market from the cooperative game theoretic viewpoint. If the perfect patent protection is present, the characteristic function of this market is given by
\[v(S)=\left\{\begin{array}{ll}
\max\{t\cdot E(t):1\leq t\leq |S|\} & \mbox{if $1\in S$}\\
0 & \mbox{if $1\not\in S$}\end{array}\right .\]

Noting that, for every $S\subseteq N$ with $1\in S$, $v(S)$ depends only on $|S|$, we denote $v(S)$ by $g(s)$ in case $1\in S$ and $|S|=s$. For each $s=1,2,\cdots ,n$, we let $l(s)$ be the number such that $g(s)=l(s)/E(l(s))$. For simplicity, we assume that $l(s)$ is uniquely determined for each $s=1,\cdots ,n$ (Muto et al. \cite[p.316]{mut88}).

First consider the case $l(n)\leq n-1$. In this case, we have $\mbox{TU}(N)-g(n-1)=0$. Thus we can show that the game $v$ is a strong big boss game. The dominance core ${\cal DC}(v)$ consists of the single imputation $\{(l(n)\cdot E(l(n)),0,\cdots ,0)\}$; this is the $\tau$-value and also the nucleolus from from Theorem \ref{mut88t32}, Propositions \ref{mut88t41} and \ref{mut88t42}. Hence the information is shared by $l(n)$ traders and all of the profits go to the initial possessor (Muto et al. \cite[p.316]{mut88}).

Now consider the case $l(n)=n$. We notice that $nE(n)>sE(s)$ for all $s=1,\cdots ,n-1$ since $l(n)$ is uniquely determined. We consider the Euclidean space $\mathbb{R}_{+}^{2}$ with $s$-axis and $sE(s)$-axis, i.e., the coordinates $(s,sE(s))$. Then the game $v$ is a big boss game if and only if all $sE(s)$ locate not above the line passing through the two points $(n,nE(n))$ and $(n-1,(n-1)E(n-1))$. Let $M=nE(n)-(n-1)E(n-1)$. Then we get
\[{\cal DC}(v)=\left\{{\bf x}\in {\cal I}(v):0\leq x_{i}\leq M\mbox{ for all }i\in N\setminus\{1\}\right\}\]
and
\[\boldsymbol{\tau}(v)=\boldsymbol{\nu}(v)=\left (nE(n)-(n-1)M/2,M/2,\cdots ,M/2,\right )\]
from Theorem \ref{mut88t32}, Propositions \ref{mut88t41} and \ref{mut88t42}. The information is shared by all traders and, in the $\tau$-value and the nucleolus, each of the demanders gets exactly half of its contribution to the grand coalition. An economicaly plausible example would be the case in which the marginal returns to coalition size are nondecreasing; namely
\[sE(s)-(s-1)E(s-1)\geq (s+1)E(s+1)-sE(s)\]
for all $S=2,3,\cdots n-1$. We further see that, under the above condition, the game $v$ is a strong big boss game. $\sharp$

Example. (Muto et al. \cite[p.318]{mut88}). (A Market of an Information Good Concerning a New Product). We consider a market consisting of a set $N=\{1,2,\cdots ,n\}$ of firms and two kinds of goods; an information good with respect to a manufacturing process of a new product, and money. Firm $1$ has the information, and each of the firms $2,\cdots ,n$ may start producing the product once it gets the information. The market of the new product is partitioned into $\{M_{T}\}_{\emptyset\neq T\subseteq N}$, where $M_{T}$ denotes the market into which only the firms belongings to $T$ can enter. For each $M_{T}$, the profit $r_{T}\geq 0$ gained by selling this product in $M_{T}$ is evaluated. Supposing a perfect patent protection on the information is provided, the characteristic function of this information market is given by
\[v(S)=\left\{\begin{array}{ll}
\sum_{\{T:T\cap S\neq\emptyset\}}r_{T} & \mbox{if $1\in S$}\\
0 & \mbox{if $1\not\in S$}.\end{array}\right .\]
We can show that this game is a strong big boss game (Muto et al. \cite[p.318]{mut88}).

We also see
\[m_{i}(v)=v(N)-v(N\setminus\{i\})=r_{\{i\}}\mbox{ for all }i\in N\setminus\{i\}\]
and
\[v(S)-v(S\setminus\{i\})=\sum_{\{T:T\cap S\neq\emptyset\}}r_{T}-
\sum_{\{T:T\cap (S\setminus\{i\})\neq\emptyset\}}r_{T}\geq r_{\{i\}}\]
for all $S\subseteq N$. Therefore
\[{\cal DC}(v)=\left\{{\bf x}\in {\cal I}(v):0\leq x_{i}\leq r_{\{i\}}\mbox{ for all }i\in N\setminus\{i\}\right\}\]
and
\[\boldsymbol{\tau}(v)=\boldsymbol{\nu}(v)=\left (\sum_{\{T:T\cap N\neq\emptyset\}}r_{T}-
\sum_{i\in N\setminus\{1\}}r_{\{i\}}/2,r_{\{2\}}/2,\cdots ,r_{\{n\}}/2,\right )\]
from Theorem \ref{mut88t32}, Propositions \ref{mut88t41} and \ref{mut88t42}. $\sharp$

Let $(N,v)$ be a cooperative game with ${\cal I}(v)\neq\emptyset$. For ${\bf x}\in {\cal I}(v)$, we define, for all pairs $(i,j)$ with $i\neq j$,
\[S_{ij}({\bf x})=\max_{S\in\Gamma_{ij}}\left (v(S)-\sum_{i\in S}x_{i}\right ).\]
An imputation ${\bf x}\in {\cal I}(v)$ is an element of the {\bf kernel} if, for all pairs $(i,j)$ with $i\neq j$, we have that $S_{ij}({\bf x})>S_{ji}({\bf x}$ implies $x_{j}=v(\{j\})$. Note that $v(S)-\sum_{i\in S}x_{i}$ measures the “unhappiness” of coalition $S$ with respect to imputation ${\bf x}$. Then $S_{ij}({\bf x})$ is the “maximal unhappiness” of coalition containing $i$ and not containing $j$. If $S_{ij}({\bf x})> S_{ji}({\bf x})$, then player $i$ has arguments for complaint and for demanding a larger share from player $j$. This demand will be sustained unless the allocation will leave the imputation set if player $j$’s share is diminished, i.e., if $x_{j}=v(\{j\})$. For clan games, we prove that the kernel contains exactly one element (Potters et al. \cite[p.282]{pot89}).

\begin{equation}{\label{pot89t31}}\tag{39}\mbox{}\end{equation}

Theorem \ref{pot89t31}. (Potters et al. \cite[p.282]{pot89}). If $(N,v)$ is a clan game, then the kernel consists of one point. $\sharp$

It is well known that the kernel contains the nucleolus. Therefore, the proof of Theorem \ref{pot89t31} gives an easy algorithm for calculating the nucleolus of a clan game. We suppose that $C$ is the clan of clan game $(N,v)$.

Step 0: $A_{0}=\emptyset$ and $t_{0}=v(N)/|N|$.
Step 1: $A_{1}=\{i\in N\setminus C:\frac{1}{2}m_{i}(v)\leq t_{0}\}$ and $t_{1}=(v(N)-\frac{1}{2}\sum_{i\in A_{1}}m_{i}(v))/|N\setminus A_{1}|$
$\vdots$
Step k: $A_{k}=\{i\in N\setminus C:\frac{1}{2}m_{i}(v)\leq t_{k-1}\}$ and $t_{k}=(v(N)-\frac{1}{2}\sum_{i\in A_{k}}m_{i}(v))/|N\setminus A_{k}|$.

It is easy to see that the sets $A_{k}$ do not decrease and the numbers $t_{k}$ also do not decrease. After finitely many steps (at most $n-|C|$), we find $A_{k}=A_{k+1}$ and $t_{k}=t_{k+1}$. Then the $i$th element of the nucleolus is $\frac{1}{2}m_{i}(v)$ if $i\in A_{k}=A_{k+1}$ and is $t_{k}=t_{k+1}$ if $i\not\in A_{k}$, in particular if $i\in C$ (Potters et al. \cite[p.283]{pot89}).

Corollary. (Arin and Feltkamp \cite{ari97}). Let $(N,v)$ be a veto-rich game. Then ${\cal K}(N,v)={\cal N}_{0}(v)$, where the nucleolus ${\cal N}_{0}(v)$ is defined in $(\ref{ga55})$. $\sharp$

The Nucleolus for the Games with Coalition Structure.

We recall that a constrained game is a game $(N,v,X)$, where the payoff vectors are taken in the set $X\subseteq\mathbb{R}^{N}$. The nucleolus with respect to the set $X$ is defined by
\[{\cal N}(N,v,X)=\left\{{\bf x}\in X:\boldsymbol{\theta}({\bf y})\succeq_{L}\boldsymbol{\theta}({\bf x})\mbox{ for all }{\bf y}\in X\right\}.\]
When $X\neq\emptyset$, the nucleolus consists of a single element. For a coalition structure ${\cal B}$, we define ${\cal N}(N,v,{\cal B})={\cal N}(N,v,X_{\cal B})$, where the constrained set $X_{\cal B}$ is given in (\ref{aum74eqa}) (Aumann and Dreze \cite[p.222]{aum74}).

Theorem. (Aumann and Dreze \cite[p.222]{aum74}). Let $(N,v)$ be a $0$-normalized game, and let ${\bf x}={\cal N}(N,v,{\cal B})$. Then ${\cal N}(N,v,{\cal B})|_{B_{k}}={\cal N}(B_{k},v_{\bf x}^{*},X_{k})$, where the game $v_{\bf x}^{*}$ is given in $(\ref{aum74eqc})$ and the constrained set $X_{k}$ is given in $(\ref{aum74eqb})$. $\sharp$

The game $(N,v)$ is decomposable with partition ${\cal B}$ is defined in Definition \ref{aum74d3}. Then we have the following corollary.

Corollary. (Aumann and Dreze \cite[p.224]{aum74}). Let $(N,v)$ be a $0$-normalized game and decomposable with partition ${\cal B}=\{B_{1},\cdots ,B_{p}\}$. Then we have ${\cal N}(N,v,{\cal B})=\prod_{k=1}^{p}{\cal N}(B_{k},v|_{B_{k}},X_{k})$, where $v_{B_{k}}$ is the game on $B_{k}$ defined for all $T\subseteq B_{k}$ by $v|_{B_{k}}(T)=v(T)$. $\sharp$

The Least Square Nucleolus.

\begin{equation}{\label{rui96l4}}\tag{40}\mbox{}\end{equation}

Proposition \ref{rui96l4}. (Ruiz et al. \cite[p.115]{rui96}). For any game $(N,v)$, the sume of the excesses of all coalitions is the same for all ${\bf x}\in {\cal I}^{*}(v)$ (i.e., independent of the pre-imputation ${\bf x}$).

Proof. Let ${\bf x}$ be any pre-imputation. Then we have
\[\sum_{S\subseteq N}e(S,{\bf x})=\sum_{S\subseteq N}(v(S)-\sum_{i\in S}
x_{i})=\sum_{S\subseteq N}v(S)-\sum_{S\subseteq N}\sum_{i\in S}x_{i}=\sum_{S\subseteq N}v(S)-2^{n-1}v(N)\]
since $\sum_{i\in S}x_{i}+\sum_{i\in N\setminus S}x_{i}=v(N)$ for all $S\subseteq N$, which is independent of ${\bf x}$. $\blacksquare$

Let $(N,v)$ be a game. The average excess at ${\bf x}$ is defined by
\[\bar{e}(S,{\bf x})=\frac{1}{2^{n}-1}\sum_{S\subseteq N}e(S,{\bf x}).\]
From Proposition \ref{rui96l4}, we see that the average excess is independent of the pre-imputation ${\bf x}$, i.e., $\bar{e}(S,{\bf x}_{1})=\bar{e}(S,{\bf x}_{2})$ for ${\bf x}_{1},{\bf x}_{2}\in {\cal I}^{*}(v)$. Therefore, we may simply denote $\bar{e}(S)\equiv\bar{e}(S,{\bf x})$. The variance of the excess at ${\bf x}$ is defined
\[l({\bf x})=\sum_{S\subseteq N}(e(S,{\bf x})-\bar{e}(v))^{2}.\]

\begin{equation}{\label{rui96d100}}\tag{41}\mbox{}\end{equation}

Definition \ref{rui96d100}. (Ruiz et al. \cite[p.115]{rui96}). Let $(N,v)$ be a game. The {\bf least square pre-nucleolus} of $v$ is the set ${\cal LSN}^{*}(v)$ defined by
\[{\cal LSN}^{*}(v)=\left\{{\bf x}\in {\cal I}^{*}(v):l({\bf x})\leq l({\bf y})\mbox{ for all }{\bf y}\in {\cal I}^{*}(v)\right\},\]
and the least square nucleolus of $v$ is the set ${\cal LSN}(v)$ defined by
\[{\cal LSN}(v)=\left\{{\bf x}\in {\cal I}(v):l({\bf x})\leq l({\bf y})\mbox{ for all }{\bf y}\in {\cal I}(v)\right\}.\sharp\]

We see that if ${\bf x}^{*}\in {\cal LSN}^{*}(v)$, then ${\bf x}^{*}$ is a solution of the following problem:
\begin{eqnarray*}
\mbox{(MP1)} & \min & \sum_{S\subseteq N}(e(S,{\bf x})-\bar{e}(v))^{2}\\
& \mbox{subject to} & \sum_{i\in N}x_{i}=v(N),
\end{eqnarray*}
and if ${\bf x}^{*}\in {\cal LSN}(v)$, then ${\bf x}^{*}$ is a solution of the following problem:
\begin{eqnarray*}
\mbox{(MP2)} & \min & \sum_{S\subseteq N}(e(S,{\bf x})-\bar{e}(v))^{2}\\
& \mbox{subject to} & \sum_{i\in N}x_{i}=v(N)\mbox{ and }x_{i}\geq v(i)\mbox{ for all }i\in N.
\end{eqnarray*}

For any $k\in\mathbb{R}$, we have
\begin{equation}{\label{riu96eq1}}\tag{42}
\sum_{S\subseteq N}(e(S,{\bf x})-k)^{2}=\sum_{S\subseteq N}e(S,{\bf x})^{2}+(2^{n}-1)k^{2}-2k\sum_{S\subseteq N}e(S,{\bf x}).
\end{equation}
We see that the following two problems
\begin{eqnarray*}
\mbox{(MP3)} & \min & \sum_{S\subseteq N}e(S,{\bf x})^{2}=\sum_{S\subseteq N}\left (v(S)-\sum_{i\in S}x_{i}\right )^{2}\\
& \mbox{subject to} & \sum_{i\in N}x_{i}=v(N),
\end{eqnarray*}
and
\begin{eqnarray*}
\mbox{(MP4)} & \min & \sum_{S\subseteq N}e(S,{\bf x})^{2}=\sum_{S\subseteq N}\left (v(S)-\sum_{i\in S}x_{i}\right )^{2}\\
& \mbox{subject to} & \sum_{i\in N}x_{i}=v(N)\mbox{ and }x_{i}\geq v(i)\mbox{ for all }i\in N.
\end{eqnarray*}
have the same optimal solutions as problems (MP1) and (MP2), respectively, since the last summation in (\ref{riu96eq1}) is independent of ${\bf x}$ so that the resulting objective functions differ by a constant. These formulations provide another two interesting interpretations of both least square pre-nucleolus and least square nucleolus of a game. For problem (MP3), it is the pre-imputation for which the excess vector is closest to vector zero; and, for problem (MP4), it is the imputation whose associated additive game is closest to a game $v$
(Ruiz et al. \cite[p.117]{rui96}).

Theorem. (Ruiz et al. \cite[p.116]{rui96}). For any game $(N,v)$, we have the following properties.

(i) The least square pre-nucleolus of $v$ consists of single point $\{{\bf x}^{*}\}$, which is given by
\begin{equation}{\label{rui96eq2}}\tag{43}
x_{i}^{*}=\frac{v(N)}{n}+\frac{1}{n\cdot2^{n-2}}\cdot\left [n\cdot a_{i}(v)-\sum_{j\in N}a_{j}(v)\right ]
\end{equation}
for all $i\in N$, where $a_{i}(v)=\sum_{\{S:i\in S}\}v(S)$.

(ii) If ${\cal I}(v)\neq\emptyset$, then the least square nucleolus of $v$ consists of single point. $\sharp$

Formula (\ref{rui96eq2}) can be rewritten as
\[x_{i}^{*}=\frac{v(N)}{n}+\frac{1}{n\cdot2^{n-2}}\cdot\left [
\sum_{\{S:i\in S\}}n\cdot v(S)-\sum_{S\subseteq N}|S|\cdot v(S)\right ],\]
or, equivalently,
\[x_{i}^{*}=\frac{v(N)}{n}+\frac{1}{n\cdot2^{n-2}}\cdot\left [
\sum_{\{S:i\in S\}}(n-|S|)\cdot v(S)-\sum_{\{S:i\not\in S\}}|S|\cdot v(S)\right ]\]
(Ruiz et al. \cite[p.118]{rui96}).

For any game $v$ and any vector ${\bf x}$, let
\[\mu_{i}({\bf x})=\sum_{\{S:i\in S\}}\left [v(S)-\sum_{i\in S}x_{i}\right ].\]

Proposition. (Ruiz et al. \cite[p.130]{rui96}). For any game $v$, an imputation ${\bf x}$ is the least square nucleolus of $v$ if and only if
\[x_{j}>v(\{j\})\mbox{ implies }\mu_{j}({\bf x})=\max_{i=1,\cdots ,n}\mu_{i}({\bf x})\]
for all $j\in N$. $\sharp$

Corollary. (Ruiz et al. \cite[p.131]{rui96}). An imputation ${\bf x}$ is the least square nucleolus of a game if and only if $\mu_{j}({\bf x})<\mu_{i}({\bf x})$ implies $x_{j}=v(\{j\})$. $\sharp$

We define the average surplus of player $i$ against $j$ at ${\bf x}\in {\cal I}^{*}(v)$ as
\[\sigma_{ij}({\bf x})=\frac{1}{2^{n-2}}\sum_{\{S:i\in S,j\not\in S\}}\left [v(S)-\sum_{i\in S}x_{i}\right ].\]
This concept is similar to the usual surplus, but now players measure their relative strength from average instead of maximal expectation (Ruiz et al. \cite[p.120]{rui96}).

Definition. (Ruiz et al. \cite[p.120]{rui96}). Given a game $(N,v)$, the average pre-kernel and the average kernel of $v$ are, respectively, the sets
\[{\cal AK}^{*}(v)=\left\{{\bf x}\in {\cal I}^{*}(v):\sigma_{ij}({\bf x})=
\sigma_{ji}({\bf x})\mbox{ for }i,j\in N\mbox{ with }i\neq j\right\}.\]
and
\[{\cal AK}(v)=\left\{{\bf x}\in {\cal I}(v):(\sigma_{ij}({\bf x})-
\sigma_{ji}({\bf x}))\cdot(x_{j}-v(\{j\}))\leq 0\mbox{ for }i,j\in N\mbox{ with }i\neq j\right\}. \sharp\]

Proposition. (Ruiz et al. \cite[p.120]{rui96}). For any game $(N,v)$, the lease square pre-nucleolus is the unique point of the average pre-kernel. $\sharp$

Proposition. (Ruiz et al. \cite[p.131]{rui96}). For any game $v$ with ${\cal I}(v)\neq\emptyset$, the least square nucleolus is the unique point of the average kernel. $\sharp$

We regard the least square pre-nucleolus as the function $\boldsymbol{\psi}:\mbox{TU}(N)\rightarrow\mathbb{R}^{n}$, i.e., $\psi_{i}(v)$ is determined by (\ref{rui96eq2}). Let us recall $a_{i}(v)=\sum_{\{S:i\in S\}}v(S)$, from (\ref{rui96eq2}), we have the following monotonicity property:
\[a_{i}(v)\geq a_{j}(v)\mbox{ implies }\psi_{i}(v)\geq\psi_{j}(v).\]
Equivalently, we have the following statements:
\[\sum_{\{S:i\in S,j\not\in S\}}v(S)\geq\sum_{\{S:j\in S,i\not\in S\}}v(S)\mbox{ implies }\psi_{i}(v)\geq\psi_{j}(v),\]
or even
\[\sum_{\{S:i\not S,j\not\in S\}}(v(S\cup\{i\})-v(S))\geq
\sum_{\{S:i\not S,j\not\in S\}}(v(S\cup\{j\})-v(S))\mbox{ implies }\psi_{i}(v)\geq\psi_{j}(v),\]
which gives a new interpretation: if player $i$’s marginal contribution (aggregated or on the average) to the coalition not containing $i$ nor $j$ is not less than that of player $j$, then $i$ should nor receive less than $j$. So we call this property as {\bf average marginal contribution monotonicity (Ruiz et al. \cite[p.121]{rui96}).

Proposition. (Ruiz et al. \cite[p.121]{rui96}). A solution $\boldsymbol{\psi}:\mbox{TU}(N)\rightarrow\mathbb{R}^{n}$ verifies efficiency, linearity and average marginal contribution monotonicity if and only if there exists $\beta\geq 0$ satisfying
\[\psi_{i}(v)=\frac{v(N)}{n}+\beta\cdot\left [n\cdot a_{i}(v)-\sum_{j\in N}a_{j}(v)\right ].\sharp\]

Theorem. (Ruiz et al. \cite[p.121]{rui96}). The least square pre-nucleolus is the unique value on $\mbox{TU}(N)$ which verifies efficiency, linearity, inessential game (i.e., for any additive game $v$ and any $i$, $\psi_{i}(v)=v(i)$) and average marginal contribution
monotonicity. $\sharp$

A function of coalitional weights (weight function, for short) on $N$ is a map which associates with every nonempty coalition $S$ a real number $m^{(n)}(S)$. Depending on the context, $m^{(n)}(S)$ can be interpreted as the probability of coalition $S$ forming, or the sensitivity to not receiving a satisfactory payoff, or the ability of the coalition in the baragining process, or the stability degree of coalition $S$. In this work, we restrict the attention to positive weight functions (we cannot find a reasonable interpretation for negative coalitional weights), namely, such that $m^{(n)}(S)\geq 0$ for all $S\subseteq N$ with $m^{(n)}(S)>0$ for some $S\neq N$, and symmetric in the sense of assigning the same weight to coalitions of the same size. Let $s$ be the size of $S$, i.e., $s=|S|$. It can be easily checked that in order to obtain symmetric solutions with this approach one has to use symmetric weight functions. So we can write $m^{(n)}(s)$ instead of $m^{(n)}(S)$. In fact, we will often simply write $m$ or $m(s)$ if $n$ is clear from the context. In what follows weight functions are assumed to be positive and symmetric, unless otherwise specified (Ruiz et al. \cite[p.112]{rui98}).

For each weight function $m$ let us consider the following problem
\begin{eqnarray*}
\mbox{(MP5)} & \min & \sum_{S\subseteq N}m(s)\cdot (e(S,{\bf x})-\bar{e}(v))^{2}\\
& \mbox{subject to} & \sum_{i\in N}x_{i}=v(N).
\end{eqnarray*}

Proposition. (Ruiz et al. \cite[p.113]{rui98}). For any weight function $m:2^{N}\setminus\emptyset\rightarrow\mathbb{R}$ and for any game $v$, there exists a unique solution ${\bf x}^{(m)}$ of problem $($MP5$)$ and it is given by
\begin{equation}{\label{rui98eq1}}\tag{44}
x_{i}^{(m)}=\frac{v(N)}{n}+\frac{1}{\alpha n}\cdot\left (na_{i}^{(m)}(v)-\sum_{j=1}^{n}a_{j}^{(m)}(v)\right )
\end{equation}
for all $i\in N$, where
\[a_{i}^{(m)}(v)=\sum_{\{S:i\in S\}}m(s)\cdot v(S)\mbox{ and }
\alpha =\sum_{s=1}^{n-1}m(s)\cdot\left (\begin{array}{c}n-2\\s-1\end{array}\right ).\]

Proof. The Lagrangian of (MP5) is
\[L({\bf x},\lambda )=\sum_{S\subseteq N}m(s)\cdot(v(S)-x(S)-\bar{e}(v))^{2}
+\lambda\cdot\left (\sum_{i\in N}x_{i}-v(N)\right ).\]
Besides the constraint equation, the Lagrange conditions are then
\[L_{x_{i}}({\bf x},\lambda )=-2\sum_{\{S:i\in S\}}m(s)\cdot(v(S)-x(S)-\bar{e}(v))+\lambda =0.\]
for $i\in N$. A simple calculation solves this linear system and shows that the unique point ${\bf x}^{(m)}$ satisfying thees conditions is given by (\ref{rui98eq1}). On the other hand, the objective function is large outside a big enough compact set within the feasible region including this point in which a minimum must be attained. So the optimal solution of (MP5) must be the obtained point. $\blacksquare$

Note that formula (\ref{rui98eq1}) does not depend on $\bar{e}(v)$. The reason is that the optimal solution of (MP5) remains unchanged if we substitute any constant $k$ for $\bar{e}(v)$ in the objective function. To see this, we can write, for all $k\in\mathbb{R}$,
\[\sum_{S\subseteq N}m(s)(e(S,{\bf x})-k)^{2}=\sum_{S\subseteq N}m(s)
e^{2}(S,{\bf x})+\sum_{S\subseteq N}m(s)k^{2}-2k\sum_{S\subseteq N}m(s)e(S,{\bf x}).\]
But the last summation is constant over the pre-imputation set, since
\[\sum_{S\subseteq N}m(s)e(S,{\bf x})=\sum_{S\subseteq N}m(s)(v(S)-x(S))=
\sum_{S\subseteq N}m(s)v(S)-\sum_{S\subseteq N}m(s)x(S),\]
and, if ${\bf x}\in {\cal I}^{*}(v)$, it follows that
\[\sum_{S\subseteq N}m(s)x(S)=\sum_{s=1}^{n}m(s)\cdot\sum_{\{T:|T|=s\}}x(T)
=\sum_{s=1}^{n}m(s)\left (\begin{array}{c} n-1\\s-1\end{array}\right )v(N).\]
Therefore, the resulting objective function differs from that of (MP5) on a constant on the feasible set. In particular, for $k=0$,
we conclude that the optimal solution of (MP5) is that of problem,
\begin{eqnarray*}
& \min & \sum_{S\subseteq N}m(s)\cdot(v(S)-x(S))^{2}\\
& \mbox{subject to} & \sum_{i\in N}x_{i}=v(N).
\end{eqnarray*}
(Ruiz et al. \cite[p.114]{rui98}).

Note the weight of the grand coalition $m(n)$ is irrelevant, because, for ${\bf x}\in {\cal I}^{*}(v)$, it is $e(N,{\bf x})=0$. Therefore, in this context, we could represent any weight function as a vector ${\bf m}=(m(1),\cdots ,m(n-1))\in\mathbb{R}_{+}^{n-1}$ with only $n-1$ components. Note likewise, that the solution of this problem remains unchanged if we replace the vector ${\bf m}$ with the vector $k{\bf m}$ whenever $k>0$ (Ruiz et al. \cite[p.114]{rui98}).

Definition. (Ruiz et al. \cite[p.114]{rui98}). A value $\boldsymbol{\psi}:\mbox{TU}(N)\rightarrow\mathbb{R}^{n}$ belongs to the least square family when there exists a weight function $m$ such that $\boldsymbol{\psi}(v)$ is the solution of (MP5) for all $v\in\mbox{TU}(N)$. We will denote $\boldsymbol{\psi}^{(m)}(v)$ to the solution of the least square family associated with $m$. $\sharp$

It will be useful to rewrite formula (\ref{rui98eq1}). A restatement of this formula is
\[\psi_{i}^{(m)}=\frac{v(N)}{n}+\frac{1}{n\alpha}\cdot\left (
\sum_{\{S:i\in S\}}(n-s)\cdot m(s)v(S)-\sum_{\{S:i\not\in S\}}s\cdot m(s)v(S)\right ).\]
Now denoting
\[\rho_{s}=\frac{s(n-s)}{n}\cdot\frac{m(s)}{\alpha},\]
it can be rewritten as
\begin{equation}{\label{rui98eq3}}\tag{45}
\psi_{i}^{(m)}=\frac{v(N)}{n}+\sum_{\{S:i\in S\neq N\}}\rho_{s}\cdot
\frac{v(S)}{s}-\sum_{\{S:i\not\in S\}}\rho_{s}\cdot\frac{v(S)}{n-s}.
\end{equation}
(Ruiz et al. \cite[p.114]{rui98}).

Proposition. (Ruiz et al. \cite[p.115]{rui98}). Any value of the least square family $\boldsymbol{\psi}^{(m)}:\mbox{TU}(N)\rightarrow\mathbb{R}^{n}$ verifies the following properties.

(i) Linearity $($and therefore continuity$)$.

(ii) Inssential game: for any additive game $v$ and any $i\in N$, $\psi_{i}^{(m)}(v)=v(i)$.

(iii) Strategic equivalence: $\boldsymbol{\psi}^{(m)}(\alpha v+\boldsymbol{\beta})=\alpha\cdot\boldsymbol{\psi}^{(m)}(v)+\boldsymbol{\beta}$ for all $v\in \mbox{TU}(N)$, all $\alpha\in\mathbb{R}$, and all $\boldsymbol{\beta}\in\mathbb{R}^{n}$.

(iv) Anonymity: for any permutation $\pi$ on $N$, all $v\in \mbox{TU}(N)$, and all $i\in N$, $\psi_{\pi (i)}^{(m)}(\pi (v))=\psi_{i}^{(m)}(v)$.

(v) Coalitional monotonicity: for all $v,w\in \mbox{TU}(N)$ satisfying $v(S)>w(S)$ for some $S$ and $v(T)=w(T)$ for any $T\neq S$, it is $\psi_{i}^{(m)}(v)\geq \psi_{i}^{(m)}(w)$ for all $i\in S$.

(vi) Is standard for two-person game: that is, for any two-person game, $\psi_{i}^{(m)}(v)=v(i)+\frac{1}{2}\cdot\left (v(\{i,j\})-v(i)-v(\{j\})\right )$. $\sharp$

Notice any $\boldsymbol{\psi}^{(m)}$ value verifies symmetry (also called equal treatment, i.e., players whose marginal contribution to any coalition is the same receive the same), for anonymity implies symmetry. It can also be easily established from formula (\ref{rui98eq3}) that an $\boldsymbol{\psi}^{(m)}$ verifies duality (i.e., for any game $v$ and its dual $v^{*}(S)\equiv v(N)-v(N\setminus S)$, it is $\boldsymbol{\psi}^{(m)}(v)=\boldsymbol{\psi}^{(m)}(v^{*})$) if and only if its associated weight function $m$ verifies the condition $m(s)=m(n-s)$ for all $s$ and $1\leq s\leq n-1$. Note also that in general these values do not satisfy individual rationality. One can define analogously individual rational least square values restricting the minimization problem to the imputation set. But the price of assuring individual rationality is losing linearity (Ruiz et al. \cite[p.115]{rui98}).

Let us recall
\[\alpha =\sum_{s-1}^{n-1}m(s)\cdot\left (\begin{array}{c}
n-2\\s-1\end{array}\right ).\]
We define
\[\sigma_{ij}^{(m)}({\bf x},N,v)=\sum_{\{S:i\in S,j\not\in S\}}\frac{m(s)}{\alpha}\cdot(v(S)-x(S)).\]

\begin{equation}{\label{rui98p7}}\tag{46}\mbox{}\end{equation}

Proposition \ref{rui98p7}. (Ruiz et al. \cite[p.115]{rui98}). For any game $v\in \mbox{TU}(N)$ and any weight function $m$, $\boldsymbol{\psi}^{(m)}(v)$ is the unique pre-imputation that verifies
\[\sigma_{ij}^{(m)}({\bf x},N,v)=\sigma_{ji}^{(m)}({\bf x},N,v)\]
for all $i,j\in N$ and $i\neq j$. $\sharp$

Note $\sigma_{ij}^{(m)}({\bf x},N,v)$ is the $m$-weighted average of the excesses of coalitions containing player $i$ but not containing player $j$. It can be interpeted as the expected surplus of player $i$ over player $j$ when the probability of coalition $S\setminus\{i\}\subseteq N\setminus\{i\}$ joining player $i$ is induced by $m$. Simply take the weights of coalitions containing $i$ but not containing $j$ and normalize them to add to $1$. So Proposition \ref{rui98p7} provides an alernative definition of each value of the least square family in a prekernel-like way, including the Shapley value (Ruiz et al. \cite[p.116]{rui98}).

\begin{equation}{\label{rui98t8}}\tag{47}\mbox{}\end{equation}

Theorem \ref{rui98t8}. (Ruiz et al. \cite[p.116]{rui98}). A value $\boldsymbol{\psi}:\mbox{TU}(N)\rightarrow\mathbb{R}^{n}$ verifies efficiency, linearity, symmetry, inessential game, and coalitional monotonicity if and only if it belongs to the least square family. $\sharp$

Definition. (Ruiz et al. \cite[p.119]{rui98}). A semivalue on $\mbox{TU}(N)$ is a function $\boldsymbol{\psi}:\mbox{TU}(N)\rightarrow\mathbb{R}^{n}$ which verifies linearity, anonymity, positivity and inessential game. $\sharp$

Dubey et al. \cite{dub81} proved that $\boldsymbol{\psi}$ is a semivalue if and only if, for all $v\in \mbox{TU}(N)$, $\boldsymbol{\psi}(v)$ is of the form,
\begin{equation}{\label{rui98eq7}}\tag{48}
\psi_{i}(v)=\sum_{S\subseteq N\setminus\{i\}}p^{S}\cdot\left (v(S\cup\{i\})-v(S)\right )
\end{equation}
for all $i\in N$, where ${\bf p}=(p_{0},p_{1},\cdots ,p_{n-1})$ is a vector such that
\[\sum_{s=0}^{n-1}\left (\begin{array}{c} n-1\\ s\end{array}\right )
\mbox{ and }p^{S}\geq 0\mbox{ for all }s\in\{0,1,\cdots ,n-1\}.\]
That is, $\mathbb{P}$ defined by $\mathbb{P}(S)=p^{S}$ for all $S\subset N$ and $S\neq N$, is a probability distribution over the coalitions not containing player $i$ which assigns the same probability to coalitions of the same size. Thus, a semivalue assigns to each player his/her expected marginal contribution according to the probability distribution $\mathbb{P}$. In general, semivalues do not satisfy efficiency. In fact, the Shapley value is the unique efficient semivalue, and this is a crucial requirement if one is looking for a solution that can be accepted by all the players. This motivates an “efficient normalization” of any semivalue (Ruiz et al. \cite[p.120]{rui98}).

Definition. (Ruiz et al. \cite[p.120]{rui98}). The {\bf additive efficient normalization} of a semivalue $\boldsymbol{\psi}$ in $\mbox{TU}(N)$ is given by
\[\bar{\boldsymbol{\psi}}(v)=\boldsymbol{\psi}(v)+\frac{1}{n}\left (v(N)-\sum_{i\in N}\psi_{i}(v)\right ). \sharp\]

That is, $\bar{\boldsymbol{\psi}}$ assigns to each player his/her expected marginal contribution $\psi_{i}(v)$ and $\bar{\boldsymbol{\psi}}$ divides the excedent (positive or negative) equally between all players (Ruiz et al. \cite[p.120]{rui98}).

\begin{equation}{\label{rui98t12}}\tag{49}\mbox{}\end{equation}

Theorem \ref{rui98t12}. (Ruiz et al. \cite[p.120]{rui98}). If $\boldsymbol{\psi}$ is a semivalue on $\mbox{TU}(N)$, then its additive efficient normalization $\bar{\boldsymbol{\psi}}$ belongs to the least square family. Furthermore, if ${\bf p}=(p_{0},p_{1},\cdots ,p_{n-1})$ is the weight vector of the semivalue $\boldsymbol{\psi}$, then the weight function of the $\boldsymbol{\psi}^{(m)}$ value such that $\bar{\boldsymbol{\psi}}=\boldsymbol{\psi}^{(m)}$ is given
$($up to a positive proportional factor$)$ by $m(s)=p_{s-1}+p^{S}$ for all $s\in\{1,\cdots ,n-1\}$. $\sharp$

It is immediate to prove that an $\boldsymbol{\psi}^{(m)}$ value is the additive efficient normalization of some semivalue if and only if the linear system $m(s)=p_{s-1}+p^{S}$ for all $s\in\{1,\cdots ,n-1\}$ with $m$ normalized so that $\alpha =1$, has a nonnegative solution. This is not always the case, so the converse of the first part of Theorem \ref{rui98t12} is not true. That is, for some weight functions $m$, there is no semivalue on $\mbox{TU}(N)$ whose additive efficient normalization coincides with the $\boldsymbol{\psi}^{(m)}$ value. In other words, not all the values of the least square family can be defined alternatively as the additive normalization of a semivalue. However, we will see later that this result holds for a very interesting subfamily of the least square family.

We have seen before that the Shapley value belongs to the least square family. Then, from Theorem \ref{rui98t12}, it follows that the weight function which leads to the Shapley value is given by
\[m^{Sh}(s)=p_{s-1}+p^{S}=\frac{1}{n-1}\cdot\left (\begin{array}{c}n-2\\s-1\end{array}\right )^{-1}.\]
Note for these weights $\alpha =1$. Then, according to Proposition \ref{rui98p7}, the corresponding $m^{Sh}$-weighted average
surpluses that the Shapley value equalizes are
\[\sigma_{ij}^{Sh}({\bf x},N,v)=\sum_{\{S:i\in S,j\not\in S\}}\frac{1}{n-1}
\cdot\left (\begin{array}{c} n-2\\s-1\end{array}\right )^{-1}\cdot (v(S)-x(S)).\]
That is, $\sigma_{ij}^{Sh}({\bf x},N,v)$ can be interpreted as the expected surplus of player $i$ against $j$ if all the coalitions of the same size not containing neither $i$ nor $j$ have the same probability of joining $i$, and all the sizes are equally probable.

In general, for any probability measure $\xi$ on $[0,1]$, one can define a semivalue $\boldsymbol{\psi}^{\xi}$ in $\mbox{TU}(N)$ associated with $\xi$ using formula (\ref{rui98eq7}) with weights given by (Dubey et al. \cite{dub81})
\[p^{n,S}=\int_{0}^{1}t^{s}(1-t)^{n-s-1}d\xi (t),\]
where $p^{n,S}$ denotes the weight $p^{S}$ when there are $n$ players. Then, by Theorem \ref{rui98t12}, the additive efficient normalization of $\boldsymbol{\psi}^{\xi}$ in $\mbox{TU}(N)$ is the $\boldsymbol{\psi}^{(m)}$ value with the weight function given by
\[m^{(n)}(s)=p_{s-1}^{(n)}+p^{n,S}=\int_{0}^{1}t^{s-1}(1-t)^{n-s-1}d\xi (t).\]
In the sequel, we are going to see that given a probability measure $\xi$, if for any number of players $n$ we compute the weights $m(s)$ according to the former expression, the corresponding $\boldsymbol{\psi}^{(m)}$ value verifies a condition of consistency.

We will show the consistency of an interesting subfamily of the least square family for a suitable reduced game concept. Note that in the preceding discussions all concepts and results concern a fixed number of players. But now, in order to deal with consistency, a value $\boldsymbol{\psi}$ has to be understood as defined for any number of players, that is, as a family of functions $\boldsymbol{\psi}=\{\boldsymbol{\psi}^{(n)}:\mbox{TU}(N)\rightarrow\mathbb{R}^{n}:n=1,2,\cdots\}$. Accordingly, a value that for any number of players belongs to the least square family must be asociated with a family of weight functions $m=\{m^{(n)}:2^{N}\setminus\emptyset\rightarrow\mathbb{R}:n=1,2,\cdots\}$, one for each possible size of the grand coalition. Consequently, a weight function $m$ will be understood in this sense and we will use the notation $m_{s}^{(n)}$ instead of $m^{(n)}(s)$ to denote the weight of any coalition of size $s<n$ in an $n$-person game. The consistenct principle is a concept associated with a notion of “reduced game”. Informally speaking a value is consistent if, for any game $v\in \mbox{TU}(N)$ and any coalition $S\subseteq N$, $S\neq N$, it prescribes, for all players in $S$, the same payoff in the original game and in the reduced game.

A value $\boldsymbol{\psi}$ is {\bf consistent} with respect to a reduced game (RD) concept, if for all $n=1,2,\cdots$, all $v\in \mbox{TU}(N)$ and all nonempty $S\subseteq N$, $S\neq N$, $\psi_{i}^{(n)}(v)=\psi_{i}^{(s)}(v_{\boldsymbol{\psi}(v),S})$ for all $i\in S$, where $v_{\boldsymbol{\psi}(v),S}$ denotes the reduced game of $S$ at payoff vector $\boldsymbol{\psi}^{(n)}(v)$. We will show that for certain weight functions $m$, the corresponding $\boldsymbol{\psi}^{(m)}$ value is consistent with respect to a reduced game concept which depends on the weight function $m$.

Let $m$ be a weight function, a game $v\in \mbox{TU}(N)$ and ${\bf x}\in\mathbb{R}^{n}$, then the $m$-reduced game of coalition $S\subseteq N$, $S\neq\emptyset$, at ${\bf x}$, is the game $(S,v^{(m)}_{(S,{\bf x})})\in G_{S}$, defined by
\[v_{(S,{\bf x})}^{(m)}(T)=\left\{\begin{array}{ll}
0 & \mbox{if $T=\emptyset$}\\ v(N)-x(N\setminus S) & \mbox{if $T=S$}\\
{\displaystyle \sum_{Q\subseteq N\setminus S}\frac{m_{t+q}^{(n)}}{K_{s}^{(n)}(t)}\cdot (v(T\cup Q)-x(Q))} (q=|Q|) & \mbox{if $T\subset S$, $T\neq S$, and $T\neq\emptyset$}
\end{array}\right .\]
where
\[K_{s}^{(n)}(t)=\sum_{q=0}^{n-s}\left (\begin{array}{c}n-s\\ q\end{array}\right )\cdot m_{t+q}^{(n)}\]
and $v_{(S,{\bf x})}^{(m)}(T)=0$, for all $T\subseteq S,T\neq S, T\neq\emptyset$, if $K_{s}^{(n)}(t)=0$. $v_{(S,{\bf x})}^{(m)}(T)$, $\emptyset\neq T\subseteq S,T\neq S$, is the $m$-weighted average of what coalition $T$ can obtain with the cooperation of coalitions $Q\subseteq N \setminus S$ (in the quoted definition it was simply the arithmetic average). Note the numbers $m_{t+q}^{(n)}/K_{s}^{(n)}(t)$ define a probability distribution over the coalitions in $N\setminus S$ (all of them are positive and they add to one), so in this new definition we weaken the assumption of all the coalitions in $N\setminus S$ having the same probability of joining coalition $T$. On the hand, if we interpret $m_{t+q}^{(n)}$ as the probability of coalition $T\cup Q$ forming, then $m_{t+q}^{(n)}/K_{s}^{(n)}(t)$ could be interpreted as the probability that $T\cup Q$ will form, under the condition that coalition $T$ was formed already. In this way, we may interpret $v_{(S,{\bf x})}^{(m)}(T)$ as the expected worth of coalition $T$ according to the probability distribution induced by $m$. (In fact, we simply take the weights corresponding to $T\cup Q$ and normalization them to add $1$).

\begin{equation}{\label{rui98d17}}\tag{50}\mbox{}\end{equation}

Definition \ref{rui98d17}. A weight function $m$ is consistent when the weights, normalized according to $\sum_{s=1}^{n-1}\left (\begin{array}{c}n-2\\s-1\end{array}\right )=1$, verify the relation $m_{s}^{(n)}=m_{s}^{(n+1)}+m_{s+1}^{(n+1)}$ for all $n$ and for all $s, 1\leq s<n$. $\sharp$

We will later give an alternative definition of consistent weight functions. The following theorem justifies this definition.

\begin{equation}{\label{rui98t18}}\tag{51}\mbox{}\end{equation}

Theorem \ref{rui98t18}. (Ruiz et al. \cite{rui98}). The value of the least square family associated with the weight function $m$ is $m$-consistent $($i.e., consistent with respect to the $m$-reduced game $v_{(S,{\bf x})}^{(m)})$ if and only if $m$ is a consistent weight function. $\sharp$

It is immediately to check that the weight function $m^{Sh}$ associated with the Shapley value is consistent. Therefore the Shapley value is consistent with respect to the $m$-reduced game.

\begin{equation}{\label{rui98t20}}\tag{52}\mbox{}\end{equation}

Proposition \ref{rui98t20}. (Ruiz et al. \cite{rui98}). For each consistent weight function $m$, the corresponding $\boldsymbol{\psi}^{(m)}$ value is the unique value which is standard for two-person games and $m$-consistent. $\sharp$

Corollary. (Ruiz et al. \cite{rui98}). For each consistent weight function $m$, the corresponding $\boldsymbol{\psi}^{(m)}$ value is the unique value which verifies anonymity, strategic equivalence, and $m$-consistency. $\sharp$

Corollary. (Ruiz et al. \cite{rui98}). For each consistent weight function $m$, the corresponding $LS^{m}$ value is the unique value which is standard for two-person games and verifies the converse reduced game property with respect to the $m$-reduced game. $\sharp$

\begin{equation}{\label{rui98t23}}\tag{53}\mbox{}\end{equation}

Theorem \ref{rui98t23}. (Ruiz et al. \cite{rui98}). A normalized (as in Definition \ref{rui98d17}) weight function $m$ is consistent if and only if there exists a probability measure $\xi$ in $[0,1]$ such that, for any number of players $n$, and any size $s<n$, it is
\begin{equation}{\label{rui98eq9}}\tag{54}
m_{s}^{(m)}=\int_{0}^{1}t^{s-1}(1-t)^{n-s-1}d\xi (t). \sharp
\end{equation}

Recall that for any probability measure $\xi$ on $[0,1]$ one can define a semivalue for any number of players $\boldsymbol{\psi}^{\xi}= \left\{\boldsymbol{\psi}^{\xi (n)}:\mbox{TU}(N)\rightarrow\mathbb{R}^{n}:n=1,2,\cdots\right\}$ following Dubey et al. \cite{dub81},
\[\psi_{i}^{\xi (n)}(v)=\sum_{S\subseteq N\setminus\{i\}}p^{n,S}\cdot (v(S\cup\{i\})-v(S)),\]
where
\[p^{n,S}=\int_{0}^{1}t^{s}(1-t)^{n-s-1}d\xi (t).\]
On the other hand, by Theorem \ref{rui98t23}, any consistent $\boldsymbol{\psi}^{(m)}$ value is associated with some probability measure $\xi$ in $[0,1]$. Denoting $LS_{N}^{\xi}$ to the $\boldsymbol{\psi}^{(m)}$ value on $\mbox{TU}(N)$ associated (for any number of players $n$) with $\xi$.

\begin{equation}{\label{rui98t24}}\tag{55}\mbox{}\end{equation}

Theorem \ref{rui98t24}. (Ruiz et al. \cite{rui98}). Any consistent least square value is, for all $n\geq 1$, the additive efficient normalization of some semivalue on $\mbox{TU}(N)$. Moreover, for any probability measure $\xi$ in $[0,1]$, and for all $n\geq 1$, $LS_{N}^{\xi}$ is the additive efficient normalization of $\boldsymbol{\psi}^{\xi (n)}$. Conversely, for any probability measure $\xi$, the value $\bar{\boldsymbol{\psi}}^{\xi}=\{\bar{\boldsymbol{\psi}}^{\xi (n)}:n=1,2,\cdots\}$, where each $\bar{\boldsymbol{\psi}}^{\xi (n)}$ is the aditive efficient normalization of the semivalue $\boldsymbol{\psi}^{\xi (n)}$, is a consistent least square value. $\sharp$

So, each $m$-consistent least square value can be alternatively defined as the additive efficient normalization of the semivalue associated with the same probability measure $\xi$. To be more precise we want to remark that the measure has ot be the same for any number of players $n$. One can define an least square value using formula (\ref{rui98eq9}) to obtain the weights $m_{s}^{(n)}$ but using a different measure $\{\xi^{(n)}\}$ for each number of players $n$. Such an least square value would be, for any $n$, the additive efficient normalization of the semivalue in $\mbox{TU}(N)$ associated with $\xi^{(n)}$. However it is clear that such an least square value would not be $m$-consistent since such an $m$ would not be consistent.

General Nucleolus.

The object of study is a class $\Omega$ of pairs $(\Pi, F)$. In each pair, $\Pi$ is a topological space and $F=\{F_{j}\}_{j\in M}$ is a finite set of real continuous functions on $\Pi$. This setup has many applications. We give two examples which should be sufficient for motivation.

\begin{equation}{\label{mas92ex21}}\tag{56}\mbox{}\end{equation}

Example \ref{mas92ex21}. (Maschler et al. \cite[p.88]{mas92}). $\Omega$ is derived from the class of all TU games $(N,v)$ on finite sets of players. For each game, $\Pi$ is the set of pre-imputations of the game and $F=\{F^{S}\}_{S\subseteq N}$, where the various $F^{S}$ are the excess functions given by $F^{S}({\bf x})=v(S)-\sum_{i\in S}x_{i}$. $\sharp$

Example. (Maschler et al. \cite[p.88]{mas92}). $\Omega$ is a class of potential “decision spaces”. In each particular case a decision maker has to make a decision ${\bf x}$ which is a point in a “decision space” $\Pi$. Any such choice may affect a set of cities $M$. The effect can be measured in monetary terms. $F_{j}({\bf x})$ is the damage caused to city $j$ if the decision ${\bf x}$ is taken. $\sharp$

The central concepts are the least core and the nucleolus defined by
\[{\cal LC}(\Pi, F)=\left\{{\bf x}\in\Pi :\max_{j\in M}F_{j}({\bf x})\leq
\max_{j\in M}F_{j}({\bf y})\mbox{ for all }{\bf y}\in\Pi\right\}\]
and
\begin{equation}{\label{mas92eq22}}\tag{57}
{\cal N}(\Pi, F)=\left\{{\bf x}\in\Pi :\theta\circ F({\bf x})\leq_{L}
\theta\circ F({\bf y})\mbox{ for all }{\bf y}\in\Pi\right\},
\end{equation}
where $\theta :\mathbb{R}^{m}\rightarrow\mathbb{R}^{m}$ is the coordinate ordering map (i.e. $\theta\circ F({\bf x})$ is an $m$-vector, $m=|M|$, with the same components as in $F({\bf x})$, but ordered in a weakly decreasing order) and “$\leq_{L}$” is the lexicographical prdering on $\mathbb{R}^{m}$. For the special case $M=\emptyset$, we define $latex {\cal LC}(\Pi, F)={\cal N}(\Pi, F)=
\Pi$. It should be noted that both the least core and nucleolus may be empty sets (Maschler et al. \cite[p.88]{mas92}).

Let $\boldsymbol{\Phi}$ be a solution concept defined on $\Omega$, i.e., $\boldsymbol{\Phi}$ assigns to each element $(\Pi, F)$ of $\Omega$ a subset $\boldsymbol{\Phi}(\Pi ,F)$ of $\Pi$. We consider the following axioms.

Axiom MPT1: (Restricted Non-emptiness). $\boldsymbol{\Phi} (\Pi ,F)\neq\emptyset$ if $\Pi$ is a nonempty compact set;
Axiom MPT2: (Non-discrimination). $\boldsymbol{\Phi}(\Pi ,F)=\Pi$ if $M=\emptyset$;
Axiom MPT3: (Redundancy). $\boldsymbol{\Phi}(\Pi ,F)=\boldsymbol{\Phi}(\Pi ,F\setminus\{F_{j}\})$ if $F_{j}$ is constant on $\Pi$ (if one of the functions makes no distinction between the points of $\Pi$, it has no influence on the outcomes under $\boldsymbol{\Phi}$);
Axiom MPT4: (Inclusion in the Least Core). $\boldsymbol{\Phi} (\Pi ,F)\subseteq {\cal LC}(\Pi ,F)$ (if the largest value among the $F_{j}({\bf x})$’s exceeds the largest value among the $F_{j}({\bf x})$’s for some ${\bf y}$, then ${\bf x}$ will not be chosen under $\boldsymbol{\Phi}$);
Axiom MPT5: (Restriction to the Least Core). $\boldsymbol{\Phi} (\Pi ,F)=\boldsymbol{\Phi}({\cal LC}(\Pi ,F),F)$ (points outside the least core do not affect the choices under $\boldsymbol{\Phi}$);
Axiom MPT6: (Invariance with Respect to Re-arrangement). If $(\Pi ,F)$ and $(\Pi, \bar{F})$ are elements of $\Omega$ and $\{F_{j}({\bf x}):j\in M\}\stackrel{eq}{=}\{\bar{F}_{j}({\bf x}):j\in M\}$ for each ${\bf x}\in\Pi$, then $\boldsymbol{\Phi}(\Pi ,F)=\boldsymbol{\Phi}(\Pi ,\bar{F})$. Here, $\stackrel{eq}{=}$ means equality of sets with counting multiplicities, i.e., every value occurs among the $F_{j}({\bf x})$’s and among the $\bar{F}_{j}({\bf x})$’s the same number of times (the solution concept considers only what and how often values of $F$ occur and does not care which functions take them);
Axiom MPT7: (Invariance with Respect to $\max /\min$). $\boldsymbol{\Phi}(\Pi ,F)=\boldsymbol{\Phi}(\Pi ,\{F_{i}\vee F_{j},F_{i}\wedge F_{j},F\setminus\{F_{i},F_{j}\}\})$ for every $i,j\in M$ with $i\neq j$ (the outcomes under $\boldsymbol{\Phi}$ do not change if we replace $F_{i}$ and $F_{j}$ by their maximun and minimum, respectively, and leave the other members of $F$ unchanged);
Axiom MPT8: (Independence of Irrelevant Alternatives). If $\bar{\Pi}$ is a subset of $\Pi$ with $(\bar{\Pi},F)\in\Omega$ and $\emptyset\neq \boldsymbol{\Phi}(\Pi ,F)\subseteq\bar{\Pi}$, then $\boldsymbol{\Phi}(\Pi ,F)=\boldsymbol{\Phi}(\bar{\Pi},F)$ (this is the well-known IIA property formulated for set-valued solution concepts);
Axiom MPT9: (Strong IIA Property). If $\bar{\Pi}$ is a subset of $\Pi$ with $(\bar{\Pi},F)\in\Omega$ and $\boldsymbol{\Phi}(\Pi ,F)\cap\bar{\Pi}\neq\emptyset$, then $\boldsymbol{\Phi}(\bar{\Pi},F)=\boldsymbol{\Phi}(\Pi ,F)\cap\bar{\Pi}$ (this time one only requires that $\boldsymbol{\Phi}(\Pi ,F)$ intersects $\bar{\Pi}$);
Axiom MPT10: (Contravariance). If $\Lambda :\bar{\Pi}\rightarrow\Pi$ is a continuous map and $\Lambda^{-1}(\boldsymbol{\Phi}(\Pi ,F))\neq\emptyset$, then $\boldsymbol{\Phi}(\bar{\Pi},F\circ\Lambda )=\Lambda^{-1}(\boldsymbol{\Phi}(\Pi ,F))$ (this is an even stronger version of IIA);
Axiom MPT11: (Closedness). $\boldsymbol{\Phi}(\Pi ,F)$ is a closed set for all pairs $(\Pi ,F)$ in $\Omega$.

\begin{equation}{\label{mas92t23}}\tag{58}\mbox{}\end{equation}

Theorem \ref{mas92t23}. (Maschler et al. \cite[p.89]{mas92}). The nucleolus in $(\ref{mas92eq22})$ defined on an arbitrary class $\Omega$ satsifies Axioms MPT1-MPT11 whenever the appropriate statements is meaningful $($e.g., Axiom MPT3 would be meaningless if $(\Pi ,F\setminus\{F_{j}\})$ had not been a member of $\Omega )$. $\sharp$

In order to determine the nucleolus for a pair $(\Pi ,F)$ in $\Omega$, we take the following algorithm:

Step 1. Remove all functions from $F$ which are constant on $\Pi$.
Step 2. If $M=\emptyset$ then ${\cal N}(\Pi ,F)=\Pi$. Go to Step 6.
Step 3. If $M\neq\emptyset$ compute ${\cal LC}(\Pi ,F)$. If ${\cal LC}(\Pi ,F)=\emptyset$ then ${\cal N}(\Pi ,F)=\emptyset$. Go to Step 6.
Step 4. If $m\geq 2$, replace $F=\{F_{1},\cdots ,F_{m}\}$ by $\bar{F}=\{\bar{F}_{1},\cdots ,\bar{F}_{m}\}$, where $\bar{F}_{p}=\bigvee_{j\leq p}\wedge F_{p+1}$ for $p=1,\cdots ,m-1$ and $\bar{F}_{m}=\bigvee_{j\leq m}F_{j}$.
Step 5. Replace $\Pi$ with ${\cal LC}(\Pi ,F)$. Go to Step 1.
Step 6. Stop. We have reached the general nucleolus. (Maschler et al. \cite[p.90]{mas92}).

Now we shall characterize the nucleolus for every class that is “rich enough” in the sense that it satisfies the following properties: for each $(\Pi ,F)\in\Omega$,

(a) $({\cal LC}(\Pi ,F),F)\in\Omega$;

(b) $(\Pi ,F\setminus\{F_{j}\})\in\Omega$ whenever $j\in M$ and $F_{j}$ is constant on $\Pi$;

(c) for all pairs $i,j\in M$ with $i\neq j$, $(\Pi ,\bar{F})$ is also in $\Omega$. Here, $\bar{F}=(\bar{F}_{1},\cdots ,\bar{F}_{m})$, where $\bar{F}_{k}=F_{k}$ for $k\in M\setminus\{i,j\}$ and $\bar{F}_{i}=F_{i}\wedge F_{j}$ and $\bar{F}_{j}=F_{i}\vee F_{j}$.

\begin{equation}{\label{mas92t31}}\tag{59}\mbox{}\end{equation}

Theorem \ref{mas92t31}. (Maschler et al. \cite[p.91]{mas92}). Let $\Omega$ be a class of pairs $(\Pi ,F)$ satisfying (a)-(c) above. Let $\boldsymbol{\Phi}$ be a solution concept satisfying Axioms MPT2, MPT3, MPT5 and MPT6. Under these conditions, we have $\boldsymbol{\Phi}(\Pi ,F)={\cal N}(\Pi ,F)$. $\sharp$

Proposition. (Maschler et al. \cite[p.92]{mas92}). The nucleolus is characterized by Axioms MPT2, MPT3, MPT5 and MPT6.

Proof. The result follows from Theorems \ref{mas92t23} and \ref{mas92t31}. $\blacksquare$

Proposition. (Maschler et al. \cite[p.93]{mas92}). The Axioms MPT2, MPT3, MPT5 and MPT6 are logically independent, i.e., there are solutions which fail to satisfy exactly any one of them. $\sharp$

Unfortunately, in the applications of nucleolus, many of the classes do not satisfy condition (c) above. For instance, the maximum and the minimum of two excesses functions in Example \ref{mas92ex21} are not themselves excess functions. However, fortunately, in these applications, the $F_{j}$’s are convex, even linear. In this case, we shall see that condition (c) is not needed. Accordingly, we shall now speak about classes $\Omega_{1}$ satisfying conditions (a), (b) and the following condition:

(d) $\Pi$ is convex and closed set in a topological vector space and each $F_{j}$ is a real, continuous and convex function whose domain is $\Pi$.

Proposition. (Maschler et al. \cite[p.94]{mas92}). If $(\Pi ,F)\in\Omega_{1}$ and $M\neq\emptyset$, then there exists a function $F_{j_{0}}$, $j_{0}\in M$, which is constant on ${\cal LC}(\Pi ,F)$. $\sharp$

\begin{equation}{\label{mas92t42}}\tag{60}\mbox{}\end{equation}

Theorem \ref{mas92t42}. (Maschler et al. \cite[p.94]{mas92}). Let $\Omega_{1}$ be a class of pairs $(\Pi ,F)$ satisfying conditions (a), (b) and (d) above, then the nucleolus on $\Omega_{1}$ is characterized by Axiomx MPT2, MPT3 and MPT5. $\sharp$

The above algorithm can be adapted to an algorithmic scheme to compute the nucleolus in a class $\Omega_{1}$. Step 4 is not needed to obtain a constant function and can be skipped (Maschler et al. \cite[p.94]{mas92}).

We further provide two additional axioms of the general nucleolus defined on a class $\Omega_{1}$ satisfying conditions (a), (b) and (d) (they are not true in other classes).

Axiom MPT12: (Deletion of the Smaller of Two Functions with Constant Difference). If $(\Pi ,F)\in\Omega_{1}$ and $F_{i}=F_{j}+\lambda$ for some $i$ and $j$ with $i\neq j$ and $\lambda >0$, then $\boldsymbol{\Phi} (\Pi ,F)=\boldsymbol{\Phi}(\Pi, F\setminus\{F_{j}\})$;
Axiom MPT13: (Indifference). $F$ is constant on $\boldsymbol{\Phi} (\Pi ,F)$.

Theorem. (Maschler et al. \cite[p.95]{mas92}). The nucleolus of a class $\Omega_{1}$ satisfying conditions (a), (b) and (d) satisfies Axioms MPT12 and MPT13. $\sharp$

In the sequel, we shall extend the class of games by allowing games in which certain coalitions are not permissible and by allowing games in which the set of imputations is restricted a-priori to a given polyhedral set. The games restricted in thi way will be called truncated games, or TU-games with permissible coalitions and permissible imputations. Formally, a truncated game will be a quadruplet $(N,{\cal S},v,\Pi )$ where $N=\{1,\cdots ,n\}$ is the set of players, ${\cal S}$ is a subset of $2^{N}\setminus\{\emptyset ,N\}$, called the set of permissible coalitions, $v:{\cal S}\rightarrow\mathbb{R}$ is the characteristic function and $\Pi$, the set of permissible imputations which is the set of the form
\[\Pi =\left\{{\bf x}\in\mathbb{R}^{N}:v(N)=\sum_{i\in N}x_{i},
\sum_{i\in S}x_{i}\geq a^{S}\mbox{ for all }S\in {\cal U}\right\},\]
where ${\cal U}$ is a, possibly empty, collection of coalitions and the numbers $a^{S}$ for $S\in {\cal U}$ are given real numbers. It is easy to see that the usual TU-games are truncated games by taking ${\cal S}=2^{N}\setminus\{\emptyset ,N\}$, ${\cal U}=\{\{i\}:i\in N\mbox{ and }a^{\{i\}}=v(i)\}$ (Maschler et al. \cite[p.98]{mas92}).

For TU-truncated games, we define the least core and the nucleolus by
\[{\cal LC}(N,{\cal S},v,\Pi )={\cal LC}(\Pi ,\{e(S,\cdot)\}_{S\in {\cal S}})\mbox{ and }{\cal N}(N,{\cal S},v,\Pi )=
{\cal N}(\Pi ,\{e(S,\cdot)\}_{S\in {\cal S}}).\]
Note that of $\Pi$ is not bounded and if some coalitions are missing from ${\cal S}$, both the nucleolsu and the least core may be empty (Maschler et al. \cite[p.99]{mas92}).

Let $\Omega_{2}$ be the class of truncated games satisfying conditions (a) and (b) (clearly condition (d) is also satisfied). Then, by
Theorem \ref{mas92t42}, the nucleolus for this class is characterized by Axioms MPT2, MPT3 and MPT5, which make perfect sense within the framework of truncated games. Here, the purpose is to provide a different axiomatic characterization by using the concept of a reduced game (Maschler et al. \cite[p.99]{mas92}).

Definition. (Maschler et al. \cite[p.99]{mas92}). Let $(N,{\cal S},v,\Pi )$ be a truncated game and let ${\cal B}$ be a subset of ${\cal S}$. Let ${\bf x}$ be a point in $\Pi$. The reduced game of $(N,{\cal S},v,\Pi )$ on ${\cal B}$ at ${\bf x}$ is the truncated game $(N,{\cal B},v|_{\cal B},\Pi^{\bf x}_{{\cal S}\rightarrow {\cal S}})$, where $v|_{\cal B}$ is the restriction of the domain of $v$ to ${\cal B}$ and
\[\Pi^{\bf x}_{{\cal S}\rightarrow {\cal B}}=\Pi\bigcap\left\{{\bf y}\in
\mathbb{R}^{N}:\sum_{i\in S}y_{i}=\sum_{i\in S}x_{i}\mbox{ for all }S\in {\cal S}\setminus {\cal B}\right\}. \sharp\]

Thus, in the reduced game, the set of permissible coalitions is restricted to ${\cal B}$, and $\Pi$ is also reduced to those imputations that have the same excess at ${\bf x}$ for coalitions of $S$ outside ${\cal B}$. The original reduced game proposed in Davis and Maschler \cite{dav65} is closely related to this one. Under some suitable conditions, the two reduced games are equivalent (Maschler et al. \cite[p.99]{mas92}).

Definition. (Maschler et al. \cite[p.100]{mas92}). We say that a solution concept $\boldsymbol{\Phi}$ defined on a class of truncated games satisfies the reduced game property, or is consistent, when it satisfies

Axiom MPT14: (Reduced Game Property). ${\bf x}\in\boldsymbol{\Phi}(N,{\cal S},v,\Pi )$ implies ${\bf x}\in\boldsymbol{\Phi}(N,{\cal B},v|_{\cal B},\Pi^{\bf x}_{{\cal S}\rightarrow {\cal B}})$, whenever $(N,{\cal B},v|_{\cal B},\Pi^{\bf x}_{{\cal S}\rightarrow {\cal B}})$ belongs to the domain of $\boldsymbol{\Phi}$.

One interpretation of the reduced game property runs as follows: Suppose ${\bf x}$ in a solution $\boldsymbol{\Phi}$ is being proposed, then someone may improve his/her payment by manipulation. He/She approaches members of a coalition $S$ (or several coalitions) and tells them: “please make your coalition unavailable (= non-permissible). In return, I shall give you $\sum_{\in S}x_{i}$ (or slightly more)”. If this manipulation were beneficial, then $\boldsymbol{\Phi}$ could be criticized for being unstable or inconsistent. Satisfying the reduced game property means that this manipulation cannot benefit any player (Maschler et al. \cite[p.100]{mas92}).

\begin{equation}{\label{mas92p63}}\tag{61}\mbox{}\end{equation}

Proposition \ref{mas92p63}. (Maschler et al. \cite[p.100]{mas92}). The nulceolus defined on an arbitarry class of truncated games satisfies the reduced game property. $\sharp$

Although the reduced game property is essentially a special case of the strong IIA property, we can use it to axiomatize the nucleolus.

\begin{equation}{\label{mas92t64}}\tag{62}\mbox{}\end{equation}

Theorem \ref{mas92t64}. (Maschler et al. \cite[p.100]{mas92}). Let $\Omega^{N}$ be the class of all truncated games on a fixed set of players $N$. Let $\boldsymbol{\Phi}$ be a solution concept for this class that satisfies the following axioms:

Axiom MPT2: (Non-discrimination). $\boldsymbol{\Phi}(N,{\cal S},v,\Pi )=\Pi$ if ${\cal S}=\emptyset$;
Axiom MPT3: (Redundancy). $\boldsymbol{\Phi}(N,{\cal S},v,\Pi )=\boldsymbol{\Phi}(N,{\cal S}\setminus\{S\},v,\Pi )$ if $e(S,\cdot)$ is constant on $\Pi$;
Axiom MPT4: (Inclusion in the Least Core). $\boldsymbol{\Phi} (N,{\cal S},v,\Pi )={\cal LC}(N,{\cal S},v,\Pi )$;
Axiom MPT14: $\boldsymbol{\Phi}$ satisfies the reduced game property.
Under these axioms, $\boldsymbol{\Phi}(N,{\cal S},v,\Pi )\subseteq {\cal N}(N,{\cal S},v,\Pi )$ for every truncated game in $\Omega^{N}$. $\sharp$

In view of Theorem \ref{mas92t23} and Proposition \ref{mas92p63}, we can paraphrase Theorem \ref{mas92t64} below.

Corollary. (Maschler et al. \cite[p.101]{mas92}). The nucleolus of the class $\Omega^{N}$ is the largest solution concept satisfying the Axioms MPT2, MPT3, MPT4 and MPT14 described in Theorem \ref{mas92t64}. $\sharp$

Definition. (Maschler et al. \cite[p.102]{mas92}). Let ${\cal B}$ and ${\cal C}$ be two collections of coalitions. We shall say that {\bf ${\cal B}$ is balanced with the help of ${\cal C}$} if positive real numbers $\lambda^{S}$ exist for each $S\in {\cal B}$ and nonnegative real numbers $\mu^{U}$ exist for every $U\in {\cal C}$ such that
\[\sum_{S\in {\cal B}}\lambda^{S}{\bf e}^{S}+\sum_{U\in {\cal C}}\mu^{U}{\bf e}^{U}={\bf e}^{N}. \sharp\]

For an imputation ${\bf x}$ in a truncated game $(N,{\cal S},v,\Pi )$, we define
\[{\cal B}_{t}({\bf x})=\left\{S\in {\cal S}:e(S,{\bf x})\geq t\right\}
\mbox{ and }{\cal C}({\bf x})=\left\{S\in {\cal U}:\sum_{i\in S}x_{i}=a^{S}\right\}.\]

Theorem. (Maschler et al. \cite[p.102]{mas92}). An imputation ${\bf x}$ in $\Pi$ is a nucleolus point of a truncated game $(N,{\cal S},v,\Pi )$ if and only if ${\cal B}_{t}({\bf x})$ is balanced with the help of ${\cal C}({\bf x})$ whenever ${\cal B}_{t}({\bf x})\neq\emptyset$. $\sharp$

Alternatively, Sakawa and Nishizaki \cite{sak94} consider a measure of dissatisfaction of players. They define the excess of a player by means of the excesses of all coalitions which he/she belongs to. That is, let ${\bf x}\in\mathbb{R}^{n}$ be a payoff vector, then the excess of player $i$ with respect to the payoff vecor ${\bf x}$ is defined by
\[w_{i}({\bf x})=\sum_{S\subseteq N,i\in S}e(S,{\bf x}).\]
Let $H:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be a mapping which arranges components of an $n$-dimensional vector in order of decreasing magnitude. Then the lexicographical solutions which minimize the excess $w(i,{\bf x})$ of a player $i$ is defined by
\[LS(v)=\left\{{\bf x}:H(w_{1}({\bf x}),\cdots ,w_{n}({\bf x}))\leq_{L}
H(w_{1}({\bf y}),\cdots ,w_{n}({\bf y}))\mbox{ for all }{\bf y}\in {\cal I}(v)\right\},\]
where $\leq_{L}$ is the lexicographical order (Molina and Tejada \cite[p.140]{mol00} and Sakawa and Nishizaki \cite[p.268]{sak94}).

It is not hard to see that the lexicographical solution is a general nucleolus, since we can take $\Pi$ as the set of imputations and $F=\{F_{j}\}_{j\in M}$ with $F_{j}=w_{j}:{\cal I}(v)\rightarrow\mathbb{R}$ (Molina and Tejada \cite[p.140]{mol00}).

Theorem. (Molina and Tejada \cite[p.141]{mol00}). For any game $(N,v)$ with nonempty imputation set, the least square nucleolus of the game coincides with its lexicographical solution. $\sharp$

Thus, the least square nucleolus turns out to be a general nucleolus obtained through a fair selection procedure towards players. On the other hand, let us consider the pair $\Pi ={\cal I}(v)$ and $F=\{w_{j}\}_{j\in M}$. Then we can see that the least core ${\cal LC}(\Pi ,F)$ contains only one point, which is the lexicographical solution. So, the lexicographical solution loses its lexicographical nature. Actually, it is a minimax-like solution concept (Molina and Tejada \cite[p.141]{mol00}).

Solution Concepts in Transferable Utility Games

The Cores.

Least Cores.

Cores of Convex Games.

Cores of Clan Games.

Cores of Games on Convex Geometry.

Cores of Restricted Games.

Cores of Multi-Choice Cooperative Games.

Bargaining Set.

Bargaining Set for the Games with Coalition Structure.

The Kernel

The Kernel for Veto-Rich Games.

The Kernel for Coalition Structures.

Original Treatment.

Alternative Treatment.

The Nucleolus.

The Nucleolus for the Big Boss Games.

The Nucleolus for the Games with Coalition Structure.

The Least Square Nucleolus.

General Nucleolus.

Hsien-Chung Wu

發佈留言取消回覆

The Cores.

Least Cores.

Cores of Convex Games.

Cores of Clan Games.

Cores of Games on Convex Geometry.

Cores of Restricted Games.

Cores of Multi-Choice Cooperative Games.

Bargaining Set.

Bargaining Set for the Games with Coalition Structure.

The Kernel

The Kernel for Veto-Rich Games.

The Kernel for Coalition Structures.

Original Treatment.

Alternative Treatment.

The Nucleolus.

The Nucleolus for the Big Boss Games.

The Nucleolus for the Games with Coalition Structure.

The Least Square Nucleolus.

General Nucleolus.

Hsien-Chung Wu

相關文章

Monotonicity

Shapley Value for Multilinear Extension of Games

Probabilistic Values

發佈留言取消回覆