Cooperative Games - Transferable Utility Games

Frederic Soulacoix (1858-1933) was an Italian painter born in France.

The topics are

Games in Characteristic Function Form
Multi-Choice Cooperative Games
Population Monotonic Allocation Schemes
Clan Games
Restricted Games

A set $P\subseteq\mathbb{R}^{n}$ is called a polyhedron when there exists a matrix ${\bf A}$ and a vector ${\bf b}$ satisfying
\[P=\{{\bf x}\in \mathbb{R}^{n}:{\bf A}{\bf x}\leq {\bf b}\}.\]
A set $P\subseteq\mathbb{R}^{n}$ is called a polytope when there exists ${\bf x}_{1},\cdots ,{\bf x}_{n}\in\mathbb{R}^{n}$ satisfying $P=\mbox{conv}\{{\bf x}_{1},\cdots ,{\bf x}_{n}\}$. A set $P$ is a polytope if and only if $P$ is a bounded polyhedron. The
polyhedron $P$ is bounded if and only if
\[\left\{{\bf x}\in\mathbb{R}^{n}:{\bf Ax}\leq{\bf 0}\right\}=\{{\bf 0}\}.\]
A vertex of $P$ is an element of $P$ which is not a convex combination of two other elements of $P$. If the polyhedron $P$ has at least one vertex, then $P$ is called pointed. The polyhedron $P$ is pointed if and only if
\[\left\{{\bf x}\in\mathbb{R}^{n}:{\bf Ax}={\bf 0}\right\}=\{{\bf 0}\}.\]

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

Games in Characteristic Function Form.

Let $N=\{1,\cdots ,n\}$ be a set of all players. In the standard mathematical notation, the class $\mathbb{R}^{N}$ means the functions $\eta :N\rightarrow\mathbb{R}$. Since the player set $N$ is finite, we always identify the class $\mathbb{R}^{N}$ as the $n$-dimensional Euclidean space $\mathbb{R}^{n}=\mathbb{R}^{|N|}$. Therefore, when we say that ${\bf x}$ is a vector of $\mathbb{R}^{N}$, it will mean that ${\bf x}\in\mathbb{R}^{n}$ in the sense that $x_{i}$ corresponds to the value of player $i$. For $S\subseteq N$, we write ${\bf x}^{S}$ for elements in $\mathbb{R}^{S}$, i.e., ${\bf x}^{S}$ is a function from $S$ into $\mathbb{R}$. We also denote by ${\bf 1}^{S}$ the vector in $\mathbb{R}^{N}$ satisfying $1_{i}^{S}=0$ if $i\not\in S$ and $1_{i}^{S}=1$ if $i\in S$.

Any nonempty subset $S\subseteq N$ is called a coalition. A transferable utility game is an ordered pair $(N,v)$, where the characteristic function $v$ is a function from $2^{N}$ to $\mathbb{R}$ satisfying $v(\emptyset )=0$. It is also called a cooperative game in characteristic function form. The number $v(S)$ can be regarded as the worth of coalition $S$ in the game $(N,v)$. Let $\mbox{TU}(N)$ denote the set of all transferable utility games with player set $N$.

Example. Suppose that there is a factory with $n$ workers each doing the same task. If each worker earns the same amount $b$ dollars, then we can take the characteristic function to be $v(S)=b\cdot |S|$, where $|S|$ denotes the number of workers in the coalition $S$. It is obvious that $v(\emptyset )=b\cdot |\emptyset |=0$ and
\[v(N)=b\cdot |N|=b\cdot n=\sum_{i=1}^{n}v(i). \sharp\]

Example. Suppose that the owner of a car, labeled player 1, offers it for $M$. There are two customers interested in the car. Customer A, labeled player 2, values the car at $a$, and customer B, labeled player 3, values it at $b$. Assume that the price is not negotiable. This means that if $M>a$ and $M>b$, then no deal will be made. In this case, we shall assume that $M\leq\min\{a,b\}$. Without loss of generality, we may assume $M<a\leq b$. The set of all possible coalitions are
\[\{123,12,13,23,1,2,3,\emptyset\}.\]
Since it requires a seller and a buyer to reach a deal, we may define the characteristic function as follows:
\[v(\emptyset )=0,\quad v(1)=M,\quad v(2)=v(3)=0,\quad v(13)=b,\quad v(12)=a,\quad v(23)=0,\quad v(123)=b.\]
$v(123)=b$ means that the car will be sold for $b$. $v(1)=M$ means that the car is worth $M$ to player 1. $v(13)=b$ means that player 1 will sell the cart o player 3 for $b>M$. $v(12)=a$ means that player 1 will sell the cart o player 2 for $a>M$. $\sharp$

Example. A small airport has a single runway and all of the different planes have to use it. Assume there are three different types of planes that use the runway. The largest plane needs $1000$ feet, the medium plane needs $750$ feet and the small plane needs $500$ feet. The runway must be built to serve the biggest plane. The runway’s cost is directly proportional to length. A possible characteristic function is as follows:
\begin{align*}
& v(\emptyset )=0,\quad v(1)=500,\quad v(2)=750, \quad v(3)=1000,\quad v(13)=1000,\\
& \quad v(12)=750,\quad v(23)=1000,\quad v(123)=1000. \sharp
\end{align*}

Example. Suppose that a family that owned a corporation has five shareholders. Family members $i=1,2,3,4,5$ holds $11,10,10,20,30$ shares, respectively. For a resolution to pass, a simple majority of shares must be in favor of the resolution. A possible characteristic function is $v(S)=1$ for any coalition $S$ consisting of $51$ or more shares. $\sharp$

Example. A simple game is one in which $v(S)=1$ or $v(S)=0$ for all coalitions. A coalition $S$ with $v(S)=1$ is called a winning coalition, and the coalition $S$ with $v(S)=0$ is called a losing coalition. For example, if we take $v(S)=1$ for $|S|>n/2$ and $v(S)=0$ otherwise, then we have a simple game that is a model of majority voting. $\sharp$

Example. (Not Finished Yet!) Given any $n$-person noncooperative and nonzero-sum game, we want to create a two-person zero-sum game in which any given coalition is played against a pure opposing coalition consisting of everyone else. The two players are the coalition $S$ versus the coalition $N\setminus S$. The characteristic function will be the value of the game associated with each coalition $S$. Let us consider a specific example using a three-player nonzero-sum game. Each player has two strategies $A$ and $B$.

Suppose that player 3 chooses strategy $A$. Then the matrix is given by
\[\begin{array}{ccccc}
&&& \mbox{Player 2} &\\
&& A && B\\
& A & (1,1,0) && (4,-2,2)\\
\mbox{Player 1} &&&&\\
& B & (1,2,-1) && (3,1,-1)
\end{array}\]
Suppose that player 3 chooses strategy $B$. Then the matrix is given by
\[\begin{array}{ccccc}
&&& \mbox{Player 2} &\\
&& A && B\\
& A & (-3,1,2) && (0,1,1)\\
\mbox{Player 1} &&&&\\
& B & (2,0,-1) && (2,1,-1)
\end{array}\]

Now, we want to find the characteristic function of this game. The possible two-players coalitions are $\{12\}$, $\{13\}$ and $\{23\}$ versus the single-player coalition $\{1\}$, $\{2\}$ and $\{3\}$.

$S=\{12\}$ versus $N\setminus S=\{3\}$: If player 1 chooses strategy $A$, player 2 chooses strategy $A$ and player 3 chooses strategy $B$, the payoffs in the nonzero-sum game are $(-3,1,2)$. $\sharp$

Now, we shall present some interesting notions for the game $(N,v)$.

A game $(N,v)$ is said to be super-additive when the following inequaility
\begin{equation}{\label{peteq18}}\tag{1}
v(S)+v(T)\leq v(S\cup T)
\end{equation}
hold for any disjoint coalitions $S$ and $T$. The inequality (\ref{peteq18}) means that the coalition $S\cup T$ has no less opportunities than the two disjoint coalitions $S$ and $T$ when they act independently. In this case, for any coalition $S$ , we have
\begin{equation}{\label{ga155}}\tag{2}
v(S)\geq\sum_{i\in S}v(i)
\end{equation}
by induction on the elements of $S$. Under the assumption of superadditivity, the players have the incentive to form and join the grand coalition $N$.
The game $(N,v)$ is called sub-additive when the reverse inequality in (\ref{peteq18}) holds true.
The game $(N,v)$ is called additive when the equality in (\ref{peteq18}) holds true.

From the superadditivity (\ref{peteq18}), we also see that, for any disjoint coalitions $\{S_{1},\cdots ,S_{k}\}$,
\[\sum_{i=1}^{k} v(S_{i})\leq v(N).\]
This says that there is no decomposition of the set $N$ into disjoint coalitions such that the guaranteed total payoff to these disjoint coalitions exceeds the maximum payoff to all players $v(N)$.

Two games $(N,v_{1})$ and $(N,v_{2})$ are said to be strategic equivalent when there exist a positive number $r$ and real constants $a_{1},\cdots ,a_{n}$ satisfying
\[v_{2}(S)=rv_{1}(S)+\sum_{i\in S}a_{i}\]
for all $S\subseteq N$.

Given a game $(N,v)$ and a coalition $S\subseteq N$, two types of subgames are defined below.

We write $(S,v^{S})$ for the subgame obtained by restricting $v$ to $S$, i.e., $v^{S}(T)=v(T)$ for all $T\subseteq S$.
We write $(N,v^{S})$ for the subgame defined by $v^{S}:2^{N}\rightarrow\mathbb{R}$ via $v^{S}(T)=v(S\cap T)$ for all $T\subseteq N$.

The subgames inherit the structure of the original game. For example, every subgame of a flow game is a flow game, every subgame of a linear production game is a linear production game and every subgame of a bankcruptcy game is a bankcruptcy game. Many special types of games are defined below.

