What does Reciprocal Edges and Ice-Breaking Pairs in Peer Boards conclude, in numbers, about “Stable Pairing: Irving's Roommates Algorithm, Instances without a Solution and the Price of Satisfaction”?

Answer: Chapter 5 finds stable pairs with Irving's roommates algorithm; under random rankings a board of sixteen has a stable pairing with probability 0.8485.

Scope of the numbers: Chapter 1 takes a census of an illustrative board, where 74 directed pairs with contact form only 15 reciprocal edges, and shows with two simulated worlds that risk ratios of 6.09 and 2.69 can both arise where reciprocal edges do nothing. Marked boxes separate published evidence, runnable Python calculations (18 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.8485

membersinstancesstable pairing exists
620000.9280
820000.9110
1220000.8680
1620000.8485
2020000.8255
3020000.7840
n = 8, 897 solvable instances:
score lost by insisting on stability: mean 1.460, zero in 0.476
blocking pairs of the score-maximising pairing: mean 0.554
worst partner rank: stable 5.456, score-maximising 5.035
Show the full program
# Chapter 5. p52: how often a stable pairing exists, and what it costs.
# Uniformly random complete rankings (each member ranks all others),
# 2,000 instances per board size, Irving's algorithm as in p51.
# For n = 8 every one of the 105 pairings is also scored: rank-sum
# score = sum over members of (7 - position of partner), the most
# satisfied pairing versus the stable one, and the blocking pairs left
# by the score-maximising pairing. Rankings are random, not real data.
import math
import random


def irving(pref):
    n = len(pref)
    rank = [{q: k for k, q in enumerate(p)} for p in pref]
    lst = [list(p) for p in pref]
    held = [None] * n
    free = list(range(n))
    while free:
        x = free.pop(0)
        while lst[x]:
            y = lst[x][0]
            if held[y] is None or rank[y][x] < rank[y][held[y]]:
                if held[y] is not None:
                    free.append(held[y])
                held[y] = x
                break
            lst[x].pop(0)
        if not lst[x]:
            return None
    for y in range(n):
        cut = rank[y][held[y]]
        for z in [z for z in lst[y] if rank[y][z] > cut]:
            lst[y].remove(z)
            if y in lst[z]:
                lst[z].remove(y)
    while True:
        if any(not lst[x] for x in range(n)):
            return None
        start = [x for x in range(n) if len(lst[x]) > 1]
        if not start:
            return [lst[x][0] for x in range(n)]
        seq, seen = [start[0]], {start[0]: 0}
        while True:
            q = lst[seq[-1]][1]
            p = lst[q][-1]
            if p in seen:
                cyc = seq[seen[p]:]
                break
            seen[p] = len(seq)
            seq.append(p)
        for p, q in [(p, lst[p][1]) for p in cyc]:
            for z in [z for z in lst[q] if rank[q][z] > rank[q][p]]:
                lst[q].remove(z)
                if q in lst[z]:
                    lst[z].remove(q)


def blocking(pref, mate):
    n = len(pref)
    rank = [{q: k for k, q in enumerate(p)} for p in pref]
    return [(a, b) for a in range(n) for b in range(a + 1, n)
            if mate[a] != b and rank[a][b] < rank[a][mate[a]]
            and rank[b][a] < rank[b][mate[b]]]


def score(pref, mate):
    n = len(pref)
    return int(math.fsum(n - 1 - pref[a].index(mate[a]) for a in range(n)))


def pairings(items):
    if not items:
        yield []
        return
    a = items[0]
    for k in range(1, len(items)):
        rest = items[1:k] + items[k + 1:]
        for m in pairings(rest):
            yield [(a, items[k])] + m


def random_pref(rng, n):
    pref = []
    for i in range(n):
        others = [j for j in range(n) if j != i]
        rng.shuffle(others)
        pref.append(others)
    return pref


rng = random.Random(20261113)
print("members   instances   stable pairing exists")
for n in (6, 8, 12, 16, 20, 30):
    ok = len([1 for _ in range(2000)
              if irving(random_pref(rng, n)) is not None])
    print("  %2d         2000        %.4f" % (n, ok / 2000))
gaps, blocks, worst_s, worst_m = [], [], [], []
for _ in range(1000):
    pref = random_pref(rng, 8)
    mate = irving(pref)
    if mate is None:
        continue
    best = None
    for m in pairings(list(range(8))):
        mt = [0] * 8
        for a, b in m:
            mt[a], mt[b] = b, a
        key = (score(pref, mt), -len(blocking(pref, mt)))
        if best is None or key > best[0]:
            best = (key, mt)
    gaps.append(best[0][0] - score(pref, mate))
    blocks.append(len(blocking(pref, best[1])))
    worst_s.append(max(pref[a].index(mate[a]) + 1 for a in range(8)))
    worst_m.append(max(pref[a].index(best[1][a]) + 1 for a in range(8)))
k = len(gaps)
print("n = 8, %d solvable instances:" % k)
print("  score lost by insisting on stability: mean %.3f, zero in %.3f"
      % (math.fsum(gaps) / k, len([g for g in gaps if g == 0]) / k))
print("  blocking pairs of the score-maximising pairing: mean %.3f"
      % (math.fsum(blocks) / k))
print("  worst partner rank: stable %.3f, score-maximising %.3f"
      % (math.fsum(worst_s) / k, math.fsum(worst_m) / k))

Single source and citation

Fan, Y. (2026). Cohesion Topology of High-Ticket Peer Boards and First-Quarter Silent Attrition: Degree Centrality, Reciprocal Edge Weights and Ice-Breaking Pairing Algorithms (Version 1.0.0), Chapter 5: Stable Pairing: Irving's Roommates Algorithm, Instances without a Solution and the Price of Satisfaction. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-278 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026278,
  author    = {Fan, Yafu},
  title     = {Cohesion Topology of High-Ticket Peer Boards and First-Quarter Silent Attrition: Degree Centrality, Reciprocal Edge Weights and Ice-Breaking Pairing Algorithms},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book