Shapley Value For Restricted Games

James McDougal Hart (1828-1901) was a Scottish-born American landscape painter.

Let $(N,v)$ be a cooperative game. Assuming that the grand coalition $N$ will be formed, the question arises how to divide the worth $v(N)$ among players. A well-known answer to this question is the Shapley value. However, in many practical situatios, not every coalition is formable, including the grand coalition. This may be due to a lack of communication possibilities, or certain institutional constraints (Derks and Peters \cite[p.351]{der93}).

Games with Coalition Structures.

Most of the existing models in economics and game theory assume that the coalition structure is given exogenously. Here, we try to obtain it as an endogenous outcome. Namely, we want to be able to predict which coalitions will in fact form in each given situation (Hart and Kurz \cite[p.1047]{har83}).

Let us recall that a coalition structure ${\cal B}$ of $N$ is a partition of $N$, i.e., ${\cal B}=\{B_{1},\cdots ,B_{k}\}$, where $\bigcup_{i=1}^{k}B_{i}=N$ and $B_{i}\cap B_{j}=\emptyset$ for $i\neq j$. A solution (or value) for cooperative game $(N,v)$ with coalition structure is a function $\boldsymbol{\phi}$ which assigns each $(N,{\cal B},v)$ a vector $\boldsymbol{\phi}(N,{\cal B},v)$ in $\mathbb{R}^{N}$. $\phi_{i}(N,{\cal B},v)$ is the payoff for player $i\in N$. We consider the following axioms.

(AD1: Relative Efficiency). For all $k$, we have $\sum_{i\in B_{k}}\phi_{i}(N,{\cal B},v)=v(B_{k})$;
(AD2: Symmetry). For all permutation $\pi$ of $N$ under which ${\cal B}$ is invariant as shown in Definition \ref{aum74d1}, we have $\sum_{i\in S}\phi_{i}(N,{\cal B},\pi v)=\sum_{i\in\pi S}\phi_{i} (N,{\cal B},v)$;
(AD3: Additivity). We have $\boldsymbol{\phi} (N,{\cal B},v_{1}+v_{2})=\boldsymbol{\phi}(N,{\cal B},v_{1})+ \boldsymbol{\phi}(N,{\cal B},v_{2})$;
(AD4: Null Player). Player $i$ is null if $v(S\cup\{i\})=v(S)$ for all $S\subseteq N$. If $i$ is a null player, then $\phi_{i}(N,{\cal B},v)=0$.

The solution function $\boldsymbol{\phi}$ is called a Aumann-Dreze value if it satisfies the axioms (AD1)–(AD4). (Winter \cite[p.56]{win91}, Winter \cite[p.139]{win92}) and Aumann and Dreze \cite[p.220]{aum74}).

When ${\cal B}=\{N\}$, it is known that there is a unique function satisfying the axioms (AD1)–(AD4), namely the Shapley value of the cooperative game. The cooperative game $(B_{k},v|_{B_{k}})$ is defined by, for all $S\subseteq B_{k}$, $(v|_{B_{k}})(S)=v(S)$. (Aumann and Dreze \cite[p.220]{aum74}).

Theorem. (Aumann and Dreze \cite[p.220]{aum74}). Given a cooperative game with coalition structure $(N,{\cal B},v)$, there is a unique solution fucntion $\boldsymbol{\phi}$ defined on $\mbox{TU}(N)$ satisfying the axioms {\em (AD1)}-{\em (AD4)}. Moreover, for all $k$ and all $i\in B_{k}$, we have $\phi_{i}(N,{\cal B},v)=\phi_{i}(v|_{B_{k}})$, where $\boldsymbol{\phi}(v|_{B_{k}})$ is the
Shapley value on the cooperative game $(B_{k},v|_{B_{k}})$. This asserts that the restriction to $B_{k}$ of the value $\boldsymbol{\phi}(N,{\cal B},v)$ is the Shapley value for the cooperative game $(B_{k},v|_{B_{k}})$. $\sharp$

Given a cooperative game with coalition structure $(N,{\cal B},v)$, let $\Pi_{\cal B}$ be the set of all permutations of the players in which players of the same coalition appear successively. That is, if $\pi =(i_{1},\cdots ,i_{n})$ is a permutation of the players, then $\pi\in\Pi_{\cal B}$ if and only if for all $j,k\in S\in {\cal B}$ if $r\in N$ is between $j$ and $k$ in $\pi$, then $r\in S$. The solution function is given by
\begin{equation}{\label{win91eq41}}\tag{1}
\phi_{i}(N,{\cal B},v)=\frac{1}{|\Pi_{\cal B}|}\cdot\sum_{\pi\in\Pi_{\cal B}}m_{i}(v,\pi ),
\end{equation}
where $p_{i}^{\omega}$ is the set of players preceding $i$ in the order $\omega$. Owen constructed this solution function axiomatically, which will be described below. We define by $v^{\cal B}$ the game induced by $v$ by considering the coalitions of ${\cal B}$ as players. We denote by $[B_{k}]$ the coalition $B_{k}$ in ${\cal B}$ when it is considered as a player, and the set of players of $v^{\cal B}$ by $[{\cal B}]$. For example,
\[v^{\cal B}(\{[B_{1}],[B_{2}]\})=v(B_{1}\cup B_{2}).\]
Two players $i$ and $j$ are said to be substitutes in the cooperative game $(N,v)$ if and only if, for each $S\subseteq N$, such that $i,j\not\in S$, $v(S\cup\{i\})=v(S\cup\{j\})$. Let us consider the following axioms:

(O1: Efficiency). $\sum_{i\in N}\phi_{i}(N,{\cal B},v)=v(N)$;
(O2: Individual Symmetry). If $i,j\in B_{k}\in {\cal B}$ and $i,j$ are substitutes in $v$, then $\phi_{i}(N,{\cal B},v)=\phi_{j}(N,{\cal B},v)$;
(O3: Coalitional Symmetry). If $S,T\in {\cal B}$ and $[S],[T]$ are symmetric as players in $v^{\cal B}$, then $\sum_{i\in S}\phi_{i}(N,{\cal B},v)=\sum_{i\in T}\phi_{i}(N,{\cal B},v)$;
(O4: Additivity). We have $\boldsymbol{\phi}(N,{\cal B},v_{1}+v_{2})=\boldsymbol{\phi}(N,{\cal B},v_{1})+\boldsymbol{\phi}(N,{\cal B},v_{2})$;
(O5: Null). If $v(S\cup\{i\})=v(S)$ for all $S\subseteq N$, then $\phi_{i}(N,{\cal B},v)=0$.

The solution function $\boldsymbol{\phi}$ is called Owen value if the axioms (O1)–(O5) are satisfied. (Winter \cite[p.56]{win91} and Winter \cite[p.133,136]{win92}).

Theorem. (Winter \cite[p.134]{win92}). There exists a unique solution function $\boldsymbol{\phi}$ defined on the set of cooperative games with coalition structures satisfying the axioms (O1)–(O5). $\sharp$

If ${\cal B}$ is a trivial coalition structure, namely ${\cal B}=\{N\}$ or ${\cal B}=\{\{1\},\{2\},\cdots ,\{n\}\}$, then $\Pi_{\cal B}$ contains all possible orders and so $\boldsymbol{\phi}(N,{\cal B},v)$ coincides with the well-known Shapley value of $(N,v)$. It is easy to verify that the solution function defined in (\ref{win91eq41}) satisfies the following properties:

(Linearity). For any cooperative games coalition structure $(N,{\cal B},v)$ and $(N,{\cal B},w)$, we have $\boldsymbol{\phi}(N,{\cal B},v+w)=\boldsymbol{\phi}(N,{\cal B},v)+\boldsymbol{\phi}(N,{\cal B},w)$.
(The null player property). For any cooperative game coalition structure $(N,{\cal B},v)$, if, for some $i\in N$, $v(S\cup\{i\})=v(S)$ for any $S\subset N$, then $\phi_{i}(N,{\cal B},v)=0$.(Winter \cite[p.56-57]{win91}).

Let ${\cal U}$ be an infinite set, the universe of players. A game $v$ is a real function defined on all subsets of $U$ satisfying $v(\emptyset )=0$. A set $N\subseteq {\cal U}$ is a {\bf carrier} of $v$, if for all $S\subseteq {\cal U}$, $v(S)=v(S\cap N)$. Here, we consider only games with finite carriers. In general, a {\bf coalition structure} ${\cal B}$ is a finite partition ${\cal B}=\{B_{1},\cdots ,B_{m}\}$ of ${\cal U}$, i.e., $\bigcup_{k=1}^{m}B_{k}={\cal U}$ and $B_{k}\cap B_{l}=\emptyset$ for $k\neq l$. For $N\subseteq {\cal U}$, which is usually taken to be a carrier of some game, we will denote by ${\cal B}(N)$ the restriction of ${\cal B}$ to $N$; namely, ${\cal B}(N)=\{B_{k}\cap N:B_{k}\in {\cal B}\mbox{ for all }k=1,\cdots ,m\}$, which is a partition of $N$. Let $\pi$ be a permutation of the players, i.e., a one-to-one mapping of ${\cal U}$ onto itself. We define a new game $\pi v$ by $(\pi v)(S)=v(\pi S)$ for all $S\subset {\cal U}$. We say that the game among coalitions is inessential if
\[v\left (\bigcup_{k\in K}B_{k}\right )=\sum_{k\in K}v(B_{k})\]
for all subsets $K$ of $\{1,2,\cdots ,m\}$, i.e., $v$ is restricted to the field generated by ${\cal B}$ is additive (Hart and Kurz \cite[p.1051-1052]{har83}).

We consider an operator $\boldsymbol{\phi}$ defined on the set of games $({\cal U},{\cal B},v)$ such that, for every player $i\in {\cal U}$, $\phi_{i}({\cal U},{\cal B},v)$ is a real number. We will consider the following axioms on $\boldsymbol{\phi}$.

(HK1: Carrier). Let $N$ be a carrier of $({\cal U},{\cal B}_{1},v)$. Then
\[\sum_{i\in N}\phi_{i}({\cal U},{\cal B},v)=v(N);\]
if ${\cal B}_{1}(N)={\cal B}_{2}(N)$, then $\phi_{i}({\cal U},{\cal B}_{1},v)=\phi_{i}({\cal U},{\cal B}_{2},v)$;

(HK2: Symmetry). If $\pi$ be a permutation of the players, then $\phi_{i}({\cal U},\pi {\cal B},\pi v)=\phi_{\pi (i)}({\cal U},{\cal B},v)$;

(HK3: Additivity). $\phi_{i}({\cal U},{\cal B},v_{1}+v_{2})=\phi_{i}({\cal U},{\cal B},v_{1})+\phi_{i}({\cal U},{\cal B},v_{2})$;

(HK4: Inessential Game). If the game $({\cal U},{\cal B},v)$ among coalitions is inessential, then
\[\sum_{i\in B_{k}}\phi_{i}({\cal U},{\cal B},v)=v(B_{k})\]
for all $k=1,2,\cdots ,m$.

The axiom (HK1) actually contains three parts. If $i$ is a null player in a cooperative game $(N,v)$, (i.e., ${\cal U}\setminus\{i\}$ is a carrier of $v$; or equivalently, $v(S\cup\{i\})=v(S)$ for all $S\subset {\cal U}$), then his/her value is $0$ in all coalition structures. Moreover, if such $i$ “moves” from one $B_{k}$ to another, it does not affect anyone’s value. And last, for all coalition structures the value is efficient. We note that the axiom (HK2) involves permuting both the game and the coalition structure. As for the additivity of the value with respect to the game, it is assumed for a fixed coalition structure. It may be replaced by the following axiom: The solution function of a probabilistic mixture of two games (i.e., with probability $p$ the game $v$ is played, and with probability $1-p$ the game $v’$ is played) is the same mixture of the solution of the two games. This is consistent with the interpretation of values as the expected utility of playing the game (Hart and Kurz \cite[p.1053]{har83}).

Let $N$ be a finite set of players, and ${\cal B}=\{B_{1},\cdots ,B_{m}\}$ a coalition structure. A complete order of $N$ is consistent with ${\cal B}$ if, for all $k=1,\cdots ,m$ and all $i,j\in B_{k}$, all elements of $N$ between $i$ and $j$ also belong to $B_{k}$. A random order of $N$ consistent with ${\cal B}$ is a random variable whose values are orders of $N$ that are consistent with ${\cal B}$, all equally probable (i.e., each with probability $1/(m!b_{1}!b_{2}!\cdots b_{m}!)$, where $b_{k}=|B_{k}\cap N|$). The interpretation is as follows: the players arrive randomly, but such that all members of the same coalition do so successfully. This is the same as randomly ordering first the coalition and then the members within each coalition (Hart and Kurz \cite[p.1053]{har83}).

\begin{equation}{\label{har83t21}}\tag{2}\mbox{}\end{equation}

Theorem \ref{har83t21}. (Hart and Kurz \cite[p.1051]{har83}) There is a solution function $\boldsymbol{\phi}$ satisfying axioms (HK1)–(HK4), which is given by $\phi_{i}({\cal U},{\cal B},v)=\mathbb{E}\left [m_{i}(v,\cdot)\right ]$, where the expectation $\mathbb{E}$ is over all random permutations on a carrier $N$ of $v$ that are consistent with ${\cal B}$. $\sharp$

From the proof of Theorem \ref{har83t21}, the axiom (HK4) may be replaced by a slightly weaker axiom:

(HK4′: Null Game). If $v\left (\bigcup_{k\in K}B_{k}\right )=0$ for all $K\subseteq\{1,2,\cdots ,m\}$, then $\sum_{i\in B_{k}}\phi_{i}({\cal U},{\cal B},v)=0$ for all $k=1,\cdots ,m$.

Two other alternative axioms that may also be used in place of axiom (HK4) are as follows:

(HK5: Dummy Coalition). If $B_{l}$ is such that
\[v\left (B_{l}\bigcup\left (\bigcup_{k\in K}B_{k}\right )\right )=v\left (\bigcup_{k\in K}B_{k}\right )+v(B_{l})\]
for all $K\subset\{1,2,\cdots ,m\}$, then $\sum_{i\in B_{l}}\phi_{i}({\cal U},{\cal B},v)=v(B_{l})$;
(HK5′: Null Coalition). If $B_{l}$ is such that
\[v\left (B_{l}\bigcup\left (\bigcup_{k\in K}B_{k}\right )\right )=v\left (\bigcup_{k\in K}B_{k}\right )\]
for all $K\subset\{1,2,\cdots ,m\}$, then $\sum_{i\in B_{l}}\phi_{i}({\cal U},{\cal B},v)=0$.

