The Expected Number of Pairwise Stable Networks

Resumo Técnico: O Número Esperado de Redes de Estabilidade Pares

Enunciado do Problema
Este artigo investiga as propriedades probabilísticas da estabilidade pares dentro de modelos de formação de redes econômicas onde as utilidades individuais são variáveis aleatórias. Embora a estabilidade pares (Jackson e Wolinsky, 1996) seja o conceito de solução dominante para a formação de redes, sua existência não é garantida para perfis de utilidade arbitrários, e a literatura tem se concentrado amplamente em derivar condições suficientes para a existência. Este trabalho desloca a perspectiva para um arcabouço probabilístico, perguntando: Qual é a probabilidade de uma rede específica ser estável por pares? Qual é o número esperado de redes estáveis por pares em uma população de tamanho $n$? Como esse número se comporta assintoticamente quando $n \to \infty$?

Metodologia
Os autores modelam uma população de $n$ indivíduos onde a utilidade de cada agente $i$ para cada rede possível $g$ é extraída independentemente e uniformemente de $[0, 1]$. Isso define um modelo de rede com utilidades aleatórias $(U_n, P_n)$.

1. Probabilidade de Estabilidade: O artigo primeiro deriva a probabilidade de uma rede específica $g$ ser estável por pares. Isso envolve analisar as condições para a exclusão unilateral de ligações e a adição bilateral de ligações. Os autores estabelecem que a probabilidade de estabilidade é monótona em relação à inclusão de conjuntos: adicionar ligações diminui a probabilidade de estabilidade.
2. Número Esperado de Redes Estáveis: Para calcular o número esperado de redes estáveis por pares, os autores introduzem o conceito de graus de senioridade. Para uma determinada rede, o grau de senioridade de um indivíduo é calculado com base em suas ligações com "seniores" (índice maior) e ligações ausentes com "juniores" (índice menor). O número esperado de redes estáveis é mostrado como a soma dos inversos dos graus de senioridade de todas as redes possíveis.
3. Limites e Assintótica: Reconhecendo que a soma exata é computacionalmente intratável para $n$ grandes (devido às $2^{n(n-1)/2}$ redes possíveis), os autores derivam limites inferior e superior tratáveis.
   • O limite inferior utiliza a desigualdade de Jensen aplicada ao logaritmo do produto dos graus de senioridade, reduzindo o problema à expectativa do logaritmo de uma variável aleatória de Bernoulli.
   • O limite superior emprega uma abordagem de integral iterada, limitando o integrando por um produto de variáveis aleatórias independentes, traçando uma analogia ao trabalho de Knuth (1976) sobre emparelhamentos estáveis.
4. Variância e Convergência: O segundo grupo de resultados analisa a variância do número de redes estáveis. Os autores relacionam a dependência entre a estabilidade de duas redes à sua distância de Hamming (o número de ligações pelas quais elas diferem). Eles provam que, se a distância de Hamming for $\ge 3$, os eventos de estabilidade são independentes; se a distância for 2, eles são positivamente dependentes; e se a distância for 1, eles são mutuamente exclusivos.

Principais Contribuições e Resultados

• Monotonicidade da Probabilidade de Estabilidade: O artigo prova que a probabilidade de uma rede ser estável por pares diminui conforme as ligações são adicionadas. A rede vazia possui a maior probabilidade de estabilidade, enquanto a rede completa possui a menor.
• Expressão de Forma Fechada: Uma expressão exata para o número esperado de redes estáveis por pares é fornecida como a soma dos inversos dos graus de senioridade de todas as redes (Teorema 4.2).
• Comportamento Assintótico: Os autores estabelecem que o número esperado de redes estáveis por pares cresce a uma taxa comparável à sequência:
  $$c_n = 2^{n(n-1)/2} \left(\frac{2}{n+1}\right)^n$$
  Embora o número total de redes cresça como $2^{n(n-1)/2}$, a fração de redes que são estáveis por pares decai como $(\frac{2}{n+1})^n$, tendendo a zero.
• Expectativa Normalizada: Ao normalizar o número de redes estáveis por $c_n$, os autores mostram que o valor esperado normalizado situa-se assintoticamente entre $\sqrt{e}$ e $e$.
• Convergência da Variância: A convergência da variância do número normalizado de redes estáveis por pares para zero quando $n \to \infty$. Isso é uma consequência do fato de que, conforme $n$ cresce, a fração de pares de redes com uma distância de Hamming $\ge 3$ aproxima-se de 1, tornando os eventos de estabilidade assintoticamente independentes.
• Convergência Quase Certa: Combinando a convergência da variância para zero com o crescimento da expectativa, o artigo conclui que, quase certamente, o número absoluto de redes estáveis por pares tende ao infinito quando $n \to \infty$, enquanto a fração de tais redes entre todas as redes possíveis tende a zero.

Significância e Alegações
O artigo afirma fornecer uma base probabilística para a visão da estabilidade por pares como um conceito de solução "fraco" ou "permissivo". Diferente dos modelos de emparelhamento aleatório onde um emparelhamento estável é garantido (Gale e Shapley, 1962), a estabilidade por pares em redes não garante a existência para cada perfil. No entanto, esta análise probabilística demonstra que, embora a fração de redes estáveis desapareça, o número absoluto de redes estáveis explode conforme a população cresce. Assim, em populações grandes, não é apenas possível, mas quase certo que múltiplas redes estáveis por pares existam.

Os autores observam que sua abordagem difere da literatura de jogos aleatórios (ex: Goldman, 1957; Rinott e Scarsini, 2000) porque a estabilidade por pares é um conceito assimétrico (exclusão unilateral vs. adição bilateral), levando a propriedades estatísticas distintas. Da mesma forma, difere dos modelos de emparelhamento aleatório devido ao espaço de probabilidade maior e à mecânica específica de formação de ligações.

Limitações e Direções Futuras
O artigo reconhece que o limite exato do número esperado normalizado de redes estáveis permanece uma questão aberta, embora esteja limitado entre $\sqrt{e}$ e $e$. As direções de pesquisa futura sugeridas incluem a introdução de correlações nos pagamentos (seguindo Rinott e Scarsini, 2000), a aplicação do arcabouço a modelos de redes específicos, como os modelos de coautoria ou de conexões, e a análise de conceitos de solução mais fortes, como redes fortemente estáveis, onde coalizões arbitrárias podem desviar-se.