The Expected Number of Pairwise Stable Networks

Résumé technique : Le nombre attendu de réseaux de stabilité par paire

Énoncé du problème
Cet article étudie les propriétés probabilistes de la stabilité par paire au sein de modèles de formation de réseaux économiques où les utilités individuelles sont des variables aléatoires. Bien que la stabilité par paire (Jackson et Wolinsky, 1996) soit le concept de solution dominant, son existence n'est pas garantie pour des profils d'utilité arbitraires, et la littérature s'est largement concentrée sur la dérivation des conditions suffisantes pour l'existence. Ce travail déplace la perspective vers un cadre probabiliste, en posant les questions suivantes : Quelle est la probabilité qu'un réseau spécifique soit stable par paire ? Quel est le nombre attendu de réseaux stables par paire dans une population de taille $n$ ? Comment ce nombre se comporte-t-il de manière asymptotique lorsque $n \to \infty$ ?

Méthodologie
Les auteurs modélisent une population de $n$ individus où l'utilité de chaque agent $i$ pour chaque réseau $g$ possible est tirée de manière indépendante et uniforme de $[0, 1]$. Cela définit un modèle de réseau avec des utilités aléatoires $(U_n, P_n)$.

1. Probabilité de stabilité : L'article dérive d'abord la probabilité qu'un réseau spécifique $g$ soit stable par paire. Cela implique l'analyse des conditions de suppression unilatérale de liens et d'ajout bilatéral de liens. Les auteurs établissent que la probabilité de stabilité est monotone par rapport à l'inclusion d'ensembles : l'ajout de liens diminue la probabilité de stabilité.
2. Nombre attendu de réseaux stables : Pour calculer le nombre attendu de réseaux stables par paire, les auteurs introduisent le concept de degrés de séniorité. Pour un réseau donné, le degré de séniorité d'un individu est calculé en fonction de ses liens avec des « seniors » (indice plus élevé) et de ses liens manquants avec des « juniors » (indice plus faible). Le nombre attendu de réseaux stables est montré comme étant la somme des inverses des degrés de séniorité à travers tous les réseaux possibles.
3. Bornes et asymptotique : Reconnaissant que la sommation exacte est numériquement intraitable pour de grands $n$ (en raison des $2^{n(n-1)/2}$ réseaux possibles), les auteurs dérivent des bornes inférieure et supérieure exploitables.
   • La borne inférieure utilise l'inégalité de Jensen appliquée au logarithme du produit des degrés de séniorité, réduisant le problème à l'espérance du logarithme d'une variable aléatoire de Bernoulli.
   • La borne supérieure emploie une approche d'intégrale itérée, bornant l'intégrande par un produit de variables aléatoires indépendantes, en faisant une analogie avec les travaux de Knuth (1976) sur les appariements stables.
4. Variance et convergence : Le second groupe de résultats analyse la variance du nombre de réseaux stables. Les auteurs relient la dépendance entre la stabilité de deux réseaux à leur distance de Hamming (le nombre de liens par lesquels ils diffèrent). Ils prouvent que si la distance de Hamming est $\ge 3$, les événements de stabilité sont indépendants ; si la distance est de 2, ils sont positivement dépendants ; et si la distance est de 1, ils sont mutuellement exclusifs.

Contributions clés et résultats

• Monotonie de la probabilité de stabilité : L'article prouve que la probabilité qu'un réseau soit stable par paire diminue à mesure que les liens sont ajoutés. Le réseau vide possède la probabilité de stabilité la plus élevée, tandis que le réseau complet possède la plus faible.
• Expression en forme close : Une expression exacte pour le nombre attendu de réseaux stables par paire est fournie sous la forme de la somme des inverses des degrés de séniorité de tous les réseaux (Théorème 4.2).
• Comportement asymptotique : Les auteurs établissent que le nombre attendu de réseaux stables par paire croît à un rythme comparable à la séquence :
  $$c_n = 2^{n(n-1)/2} \left(\frac{2}{n+1}\right)^n$$
  Alors que le nombre total de réseaux croît comme $2^{n(n-1)/2}$, la fraction de réseaux qui sont stables par paire décroît comme $(\frac{2}{n+1})^n$, tendant vers zéro.
• Espérance normalisée : En normalisant le nombre de réseaux stables par $c_n$, les auteurs montrent que l'espérance normalisée se situe asymptotiquement entre $\sqrt{e}$ et $e$.
• Convergence de la variance : La variance du nombre normalisé de réseaux stables par paire converge vers zéro lorsque $n \to \infty$. Cela découle du fait qu'à mesure que $n$ augmente, la fraction de paires de réseaux ayant une distance de Hamming $\ge 3$ approche 1, rendant les événements de stabilité asymptotiquement indépendants.
• Convergence presque sûre : En combinant la convergence de la variance vers zéro avec la croissance de l'espérance, l'article conclut qu'presque sûrement, le nombre absolu de réseaux stables par paire tend vers l'infini lorsque $n \to \infty$, tandis que la fraction de tels réseaux parmi tous les réseaux possibles tend vers zéro.

Signification et affirmations
L'article affirme fournir un fondement probabiliste à la vision de la stabilité par paire comme un concept de solution « faible » ou « permissif ». Contrareusement aux modèles d'appariement aléatoire où un appariement stable est garanti d'exister (Gale et Shapley, 1962), la stabilité par paire dans les réseaux ne garantit pas l'existence pour chaque profil. Cependant, cette analyse probabiliste démontre que bien que la fraction de réseaux stables disparaisse, le nombre absolu de réseaux stables explose à mesure que la population croît. Ainsi, dans de grandes populations, il est non seulement possible mais presque certain que plusieurs réseaux stables par paire existent.

Les auteurs notent que leur approche diffère de la littérature sur les jeux aléatoires (par exemple, Goldman, 1957 ; Rinott et Scarsini, 2000) car la stabilité par paire est un concept asymétrique (suppression unilatérale vs ajout bilatéral), conduisant à des propriétés statistiques distinctes. De même, elle diffère des modèles d'appariement aléatoire en raison de l'espace probabiliste plus vaste et des mécanismes spécifiques de formation de liens.

Limites et directions futures
L'article reconnaît que la limite exacte du nombre attendu normalisé de réseaux stables demeure une question ouverte, bien qu'elle soit bornée entre $\sqrt{e}$ et $e$. Les directions de recherche futures suggérées incluent l'introduction de corrélations dans les gains (suivant Rinott et Scarsini, 2000), l'application du cadre à des modèles de réseaux spécifiques comme les modèles de co-auteurs ou de connexions, et l'analyse de concepts de solution plus forts tels que les réseaux fortement stables où des coalitions arbitraires peuvent dévier.