Resumo Técnico: Uma Classe Tratável de Jogos Cooperativos Definidos por Redes Direcionadas

Declaração do Problema

O artigo aborda os desafios computacionais e analíticos inerentes à teoria dos jogos cooperativos, especificamente no que diz respeito a jogos induzidos por grafos direcionados ponderados. Jogos cooperativos tipicamente sofrem com um tamanho de representação exponencial em relação ao número de jogadores, tornando o cálculo de conceitos de solução (como os valores de Shapley e Banzhaf) e propriedades de estabilidade (como o núcleo) intratável ($\sharp$P-completo em muitos casos).

Embora trabalhos anteriores tenham estudado jogos induzidos por grafos não direcionados ou subclasses específicas (por exemplo, jogos de votação ponderada), há uma necessidade de classes estruturadas de jogos definidas por redes direcionadas que permaneçam tratáveis analítica e computacionalmente. Os autores introduzem uma classe específica de jogos, denominada "jogos de confiança", onde o valor da coalizão é determinado tanto por interações internas quanto por exposições externas. O principal desafio é derivar fórmulas de tempo polinomial e de forma fechada para conceitos de solução e caracterizar as propriedades de estabilidade desses jogos, particularmente dado que o componente externo introduz um comportamento não aditivo, semelhante a um gargalo.

Metodologia

Os autores definem o Jogo de Confiança $(N, v)$ induzido por um grafo direcionado ponderado $G = (N, E)$ com pesos de aresta $a_{ij} \in [0, 1]$. O valor de uma coalizão $S \subseteq N$ é definido como a soma de dois componentes:

1. Termo Interno: A soma dos pesos de todas as arestas $(i, j)$ onde ambos $i, j \in S$. Isso corresponde a um jogo de subgrafo induzido.
2. Termo Externo: Para cada jogador $i \in S$ que possui arestas de entrada vindas de fora de $S$, o valor inclui o mínimo peso entre essas arestas de entrada. Se um jogador em $S$ não tiver arestas de entrada vindas de fora, este termo contribui com 0.

Matematicamente:
$$v(S) = \sum_{i \in S, j \in S, (i,j) \in E} a_{ij} + \sum_{i \in S^*} \min_{j \notin S: (j,i) \in E} a_{ji}$$
onde $S^*$ é o conjunto de jogadores em $S$ com pelo menos uma aresta de entrada de $N \setminus S$.

Para analisar este jogo, os autores empregam a transformada de Möbius para decompor o jogo em uma combinação linear de jogos de unanimidade ($u_T$).

• O componente interno é direto, envolvendo jogos de unanimidade pares.
• O componente externo é mais complexo devido ao operador $\min$. Os autores ordenam os vizinhos de entrada de cada jogador $i$ por pesos de aresta não decrescentes. Eles demonstram que o jogo externo para o jogador $i$ pode ser expresso como uma soma telescópica de jogos de unanimidade, onde os suportes formam uma cadeia de inclusão determinada pela classificação dos vizinhos de entrada.

Essa decomposição permite que os autores aproveitem a linearidade dos operadores de Shapley e Banzhaf para derivar fórmulas explícitas.

Contribuições e Resultados Principais

1. Decomposição de Unanimidade

O artigo estabelece uma decomposição de unanimidade de forma fechada para o jogo de confiança.

• Lema 2.3: O jogo externo $w_i(S)$ para um jogador $i$ é decomposto em uma soma de jogos de unanimidade $u_{T_i(t)}$, onde $T_i(t)$ consiste no jogador $i$ e seus primeiros $t-1$ vizinhos de entrada (ordenados por peso). Os coeficientes são diferenças nos pesos de aresta ordenados.
• Lema 3.2: O jogo total $v(S)$ é a soma dos jogos de unanimidade pares internos e dos jogos de unanimidade externos decompostos.

2. Conceitos de Solução em Tempo Polinomial

Usando a decomposição de unanimidade, os autores derivam fórmulas explícitas e de tempo polinomial para:

