The algebraic structures of social organizations: the operad of cooperative games

Resumo Técnico: As Estruturas Algébricas de Organizações Sociais: O Operad de Jogos Cooperativos

1. Problema e Motivação

A teoria dos jogos cooperativos modela situações onde grupos de indivíduos (coalizões) decidem cooperar para obter benefícios. Um desafio fundamental nesta teoria é a complexidade computacional e estrutural: um jogo com $n$ jogadores é definido por uma função de coalizão com $2^n - 1$ valores, o que torna a análise direta inviável à medida que $n$ cresce.

Historicamente, tentativas de decompor jogos complexos em jogos mais simples (composição/agregação) foram feitas por von Neumann, Morgenstern, Shapley e Owen. No entanto, essas abordagens eram frequentemente ad hoc, limitadas a casos específicos (como jogos simples ou aditivos) e careciam de uma estrutura algébrica unificada. A questão central abordada pelo artigo é: como formalizar sistematicamente a composição de jogos cooperativos, permitindo a análise de jogos compostos e iterados, e quais são as propriedades algébricas dessa estrutura?

2. Metodologia

Os autores utilizam a teoria dos Operads Algébricos (especificamente operads lineares em espaços vetoriais) para fornecer uma estrutura unificada para a composição de jogos.

• Definição do Operad de Jogos ($\mathcal{G}$): Eles definem um operad onde o espaço vetorial $\mathcal{G}(n)$ contém todos os jogos cooperativos com $n$ jogadores.
• Operação de Composição Parcial ($\circ_i$): Introduzem uma operação bilinear que substitui o jogador $i$ de um jogo $\Gamma_A$ por um jogo inteiro $\Gamma_B$. A função de valor do jogo composto $\Gamma_A \circ_i \Gamma_B$ é definida pela fórmula:
  $$\gamma(S) = \beta(B)\alpha(S_A) + \partial_i\alpha(S_A) \cdot \beta(S_B)$$
  Onde:
  • $S_A = S \cap A$ e $S_B = S \cap B$.
  • $\partial_i\alpha(S_A) = \alpha(S_A \cup \{i\}) - \alpha(S_A)$ é a contribuição marginal do jogador $i$ no jogo original.
  • $\beta(B)$ atua como um fator de normalização.
• Transformada de Möbius: Utilizam a transformada de Möbius (que mapeia jogos para a base de jogos de unanimidade) como uma ferramenta chave para isomorfismos e simplificações algébricas.

3. Principais Contribuições e Resultados

A. Estrutura de Operad e Generalização
O artigo prova que a coleção de todos os jogos cooperativos, equipada com as composições parciais definidas, forma um operad unital.

• Generalização: Esta estrutura generaliza todas as noções anteriores de composição, incluindo a soma e produto de Shapley para jogos simples, a composição de jogos simples e a composição tensorial de Owen para jogos normalizados.
• Iteração: A estrutura permite a composição total (agregação de múltiplos jogos em um único), recuperando a definição de jogos compostos de Shapley e Owen como casos particulares de composição total no operad.

B. Apresentação Explícita e Isomorfismo (Teorema B)
Um dos resultados mais profundos é a apresentação explícita do operad de jogos cooperativos em termos de geradores e relações.

• Isomorfismo: Os autores estabelecem um isomorfismo canônico entre o operad de jogos cooperativos ($\mathcal{G}$) e o operad que codifica álgebras trialgebras comutativas ($\text{ComTriass}$), definido por Vallette.
• Geradores: O isomorfismo é induzido pela transformada de Möbius. Concretamente, qualquer jogo cooperativo pode ser expresso como uma combinação linear de composições iteradas de dois jogos básicos de 2 jogadores:
  1. O Jogo de Barganha (2 jogadores).
  2. Os Jogos de Ditador (2 jogadores).
• Isso implica que a estrutura algébrica subjacente a qualquer jogo cooperativo é fundamentalmente construída a partir dessas interações básicas de 2 jogadores.

C. Suboperads Estáveis
O artigo demonstra que diversas classes importantes de jogos, frequentemente estudadas na literatura e em aplicações práticas, formam suboperads (são estáveis sob a operação de composição parcial):

1. Jogos Normalizados e Simples Monótonos: Incluem jogos de votação e clutters.
2. Capacidades (Medidas Fuzzy): Jogos não-negativos e monótonos.
3. Jogos Convexos (e k-monótonos): Relacionados a supermodularidade.
4. Jogos Submodulares (e k-alternantes): Relacionados a submodularidade.
5. Funções de Crença e Medidas de Plausibilidade: Fundamentais na teoria de Dempster-Shafer (evidência).
6. Jogos Balanceados: Jogos com núcleo não-vazio (Teorema de Bondareva-Shapley).

D. Geometria: Permutaedros Generalizados
Uma consequência direta da estabilidade dos jogos convexos não-negativos é a indução de uma estrutura de operad na família de permutaedros generalizados (generalizações de politopos associados a funções convexas). Isso conecta a teoria dos jogos à geometria combinatória e à teoria dos matroides/polimatroides.

E. Agregação de Soluções
Os autores analisam como conceitos de solução clássicos se comportam sob a composição:

• Núcleo (Core): O núcleo de um jogo composto contém o produto tensorial parcial dos núcleos dos componentes. Eles provam que se os núcleos dos componentes são não-vazios, o núcleo do composto também o é (sob certas condições), e fornecem condições para injetividade e sobrejetividade desse mapeamento.
• Valor de Shapley: É derivada uma fórmula explícita para o Valor de Shapley de um jogo composto em termos da transformada de Möbius dos componentes.
• Índice de Banzhaf: Um resultado notável é que o Índice de Banzhaf de um jogo composto é o produto tensorial parcial do Índice de Banzhaf do jogo quotient e do Valor de Shapley do jogo componente, escalado por um fator dependente do tamanho do componente.

4. Significado e Impacto

• Unificação Teórica: O trabalho fornece a primeira estrutura algébrica sistemática que engloba todas as noções de composição de jogos cooperativos, resolvendo o "problema de agregação" de forma unificada.
• Ponte entre Disciplinas: Conecta a Teoria dos Jogos com a Álgebra Homológica (Teoria de Operads), Geometria Combinatória (Permutaedros) e Teoria da Evidência (Funções de Crença).
• Novas Ferramentas Computacionais: Ao reduzir jogos complexos a composições de jogos de 2 jogadores (ditador e barganha), o artigo oferece uma nova base para a análise e computação de valores em jogos grandes.
• Robustez de Soluções: A análise de como o Núcleo e outros índices de poder se comportam sob composição valida a robustez dessas medidas em contextos sociais hierárquicos ou compostos (ex: eleições em sistemas federais ou conselhos internacionais).

Em suma, o artigo reinterpreta a teoria dos jogos cooperativos não apenas como um conjunto de funções de valor, mas como uma estrutura algébrica rica e hierárquica, onde a composição é a operação fundamental, permitindo novas perspectivas sobre a agregação de poder e a estabilidade de soluções em organizações sociais complexas.