关于「稳定配对:伊尔文室友算法、无解的情形与满意度的代价」,《私董社群的互惠边与破冰配对》给出的定量结论是什么?
结论:第五章用伊尔文的室友算法求稳定配对,随机意向下十六人社群有 0.8485 的机会存在稳定配对。
数据口径:书中的社群、成员、属性与概率均为示意;全部计算由书中程序生成;本书是非个人化经营建议,只使用成员明示同意的数据,不做个人画像,退群自由,退款按约定。 第一章普查一个示意社群:74 个有往来的有向对只形成 15 条互惠边,并用两个模拟世界说明,风险比 6.09 与 2.69 都可能出自互惠边毫无作用的世界。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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 |
查看完整验算程序
# 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))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《高客单私董社群防退群内聚拓扑、度中心性互惠边权重与破冰配对算法母典》第 5 章「稳定配对:伊尔文室友算法、无解的情形与满意度的代价」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}