Valor de Shapley

Em termos de sinergia

A partir da função característica ${\displaystyle v}$, é possível calcular a sinergia (dividendo de Harsanyi) proporcionada por cada grupo de jogadores. A sinergia é a única função ${\displaystyle w\colon 2^{N}\to \mathbb {R} }$ tal que

${\displaystyle v(S)=\sum _{R\subseteq S}w(R)}$

para qualquer subconjunto ${\displaystyle S\subseteq N}$ de jogadores. Em outras palavras, o "valor total" da coalizão ${\displaystyle S}$ resulta da soma das sinergias de cada subconjunto possível de ${\displaystyle S}$.

Dada uma função característica ${\displaystyle v}$, a função de sinergia ${\displaystyle w}$ é calculada por

${\displaystyle w(S)=\sum _{R\subseteq S}(-1)^{|S|-|R|}v(R)}$

mediante o princípio da inclusão-exclusão.

Os valores de Shapley são dados, em termos da função de sinergia, por

${\displaystyle \varphi _{i}(v)=\sum _{i\in S\subseteq N}{\frac {w(S)}{|S|}}}$

em que a soma abrange todos os subconjuntos ${\displaystyle S}$ de ${\displaystyle N}$ que incluem o jogador ${\displaystyle i}$.

Isso pode ser interpretado como

${\displaystyle \varphi _{i}(v)=\sum _{{\text{coalizões que incluem }}i}{\frac {\text{sinergia da coalizão}}{\text{número de membros da coalizão}}}}$

Em outras palavras, a sinergia de cada coalizão é dividida igualmente entre todos os seus membros.

Essa interpretação pode ser visualizada por meio de um diagrama de Venn. No primeiro diagrama de exemplo acima, cada região foi rotulada com o bônus de sinergia da coalizão correspondente. O valor total produzido por uma coalizão é a soma dos bônus de sinergia das subcoalizões que a compõem — no exemplo, a coalizão formada pelos jogadores identificados como "You" e "Emma" produziria um lucro de ${\displaystyle 30+20+40=90}$ dólares, em comparação com os seus lucros individuais de ${\displaystyle 30}$ e ${\displaystyle 20}$ dólares, respectivamente. As sinergias são então repartidas igualmente entre os membros da subcoalizão que gera cada sinergia, como mostra o segundo diagrama.

Exemplo empresarial

Considere-se a descrição simplificada de uma empresa. Um proprietário, o, fornece o capital indispensável, no sentido de que, sem ele, nenhum ganho pode ser obtido. Há m trabalhadores w₁,...,w_m, cada um dos quais contribui com uma quantia p para o lucro total. Seja

${\displaystyle N=\{o,w_{1},\ldots ,w_{m}\}.}$

A função de valor desse jogo de coalizão é

${\displaystyle v(S)={\begin{cases}(|S|-1)p&{\text{se }}o\in S\;,\\0&{\text{caso contrário}}\;.\\\end{cases}}}$

O cálculo do valor de Shapley para esse jogo de coalizão resulta num valor de ⁠mp/2⁠ para o proprietário e de ⁠p/2⁠ para cada um dos m trabalhadores.

Esse resultado pode ser compreendido do ponto de vista da sinergia. A função de sinergia ${\displaystyle w}$ é

${\displaystyle w(S)={\begin{cases}p,&{\text{se }}S=\{o,w_{i}\}\\0,&{\text{caso contrário}}\\\end{cases}}}$

de modo que as únicas coalizões que geram sinergia são as formadas, uma a uma, entre o proprietário e cada trabalhador individualmente.

Aplicando a fórmula acima do valor de Shapley em termos de ${\displaystyle w}$, obtém-se

${\displaystyle \varphi _{w_{i}}={\frac {w(\{o,w_{i}\})}{2}}={\frac {p}{2}}}$

e

${\displaystyle \varphi _{o}=\sum _{i=1}^{m}{\frac {w(\{o,w_{i}\})}{2}}={\frac {mp}{2}}}$

O resultado também pode ser compreendido do ponto de vista da média sobre todas as ordenações. Um dado trabalhador entra na coalizão depois do proprietário (contribuindo, portanto, com p) em metade das ordenações e, assim, tem uma contribuição média de ${\displaystyle {\frac {p}{2}}}$ ao entrar. Quando o proprietário entra, em média metade dos trabalhadores já está presente, de modo que a sua contribuição média ao entrar é ${\displaystyle {\frac {mp}{2}}}$.

Jogo das luvas

O jogo das luvas é um jogo de coalizão no qual os jogadores possuem luvas da mão esquerda e da mão direita, e o objetivo é formar pares. Seja

${\displaystyle N=\{1,2,3\},}$

em que os jogadores 1 e 2 possuem luvas da mão direita e o jogador 3 possui uma luva da mão esquerda.

A função de valor desse jogo de coalizão é

${\displaystyle v(S)={\begin{cases}1&{\text{se }}S\in \left\{\{1,3\},\{2,3\},\{1,2,3\}\right\};\\0&{\text{caso contrário}}.\\\end{cases}}}$

A fórmula para o cálculo do valor de Shapley é

${\displaystyle \varphi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right],}$

em que R é uma ordenação dos jogadores e ${\displaystyle P_{i}^{R}}$ é o conjunto dos jogadores de N que precedem i na ordenação R.

