Stabile Zuordnungen im Mittelbereich

Betrachten Sie den vollständigen bipartiten Graphen mit n+n Knoten, bei dem die Kanten mit i.i.d. exponentiellen Kosten ausgestattet sind. Eine Zuordnung der Knoten ist stabil, wenn sie keine Knotenpaare enthält, bei denen die verbindende Kante günstiger ist als die Matching-Kosten beider. Es gibt eine eindeutige stabile Zuordnung, die durch iteratives Paaren von Knoten mit niedrigen Kantenkosten gewonnen wird. Wir zeigen, dass die Gesamtkosten C₍, ₍ dieser Zuordnung von der Ordnung n mit begrenzter Varianz sind und dass C₍, ₍ - n gegen eine Gumbel-Verteilung konvergiert. Wir zeigen auch, dass die typischen Kosten einer Kante im Matching von der Ordnung 1/n sind, mit einer expliziten Dichte auf dieser Skala, und analysieren den Rang einer typischen Kante. Diese Ergebnisse parallelisieren die von Aldous für die minimalen Kosten-Zuordnung im gleichen Rahmen. Wir betrachten dann die Empfindlichkeit der Zuordnung und der Matching-Kosten gegenüber Störungen der zugrunde liegenden Kantenkosten. Es wird gezeigt, dass das Matching selbst robust ist in dem Sinne, dass zwei Zuordnungen, die auf weitgehend identischen Kantenkosten basieren, eine erhebliche Überlappung aufweisen. Die Matching-Kosten hingegen sind geräuschempfindlich, da mit hoher Wahrscheinlichkeit die teuersten Kanten nach dem Neuzufällig machen ersetzt werden. Unsere Beweise gelten auch für den vollständigen (unipartiten) Graphen und die Ergebnisse sind in diesem Fall qualitativ ähnlich.