Set-Valued Nonlinear Analogues Of The Shapley Value

James Edward Buttersworth (1817-1894) was an English painter.

The notation $N^{v}$ will be used to denote the set of players in the game with characteristic function $v$.

Definition. (Pechersky and Sobolev \cite[p.58]{pec95}). A solution is a set-valued map $F:v\rightarrow F(v)\subset \mathbb{R}^{N^{v}}$ with $F(v)\neq\emptyset$ for every game $v$. The set $F(v)$ is called the solution of the game $v$. $\sharp$

Definition. (Pechersky and Sobolev \cite[p.58]{pec95}). A mapping $\tau :N^{v_{1}}\rightarrow N^{v_{2}}$ is called an isomorphism of games $v_{1}$ and $v_{2}$ if $\tau$ is one-to-one mapping and $v_{2}(\tau (S))=v_{1}(S)$ for every $S\subseteq N^{v_{1}}$. The games $v_{1}$ and $v_{2}$ are called isomorphic. $\sharp$

If $\tau$ is an isomorphism, then $\tau^{*}:\mathbb{R}^{I^{v_{1}}}\rightarrow\mathbb{R}^{I^{v_{2}}}$ denotes the mapping defined by the formula $\tau^{*}({\bf x})=(x_{\tau (i)})_{i\in I^{v_{1}}}$ for every ${\bf x}\in\mathbb{R}^{I^{v_{1}}}$ (Pechersky and Sobolev \cite[p.58]{pec95}).

For any real-valued function $\eta$ and evert game $v$, let $\eta v$ be the game defined by $(\eta v)(N)=(\eta v)(\emptyset )=0$ and $(\eta v)(S)=\eta (v(S))$ for $S\neq N,\emptyset$. The $\eta$-sum $v_{1}\oplus_{\eta}v_{2}$ of games $v_{1}$ and $v_{2}$ is the set of games $v_{3}$ such that $v_{3}(N)=0$ and $\eta v_{3}=\frac{1}{2}(\eta v_{1}+\eta v_{2})$. The $\eta$-sum of the games $v_{1}$ and $v_{2}$ always exists for any continuous functions $\eta$ (Pechersky and Sobolev \cite[p.58]{pec95}).

It is convenient to consider sometimes vector ${\bf x}\in\mathbb{R}^{N}$ as a game defined by formula ${\bf x}(S)=\sum_{i\in S}x_{i}$ for all $S\subseteq N$. We denote by $Pr_{\mathbb{R}^{S}}(A)$ the projection of the set $A$ on the subspace $\mathbb{R}^{S}$ for $S\subseteq N$. $A+B=\{{\bf x}+{\bf y}:{\bf x}\in A,{\bf y}\in B\}$. The Shapley value $\boldsymbol{\phi}$ is given by
\[\phi_{i}(v)=\sum_{\{S:i\not\in S\}}\frac{s!(n-s-1)!}{n!}\cdot(v(S\cup\{i\})-v(S)),\]
where $s=|S|$ and $n=|N^{v}|$. (Pechersky and Sobolev \cite[p.59]{pec95}).

We now formulate the axioms which we claim a solution $F$ to satisfy.

Axiom PS1: (Anonymity). If ${\bf x}\in F(v_{1})$ and $\tau$ is an isomorphism of the games $v_{1}$ and $v_{2}$, then $\tau^{*}({\bf x})\in F(v_{2})$.
Axiom PS2: (Symmetry). If $v(S)=f(|S|)$ and $v(N)=0$, then ${\bf 0}\in F(v)$.
Axiom PS3: (Dummy). Let $v_{1}$ and $v_{2}$ be the games such that $N^{v_{1}}=N$, $N^{v_{2}}=N\cup\{i_{0}\}$ with $i_{0}\not\in N$ and $v_{1}(S)=v_{2}(S)=v_{2}(S\cup\{i_{0}\})$ for all $S\subseteq N$, then $x_{i_{0}}=0$ for every ${\bf x}\in F(v)$ and $Pr_{\mathbb{R}^{N}}(F(v_{2}))=F(v_{1})$.
Axiom PS4: (Efficiency). If ${\bf x}\in F(v)$, then ${\bf x}(I)=v(I)$.
Axiom PS5: (Weak covariance). Let ${\bf a}\in\mathbb{R}^{N}$, and two games $v_{1}$ and $v_{2}$ are connected by equality $v_{2}=v_{1}+{\bf a}$. Then $F(v_{2})=F(v_{1})+{\bf a}$.
Axiom PS6($\eta$): ($\eta$-closedness of the null games set}. If ${\bf 0}\in F(v_{1})\cap F(v_{2})$, $v_{3}\in v_{1}\oplus_{\eta}v_{2}$, then ${\bf 0}\in F(v_{3})$.

