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
| members | instances | stable pairing exists |
|---|---|---|
| 6 | 2000 | 0.9280 |
| 8 | 2000 | 0.9110 |
| 12 | 2000 | 0.8680 |
| 16 | 2000 | 0.8485 |
| 20 | 2000 | 0.8255 |
| 30 | 2000 | 0.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
- Chapter 1 · No Reciprocal Edge: a Structural Signal of First-Quarter Silent Attrition and the Problem of Identifying It
- Chapter 2 · Degree, Betweenness and Structural Holes: Whose Exit Would Cut the Board Apart
- Chapter 3 · Weighing Reciprocal Edges: Chat Volume, Two-Way Exchange and a Random Baseline
- Chapter 4 · Maximum-Weight Matching for Ice-Breaking Pairs: Exact Recursion, Greed, Rotation and Three Possible Worlds
- Chapter 6 · Similarity and Bridging: the Structural Cost of Pairing and the Ethical Limits of Risk Labels
- Chapter 7 · Eastern and Western Sources Examined: the Joined Lakes of the Dui Hexagram and Aristotle on Friendship
- Chapter 8 · Closing the Loop: the Intake Pairing Sheet, the Ice-Breaker Pairing Planner and a Pre-Registered Test