The game $(N,v)$ is said to be a monotonic game when $S\subseteq T$ implies $v(S)\leq v(T)$.
The game $(N,v)$ is said to be a simple game when the characteristic function $v$ takes only the values $0$ and $1$. If $v(S)=1$, then $S$ is called a winning coalition; otherwise $S$ is a losing coalition. A simple game $(N,v)$ is completely determined by the set
\[W(v)=\{S\subseteq N:v(S)=1\}\]
of winning coalitions.
The control game is a simple game in which the grand coalition $N$ is a winning coalition, i.e., $v(N)=1$.
For $\emptyset\neq S\subseteq N$, the unanimity game $u_{S}$ is defined by
\begin{equation}{\label{ga2*11}}\tag{3}
u_{S}(T)=\left\{\begin{array}{ll}
1, & \mbox{if $S\subseteq T$}\\ 0, & \mbox{otherwise}.\end{array}\right .
\end{equation}
We can also consider the strict unanimity game
\begin{equation}{\label{ga28}}\tag{4}
\widehat{u}_{S}(T)=\left\{\begin{array}{ll}
1, & \mbox{if $S\subseteq T$ and $S\neq T$}\\ 0, & \mbox{otherwise}
\end{array}\right .
\end{equation}
We shall occasionally refer to the game $\widehat{u}_{\emptyset}$ defined by $\widehat{u}_{\emptyset}(S)=1$ for all nonempty coalitions $S$.
The game $(N,v)$ is zero-normalized when $v(i)=0$ for all $i\in N$. The zero-normalization of $(N,v)$, denoted by $(N,v_{0})$, is defined by
\[v_{0}(S)=v(S)-\sum_{i\in S}v(i)\]
for all $S\subseteq N$.
The game $(N,v)$ is said to be zero-monotonic when $(N,v_{0})$ is monotonic. Some researchers say that a cooperative game $(N,v)$ is called zero-monotonic when the unique zero-normalized game that is strategically equivalent to $(N,v)$ is monotonic.

We have the following observations.

Every supper-additive game is zero-monotonic.
Neither the set of all monotonic games nor the set of all zero-monotonic games contains the other.
Every unanimity game or strict unanimity game is monotonic, super-additive and simple.
For simple games, super-additivity implies monotonicity.
The set of all super-additive game and the set of all monotonic games are cones in $\mbox{TU}(N)$.
A game $(N,v)$ is zero-monotonic if and only if
\[v(S)\geq v(T)+\sum_{i\in S\setminus T}v(i)\]
whenever $T\subseteq S$.

\begin{equation}{\label{perl3134}}\tag{5}\mbox{}\end{equation}

Lemma \ref{perl3134}. Given a game $(N,v)$, there exist $2^{|N|}-1$ real numbers $\{c_{S}\}_{S\subseteq N}$ satisfying
\begin{equation}{\label{pereq3134}}\tag{6}
v=\sum_{S\subseteq N}c_{S}\cdot u_{S}
\end{equation}
and the representation $(\ref{pereq3134})$ is unique, where
\begin{equation}{\label{pereq3135}}\tag{7}
c_{S}=\sum_{\{T:T\subseteq S\}}(-1)^{|S|-|T|}v(T).
\end{equation}

Proof. If $U$ is an arbitrary coalition, then
\begin{align*}
\sum_{\{S:S\subseteq N\}}c_{S}u_{S}(U) & =\sum_{\{S:S\subseteq U\}}c_{S}
=\sum_{\{S:S\subseteq U\}}\left [\sum_{\{T:T\subseteq S\}}(-1)^{|S|-|T|}v(T)\right ]\\
& =\sum_{\{T:T\subseteq U\}}\left [\sum_{\{S:T\subseteq S\subseteq U\}} (-1)^{|S|-|T|}\right ]v(T).
\end{align*}
We shall consider the quantity which is bracketed in the last expression. For every value $s$ between $|T|$ and $|U|$, there are $\left (\begin{array}{c} |U|-s\\ |U|-|T|\end{array}\right )$ sets $S$ with $s$ elements such that $T\subseteq S\subseteq U$. Therefore the bracketed expression can be replaced by the following
\[\sum_{s=|T|}^{|U|}\left (\begin{array}{c} |U|-s\\ |U|-|T|\end{array}\right )
(-1)^{s-|T|}=\sum_{s=|T|}^{|U|}\left (\begin{array}{c} s-|T|\\ |U|-|T|
\end{array}\right )(-1)^{s-|T|}=(1-1)^{|U|-|T|}=\left\{\begin{array}{ll}
0, & \mbox{if $|T|<|U|$}\\ 1, & \mbox{if $|T|=|U|$}\end{array}\right .\]
Therefore, for all $U\subseteq N$, we have
\[\sum_{\{S:S\subseteq N\}}c_{S}u_{S}(U)=v(U).\]
We shall prove the uniqueness of representation (\ref{pereq3134}). Equivalently, we shall prove that $u_{S}$ are linearly independent for all $S\subseteq N$. Let
\[\sum_{\{S:S\subseteq N\}}\lambda_{S}u_{S}(T)=0\mbox{ for all }T\subseteq N.\]
For $T=\{i\}$, we have
\[u_{S}(i)=\left\{\begin{array}{ll}
1 & \mbox{if $S=\{i\}$}\\ 0 & \mbox{if $S\neq\{i\}$}.\end{array}\right .\]
Hence $\sum_{\{S:S\subseteq N\}}\lambda_{S}u_{S}(i)=0$ implies $\lambda_{\{i\}}=0$ for all $\{i\}\subseteq N$. Continue the proof by using the induction on the elements of $S$. Let $\lambda_{S}=0$ for all $S\subseteq T$ and $S\neq T$. Then
\[0=\sum_{\{S:S\subseteq N\}}\lambda_{S}u_{S}(T)=\sum_{\{S:S\subseteq T\}}\lambda_{S}u_{S}(T)=\lambda_{T}.\]
Now we have $2^{|N|}-1$ linearly independent vectors in $\mathbb{R}^{2^{|N|}-1}$. Therefore, every characteristic function $v$ is uniquely expressed as a linear conbimation of the functions $u_{S}$. This completes the proof. $\blacksquare$

Since the games are essentially identified with the characteristic functions, the addition of two gams $(N,v_{1})$ and $(N,v_{2})$ is defined by
\[(v_{1}+v_{2})(S)=v_{1}(S)+v_{2}(S)\]
and the multiplication of the game $(N,v)$ by a scalar $\alpha$ is defined by
\[(\alpha v)(S)=\alpha\cdot v(S).\]

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

Lemma \ref{gal57} Given a game $(N,v)$, the characteristic function $v$ can be expressed as the following two ways.

(a) For the family of games $\{\delta_{S}:\emptyset\neq S\subseteq N\}$ defined by
\[\delta_{S}(T)=\left\{\begin{array}{ll}
1, & \mbox{if $T=S$}\\ 0, & \mbox{if $T\neq S$},
\end{array}\right .\]
we have
\[v=\sum_{\{S:\emptyset\neq S\subseteq N\}}v(S)\cdot\delta_{S}.\]

(b) For the family of unanimity games $\{u_{S}:\emptyset\neq S\subseteq N\}$, we have
\begin{equation}{\label{gileqaa}}\tag{9}
v=\sum_{\{S:\emptyset\neq S\subseteq N\}}\Delta_{v}(S)\cdot u_{S},
\end{equation}
where the quantity $\Delta_{v}(S)$ is referred to as the dividend of coalition
$S$ and is defined recursively as follows:
\[\Delta_{v}(S)=\left\{\begin{array}{ll}
0, & \mbox{if $S=\emptyset$}\\
{\displaystyle v(S)-\sum_{\{T:T\subseteq S\}}\Delta_{v}(T)}, & \mbox{otherwise}
\end{array}\right .\]

Proposition. The set of all transferable utility games $\mbox{TU}(N)$ is a $(2^{|N|-1})$-dimensional real vector space.

Proof. Lemma \ref{perl3134} shows that the family of games $\{u_{S}\}_{S\subseteq N}$ is a basis for $\mbox{TU}(N)$. $\blacksquare$

In Lemma \ref{gal57}, the family of games $\{\delta_{S}:\emptyset\neq S\subseteq N\}$ is called the standard basis of $\mbox{TU}(N)$ and the family of unanimity games $\{u_{S}:\emptyset\neq S\subseteq N\}$ is called the unanimity basis of $\mbox{TU}(N)$

The marginal contribution of player $i$ to the grand coalition $N$ is defined by
\[m_{i}(v)=v(N)-v(N\setminus\{i\}).\]
For each coalition $\emptyset\neq S\subseteq N$ and each player $i\in S$, the marginal contribution of player $i$ to coalition $S$ is defined by
\[m_{i}(S,v)=v(S)-v(S\setminus\{i\}).\]
Some researchers also define the marginal contribution of player $i$ to coalition $S$ as follows:
\begin{equation}{\label{ga35}}\tag{10}
\Delta_{i}v(S)=\left\{\begin{array}{ll}
v(S)-v(S\setminus\{i\}), & \mbox{if $i\in S$}\\
v(S\cup\{i\})-v(S), & \mbox{if $i\not\in S$}.
\end{array}\right .
\end{equation}

For any permutation $\pi =\{i_{1},\cdots ,i_{n}\}$ of the player set $N$, let $P(\pi ,i_{k})=\{i_{1},\cdots ,i_{k-1}\}$ be the set of predecessors of $i_{k}$ in $\pi$. The {\bf marginal vector} ${\bf m}(v,\pi )$ is defined by
\begin{equation}{\label{ga40}}\tag{11}
m_{i}(v,\pi )=v(\{\pi (1),\cdots ,\pi (k)\})-v(\{\pi (1),\cdots ,\pi (k-1)\})=v(P(\pi ,i)\cup\{i\})-v(P(\pi,i)),
\end{equation}
where $i=\pi (k)$. This says that $m_{i}(v,\pi )$ is the marginal contribution of player $i=\pi (k)$ enterning the coalition $\{\pi (1),\cdots ,\pi (k-1)\}$ of predecessors of $i$ in the permutation $\pi$.

Given a cooperative game $(N,v)$, we consider the following concepts.

A player $i\in N$ is a dummy player when
\begin{equation}{\label{ga36}}\tag{12}
v(S\cup\{i\})=v(S)+v(i)
\end{equation}
for every $S\subseteq N\setminus\{i\}$. This means that player $i$ has no meaningful strategic role in the game.
A player $i\in N$ is called a null player when
\begin{equation}{\label{ga37}}\tag{13}
\mbox{$v(S)=v(S\setminus\{i\})$ for all $S\subseteq N$ containing $i$,}
\end{equation}
which is equivalent to $m_{i}(S,v)=0$ for all $S\subseteq N$ containing $i$.
A player $i\in N$ is called a null player when
\begin{equation}{\label{ga39}}\tag{14}
\mbox{$v(S\cup\{i\})=v(S)$ for all $S\subset N\setminus\{i\}$}.
\end{equation}
A player $i\in N$ is called a null player when
\begin{equation}{\label{ga38}}\tag{15}
\Delta_{i}v=0,
\end{equation}
where $\Delta_{i}v(S)$ is defined in (\ref{ga35}).

Relations with Non-cooperative Game.

We shall now consider a non-cooperative game $\Gamma =(N,\{X_{i}\}_{i\in N},\{H_{i}\}_{i\in N})$. Suppose the players appearing in a coalition $S$ unite their efforts for the purpose of increasing their total payoff. Let us find the largest payoff they can guarantee themselves. The joint actions of the players from a coalition $S$ imply that the coalition $S$ acting for all its members as one player (called player 1) takes the set of pure strategies to the set of all possible combinations of strategies for its constituent players from $S$, i.e., the elements of the Cartesian product ${\bf x}^{S}=\prod_{i\in S}X_{i}$. The community of interests of the players from $S$ means that a payoff to the coalition $S$ (player 1) is the sum of payoffs to the players from $S$, i.e.,
\[H_{S}({\bf x})\equiv\sum_{i\in S}H_{i}({\bf x}),\]
where ${\bf x}=(x_{1},\cdots ,x_{n})\in {\bf X}_{N}$ is a policy.

We are interested in the largest payoff of the players from $S$. In the worst case for player 1, i.e., coalition $S$, the remaining players from $N\setminus S$ may also unite into a collective player 2 with the set of strategies ${\bf X}_{N\setminus S}=\prod_{i\in N\setminus S}X_{i}$, where the payoff of player 2 at ${\bf x}$ is $-H_{S}({\bf x})$. As a result of this reasoning, the question of the largest guaranteed payoff to the coalition $S$ becomes the issue of the largest guaranteed payoff to player 1 in the zero-sum two-person game $\Gamma_{S}=({\bf x}^{S},{\bf X}_{N\setminus S},H_{S})$. In the mixed extension $\widehat{\Gamma}_{S}=(\widehat{{\bf X}}_{S},\widehat{{\bf X}}_{N\setminus S},K_{S})$ of the game $\Gamma_{S}$, the guaranteed payoff $v(S)$ to player 1 can merely be increased in comparison with that in the game $\Gamma_{S}$. For this reason, the following discussion concentrates on the mixed extension of $\Gamma_{S}$. In particular, it should be noted that, according to the interpretation, $v(S)$ coincides with the value of the game $\widehat{\Gamma}_{S}$, while $v(N)$ is the maximum total payoff to the players. Evidently, $v(S)$ only depends on the coalition $S$ and is a function of $S$. We shall verify that this function is a characteristic function of a noncooperative game. To do this, it suffices to show that the conditions (\ref{peteq18}) is satisfied.

Proposition. For the non-cooperative game $\Gamma =(N,\{X_{i}\}_{i\in N},\{H_{i}\}_{i\in N})$, we have the following properties.

(i) We construct the function $v(S)$ as
\[v(S)=\sup_{{\bf x}^{S}}\inf_{{\bf x}_{N\setminus S}}H_{S}({\bf x}^{S},{\bf x}_{N\setminus S}),\]
where ${\bf x}^{S}\in {\bf x}^{S}$ and ${\bf x}_{N\setminus S}\in {\bf X}_{N\setminus S}$, and $\Gamma_{S}=({\bf x}^{S},{\bf X}_{N\setminus S},H_{S})$ is a zero-sum two-person game. Then for all $S,T\subseteq N$ for which $S\cap T=\emptyset$, the following inequality holds
\[v(S\cup T)\geq v(S)+v(T).\]

(ii) We construct the function $v(S)$ as
\begin{equation}{\label{peteq21}}\tag{16}
v(S)=\sup_{\mu_{S}}\inf_{\nu_{N\setminus S}}K_{S}(\mu_{S},\nu_{N\setminus S}),
\end{equation}
where $\mu_{S}\in\widehat{{\bf X}}_{S}$ and $\nu_{N\setminus S}\in\widehat{{\bf X}}_{N\setminus S}$, and $\widehat{\Gamma}_{S}=(\widehat{{\bf X}}_{S},\widehat{{\bf X}}_{N\setminus S},K_{S})$ is a mixed extension of the zero-sum two-person game $\Gamma_{S}$. Then for all $S,T\subseteq N$ for which $S\cap T=\emptyset$, the following inequality holds
\begin{equation}{\label{peteq20}}\tag{17}
v(S\cup T)\geq v(S)+v(T). \sharp
\end{equation}

The non-cooperative game $\Gamma =(N,\{X_{i}\}_{i\in N},\{H_{i}\}_{i\in N})$ is called a constant sum game when
\[\sum_{i\in N}H_{i}({\bf x})=c,\]
for all ${\bf x}\in {\bf X}_{N}$, where $c$ is a constant and ${\bf X}_{N}=\prod_{i\in N}X_{i}$.

Proposition. Let $\Gamma =(N,\{X_{i}\}_{i\in N},\{H_{i}\}_{i\in N})$ be a non-cooperative constant sum game. Suppose that the function $v(S)$ is defined in (\ref{peteq21}) and the games $\Gamma_{S}$ have the values in mixed strategies. Then, we have
\[v(N)=v(S)+v(N\setminus S). \sharp\]

Example. Manager of a club promises singer $S$, pianist $P$, and drummer $D$ to pay $100$ for a joint performance. He values a singer-pianist duet at $80$, a drummer-pianist duet at $65$ and a pianist at $30$. A singer-drummer duet may earn $50$ and a singer, on the average, $20$ for doing an evening performance. A drummer my not earn anything by playing alone. Designating players $S$, $P$, and $D$ by numbers $1,2,3$, respectively, we are facing a cooperative game $(N,v)$, where $N=\{1,2,3\}$, $v(\{1,2,3\})=100$, $v(\{1,3\})=50$, $v(\{1\})=20$, $v(\{1,2\})=80$, $v(\{2,3\})=65$, $v(\{2\})=30$, and $v(\{3\})=0$. $\sharp$

Imputation.

Definition. Given a game $(N,v)$, let ${\bf x}\in\mathbb{R}^{N}$ be a payoff vector or an allocation, where each $x_{i}$ represents the share of the value of $v(N)$ received by player $i$.

The vector ${\bf x}\in\mathbb{R}^{N}$ is said to be feasible when
\[\sum_{i\in N}x_{i}\leq v(N).\]
The vector ${\bf x}\in\mathbb{R}^{N}$ is called a pre-imputation when it satisfies
\begin{equation}{\label{peteq23}}\tag{18}
v(N)=\sum_{i\in N}x_{i};
\end{equation}
that is, the group rationality is satisfied.
The vector ${\bf x}\in\mathbb{R}^{N}$ is called an imputation when it is a pre-imputation and satisfies the individual rationality
\begin{equation}{\label{peteq22}}\tag{19}
x_{i}\geq v(i)\mbox{ for }i\in N.
\end{equation}
The vector ${\bf x}\in\mathbb{R}^{N}$ is called as pseudo-imputation when it is pre-imputation and satisfies $x_{i}\geq 0$ for all $i\in N$.

We denote by ${\cal I}(v)$ the set of all imputations of $(N,v)$, and by ${\cal I}^{*}(v)$ the set of all pre-imputations of $(N,v)$. $\sharp$

The individual rationality condition (\ref{peteq22}) says that each member of coalition receives at least the same amount that the player could obtain by acting alone without any support of other players. Group rationality means any increase of reward to a player must be matched by a decrease in reward for one or more other players. Suppose that $\sum_{i\in N}x_{i}<v(N)$. Then, each player could actually receives a larger share than $x_{i}$. For example, one possibility is an additional amount $(v(N)-\sum_{i\in N}x_{i})/n$. This says that the allocation $x_{i}$ would be rejected by each player. Therefore, we must have $\sum_{i\in N}x_{i}=v(N)$ for any reasonable allocation. All of $v(N)$ should be distributed to the players, and nothing should be left over.

The main objective in cooperative game theory is to determine the imputation that results in a fair allocation of the total rewards, which will depend on the definition of fair. This word is not at all precise. If we change the meaning of fair, we shall change the imputation.

Definition. The game $(N,v)$ is called essential when
\begin{equation}{\label{ga73}}\tag{20}
v(N)>\sum_{i\in N}v(i),
\end{equation}
otherwise it is called inessential, i.e.,
\begin{equation}{\label{ga*38}}\tag{21}
v(N)\leq\sum_{i\in N}v(i). \sharp
\end{equation}

We have the following observations.

Suppose that ${\cal I}(v)\neq\emptyset$. From (\ref{peteq23}) and (\ref{peteq22}), we immediately have
\begin{equation}{\label{ga*37}}\tag{22}
v(N)\geq\sum_{i\in N}v(i).
\end{equation}
Suppose that $(N,v)$ is an inessential game satisfying ${\cal I}(v)\neq\emptyset$. Then, for any ${\bf x}\in {\cal I}(v)$,
from (\ref{ga*38}) and (\ref{ga*37}), we have
\begin{equation}{\label{ga34}}\tag{23}
\sum_{i\in N}x_{i}=v(N)=\sum_{i\in N}v(i).
\end{equation}
Since $x_{i}\geq v(i)$, we conclude that the inessential game has a unique imputation
\[{\bf x}=(v(\{1\}),v(\{2\}),\cdots ,v(\{n\})).\]
In any essential game with more than one player, the imputation set is infinite.
If $(N,v)$ is an essential game, then ${\cal I}(v)$ is a simplex of $n-1$ dimensions and ${\cal I}^{*}(v)$ is a $(n-1)$-dimensional affine set.

Proposition. Suppose that $(N,v)$ is an inessential game satisfying ${\cal I}(v)\neq\emptyset$. If $(N,v)$ is super-additive, then it is also additive.

Proof. We have
\begin{align}
v(N) & =\sum_{i\in N}v(i)\mbox{ (by (\ref{ga34}))}\nonumber\\
& =\sum_{i\in S}v(i)+\sum_{j\in T}v(\{j\})+\sum_{k\in N\setminus (S\cup T)}v(\{k\})\nonumber\\
& \leq v(S)+v(T)+v(N\setminus (S\cup T))\mbox{ (by the superadditivity)})\label{ga*35}\tag{24}\\
& \leq v(S\cup T)+v(N\setminus (S\cup T))\mbox{ (by the superadditivity)}\label{ga*36}\tag{25}\\
& \leq v(N)\mbox{ (by the superadditivity)},\nonumber
\end{align}
which implies, by (\ref{ga*35}) and (\ref{ga*36}),
\[v(S)+v(T)+v(N\setminus (S\cup T))=v(S\cup T)+v(N\setminus (S\cup T)).\]
Therefore, we obtain
\[v(S)+v(T)=v(S\cup T).\]
This completes the proof. $\blacksquare$

Imputation ${\bf x}$ dominates imputation ${\bf y}$ in coalition $S$, denoted by ${\bf x}\succ_{S}{\bf y}$, when
\begin{equation}{\label{ga43}}\tag{26}
x_{i}>y_{i}\mbox{ for }i\in S\mbox{ and }\sum_{i\in S}x_{i}\leq v(S).
\end{equation}
The condition $x_{i}>y_{i}$ for $i\in S$ says that imputation ${\bf x}$ is more advantageous to all members of coalition $S$ than imputation ${\bf y}$. The condition $\sum_{i\in S}x_{i}\leq v(S)$ means that imputation ${\bf x}$ can be realized by coalition $S$. In other words, the coalition $S$ can offer an amount $x_{i}$ to each player $i\in S$ such that the payoff $\sum_{i\in S}x_{i}$ is reachable by the coalition. The imputation ${\bf x}$ is said to {\bf dominate} imputation ${\bf y}$, denoted by ${\bf x}\succ {\bf y}$, if and only if there is a coalition $S$ satisfying ${\bf x}\succ_{S}{\bf y}$. The dominance is not possible in a single element coalition and the grand
coalition $N$ as shown below.

If ${\bf x}\succ_{\{i\}}{\bf y}$, then $y_{i}<x_{i}\leq v(i)$ which constradicts condition (\ref{peteq22}).
If ${\bf x}\succ_{N}{\bf y}$, then $y_{i}<x_{i}$ for all $i\in N$, ${\bf x},{\bf y}\in {\cal I}(v)$, since
\[v(N)=\sum_{i\in N}x_{i}>\sum_{i\in N}y_{i}=v(N).\]

Strategical Equivalence.

The game $(N,v)$ is called (strategically) equivalent to the game $(N,v’)$ when there exists a positive number $k$ and $n$ arbitrary real numbers $c_{i}$ for $i\in N$ satisfying
\begin{equation}{\label{ga41}}\tag{27}
v'(S)=kv(S)+\sum_{i\in S}c_{i}
\end{equation}
for any coalition $S$. The equivalence of the game $(N,v)$ to $(N,v’)$ will be denoted by $v\sim v’$.

It is obvious that $v\sim v$. This can be verify by setting $c_{i}=0$, $k=1$, and $v’=v$. This property is called reflexivity.
We shall prove the symmetry of the relation, i.e., that the condition $v\sim v’$ implies $v’\sim v$. In fact, setting $k’=1/k$, $c’_{i}=-c_{i}/k$ we obtain $v(S)=k’v'(s)+\sum_{i\in S}c’_{i}$, i.e., $v’\sim v$.
If $v\sim v’$ and $v’\sim v”$, then $v\sim v”$. This property is called transitivity.

Since the equivalence relation is reflexive, symmetric and transitive, it decomposes the set of all $n$-person games into mutually disjoint classes of equivalent games.

Proposition. Suppose that the games $(N,v)$ and $(N,v’)$ are equivalent. We define the map ${\bf x}\mapsto {\bf x}^{\prime}$ by $x_{i}^{\prime}=kx_{i}+c_{i}$ for $i\in N$. Then, we have the following properties.

(i) The map is one-to-one.

(ii) ${\bf x}$ is an imputation for $(N,v)$ if and only if ${\bf x}^{\prime}$ is an imputation for $(N,v’)$.

(iii) ${\bf x}\succ_{S}{\bf y}$ if and only if ${\bf x}^{\prime}\succ_{S}{\bf y}^{\prime}$.

Proof. Part (i) is obvious, since $k\neq 0$. To prove part (ii), if ${\bf x}$ is an imputation for $(N,v)$, from (\ref{ga41}), we have
\[x_{i}^{\prime}=kx_{i}+c_{i}\geq kv(i)+c_{i}=v'(i)\]
and
\[\sum_{i\in N}x_{i}^{\prime}=\sum_{i\in N}\left (kx_{i}+c_{i}\right )=kv(N)+\sum_{i\in N}c_{i}=v'(N).\]
This shows that ${\bf x}^{\prime}$ is also an imputation for $(N,v’)$. Conversely, if ${\bf x}^{\prime}$ is an imputation for $(N,v’)$, then we have
\[x_{i}=\frac{1}{k}\left (x_{i}^{\prime}-c_{i}\right )\geq\frac{1}{k}\left (v'(i)-c_{i}\right )=v(i)\]
and
\[\sum_{i\in N}x_{i}=\sum_{i\in N}\left [\frac{1}{k}\left (x_{i}^{\prime}-c_{i}\right )\right ]=
\frac{1}{k}\left (v'(N)-\sum_{i\in N}c_{i}\right )=v(N).\]
This shows that ${\bf x}$ is also an imputation for $(N,v)$.

To prove part (iii), we assume that ${\bf x}\succ_{S}{\bf y}$. By definition, we have $x_{i}>y_{i}$ for each $i\in S$ and $\sum_{i\in S}x_{i}\leq v(S)$. Therefore, since $k>0$, we obtain
\[x_{i}^{\prime}=kx_{i}+c_{i}>ky_{i}+c_{i}=y_{i}^{\prime}\]
and
\[\sum_{i\in S}x_{i}^{\prime}=\sum_{i\in S}\left (kx_{i}+c_{i}\right )\leq kv(S)+\sum_{i\in S}c_{i}=v'(S),\]
which shows that ${\bf x}^{\prime}\succ_{S}{\bf y}^{\prime}$. Conversely, we assume that ${\bf x}^{\prime}\succ_{S}{\bf y}^{\prime}$. Therefore, we obtain
\[x_{i}=\frac{1}{k}\left (x_{i}^{\prime}-c_{i}\right )>\frac{1}{k}\left (y_{i}^{\prime}-c_{i}\right )=y_{i}\]
and
\[\sum_{i\in S}x_{i}=\sum_{i\in S}\left [\frac{1}{k}\left (x_{i}^{\prime}-c_{i}\right )\right ]\leq
\frac{1}{k}\left (v'(S)-\sum_{i\in S}c_{i}\right )=v(S),\]
which shows that ${\bf x}\succ_{S}{\bf y}$. This completes the proof. $\blacksquare$

Normalization.

We shall present a way to transform a given characteristic function for a cooperative game to one which is easier to work with. The game $(N,v)$ is said to be in $(0,1)$-reduced form (or $(0,1)$-normalized) when, for all $i\in N$, we have $v(i)=0$ and $v(N)=1$.

\begin{equation}{\label{ga*40}}\tag{28}\mbox{}\end{equation}

Proposition \ref{ga*40}. Every essential game is equivalent to some game in $(0,1)$-reduced form in the sense of $(\ref{ga41})$.

Proof. Given any coalition $S$ in $N$, we define
\[k=\frac{1}{\displaystyle v(N)-\sum_{i\in N}v(i)}>0\mbox{ and }c_{i}=-\frac{v(i)}{\displaystyle v(N)-\sum_{i\in N}v(i)}\]
for $i\in S$. Then
\[v'(S)=\frac{\displaystyle v(S)-\sum_{i\in S}v(i)}{\displaystyle v(N)-\sum_{i\in N}v(i)}=kv(S)+\sum_{i\in S}c_{i}\]
satisfies $v'(i)=0$ and $v'(N)=1$. This completes the proof.

Proposition \ref{ga40} says that the game theoretic properties can be examined on the games in $(0,1)$-reduced form. If $v$ is the characteristic function of an arbitrary essential game $(N,v)$, then
\[v'(S)=\frac{\displaystyle v(S)-\sum_{i\in S}v(i)}{\displaystyle v(N)-\sum_{i\in N}v(i)},\]
is $(0,1)$-normalization corresponding to the function $v$. Then, we have the following observations.

An imputation is any vector ${\bf x}=(x_{1},\cdots ,x_{n})$ whose components satisfy the folowing conditions
\[x_{i}\geq 0\mbox{ for }i\in N\mbox{ and }\sum_{i\in N}x_{i}=1,\]
i.e., the imputations can be regarded as the points of the $(n-1)$-dimensional simplex generated by the unit vectors ${\bf e}_{j}=(0,\cdots ,0,1,0,\cdots ,0)$ for $j=1,\cdots ,n$ in the space $\mathbb{R}^{n}$
If ${\bf x}^{\prime}$ is an imputation for $v’$, then the imputation ${\bf x}$ for $v$ is given by
\[x_{i}=x_{i}^{\prime}\cdot\left (v(N)-\sum_{i=1}^{n}v(i)\right )+v(i)\]
for $i=1,\cdots ,n$.
If ${\bf x}$ is an imputation for the original game $v$, then, for $i=1,\cdots ,n$,
\[x_{i}^{\prime}=\frac{x_{i}-v(i)}{\displaystyle v(N)-\sum_{i=1}^{n}v(i)}\]
forms an imputation ${\bf x}^{\prime}$ for $v’$.

Given a game $(N,v)$, we plan to add an additional player $k$, $k\not\in N$, to the player set $N$. Therefore, we define a dynamic cooperative game by setting $N’=N\cup\{k\}$ and setting a characteristic function $w$ such that $w(S)=v(S)$ for all $S\subseteq N$. In this case, we may say that $(N,v)$ is a subgame of $(N’,w)$. We define {\bf dynamic cooperative convex game} as dynamic cooperative game $(N’,w)$ such that $(N’,w)$ is convex.

Balanced Games.

Let $S\subseteq N$ be a coalition. A collection ${\cal S}=\{S_{1},\cdots ,S_{p}\}$ of nonempty subsets of $S$ is called balanced over $S$ when there exists positive constants $\gamma_{1},\cdots ,\gamma_{p}$ satisfying
\[\sum_{\{j:i\in S_{j}\}}\gamma_{j}=1\]
holds for each $i\in S$. The numbers $\gamma_{j}$ are called balancing coefficients. Also, ${\cal S}$ is called minimal balanced over $S$ when it is balanced over $S$ and no proper sub-collection of ${\cal S}$ is balanced over $S$. If $S=N$, then we simply say that ${\cal S}$ is balanced instead of balanced over $N$. Equivalently, a collection ${\cal S}$ of nonempty subsets of $N$ is balanced if and only if there exists positive numbers $\lambda^{S}$ for all $S\in {\cal S}$ such that $\sum_{S\in {\cal S}}\lambda^{S}\cdot1_{S}=1$,
where $1_{S}$ is the indicator function of $S$.

Let $S\subseteq N$ be a coalition. We denote by ${\bf 1}_{S}$ the $|N|$-dimensional vector such that the $i$th component of ${\bf 1}_{S}$ is $1$ for $i\in S$ and $0$ for $i\in N\setminus S$. Let ${\cal P}(N)$ be the collection of all nonempty subsets of $N$. A map $\gamma:{\cal P}(N)\rightarrow\mathbb{R}_{+}$ is called a balanced map when
\[\sum_{S\in{\cal P}(N)}\gamma(S){\bf 1}_{S}={\bf 1}_{N}.\]

Proposition. We have the following properties.

(i) The union of balanced collection is balanced.

(ii) Any balanced collection is the union of minimal balanced collections.

(iii) A balanced collection has a unique balancing vector if and only if it is minimal.

(iv) A minimal balanced collection has at most $|N|$ sets.

(v) The inequality $\sum_{j=1}^{p}\gamma_{j}\geq 1$ always holds, and holds strictly unless ${\cal S}$ is the trivial collection $\{S\}$. $\sharp$

A cooperative game $(N,v)$ is called a balanced game when, for every balanced collection ${\cal S}$ with coefficients $\{\lambda^{S}\}_{S\in {\cal S}}$ the following holds:
\[v(N)\geq\sum_{S\in {\cal S}}\lambda^{S}v(S).\]
A cooperative game $(N,v)$ is called totally balanced when, for each coalition $S$, the subgame $(S,v^{S})$ is balanced. We denote by $\tau_{S}$ the family of all balanced collections over $S$ and $B({\cal S})$ the set of all balancing coefficients $\{\gamma_{j}\}$ for ${\cal S}$. Some researchers says that a cooperative game $(N,v)$ is called a balanced game when, for every balanced map $\gamma$, we have
\[v(N)\geq\sum_{S\in {\cal P}(N)}\gamma(S)v(S).\]

Proposition. We see that the cooperative game $(N,v)$ is balanced if
\[v(N)\geq\max_{{\cal S}\in\tau_{N},\{\gamma_{j}\}\in B({\cal S})}\sum_{j}\gamma_{j}v(S_{j}). \sharp\]

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

Definition \ref{gad13}. The cover of a game $(N,v)$ is defined to be the game $(N,\widehat{v})$ with $\widehat{v}(\emptyset )=0$ and
\[\widehat{v}(S)=\max_{{\cal S}\in\tau_{S},\{\gamma_{j}\}\in B({\cal S})}\sum_{j}\gamma_{j}v(S_{j})\]
for each $S\neq\emptyset$. $\sharp$

It is clear that the cover $(N,\widehat{v})$ is totally balanced, and that it is the least totally balanced game that majorizes $(N,v)$. In other words, if $(N,v’)$ is totally balanced and $v’\geq v$ then $v’\geq\widehat{v}$.

Convex Cooperative Games.

The game $(N,v)$ is said to be convex when
\[v(S)+v(T)\leq v(S\cup T)+v(S\cap T)\]
for all $S,T\in 2^{N}$. Equivalently, the cooperative game $(N,v)$ is convex if and only if
\[v(S\cup\{i\})-v(S)\leq v(T\cup\{i\})-v(T)\]
for all $i\in N$ and all $S\subseteq T\subseteq N\setminus\{i\}$, which is expressed as a sort of increasing marginal utility for coalition membership. The game $(N,v)$ is called concave when the reverse inequality holds..

Proposition. The game $(N,v)$ is convex if it satisfies one of the following equivalent conditions.

(a) (Super-modularity Property). For each $S,T\subseteq N$, we have $v(S\cup T)+v(S\cap T)\geq v(S)+v(T)$.

(b) (Increasing Marginal Contribution Property for Players). For each $S,T\subseteq N$ with $S\subseteq T$ and for each $i\in N\setminus T$, we have $v(S\cup\{i\})-v(S)\leq v(T\cup\{i\})-v(T)$.

(c) (Increasing Marginal Contribution Property for Coalitions). For each $S,T,U\subseteq N$ with $S\subseteq T\subseteq N\setminus U$, we have $v(S\cup U)-v(S)\leq v(T\cup U)-v(T)$.

(d) (Stable Marginal Vector Property). For each permutation $\pi$ of $N$, we have ${\bf m}(v,\pi )\in C(v)$, i.e., the marginal vector ${\bf m}(v,\pi )$ is a core element. $\sharp$

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

Multi-Choice Cooperative Games.

We extend cooperative games in characteristic function form to multi-choice cooperative games. Suppose a land lord can harvest 20 bags of rice employing one honest hardworking peasant, and can produce 24 bags employing two such peasants. As an alternative plan, the landlord can harvest only 10 bags of rice employing a leisure seeking peasant, and can produce 18 bags employing two such peasants. Therefore, it may be useful to model cooperative games with the possibility that players have more than one way of acting within coalition (Hsiao and Raghavan \cite[p.241]{hsi93}).

The Same Activity Levels for Each Player.

Example (Hsiao and Raghavan \cite[p.241]{hsi93}). Players 1,2,3 and 4 jointly own a piece of land. Each player has three possible
actions to take.

Action $\sigma_{0}$: work not all.
Action $\sigma_{1}$: work half-hartedly.
Action $\sigma_{2}$: work whole-heartedly.

Let the outcome be the final harvest of corn measured in buchels. For any finite set $S$, if $x_{1},x_{2},x_{3}$ and $x_{4}$ are the actions of players 1,2,3 and 4, respectively, let the final harvest $v$ be given by
\[v(x_{1},x_{2},x_{3},x_{4})=\left\{\begin{array}{ll}
0 & \mbox{if $|\{x_{i}:x_{i}=\sigma_{2}\}|=0$}\\
15+2\cdot|\{x_{i}:x_{i}=\sigma_{1}\}| & \mbox{if $|\{x_{i}:x_{i}=\sigma_{2}\}|=1$}\\
25 & \mbox{if $|\{x_{i}:x_{i}=\sigma_{2}\}|=2$}\\
30 & \mbox{if $|\{x_{i}:x_{i}=\sigma_{2}\}|\geq 3$}
\end{array}\right .\]
This a four-person game with three possible actions for each player. Each player would like to know the value for each one of his effort levels. $\sharp$

Let us consider the cooperative game $(N,v)$ with $|N|=n$. Let $\beta =\{0,1\}$ and
\[\beta^{n}=\left\{(x_{1},\cdots ,x_{n}):x_{i}\in\beta\mbox{ for all }i\in N\right\}.\]
Given any coalition $S\subseteq N$, we define ${\bf b}_{S}=(x_{1},\cdots ,x_{n})$, where
\[x_{i}=\left\{\begin{array}{ll}
1 & \mbox{if $i\in S$}\\ 0 & \mbox{otherwise}.\end{array}\right .\]
Therefore, we can identify $\beta^{n}$ with $2^{N}$. Let us call $\beta^{n}$ the action space of the players $\{1,2,\cdots ,n\}$. Then, the characteristic function of the cooperative game can also be defined by $v:\beta^{n}\rightarrow\mathbb{R}^{n}$ such that $v({\bf 0})=0$, where ${\bf 0}=(0,\cdots ,0)$. We can extend this cooperative game as follows.

We allow each player to have $(m+1)$ actions, say $\sigma_{0},\sigma_{1},\cdots ,\sigma_{m}$, where $\sigma_{0}$ is the action of doing nothing,while $\sigma_{k}$ is the action of working at level $k$ for $k=1,\cdots ,m$.
Let $\beta =\{0,1,2,\cdots ,m\}$. The action space of $N$ is defined by
\[\beta^{n}=\left\{(x_{1},\cdots ,x_{n}):x_{i}\in\beta\mbox{ for all }i\in N\right\}.\]
Therefore, $(x_{1},\cdots ,x_{n})$ is called the {\bf action} of $N$, and $x_{i}=k$ if and only if player $i$ takes action $\sigma_{k}$.

A multi-choice cooperative game in characteristic function form is the pair $(\beta^{n},v)$ defined by $v:\beta^{n}\rightarrow\mathbb{R}$ satisfying $v({\bf 0})=0$. A multi-choice cooperative game is said to be nondecreasing when ${\bf x}\geq {\bf y}$ implies $v({\bf x})\geq v({\bf y})$ (Hsiao and Raghavan \cite[p.242-243]{hsi93}).

Different Action Levels for Each Player.

Let $N$ be the set of players and suppose each player $i\in N$ has $m_{i}+1$ action levels. We set $M_{i}=\{0,1,\cdots ,m_{i}\}$ as the action space of player $i\in N$, where the action $0$ means not participating the coalition. The characteristic function of the cooperative game is defined by
\[v:\prod_{i\in N}M_{i}\rightarrow\mathbb{R}\mbox{ with }v({\bf 0})=0.\]
For each coalition
\[{\bf s}=(s_{1},\cdots ,s_{n})\in\prod_{i\in N}M_{i},\]
the value $v({\bf s})$ is the worth that the players can obtain, when player $i$ plays at level $s_{i}\in M_{i}$. We denote by $\mbox{MCTU}(N)$ the set of all multi-choice cooperative games with player set $N$..

For all $i\in N$ and $j\in M_{i}\setminus\{0\}$, $x_{ij}$ denotes the increase in payoff to player $i$ corresponding to a change of action
from level $j-1$ to level $j$ by this player and $x_{i0}=0$ for all $i\in N$.

A payoff vector ${\bf x}=(x_{ij})$ is called efficient when
\[\sum_{i\in N}\sum_{j=1}^{m_{i}}x_{ij}=v({\bf m}),\]
where ${\bf m}=(m_{1},\cdots ,m_{n})$.
A payoff vector ${\bf x}=(x_{ij})$ is called level increase rational when, for all $i\in N$ and $j\in M_{i}\setminus\{0\}$, $x_{ij}$ is at least the increase in worth that player $i$ can obtain, when he/she works alone and changes his/her action from level $j-1$ to level $j$, i.e.,
\[x_{ij}\geq v\left (j{\bf 1}^{\{i\}}\right )-v\left ((j-1){\bf 1}^{\{i\}}\right ).\]
A payoff vector ${\bf x}=(x_{ij})$ is called an imputation when it is efficient and level increase rational.

We denote the set of imputations of the multi-choice cooperative game $v\in MC\mbox{TU}(N)$ by ${\cal MI}(v)$. It is easily seen that ${\cal MI}(v)\neq\emptyset$ if and only if
\[\sum_{i\in N}v\left (m_{i}{\bf 1}^{\{i\}}\right )\leq v({\bf m}).\]

Given a payoff vector ${\bf x}$, if player $i$ works at the $j$th level, then this player obtains the amount $\sum_{k=0}^{j}x_{ik}$. It will often be more natural to look at these accumulated payoffs. For $i\in N$ and $j\in M_{i}$, we denote
\begin{equation}{\label{van95eqa}}\tag{30}
x_{ij}=\sum_{k=0}^{j}x_{ik}. (?????)
\end{equation}
The coalition ${\bf s}\in\prod_{i\in N}M_{i}$ obtains $\sum_{i\in N}x_{is_{i}}$.

\begin{equation}{\label{gad20}}\tag{31}\mbox{}\end{equation}

Definition \ref{gad20}. Many kinds of muti-choice cooperative games are also defined below.

The multi-choice game $(N,v)$ is called zero-normalized when the players cannot gain anything by working alone, i.e., $v(j{\bf 1}^{\{i\}})=0$ for all $i\in N$ and $j\in M_{i}$.
The multi-choice game $(N,v)$ is called additive when the worth of each coalition ${\bf s}$ equals the sum of the worth of the players when they work alone at the level they work at in ${\bf s}$, i.e.,
\begin{equation}{\label{ga18}}\tag{32}
v({\bf s})=\sum_{i\in N}v\left (s_{i}{\bf 1}^{\{i\}}\right )
\end{equation}
for all ${\bf s}\in\prod_{i\in N}M_{i}$.
For an arbitrary multi-choice game $(N,v)$, the zero-normalization of $v$ is the game $v_{0}$ that is obtained by subtracting from $v$ the additive game $a$ with $a(j{\bf 1}^{\{i\}})=v(j{\bf 1}^{\{i\}})$ for all $i\in N$ and $j\in M_{i}\setminus\{0\}$.
The multi-choice game $(N,v)$ is called balanced when, for all maps
\[\lambda :M\equiv\prod_{i\in N}M_{i}\rightarrow\mathbb{R}_{+}\mbox{ satisfying }
\sum_{{\bf s}\in M}\lambda ({\bf s}){\bf 1}^{c({\bf s})}={\bf 1}^{N},\]
it holds that
\[\sum_{{\bf s}\in M}\lambda ({\bf s})v_{0}({\bf s})\leq v_{0}({\bf m}),\]
where $v_{0}$ is the zero-normalization of $v$. Note that this definition coincides with the familiar definition of balancedness for cooperative games with ${\bf m}=(1,1,\cdots ,1)$. $\sharp$
(van den Nouweland et al. \cite[p.291-292]{van95})

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

Population Monotonic Allocation Schemes.

In most interesting economic applications, the cooperative game $(N,v)$ is super-additive such that it is efficient for the players to form the grand coalition $N$. If an allocation belongs to the core, no coalition $S$ will unanimously decide to challenge it, since there is no way to divide $v(S)$ so as to make every member of $S$ better off. But the process of coalition formation is a complex one, in which players may not necessarily achieve full efficiency. To deal with the possibility of partial cooperation, we should specify not only how to allocate $v(N)$ but also how to allocate the worth of every coalition $S$, should the players fail to fully cooperate and $S$ eventually be formed. The concern is to guarantee that once a coalition $S$ has decided upon an allocation of $v(S)$, no player will ever be tempted to induce the formation of a coalition smaller than $S$ by using his bargaining skills or by any other means. This amounts to requiring that the payoff to every player increase as the coalition to which he belongs grows larger. Formally, we are searching for what we call a population monotonic allocation scheme, in short, a PMAS.

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

Definition \ref{sprd300}. Given any coalition $S$ in $N$, we write ${\bf x}^{S}=(x_{i}^{S})_{i\in S}$. A vector ${\bf x}=({\bf x}^{S})_{S\subseteq N}=(x_{i}^{S})_{i\in S,S\subseteq N}$ is a population monotonic allocation scheme of the cooperative game $(N,v)$ when the following conditions are satisfied:

$\sum_{i\in S}x_{i}^{S}=v(S)$ for all $S\subseteq N$;
for all $S,T\subseteq N$ and $i\in S$, if $S\subseteq T$ then $x_{i}^{S}\leq x_{i}^{T}$. $\sharp$

We denote by ${\cal C}(v)$ the core of game $(N,v)$. Given any coalition $S$ in $N$, we consider the subgame $(S,v^{S})$, i.e., $v^{S}$ is the restriction of $v$ to the class $\{T:T\subseteq S,T\neq\emptyset\}$. It is apparent from the definition that if ${\bf x}$ is a PMAS of $(N,v)$, then ${\bf x}^{S}=(x_{i}^{S})_{i\in S}\in {\cal C}(v^{S})$. By definition, every game $(N,v)$ that possesses a PMAS must be totally balanced. As long as $n\leq 3$, the converse of that proposition is also true.

Proposition. Every $3$-person game that is totally balanced has a PMAS.

Let us denote by $\Pi (N)$ the set of all permutation of $N$. For $\pi\in\Pi (N)$ and $i\in N$, we let $P(\pi ,i)=\{j\in N:\pi (j)\leq\pi (i)\}$. We generalize the definition of marginal contribution as follows. Given a cooperative game $(N,v)$ and a permutation $\pi\in\Pi (N)$, the extended marginal vector associated with $\pi$ is the vector ${\bf x}^{\pi}=(x_{i}^{\pi ,S})_{i\in S,S\subseteq N}$ defined componentwise by
\begin{equation}{\label{ga31}}\tag{34}
x_{i}^{\pi ,S}=v(P(\pi ,i)\cap S)-v((P(\pi ,i)\cap S)\setminus\{i\}).
\end{equation}

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

Proposition \ref{sprp3}. If the cooperative game $(N,v)$ is convex, then every extended marginal vector is a PMAS.

The PMAS ${\bf x}^{\pi}$ penalizes those players who occupy the first positions in the ordering associated with $\pi$. For instance, if $P(\pi ,i)=\{i\}$, then player $i$ will not derive any benefit from the game. Indeed, we have $x_{i}^{\pi ,S}=v(i)$ for all $S\subseteq N$ and $i\in S$. However, we can compromise between the extreme solutions suggested by the extended marginal vectors. Shapley \cite{sha71} proved that the core of a convex game is a polytope whose extreme points are the (usual) marginal contributions. Because every convex combinatiuon of PMAS of a game $(N,v)$ is itself a PMAS of that game. We obtain the following corollary of Proposition \ref{sprp3}.

Corollary. If the cooperative game $(N,v)$ is convex and ${\bf x}=(x_{i})_{i\in N}\in {\cal C}(v)$, then there exists a PMAS ${\bf y}=(y_{iS})_{i\in S,S\subseteq N}$ satisfying ${\bf y}^{N}={\bf x}$, i.e., $y_{i}^{N}=x_{i}$ for all $i\in N$. In other words, every core allocation of a convex game can be “reached through a PMAS”. $\sharp$

The convex games are just one class of games that possesses a PMAS. Now, we want to describe the set of all such games. A player $i\in N$ is a veto player in the cooperative game $(N,v)$ when $v(S)=0$ for all $S\in P(N\setminus\{i\})$. For convenience, we call a cooperative game in which player $i$ is a veto player an $i$-veto game, and a game with at least one veto player a game with veto control. Let us recall that $(N,v)$ is an additive game if and only if $v(S\cup T)=v(S)+v(T)$ for $S,T\in 2^{N}$ and $S\cap T=\emptyset$. If a cooperative game $(N,v)$ has a PMAS, then every game obtained by adding to $(N,v)$ an additive game also has a PMAS.

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

Theorem \ref{sprt1}. (Sprumont \cite[p.383]{spr}) A zero-normalized game has a PMAS if and only if it is a positive linear combination of monotonic simple games with veto control. $\sharp$

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

Corollary \ref{sprca}. A cooperative game has a PMAS if and only if it is the sum of a positive linear combination of monotonic simple games with veto control and an additive game $(N,v_{a})$ given by $v_{a}(S)=a\cdot|S|$ for all $S\subseteq N$, where $a$ is an arbitrary real number. $\sharp$

We have the following observations.

Derks \cite{der} has shown that every nonnegative games (i.e., $v(S)\geq 0$ for all $S\subseteq N$) with nonempty core can be represented as a positive linear combination of simple games with veto control. Corollary \ref{sprca} shows that if $(N,v)$ has a PMAS, these simple games can be chosen monotonic.
A well-known result by Shapley states that every game can be written as a linear combination of unanimity games. Since unanimity games form a subset of the set of monotonic simple games with veto control, the crucial feature in Theorem \ref{sprt1} is that we can restrict ourselves to positive linear combination.
A super-additive simple game has a nonempty core if and only it is a game with veto control. That statement remains true, when “superadditive” is replaced by “monotonic”, thereby providing a nice alternative expression of Theorem \ref{sprt1}.

It may be worthwhile studying some specific classes of games for which a PMAS can be computed. We say that the cooperative game $(N,v)$ has the property of increasing average worths when
\[\frac{v(S)}{|S|}\leq\frac{v(T)}{|T|}\]
whenever $S\subseteq T\subseteq N$, and has the property of increasing relative worths when
\[\frac{v(S)}{\sum_{i\in S}v(i)}\leq\frac{v(T)}{\sum_{i\in T}v(i)}\]
whenever $S\subseteq T\subseteq N$.

Proposition. The cooperative games with increasing average worth or increasing relative worths admit a PMAS. (They can be obtained by just dividing $v(S)$ equally in the first case and in proportion to the $v(i)$’s in the second case.) $\sharp$

Let $(N,v)$ be a cooperative game and let
\[v'(S)=\frac{1}{|S|}\cdot\sum_{i\in S}\left [v(S)-v(S\setminus\{i\})\right ]\]
for all $S\subseteq N$. We say that $(N,v)$ has increasing average marginal contributions, in short, it is an IAMC game, when, for all $S,T\subseteq N$, $v'(S)\leq v'(T)$ whenever $S\subseteq T$. Clearly, many IAMC games are not convex and not all convex games have increasing average marginal contributions (Sprumont \cite[p.386]{spr}).

Proposition. Every IAMC game has a PMAS.

Proof. The proof is constructive. We define $\boldsymbol{\xi}=(\xi_{iT})_{i\in T,T\subseteq N}$ recursively as follows:
\begin{equation}{\label{spreqb}}\tag{38}
\xi_{iT}=\frac{1}{|T|}\cdot\left [v'(T)+\sum_{\{S:S\subseteq T, |S|=|T|-1,i\in S\}}\xi_{iS}\right ]
\end{equation}
with the convention that $\xi_{i\emptyset}=0$ for all $i\in N$. Then, we show that $\boldsymbol{\xi}$ is a PMAS of $(N,v)$ whenever $(N,v)$ is IAMC. $\blacksquare$

We see that if the cooperative game $(N,v)$ is an IAMC game, then the PMAS can be obtained by the recursive formula (\ref{spreqb}).

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

Clan Games.

Big Boss Games.

Games with one big player generated from economic systems have been often studied in different contexts, e.g.,

a market of an indivisible good with one seller and many buyers;
a bankruptcy problem with one big claimant;
a production economy with one landowner and many peassants;
an information good market with one possessor of information and many demanders.
(Muto et al. \cite[p.303]{mut88}).

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

Definition \ref{mut88d1}. The monotonic game $(N,v)$ is called a big boss game when there is one player, denoted by $i^{*}$, satisfying the following conditions.

We have $v(S)=0$ if $i^{*}\not\in S$. This condition means that player $i^{*}$ is very powerful, i.e., coalitions not containing $i^{*}$ cannot get anything.
We have $v(N)-v(S)\geq\sum_{i\in N\setminus S}\left (v(N)-v(N\setminus\{i\})\right )$ if $i^{*}\not\in S$. This condition means that, for every coalition not containing $i^{*}$, its contribution to the grand coalition is not less than the sum of the contributions of its players to the grand coalition. $\sharp$

We see that a big boss game $v$ is super-additive because of the monotonicity of $v$ and the first condition. We denote a set of all big boss games with the set of players $N$ and with the powerful player $i^{*}$ by $BBG_{i^{*}}^{N}$. We also see that $BBG_{i^{*}}^{N}$ forms a cone in $\mbox{TU}(N)$, i.e., for all $v,w\in BBG_{i^{*}}^{N}$ and real numbers $a,b\geq 0$, $av+bw$ is also in $BBG_{i^{*}}^{N}$. For simplicity, we take $i^{*}=1$ and denote $BBG_{1}^{N}$ simply by $BB\mbox{TU}(N)$ throughout the discussion (Muto et al. \cite[p.304]{mut88}).

We consider the following condition.
\begin{equation}{\label{mut88eq10}}\tag{40}
\mbox{for all $S,T\subseteq N$ such that $1\in S\subseteq T$, we have $v(T)-v(S)\geq\sum_{i\in T\setminus S}m_{i}(v)$.}
\end{equation}
This condition implies that, for every coalition not containing the big boss $1$, its contribution to its proper super set containing player $1$ is not less than the sum of the marginal contribution of its players to the grand coalition. We easily notice that condition (\ref{mut88eq10})
implies condition (ii) in Definition~\ref{mut88d1}. Let us consider one more condition presented below.
\begin{equation}{\label{mut88eq11}}\tag{41}
\mbox{for all $\{1\}\subseteq S\subseteq N$ with $\{1\}\neq S$, we have
$v(S)-v(S\setminus\{i\})\geq m_{i}(v)\mbox{ for all }i\in S\setminus\{1\}$.}
\end{equation}
Condition (\ref{mut88eq11}) says that, for each of the weak players $2,\cdots ,n$, his/her contribution to each of the coalitions containing player $1$ is not less than his/her marginal contribution to the grand coalition (Muto et al. \cite[p.312]{mut88}).

Proposition. Conditions (\ref{mut88eq10}) and (\ref{mut88eq11}) are equivalent for all games in $\mbox{TU}(N)$. $\sharp$

\begin{equation}{\label{mut88d2}}\tag{42}\mbox{}\end{equation}

Definition. \ref{mut88d2}. We call a monotonic game $v$ satisfying condition (i) in Definition \ref{mut88d1} and condition (\ref{mut88eq10}) (or condition (\ref{mut88eq11}) a strong big boss game. $\sharp$

A veto player of a game $(N,v)$ is a player $i\in N$ that is necessary to obtain a positive payoff, i.e., $v(S)=0$ for all coalitions $S$ not containing player $i$. A game $(N,v)$ is a veto-rich game when it has at least one veto player $i$. Note that we do not require a veto-rich game to be nonnegative. However, the name “veto player” seems to imply a veto player occupies a strong position, which is not true if some coalitions containing the veto players have negative worth while all coalitions which do not contain all veto players have zero worth. Clearly, a game $(N,v)$ with veto player $i$ has imputations if and only if $v(N)\geq v(i)$. The class $VG_{i}^{N}$ of veto-rich games with fixed player set $N$ and a fixed veto player $i$ which have imputations is a convex cone $\mbox{TU}(N)$; that is, if $v$ and $w$ are veto-rich games with veto player $i$, then so is $\alpha v+\beta w$ for all nonnegative numbers $\alpha$ and $\beta$. (Arin and Feltkamp \cite{ari97}).

Clan Games.

Many social conflict situations can be understood as conflicts of the rich versus the poor, the influential versus the powerless agents. In such situations, the powerless agents can often strengthen their influence by showing a kind of solidarity. The cooperative games we define here, clan games, are meant to describe and analyze such conflicts. The set of influential agents will be called the clan and we exaggerate their influence a little by posing that no positive result can be attained unless all clan members cooperate. The value of solidarity will appear from the fact that it is more profitable for any coalition of powerless agents to enter into negotiation with the clan as a group than to act as an individual. Examples of conflicts of this kind are given below:

the controversy between “big” and “small” claimants in a case of bankruptcy;
controversy between the owners of the means of production and the laborers in a wage conflict;
the potential controversy between the permanent members of the UN council with veto power and the other members.

The two essential features of all these conflicts are the existence of agents with veto power and the fact that solidarity of the powerless agents pays (Potters et al. \cite[p.275-276]{pot89}).

\begin{equation}{\label{pot89d1}}\tag{43}\mbox{}\end{equation}

Definition \ref{pot89d1}. (Potters et al. \cite[p.276]{pot89}) A cooperative game $(N,v)$ is called a clan game when the function $v:2^{N}\rightarrow\mathbb{R}$ satisfies the following conditions.

We have $v(S)\geq 0$ for all $S\subseteq N$ and $m_{i}(v)= v(N)-v(N\setminus\{i\})\geq 0$ for all $i\in N$.
There is a nonempty coalition $C\subseteq N$ satisfying
\[\left\{\begin{array}{ll}
v(S)=0 & \mbox{if $C\not\subseteq S$ ({\bf clan property})}\\
{\displaystyle v(N)-v(S)\geq\sum_{i\in N\setminus S}m_{i}(v)} & \mbox{if $C\subseteq S$ ({\bf union property}).}
\end{array}\right .\]
The coalition $C\subseteq N$ is regarded as a clan in the game.

We denote by $G_{C}^{N}$ the set of all clan games with clan $C$. $\sharp$

The following set of clan games with clan $C$ is a basis of $G_{C}^{N}$:

for $i\in N\setminus C$,
\[v_{i}(S)=\left\{\begin{array}{ll}
1, & \mbox{if $|S|\geq n-1$ and $i\in S$}\\ 0, & \mbox{otherwise};
\end{array}\right .\]
for $C\subseteq T$ and $|T|\leq n-2$,
\[v^{T}(S)=\left\{\begin{array}{ll}
1, & \mbox{if $|S|\geq n-1$ or $S=T$}\\ 0, & \mbox{otherwise};
\end{array}\right .\]
$v(S)=1$ if $|S|\geq n-1$ and $v(S)=0$ otherwise.

It is clear that these $2^{n-|C|}$ simple clan games are linearly independent. Hence the dimension of $G_{C}^{N}$ is $2^{n-|C|}$ (Potters et al. \cite[p.287]{pot89}).

We define ${\cal P}(C)=\{S\subseteq N:C\subseteq S\}$ as the collection of coalitions including all clan members. According to the clan property, these are the only coalitions that can possibly attain a positive value. It is more profitable for any coalition of non-clan members to enter into negotiations with the clan as a group than to act as an individual; this is referred to as the union property. (Voorneveld et al. \cite[p.441]{voo02}).

Example. (Potters et al. \cite[p.276]{pot89}) (Bankcruptcy, big claimants vs. small claimants). Suppose a firm goes bankcruptcy leaving an estate with value $E>0$ and $n$ creditors $1,\cdots ,n$ with claims ${\bf d}=(d_{1},\cdots ,d_{n})>{\bf 0}$. We assume that $\sum_{i\in N}d_{i}>E$. In order to find a fair division of the estate among the creditors, the cooperative game $(N,v_{E|{\bf d}})$ is given by
\[v_{E|{\bf d}}(S)=\max\left\{\{E-\sum_{i\in N\setminus S}d_{i},0\right\}.\]
This means that the value of a coalition is what is left if the other creditors have gitten their claims. It is known that $v_{E|{\bf d}}$ is a convex game. We can show that a bankcruptcy game $(N,v_{E|{\bf d}})$ is a clan game if and only if $S_{0}\equiv\{i\in N:d_{i}\geq E\}\neq\emptyset$ and $\sum_{i\in N\setminus S_{0}}d_{i}\leq E$. It says that $(N,v_{E|{\bf d}})$ is a clan game if there are creditors with claims at least as large as the value of the total estate and creditors with small claims, together not exceeding the value of the estate. Note that, if a bankcruptcy game is a clan game, the union property holds with equalities and that the “big” claimants form the clan. Only in the case where all claimants are big creditors ($N=S_{0}$) can we also take every coalition with $n-1$ players as the clan. $\sharp$

Example. (Potters et al. \cite[p.277]{pot89})(Owners of the means of production vs. laborers). Suppose in a region there is one landowner $L$, one owner of agricultural implements $P$, and $n$ landless peasants. Let there be give a function $f:\{0,1,\cdots ,n\}\rightarrow\mathbb{R}$ which is monotonic increasing and $f(0)=0$. The value $f(s)$ denotes the net earnings obtained if $s$ peasants cultivate the land of the landowner $L$ using the machine $P$. The players sets is given by $N’=\{L,P,1,\cdots ,n\}$ and the characteristic function is defined by
\[v(S)=0\mbox{ if }\{L,P\}\not\subseteq S\mbox{ and }v(S’)=f(|S|)\mbox{ if }S’=S\cup\{L,P\}.\]
We can show that the game $(N,v)$ is a clan game with clan $\{L,P\}$ if and only if $f(n)-f(s)\geq (n-s)\cdot(f(n)-f(n-1))$ for all $s=0,1,2,\cdots ,n-2$. $\sharp$

It is easy to see that $G_{C}^{N}$ is a cone in $\mbox{TU}(N)$, since conditions in Definition \ref{pot89d1} are linear inequalities in the variables $\{v(S):S\neq\emptyset\}$. A clan game $(N,v)$ with clan $C$ is an extreme direction of $G_{C}^{N}$ if and only if $v=v_{1}+v_{2}$ with $v_{1},v_{2}\in G_{C}^{N}$ implies $v_{1}=\lambda_{1}v$ and $v_{2}=\lambda_{2}v$ with $\lambda_{1},\lambda_{2}>0$ (Potters et al. \cite[p.283]{pot89}).

Proposition. A clan game $(N,v)$ with clan $C$ is an extreme direction of $G_{C}^{N}$ if and only if $(N,v)$ is a multiple of a simple clan game with clan $C$. $\sharp$

Total Clan Games.

We have introduced clan games to model social conflicts between powerful players (clan members) and powerless players (non-clan members), in which the powerful players have veto power, and the powerless players operate more profitably in unions than on their own. Here we consider total clan games: cooperative situations in which the game itself and each of its subgames can be modeled as a clan game (Voorneveld et al. \cite[p.439]{voo02}).

A player $i\in N$ is a veto player if $v(S)=0$ whenever $i\not\in S$. Each clan member is a veto player. In many games $(N,v)$ arising from practical situations, the subgames $(S,v^{S})$ inherit the structure of the original game. For example, every subgame of a flow game is a flow game, every subgame of a linear production game is a linear production game and every subgame of a bankcruptcy game is a bankcruptcy game. Similarly, it is easy to imagine that in practical situation giving rise to clan games, the same distinction between powerful and powerless players will exist in its subgames. We refer to clan games in which every subgame that contains the clan is again a clan game. A cooperative game $(N,v)$ is a {\bf total clan game} with clan $C$ if and only if the subgame $(S,v^{S})$ is a clan game with clan $C$ for every coalition $S\in {\cal P}(C)$, where ${\cal P}(C)$ is the collection of coalitions including all clan members. (Voorneveld et al. \cite[p.441]{voo02}).

For each coalition $\emptyset\neq S\subseteq N$ and each player $i\in S$, we recall that $m_{i}(S,v)=v(S)-v(S\setminus\{i\})$ is the marginal contribution of player $i$ to coalition $S$. We assume the clan $\emptyset\neq C\neq N$.

\begin{equation}{\label{voo02t1}}\tag{44}\mbox{}\end{equation}

Theorem \ref{voo02t1}. (Voorneveld et al. \cite[p.442]{voo02}) Let $(N,v)$ be a cooperative game and $\emptyset\neq C\subset N$ with $C\neq N$. The following statements are equivalent.

(a) $(N,v)$ is a total clan game with clan $C$.
(b) $(N,v)$ is monotonic, every player $i\in C$ is a veto player, and, for all $S,T\in {\cal P}(C)$, if $S\subseteq T$ then $v(T)-v(S)\geq\sum_{i\in T\setminus S}m_{i}(T,v)$.
(c) $(N,v)$ is monotonic, every player $i\in C$ is a veto player, and, for all $S,T\in {\cal P}(C)$, if $S\subseteq T$ and $i\in S\setminus C$ then $m_{i}(S,v)\geq m_{i}(T,v)$. $\sharp$

Let us recall that a PMAS specifies, for each coalition $S\subseteq N$, an allocation of $v(S)$ over its members. Moreover, it reflects the intuition that there is “strength in numbers”: the share allocated to every player increases as the colaition to which he/she belongs grows larger. When we consider PMAS in total clan games, we restrict attention to the allocation of $v(S)$ for coalitions $S\in {\cal P}(C)$, since other coalitions have value zero by the clan property. Let $(N,v)$ be a total clan game with clan $C$. A PMAS for the game $(N,v)$ is a vector $(x_{i}^{S})_{S\in {\cal P}(C),i\in S}$ of real numbers such that, for all $S\in {\cal P}(C)$, $\sum_{i\in S}x_{i}^{S}=v(S)$ and, for all $S,T\in {\cal P}(C)$ and all $i\in S$, if $S\subseteq T$ then $x_{i}^{S}\leq x_{i}^{T}$. An imputation ${\bf y}\in {\cal I}(v)$ is
{\bf PMAS extendable} if there exists a PMAS, say $(x_{i}^{S})_{S\in {\cal P}(C),i\in S}$, such that $x_{i}^{N}=y_{i}$ for each player $i\in N$. (Voorneveld et al. \cite[p.443]{voo02}).

Theorem. Let $(N,v)$ be a total clan game with clan $C$. If ${\bf y}\in C(v)$ then ${\bf y}$ is PMAS extendable. $\sharp$

Whereas a PMAS allocates a larger payoff to each players as the coalitions grow larger, property (iii) in Theorem~\ref{voo02t1} suggests a slightly different approach in total clan games: the marginal contribution of non-clan members actually decreases in a larger coalition. Think of instance of the clan members as owners of production facilities and the non-clan members as laborers: one can easily imagine their marginal product of labor to be decreasing in the face of more co-workers. Taking the decreasing influence of non-clan members into account, one might actually allocate a smaller amount to the non-clan members in larger coalitions. Moreover, to still maintain some stability, such allocations should still rise to core allocation in the subgames. An allocation scheme satisfying these properties is called a bi-monotonic allocation scheme (bi-MAS). Let $(N,v)$ be a total clan game with clan $C$. A bi-MAS for the game $(N,v)$ is a vector $(x_{i}^{S})_{S\in {\cal P}(C),i\in S}$ of real numbers such that the following conditions are satisfied:

for each $S\in {\cal P}(C)$, we have $\sum_{i\in S}x_{i}^{S}=v(S)$;
if $S,T\in {\cal P}(C)$ with $S\subseteq T$ and $i\in S\cap C$, then $x_{i}^{S}\leq x_{i}^{T}$;
if $S,T\in {\cal P}(C)$ with $S\subseteq T$ and $i\in S\setminus C$, then $x_{i}^{S}\geq x_{i}^{T}$;
the vector $(x_{i}^{S})_{i\in S}$ is a core element of the subgame $(S,v^{S})$ for each coalition $S\in {\cal P}(C)$.

As before, attention is restricted to coalitions containing the clan, since other coalitions have value zero by the clan property. A straightforward extension of the definition of bi-MAS that also includes coalitions in $2^{N}\setminus {\cal P}(C)$ would then allocate zero to all players in such a coalition. An imputation ${\bf y}\in {\cal I}(v)$ is bi-MAS extendable when there exists a bi-MAS $(x_{i}^{S})_{S\in {\cal P}(C),i\in S}$ such that $x_{i}^{N}=y_{i}$ for each player $i\in N$. (Voorneveld et al. \cite[p.445]{voo02}).

Theorem. Let $(N,v)$ be a total clan game with clan $C$. If ${\bf y}\in C(v)$, then ${\bf y}$ is bi-MAS extendable. $\sharp$

The total clan game $(N,v)$ is called a total big boss game when the clan $C$ consisting of a single player.

Theorem. Let $(N,v)$ be a total big boss game. For each $S\in {\cal P}(C)$ and $i\in S$, where $|C|=1$, we define $x_{i}^{S}$ as the payoff to player $i\in S$ in the nucleolus of the clan game $(S,v^{S})$. Then $(x_{i}^{S})_{S\in {\cal P}(C),i\in S}$ is a bi-MAS. $\sharp$

\begin{equation}{\label{f}}\tag{F}\mbox{}\end{equation}

Restricted Games.

The formation of coalitions is a fundamental problem in game theory. By a “coalition” is meant a group of “players” (e.g., economic or political agents) which decide to act together, as one unit, relative to the rest of the players. This includes the instances of syndicates, unions, cartels, blocks, political parties, parliamentary coalitions, etc. We would like to emphasize that forming a coalition does not eliminate the individual players as decision makers. In all interactions with the other players, coalition members act as one unit (it may be useful to think of a “representative agent” taking their place); however, this arrangement will continue only as long as each player finds it desirable to act this way. Further bargaining occurs among the members of each coalition on how to divide what they obtained together. Thus, the existence of coalitions implies that the interactions among the players will be conducted on two levels: among the coalitions and within each coalition (Hart and Kurz \cite[p.1047]{har83}).

\begin{equation}{\label{gad17}}\tag{45}\mbox{}\end{equation}

Definition \ref{gad17}. A game with restricted cooperation is a quadruple $\Gamma =(N,{\cal F},v,\lambda )$, where

$N$ is the finite set of players,
${\cal F}$ is a nonempty collection of subsets of $N$ called feasible coalitions,
$v:{\cal F}\rightarrow\mathbb{R}$ is the value function with $v(\emptyset )=0$,
$\lambda\in\mathbb{R}$ is the value of the game $\Gamma$. $\sharp$

If $v$ and $\lambda$ are nonnegative, then $\Gamma$ is called a positive game. We call the game $\Gamma =(N,{\cal F},v,\lambda )$ balanced when, for all $S_{1},\cdots ,S_{k}\in {\cal F}$ and a positive integer $m\in\mathbb{N}$,
\[\frac{1}{m}\sum_{i=1}^{k}1_{S_{i}}=1_{N}\mbox{ implies }\frac{1}{m}\sum_{i=1}^{k}v(S_{i})\leq\lambda ,\]
where $1_{A}$ is the indicator function of $A$. (Faigle \cite[p.412]{fai89}).

Games with Coalition Structure.

One of the problems of cooperative game theory concerns the question how to allocate the value generated cooperatively by the group of players in a fair way to the individual players. In the original model for a cooperative game, any subset of players is assumed to be free to form a coalition in its own right. A cooperative game may thus simply be viewed as a real-valued function defined on the collection of all nonempty subsets of players. It turns out, however, that the original model where every subset of players may occur as a feasible coalition is often inappropriate. Cooperation among players might be restricted by pre-imposed constraints (Faigle and Kern \cite[p.249-250]{fai92}).

Let $(N,v)$ be a cooperative game.

It is sometimes useful to constrain the set of payoff vector under consideration to a subset $X$ of $\mathbb{R}^{N}$. We define a
constrained game to be a triple $(N,v,X)$, where $X\subseteq\mathbb{R}^{N}$.
A coalition structure ${\cal B}=\{B_{1},\cdots ,B_{p}\}$ on $N$ is a partition of $N$. A {\bf game with coalition structure ${\cal B}$} is a triple $(N,v,{\cal B})$.

Given a game with coalition structure $(N,v,{\cal B})$, we can define the constrained game $(N,v,X_{\cal B})$ such that the set of constraints on the set of payoff vectors is defined by
\begin{equation}{\label{aum74eqa}}\tag{46}
X_{\cal B}=\left\{{\bf x}\in\mathbb{R}^{N}:\sum_{i\in B_{k}}x_{i}=v(B_{k})
\mbox{ for all }k\mbox{ and }x_{i}\geq v(i)\mbox{ for all }i\right\}.
\end{equation}
We also find it convenient to define
\begin{equation}{\label{aum74eqb}}\tag{46}
X_{k}=\left\{{\bf x}\in\mathbb{R}^{B_{k}}:\sum_{i\in B_{k}}x_{i}=v(B_{k})
\mbox{ and }x_{i}\geq 0\mbox{ for all }i\in B_{k}\right\}.
\end{equation}
Let us recall that a $0$-normalized game is a game for which $v(i)=0$ for all $i$. If $(N,v)$ is a $0$-normalized game, then $X_{\cal B}=\prod_{k}X_{k}$ (Aumann and Dreze \cite[p.219]{aum74}).

Let ${\cal B}=\{B_{1},\cdots ,B_{m}\}$ be a coalition structure for a cooperative game $(N,v)$. Heuristically, a coalition structure represents the “breaking up” of the set $N$ into mutually disjoint coalitions. Suppose such a structure is reached. We assume that each of the coalitions $B_{k}$ which forms will receive the amount $v(B_{k})$ to be divided among its members. The question is how this amount will be divided. A payoff configuration is a pair $({\bf x};{\cal B})=(x_{1},\cdots ,x_{n};B_{1},\cdots ,B_{m})$ satisfying
\begin{equation}{\label{oweeq1311}}\tag{48}
\sum_{i\in B_{k}}x_{i}=v(B_{k})
\end{equation}
for all $k=1,\cdots ,m$. We wish to know which payoff configurations will be reached. An obvious requirement will be that of individual rationality, i.e., we may demand
\begin{equation}{\label{oweeq1312}}\tag{49}
x_{i}\geq v(i)\mbox{ for all }i\in N.
\end{equation}
A further possible requirement may be that no coalition $B_{k}$ will form if one of its subcoalitions can obatin more than the payoff vector ${\bf x}$ gives it. Thus
\begin{equation}{\label{oweeq1313}}\tag{50}
\sum_{i\in S}x_{i}\geq v(S)\mbox{ for }S\subseteq B_{k}\in {\cal B}.
\end{equation}
It is clear that (\ref{oweeq1313}) is stronger than (\ref{oweeq1312}). On the other hand, the necessity for (\ref{oweeq1313}) is not as clear as that for (\ref{oweeq1312}). The payoff configuration satisfying (\ref{oweeq1313}) will be called coalitionally rational and it will be called individually rational if it satisfies only (\ref{oweeq1312}) (Owen \cite[p.314]{owe}).

Let ${\cal B}=\{B_{1},\cdots ,B_{m}\}$ be a coalition structure, and let $K$ be a coalition. Then, by the {\bf partners} of $K$ in ${\cal B}$, we mean the set
\begin{equation}{\label{ga23}}\tag{51}
P(K;{\cal B})=\left\{i\in B_{k}:B_{k}\cap K\neq\emptyset\right\}.
\end{equation}
Note that each member of $K$ is also a partner of $K$. The idea is that, for the members of $K$ to get their share of the coalitionally rational payoff configuration $({\bf x};{\cal B})$, they need the consent of their partners and no other.

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

Definition \ref{aum74d1}. (Aumann and Dreze \cite[p.219]{aum74}) Let $\pi$ be a permutation on $N$. We call a coalition structure ${\cal B}=\{B_{1},\cdots ,B_{p}\}$ is invariant under $\pi$ when $\pi B_{k}=B_{k}$ for all $k$. $\sharp$

Given a game $(N,v,{\cal B})$, a payoff vector ${\bf x}$ and a coalition $B_{k}\in {\cal B}$, we define a game $(B_{k},v_{\bf x}^{*})$ by
\begin{equation}{\label{aum74eqc}}\tag{53}
v_{\bf x}^{*}(S)=\left\{\begin{array}{ll}
{\displaystyle \max_{T\subseteq N\setminus B_{k}}\left [v(S\cup T)-
\sum_{i\in T}x_{i}\right ]} & \mbox{if $\emptyset\neq S\subseteq B_{k}$
with $S\neq B_{k}$}\\
v(S) & \mbox{if $S=\emptyset$ or $S=B_{k}$}.
\end{array}\right .
\end{equation}
Obviously, $v_{\bf x}^{*}(S)\geq v(S)$ for every ${\bf x}$. Note that $v_{\bf x}^{*}$ need not be $0$-normalized, even when $v$ is (Aumann and Dreze \cite[p.220]{aum74}).

\begin{equation}{\label{aum74d4}}\tag{54}\mbox{}\end{equation}

Definition \ref{aum74d4}. {(Aumann and Dreze \cite[p.220]{aum74}). Let $Z$ be a subset of $\mathbb{R}^{N}$ and $B$ a subset of $N$. For every ${\bf y}$ in the projection of $Z$ on $\mathbb{R}^{N\setminus B}$, we define the {\bf section} of $Z$ at ${\bf y}$ as $\{{\bf w}\in \mathbb{R}^{B}:({\bf w},{\bf y})\in Z\}$. $\sharp$

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

Definition \ref{aum74d3}. (Aumann and Dreze \cite[p.220]{aum74}). Let ${\cal B}=\{B_{1},\cdots ,B_{p}\}$ be a partition of $N$. The game $(N,v)$ is called decomposable with partition ${\cal B}$ when, for all $S$,
\[v(S)=\sum_{k=1}^{p}v(S\cap B_{k}). \sharp\]

Games with Permission Structures.

The goal is to analyze the consequences of the adoption of a hierarchical authority structure on the set of players in the context of a cooperative game with transferable utilities. In this analysis, we suppose that the authority structure is exogenously given and puts certain constraints on the behavior of the players in the game. The motivation to analyze the consequences of a hierarchical authority structure on a cooperative game is that in many economic organizations one spots a hierarchical authority structure. Here we consider an abstract authority structure in which certain players dominate certain players in the sense that the superior have well specified veto power over the activities undertaken by their subordinates.

We introduce a type of asymmetry between players in a cooperative game with side payments. We describe an organization in which each player has veto power over the activities as performed by a specified collection of players. So, all players in the game are dominating a collection of other players in the sense that they have veto power over the actions undertaken by these players (Gilles et al. \cite[p.277]{gil}).

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

Example \ref{gilee}. (Gilles et al. \cite[p.278]{gil}). We consider the interaction between a potential seller and two potential buyers of some object. The seller values the object at 10 dollars, the first buyer values it at 20 dollars, and the second buyer values it at 30 dollars. Let $N=\{1,2,3\}$ with $v$ defined by $v(\emptyset )=0$, $v(\{1\})=10$, $v(\{2\})=v(\{3\})=0$, $v(\{1,2\})=20$, $v(\{1,3\})=30$, $v(\{2,3\})=0$ and $v(N)=30$. Now we introduce the additional information that the seller, i.e., player 1, only has the right to use the object, but that the property rights are in the hands of the first buyer, i.e., player 2. This implies that the seller has to get permission from the first buyer with respect to the sale of the object. In other words, this means that player 2 can veto the sale of the object. In stead of the game $(N,v)$ as described above, we have to describe the new situation with the use of a modified game $(N,u)$, where $u$ is given by $u(\emptyset )=u(\{1\})=u(\{2\})=u(\{3\})=0$, $u(\{1,2\})=20$, $u(\{1,3\})=u(\{2,3\})=0$ and $u(N)=30$. $\sharp$

Example \ref{gilee} illustrates the consequences of the separation between property rights and user rights. It is our purpose to separate the (potential) individual abilities as described by the game from the behaviouristic rules or the organization structure such as the separation of property rights from user rights. We refer to the interpretation of the dominance structure as considered in the example, in which a player has to get permission from all her/his superiors to pursue a certain goal, as the conjunctive approach. In the disjunctive approach, it is assumed that every player has to get permission from at least one of her/his superiors (Gilles et al. \cite[p.278]{gil}).

Example. (Gilles and Owen \cite[p.3]{gil99}). We consider the three-player example of a hierarchical production situation. In a conjunctive hierarchy, player $1$ has to obtain permission to produce from both his superiors, who are players $2$ and $3$. Hence, this conjunctive production situation can be represented as a game $v_{c}:2^{N}\rightarrow\mathbb{R}$ with $v_{c}(N)=1$ and $v_{c}(E)=0$ for any $E\subset N$ with $E\neq N$. In constrast, within a disjunctive hierarchy, player 1 has to obtain permission to produce from either player $2$ or $3$ or both. Such a production situation can be represented by a game $v_{d}:2^{N}\rightarrow\mathbb{R}$ with $v_{d}(E)=1$ if $E$ is equal to $\{1,2\}$, $\{1,3\}$ or $\{1,2,3\}$ and $v_{d}(E)=0$ otherwise. The game $v_{d}$. $\sharp$

A permission structure on $N$ is a set-valued function $F:N\rightarrow 2^{N}$. In this setting, $j\in F(i)$ means that player $i$ is a superior of player $j$ in the permission structure $F$ on $N$. We call a player $j\in F(i)$ a successor of $i$ in $F$.

\begin{equation}{\label{gildb}}\tag{57}\mbox{}\end{equation}

Definition \ref{gildb}. (Gilles et al. \cite[p.280]{gil}). For every permission structure $F$, we can introduce its transitive closure by the set-valued function $\widehat{F}:N\rightarrow 2^{N}$. For every player $i\in N$, we define $j\in\widehat{F}(i)$ if there exists a sequence $\{h_{1},\cdots ,h_{m}\}\subseteq N$ with $h_{1}=i$ and $h_{m}=j$, and, for every $1\leq k\leq m-1$, $h_{k+1}\in F(h_{k})$. $\sharp$

We call the players in the collection $\widehat{F}(i)$ the subordinates of player $i$ in the permission structure $F$. Similarly, we denote by $\widehat{F}^{-1}(i)=\{j\in N:i\in\widehat{F}(j)\}$ the collection of the superiors of player $i\in N$ in the permission structure $F$ on $N$. Furthermore, for every coalition $S\subseteq N$, we define $F(S)=\bigcup_{i\in S}F(i)$. Analogously, we define $\widehat{F}(S)=\bigcup_{i\in S}\widehat{F}(i)$ and $\widehat{F}^{-1}(S)=\bigcup_{i\in S}\widehat{F}^{-1}(i)$. A game with permission structure is a triple $(N,v,F)$ (Gilles et al. \cite[p.280]{gil}).

The Conjunctive Approach.

Let $(N,v,F)$ be a game with permission structure. In the sequel, we explicitly assume that the members of $S$ cannot act without permission from all their predecessors. In this case, coaliton $S$ can only count on the cooperation of those $i\in S$, who do not require outside permission for their acts. We refer to the interpretation as described above as the {\bf conjunctive approach} to games with permission structure. In other words, a player needs permission from all of his/her superiors before he/she can act. This means that a coalition $S\subseteq N$ is formable if and only if all superiors of the players in $S$ are also part of $S$, i.e., $\widehat{F}^{-1}(S)\subseteq S$. Therefore we propose the following definition (Gilles et al. \cite[p.280]{gil} and Van den Brink and Giles \cite[p.115]{van96}).

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

Definition \ref{gilde}. (Gilles et al. \cite[p.281]{gil}). Let $F$ be a permission structure on $N$. The coalition $S\subseteq N$ is conjunctively autonomous in $F$ when $\widehat{F}^{-1}(S)\subseteq S$. The collection of all conjunctively autonomous coalitions in $F$ is denoted by $\Phi_{F}^{C}$. $\sharp$

The definition shows explicitly that all superiors of the players in a conjunctively autonomous coalition are also member of that coalition. According the conjunctive approach, the conjunctively autonomous coalitions are essentially the only coalitions that can generate the payoff within a game with a permission structure (Gilles et al. \cite[p.281]{gil}).

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

Definition \ref{gilda}. (Gilles et al. \cite[p.280]{gil}). Let $F$ be a permission structure on $N$. We say that $F$ is asymmetric when, for every pair $i,j\in N$, $j\in F(i)$ implies $i\not\in F(j)$. $\sharp$

We remark that asymmetry of the permission structure $F$ implies that it also satisfies irreflexity, i.e., for every player $i\in N$, it holds that $i\not\in F(i)$.

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

Proposition \ref{gilp32}. (Gilles et al. \cite[p.281]{gil}). Let $F$ be an asymmetric permision structure on $N$. Then the collection $\Phi_{F}^{C}$ of conjunctively autonomous coalitions satisfies the following properties:

$\emptyset\in\Phi_{F}^{C}$;
$N\in\Phi_{F}^{C}$;
For all $S,T\in\Phi_{F}^{C}$, it holds that $S\cup T\in\Phi_{F}^{C}$ and $S\cap T\in\Phi_{F}^{C}$. $\sharp$

Proposition \ref{gilp32} shows that there exists a largest conjunctively autonomous subset and a smallest conjunctively autonomous superset. This leads to the following definition

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

Definition \ref{gild99}. (Gilles et al. \cite[p.281]{gil}). Let $F$ be an asymmetric permission structure and $S\subseteq N$. The sovereign part of $S$ in $F$ is the set
\[\sigma_{C}(S)=\bigcup\{T:T\subseteq S,T\in\Phi_{F}^{C}\}=S\cap\widehat{F}(N\setminus S).\]
The authorizing set of $S$ in $F$ is given by
\[\alpha_{C}(S)=\bigcap\{T:S\subseteq T,T\in\Phi_{F}^{C}\}=S\cup\widehat{F}^{-1}(S). \sharp\]

We see that $\sigma_{C}(S)$ is the largest conjunctively autonomous coalition, which is contained in $S$. In the framework of the conjunctive approach, it is clear that a coalition $S\subseteq N$ can maximally obtain the payoff generated by its sovereign part $\sigma_{C}(S)$. On the other hand, the authorizing set $\alpha_{C}(S)$ of $S$ is precisely the smallest conjunctively autonomous coalition, which contains all members of $S$ as well as their superiors (Gilles et al. \cite[p.281]{gil}).

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

Example \ref{gile34} (Gilles et al. \cite[p.282]{gil}). Consider the player set $N=\{1,2,3,4,5\}$ and the permission structure $F:N\rightarrow 2^{N}$ given by $F(1)=\{2,3,4\}$, $F(2)=\{4\}$, $F(3)=\{5\}$, $F(4)=\{6\}$, $F(5)=F(6)=\emptyset$. Therefor, we have three hierarchical chains $1\rightarrow 2\rightarrow 4\rightarrow 6$, $1\rightarrow 3\rightarrow 5$ and $1\rightarrow 4\rightarrow 6$. Take $S=\{1,4,6\}$, then $F(N\setminus S)=\{4,5\}$. Clearly, since $S\cap F(N\setminus S)=\{4\}$, the coalition $S$ is not conjunctively autonomous. As $\widehat{F}(N\setminus S)=\{4,5,6\}$, the sovereign part of $S$ is given by $\sigma_{C}(S)=S\setminus\widehat{S}(N\setminus S)=\{1\}$. Furthermore, the authorizing set of $S$ is just $\alpha_{C}(S)=\{1,2,4,6\}$. $\sharp$

Proposition (Gilles et al. \cite[p.282]{gil}). Let $S$ and $T$ be two coalitions in $N$. Then, we have the following properties:

$\sigma_{C}(S)\bigcup\sigma_{C}(T)\subseteq\sigma_{C}(S\cup T)$;
$\sigma_{C}(S)\bigcap\sigma_{C}(T)=\sigma_{C}(S\cap T)$;
$\alpha_{C}(S)\bigcup\alpha_{C}(T)=\alpha_{C}(S\cup T)$;
$\alpha_{C}(S)\bigcap\alpha_{C}(T)\subseteq\alpha_{C}(S\cap T)$. $\sharp$

Let $F$ be a permission structure on $N$. We write
\[P\mbox{SG}(N)_{F}=\{v\in \mbox{TU}(N):v(S)=v(\sigma_{C}(S))\mbox{ for all }S\subseteq N\}.\]
We also introduce the mapping ${\cal R}_{F}^{C}:\mbox{TU}(N)\rightarrow P\mbox{SG}(N)_{F}$

\begin{equation}{\label{van96d1}}\tag{63}\mbox{}\end{equation}

Definition \ref{van96d1} (Van den Brink and Giles \cite[p.116]{van96}). Let $F$ be a permission structure. Given a cooperative game $(N,v)\in \mbox{TU}(N)$, the game ${\cal R}_{F}^{C}(v)\in P\mbox{SG}(N)_{F}$ is called the {\bf conjunctive restriction} of $v$ on $F$ when it satisfies ${\cal R}_{F}^{C}(v)(S)=v(\sigma_{C}(S))$ for all $S\subseteq N$. $\sharp$

We see that the mapping ${\cal R}_{F}^{C}$ assign each game $v\in \mbox{TU}(N)$ its conjunctive restriction ${\cal R}_{F}^{C}(v)\in P\mbox{SG}(N)_{F}$. It is evident that ${\cal R}_{F}^{C}$ is a linear mapping. We recall the unanimity game defined in (\ref{ga2*11}).

\begin{equation}{\label{gilt42}}\tag{64}\mbox{}\end{equation}

Theorem \ref{gilt42} (Gilles et al. \cite[p.284]{gil}). We have the following properties.

(i) For any coalition $S\neq\emptyset$ in $N$, we have ${\cal R}_{F}^{C}(u_{S})=u_{\alpha_{C}(S)}$.

(ii) Let $v\in \mbox{TU}(N)$ be any game. Then we have
\[{\cal R}_{F}^{C}(v)=\sum_{T\in\Phi_{F}^{C}}\left [\sum_{\{S:S\subseteq N,\alpha_{C}(S)=T\}}\Delta_{v}(S)\right ]\cdot u_{T}. \sharp\]

Suppose that the coalition $S\subseteq N$ is not conjunctively autonomous. Let $\widehat{z}={\cal R}_{F}^{C}(z_{S})$. Now there is no coalition $T$ such that $S=\sigma_{C}(T)$. Thus for any coalition $T\subseteq N$, we have $\widehat{z}(T)=z_{S}(\sigma_{C}(T))=0$. We may conclude that $\widehat{z}$ is the null game and so $z_{S}\in\mbox{Kernel}({\cal R}_{F}^{C})$. Now suppose that $S\neq\emptyset$ is an conjunctively autonomous coalition. Then $\alpha_{C}(S)=S$. By part (i) of Theorem \ref{gilt42}, it shows that ${\cal R}_{F}^{C}(u_{S})=u_{\alpha_{C}(S)}=u_{S}$, and hence that $u_{S}\in\mbox{Image}({\cal R}_{F}^{C})$. We denote by $r=|\Phi_{F}^{C}-1|$ the number of nonempty conjunctively autonomous subsets in $F$. Now there are $2^{n}-1-r$ games $z_{S}$, where $S$ is not conjunctively autonomous, all belong to the kernel of ${\cal R}_{F}^{C}$. Since these games are all linearly independent, the dimension $\dim (\mbox{Kernel}({\cal R}_{F}^{C}))\geq 2^{n}-1-r$. On the other hand, the $r$ games $u_{S}$, where $S$ is conjunctively autonomous, all belong to the image of ${\cal R}_{F}^{C}$. These games are also all linearly independent, and so the dimension $\dim (\mbox{Image}({\cal R}_{F}^{C}))\geq r$. However, we see that $\dim (\mbox{Kernel}({\cal R}_{F}^{C}))+\dim (\mbox{Image}({\cal R}_{F}^{C}))=2^{n}-1$. It shows that $\dim (\mbox{Kernel}({\cal R}_{F}^{C}))=2^{n}-1-r$ and $\dim (\mbox{Image}({\cal R}_{F}^{C}))=r$. The given sets of games clearly form bases for the kernel and image of the linear mapping ${\cal R}_{F}^{C}$, respectively. If $v\in\mbox{Image}({\cal R}_{F}^{C})$, then $v$ can be expressed as $v=\sum_{S\in\Phi_{F}^{C}}c_{S}u_{S}$. Hence, from part (i) of Theorem \ref{gilt42}, it immediately follows that ${\cal R}_{F}^{C}(v)=v$. It says that ${\cal R}_{F}^{C}$ is a projection mapping. Therefore, we have the following result.

Theorem (Gilles et al. \cite[p.285]{gil}). The linear mapping ${\cal R}_{F}^{C}$ is a projection mapping of rank $|\Phi_{F}^{C}-1|$. Its kernel is generated by the games $\{z_{S}:S\not\in\Phi_{F}^{C}\}$ and its image is generated by the games $\{u_{S}:S\in\Phi_{F}^{C}\}$. $\sharp$

Theorem (Gilles et al. \cite[p.286]{gil}). Let $F$ be any asymmetric permission structure. Then, we have following properties.

(i) If $v$ is a monotonic game, then its conjunctive restriction ${\cal R}_{F}^{C}(v)$ is also a monotonic game. Moreover if $v$ is monotonic and balanced, then ${\cal R}_{F}^{C}(v)$ is also monotonic and balanced.

(ii) If $v$ is a superadditive game, then its conjunctive restriction ${\cal R}_{F}^{C}(v)$ is also a superadditive game.

(iii) If $v$ is a convex game, then its conjunctive restriction ${\cal R}_{F}^{C}(v)$ is also a convex game.

(iv) If $F$ is such that there exists a player $i\in N$ with $\widehat{F}(i)=N\setminus\{i\}$, then the conjunctive restriction ${\cal R}_{F}^{C}(v)$ of any monotonic game $v$ is superadditive and balanced. $\sharp$

The Disjunctive Approach.

In an arbitrary permission structure, there can occur “domination cycles”, which says that there is at least one player that is subordinate of himself. In this case, all players in the cycle are subordinates of themselves. For certain economic applications, we want to exclude such domination cycles Let $F$ be a permission structure.

We say that $F$ is acyclic when, for every player $i\in N$, it holds that $i\not\in\widehat{F}(i)$.
We says that $F$ is hierarchical when $F$ is acyclic and $F$ is quasi-strongly connected, i.e., there exists an $i\in N$ satisfying $\widehat{F}(i)=N\setminus\{i\}$.

In a hierarchical permission structure, there exists a unique player $i_{0}$ such that $\widehat{F}(i_{0})=N\setminus\{i_{0}\}$, Moreover, for this player, it holds that $F^{-1}(i_{0})=\emptyset$. We call this player the top man in the permission structure. (Van den Brink and Giles \cite[p.119]{van96}, Van den Brink \cite[p.29]{van97} and Gilles and Owen \cite[p.5]{gil99}).

We define $B_{F}=\{i\in N:F^{-1}(i)=\emptyset\}$. It is clear that, for every acyclic permission structure $F$ on $N$, it holds that $B_{F}\neq\emptyset$. A permission structure $F$ is {\bf strictly hierarchical} if and only if it is acyclic and $|B_{F}|=1$. Withou loss of generality, we may assume that, for any strictly hierarchical permission structure $F$, we have $B_{F}=\{1\}$. (Gilles and Owen \cite[p.5]{gil99}).

In the disjunctive approach, we assume that each player needs permission from at least one of his/her predecessors before he/she is allowed to cooperate with other players. Consequently, a coalition can cooperate only if every player in the coalition, except the top man $i_{0}$, has a predecessor who also belongs to the coalition. Note that this implies that the unique top man $i_{0}$ belongs to the coalition. Thus, the “formable” coalition is defined below (Van den Brink \cite[p.30]{van97}).

\begin{equation}{\label{van97d200}}\tag{65}\mbox{}\end{equation}

Definition \ref{van97d200} (Van den Brink \cite[p.30]{van97}). Let $S\subseteq N$ be a coalition. We say that $S$ is disjunctively autonomous when, for every $i\in S$, there is a sequence of players $\{h_{1},\cdots ,h_{t}\}$ such that $h_{1}=i_{0}$, $h_{k+1}\in F(h_{k})$ for all $1\leq k\leq t-1$ and $h_{t}=i$. $\sharp$

Here we assume that the authorization of at least one direct superior is necessary and sufficient for a player to enter in cooperation with other players. In this case, a coalition $S$ is “formable” if, for every member $i\in S$, there is at least one direct superior present in that
coalition (Gilles and Owen \cite[p.5]{gil99}).

\begin{equation}{\label{gil99d200}}\tag{66}\mbox{}\end{equation}

Definition \ref{gil99d200} (Gilles and Owen \cite[p.5]{gil99}). A coalition $S\subseteq N$ is disjunctively autonomous in the acyclic permission structure $F$ if, for every $i\in S\setminus B_{F}$, we have $F^{-1}(i)\cap S\neq\emptyset$. $\sharp$

The above definition can be restated by noting that a coalition $S$ is disjunctively autonomous if and only if, for every $i\in S$, there exists a collection of players $\{j_{1},\cdots ,j_{m}\}\subseteq S$ with $j_{1}\in B_{F}$, $j_{m}=i$, and, for every $1\leq k\leq m-1$, we have $j_{k+1}\in F(j_{k})$. We denote by $\Phi_{F}^{D_{1}}$ the collection of all disjunctively autonomous coalitions in Definition \ref{van97d200} and $\Phi_{F}^{D_{2}}$ the collection of all disjunctively autonomous coalitions in Definition \ref{gil99d200}.

\begin{equation}{\label{gil99l22}}\tag{67}\mbox{}\end{equation}

Proposition \ref{gil99l22} (Gilles and Owen \cite[p.5]{gil99}). Let $F$ be an acyclic permission structure. Then, we have the following properties:

$\emptyset, N\in\Phi_{F}^{D_{2}}$;
for every $S,T\in \Phi_{F}^{D_{2}}$, we have $S\cup T\in\Phi_{F}^{D_{2}}$. $\sharp$

Let $F$ be a permission structure on $N$ and let $S$ be a coalition in $N$.

If $F$ is hierarachical, then the disjunctively sovereign part of $S$ in $F$ is given by
\[\sigma_{D_{1}}(S)=\bigcup_{T\in \Phi_{F}^{D_{1}},T\subseteq S}T\]
If $F$ is acyclic, then the sub-coalition given by
\[\sigma_{D_{2}}(S)=\bigcup_{T\in \Phi_{F}^{D_{2}},T\subseteq S}T\]
is the disjunctively sovereign part of $S$ in $F$. A coalition $T$ in $N$ is a disjunctive authorizing set for $S$ when $S\subseteq T$, $T\in \Phi_{F}^{D_{2}}$ and there does not exist a $U\in \Phi_{F}^{D_{2}}$ such that $S\subseteq U\subseteq T$ and $U\neq T$.

The disjunctive sovereign part of $S$ is the largest formable subset of $S$. It consists of those players in $S$ that can be reached by a “permission path” starting at the topman such that all players on this path belong to coalition $S$ (Van den Brink \cite[p.30]{van97}).

From Proposition \ref{gil99l22}, it follows that, for every coalition $S\subseteq N$, we have $\sigma_{D_{2}}(S)\in \Phi_{F}^{D_{2}}$, which also says that $\sigma_{D_{2}}(S)$ is the largest autonomous subcoalition of $S$ in $F$. Moreover, $\Phi_{F}^{D_{2}}(\sigma_{D_{2}}(S))=\sigma_{D_{2}}(S)$ and $\Phi_{F}^{D_{2}}=\{S\subseteq N:S=\sigma_{D_{2}}(S)\}$ (Gilles and Owen \cite[p.6]{gil99}).

The collection of all authorizing sets for $S$ in $F$ is denoted by $\alpha_{D_{2}}(S)\subseteq \Phi_{F}^{D_{2}}$. Clearly, $S\in \Phi_{F}^{D_{2}}$ if and only if, for every $i\in S$, there is an authorizing set $T_{i}\in\alpha_{D_{2}}(i)$ with $T_{i}\subseteq S$. Another characterization of autonomous coalitions with the use of authorizing set is given by
\[\Phi_{F}^{D_{2}}=\{S\subseteq N:\alpha_{D_{2}}(S)=\{S\}\}\mbox{ and }
\Phi_{F}^{D_{2}}=\bigcup_{S\subseteq N}\alpha_{D_{2}}(S).\]
Furthermore, we mention that, for every nonempty coalition $\emptyset\neq S\subseteq N$, it holds that $\alpha_{D_{2}}(S)\neq\emptyset$. As a special case, we have the “empty” permission structure $F_{0}$ defined by $F_{0}(i)=\emptyset$ for every $i\in N$. Obviously, $\Phi_{F_{0}}^{D_{2}}=2^{N}$ and, for every $S\subseteq N$, we have $\alpha_{D_{2}}(S)=\{S\}$ and $\sigma_{D_{2}}(S)=S$.

Given a coalition $S\subseteq N$, if $S$ is not disjunctively autonomous in the permission structure $F$, the authority exercised prevents the coalition $S$ from forming. In fact, only its autonomous part $\sigma_{D_{2}}(S)\subseteq S$ is able to form within $F$ (Gilles and Owen \cite[p.6-7]{gil99}).

\begin{equation}{\label{van97d201}}\tag{68}\mbox{}\end{equation}

Definition \ref{van97d201} (Van den Brink \cite[p.30]{van97}). Let $F$ be a hierarchical permission structure on $N$. We introduce a mapping ${\cal R}_{F}^{D_{1}}:\mbox{TU}(N)\rightarrow \mbox{TU}(N)$, which assigns to every cooperative game $(N,v)$ its {\bf disjunctive restriction}, given as the game ${\cal R}_{F}^{D_{1}}(v)(S)=v(\sigma_{D_{1}}(S))$ for $S\subseteq N$. $\sharp$

Definition (Gilles and Owen \cite[p.6-7]{gil99}). Let $F$ be an acyclic permission structure. Then the disjunctive restriction is similarly defined by ${\cal R}_{F}^{D_{2}}(v)(S)=v(\sigma_{D_{2}}(S))$ for $S\subseteq N$. $\sharp$

Obviously, for the empty permission structure ${\cal R}_{F_{0}}^{D_{2}}(v)=v$ for every $v\in \mbox{TU}(N)$. Let $S\subseteq N$ be a coalition. We define $\alpha_{D_{2}}^{*}(S)\subseteq 2^{N}$ as the collection of all finite unions of authorizing sets for $S$, i.e., $T\in \alpha_{D_{2}}^{*}(S)$ if and only if there exist $T_{q}\in\alpha_{D_{2}}(S)$, $1\leq q\leq Q$, satisfying $T=\bigcup_{q=1}^{Q}T_{q}$. It is clear that $\alpha_{D_{2}}(S)\subseteq \alpha_{D_{2}}^{*}(S)\subseteq\Phi_{F}^{D_{2}}$. We also write $\alpha_{D_{2}}^{-1}(S)=\{T\subseteq N:S\in \alpha_{D_{2}}(T)\}$ and $\widehat\alpha_{D_{2}}(S)=\{T\subseteq N:S\in \alpha_{D_{2}}^{*}(T)\setminus \alpha_{D_{2}}(T)\}$. For every $S\in\Phi_{F}^{D_{2}}$ and $T\in \alpha_{D_{2}}^{*}(S)$, we define the number $\delta_{S}(T)=\Delta_{{\cal R}_{F}^{D_{2}}(u_{T})}(S)\in {\bf Z}$, where $\Delta_{{\cal R}_{F}^{D_{2}}(u_{T})}(S)$ is the dividend of coalition $S$ in game ${\cal R}_{F}^{D_{2}}(u_{T})$ and $u_{T}$ is the unanimity game on $T$. The numbers $\delta_{S}(T)\in {\bf Z}$ for coalitions $S$ and $T$ are clearly independent of the game $v$, and therefore determined completely by the structure as described by $F$ (Gilles and Owen \cite[p.9]{gil99}).

Theorem (Gilles and Owen \cite[p.9]{gil99}). Let $v\in \mbox{TU}(N)$. Then its disjunctive restriction on the acyclic permission
structure $F$ is given by
\[{\cal R}_{F}^{D_{2}}(v)=\sum_{S\in \Phi_{F}^{D_{2}}}\left [\sum_{T\in
\alpha_{D_{2}}^{-1}(S)}\Delta_{v}(T)+\sum_{T\in\widehat\alpha_{D_{2}}(S)}
\delta_{S}(T)\cdot\Delta_{v}(T)\right ]\cdot u_{S}.\]

Theorem (Gilles and Owen \cite[p.10]{gil99}). Let $(v,F)$ be a monotonic game with an acyclic permission structure. Then, we have the following properties.

(i) ${\cal R}_{F}^{D_{2}}(v)$ is a monotonic game.

(ii) If $v$ is superadditive, then ${\cal R}_{F}^{D_{2}}(v)$ is super-additive as well.

(iii) If $v$ is balanced, then ${\cal R}_{F}^{D_{2}}(v)$ is balanced as well.

(iv) If $F$ is strictly hierarchical, then ${\cal R}_{F}^{D_{2}}(v)$ is monotone, super-additive, and balanced. $\sharp$

Games under Precedence Constraints.

It is not necessarily that every subset of $N$ may occur as a coalition.

\begin{equation}{\label{fai92d2}}\tag{69}\mbox{}\end{equation}

Definition \ref{fai92d2} (Faigle and Kern \cite[p.251,252]{fai92}). Let $(N,\preceq )$ be a finite partially ordered set of players, where $N$ is the collection of players and the relation $i\preceq j$ indicates that the presence of $j$ enforces the presence of $i$ in any coalition $S\subseteq N$. A coalition of $(N,\preceq )$ is a subset $S\subseteq N$ such that $s\in S$ and $t\preceq s$ yield $t\in S$ for all $s,t\in N$. We set

\[{\cal S}^{(N,\preceq )}=\{S:S\mbox{ is a coalition of }(N,\preceq )\}.\]

A cooperative game on $(N,\preceq )$ is a function $v:{\cal S}^{(N,\preceq )}\rightarrow\mathbb{R}$ satisfying $v(\emptyset )=0$. $\sharp$

We see that the union and intersection of coalitions are again coalitions while complements of coalitions may fail to have this property. We denote by $G^{(N,\preceq )}$ the vector space of all cooperative games on $(N,\preceq )$. We remark that if $(N,\preceq )$ is “trivially ordered”, i.e., $i\preceq j$ implies $i=j$ for all players $i,j\in N$, then ${\cal S}^{(N,\preceq )}$ is the power set of $N$, i.e., $(N,\preceq )=2^{N}$ (Faigle and Kern \cite[p.251-252]{fai92}).

For $\emptyset\neq S\in {\cal S}^{(N,\preceq )}$, we define two games $\delta_{S}$ on $(N,\preceq )$ is defined by
\begin{equation}{\label{ga12}}\tag{70}
\delta_{S}(T)=\left\{\begin{array}{ll}
1 & \mbox{if $S=T$}\\ 0 & \mbox{if $S\neq T$}.
\end{array}\right .\mbox{ and }\zeta_{S}(T)=\left\{\begin{array}{ll}
1 & \mbox{if $S\subseteq T$}\\ 0 & \mbox{otherwise}.
\end{array}\right .
\end{equation}

We see that the game $\zeta_{S}$ is just the unanimity game if ${\cal S}^{(N,\preceq )}$ is trivially ordered.
We also have that each game $\zeta_{S}$ is a linear combination of games $\{\delta_{S}\}_{S\in {\cal S}^{(N,\preceq )}}$.
We observe
\[\zeta_{S}=\sum_{\{T:S\subseteq T\}}\delta_{T}\]
where the summation is always to be understood relative to ${\cal C}$.
The collection of all games $\{\delta_{S}\}_{S\in {\cal S}^{(N,\preceq )}}$ on $(N,\preceq )$ is a basis of $G^{(N,\preceq )}$.

More precisely, we have the following result.

\begin{equation}{\label{fai92l1}}\tag{71}\mbox{}\end{equation}

Proposition \ref{fai92l1} (Faigle and Kern \cite[p.252]{fai92}). For all $v\in G^{(N,\preceq )}$, we have
\[v=\sum_{S\in {\cal S}^{(N,\preceq )}}v(S)\delta_{S}. \sharp\]

The Möbius function relative to ${\cal S}^{(N,\preceq )}$ is the unique function $\mu:{\cal S}^{(N,\preceq )}\times {\cal S}^{(N,\preceq )}\rightarrow\mathbb{Z}$ such that the following conditions are satisfies:

$\mu (S,U)=0$ if $S\not\subseteq U$;
$\sum_{\{T:S\subseteq T\subseteq U\}}\mu (S,T)=\delta_{S}(U)$ if $S\subseteq U$.

This implies the well-known Möbius inversion formula
\[\delta_{S}=\sum_{\{T:S\subseteq T\}}\mu (S,T)\zeta_{T}.\]

\begin{equation}{\label{fai92l2}}\tag{72}\mbox{}\end{equation}

Proposition \ref{fai92l2} (Faigle and Kern \cite[p.253]{fai92}). For every game $v\in G^{(N,\preceq )}$, we have
\[v=\sum_{T}\left [\sum_{S}\mu (S,T)v(S)\right ]\zeta_{T}. \sharp\]

The above proposition shows that the collection of all games $\{\zeta_{S}\}_{S\in {\cal S}^{(N,\preceq )}}$ on $(N,\preceq )$ is also a basis of $G^{(N,\preceq )}$. If $(N,\preceq )$ is trivially ordered, i.e., $(N,\preceq )=2^{N}$, then the M\”{o}bius function is explicitly given by
\[\mu (S,T)=(-1)^{|T|-|S|}\mbox{ if }S\subseteq T,\]
which implies the Shapley’s formula
\[v=\sum_{T}\left [\sum_{S\subseteq T}(-1)^{|T|-|S|}v(S)\right ]\zeta_{T}\]
(Faigle and Kern \cite[p.253]{fai92}).

Games on Convex Geometries.

The cooperative games under precedence constraints discussed above are defined on distributive lattices of subsets of players, but there may exist some player $i\in N$ such that the coalition $\{i\}\not\in {\cal S}^{(N,\preceq )}$. Here we are going to consider another kind of restricted games. We consider a family ${\cal L}$ of subsets of $N$ with the following properties:

(a) $\emptyset ,N\in {\cal L}$;

(b) $A\in {\cal L}$ and $B\in {\cal L}$ imply that $A\cap B\in {\cal L}$.

The family ${\cal L}$ gives rise to the operator $\mbox{cl}:2^{N}\rightarrow 2^{N}$ defined by
\[A\mapsto\mbox{cl}A\equiv\bigcap\{C\in {\cal L}:A\subseteq C\}.\]
It is easy to check that the operator $\mbox{cl}$ has the following properties of a closure operator:

(d) $A\subseteq B$ implies $\mbox{cl}A\subseteq\mbox{cl}B$ for all $A,B\subseteq N$.

Conversely, every closure operator with the properties (c) and (d) defines a family ${\cal L}\subseteq 2^{N}$ with properties (a) and (b) as the family of its closed sets
\[{\cal L}={\cal L}(N,\mbox{cl})\equiv\{A\subseteq N:A=\mbox{cl}A\}.\]
If $(N,\mbox{cl})$ is a closure space, then ${\cal L}(N,\mbox{cl})\subseteq 2^{N}$ that is ordered by inclusion is a complete lattice in which meet and joint operations are defined by, for all $A,B\in {\cal L}(N,\mbox{cl})$,
\begin{equation}{\label{bil99eq30}}\tag{73}
A\wedge B=A\cap B\mbox{ and }A\vee B=\mbox{cl}(A\cup B).
\end{equation}
(Bilbao \cite[p.368-369]{bil98} and Bilbao and Jim\'{e}nez \cite[p.366]{bil99}).

\begin{equation}{\label{bil98d2}}\tag{74}\mbox{}\end{equation}

Definition \ref{bil98d2} The family of the closed sets ${\cal L}$ is a convex geometry when it satisfies the anti-exchange property; that is, for every $S\subseteq N$, if $i,j\not\in\mbox{cl}S$ and $i\in\mbox{cl}(S\cup\{i\})$, then $i\not\in\mbox{cl}(S\cup\{j\})$. A set in a convex geometry ${\cal L}$ is called convex. For $S\subseteq N$, an element $s\in S$ is an {\bf extreme point} of $S$ if $s\not\in\mbox{cl}(S\setminus\{s\})$. $\sharp$

For a closed set $S\in {\cal L}$, the element $s$ is an extreme point is equivalent to $S\setminus\{s\}\in {\cal L}$. We denote by $\mbox{ext}(S)$ the set of all extreme points of $S$. The convex geometries are the abstract closure spaces satisfying the finite Minkowski-Krein-Milman property: Every closed set is the closure of its extreme points. The following results shows that convex geometries have some properties of Euclidean convexity (Bilbao and Jim\'{e}nez \cite[p.366]{bil99}).

\begin{equation}{\label{bil99p777}}\tag{75}\mbox{}\end{equation}

Proposition \ref{bil99p777} (Bilbao and Jim\'{e}nez \cite[p.366]{bil99} and Bilbao \cite[p.369]{bil98}). Let $\mbox{cl}:2^{N}\rightarrow 2^{N}$ be a closure operator on $N$, and let ${\cal L}$ be the family of its closed sets. Then, we have the following properties.

(i) ${\cal L}$ is a convex geometry.

(ii) If $S\neq N$ is a closed set then $S\cup\{i\}$ is closed for some $i\in N\setminus S$ (this is also called the extension property).

(iii) For every closed set $S\subseteq N$, $S=\mbox{\em cl ext}(S)$. $\sharp$

A maximal chain of the convex geometry ${\cal L}\subseteq 2^{N}$ is an ordered collection of convex sets that is not contained in any larger chain. From the definition and by induction, we can show that every maximal chain contains $n+1$ convex sets
\[\emptyset =S_{0}\subset S_{1}\subset\cdots\subset S_{n-1}\subset S_{n}=N,\]
and $|S_{k}|=k$ for all $k=0,1,2,\cdots ,n$ (Bilbao \cite[p.369]{bil98}).

Example (Bilbao \cite[p.369]{bil98}). Let $N=\{1,2,3,4\}$ be a set and we consider
\[{\cal L}=\{\emptyset ,\{1\},\{1,2\},\{1,2,3\},N\}\mbox{ and }
{\cal F}=\{\emptyset ,\{1\},\{2\},\{1,3\},\{2,4\},N\}.\]
The collection ${\cal L}$ is a convex geometry such that $\mbox{cl}\{1\}=\{1\}$, $\mbox{cl}\{2\}=\{1,2\}$, $\mbox{cl}\{3\}=\{1,2,3\}$, $\mbox{cl}\{4\}=N$ and $\mbox{ext}(\{1,2,\cdots ,k\})=\{k\}$ for $1\leq k\leq 4$. For the collection ${\cal F}$ fails the extension property and $\mbox{ext}(N)=\emptyset$. $\sharp$

Example (Bilbao \cite[p.369]{bil98}). Let $(P,\preceq )$ be a partially ordered set, i.e., a set with a binary relation “$\preceq$” which satisfies the reflexive, antisymmetric and transitivity properties. A subset $S$ of $(P,\preceq )$ is convex whenever $a,b\in S$ and $a\preceq b$ imply that the interval $[a,b]=\{x\in P:a\preceq x\preceq b\}\subseteq S$. The convex subsets of $P$ form a closure system $\mbox{Co}(P)$. If $P$ (or, equivalently $\mbox{Co}(P)$) is finite, then each element is between a maximal element and a minimal element one. If $C\in\mbox{Co}(P)$ then $\mbox{ext}(C)$ is the union of the maximal and minimal elements of $C$. Moreover, $\mbox{Co}(P)$ is a convex geometry. $\sharp$

\begin{equation}{\label{bil98d1}}\tag{76}\mbox{}\end{equation}

Definition \ref{bil98d1} (Bilbao \cite[p.370]{bil98}). A cooperative game on a convex geometry ${\cal L}$ is a function $v:{\cal L}\rightarrow\mathbb{R}$ with $v(\emptyset )=0$. The coalitions are the convex sets of ${\cal L}$ and the players are the elements $i\in N$. $\sharp$

Let $CGG^{\cal L}$ be the vector space over $\mathbb{R}$ of all games on the convex geometry ${\cal L}\subseteq 2^{N}$. A game on a convex geometry is called simple, monotone, superadditive or convex when $v$ satisfies the corresponding property for the partial order, and the join and meet operations. For any $\emptyset\neq S\in {\cal L}$, we can also consider the games $\delta_{S}$ and $\zeta_{S}$ defined in (\ref{ga12}). The collections of these games are two different basis of the vector space $CGG^{\cal L}$. This can be seen similarly in \S\ref{fai92a} (Bilbao \cite[p.370]{bil98}).

Example (Bilbao \cite[p.370]{bil98}). Let $(P,\preceq )$ be a partially ordered set. For any $X\subseteq P$,
\[X\mapsto\mbox{cl}X\equiv\{y\in P:y\preceq x\mbox{ for some }x\in X\}\]
defines a closure operator on $P$. Its closed sets are the order ideals of $P$, and we denote this lattice $J(P)$. Since the union and intersection of order ideals is again an order ideal, it follows that $J(P)$ is a sublattice of $2^{P}$. Then $J(P)$ is a distributive lattice and so, $J(P)$ is a convex geometry closed under set-union and $\mbox{ext}(S)$ is the set of all maximal points $\max (S)$ of the subposet $S\in J(P)$. Then the game $({\cal C},v)$ of Faigle and Kern \cite{fai92}, where ${\cal C}$ is the family of order ideals of $P$ is a game on a distributive lattice. $\sharp$

A set system on a finite ground set $N$ is a pair $(N,{\cal F})$ with ${\cal F}\subseteq 2^{N}$. The sets belonging to ${\cal F}$ are called feasible coalitions. For any $S\subseteq N$, maximal feasible subsets of $S$ are called components of $S$ (Bilbao \cite[p.132]{bil98a}).

\begin{equation}{\label{bil98ad1}}\mbox{}\tag{77}\end{equation}

Definition \ref{bil98ad1} (Bilbao \cite[p.132]{bil98a}). A partition system is a pair $(N,{\cal F})$ satisfying the following conditions:

$\emptyset\in {\cal F}$ and $\{i\}\in {\cal F}$ for every $i\in N$;
For all $S\subseteq N$, the components of $S$, denoted by $\Pi_{S}=\{T_{1},\cdots ,T_{p}\}$, forms a partition of $S$. $\sharp$

Proposition (Bilbao \cite[p.132]{bil98a})}. A set system $(N,{\cal F})$ which satisfies condition (i) in Definition \ref{bil98ad1} is a partition system if and only if $F,G\in {\cal F}$ nd $F\cap G=\emptyset$ imply $F\cup G\in {\cal F}$. $\sharp$

\begin{equation}{\label{bil98ad2}}\tag{78}\mbox{}\end{equation}

Definition \ref{bil98ad2}. Let $(N,{\cal F})$ be a partition system. The ${\cal F}$-restricted game associated with $(N,v)$ is the game $(N,v^{\cal F})$ defined by
\[v^{\cal F}(S)=\sum_{T\in\Pi_{S}}v(T),\]
where $\Pi_{S}$ is the collection of the components of $S$. $\sharp$

We see that if $S\in {\cal F}$ then $v^{\cal F}(S)=v(S)$. The map $L^{\cal F}:\mbox{TU}(N)\rightarrow\mbox{TU}(N)$ defined by $L^{\cal F}(v)=v^{\cal F}$ is a linear operator Let us recall that every game $v$ is a linear combination of unanimity games given by
\[v=\sum_{T\subseteq N}\Delta_{T}(v)\cdot u_{T},\]
where
\[\Delta_{T}(v)=\sum_{S\subseteq T}(-1)^{|T|-|S|}\cdot v(S).\]
We see that the linearity implies
\[v^{\cal F}=\sum_{T\subseteq N}\Delta_{T}(v)u_{T}^{\cal F},\]
where the game $u_{T}^{\cal F}$ satisfies
\[u_{T}^{\cal F}(S)=\sum_{F\in\Pi_{S}}u_{T}(F)=\left\{\begin{array}{ll}
1 & \mbox{if there exists $F\in {\cal F}$ such that $latex T\subseteq F
\subseteq S$}\\ 0 & \mbox{otherwise}.
\end{array}\right .\]

Theorem (Bilbao \cite[p.134]{bil98a}).
If $(N,{\cal F})$ is a partition system, then the unanimity games $\{u_{T}:\emptyset\neq T\in {\cal F}\}$ form a basis of the vector space
$\{(N,v^{\cal F}):v\in \mbox{TU}(N)\}$, i.e.,
\[v^{\cal F}=\sum_{T\in {\cal F}}\Delta_{T}(v^{\cal F})u_{T},\]
where $v_{\emptyset}(v^{\cal F})=0$. $\sharp$

From Proposition \ref{bil99p777}, we can propose the following definition.

\begin{equation}{\label{bil98ad100}}\tag{79}\mbox{}\end{equation}

Definition \ref{bil98ad100} (Bilbao \cite[p.136]{bil98a}). The finite set system $(N,{\cal L})$ is a convex geometry on $N$ when the following conditions are satisfied:

$\emptyset\in {\cal F}$;
${\cal L}$ is closed under intersection;
if $S\in {\cal L}$ with $S\neq N$, then there exists $j\in N\setminus S$ such that $S\cup\{j\}\in {\cal L}$.

A partition convex geometry is a convex geometry $(N,{\cal L})$ which is also a partition system. $\sharp$

Proposition (Bilbao \cite[p.138]{bil98a}). Let $(N,{\cal L})$ be a parition convex geometry and let $(N,v)$ be a game. The dividends of $S\in {\cal L}$ in the ${\cal L}$-restricted game $v^{\cal L}$ are
\[\Delta_{S}(v^{\cal L})=\sum_{\{T\subseteq N:cl T=S\}}\Delta_{T}(v)=
\sum_{\{T\subseteq N:ext(S)\subseteq T\subseteq S\}}\Delta_{T}(v).\sharp\]

Proposition (Bilbao \cite[p.139]{bil98a}). Let $(N,{\cal L})$ be a partition convex geometry and let $(N,v)$ be a game. If $v^{\cal L}$ is the ${\cal L}$-restricted game associated to $v$, then
\[\Delta_{S}(v^{\cal L})=\sum_{\{T\in {\cal L}:S^{-}\subseteq T\subseteq S\}}
(-1)^{|S|-|T|}v(T),\mbox{ where }S^{-}=S\setminus\mbox{ext}(S)\]
(we also see that $\{T\in {\cal L}:S^{-}\subseteq T\subseteq S\}=\{T\in {\cal L}:S\setminus T\subseteq\mbox{ext}(S)\}$). $\sharp$

Cooperative Games – Transferable Utility Games

Games in Characteristic Function Form.

Relations with Non-cooperative Game.

Imputation.

Strategical Equivalence.

Normalization.

Balanced Games.

Convex Cooperative Games.

Multi-Choice Cooperative Games.

The Same Activity Levels for Each Player.

Different Action Levels for Each Player.

Population Monotonic Allocation Schemes.

Clan Games.

Big Boss Games.

Clan Games.

Total Clan Games.

Restricted Games.

Games with Coalition Structure.

Games with Permission Structures.

The Conjunctive Approach.

The Disjunctive Approach.

Games under Precedence Constraints.

Games on Convex Geometries.

Hsien-Chung Wu

發佈留言取消回覆

Games in Characteristic Function Form.

Relations with Non-cooperative Game.

Imputation.

Strategical Equivalence.

Normalization.

Balanced Games.

Convex Cooperative Games.

Multi-Choice Cooperative Games.

The Same Activity Levels for Each Player.

Different Action Levels for Each Player.

Population Monotonic Allocation Schemes.

Clan Games.

Big Boss Games.

Clan Games.

Total Clan Games.

Restricted Games.

Games with Coalition Structure.

Games with Permission Structures.

The Conjunctive Approach.

The Disjunctive Approach.

Games under Precedence Constraints.

Games on Convex Geometries.

Hsien-Chung Wu

相關文章

Monotonicity

Shapley Value for Multilinear Extension of Games

Probabilistic Values

發佈留言取消回覆