It is clear that axiom (HK5) implies axiom (HK4), and axiom (HK5′) implies axiom (HK4′). However, toghther with axioms (HK1)–(HK3), they all become equivalent (Hart and Kurz \cite[p.1056]{har83}).

Corollary. (Hart and Kurz \cite[p.1056]{har83}) Let $N$ be a finite carrier of the game $({\cal U},{\cal B},v)$.
For all $B_{k}\in {\cal B}$, we have
\[\sum_{i\in B_{k}}\phi_{i}({\cal U},{\cal B},v)=\sum_{i\in B_{k}}\psi_{i}(v^{\cal B}),\]
where $(v^{\cal B},{\cal B})$ is the game restricted to the field generated by ${\cal B}$, i.e., each $B_{k}\in {\cal B}$ is a “player”, and $\psi_{i}(v)$ denotes the Shapley value of player $i$ in the cooperative game $(N,v)$. $\sharp$

It says that the total value of each coalition in ${\cal B}$ is precisely the Shapley value of the game played by the (representative of the) coalitions in ${\cal B}$. Note that if one wants the solution function to satisfy the “null player” axiom (i.e., adding null players does not change the value), one is necessarily led to regard each coalition in the coalition structure as one “representative”, independent of the number of original players it is composed of. For any set $S=\{i_{1},i_{2},\cdots ,i_{s}\}$. We write $\langle S\rangle =\{\{i_{1}\},\{i_{2}\},\cdots ,\{i_{s}\}\}$, i.e., the partition of $S$ is into singletons; in constrast, $\{S\}$ means that all members of $S$ are “together” in one coalition (Hart and Kurz \cite[p.1056]{har83}).

Corollary. (Hart and Kurz \cite[p.1056]{har83}) Let $N$ be a finite carrier of the game $({\cal U},{\cal B},v)$. Then
\[\phi_{i}({\cal U},\{N\},v)=\phi_{i}({\cal U},\langle N\rangle ,v)=\psi_{i}(v)\]
for all $i$, where $\psi_{i}(v)$ denotes the Shapley value of player $i$ in the cooperative game $(N,v)$. $\sharp$

For each cooperative game with coalition structure $(N,{\cal B},v)$ and each coalition $S$ in $N$, we denote by ${\cal B}^{S}$ the coalition structure on the set $S$ obtained from ${\cal B}$ by eliminating the players in $N\setminus S$. Let $\boldsymbol{\phi}$ be a value defined on the set of all games with coalition structure. Let $(N,v,{\cal B})$ be a game with coalition structure ${\cal B}=\{B_{1},\cdots ,B_{m}\}$. For each $S\subseteq B_{k}$, we define the {\bf reduced game} $v^{S,{\cal B}}$ on the set of all players $S$ as follows:
\[v^{S,{\cal B}}(T)=v((N\setminus S)\cup T)-\sum_{i\in N\setminus S}
\phi_{i}\left ((N\setminus S)\cup T,{\cal B}|_{(N\setminus S)\cup T},v^{(N\setminus S)\cup T}\right )\]
for all $T\subseteq S$. The motivation behind the definition of the reduced game is the following: The players in $T$ cooperate with $N\setminus S$. The players of $N\setminus S$ get the anticipated payoff according to $\boldsymbol{\phi}$ in the relevant coalition structure, i,e, ${\cal B}|_{(N\setminus S)\cup T}$ and the players of $T$ get the remaining payoff from the total amount $v((N\setminus S)\cup T)$. We turn now to formulating the Owen value axiomatically by considering the concept of consistency. We consider the following axioms.

(W1: Efficiency). For each $(N,v,{\cal B})$, we have $\sum_{i\in N}\phi_{i}(N,{\cal B},v)=v(N)$;
(W2: Covariant). For all $(N,v,{\cal B})$, $\alpha >0$ and $\boldsymbol{\beta}\in\mathbb{R}^{N}$, we have $\boldsymbol{\phi}({\cal B},\alpha v+\boldsymbol{\beta})=\alpha\boldsymbol{\phi}(N,{\cal B},v)+\boldsymbol{\beta}$, where $(\alpha v+\boldsymbol{\beta})(S)=\alpha v(S)+\sum_{i\in S}\beta_{i}$;
(W3: Game between Coalition Property). For all $(N,v,{\cal B})$ and all $B_{k}\in {\cal B}$, we have $\sum_{i\in B_{k}}\phi_{i}(N,{\cal B},v)=\psi_{[B_{k}]}([B_{k}],v^{\cal B})$;
(W4: Symmetry). For each $(N,v,{\cal B})$ and all $i,j\in B_{k}\in {\cal B}$ such that $i$ and $j$ are substitutes in $v$, we have
$\phi_{i}(N,{\cal B},v)=\phi_{j}(N,{\cal B},v)$.
(W5: Consistency). For each game $(N,v,{\cal B})$, $S\subseteq B_{k}\in {\cal B}$ and $i\in S$, we have $\phi_{i}({\cal B}^{S},v^{S,{\cal B}})=\phi_{i}(N,{\cal B},v)$.

Since $S\subseteq B_{k}\in {\cal B}$, we see that ${\cal B}^{S}=\{S\}$. In other words, if the players of $S$ cooperate by getting organized in the coalition structure of the grand coalition, then each player in $S$ gets in $v^{S,{\cal B}}$ exactly the same amount he/she gets in the original game $v$ and the original coalition structure ${\cal B}$, when $\boldsymbol{\phi}$ is implemented. The consistency proposed by Hart and Mas-Colell \cite{har89}) is a special case of this definition. This can be easily verified by letting ${\cal B}=\{N\}$
(Winter \cite[p.136]{win92}).

Proposition. (Winter \cite[p.136]{win92}) The solution function $\boldsymbol{\phi}$ satisfying axioms (O1)–(O5) (i.e., the Owen value) also satisfies the consistency axiom (W5). $\sharp$

Theorem. (Winter \cite[p.137]{win92}). There is a unique solution function $\boldsymbol{\phi}$ satisfies the axioms (W1)–(W5). Moreover, this value is the Owen value. $\sharp$

We consider a different definition of the reduced game: for all $S\subseteq B_{k}\in {\cal B}$, we define
\[\bar{v}^{S,{\cal B}}(T)=v((B_{k}\setminus S)\cup T)-\sum_{i\in B_{k}\setminus S}\phi_{i}\left ((B_{k}\setminus S)\cup T,
{\cal B}|_{(B_{k}\setminus S)\cup T},v^{(B_{k}\setminus S)\cup T}\right ).\]
With respect to this definition, one can define a new consistency axiom as follows:

(W5′: Consistency). For all $S\subseteq B_{k}\in {\cal B}$ and $i\in S$, we have $\phi_{i}(N,{\cal B},v)=\phi_{i}(S,{\cal B}^{S},\bar{v}^{S,{\cal B}})$.

We also consider the following axiom.

(W6: Efficiency with Respect to the Components of ${\cal B}$). For all $B_{k}\in {\cal B}$, we have $\sum_{i\in B_{k}}\phi_{i}(N,{\cal B},v)=v(B_{k})$.

Theorem. (Winter \cite[p.139]{win92}). There exists a unique solution function $\boldsymbol{\phi}$ satisfies axioms (W2), (W4), (W5′) and (W6). In this case, $\boldsymbol{\phi}$ is also the Aumann-Dreze value. $\sharp$

The two alternative definitions of consistency may give an insight into the conceptual difference between the Owen value and that of Aumann-Dreze value. For the Owen value, players of some coalition in the coalition structure may cooperate with players of some different coalition; while for the case of Aumann-Dreze value, only internal cooperation between members of the same coalition are admissible. This is emphasized in the different definition of the reduced game: In $v^{S,{\cal B}}$, players of $T\subseteq S$ cooperate with $N\setminus S$ while, in $\bar{v}^{S,{\cal B}}$, they may cooperate only with $B_{k}\setminus S$, where $B_{k}\in {\cal B}$ (Winter \cite[p.140]{win92}).

