The Expected Number of Pairwise Stable Networks

Resumen Técnico: El Número Esperado de Redes de Estabilidad por Pares

Planteamiento del Problema
Este artículo investiga las propiedades probabilísticas de la estabilidad por pares dentro de los modelos de formación de redes económicas donde las utilidades individuales son variables aleatorias. Si bien la estabilidad por pares (Jackson y Wolinsky, 1996) es el concepto de solución dominante, su existencia no está garantizada para perfiles de utilidad arbitrarios, y la literatura se ha centrado principalmente en derivar condiciones suficientes para su existencia. Este trabajo cambia la perspectiva hacia un marco probabilístico, preguntando: ¿Cuál es la probabilidad de que una red específica sea estable por pares? ¿Cuál es el número esperado de redes estables por pares en una población de tamaño $n$? ¿Cómo se comporta este número asintóticamente cuando $n \to \infty$?

Metodología
Los autores modelan una población de $n$ individuos donde la utilidad de cada agente $i$ para cada posible red $g$ se extrae de forma independiente y uniforme de $[0, 1]$. Esto define un modelo de red con utilidades aleatorias $(U_n, P_n)$.

1. Probabilidad de Estabilidad: El artículo deriva primero la probabilidad de que una red específica $g$ sea estable por pares. Esto implica analizar las condiciones para la eliminación unilateral de enlaces y la adición bilateral de enlaces. Los autores establecen que la probabilidad de estabilidad es monótona con respecto a la inclusión de conjuntos: añadir enlaces disminuye la probabilidad de estabilidad.
2. Número Esperado de Redes Estables: Para calcular el número esperado de redes estables por pares, $E(s_n)$, los autores introducen el concepto de grados de antigüedad (seniority degrees). Para una red dada, el grado de antigüedad de un individuo se calcula basándose en sus enlaces con "seniors" (índice mayor) y sus enlaces faltantes con "juniors" (índice menor). Se demuestra que el número esperado de redes estables es la suma de los inversos de los grados de antigüedad de todas las redes posibles.
3. Límites y Asintótica: Reconociendo que la sumatoria exacta es computacionalmente intratable para $n$ grandes (debido a las $2^{n(n-1)/2}$ redes posibles), los autores derivan límites inferior y superior tratables.
   • El límite inferior utiliza la desigualdad de Jensen aplicada al logaritmo del producto de los grados de antigüedad, reduciendo el problema a la esperanza del logaritmo de una variable de Bernoulli.
   • El límite superior emplea un enfoque de integral iterada, acotando el integrando mediante un producto de variables aleatorias independientes, trazando una analogía con el trabajo de Knuth (1976) sobre emparejamientos estables.
4. Varianza y Convergencia: El segundo grupo de resultados analiza la varianza del número de redes estables. Los autores relacionan la dependencia entre la estabilidad de dos redes con su distancia de Hamming (el número de enlaces en los que difieren). Demuestran que si la distancia de Hamming es $\ge 3$, los eventos de estabilidad son independientes; si la distancia es 2, son dependientes positivamente; y si la distancia es 1, son mutuamente excluyentes.

Contribuciones Clave y Resultados

• Monotonicidad de la Probabilidad de Estabilidad: El artículo demuestra que la probabilidad de que una red sea estable por pares disminuye a medida que se añaden enlaces. La red vacía tiene la mayor probabilidad de estabilidad, mientras que la red completa tiene la menor.
• Expresión de Forma Cerrada: Se proporciona una expresión exacta para el número esperado de redes estables por pares como la suma de los recíprocos de los grados de antigüedad de todas las redes (Teorema 4.2).
• Comportamiento Asintótico: Los autores establecen que el número esperado de redes estables por pares crece a un ritmo comparable a la secuencia:
  $$c_n = 2^{n(n-1)/2} \left(\frac{2}{n+1}\right)^n$$
  Mientras que el número total de redes crece como $2^{n(n-1)/2}$, la fracción de redes que son estables por pares decae como $(\frac{2}{n+1})^n$, tendiendo a cero.
• Esperanza Normalizada: Al normalizar el número de redes estables por $c_n$, los autores muestran que la esperanza normalizada se sitúa asintóticamente entre $\sqrt{e}$ y $e$.
• Convergencia de la Varianza: La varianza del número normalizado de redes estables por pares converge a cero cuando $n \to \infty$. Esto es consecuencia de que, a medida que $n$ crece, la fracción de pares de redes con una distancia de Hamming $\ge 3$ se aproxima a 1, haciendo que los eventos de estabilidad sean asintóticamente independientes.
• Convergencia Casi Segura: Combinando la convergencia de la varianza a cero con el crecimiento de la esperanza, el artículo concluye que, casi seguramente, el número absoluto de redes estables por pares tiende al infinito cuando $n \to \infty$, mientras que la fracción de tales redes entre todas las redes posibles tiende a cero.

Significancia y Reivindicaciones
El artículo afirma proporcionar una base probabilística para la visión de la estabilidad por pares como un concepto de solución "débil" o "permisivo". A diferencia de los modelos de emparejamiento aleatorio donde se garantiza la existencia de un emparejamiento estable (Gale y Shapley, 1962), la estabilidad por pares en redes no garantiza la existencia para cada perfil. Sin embargo, este análisis probabilístico demuestra que, si bien la fracción de redes estables desaparece, el número absoluto de redes estables explota a medida que la población crece. Por lo tanto, en poblaciones grandes, no solo es posible, sino casi seguro que existan múltiples redes estables por pares.

Los autores señalan que su enfoque difiere de la literatura de juegos aleatorios (por ejemplo, Goldman, 1957; Rinott y Scarsini, 2000) porque la estabilidad por pares es un concepto asimétrico (eliminación unilateral frente a adición bilateral), lo que conduce a propiedades estadísticas distintas. Del mismo modo, difiere de los modelos de emparejamiento aleatorio debido al espacio de probabilidad más amplio y a la mecánica específica de la formación de enlaces.

Limitaciones y Direcciones Futuras
El artículo reconoce que el límite exacto del número esperado normalizado de redes estables sigue siendo una cuestión abierta, aunque está acotado entre $\sqrt{e}$ y $e$. Las direcciones de investigación futura sugeridas incluyen la introducción de correlaciones en las utilidades (siguiendo a Rinott y Scarsini, 2000), la aplicación del marco a modelos de redes específicos como los modelos de coautoría o de conexiones, y el análisis de conceptos de solución más fuertes, como las redes fuertemente estables donde coaliciones arbitrarias pueden desviarse.