Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games

Resumo Técnico: Eliminação Sequencial e Valor Shapley de União para Avaliação de Grupos em Jogos Cooperativos

Enunciação do Problema
Na teoria dos jogos cooperativos e em campos relacionados, como centralidade em redes e valoração de dados em aprendizado de máquina, um desafio fundamental é estender avaliações de jogadores individuais para grupos. Os métodos existentes geralmente dependem de duas abordagens diretas:

1. Soma: Agregação de valores individuais (por exemplo, a soma dos valores de Shapley). Isso ignora a estrutura subjacente de cooperação e as dependências entre os jogadores.
2. Fusão: Tratamento do grupo como um único elemento fundido e sua avaliação (por exemplo, o Valor Shapley de Fusão). Isso altera a estrutura do jogo e falha em distinguir entre jogadores independentes e jogadores altamente dependentes.

Ambas as abordagens frequentemente falham em capturar com precisão as dependências dentro dos grupos. Por exemplo, em um jogo onde dois pares disjuntos de jogadores geram valor independentemente, somar valores individuais ou fundir grupos pode atribuir incorretamente importância igual a um par de jogadores cooperativos e a um par de jogadores independentes, falhando em refletir a assimetria em seu impacto sistêmico.

Metodologia
Os autores propõem e analisam uma terceira abordagem baseada na eliminação sequencial. Neste quadro, os elementos de um grupo são removidos um por um, e suas avaliações nos jogos reduzidos resultantes são agregadas. A hipótese central é que este método mede naturalmente a contribuição líquida de um grupo, descontando efeitos sobrepostos e focando no dano causado pela ausência do grupo.

O estudo fundamenta-se numa análise axiomática abrangente de valores de grupo em jogos cooperativos. A metodologia envolve:

• Definição de Classes Axiomáticas: Os autores introduzem uma classe de semivalores de grupo (fracamente consistentes). Estes são valores de grupo que satisfazem Linearidade, Simetria, Monotonicidade Fraca, Saída do Jogador Nulo e o Axioma do Jogador Falso. Eles também definem uma classe correspondente de semivalores de sinergia, que substituem o Axioma do Jogador Falso pelo Axioma do Jogador Desfazedor (introduzido por Grabisch e Roubens).
• Extensão Sequencial: O artigo estabelece que um valor de jogador admite uma extensão sequencial se e somente se satisfizer a propriedade de Contribuições Equilibradas. É provado que todo semivale consistente (satisfazendo Saída do Jogador Nulo) admite uma extensão sequencial única.
• Função Potencial: Os autores utilizam a função potencial introduzida por Hart e Mas-Colell para caracterizar a extensão sequencial do valor de Shapley.

Principais Contribuições e Resultados

1. O Valor Shapley de União:
   Os autores introduzem o Valor Shapley de União como a extensão sequencial única do valor de Shapley. É definido como a diferença entre o potencial do jogo original e o potencial do jogo após a remoção do grupo:
   $$US_S(N, v) = P(N, v) - P(N \setminus S, v) = \sum_{T \subseteq N, S \cap T \neq \emptyset} \frac{\Delta v(T)}{|T|}$$
   onde $\Delta v(T)$ são os dividendos de Harsanyi.

   • Interpretação: Este valor mede o "dano" infligido ao jogo quando um grupo sai. Ele agrega contribuições de modo que o dividendo de cada coalizão seja contado no máximo uma vez, mesmo que o grupo contenha múltiplos membros dessa coalizão.
   • Axiomatização: O valor Shapley de União é caracterizado unicamente pelos axiomas de Potencial (ou Contribuições Equilibradas) combinados com Eficiência. Também é caracterizado unicamente entre semivalores de grupo pela Igualdade de Grupos (todos os grupos em um jogo de unanimidade são igualmente importantes).

2. Classificação Axiomática de Valores de Grupo:
   O artigo distingue entre duas variantes de avaliação de grupo:

   • Valor Total: Valores que avaliam o valor total de um grupo (por exemplo, Extensão de Soma, Shapley de Fusão, Shapley de União). Estes são capturados por semivalores de grupo.
   • Sinergia: Valores que medem a sinergia de um grupo (por exemplo, Índice de Interação). Estes são capturados por semivalores de sinergia.
     Os autores fornecem uma correspondência funcional entre essas duas classes. Especificamente, eles mostram que o Valor Shapley de Fusão corresponde ao Índice de Interação (um contraparte sinérgico), e o Valor Shapley de União corresponde a um novo valor sinérgico chamado Valor Shapley de Interseção.

3. O Valor Shapley de Interseção:
   Definido como a soma dos dividendos das coalizões que contêm o grupo inteiro:
   $$IS_S(N, v) = \sum_{S \subseteq T \subseteq N} \frac{\Delta v(T)}{|T|}$$
   Este valor mede a interseção de contribuições. Para um grupo de tamanho dois, a soma do Valor Shapley de União e do Valor Shapley de Interseção é igual à soma dos valores de Shapley individuais:
   $$US_{\{i,j\}}(N, v) + IS_{\{i,j\}}(N, v) = SV_i(N, v) + SV_j(N, v)$$
   Esta decomposição permite a separação do valor conjunto de um grupo em uma parte de "união" (contando contribuições uma vez) e uma parte de "interseção" (sinergia).

4. Comparação com Trabalhos Existentes:
   A análise esclarece a relação entre os valores propostos e a literatura existente:

   • O Valor Shapley de Fusão (Marichal et al.) é mostrado como o único semivale de grupo que satisfaz o axioma da Coalizão Falsa.
   • O Índice de Interação (Grabisch e Roubens) é identificado como um semivale de sinergia, distinto dos semivalores de grupo porque viola o axioma padrão do Jogador Falso em favor do Axioma do Jogador Desfazedor.
   • O artigo demonstra que a abordagem de extensão sequencial é teoricamente robusta, pois se aplica a todos os semivalores consistentes e produz valores com fortes propriedades axiomáticas.

Significância
O artigo afirma que a abordagem de extensão sequencial, e especificamente o Valor Shapley de União, constitui uma das extensões mais naturais e teoricamente fundamentadas de valores de jogadores para grupos em jogos cooperativos. Ao distinguir entre avaliar o valor total e medir a sinergia, os autores fornecem um quadro unificado que esclarece as diferenças entre noções existentes na literatura. A introdução dos Valores Shapley de União e de Interseção oferece novas ferramentas para analisar interações, particularmente em cenários onde a sobreposição de contribuições deve ser descontada (União) ou onde a sinergia pura deve ser isolada (Interseção). O trabalho estabelece que esses valores não são heurísticas arbitrárias, mas são determinados unicamente por axiomas fundamentais, como Contribuições Equilibradas, Potencial e Igualdade de Grupos.