A tabela a seguir apresenta as contribuições marginais (CM) do jogador 1.

${\displaystyle {\begin{array}{|c|r|}{\text{Ordem }}R\,\!&CM_{1}\\\hline {1,2,3}&v(\{1\})-v(\varnothing )=0-0=0\\{1,3,2}&v(\{1\})-v(\varnothing )=0-0=0\\{2,1,3}&v(\{1,2\})-v(\{2\})=0-0=0\\{2,3,1}&v(\{1,2,3\})-v(\{2,3\})=1-1=0\\{3,1,2}&v(\{1,3\})-v(\{3\})=1-0=1\\{3,2,1}&v(\{1,3,2\})-v(\{3,2\})=1-1=0\end{array}}}$

Observa-se que

${\displaystyle \varphi _{1}(v)=\!\left({\frac {1}{6}}\right)(1)={\frac {1}{6}}.}$

Por um argumento de simetria, pode-se demonstrar que

${\displaystyle \varphi _{2}(v)=\varphi _{1}(v)={\frac {1}{6}}.}$

Em virtude do axioma da eficiência, a soma de todos os valores de Shapley é igual a 1, o que significa que

${\displaystyle \varphi _{3}(v)={\frac {4}{6}}={\frac {2}{3}}.}$

Eficiência

A soma dos valores de Shapley de todos os agentes é igual ao valor da grande coalizão, de modo que todo o ganho é distribuído entre os agentes:

${\displaystyle \sum _{i\in N}\varphi _{i}(v)=v(N)}$

Demonstração: ${\displaystyle \sum _{i\in N}\varphi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\sum _{i\in N}v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})}$ ${\displaystyle ={\frac {1}{|N|!}}\sum _{R}v(N)={\frac {1}{|N|!}}|N|!\cdot v(N)=v(N)}$

uma vez que ${\displaystyle \sum _{i\in N}v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})}$ é uma soma telescópica e existem ${\displaystyle |N|!}$ ordenações distintas ${\displaystyle R}$.

Simetria

Se ${\displaystyle i}$ e ${\displaystyle j}$ são dois agentes equivalentes, no sentido de que

${\displaystyle v(S\cup \{i\})=v(S\cup \{j\})}$

para todo subconjunto ${\displaystyle S}$ de ${\displaystyle N}$ que não contém nem ${\displaystyle i}$ nem ${\displaystyle j}$, então ${\displaystyle \varphi _{i}(v)=\varphi _{j}(v)}$.

Essa propriedade também é chamada de tratamento igual para iguais.

Linearidade

Se dois jogos de coalizão descritos pelas funções de ganho ${\displaystyle v}$ e ${\displaystyle w}$ forem combinados, os ganhos distribuídos devem corresponder aos ganhos derivados de ${\displaystyle v}$ somados aos ganhos derivados de ${\displaystyle w}$:

${\displaystyle \varphi _{i}(v+w)=\varphi _{i}(v)+\varphi _{i}(w)}$

para todo ${\displaystyle i}$ em ${\displaystyle N}$. Além disso, para qualquer número real ${\displaystyle a}$,

${\displaystyle \varphi _{i}(av)=a\varphi _{i}(v)}$

para todo ${\displaystyle i}$ em ${\displaystyle N}$.

Jogador nulo

O valor de Shapley ${\displaystyle \varphi _{i}(v)}$ de um jogador nulo ${\displaystyle i}$ num jogo ${\displaystyle v}$ é zero. Um jogador ${\displaystyle i}$ é nulo em ${\displaystyle v}$ se ${\displaystyle v(S\cup \{i\})=v(S)}$ para todas as coalizões ${\displaystyle S}$ que não contêm ${\displaystyle i}$.

Teste de autonomia

Se ${\displaystyle v}$ for uma função de conjunto subaditiva, isto é, se ${\displaystyle v(S\cup T)\leq v(S)+v(T)}$, então, para cada agente ${\displaystyle i}$: ${\displaystyle \varphi _{i}(v)\leq v(\{i\})}$.

Analogamente, se ${\displaystyle v}$ for uma função de conjunto superaditiva, isto é, se ${\displaystyle v(S\cup T)\geq v(S)+v(T)}$ para ${\displaystyle S\cap T=\emptyset }$, então, para cada agente ${\displaystyle i}$: ${\displaystyle \varphi _{i}(v)\geq v(\{i\})}$.

Assim, se a cooperação tiver sinergia positiva, todos os agentes ganham (em sentido fraco); se tiver sinergia negativa, todos os agentes perdem (em sentido fraco).^:147–156

Anonimato

Se ${\displaystyle i}$ e ${\displaystyle j}$ são dois agentes e ${\displaystyle w}$ é uma função de ganho idêntica a ${\displaystyle v}$, exceto pelo fato de os papéis de ${\displaystyle i}$ e ${\displaystyle j}$ terem sido trocados, então ${\displaystyle \varphi _{i}(v)=\varphi _{j}(w)}$. Isso significa que a identificação dos agentes não desempenha nenhum papel na atribuição dos seus ganhos.

Marginalismo

O valor de Shapley pode ser definido como uma função que utiliza como argumentos apenas as contribuições marginais do jogador ${\displaystyle i}$.