The Axiom (A6)($\eta$) depends on the function $\eta$. Therefore, we obtain the whole family of axiom systems, and every system possibly defines some solution $F$ (Pechersky and Sobolev \cite[p.59-60]{pec95}).

Proposition. (Pechersky and Sobolev \cite[p.60]{pec95}). Let $v_{k}$, $k=1,\cdots ,m$ be the games with the same set of players. Suppose that
\[{\bf 0}\in\bigcap_{k=1}^{m}F(v_{k})\mbox{ and }\eta v=\sum_{k=1}^{m}\lambda_{k}\cdot\eta v_{k},\]
where $\lambda_{k}$ are the binary-rational numbers, i.e., the numbers of the form $p/2^{q}$, such that $\lambda_{k}>0$ and $\sum_{k=1}^{m}\lambda_{k} =1$. Then ${\bf 0}\in F(v)$. $\sharp$

Proposition. (Pechersky and Sobolev \cite[p.60]{pec95}). If ${\bf 0}\in F(v_{1})$, $v_{2}(N)=0$, $\eta v_{1}=\eta v_{2}$, then ${\bf 0}\in F(v_{2})$. $\sharp$

Proposition. (Pechersky and Sobolev \cite[p.60]{pec95}). Let $v$ be a game such that $v(N)=0$ and $v(S\cup\{i_{0}\})=v(S)=f(|S|)$ for some $i_{0}\in N$ and every $S$ with $i_{0}\not\in S$. Then ${\bf 0}\in F(v)$. $\sharp$

Proposition. (Pechersky and Sobolev \cite[p.60]{pec95}). If the function $\eta$ is linear and $F$ satisfies the Axioms PS1–PS6$(\eta )$, then $F$ is single-valued for any game $v$ and therefore $F\equiv\boldsymbol{\phi}$, where $\boldsymbol{\phi}$ is the Shapley value. $\sharp$

Let the number $q_{i}(v)$ be defined for every game $v$ by
\[q_{i}(v)=\sum_{\{S:i\in S\neq N^{v}\}}(s-1)!(n-s-1)!\eta (v(S)),\]
where $s=|S|$ and $n=|N^{v}|$.

\begin{equation}{\label{pec95t1}}\tag{1}\mbox{}\end{equation}