Definition. (Winter \cite[p.140]{win92}). Let $P$ be a function defined on the set of all games with coalition structure satisfying ${\bf P}(N,v,{\cal B})\in\mathbb{R}^{k}$, where ${\cal B}=\{B_{1},\cdots ,B_{m}\}$, and $P_{k}(N,v,{\cal B})=0$ when $latex B_{k}\cap N
=\emptyset$. Let $i\in B_{k}$. The marginal contribution of player $i$ to $(N,v,{\cal B})$ is defined by
\[D_{i}({\bf P}(N,v,{\cal B}))=P_{k}(N,v,{\cal B})-P_{k}(N\setminus\{i\},B|_{N\setminus\{i\}},v).\]
${\bf P}$ is said to be a potential function for games with coalition structure if
\begin{equation}{\label{win92eq31}}\tag{3}
\sum_{i\in B_{k}}D_{i}({\bf P}(N,v,{\cal B}))=D_{[B_{k}]}({\bf P}([{\cal B}],\{[{\cal B}]\},v^{\cal B})
\end{equation}
for all $B_{k}\in {\cal B}$ and
\[\sum_{i\in N}D_{i}({\bf P}(N,v,{\cal B}))=v(N).\sharp \]

Equation (\ref{win92eq31}) says that the sum of the marginal contributions of plqyers $i\in B_{k}\in {\cal B}$ is the marginal contribution of the player $[B_{k}]$ to the corresponding $([{\cal B}],\{[{\cal B}]\},v^{\cal B})$, i.e., the set of all players is $[{\cal B}]$, the coalition structure is $\{[{\cal B}]\}$, and the game is $v^{\cal B}$ (Winter \cite[p.141]{win92}).

Theorem. (Winter \cite[p.141]{win92}). There exists a unique potential function ${\bf P}$ for games with coalition structure. Moreover, for each $i\in N$, we have $D_{i}({\bf P}(N,v,{\cal B}))=\phi_{i}(N,{\cal B},v)$, where $\boldsymbol{\phi}$ is the Owen value. $\sharp$

The original potential function defined by Hart and Mas-Colell \cite{har89} turned out to be a function which assigns to each pair $(N,v)$ the real number $\sum_{S\subseteq N}a_{S}/|S|$, where $a_{S}/|S|$ is the dividend for players of coalition $S$. When we ignore the coalition structure or equivalently consider the coalition structure to be the grand coalition, players of some coalition $S$ get equal dividends. For different coalition structures this is not true anymore since players of different components of the coalition structure ${\cal B}$ may share different dividends. Therefore, one should consider vectors for describing these dividends rather than real numbers. This explains why the potential for games with coalition structure turns out to be a vector function (Winter \cite[p.142]{win92}).

Definition. (Winter \cite[p.142]{win92}). Let $P$ be a function which assign a real number to each game $(N,v,{\cal B})$. $P$ is said to be an AD potential function if $P$ satisfies
\begin{equation}{\label{win92eq34}}\tag{4}
\sum_{i\in N}D_{i}(P(N,v,{\cal B}))=\sum_{B_{k}\in {\cal B}}v(B_{k}),
\end{equation}
where $D_{i}(P(N,v,{\cal B}))=P(N,v,{\cal B})-P(N\setminus\{i\},B|_{N\setminus\{i\}},v|_{N\setminus\{i\}})$. $\sharp$

Note that the requirement on $P$ here is different from that of Hart and Mas-Colell \cite{har89} only in the sense that here we have on the right-hand side of (\ref{win92eq34}) $\sum_{B_{k}\in {\cal B}}v(B_{k})$ instead of $v(N)$ (Winter \cite[p.143]{win92}).

Theorem. (Winter \cite[p.143]{win92}). There exists a unique AD potential function $P$. Moreover, $D_{i}(P(N,v,{\cal B}))=\phi_{i}(N,{\cal B},v)$, where $\boldsymbol{\phi}$ is the Aumann-Dreze value. $\sharp$

Games with Permission Structures.

Let us recall Example \ref{gilee}. We give a similar example.

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

Example \ref{der93exa}. (Derks and Peters \cite[p.351]{der93}) Given a game $(N=\{1,2,3\},v)$ with $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$. Here player 1 is the seller of an object who values this object at $10$ dollars; players 2 and 3 are buyers who value the object at $20$ and $30$ dollars, respectively. Now suppose that player 2 can veto the sale of the object. This gives rise to a new game $(\{1,2,3\},u)$ with $u(\{1,3\})=10$ and $u(S)=v(S)$ otherwise. The Shapley value assigns the distribution $(21\frac{2}{3},1\frac{2}{3},6\frac{2}{3})$ to the game $v$ and $latex (18\frac{1}{3},8\frac{1}{3},
3\frac{1}{3})$ to the game $u$. These distributions reflect the additional power of player $2$. $\sharp$

The asymmetric permission structure was introduced in Definition \ref{gilda}. Now we are going to present the Shapley value of additive games with asymmetric and acyclic permission structure. From Definition \ref{gildb}, an asymmetric permission structure $F$ is {\bf acyclic} if, for every $i\in N$, it holds that $i\not\in\widehat{F}(i)$. Let $\boldsymbol{\lambda}\in\mathbb{R}_{++}^{N}$ be a strictly positive vector of weights. It is assumed that the (original) individual abilities of player $i\in N$ are represented by the weight $\lambda_{i}>0$. Now we introduce the game $v_{\lambda}\in \mbox{TU}(N)$ with the weight vector $\boldsymbol{\lambda}$ defined by
\[v_{\lambda}(S)=\sum_{i\in S}\lambda_{i}\]
for all $S\subseteq N$. Then we see that $v_{\lambda}$ is an additive game. Since the player $i\in N$ has to give the permission to her/his subordinates $j\in\widehat{F}(i)$, she/he can evidently claim a part of the payoff generated by these subordinates. This is exactly what is described by the restricted game ${\cal R}_{F}^{C}(v_{\lambda})$ given in Definition \ref{gildc} (Gilles et al. \cite[p.288]{gil}).

From the dividend given in (\ref{gileqaa}), it is obvious that, for every coalition $S\subseteq N$, it holds that
\[\Delta_{v_{\lambda}}(S)=\left\{\begin{array}{ll}
\lambda_{i} & \mbox{if $S=\{i\}$ for $i\in N$}\\ 0 & \mbox{otherwise}.
\end{array}\right .\]
Let $u_{\lambda}={\cal R}_{F}^{C}(v_{\lambda})$. Then, by Theorem \ref{gilt42} (ii), we can derive that, for every coalition $\emptyset\neq S\subseteq N$, we have
\[\Delta_{u_{\lambda}}(S)=\sum_{i\in N,\alpha_{C}(i)=S}\lambda_{i}.\]
By the definition of the authorizing set of a coalition and the acyclicity of $F$, it is obviou that, for $i\neq j$, it is not possible that $i\in\widehat{F}(j)$ and $j\in\widehat{F}(i)$. This implies that, for $i\neq j$, $\alpha_{C}(i)\neq\alpha_{C}(\{j\})$. Therefore, we conclude that
\begin{equation}{\label{gileq3}}\tag{6}
\Delta_{u_{\lambda}}(S)=\left\{\begin{array}{ll}
\lambda_{i} & \mbox{if $S=\alpha_{C}(i)$ for $i\in N$}\\ 0 & \mbox{otherwise}.
\end{array}\right .
\end{equation}
A well-known formula for the Shapley value, applied to the game $u_{\lambda}$, is given by
\begin{equation}{\label{gileq4}}\tag{7}
\phi_{i}(u_{\lambda})=\sum_{\{S:S\subseteq N,i\in S\}}\frac{\Delta_{u_{\lambda}}}{|S|}.
\end{equation}
We also see that
\[S=\alpha_{C}(i)=\{i\}\cup\widehat{F}^{-1}(i).\]
Let $\beta_{j}=|\widehat{F}^{-1}(\{j\})|$ for $j\in N$. Hence, substituting (\ref{gileq3}) into (\ref{gileq4}) yields
\begin{equation}{\label{gileqab}}\tag{8}
\phi_{i}(u_{\lambda})=\sum_{j\in N,i\in\alpha_{C}(i)}\frac{\lambda_{j}}{1+\beta_{j}}=\frac{\lambda_{i}}{1+\beta_{i}}+
\sum_{j\in\widehat{F}(i)}\frac{\lambda_{j}}{1+\beta_{j}}
\end{equation}
(Gilles et al. \cite[p.288]{gil}).

Example. (Gilles et al. \cite[p.288]{gil}) Consider the permission structure as given in Example \ref{gile34}. Clearly, it is acyclic. We immediately see that $\beta_{1}=0$, $\beta_{2}=1=\beta_{3}$, $\beta_{4}=2=\beta_{5}$ and $\beta_{6}=3$. Now we assign to every player the unit weight, i.e., $\boldsymbol{\lambda}=(1,\cdots ,1)\in\mathbb{R}_{++}^{6}$. The Shapley value of the conjunctive restriction of the additive game $v_{\lambda}$ is given by
\[\boldsymbol{\phi}({\cal R}_{F}^{C}(v_{\lambda}))=\frac{1}{12}\cdot(35,13,10,7,4,3).\]
Comparing this power index with the Shapley value of the original additive game $v_{\lambda}$, which is given by $\boldsymbol{\phi}(v_{\lambda})=(1,\cdots ,1)$, we conclude that a substantial shift in power has been resulting from the various positions of the players in the premission structure $F$. The leader $i\in N$, i.e., player 1, has gained a much higher payoff because of his/her leadership. $\sharp$

The expression of the Shapley value of the restriction of the additive game $v_{\lambda}$ presented in (\ref{gileqab}) is clearly
an index that measures the hierarchical power of players in the (acyclic) permission structure $F$. Taking the weights of the players into account this index only depends upon the organization structure as represented by $F$. The weight of some player $i\in N$ is equally spread over herself/himelf and her/his superiors (Gilles et al. \cite[p.289]{gil}).

Here we consider hierarchical permission structures and apply this concept to analyze organizations in which the “productive” players are in the lowest level of hierarcy (Gilles et al. \cite[p.289]{gil}). We define an asymmetric permission structure $F$ to be hierarchical if it is acyclic and, for every $i,j\in N$, there exists a player $h\in N$ such that $\{i,j\}\subseteq (\widehat{F}(h)\cup\{h\})$. The definition implies a completeness of the permission structure in the sense that every two players have either a superior-subordinate relationship or have a common superior. This requirement is equivalent to the hierarchical nature of a permission structure shown as follows. There exists a partition $L_{1},\cdots ,L_{m}$ of $N$ with
\[L_{1}=\{i\in N:F(i)=\emptyset\}\mbox{ and }L_{k}=\left\{i\in N\setminus
\bigcup_{p=1}^{k-1}L_{p}:F(i)\subseteq\bigcup_{p=1}^{k-1}L_{p}\right\}\mbox{ for }2\leq k\leq m.\]
Moreover, it can be shown that $L_{m}$ is a singleton. The sets $L_{k}$ are called the echelons or levels or the hierarchical permission
structure $F$ (Gilles et al. \cite[p.289]{gil}).

Let $S\subseteq N$ be some coalition. Then we indicate by $\gamma (S)=\{i\in S:\widehat{F}(i)\cap S=\emptyset\}$ the collection of pending players in $S$. With the definition of echelons in the permission structure $F$, we derive that $\gamma (N)=L_{1}$. With the use of the notion of pending players, we can derive an alternative characterization of an conjunctively autonomous coalition.

Proposition. (Gilles et al. \cite[p.290]{gil}). Let $T\subseteq S\subseteq N$. Then $S=\alpha_{C}(T)$ if and only if $\gamma (S) \subseteq T$ and $S=\alpha_{C}(\gamma(S))$. $\sharp$

It shows that $S\subseteq N$ is an conjunctively autonomous coalition in the hierarchical permission structure $F$ if and only if $S=\alpha_{C}(\gamma (S))$. With these notions and results we can restate the expressions for the dividends of the conjunctive restriction of a game in terms of the dividends of the original games. Let $v\in \mbox{TU}(N)$ and $u={\cal R}_{F}^{C}(v)$. Then we derive that, for $S\subseteq N$ with $S=\alpha_{C}(\gamma (S))$:
\[\Delta_{u}(S)=\sum_{\{T:\gamma (S)\subseteq T\}}\Delta_{v}(T)=
\sum_{\{F:F\subseteq\widehat{F}^{-1}(\gamma (S))}\Delta_{v}(T\cup\gamma (S)).\]
Now we turn to the description of a situation with unproductive superiors (Gilles et al. \cite[p.290]{gil}).

Let $P=\{1,\cdots ,p\}$ and $Q=\{p+1,\cdots ,p+q\}$. Define $N=P\cup Q$. Now we take a hierarchical permission structure $F$ with $Q=L_{1}=\gamma (N)$. It says that, for every $i\in Q$, $F(i)=\emptyset$. Hence, the collection $Q$ is the lowest echelon in the hierarchy as described by the permission structure $F$. It is our purpose to describe a situation in which the players in $Q$ are (potential) “productive”, while the players in $P$ are (potential) “unproductive”. However, from their positions in the hierarchy, the unproductive players or managers in $P$ can claim certain portions of the payoffs generated by the productive players or workers in $Q$ (Gilles et al. \cite[p.291]{gil}).

We construct such a game with a permission structure as follows. Let $q\in G^{Q}$ be any game on $Q$. Now we define the new game $v\in \mbox{TU}(N)$ by $v(S)=q(S\cap Q)$ for $S\subseteq N$. It is clear that $(N,v,F)$ as just constructed indeed describes a situation with managers $i\in P$ and workers $j\in Q$. The allocation of payoffs in this particular situation can be analyzed with the use of the Shapley value of the conjunctive restriction of $v$ on $F$ (Gilles et al. \cite[p.291]{gil}).

We define $u={\cal R}_{F}^{C}(v)$ as the relevant description of the productive situation. Then we have
\[\Delta_{u}(S)=\left\{\begin{array}{ll}
\Delta_{q}(S\cap Q) & \mbox{if $S=\alpha_{C}(S\cap Q)$}\\ 0 & \mbox{otherwise}.
\end{array}\right .\]
We note that the requirement that $S=\alpha_{C}(S\cap Q)$ is equivalent to the condition that $S=\alpha_{C}(\gamma (S))$ and $\gamma (S)\subseteq Q$. With use of this formulation, we can analyze the positions of the players in the production game $u$ by means of the Shapley value (Gilles et al. \cite[p.291]{gil}).

For the productive workers in $(N,v,F)$, we can deduce the following properties. Let $i\in Q$. Then we have
\[\phi_{i}(u)=\sum_{\{S:i\in S\}}\frac{{\Delta}_{u}(S)}{|S|}=\sum_{\{T:T\subseteq Q,i\in T\}}\frac{\Delta_{q}(F)}{|\alpha_{C}(T)|}.\]
Evidently, for every player $i\in T\subseteq Q$, it holds that $|\alpha_{C}(T)|\geq |T|+|\widehat{F}^{-1}(i)|=|T|+\beta_{i}$. Hence, we have
\[\frac{|T|}{|\alpha_{C}(T)|}\leq\frac{|T|}{|T|+\beta_{i}}\leq\frac{|Q|}{|Q|+\beta_{i}}.\]
This leads to the conclusion that, for every $i\in Q$,
\[\phi_{i}(u)\leq\frac{|Q|}{|Q|+\beta_{i}}\cdot\phi_{i}(q).\]
We remark that the bound is exact if and only if $i$ is the unique productive player in the game $u$, i.e., $Q=\{i\}$ (Gilles et al. \cite[p.291]{gil}).

We give a similar analysis for the “unproductive” managers in the collection $P$. For every $i\in P$, we define $Q(i)=\{T\subseteq Q:T\cap\widehat{F}(i)\neq\emptyset\}$. Then the expected payoff, represented by the Shapley value, is given by
\[\phi_{i}(u)=\sum_{\{T:T\in Q(i)\}}\frac{\Delta_{q}(T)}{|\alpha_{C}(T)|}.\]
We define $r_{i}=|\gamma (\widehat{F}(i))|$, where $\gamma (\widehat{F}(i))=Q\cap\widehat{F}(i)$. It follows that, for $i\in P$,
\[\phi_{i}(u)\geq\max_{\{j:j\in \gamma (\widehat{F}(i))\}}\phi_{j}(u)\geq
\frac{1}{r_{i}}\cdot\sum_{\{j:j\in \gamma (\widehat{F}(i))\}}\phi_{j}(u)\]
(Gilles et al. \cite[p.292]{gil}).

Example. (Gilles et al. \cite[p.292]{gil}) We take the permission structure as described in Example \ref{gile34}. It is clearly hierarchical with echelons $L_{1}=\{5,6\}$, $L_{2}=\{3,4\}$, $L_{3}=\{2\}$ and $L_{4}=\{1\}$. Take $P=N\setminus L_{1}=\{1,2,3,4\}$ and $Q=L_{1}=\{5,6\}$. Now let the game $q\in G^{Q}$ be given by $q(\emptyset )=0$, $q(\{5\})=q(\{6\})=1$ and $q(Q)=5$. Evidently, it holds that the dividends $\Delta_{q}(\{5\})=\Delta_{q}(\{6\})=1$ and $\Delta_{q}(Q)=3$. As before, we define the game $v\in \mbox{TU}(N)$ as $v(S)=q(S\cap Q)$ for every $S\subseteq N$. Applying the formula as derived above, we can compute
\[\boldsymbol{\phi}(u)=\frac{1}{12}\cdot(13,9,10,9,10,9),\]
where $u={\cal R}_{F}^{C}(v)$. This shows that the upper bound as given above for players in $Q$ indeed gives a good indication for the payoff that is actually reached under the conjunctive approach to the description of a production organization. Moreover, it shows that the lower bound for certain players in $P$ can be exact as is the case for players $2$ and $3$. $\sharp$

Let $(N,v,F)$ be a game with permission structure $F$ of $N$. The conjuntive permission value of $(N,v,F)$ is defined by $\boldsymbol{\psi}^{C}(N,v,F)= \boldsymbol{\phi}({\cal R}_{F}^{C}(v))$, where ${\cal R}_{F}^{C}(v)$ is the conjunctive restriction of $v$ in Definition \ref{van96d1} and $\boldsymbol{\phi}({\cal R}_{F}^{C}(v))$ is the Shapley value of the game ${\cal R}_{F}^{C}(v)$. If we take the trivial permission structure $F_{\emptyset}$ which is given by $F_{\emptyset}(i)=\emptyset$ for all $i\in N$, then it is easy to see that $\sigma^{C}(S)=S$ for all $S\subseteq N$ and thus the restriction ${\cal R}_{F_{\emptyset}}(v)=v$. Thus, the conjunctive value $\boldsymbol{\psi}$ is a generalization of the Shapley value for TU-games. For computing the conjunctive permission value of a game with permission structure, we derive the following formula (Van den Brink and Giles and Giles \cite[p.116]{van96}).

Proposition. (Van den Brink and Giles \cite[p.116]{van96}). Let $(N,v,F)$ be a game with permission structure $F$ of $N$. For every $latex i
in N$, we define $\Gamma_{i}=\{S\subseteq N:S\cap (\widehat{S}(i)\cup\{i\})\neq\emptyset\}$. Then
\[\psi_{i}^{C}(N,v,F)=\sum_{S\in\Gamma_{i}}\frac{\Delta_{v}(S)}{|\alpha_{C}(S)|},\]
where $\alpha_{C}(S)$ is the authorizing set of $S$ in Definition \ref{gild99} and the dividends $\Delta_{v}(S)$ are given by $\Delta_{v}(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}v(T)$. $\sharp$

Note that from this proposition, it directly follows that the conjunctive permission value is a generalization of the Shapley value, since, for $F_{\emptyset}$, it holds that $\Gamma_{i}=\{S\subseteq N:i\in S\}$ for all $i\in N$ and $|\alpha_{C}(S)|=|S|$ for all $S\subseteq N$ (Van den Brink and Giles \cite[p.117]{van96}).

In the sequel, we are going to give a set of five axioms that uniquely determine the conjunctive permission value for games with a permission structure.

Axiom BG1: (Efficiency). For every game $(N,v,F)$, it holds that $\sum_{i\in N}\psi_{i}^{C}(N,v,F)=v(N)$.
Axiom BG2: (Additivity). For games $(N,v_{1},F)$ and $(N,v_{2},F)$, it holds that $\boldsymbol{\psi}^{C}(N,v_{1}+v_{2},F)=\boldsymbol{\psi}^{C}(N,v_{1},F)+\boldsymbol{\psi}^{C}(N,v_{2},F)$.

Suppose that player $i\in N$ is a null player defined in (\ref{ga36}), i.e., $v(S)=v(S\setminus\{i\})$ for all $S\subseteq N$. Further assume that the players are not part of a permission sreucture but can do what they want without having to ask anyone for permission, Then it seems reasonable to assume that player $i$ gets a payoff equal to zero. This is the well-known dummy axiom of the Shapley value. But if the players are part of a permission structure $F$, then, although player $i$ is a dummy player in game $v$, it might be that there are other players that need his/her permission. In that case, it seems no longer reasinable to assume that player $i$ gets a zero payoff. The dummy axiom may however still be applicable for the case in which all subordinates of the dummy player $i$ are dummy players in $v$. We call such a player weakly inessential in $(N,v,F)$.

Axiom BG3: (Weakly Inessential Player Property). For every game $(N,v,F)$ and $i\in N$ such that every player $j\in\widehat{F}(i)\cup\{i\}$ is a dummy player in $v$, it holds that $\psi_{i}^{C}(N,v,F)=0$.
Axiom BG4: (Structural Monotonicity). For every game $(N,v,F)$, where $v$ is monotonic, and player $i\in N$ such that $F(i)\neq\emptyset$, it holds that $\psi_{i}^{C}(N,v,F)\geq\max_{j\in F(i)}\psi_{j}^{C}(N,v,F)$.
Axiom BG5: (Necessary Player Property). For every game $(N,v,F)$, where $v$ is monotonic, and player $i\in N$ such that $v(S)=0$ for every $S\subseteq N\setminus\{i\}$, it holds that $\psi_{i}^{C}(N,v,F)\geq\psi_{j}^{C}(N,v,F)$ for all $j\in N$.

The Axiom BG5 has the following interpretation. Suppose that player $i$ is necessary for any coalition to obtain any positive payoff in a monotone game. Then, regardless of his/her position in the permission structure, player $i$ can always guarantee that the other players
earn nothing by refusing any cooperation. Therefore, it seems fair that such a necessary player gets at least as much as any other player.
Examples can be given to show that the five axioms are independent (Van den Brink and Giles \cite[p.119]{van96}).

Theorem. (Van den Brink and Giles \cite[p.119]{van96}) An allocation rule $\boldsymbol{\psi}^{C}$ defined on the games $(N,v,F)$ is uniquely equal to the conjunctive permission value if and only if the Axioms BG1–BG5 are satisfied. $\sharp$

We can now axiomatize the conjunctive permission value restricted to the class of games with an acyclic permission structure by replacing the weakly inessental player property by two axioms (note the previous axioms will be stated on the acyclic permission structure). The first new axiom states that a player who is a dummy player in $v$ and, moreover, is powerless in the permission structure $F$ in the sense that he/she does not dominate any other player, gets a zero payoff. Suhc a player is called strongly inessential in $(N,v,F)$. Note that in determining whether a player is strongly inessential in a game with an acyclic permission structure, we look at the game and the permission structure separately. In determining whether a player is weakly inessential, we had to look at the game and the permission structure simultaneously.

Axiom BG6: (Strongly Inessential Player Property}. For every game $(N,v,F)$, where $F$ is an acyclic permission structure, and $i\in N$ such that $i$ is a dummy player in $v$ and $F(i)=\emptyset$, it holds $\psi_{i}^{C}(N,v,F)=0$.

Since every player that is strongly inessential in $(N,v,F)$ is also weakly inessential in $(N,v,F)$, the strongly inessential player property is weaker than the weakly inessential player property. The second new axiom states that the final distribution of the payoffs should not change if we delete relations in which strongly inessential players are dominated.

Axiom BG7: (Strongly Inessential Relation Property). For every game $(N,v,F)$, where $F$ is an acyclic permission structure, and $i\in N$ such that $i$ is a dummy player in $v$ and $F(i)=\emptyset$, it holds that $\psi_{j}^{C}(N,v,F)=\psi_{j}^{C}(N,v,F_{-i})$ for all $j\in N$, where $F_{-i}$ is given by $F_{-i}(j)=F(j)\setminus\{i\}$ for all $j\in N$ (Van den Brink and Giles \cite[p.123]{van96}).

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

Theorem \ref{van96t44}. (Van den Brink and Giles \cite[p.124]{van96}) An allocation rule $\boldsymbol{\psi}^{C}$ defined on the games $(N,v,F)$, where $F$ is an acyclic permission structure, is uniquely equal to the conjunctive permission value restricted to the acyclic permission structures if and only if the Axioms BG1, BG2 and BG4–BG7 are satisfied. $\sharp$

The axioms of Theorem \ref{van96t44} are not sufficient to uniquely determine the conjunctive permission value for games with an arbitrary permission structure. Examples can also be given to show that the axioms of Theorem \ref{van96t44} are independent (Van den Brink and Giles \cite[p.124]{van96}).

Now we discuss the {\bf disjunctive permission value} of $(N,v,F)$ defined by $\boldsymbol{\psi}^{D}(N,v,F)=\boldsymbol{\phi}({\cal R}_{F}^{D_{1}}(v))$, where ${\cal R}_{F}^{D_{1}}(v)$ is the disjunctive restriction of $v$ in Definition \ref{van97d201} and $\boldsymbol{\phi}({\cal R}_{F}^{D_{1}}(v))$ is the Shapley value of the game ${\cal R}_{F}^{D_{1}}(v)$ (Van den Brink \cite[p.30]{van96}).

We shall discuss a particular axiom that plays an important role in the axiomatization of the disjunctive permission value. Suppose that $i\in N$ and $j\in F(i)$ are such that the permission structure that results after the deletion of the permission relation between players $i$ and $j$ is hierarchical. The axiom states that if we delete the relation between players $i$ and $j$, then their disjunctive permission values decrease (or increase) by the same amount. Moreover, if player $k$ dominates player $i$ “completely” in the sense that all permission paths from the unique topman $i_{0}$ to player $i$ contains player $k$, then also player $k$’s disjunctive permission value changes by that same amount. This observation will be shown in Theorem \ref{van97t33} below (Van den Brink \cite[p.32]{van96}).

Given a hierachical permission structure $F$ and two players $imj\in N$ satisfying $j\in F(i)$, we define the permission structure $F_{-(i,j)}$ by
\[F_{-(i,j)}(k)=\left\{\begin{array}{ll}
F(k)\setminus \{j\} & \mbox{if $k=i$}\\ F(k) & \mbox{otherwise}.
\end{array}\right .\]
Note that in order for $F_{-(i,j)}$ to be a hierarchical permission structure it must hold that $|F^{-1}(j)|\geq 2$. If this is not the case, then $F^{-1}_{-(i,j)}(j)=\emptyset$, and thus $j\not\in\widehat{F}_{-(i,j)}(i_{0})$ (Van den Brink \cite[p.32]{van96}).

If we delete a relation in a hierarchical permission structure such that the permission structure stays hierarchical, that this leads to less
autonomous coalitions in the disjunctive approach, while it leads to more autonomous coalitions in the conjunctive approach. The following proposition presents this situation.

Proposition. (Van den Brink \cite[p.32]{van96}) Let $F$ be a hierarchical permission structure and $i,j\in N$ such that $j\in F(i)$ and $|F^{-1}(j)|\geq 2$. Then it holds that $\Phi_{F_{-(i,j)}}^{D_{2}}\subset\Phi_{F}^{D_{2}}$ and $\Phi_{F}^{C}\subset\Phi_{F_{-(i,j)}}^{C}$. $\sharp$

Next we present a proposition which states that a disjunctive autonomous coalition $S$ that does not contain player $i$ and his successor $j\in F(i)$ is still disjunctive autonomous after the deletion of the relation between $i$ and $j$.

Proposition. (Van den Brink \cite[p.33]{van96}). Let $F$ be a hierarchical permission structure and $i,j\in N$ such that $j\in F(i)$ and $|F^{-1}(j)|\geq 2$. Then it holds that $S\in\Phi_{F}^{D_{2}}$ and $S\not\supset\{i,j\}$ impies that $S\in\Phi_{F_{-(i,j)}}^{D_{2}}$. $\sharp$

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

Theorem \ref{van97t33}. {(Van den Brink \cite[p.33]{van96}) For every game $v$, every hierarchical permission structure $F$ and $latex i,j
\in N$ such that $j\in F(i)$ and $|F^{-1}(j)|\geq 2$, it holds that
\[\psi_{k}^{D}(N,v,F)-\psi_{k}^{D}(N,v,F_{-(i,j)})=\psi_{j}^{D}(N,v,F)-\psi_{j}^{D}(N,v,F_{-(i,j)})\]
for all $k\in\{i\}\cup\bar{F}^{-1}(i)$, where
\[\bar{F}^{-1}(i)=\{k\in\widehat{F}^{-1}(i):S\in\Phi_{F}^{D_{2}}\mbox{ and }i\in S\mbox{ implies that }k\in S\}. \sharp\]

An allocation rule that satisfies the condition stated in Theorem \ref{van97t33} is said to be {\bf fair}. An example shows that the conjunctive permission value is not fair (Van den Brink \cite[p.35]{van96}).

We shall present six axioms on an allocation rule that uniquely determine the disjunctive permission value for games with a hierarchical permission structure. Five of these axioms are also satisfied by the conjunctive permission value. The sixth axiom is fairness.

Axiom B1: (Efficiency). For every game $(N,v,F)$, where $F$ is a hierarchical permission structure, it holds that $\sum_{i\in N}\psi_{i}^{D}(N,v,F)=v(N)$.
Axiom B2: (Additivity). For games $(N,v_{1},F)$ and $(N,v_{2},F)$, where $F$ is a hierarchical permission structure, it holds that
$\boldsymbol{\psi}^{D}(N,v_{1}+v_{2},F)=\boldsymbol{\psi}^{D}(N,v_{1},F)+\boldsymbol{\psi}^{D}(N,v_{2},F)$.
Axiom B3: (Inessential Player Property). For every game $(N,v,F)$, where $F$ is a hierarchical permission structure, and $i\in N$ such that every player $j\in\widehat{F}(i)\cup\{i\}$ is a dummy player in $v$, it holds that $\psi_{i}^{D}(N,v,F)=0$.
Axiom B4: (Necessary Player Property). For every game $(N,v,F)$, where $v$ is monotonic and $F$ is a hierarchical permission structure, and player $i\in N$ such that $v(S)=0$ for every $S\subseteq N\setminus\{i\}$, it holds that $\psi_{i}^{D}(N,v,F)\geq\psi_{j}^{D}(N,v,F)$ for all $j\in N$.
Axiom B5: (Weak Structural Monotonicity). For every game $(N,v,F)$, where $v$ is monotonic and $F$ is a hierarchical permission structure, and player $i\in N$, it holds that $\psi_{i}^{D}(N,v,F)\geq\psi_{j}^{D}(N,v,F)$ for all $j\in\bar{F}(i)$, where
\[\bar{F}(i)=\{j\in N:i\in\bar{F}^{-1}(j)\}=\{j\in\widehat{F}(i):S\in\Phi_{F}^{D_{2}}\mbox{ and }j\in S\mbox{ implies that }i\in S\}.\]

As shown in Axiom BG4, the structural monotonicity states that a player in a monotone game with a permission structure gets at least as much as any of his/her subordinates. Here in Axiom B5, we consider a weaker version of structural monotonicity. It says that if player $i$ dominates player $j$ “completely” in the sense that all permission paths from the topman $i_{0}$ to player $j$ contain player $i$, then $i$ gets at least as much as $j$ if the game is monotone.

Axiom B6: (Fairness). For every game $v$, every hierarchical permission structure $F$ and $i,j\in N$ such that $j\in F(i)$ and $|F^{-1}(j)|\geq 2$, it holds that
\[\psi_{k}^{D}(N,v,F)-\psi_{k}^{D}(N,v,F_{-(i,j)})=\psi_{j}^{D}(N,v,F)-\psi_{j}^{D}(N,v,F_{-(i,j)})\]
for all $k\in\{i\}\cup\bar{F}^{-1}(i)$.

Examples can be given to show that the six axioms are independent (Van den Brink \cite[p.37-38]{van96}).

\begin{equation}{\label{van96t44}}\tag{11}\mbox{}\end{equation}

Theorem \ref{van96t44}. (Van den Brink \cite[p.38]{van96}) An allocation rule $\boldsymbol{\psi}^{D}$ defined on the games $(N,v,F)$, where $F$ is a hierarchical permission structure, is uniquely equal to the disjunctive permission value if and only if the Axioms B1–B6 are satisfied. $\sharp$

We are going to generalize the above approaches.

\begin{equation}{\label{der93da}}\tag{12}\mbox{}\end{equation}

Definition \ref{der93da}. (Derks and Peters \cite[p.352]{der93}). The map $\rho :2^{N}\rightarrow 2^{N}$ is a restriction if the following conditions are satisfied.

For all $S\subseteq N$, we have $\rho (S)\subseteq S$;
For all $S,T\in 2^{N}$, if $S\subseteq T$ then $\rho (S)\subseteq\rho (T)$;
For all $S\subseteq N$, we have $\rho (\rho (S))=\rho (S)$. $\sharp$

It says that a restriction is a monotonic projection (i.e., the second and third conditions) assigning to each coalition a subcoalition (i.e., the first condition). With each restriction $\rho$, we associate a restricted Shapley value $\boldsymbol{\phi}^{\rho}$ given by
\[\phi_{i}^{\rho}(v)=\sum_{\{S:i\not\in S\}}\frac{|S|!(|N|-|S|-1)!}{|N|!}\cdot\left [v(\rho (S\cup\{i\}))-v(\rho (S))\right ]\]
for every $i\in N$. If $\rho$ is the identity, then $\boldsymbol{\phi}^{\rho}$ is the familiar Shapley value, and we write $\boldsymbol{\phi}$ instead of $\boldsymbol{\phi}^{\rho}$. Obviously $\boldsymbol{\phi}^{\rho}(v)=\boldsymbol{\phi}(v\circ\rho )$ for every restriction $\rho$ and every game $v$. In Example \ref{der93exa}, we see that $u=v\circ\rho$, where $latex \rho (\{1,3\})=
\{1\}$, $\rho (\{3\})=\emptyset$ and $\rho (S)=S$ otherwise. Apparently, $latex \boldsymbol{\phi}(u)=\boldsymbol{\phi}(v\circ\rho )=
\boldsymbol{\phi}^{\rho}$, so the Shapley value of $u$ is obtained by applying an appropriately restricted value to $v$ (Derks and Peters \cite[p.352]{der93}).

Let $\rho$ be a restriction and let
\[Im(\rho)=\{S\subseteq N:S=\rho (T)\mbox{ for }T\subseteq N\}\]
be the image} of $\rho$. By (i) in Definition \ref{der93da}, we see that $\rho (\emptyset )=\emptyset$. Further, for $S,T\in Im(\rho )$,
we have
\[S\cup T=\rho (S)\cup\rho (T)\subseteq\rho (S\cup T)\subseteq S\cup T,\] where the equality follows from the third condition, the first inclusion follows from the second condition, (since $\rho (S)\subseteq\rho (S\cup T)$ and $\rho (T)\subseteq\rho (S\cup T)$), and the last inclusion from (i) in definition \ref{der93da}, respectively. Consequently, $S\cup T=\rho (S\cup T)$, i.e., $S\cup T\in Im(\rho )$. So the image of a restriction is closed under union and contains the empty set. Conversely, let $\Omega$ be a subset of $2^{N}$ with these two properties, i.e., $\Omega$ is closed under union and contains the empty set. Let the map $\rho^{\Omega}:2^{N}\rightarrow 2^{N}$ assign to each $S\subseteq N$ its largest subset in $\Omega$, i.e., $\rho^{\Omega}(S)\in\Omega$ and $\rho^{\Omega}(S)$ is the largest subset of $S$, or, we can write
\[\rho^{\Omega}(S)=\bigcup_{\{T:T\in (\Omega\cap 2^{S})\}}T.\]
It is straightforward to check that $\rho^{\Omega}$ is a restriction, and $Im(\rho^{\Omega})=\Omega$. Further, for a restriction $\rho$ and, for each $S\subseteq N$, the set $\rho (S)$ is contained in $Im(\rho )$; and, for each subset $T$ of $S$ with $T\in Im(\rho )$, we have $T=\rho (T)\subseteq\rho (S)$ by (ii) in Definition \ref{der93da}, implying
\[\rho (S)=\bigcup_{T\in (Im(\rho )\cap 2^{S})\}}T=\rho^{Im(\rho )}(S).\]
Therefore, $\rho =\rho^{Im(\rho )}$, i.e., $\rho$ is completely determined by its image. We present the above results in the following proposition (Derks and Peters \cite[p.353]{der93}).

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

Proposition \ref{der93l31}. (Derks and Peters \cite[p.353]{der93}).
Let $(N,v)$ be a cooperative game. Then, we have the following properties.

(i) For any restriction $\rho$, $Im(\rho )$ is closed under union and contains the empty set.

(ii) If $\Omega\subseteq 2^{N}$ is closed under union and contains the empty set, then $\rho^{\Omega}$ is a restriction.

(iii) For any restriction $\rho$, we have $\rho =\rho^{Im(\rho )}$. $\sharp$

Let $v$ be a game and $\Omega\subseteq 2^{N}$ with $\emptyset\in\Omega$. We define the map $\Delta_{v}^{\Omega}:\Omega\rightarrow\mathbb{R}$ recursively by
\[\Delta_{v}^{\Omega}(S)=\left\{\begin{array}{ll}
0 & \mbox{if $S=\emptyset$}\\
v(S)-\sum_{\{T\subseteq S:T\in\Omega\setminus\{S\}\}}\Delta_{v}^{\Omega}(T) &
\mbox{if $S\in\Omega\setminus\{\emptyset\}$}.\end{array}\right .\]
The number $\Delta_{v}^{\Omega}$ is interpreted as the additional dividend the coalition $S$ obtains if it is formed, given that all proper formable (i.e., in $\Omega$) subcoalitions have been formed already. For $\Omega=2^{N}$, we write $\Delta_{v}$ instead of $\Delta_{v}^{2^{N}}$. It is well known that, for any game $v$,
\begin{equation}{\label{der93eq31}}\tag{14}
v=\sum_{S\subseteq N}\Delta_{n}(S)\cdot u_{S},
\end{equation}
where $u_{S}$ denotes the unanimity game (Derks and Peters \cite[p.353]{der93}).

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

Proposition \ref{der93l31}. (Derks and Peters \cite[p.353]{der93}). Let $v$ be a game and $\rho$ be a restriction. Let $\Omega =Im(\rho )$. Then, we have
\[\Delta_{v\circ\rho}(S)=\left\{\begin{array}{ll}
0 & \mbox{if $S\not\in\Omega$}\\ \Delta_{v}^{\Omega} & \mbox{if $S\in\Omega$}
\end{array}\right .\]
for each $S\subseteq N$. $\sharp$

Proposition \ref{der93l31} and (\ref{der93eq31}) immediately imply the following result.

Corollary. (Derks and Peters \cite[p.354]{der93}). For every game $v$ and restriction $\rho$, we have
\[v\circ\rho =\sum_{\{S:S\in Im(\rho )\}}\Delta_{v\circ\rho}(S)\cdot u_{S}. \sharp\]

Another well-known fact is the following formula for the Shapley value $\boldsymbol{\phi}$. Let $v$ be a game. Then, for $i\in N$,
\begin{equation}{\label{der93eq33}}\tag{16}
\phi_{i}(v)=\sum_{\{S:i\in S\}}\frac{\Delta_{v}(S)}{|S|},
\end{equation}
i.e., the Shapley value assigns to each player the sum of his proportion of the dividends obtained by those coalitions of which he/she is a member. This can be derived from (\ref{der93eq31}). We also see that Proposition \ref{der93l31} and (\ref{der93eq33}) obviously imply
\[\phi_{i}^{\rho}(v)=\phi_{i}(v\circ\rho )=\sum_{\{S:i\in S,S\in Im(\rho )\}}\frac{\Delta_{v}^{Im(\rho )}(S)}{|S|}\]
for every restriction $\rho$ and player $i\in N$. This provides an alternative expression for restricted Shapley values (Derks and Peters \cite[p.354-355]{der93}).

In the sequel, we are going to present an axiomatic characterization of restricted Shapley values. The axioms will be formulated for a so-called value $\boldsymbol{\psi}:\mbox{TU}(N)\rightarrow\mathbb{R}^{N}$. A restriction $\rho$ will not be exogenously given, but endogenously determined by the axioms (Derks and Peters \cite[p.355]{der93}).

Definition. (Derks and Peters \cite[p.355]{der93}). Let $S$ be a coalition. We call $S$ $\boldsymbol{\psi}$-essential if $S=\emptyset$ or for all $u,v\in \mbox{TU}(N)$ with $u(T)=v(T)$ for all $T\neq S$, we have: if $v(S)\neq u(S)$ then $\boldsymbol{\psi}(v)= \boldsymbol{\psi}(u)$. We call $S$ $\boldsymbol{\psi}$-inessential if $S\neq\emptyset$ and for all $u,v\in \mbox{TU}(N)$ with $u(T)=v(T)$ for all $T\neq S$, we have $\boldsymbol{\psi}(u)=\boldsymbol{\psi}(v)$. $\sharp$

Observe that the worth of a nonempty $\boldsymbol{\psi}$-essential coalition always matters for the distribution $\boldsymbol{\psi}(v)$, whereas the worth of a $\boldsymbol{\psi}$-inessential coalition never matters. The empty set is defined to be $\boldsymbol{\psi}$-essential just for convenience; it guarantees the existence of maximal $\boldsymbol{\psi}$-essential coalition, i.e., $\boldsymbol{\psi}$-essential coalition $S$ such that no proper superset of $S$ is $\boldsymbol{\psi}$-essential. We recall that a player $i\in N$ is a veto player in a game $v$ if $v(S)=0$ for every $S$ with $i\not\in S$ (Derks and Peters \cite[p.355]{der93}).

For a value $\boldsymbol{\psi}$, the axioms are as follows.

(a) Every coalition $S$ is $\boldsymbol{\psi}$-essential or $\boldsymbol{\psi}$-inessential.
(b) If $S$ and $T$ are $\boldsymbol{\psi}$-essential coalitons, then so is $S\cup T$.
(c) For every game $v$, $\sum_{i\in N}\psi_{i}(v)=v(S)$ for some maxial $\boldsymbol{\psi}$-essential coalition $S$.
(d) For all $u,v\in \mbox{TU}(N)$ and $i\in N$, if, for all $S,T$ with $T$ $\boldsymbol{\psi}$-essential, $i]in T$ and $S$ a maximal $\boldsymbol{\psi}$-essential subcoalition of $T\setminus\{i\}$, we have that if $v(T)-v(S)\geq u(T)-u(S)$, then $\psi_{i}(v)\geq\psi_{i}(u)$.
(e) For every game $v$ and $i,j\in N$, if $i$ and $j$ are veto players in $v$, then $\psi_{i}(v)=\psi_{j}(v)$.

Axiom (a) excludes the existence of a coalition whose worth is taken into account by $\boldsymbol{\psi}$ in one game but not in some other game. Axiom (b) states that if the worths of coalitions $S$ and $T$ always matter for the determination of $\boldsymbol{\psi}$, then so should the worth of the union $S\cup T$. Axiom (c) is a generalization of the usual efficiency axiom. Similarly, axiom (d) generalizes the monotonicity axiom. Axiom (e) states that veto players in a game should be treated as equally powerful (Derks and Peters \cite[p.355]{der93}).

Theorem. (Derks and Peters \cite[p.356-358]{der93}) Let $\rho$ be a restriction. Then $\boldsymbol{\phi}^{\rho}$ satisfies axioms (a)–(e). Let $\boldsymbol{\psi}$ be a value satisfying axioms (a)}–(e). Then there exists a unique restriction $\rho$ such that $\boldsymbol{\psi}=\boldsymbol{\phi}^{\rho}$. In other words, a value satisfies axioms {\em (i)}-{\em (v)} if and only if it is a restricted Shapley value. $\sharp$

Let us recall that the permission structure $F:N\rightarrow 2^{N}$ with the property that if $j\in F(i)$ then $i\not\in F*j)$. Let $\Omega_{F}^{c}$ denote the collection of those coaltions $S$ with the property that if $i\in S$, then also every $j$ with $i\in F(j)$ is in $S$ for every $i\in N$. Let $\Omega_{F}^{d}$ denote the collection of those coalitions $S$ with the property that if $i\in S$, then at least one $j\in N$ with $i\in F(j)$ is in $S$ (if such a $j$ exists) for every $i\in N$. It is easily established that both $\Omega_{F}^{c}$ (“c” for conjunctive) and $\Omega_{F}^{d}$ (“d” for disjunctive) are closed under union and contain the empty set, so that Proposition \ref{der93l31} both can be described as the image of a restriction. Also, the variant of the Shapley value proposed by Gilles et al. \cite{gil} coincides with the concept of a restricted Shapley value (Derks and Peters \cite[p.358]{der93}).

The method proposed here can also be used to define a Shapley value for so-called multi-choice games as introduced by Hsiao and Raghavan \cite{hsi93}. A multi-choice game is a refinement of a transferable utility game in the sense that each player $i$ has a finite number of “activity levels” $\beta_{0}^{(i)}<\beta_{1}^{(i)}<\cdots <\beta_{m}^{(i)}$. Level $\beta_{0}^{(i)}$ is interpreted as “not present”. A coalition is an $n$ tuple of activity levels, one for each player, and each coalition is assigned a real number, its worth. One can regard each activity level of each player as a separate player and define a permission structure $F$ by $F(\beta_{j}^{(i)})=\beta_{j+1}^{(i)}$ for every $i$ and every $0\leq j<m$, $F(\beta_{m}^{(i)})=0$ for every $i$. This $F$ is acyclic
and $\Omega_{F}^{c}$ contains exactly those “coalitions” which for each activity level of a member also contains all lower activity levels.
Such a “coalition” for the extended player set is given the worth of the corresponding coalition in the multi-choice game, obtained by taking for each playr his highest acitivity level occurring in the “coalition” within the extended player set. As before, $\Omega_{F}^{c}$ is the image of a restriction on the extended player set, to whcih a restricted Shapley value can be associated. Hsiao and Raghavan \cite{hsi93} also propose a Shapley value for multi-choice game. Again, the two approaches are different from each other. Consider the unanimity game, which in this context is determined by a vector $\widehat{\boldsymbol{\beta}}\in A\equiv\times_{i=1}^{n}\{\beta_{0}^{(i)},\cdots m\beta_{m}^{(i)}\}$ such that a coalition $\boldsymbol{\beta}\in A$ has worth $1$ if $\boldsymbol{\beta}\geq\widehat{\boldsymbol{\beta}}$, and $0$ otherwise. A Shapley value as proposed by Hsiao and Raghavan \cite{hsi93} distributes the worth of the grand coalition (which equals $1$) among the levels of “players” occurring in $\widehat{\boldsymbol{\beta}}$, and, in an equal fashion, to all $n$-tuples of higher levels. The restricted Shapley value proposed here distributes $1$ among the levels not exceeding those occurring in $\widehat{\boldsymbol{\beta}}$. In Hsiao and Raghavan’s model, each player can onlt be present at one specific level. In our adaptation of their model, the presence of a player at a certain level implies the presence of that player at all lower levels. This distinction largely accounts for the distinction between the respective Shapley values. In fact, Hsiao and Raghavan’s Shaplet value may be transformed into the restricted Shapley value proposed here for this special contex of multi-choice games (This requires an appropriate choice of weights for the Hsiao and Raghavan Shapley value.) (Derks and Peters \cite[p.359]{der93}).

We consider another generalization for the permission structure. The cooperative games on antimatroids are cooperative games restricted by a combinatorial structure which generalize the permission structure.

Definition. (Algaba et al. \cite[p.51]{alg03}). An antimatroid ${\cal A}$ of $N$ is a family of subsets of $2^{N}$
satisfying the following conditions:

$\emptyset\in {\cal A}$;
(Accessibility). If $\emptyset\neq S\in {\cal A}$, then there exists $i\in S$ such that $S\setminus\{i\}\in {\cal A}$;
(Closed under Union). If $S,T\in {\cal A}$, then $S\cup T\in {\cal A}$;
(Normality). For every $i\in N$, there exists an $S\in {\cal A}$ such that $i\in S$. $\sharp$

The coalitions in the antimatroid are also called the feasible coalitions. Let ${\cal A}$ be an antimatroid of $N$. This family allows to define the interior operator $\mbox{int}_{\cal A}:2^{N}\rightarrow {\cal A}$ given by $\mbox{int}_{\cal A}(S)=\bigcup_{T\subseteq S}T\in {\cal A}$ for all $S\subseteq N$. This operator satisfies the following properties:

$\mbox{int}_{\cal A}(\emptyset )=\emptyset$;
$\mbox{int}_{\cal A}(S)\subseteq S$;
if $S\subseteq T$, then $\mbox{int}_{\cal A}(S)\subseteq\mbox{int}_{\cal A}(T)$;
$\mbox{int}_{\cal A}(\mbox{int}_{\cal A}(S))=\mbox{int}_{\cal A}(S)$;
if $i,j\in\mbox{int}_{\cal A}(S)$ and $j\not\in\mbox{int}_{\cal A}(S\setminus\{i\})$, then $i\in\mbox{int}_{\cal A}(E\setminus\{j\})$. (Algaba et al. \cite[p.51]{alg03})

Let ${\cal A}$ be an antimatroid of $N$. An endpoint or extreme point of $S\in {\cal A}$ is a player $i\in S$ such that $S\setminus\{i\}\in {\cal A}$. By condition (ii) of accessibility, every nonempty coalition in ${\cal A}$ has at least one endpoint. A set $S\in {\cal A}$ is a path in ${\cal A}$ if it has a single endpoint. The path $S\in {\cal A}$ is called a $i$-path in ${\cal A}$ if it has $i\in N$ as unique endpoint. A coalition $S\in {\cal A}$ if and only if $S$ is a union of paths. Moreover, for every $S\in {\cal A}$ with $i\in S$, there exists an $i$-path $T$ such that $T\subseteq S$. The set of $i$-paths for a given player $i\in N$ will be denoted by $A(i)$ (Algaba et al. \cite[p.51]{alg03}).

Definition. (Algaba et al. \cite[p.52]{alg03}). An antimatroid ${\cal A}$ of $N$ is said to have the path property if the following conditions are satisfied.

Every path $S$ has a unique feasible ordering, i.e., $E\equiv (i_{1}>\cdots >i_{t})$ such that $\{i_{1},\cdots ,i_{k}\}\in {\cal A}$ for all $1\leq k\leq t$. Furthermore, the union of these orderings for all paths is a partial ordering of $N$.
If $S,T$ and $S\setminus\{i\}$ are paths such that the endpoint of $T$ equals the endpoint of $S\setminus\{i\}$, then $latex T\cup\{i\}\in
{\cal A}$. $\sharp$

Observe that every path has a unique feasible ordering if and only if for any $i$-path $S$ with $|S|>1$ we have that $S\setminus\{i\}$ is a path. A special case of antimatroids are the poset antimatroid being antimatroid that are closed inder intersection
(Algaba et al. \cite[p.52]{alg03}).

Definition. (Algaba et al. \cite[p.52]{alg03}). An antimatroid ${\cal A}$ is a poset antimatroid if $S\cap T\in {\cal A}$ for every $S,T\in {\cal A}$. $\sharp$

For a coopeative game $v$ and an antimatroid ${\cal A}$ of $N$, we define the restricted game $v_{\cal A}$ which assigns to every coalition $S$ the worth generated by the inetrior of $S$, i.e., $v_{\cal A}(S)=v(\mbox{int}_{\cal A}(S))$ for all $S\subseteq N$. A solution for games on antimatroid is a function $\boldsymbol{\phi}$ that assigns a payoff vector $\boldsymbol{\phi}(v,{\cal A})\in\mathbb{R}^{N}$. The restricted Shapley value $\bar{\boldsymbol{\phi}}(v,{\cal A})$ for a cooperative game $v$ and an antimatroid ${\cal A}$ of $N$ is obtained by applying the Shapley value to the restricted game $v_{\cal A}$, i.e.,
\[\bar{\phi}_{i}(v,{\cal A})=\phi_{i}(v_{\cal A})=\sum_{\{S:i\in S\subseteq N\}}\frac{d_{v_{\cal A}}(S)}{|S|},\]
where
\[d_{v_{\cal A}}(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}v_{\cal A}(T)\]
denotes the dividend of the coalition $S$ in game $v_{\cal A}$ (Algaba et al. \cite[p.52]{alg03}).

Let $F$ be an acyclis permission structure. We can show that the conjunctively autonomous $\Phi_{F}^{C}$ in Definition \ref{gilde} and the disjunctively autonomous $\Phi_{F}^{D_{1}}$ in Definition \ref{van97d200} or $\Phi_{F}^{D_{2}}$ in Definition \ref{gil99d200} are antimatriodsof $N$. A solution for games with a permission structure is a function $\boldsymbol{\phi}$ that assigns a payoff vector
$\boldsymbol{\phi}(v,F)\in\mathbb{R}^{N}$ to every cooperative game $v$ and permission structure $F$. The conjunctive permission value is obtained by applying the Shapley value to the conjunctive restricted game $v_{\Phi_{F}^{C}}$, while the disjunctive permission value is obtained by applying the Shapley value to the disjunctive restricted games $v_{\Phi_{F}^{D_{1}}}$ or $v_{\Phi_{F}^{D_{2}}}$, i.e., they are the restricted values $\bar{\boldsymbol{\phi}}(v,\Phi_{F}^{C})=\boldsymbol{\phi}(v_{\Phi_{F}^{C}})$ and
$\bar{\boldsymbol{\phi}}(v,\Phi_{F}^{D_{1}})=\boldsymbol{\phi}(v_{\Phi_{F}^{D_{1}}})$ or $\bar{\boldsymbol{\phi}}(v,\Phi_{F}^{D_{2}})=\boldsymbol{\phi}(v_{\Phi_{F}^{D_{2}}})$, respectively. The purpose is to generalize axiomatization given for the conjunctive and disjunctive permission values to obtain axiomatizations of the restricted Shapley value for cooperative games on antimatroid (Algaba et al. \cite[p.53]{alg03}).

The first three axioms are straightforward generalization of efficiency, additivity and the necessary player property for cooperative games with a permission structure.

Axiom ABBJ1: (Efficiency). For every cooperative game $v$ and an antimatroid ${\cal A}$ of $N$, we have $\sum_{i\in N}\bar{\phi}_{i}(v,{\cal A})=v(N)$;
Axiom ABBJ2: (Additivity). For every pair of cooperative games $v_{1}$, $v_{2}$ and an antimatroid ${\cal A}$ of $N$, we have $\bar{\boldsymbol{\phi}}(v_{1}+v_{2},{\cal A})=\bar{\boldsymbol{\phi}}(v_{1},{\cal A})+\bar{\boldsymbol{\phi}}(v_{2},{\cal A})$;
Axiom ABBJ3: (Necessary Player Property). For every cooperative game $v$ and an antimatroid ${\cal A}$ of $N$, if $i\in N$ satisfies $v(S)=0$ for all $S\subseteq N\setminus\{i\}$, then $\bar{\phi}_{i}(v,{\cal A})\geq \bar{\phi}_{j}(v,{\cal A})$ for all $j\in N$.

Note that the necessary player axiom requires that all necessary players get the same payoff. Recall that player $i$ is inessential in a game $v$ with permission structure $F$ of $N$ if $i$ and all its subrdinates are null players in a game $v$. This concept extends the one of null player in a game $v$. Let ${\cal A}$ be an antimatroid of $N$. The path group $P^{i}$ of player $i$ is defined as the set of players that are in some $i$-path, i.e., $P^{i}=\bigcup_{S\in A(i)}S$. So, the path group of player $i$ are all players on which $i$ has some dependence. Now, given an antimatroid ${\cal A}$ of $N$, we call $i\in N$ an inessential player for ${\cal A}$ in $v$ if player $i$ and every player $j\in N$ such that $i\in P^{j}$ are null players in $v$.

Axiom ABBJ4: (Inessential Player Property). For every cooperative game $v$ and an antimatroid ${\cal A}$ of $N$, if $i$ is an inessential player for ${\cal A}$ in $v$, then $\bar{\phi}_{i}(v,{\cal A})=0$.

We generalize structural monotonicity for games with a permission structure by introducing a new set. Let ${\cal A}$ be an antimatroid of $N$. The basic path group $P_{i}$ of player $i$ is given by those players that are in every $i$-path, i.e., $P_{i}=\bigcap_{S\in A(i)}S$. This set is formed by those players that control totally player $i$ in ${\cal A}$, i.e., without them player $i$ cannot form any feasible coalition. Obviously, $i\in P_{i}$ and $P_{i}\subseteq P^{i}$.

Axiom ABBJ5: (Structural Monotonicity). For every cooperative game $v$ and an antimatroid ${\cal A}$ of $N$, if $j\in N$ then, for all $i\in P_{j}$, we have $\bar{\phi}_{i}(v,{\cal A})\geq\bar{\phi}_{j}(v,{\cal A})$.

We can generalize both conjunctive and disjunctive fairness for games with a permission structure by requiring that deleting a feasible coalition $S$ from antimatroid ${\cal A}$, such that ${\cal A}\setminus\{S\}$ is also an antimatroid, changes the payoffs of all players in $S$ by the same amout.

Axiom ABBJ6: (Fairness). For every cooperative game $v$ and an antimatroid ${\cal A}$ of $N$, if $S\in {\cal A}$ is such that ${\cal A}\setminus\{S\}$ is an antimatroid of $N$, then
\[\bar{\phi}_{i}(v,{\cal A})-\bar{\phi}_{i}(v,{\cal A}\setminus\{S\})=\bar{\phi}_{j}(v,{\cal A})-\bar{\phi}_{j}(v,{\cal A}\setminus\{S\})\]
for all $i,j\in S$.

An example shows that in general to delete a feasible coalition from an antimatroid does not always given an antimatroid. Note that given a
permission structure $F$, applying ths fairness axiom to the antimatroid $\Phi_{F}^{C}$ (resp. $\Phi_{F}^{D_{1}}$ or $\Phi_{F}^{D_{2}}$) is equivalent to applying conjunctive (resp. disjunctive) fairness to the corresponding game with permission structure. We say that coalition $T\in {\cal A}$ {\bf covres} coalition $S\in {\cal A}$ if $S\subseteq T$ and $|T|=|S|+1$ (Algaba et al. \cite[p.53-54]{alg03}).

Proposition. (Algaba et al. \cite[p.55]{alg03}). Let ${\cal A}$ be an antimatroid of $N$ and $S\in {\cal A}$. Then ${\cal A}\setminus\{S\}$ is an antimatroid if and only if $S$ is a path, $S\not\in\{\emptyset ,N\}$ and every $T\in {\cal A}$ that covers $S$ is not a path. $\sharp$

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

Theorem \ref{alg03t2}. (Algaba et al. \cite[p.55,58]{alg03}). The restricted Shapley value satisfies Axioms ABBJ1–ABBJ6. Furthermore, a solution for games on antimatroids is equal to the restricted Shapley value if and only if it satisfies the Axioms ABBJ1–ABBJ6. $\sharp$

We can show that the six axioms stated in Theorem \ref{alg03t2} are logically independent Deleting fairness from the set of axioms stated in Theorem \ref{alg03t2} characterizes the restricted Shapley value for games on poset antimatroid. Moreover, poset antimatroid are the unique antimatroids for which it is possible to delete the fairness axiom. Poset antimatroids are the unique antimatroids such that every player has a unique path. In particular, we can conclude that given an antimatroid ${\cal A}$ of $N$, ${\cal A}$ is a poset antimatroid if and only if $P_{i}=P^{i}$ for all $i\in N$ (Algaba et al. \cite[p.61]{alg03}).

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

Theorem \ref{alg03t3}. (Algaba et al. \cite[p.61]{alg03}). A solution for games on poset antimatroids is equal to the restricted Shapley value if and only if it satisfies the Axioms ABBJ1–ABBJ5. $\sharp$

We can show that the six axioms stated in Theorem \ref{alg03t3} are logically independent. For games on poset antimatroids, the restricted Shapley value can be written as follows (Algaba et al. \cite[p.61]{alg03}).

Proposition. (Algaba et al. \cite[p.62]{alg03}). If ${\cal A}$ is a poset antimatroid of $N$, then the restricted Shapley value is given by
\[\bar{\phi}_{i}(v,{\cal A})=\sum_{\{S\subset N:i\in P^{S}\}}\frac{d_{v}(S)}{|P^{S}|},\]
where $P^{S}=\bigcup_{i\in S}P^{i}$. $\sharp$

Theorem. (Algaba et al. \cite[p.62]{alg03}). Let ${\cal A}$ be an antimatroid of $N$. Then ${\cal A}$ is a poset antimatroid if and only if the restricted Shapley value $\bar{\boldsymbol{\phi}}(\cdot,{\cal A})$ is the unique solution satisfying the Axioms ABBJ1–ABBJ5. $\sharp$

Corollary. (Algaba et al. \cite[p.63]{alg03}). Let ${\cal A}$ be a poset antimatroid of $N$ satisfying the path property. Then the restricted Shapley value $\bar{\boldsymbol{\phi}}(\cdot,{\cal A})$ is the unique solution satisfying the Axioms ABBJ1–ABBJ5. $\sharp$

Games under Preference Cosntraints.

We shall investigate the Shapley value of a special type of game with restricted cooperation. We assume the set of players to be partially ordered by some preference relation as in Definition \ref{fai92d2}. Only those coalitions are considered feasible that satisfy the precedence constraints in the following sense: if a players $k$ is member of a coalition $S$, then all players preceding $k$ must be members of the same coalition $S$ as well (Faigle and Kern \cite[p.250]{fai92}).

Let us recall that $G^{(N,\preceq )}$ is the vector space of all cooperative games on $P$. The Shapley value we seek will be a vector-valued function $\boldsymbol{\phi}:G^{(N,\preceq )}\rightarrow\mathbb{R}^{N}$ that assigns to each player $i\in N$ his/her share $\phi_{i}(v)$ relative to the game $v$. The function $\boldsymbol{\phi}$ should respect some fundamental axioms that one may feel are reasonable demands for $\boldsymbol{\phi}$ to be a fair solution concept. Moreover, we shall see that $\boldsymbol{\phi}$ should reduce to the conventional Shapley value in the case where $P$ is trivially ordered (Faigle and Kern \cite[p.251-252]{fai92}).

We say that a coalition $T\in {\cal C}$ is a {\bf carrier} for $v\in G^{(N,\preceq )}$ if $v(S)=v(S\cap T)$ for all $S\in {\cal C}$. We say that an injective map $\pi :N\rightarrow \{1,2,\cdots ,|N|\}$ is a ranking of the players in $N$ if, for all $i,j\in N$, we have that $i\prec j$ implies $\pi (i)<\pi (j)$. The ranking $\pi$ of $N$ induces a ranking $\pi_{S}:S\rightarrow\{1,2,\cdots ,|S|\}$ of and coalition $S\in {\cal C}$ in a natural way via $\pi_{S}(i)<\pi_{S}(j)$ if and only if $\pi (i)<\pi (j)$ for all $i,j\in S$. Thus we may define $k\in S$ to be $S$-maximal in the ranking $\pi$ if $\pi_{S}(k)=|S|$, or, equivalently, $\pi (k)=\max_{i\in S}\pi (i)$. The hierarchical strength $h_{S}(k)$ in $S$ of the player $k\in S$ is defined by the average number of rankings $\pi$ in which $k$ is $S$-maximal, i.e.,
\[h_{S}(k)=\frac{1}{|\Pi (N)|}\cdot\left |\{\pi\in \Pi (N):\mbox{$k$ is $S$-maximal in $\pi$}\}\right |,\]
where $\Pi (N)$ denotes the collection of all rankings of the set $N$ of players. In the case of a trivially ordered $P$, $\Pi (N)$ coincides with all permutations of $N$ and all players in any coalition $S\subseteq N$ share the same hierarchical strength (Faigle and Kern \cite[p.254]{fai92}).

Proposition. (Faigle and Kern \cite[p.253]{fai92}). If $v=\sum_{S}c_{S}\zeta_{S}$ is an arbitrary game in $G^{(N,\preceq )}$, then each carrier $T$ of $v$ is a carrier for every $\zeta_{S}$ with $c_{S}\neq 0$ in the representation of $v$. $\sharp$

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

Proposition \ref{fai92l4}. (Faigle and Kern \cite[p.254]{fai92}). For all $S\in {\cal C}$ and $k\in S$, $h_{S}(k)\neq 0$ if and only if $k$ is a maximal element in $S$. $\sharp$

Let us recall the definition of convex geometry in Definition \ref{bil98d2}. A compatible ordering of a convex geometry ${\cal L}\subseteq 2^{N}$ is a total ordering of the elements of $N$, $i_{1}<i_{2}<\cdots <i_{n}$ such that the set $\{i_{1},i_{2},\cdots ,i_{k}\}\in {\cal L}$ for all $1\leq k\leq n$. A compatible ordering of ${\cal L}$ corresponds exactly to a maximal chain in ${\cal L}$. We will denote the set of all compatible orderings by ${\cal R}({\cal L})$. Given an element $i\in N$ and a compatible ordering $C$ of ${\cal L}$, we let $C(i)=\{j\in N:i\preceq i\mbox{ in }C\}$. Let $S\in {\cal L}$ and $i\in S$. The hierarchical strength $h_{S}(i)$ of $i$ in $S$ can be rewritten as
\[h_{S}(i)=\frac{|\{C\in {\cal R}({\cal L}):C(i)\cap S=S\}}{|{\cal R}({\cal L})|},\]
i.e., $h_{S}(i)$ is the everage number of compatible orderings of ${\cal L}$ in which $i$ is the last member of $S$ in the ordering. Note that $h_{S}(i)\neq0$ if and only if $i\in\mbox{ext}(S)$, where $\mbox{ext}(S)$ is defined in Definition \ref{bil98d2} (Bilbao \cite[p.373]{bil98}).

Now we present the axioms for Shapley value.

Axiom FK1: (Linearity). For all $c\in\mathbb{R}$ and $v,w\in G^{(N,\preceq )}$, we have $\boldsymbol{\phi}(cv)=c\boldsymbol{\phi}(v)$ and $\boldsymbol{\phi}(v+w)=\boldsymbol{\phi}(v)+\boldsymbol{\phi}(w)$;
Axiom FK2: (Carrier). If $T$ is a carrier of $v\in G^{(N,\preceq )}$, then $\sum_{i\in T}\phi_{i}(v)=v(T)$;
Axiom FK3: (Hierarchical Strength). For any $S\in {\cal C}$ and $i,j\in S$, we have $h_{S}(i)\cdot\boldsymbol{\phi}_{j}(\zeta_{S})=h_{S}(j)\cdot\boldsymbol{\phi}_{i}(\zeta_{S})$.

In view of Axiom FK1, we may always restrict the discussion of $\boldsymbol{\phi}$ to its effect on any given basis of the vector space $G^{(N,\preceq )}$. Let us refer to Propositions \ref{fai92l1} and \ref{fai92l2} for basis of $G^{(N,\preceq )}$. It is straightforward to verify that Axiom FK2 implies $\phi_{i}(v)=0$ for all players $i$ not belonging to a given carrier $T$. We have two reasons to present the formulation of Axiom FK3. Firstly, it respects the fact that, in the precedence structure $P$, a player $k$ in some coalition $S$ has no individual power to let the coalition $S$ happen unless $k$ is a maximal element in $S$ (see Proposition \ref{fai92l4}). Secondly, Axiom FK3 as stated here naturally arises when we insist that the Shapley value reflect the expected marginal contribution of an individual player to the game (we shall see this point later). It might be interesting to clarify the role of Axiom FK3 in strengthening the usual symmetry axiom. In this case, a {\bf symmetry} $\sigma$ of $P$ must preserve the structure of $P$, i.e., it must be an automorphism of the ordered set. So we require $\sigma$ to have the properties:

$\sigma :N\rightarrow N$ is a bijection;
$x\preceq y$ if and only if $\sigma (x)\leq\sigma (y)$ for all $x,y\in N$.

Because $\sigma (S)\in {\cal C}$ whenever $S\in {\cal C}$, we may consider the following axiom

Axiom FK3′: (Symmetry). For each symmetry $\sigma$, $v\in G^{(N,\preceq )}$ and $i\in N$, we have $\phi_{i}(v)=\phi_{\sigma (i)}(\sigma v)$ (Faigle and Kern \cite[p.254-255]{fai92}).

Proposition. (Faigle and Kern \cite[p.255]{fai92}). If Axioms FK1, FK2 and FK3 hold true, the Axiom FK3′ also holds true. $\sharp$

We can show that if $\boldsymbol{\phi}$ exists, then we have
\begin{equation}{\label{fai92eq1}}\tag{20}
\phi_{i}(\zeta_{T})=\left\{\begin{array}{ll}
\frac{h_{T}(i)}{\sum_{j\in T}h_{T}(j)} & \mbox{if $i\in T$}\\
0 & \mbox{if $i\in N\setminus T$}.
\end{array}\right .
\end{equation}
By linearity in Axiom FK1, we can extend (\ref{fai92eq1}) to all of $G^{(N,\preceq )}$ uniquely via
\begin{equation}{\label{fai92eq2}}\tag{21}
\phi_{i}(v)=\sum_{T\in {\cal C}}c_{T}\phi_{i}(\zeta_{T})
\end{equation}
if $v=\sum_{T}c_{T}\zeta_{T}$ is the unique representation of $v$ in terms of simple games (Faigle and Kern \cite[p.256]{fai92}).

\begin{equation}{\label{fai92t1}}\tag{22}\mbox{}\end{equation}

Theorem \ref{fai92t1}. (Faigle and Kern \cite[p.256]{fai92}). There is a unique function $\boldsymbol{\phi}:G^{(N,\preceq )}\rightarrow\mathbb{R}$ satisfying Axioms FK1, FK2 and FK3. Moreover, $\boldsymbol{\phi}$ is given by (\ref{fai92eq2}). $\sharp$

We remark that the uniqueness statement in Theorem \ref{fai92t1} may not be obtained if Axiom FK3 is replaced by the weaker axiom FK3′. Indeed, we define
\begin{equation}{\label{fai92eq3}}\tag{23}
\phi_{i}^{\prime}(\zeta_{T})=\left\{\begin{array}{ll}
1/|T| & \mbox{if $i\in T$}\\ 0 & \mbox{if $i\in N\setminus T$}.
\end{array}\right .
\end{equation}
and extend (\ref{fai92eq3}) by linearity to a function $\boldsymbol{\phi}^{\prime}:G^{(N,\preceq )}\rightarrow\mathbb{R}$. It is readily seen that $\boldsymbol{\phi}^{\prime}$ satisfies Axioms FK1, FK2 and FK3′ (Faigle and Kern \cite[p.256-257]{fai92}).

Proposition. (Faigle and Kern \cite[p.257]{fai92}). $\boldsymbol{\phi}^{\prime}=\boldsymbol{\phi}$ if and only if $P$ is trivially ordered. $\sharp$

We shall now derive an interpretation of the number $\phi_{i}(v)$ as the expected marginal contribution of the player $i$ to the game $v\in G^{(N,\preceq )}$. Consider an arbitrary feasible ranking $\pi :N\rightarrow\{1,2,\cdots ,|N|\}$. It is straightforward to check that, for all $k\in N$, the set $T(\pi ,k)=\{i\in N:\pi (i)\leq\pi (k)\}$ is a member of the collection ${\cal C}$ of coalitions relative to the precedence structure $P$. Assuming all rankings $\pi\in \Pi (N)$ to be equally likely, the expected marginal contribution $\mathbb{E}_{k}(v)$ of the player $k\in N$ to the game $v\in G^{(N,\preceq )}$ is therefore given by
\begin{equation}{\label{fai92eq4}}\tag{24}
\mathbb{E}_{k}(v)=\frac{1}{|\Pi (N)|}\sum_{\pi\in \Pi (N)}\left [v(T(\pi ,k))-v(T(\pi ,k)\setminus\{k\})\right ].
\end{equation}
We see that $\mathbb{E}_{k}(v)$ is the expected contribution of $k$ to the already existing coalition if the players arrive according to some random ranking (Faigle and Kern \cite[p.257]{fai92}).

The expected marginal contribution give rise to the marginal expectation function ${\bf E}:G^{(N,\preceq )}\rightarrow\mathbb{R}^{N}$ via ${\bf E}(v)=(\mathbb{E}_{k}(v))_{k\in N}$. Note that, for each coalition $T\in {\cal C}$
containing the player $k$ as a maximal element, there are $|{\cal R}(T\setminus\{k\})|\cdot|{\cal R}(N\setminus T)|$ rankings $\pi\in \Pi (N)$ with the property $T=T(\pi ,k)$ because any ranking $\pi_{1}\in {\cal R}(T\setminus\{k\})$ and ranking $\pi_{2}\in{\cal R}(N\setminus T)$ may be concatenated to such a ranking $\pi =\pi_{1}k\pi_{2}$. Hence (\ref{fai92eq4}) can be rewritten as follows:
\begin{equation}{\label{fai92eq10}}\tag{25}
\mathbb{E}_{k}(v)=\frac{1}{|\Pi (N)|}\sum_{T\in {\cal C},k\in T^{+}}
|{\cal R}(T\setminus\{k\})|\cdot|{\cal R}(N\setminus T)|\left [v(T)-v(T\setminus\{k\})\right ],
\end{equation}
where $k\in T^{+}$ indicates that $k$ is maximal in $T$ and $|{\cal R}(\emptyset )|$ is understood to equal $1$ (Faigle and Kern \cite[p.257]{fai92}).

Theorem. (Faigle and Kern \cite[p.258]{fai92}). ${\bf E}=\boldsymbol{\phi}$. $\sharp$

The interpretation of the Shapley value as the expected marginal contribution allows us to gain more insight into the nature of $\boldsymbol{\phi}$ on particular types of games.

Example. (Faigle and Kern \cite[p.258]{fai92}). We say that the cooperative game $v\in G^{(N,\preceq )}$ is additive if, for all $S,T\in {\cal C}$, $v(S)+v(T)=v(S\cap T)+v(S\cup T)$. It is easy to see that, for the additive game $v$, there is a unique function $latex \omega :N
\rightarrow\mathbb{R}$ such that, for all $S\in {\cal C}$, we have $v(S)=\sum_{i\in S}w(i)$. So $w(i)$ is the marginal contribution of player $i\in N$ in any ranking and, therefore, it is the Shapley value of $i$. $\sharp$

Example. (Faigle and Kern \cite[p.259]{fai92}) The player $k\in N$ is a {\bf dummay player} in the game $v\in G^{(N,\preceq )}$ if,
for every coalition $S\in {\cal C}$ such that $S\cup\{k\}$ is also a feasible coalition, $v(S\cup\{k\})=v(S)$. The marginal contribution of a dummy player is thus zero, and hence, so is its Shapley value. $\sharp$

Games on Convex Geometries.

The games on convex geometry is presented in Definition \ref{bil98d1}. Here we are going to discuss the Shapley value on convex geometry. Let us recall that $CGG^{\cal L}$ denotes the set of all games on convex geometry.

Definition. (Bilbao \cite[p.371]{bil98}). The player $i\in N$ is a dummy in the game $v\in CGG^{\cal L}$ if, for every convex set $S\in {\cal L}$ such that $i\in\mbox{ext}(S)$, we have
\[v(S)-v(S\setminus\{i\})=\left\{\begin{array}{ll}
v(i) & \mbox{if $\{i\}\in {\cal L}$}\\ 0 & \mbox{otherwise}
\end{array}\right .\]

Let us remark that a different definition has been suggested by Faigle and Kern \cite{fai92}. We need some properties of the dummy players in the games which are defined in (\ref{ga12}).

Proposition. (Bilbao \cite[p.371]{bil98}). Let ${\cal L}$ be a convex geometry and let $S\in {\cal L}$ be a convex set.
Then, we have the following properties.

(i) If $i\not\in\mbox{ext}(S)$ then $i$ is a dummy player in the upper game $\zeta_{S}$.

(ii) If $i\in S\setminus\mbox{ext}(S)$ then $i$ is a dummy player in the identity game $\delta_{S}$. $\sharp$

Let $\boldsymbol{\phi}$ be a map $\boldsymbol{\phi}:CGG^{\cal L}\rightarrow\mathbb{R}^{N}$. Now we present the axioms for Shapley value (Bilbao \cite[p.370]{bil98}).

Axiom B1: (Linearity). For all $\alpha ,\beta\in\mathbb{R}$ and $v,w\in CGG^{\cal L}$, we have $\phi_{i}(\alpha v+\beta w)=\alpha\phi_{i}(v)+\beta\phi_{i}(w)$ for every $i\in N$;
Axiom B2: (Dummy). If the player $i\in N$ is a dummy in $v\in CGG^{\cal L}$, then
\[\phi_{i}(v)=\left\{\begin{array}{ll}
v(i) & \mbox{if $\{i\}\in {\cal L}$}\\ 0 & \mbox{otherwise};
\end{array}\right .\]
Axiom B3: (Efficiency). If $N$ is the set of all players of $v\in CGG^{\cal L}$, then $\sum_{i\in N}\phi_{i}(v)=v(N)$.

\begin{equation}{\label{bil98t1}}\tag{26}\mbox{}\end{equation}

Proposition \ref{bil98t1}. (Bilbao \cite[p.370]{bil98}). Let $\phi_{i}:CGG^{\cal L}\rightarrow\mathbb{R}$ be a value for $i$ which satisfies Axiom B1. Then there exists an unique set of coefficients $\{a_{S}^{i}:\emptyset\neq S\in {\cal L}\}$ such that
\[\phi_{i}(v)=\sum_{S\in {\cal L}}a_{S}^{i}v(S)\]
for all $v\in CGG^{\cal L}$. $\sharp$

\begin{equation}{\label{bil98t2}}\tag{27}\mbox{}\end{equation}

Proposition \ref{bil98t2}. (Bilbao \cite[p.371]{bil98}). Let $\phi_{i}:CGG^{\cal L}\rightarrow\mathbb{R}$ be a value for $i$ defined by
\[\phi_{i}(v)=\sum_{S\in {\cal L}}a_{S}^{i}v(S)\]
which satisfies Axiom B2. Then, for every game $v$, we have
\[\phi_{i}(v)=\sum_{\{S\in {\cal L}:i\in ext(S)\}}a_{S}^{i}\left [v(S)-v(S\setminus\{i\})\right ].\]
Moreover, if $\{i\}\in {\cal L}$, then
\[\sum_{\{S\in {\cal L}:i\in ext(S)\}}a_{S}^{i}=1. \sharp\]

We consider a convex geometry with $\{i\}\not\in {\cal L}$ for some $i\in N$. In this case, we note that
\[\sum_{\{S\in {\cal L}:i\in ext(S)\}}a_{S}^{i}=\sum_{\{S\in {\cal L}:i\in S\}}a_{S}^{i}=\phi_{i}(\zeta_{cl\{i\}}),\]
where the upper game on the closure of $\{i\}$ satisfies
\[\zeta_{cl\{i\}}(T)=\left\{\begin{array}{ll}
1 & \mbox{if $\mbox{cl}\{i\}\subseteq T$}\\ 0 & \mbox{otherwise}
\end{array}\right .=\left\{\begin{array}{ll}
1 & \mbox{if $i\in T$}\\ 0 & \mbox{otherwise}\end{array}\right .\]
From Propositions\ref{bilp98t1} and \ref{bil98t2}, we obtain the following result (Bilbao \cite[p.372]{bil98}).

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

Proposition \ref{bil98t3}. (Bilbao \cite[p.372]{bil98}). Let $\phi_{i}:CGG^{\cal L}\rightarrow\mathbb{R}$ be a value for $i$ which satisfies Axioms B1 and B2. Then, for every game $v$, there exists an unique set of coefficients $\{a_{S}^{i}:\S\in {\cal L},i\in\mbox{ext}(S)\}$ such that
\[\phi_{i}(v)=\sum_{\{S\in {\cal L}:i\in ext(S)\}}a_{S}^{i}\left [v(S)-v(S\setminus\{i\})\right ].\]
Moreover, if $\phi_{i}(\zeta_{cl\{i\}})=1$, then
\[\sum_{\{S\in {\cal L}:i\in ext(S)\}}a_{S}^{i}=1. \sharp\]

Let us remark that, for convex geometry which satisfy $\{i\}\in {\cal L}$ for all $i\in N$, the condition $\phi_{i}(\zeta_{cl\{i\}})=1$ is not necessary, since it follows from Axiom B2 (Bilbao \cite[p.372]{bil98}).

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

Proposition \ref{bil98t4}. (Bilbao \cite[p.372]{bil98}). Let $\boldsymbol{\phi}:CGG^{\cal L}\rightarrow\mathbb{R}^{N}$ be a value
defined for all game $v$ and for all $i\in N$ by
\[\phi_{i}(v)=\sum_{\{S\in {\cal L}:i\in ext(S)\}}a_{S}^{i}\left [v(S)-v(S\setminus\{i\})\right ].\]
Then the value $\boldsymbol{\phi}$ satisfies Axiom B3 if and only if
\[\sum_{i\in ext(N)}a_{N}^{i}=1\mbox{ and }\sum_{i\in ext(S)}a_{S}^{i}=
\sum_{\{j\not\in S:S\cup\{j\}\in {\cal L}\}}a_{S\cup\{j\}}^{j}\]
for all $S\in {\cal L}$ with $\emptyset\neq S\neq N$. $\sharp$

The conventional characterization of the Shapley value is as the only value that satisfies the carrier, symmetry and additivity on the class of all super-additive games. For the class of all games, Weber \cite{web88} considered linearity, dummy, symmetry and efficiency axioms, and proved the uniqueness of the Shapley value (Bilbao \cite[p.372-373]{bil98}).

We denote by $c([T,S])$ the number of maximal chains from $T$ to $S$, where $T\subset S$ and $c(S)\equiv c([\emptyset ,S])$ is the number of maximal chains from $\emptyset$ to $S\neq\emptyset$. Furthermore, we see that $c([S,S])=1$ for all $S\in {\cal L}$ (Bilbao \cite[p.373]{bil98}).

Definition. (Bilbao \cite[p.373]{bil98}). Let $v\in G^{|cal L}$ be a game on a convex geometry ${\cal L}$. The Shapley value for the player $i\in N$ is given by
\[\phi_{i}(v)\equiv\sum_{\{S\in {\cal L}:i\in ext(S)\}}
\frac{c(S\setminus\{i\})\cdot c([S,N])}{c(N)}\cdot\left [v(S)-v(S\setminus\{i\})\right ]. \sharp\]

Now we introduce a new axiom, in which the value of the player depends of the position on lattice structure of the convex geometry.

Axiom B4: (Chain). For any nonempty $S\in {\cal L}$ and $i,j\in\mbox{ext}(S)$, we have $c(S\setminus\{i\})\phi_{j}(\delta_{S})= c(S\setminus\{j\})\phi_{i}(\delta_{S})$.

We need this axiom since in the model of convex geometries the hypothesis of symmetry for the players is not applied. To interpret the chain axiom, we assume that ${\cal L}=2^{N}$. Then, the coefficient of the values in Proposition \ref{bil98t2} satisfy $a_{S}^{i}=a_{S}^{j}$ for every pair $i,j\in S$ and for all $S\subseteq N$. The same property is consequence of the conventional symmetry axiom (Bilbao \cite[p.373]{bil98}).

Theorem. (Bilbao \cite[p.373]{bil98}). The Shapley value is the unique function $\boldsymbol{\phi}:CGG^{\cal L}\rightarrow\mathbb{R}^{N}$ that satisfies Axioms B1, B2, B3 and B4.

Proof. The Shapley value satisfies the axioms. Let $\boldsymbol{\phi}$ be a function that satisfies Axioms B1, B2, B3 and B4. From Propositions \ref{bil98t3} and \ref{bil98t4}, it suffices to show that
\[a_{S}^{i}=\frac{c(S\setminus\{i\})\cdot c([S,N])}{c(N)}\]
for all $S\in {\cal L}$ and $i\in\mbox{ext}(S)$. $\blacksquare$

Note that if ${\cal L}=2^{N}$, then $\mbox{ext}(S)=S$ for all coalition $S\subseteq N$, and
\[\frac{c(S\setminus\{i\})\cdot c([S,N])}{c(N)}=\frac{(|S|-1)!(|N|-|S|)!}{|N|!}\]
(Bilbao \cite[p.374]{bil98}).

Next we consider the Shapley value and Banzhaf value of a game $(N,v)$ with a partion convex geometry defined in Definition \ref{bil98ad100}. Let first recall that the Banzhaf value for player $i$ in a game $(N,v)$ is given by
\[\beta_{i}(N,v)=\sum_{\{S\subseteq N:i\in S}\frac{1}{2^{n-1}}\left [v(S)-v(S\setminus\{i\})\right ]\]
for $i\in N$.

Let $(N,{\cal L})$ be a partition convex geometry and let $(N,v)$ be a game. The concept of ${\cal L}$-restricted was given in Definition \ref{bil98ad2}. The Shapley value for the player $i$ in the ${\cal L}$-restricted game $v^{\cal L}$ is given by $\phi_{i}(N,v^{\cal L})$ for all $i\in N$, where $\phi_{i}(N,v)$ denotes the conventional Shapley value of game $(N,v)$. The Banzhaf value for the player $i$ in the game $v^{\cal L}$ is given by $\beta_{i}(N,v^{\cal L})$ for all $i\in N$. In terms of dividends, we have
\[\phi_{i}(N,v^{\cal L})=\sum_{\{S\subseteq N:i\in S\}}\frac{\Delta_{S}
(v^{\cal L})}{|S|}\mbox{ and }\beta_{i}(N,v^{\cal L})=\sum_{\{S\subseteq N:
i\in S\}}\frac{\Delta_{S}(v^{\cal L})}{2^{|S\setminus\{i\}|}}.\]
We write $T^{+}=\{i\in N:T\cup\{i\}\in {\cal L}\}$ (Bilbao \cite[p.139-140]{bil98a}).

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

Theorem \ref{bil98at3}. (Bilbao \cite[p.140]{bil98a}). Let $(N,{\cal L})$ be a partition convex geometry and let $(N,v)$ be a game.
Suppose that we consider the following collections.
\begin{align*}
{\cal L}_{i} & =\{T\in {\cal L}:i\in T\}\\
{\cal L}_{i}^{+} & = & \{T\in {\cal L}:i\in ext(T),(T\setminus\{i\})^{+}=T^{+}\}\\
{\cal L}_{i}^{*} & =\{T\in {\cal L}:i\not T,T\cup\{i\}\in {\cal L},T^{+}\neq (T\cup\{i\})^{+}\}
\end{align*}
for all $i\in N$. Then the Shapley value for the player $i$ in the restricted game $v^{\cal L}$ satisfies
\begin{align*}
\phi_{i}(N,v^{\cal L}) & =\sum_{T\in {\cal L}_{i}^{+}}\frac{(|T|-1)!
(|T^{+}|-|T|)!}{|T^{+}|!}\left [v(T)-v(T\setminus\{i\})\right ]+
\sum_{T\in {\cal L}_{i}\setminus {\cal L}_{i}^{+}}\frac{(|T|-1)!(|T^{+}|-|T|)!}{|T^{+}|!}v(T)\\
& -\sum_{T\in {\cal L}_{i}^{*}}
\frac{|T|!(|T^{+}|-|T|-1)!}{|T^{+}|!}v(T)
\end{align*}
and the Banzhaf value for the player $i$ in the restricted game $v^{\cal L}$ satisfies
\[\beta_{i}(N,v^{\cal L})=\sum_{T\in {\cal L}_{i}^{+}}\frac{1}{2^{|T^{+}|-1}}
\left [v(T)-v(T\setminus\{i\})\right ]+\sum_{T\in {\cal L}_{i}\setminus
{\cal L}_{i}^{+}}\frac{1}{2^{|T^{+}|-1}}v(T)-\sum_{T\in {\cal L}_{i}^{*}}\frac{1}{2^{|T^{+}|-1}}v(T). \sharp\]

Notice that if ${\cal L}=2^{N}$, then $\mbox{ext}(T)=T$ and $T^{+}=N$ for every $T\in {\cal L}$. Thus, the formulas in Theorem \ref{bil98at3} are equals to the conventional Shapley value and Banzhaf value (Bilbao \cite[p.142]{bil98a}).

Theorem. (Bilbao \cite[p.143]{bil98a}). Let $(N,{\cal L})$ be a partition convex geometry and let $(N,v)$ be a game such that $v(i)=0$ for all $i\in N$. If $i\in\mbox{ext}(N)$, then the values for the player $i$ in $v^{\cal L}$ satisfy
\[\phi_{i}(N,v^{\cal L})=\sum_{T\in {\cal L}}\frac{(|T|-1)!(|T^{+}|-|T|)!}{|T^{+}|!}\left [v(T)-v(T\setminus\{i\})\right ]\]
and
\[\beta_{i}(N,v^{\cal L})=\sum_{T\in {\cal L}}\frac{1}{2^{|T^{+}|-1}}\left [v(T)-v(T\setminus\{i\})\right ]. \sharp\]

The explicit formula for the potential of $v^{\cal L}$ can be obtained below by referring to Definition \ref{bil98ad200} and Theorem \ref{bil98at200}.

Theorem. (Bilbao \cite[p.143]{bil98a}). Let $(N,{\cal L})$ be a partition convex geometry and let $(N,v)$ be a game. Then the potential of $v^{\cal L}$ satisfies
\[P(N,v^{\cal L})=\sum_{T\in {\cal L}}\frac{(|T|-1)!(|T^{+}|-|T|)!}{|T^{+}|!}v(T). \sharp\]

Games with Coalition Structures.

Games with Permission Structures.

Games under Preference Cosntraints.

Games on Convex Geometries.

Hsien-Chung Wu

發佈留言取消回覆

Games with Coalition Structures.

Games with Permission Structures.

Games under Preference Cosntraints.

Games on Convex Geometries.

Hsien-Chung Wu

相關文章

Set-Valued Nonlinear Analogues of the Shapley Value

The Shapley Value as a Von Neumann-Morgenstern Utility

Shapley Value for Multi-choice Cooperative Games

發佈留言取消回覆