• Valor de Shapley ($\phi_i$): O valor é expresso como uma soma de três partes:
  1. A média dos pesos das arestas internas (centralidade de grau ponderado simétrica).
  2. Um termo derivado das próprias arestas de entrada do jogador $i$ (exposição externa).
  3. Um termo derivado das arestas de entrada para os vizinhos de saída de $i$ (efeitos de vizinhos compartilhados).
     A fórmula (Teorema 3.1) conta explicitamente a classificação de cada jogador entre os vizinhos de entrada de outros.
• Valor de Banzhaf ($\beta_i$): Da mesma forma, uma fórmula de forma fechada é derivada (Teorema 4.2), utilizando o valor específico de Banzhaf de jogos de unanimidade ($2^{1-|T|}$).

3. Análise de Efeitos Marginais

O artigo analisa como mudanças locais nos pesos das arestas afetam os valores de solução.

• Lemas 3.5 e 4.3: O efeito marginal de um peso de aresta $a_{kj}$ no valor de um jogador depende da posição do jogador em relação à aresta:
  • Arestas internas: Contribuem linearmente para os valores de Shapley e Banzhaf.
  • Arestas externas: O efeito é não linear e depende da classificação do jogador entre os vizinhos de entrada do nó alvo. Para o valor de Shapley, o efeito envolve termos como $\frac{1}{r(r+1)}$, enquanto o valor de Banzhaf envolve $\frac{1}{2^r}$.
• Caracterização de Jogador Nulo: O Lema 3.6 fornece condições necessárias e suficientes para um jogador ser um jogador nulo (valor 0), o que ocorre se ele não tiver arestas de entrada ou se suas arestas de entrada forem de jogadores que são, eles mesmos, nulos em um sentido estrutural específico.

4. Estabilidade e Propriedades do Núcleo

Os autores investigam a estabilidade do jogo de confiança:

• Caracterização do Núcleo (Lema 5.1): O núcleo do jogo de confiança é um singleton. Consiste em uma alocação única onde cada jogador $i$ recebe a soma de todos os pesos das arestas de entrada de todo o grafo ($\sum_{j} a_{ji}$).
• Equilíbrio Total (Lema 5.2): O jogo é totalmente equilibrado, o que significa que todo subjogo (restrito a qualquer coalizão $S$) tem um núcleo não vazio. Isso é provado construindo uma alocação de núcleo explícita para qualquer subjogo.
• Divergência de Conceitos: O artigo destaca que a alocação única do núcleo (baseada nos pesos totais de entrada) geralmente não coincide com os valores de Shapley ou Banzhaf. Isso demonstra um cenário onde alocações baseadas em estabilidade e conceitos de solução baseados em equidade divergem.

Significado e Alegações

O artigo alega fornecer um exemplo tratável de jogos cooperativos induzidos por redes estruturadas. Seu significado reside em:

1. Tratabilidade Computacional: Oferece uma classe de jogos onde conceitos de solução (Shapley, Banzhaf) e propriedades de estabilidade (Núcleo) podem ser computados em tempo polinomial, evitando a complexidade exponencial típica de jogos cooperativos gerais.
2. Insight Estrutural: A decomposição de unanimidade revela que o complexo operador "mínimo" no componente externo cria uma cadeia aninhada de jogos de unanimidade, tornando o jogo analiticamente gerenciável.
3. Distinção Teórica: Ilustra explicitamente um cenário onde o núcleo (estabilidade) e o valor de Shapley (equidade/contribuição marginal) produzem alocações diferentes, apesar de o jogo ser totalmente equilibrado.
4. Fundação para Trabalho Futuro: Os autores sugerem que esta classe serve como uma linha de base para explorar generalizações paramétricas, regras de agregação alternativas para o componente externo e problemas de design de mecanismos relacionados à compatibilidade de incentivos.

O trabalho não propõe novas aplicações experimentais, mas estabelece um quadro teórico para analisar interações cooperativas em redes direcionadas com avaliações locais assimétricas.