关于「稳定配对:伊尔文室友算法、无解的情形与满意度的代价」,《私董社群的互惠边与破冰配对》给出的定量结论是什么?

结论:第五章用伊尔文的室友算法求稳定配对,随机意向下十六人社群有 0.8485 的机会存在稳定配对。

数据口径:书中的社群、成员、属性与概率均为示意;全部计算由书中程序生成;本书是非个人化经营建议,只使用成员明示同意的数据,不做个人画像,退群自由,退款按约定。 第一章普查一个示意社群:74 个有往来的有向对只形成 15 条互惠边,并用两个模拟世界说明,风险比 6.09 与 2.69 都可能出自互惠边毫无作用的世界。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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
查看完整验算程序
# 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}
}

本书其他章节结论