The Expected Number of Pairwise Stable Networks

Technische Samenvatting: Het Verwachte Aantal Paar-stabiele Netwerken

Probleemstelling
Dit artikel onderzoekt de probabilistische eigenschappen van paar-stabiliteit binnen economische netwerkvormingsmodellen waarbij individuele nutten willekeurige variabelen zijn. Hoewel paar-stabiliteit (Jackson en Wolinsky, 1996) de dominante oplossingsconcept is voor netwerkvorming, is de existentie ervan niet gegarandeerd voor willekeurige nutprofielen, en de literatuur heeft zich grotendeels gericht op het afleiden van voldoende voorwaarden voor existentie. Dit werk verschuift het perspectief naar een probabilistisch kader, met de vraag: Wat is de waarschijnlijkheid dat een specifiek netwerk paar-stabiel is? Wat is het verwachte aantal paar-stabiele netwerken in een populatie van omvang $n$? Hoe gedraagt dit aantal zich asymptotisch wanneer $n \to \infty$?

Methodologie
De auteurs modelleren een populatie van $n$ individuen waarbij het nut van elke agent $i$ voor elk mogelijk netwerk $g$ onafhankelijk en uniform wordt getrokken uit $[0, 1]$. Dit definieert een netwerkmodel met willekeurige nutten $(U_n, P_n)$.

1. Waarschijnlijkheid van Stabiliteit: Het artikel leidt eerst de waarschijnlijkheid af dat een specifiek netwerk $g$ paar-stabiel is. Dit omvat het analyseren van de voorwaarden voor unilaterale linkverwijdering en bilaterale linktoevoeging. De auteurs stellen vast dat de waarschijnlijkheid van stabiliteit monotoon is met betrekking tot de inclusie van verzamelingen: het toevoegen van links verlaagt de waarschijnlijkheid van stabiliteit.
2. Verwacht Aantal Stabiele Netwerken: Om het verwachte aantal paar-stabiele netwerken te berekenen, introduceren de auteurs het concept van senioriteitsgraden (seniority degrees). Voor een gegeven netwerk wordt een senioriteitsgraad van een individu berekend op basis van hun links met "senioren" (hogere index) en ontbrekende links met "junioren" (lagere index). Het verwachte aantal stabiele netwerken wordt aangetoond de som te zijn van de inversen van de senioriteitsgraden over alle mogelijke netwerken.
3. Grenswaarden en Asymptotica: In het besef dat de exacte sommation computationeel onhandelbaar is voor grote $n$ (vanwege de $2^{n(n-1)/2}$ mogelijke netwerken), leiden de auteurs hanteerbare onder- en bovengrenzen af.
   • De ondergrens maakt gebruik van de Jensen-ongelijkheid toegepast op de logaritme van het product van senioriteitsgraden, wat het probleem reduceert tot de verwachting van de logaritme van een Bernoulli-variabele.
   • De bovengrens hanteert een iteratieve integraalmethode, waarbij de integrand wordt begrensd door een product van onafhankelijke willekeurige variabelen, waarbij een analogie wordt getrokken met het werk van Knuth (1976) over stabiele koppelingen.
4. Variantie en Convergentie: De tweede groep resultaten analyseert de variantie van het aantal stabiele netwerken. De auteurs relateren de afhankelijkheid tussen de stabiliteit van twee netwerken aan hun Hamming-afstand (het aantal links waarmee ze verschillen). Ze bewijzen dat als de Hamming-afstand $\ge 3$ is, de gebeurtenissen van stabiliteit onafhankelijk zijn; als de afstand 2 is, ze positief afhankelijk zijn; en als de afstand 1 is, ze wederzijds uitsluitend zijn.

Belangrijkste Bijdragen en Resultaten

• Monotoniciteit van de Waarschijnlijkheid van Stabiliteit: Het artikel bewijst dat de waarschijnlijkheid dat een netwerk paar-stabiel is afneemt naarmate er meer links worden toegevoegd. Het lege netwerk heeft de hoogste waarschijnlijkheid van stabiliteit, terwijl het volledige netwerk de laagste heeft.
• Gesloten Vorm: Er wordt een exacte uitdrukking geleverd voor het verwachte aantal paar-stabiele netwerken als de som van de reciproken van de senioriteitsgraden van alle netwerken (Theorema 4.2).
• Asymptotisch Gedrag: De auteurs stellen vast dat het verwachte aantal paar-stabiele netwerken groeit met een snelheid die vergelijkbaar is met de sequentie:
  $$c_n = 2^{n(n-1)/2} \left(\frac{2}{n+1}\right)^n$$
  Hoewel het totale aantal netwerken groeit als $2^{n(n-1)/2}$, neemt het deel van de netwerken dat paar-stabiel is af als $(\frac{2}{n+1})^n$, en nadert dit naar nul.
• Genormaliseerde Verwachting: Door het aantal stabiele netwerken te normaliseren met $c_n$, tonen de auteurs aan dat de verwachte genormaliseerde waarde asymptotisch tussen $\sqrt{e}$ en $e$ ligt.
• Variantieconvergentie: De variantie van het genormaliseerde aantal paar-stabiele netwerken convergeert naar nul wanneer $n \to \infty$. Dit is een gevolg van het feit dat naarmate $n$ groter wordt, het deel van de netwerkparen met een Hamming-afstand $\ge 3$ de 1 nadert, waardoor de stabiliteitsgebeurtenissen asymptotisch onafhankelijk worden.
• Bijna Zekere Convergentie: Door de convergentie van de variantie naar nul te combineren met de groei van de verwachting, concludeert het artikel dat bijna zeker het absolute aantal paar-stabiele netwerken naar oneindig divergeert wanneer $n \to \infty$, terwijl het deel van deze netwerken onder alle mogelijke netwerken naar nul neigt.

Betekenis en Claims
Het artikel beweert een probabilistische fundering te bieden voor de visie op paar-stabiliteit als een "zwak" of "permissief" oplossingsconcept. In tegenstelling tot willekeurige koppelingsmodellen waar een stabiele koppeling gegarandeerd bestaat (Gale en Shapley, 1962), garandeert paar-stabiliteit in netwerken niet de existentie voor elk profiel. Echter, deze probabilistische analyse demonstreert dat hoewel het deel van de stabiele netwerken verdwijnt, het absolute aantal stabiele netwerken explodeert naarmate de populatie groeit. Zo is het in grote populaties niet alleen mogelijk, maar bijna zeker dat er meerdere paar-stabiele netwerken bestaan.

De auteurs merken op dat hun benadering verschilt van de literatuur over willekeurige spelen (bijv. Goldman, 1957; Rinott en Scarsini, 2000), omdat paar-stabiliteit een asymmetrisch concept is (unilaterale verwijdering versus bilaterale toevoeging), wat leidt tot onderscheidende statistische eigenschappen. Het verschilt eveneens van willekeurige koppelingsmodellen vanwege de grotere probabilistische ruimte en de specifieke mechanica van linkvorming.

Beperkingen en Toekomstige Richtingen
Het artikel erkent dat de exacte limiet van het genormaliseerde verwachte aantal stabiele netwerken een openstaande vraag blijft, hoewel het begrensd is tussen $\sqrt{e}$ en $e$. Voorgestelde toekomstige onderzoeksrichtingen omvatten het introduceren van correlaties in de uitbetalingen (volgens Rinott en Scarsini, 2000), het toepassen van het kader op specifieke netwerkmodellen zoals het co-auteurschap- of connectiemodel, en het analyseren van sterkere oplossingsconcepten zoals sterk stabiele netwerken waar willekeurige coalities kunnen afwijken.