Theorem \ref{pec95t1}. {(Pechersky and Sobolev \cite[p.62]{pec95}). Let $\eta$ be a continuous nondecreasing function and
\[m=\inf_{t\in\mathbb{R}}\eta (t)<\eta (0)<\sup_{t\in\mathbb{R}}\eta (t)=M\]
(the numbers $m$ and $M$ can equal $\infty$). If a solution $F$ satisfies Axioms PS1–PS6$(\eta )$ and ${\bf 0}\in F(v)$, then
\begin{equation}{\label{pec95eq1}}\tag{2}
q_{i}(v)=q_{j}(v)
\end{equation}
for all $i,j\in N$. $\sharp$

The Axiom PS4 is not used in the proof of theorem. It follows, from (\ref{pec95eq1}) that if ${\bf 0}\in F(v)$ and $\eta$ satisfies the
conditions of Theorem \ref{pec95t1}, then $\boldsymbol{\phi}(\eta v)={\bf 0}$ (Pechersky and Sobolev \cite[p.65]{pec95}).

In the sequel, we shall define a family of solutions satisfying the proposed system of axioms. Let $v$ be a game and ${\bf x}\in\mathbb{R}^{N}$. Let us take a convex function $\zeta :\mathbb{R}\rightarrow\mathbb{R}$ and consider the functional
\[Q^{\zeta}({\bf x},v)=\sum_{\{S:S\neq N,\emptyset\}} (s-1)!(n-s-1)!\zeta (v(S)-{\bf x}(S)).\]
Let $Y(v)$ be the set of preimputations in the game $v$ given by
\[Y(v)=\{{\bf x}\in\mathbb{R}^{N}:{\bf x}(N)=v(N)\}.\]
Define now the map $F^{\zeta}$ as follows
\[F^{\zeta}(v)=\arg\min\left\{Q^{\zeta}({\bf x},v):{\bf x}\in Y(v)\right\}.\]
(Pechersky and Sobolev \cite[p.65]{pec95}).

Proposition. (Pechersky and Sobolev \cite[p.65]{pec95}). The set $F^{\zeta}(v)$ is nonempty and convex. If $\zeta$ is not affine, then
the set $F^{\zeta}(v)$ is compact. $\sharp$

It is clear that the map $F^{\zeta}$ satisfies Axioms PS1, PS2, PS4, and PS5 (Pechersky and Sobolev \cite[p.66]{pec95}).

Proposition. (Pechersky and Sobolev \cite[p.66]{pec95}). If $v_{1}(S)=v_{2}(N\setminus S)-v_{2}(N)$ for all $S\subseteq N$, then $F^{\zeta}(v_{1})=-F^{\zeta}(v_{2})$. $\sharp$

Proposition. (Pechersky and Sobolev \cite[p.66]{pec95}). If ${\bf x}\in F^{\zeta}(v)$, then
\begin{equation}{\label{pec95eq4}}\tag{3}
\sum_{\{S:i,j\not\in S\}}s!(n-s-2)!\left (\zeta^{\prime}_{+}(V(S\cup\{i\})-{\bf x}(S\cup\{i\}))-\zeta^{\prime}_{-}(v(S\cup\{j\})-{\bf x}(S\cup\{j\}))\right )\geq 0
\end{equation}
for all $i,j\in N$. $\sharp$

If $\zeta$ is continuously differentiable, then the inequality (\ref{pec95eq4}) transforms to the equality
\[\sum_{\{S:i,j\not\in S\}}s!(n-s-2)!\left (\zeta^{\prime}(V(S\cup\{i\})-
{\bf x}(S\cup\{i\}))-\zeta^{\prime}(v(S\cup\{j\})-{\bf x}(S\cup\{j\}))\right )=0.\]
This quality and inclusion ${\bf x}\in Y(v)$ are sufficient conditions for ${\bf x}\in F^{\zeta}(v)$ (Pechersky and Sobolev \cite[p.67]{pec95}).

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

Proposition \ref{pec95p8}. (Pechersky and Sobolev \cite[p.67]{pec95}). If $\zeta$ is continuously differentiable, then $F^{\zeta}$ satisfies Axiom PS6$(\zeta^{\prime})$. $\sharp$

Let $\mbox{epi }\zeta$ denote the epigraph of function $\Psi$, that is, $\mbox{epi }\zeta =\{(t,y)\in\mathbb{R}^{2}:y\geq\zeta (t)\}$.

Proposition. (Pechersky and Sobolev \cite[p.67]{pec95}). The map $F^{\zeta}$ satisfies Axiom PS3 if and only if the point $(0,\zeta (0))$ is extremal in $\mbox{epi }\zeta$. $\sharp$

Proposition. (Pechersky and Sobolev \cite[p.69]{pec95}). Let $\zeta$ be a convex, continuously differentiable function and ${\bf x},{\bf y}\in F^{\zeta}(v)$. Then for every $S$, $\zeta^{\prime}(v(S)-{\bf x}(S))=\zeta^{\prime}(v(S)-y(S))$. $\sharp$

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

Theorem \ref{pec95t2}. {\em (Pechersky and Sobolev \cite[p.69]{pec95}). Let $\eta$ be a continuous non-decreasing function and the point $0$ be its growth point $($i.e. in every neighborhood of $0$ there is a point $t$ such that $\eta (t)\neq\eta (0))$. Let $\zeta$ be some primitive of $\eta$ $($i.e. $\zeta^{\prime}=\eta )$. Then the map $F^{\zeta}$ satisfies Axioms PS1–PS6$(\phi )$. If, moreover, the function $\eta$ satisfies the inequality $\inf_{t}\eta (t)<\eta (0)<\sup_{t}\eta (t)$, then $F^{\zeta}$ is the unique map satisfying the system of axioms. $\sharp$

If the function $\eta$ is strictly increasing, then $F^{\zeta}(v)$ is a singleton (Pechersky and Sobolev \cite[p.70]{pec95}).

Example. (Pechersky and Sobolev \cite[p.70]{pec95}) Let $\epsilon\in\mathbb{R}$ and
\[\eta (t)=\left\{\begin{array}{ll}
0 & t\leq\epsilon\\ t-\epsilon & t>\epsilon\end{array}\right .\]
Consider the map $F^{\zeta}$, where $\zeta^{\prime}=\eta$. It is clear that if the $\epsilon$-core $C_{\epsilon}(v)$ of game $v$ is nonempty, then $F^{\zeta}(v)=C_{\epsilon}(v)$. On the other hand, it can be shown that if $v(N)$ is small enough with respect to other $v(S)$, then $F^{\zeta}(v)$ consist of the unique point which coincides with the Shapley value of the game $v$. By Theorem \ref{pec95t2} and Proposition \ref{pec95p8} $F^{\zeta}$ satisfies the proposed system of axioms only if $\epsilon\leq 0$. Moreover if $\epsilon <0$, then $F^{\zeta}$ is the unique map satisfying the system. $\sharp$

We now consider the following question: Is there a selector of the presented solution? This studies the possibility of constructing the mapping $f$ such that $f(v)\in F(v)$ with $|f(v)|=1$. Surely it would be interesting to find selectors satisfying the Axioms PS1-PS6($\phi$), but it is impossible since $F^{\zeta}$ is the unique map satisfying the axioms. Therefore we will claim selectors to satisfy the following analogues of PS6($\phi$).

Axiom PS6′($\phi$). There is such an opertaion $\oplus$ on the set of games, that $v_{1}\oplus v_{2}\in v_{1}\oplus_{\phi}v_{2}$ and $f(v_{1})=f(v_{2})={\bf 0}$ implies $f(v_{1}\oplus v_{2})={\bf 0}$.

Since $f$ is single-valued, the Axioms PS1-PS5 can be simplified. For example, PS2 follows in this case from PS1 and PS4 (Pechersky and Sobolev \cite[p.71]{pec95}).

\begin{equation}{\label{pec95t3}}\tag{6}\mbox{}\end{equation}

Theorem \ref{pec95t3}. (Pechersky and Sobolev \cite[p.71]{pec95}). Let $\eta$ be a continuous nondecreasing function on $\mathbb{R}$ for which ${\bf 0}$ is a growth point. Then the map $F^{\zeta}$, where $\zeta^{\prime}=\eta$, admits a selector satisfying Axioms PS1–PS6’$(\eta )$. $\sharp$

We now present the set of axioms defining the prekernel. This set of axioms is in some sense analogous to the axiom system PS1–PS6($\phi$). We replace only PS2 and PS6($\phi$) by the following axioms

Axiom PS2*. If $v(S\cup\{i\})=v(S\cup\{j\})$ for every $S$ with $i,j\not\in S$ and ${\bf x}\in F(v)$, then $x_{i}=x_{j}$.
Axiom PS6*. If ${\bf 0}\in F(v_{1})\cap F(v_{2})$ and $v_{3}(S)=\max\{v_{1}(S),v_{2}(S)\}$, then ${\bf 0}\in F(v_{3})$.

Let us introduce the following axiom

Axiom PS7. Let $a\in\mathbb{R}$, $v_{1}(N)=v_{2}(N)$ and $v_{1}(S)=v_{2}(S)+a$ for $S\neq N,\emptyset$. Then $F(v_{1})=F(v_{2})$.

The prekernel}$K(v)$ of the game $v$ is given by
\[K(v)=\left\{{\bf x}\in\mathbb{R}^{N}:\max_{\{S:i\in S,j\not\in S\}}(v(S)-{\bf x}(S))=\max_{\{S:j\in S,i\not\in S\}}(v(S)-{\bf x}(S))\mbox{ for }i,j\in N, {\bf x}(N)=v(N)\right\}.\]

Proposition. (Pechersky and Sobolev \cite[p.74]{pec95}). The map $K$ satisfies Axioms PS1, PS2*, PS3-PS5, PS6* and PS7. $\sharp$

Theorem. (Pechersky and Sobolev \cite[p.75]{pec95}). Let $F$ satisfies Axioms PS1, PS2*, PS3-PS5, PS6* and PS7. Then $F(v)\subseteq K(v)$ for any game $v$. $\sharp$

The above theorem shows that the map $K$ is the maximal solution satisfying the proposed system of axioms. Unfortunately, it is not unique. For example, the prenucleolus also satisfies this axiom’s system (Pechersky and Sobolev \cite[p.77]{pec95}).