站内独立游戏平衡与经济设计 讲平衡靠的是人肉评审：数值怎么调、版本怎么迭代，全是经验判断，没有一句「这条策略被那条压住」的机器判据。本节把它做成算法——给定一张得分矩阵，怎么在可接受的时间内把所有被支配策略找出来，以及这个代价的上界长什么样。检测算法是支配修复（2.3）与均衡求解（第 3 章）共同的底座。
2.2 检测算法与复杂度
2.1 定义了「严格支配」与「弱支配」，但没有说怎么算。给定 |S| 条策略、|Ω| 个环境，最直接的做法是把每个有序对 (s,t) 都查一遍——这就是全对枚举。它有明显的浪费：既然 s ≻ t 蕴含 sum(s) > sum(t)，那么行和更小的对根本不必查。再加一层，被支配策略可以删掉后再找，因为删掉它们不会让别的策略失去支配关系——这就是迭代删除（IESDS）。
| 实现 | 做什么 | 关键点 |
|---|---|---|
| naive | 每个有序对逐环境比到出现反例 | 正确但做满 |
| pruned | 先算行和，只查 sum(s) > sum(t) 的对 | 支配的必要条件，剪枝合法（不丢解） |
| iesds | 删掉被支配策略后重查，直到不动点 | 与全对被支配集等价；删掉的不影响最优解 |
复杂度上界很干脆：有序对数是 |S|·(|S|−1)，每对最多比 |Ω| 个环境，所以元素比较次数 ≤ |S|·(|S|−1)·|Ω|。提前退出只会在某些对上少比几次，绝不会超过这个上界。下面的脚本把三种实现跑在同一张矩阵上，验证结论一致、并数出各自花了多少次比较。
S 层：三种等价实现
脚本复用 2.1 的 payoff_matrix 建矩阵，再分别跑 naive / pruned / iesds，比对结论与代价。全整数，无浮点，无随机。
#!/usr/bin/env python3
# file: sim/gd_play_02_detection.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/gd_play_02_detection.py
"""卷二 2.2 检测算法与复杂度（S 层）。
三种等价实现，比较它们做的事：
naive 全对枚举 + 逐元素提前退出：对每个有序对 (i,j) 从头比到出现反例
pruned 先算每行得分和，只检查 sum(s) > sum(t) 的对（支配的必要条件，剪枝合法）
iesds 迭代删除严格被支配策略，直到不动点
三者的严格支配对必须**逐字一致**；差别只在比较次数。
复杂度上界：元素比较 ≤ |S|·(|S|−1)·|Ω|（有序对 × 环境数）。
产出 out/play02_detection.csv + out/play02_detection.json。全整数，无浮点，无 random。
"""
from __future__ import annotations
import json
import os
import sys
import time
HERE = os.path.dirname(os.path.abspath(__file__))
ROOT = os.path.dirname(HERE)
OUT = os.path.join(ROOT, "out")
CONFIG = os.path.join(ROOT, "config/gd_play_02_dominance.json")
sys.path.insert(0, HERE)
from gd_play_02_dominance import payoff_matrix # noqa: E402
def naive(rows):
"""全对枚举 + 提前退出；返回 (严格对集合, 元素比较次数, 检查的对数)。"""
n = len(rows)
pairs, cmps, checks = set(), 0, 0
for i in range(n):
for j in range(n):
if i == j:
continue
checks += 1
ok = True
for a, b in zip(rows[i], rows[j]):
cmps += 1
if a <= b:
ok = False
break
if ok:
pairs.add((i, j))
return pairs, cmps, checks
def pruned(rows):
"""先按行和排序，只检查 sum(i) > sum(j) 的有序对（支配的必要条件）。"""
n = len(rows)
sums = [sum(r) for r in rows]
pairs, cmps, checks, skipped = set(), 0, 0, 0
for i in range(n):
for j in range(n):
if i == j:
continue
if sums[i] <= sums[j]:
skipped += 1
continue
checks += 1
ok = True
for a, b in zip(rows[i], rows[j]):
cmps += 1
if a <= b:
ok = False
break
if ok:
pairs.add((i, j))
return pairs, cmps, checks, skipped
def iesds(rows):
"""迭代删除严格被支配策略，返回 (存活下标, 每轮被删集合)。"""
alive, rounds = list(range(len(rows))), []
while True:
dominated = {t for t in alive for s in alive
if s != t and all(a > b for a, b in zip(rows[s], rows[t]))}
if not dominated:
break
rounds.append(sorted(dominated))
alive = [i for i in alive if i not in dominated]
return alive, rounds
def main() -> int:
t0 = time.perf_counter_ns()
with open(CONFIG, encoding="utf-8") as f:
cfg = json.load(f)
names, rows, _ = payoff_matrix(__import__("ashlib").load_spec(), cfg, cfg["seeds"])
n, m = len(rows), len(rows[0])
bound = n * (n - 1) * m
npairs, ncmps, nchecks = naive(rows)
ppairs, pcmps, pchecks, skipped = pruned(rows)
alive, rounds = iesds(rows)
same = npairs == ppairs
elim = {j for _, j in npairs}
survive_ok = set(alive) == set(range(n)) - elim
ashlib = __import__("ashlib")
ashlib.write_csv(os.path.join(OUT, "play02_detection.csv"),
["impl", "pairChecks", "elemCompares", "bound", "strictPairs"],
[["naive", nchecks, ncmps, bound, len(npairs)],
["pruned", pchecks, pcmps, bound, len(ppairs)]])
report = {"id": "gd_play_02_detection", "strategies": n, "envs": m, "bound": bound,
"naive": {"pairChecks": nchecks, "elemCompares": ncmps, "strictPairs": len(npairs)},
"pruned": {"pairChecks": pchecks, "elemCompares": pcmps,
"skippedPairs": skipped, "strictPairs": len(ppairs)},
"iesds": {"rounds": rounds, "survivors": [names[i] for i in alive]},
"agree": same, "surviveMatches": survive_ok,
"elapsedMs": (time.perf_counter_ns() - t0) // 1000000}
with open(os.path.join(OUT, "play02_detection.json"), "w", encoding="utf-8") as f:
json.dump(report, f, ensure_ascii=False, indent=2, sort_keys=True)
f.write("\n")
print(f"|S|={n} |Ω|={m} 复杂度上界 |S|(|S|-1)|Ω| = {bound} 次元素比较")
print(f"{'实现':<8}{'对检查':>8}{'元素比较':>10}{'严格对':>7}")
print(f"{'naive':<8}{nchecks:>8}{ncmps:>10}{len(npairs):>7}")
print(f"{'pruned':<8}{pchecks:>8}{pcmps:>10}{len(ppairs):>7} （剪掉 {skipped} 对，占 {skipped * 1000 // nchecks}‰）")
print(f"两实现严格对一致={same}")
print(f"IESDS 轮次={rounds} 存活={[names[i] for i in alive]} 与全对被支配集一致={survive_ok}")
print("严格对: " + " ".join(f"{names[i]}≻{names[j]}" for i, j in sorted(npairs)))
print(f"naive 用了上界的 {ncmps * 1000 // bound}‰；pruned 用了上界的 {pcmps * 1000 // bound}‰")
print(f"elapsed={report['elapsedMs']} ms")
print("wrote out/play02_detection.csv out/play02_detection.json")
return 0 if (same and survive_ok) else 1
if __name__ == "__main__":
sys.exit(main())
本机实跑 /opt/homebrew/bin/python3 sim/gd_play_02_detection.py：
|S|=5 |Ω|=16 复杂度上界 |S|(|S|-1)|Ω| = 320 次元素比较
实现 对检查 元素比较 严格对
naive 20 111 5
pruned 10 99 5 （剪掉 10 对，占 500‰）
两实现严格对一致=True
IESDS 轮次=[[3, 4]] 存活=['slot0', 'slot1', 'slot2'] 与全对被支配集一致=True
严格对: slot0≻slot3 slot0≻slot4 slot1≻slot4 slot2≻slot4 slot3≻slot4
naive 用了上界的 346‰；pruned 用了上界的 309‰
elapsed=15 ms
wrote out/play02_detection.csv out/play02_detection.json
判读：一致，但代价差一倍
三处读数各有含义：
| 读数 | 值 | 说明 |
|---|---|---|
两实现严格对一致 | True | naive 与 pruned 找到的 5 条严格对完全相同，剪枝没丢解 |
IESDS 轮次 | [[3, 4]] | 一轮就把 slot3、slot4 全删掉，剩下 slot0/1/2 互不支配 |
与全对被支配集一致 | True | 迭代删除的存活集 = 全集减去被支配集，等价 |
对检查 | 20 → 10 | 剪枝把有序对从 20 砍到 10（行和相等或更小的直接跳过） |
元素比较 | 111 → 99 | 省得没对检查那么多——被保留的对仍要逐环境比完 |
naive 用掉上界的 346‰、pruned 309‰，都远低于 320 的上界——因为提前退出在很多对上很早就撞见反例。真正值得记住的是上界的形式：它随策略数的平方增长。|S| 翻倍，代价翻四倍；这就是下一节「何时改用采样」的由来。
B 层：规模基准与「何时改用采样」
上界既然是平方级的，就必须知道它在多大尺寸上还跑得动。脚本用自实现 PRNG 造一批合成整数矩阵，实测比较次数与上界比对，并在上界超过阈值时提示改用采样。
#!/usr/bin/env python3
# file: sim/gd_play_02_detection_bench.py
# tier: B
# verify: /opt/homebrew/bin/python3 sim/gd_play_02_detection_bench.py
"""卷二 2.2 检测复杂度的规模基准（B 层）：实测元素比较是否守住 |S|(|S|−1)|Ω|。
对若干 (|S|, |Ω|) 生成**合成整数得分矩阵**（ashlib.rng_next 播种，禁 random 模块），
跑与 2.2 S 层同口径的 naive 检测（直接复用），记录元素比较次数并与理论上界比对：
实测 ≤ 上界 → 符合；实测 > 上界 → 判据自身有 bug（软告警，不硬失败）。
再给一条「何时改用采样」的判据：上界超过阈值就应放弃全枚举，改采样估计支配缺失度。
永远 exit 0：B 档软告警不硬失败。产出 out/play02_bench.json。
"""
from __future__ import annotations
import json
import os
import sys
import time
HERE = os.path.dirname(os.path.abspath(__file__))
ROOT = os.path.dirname(HERE)
OUT = os.path.join(ROOT, "out")
sys.path.insert(0, HERE)
import ashlib # noqa: E402
from gd_play_02_detection import naive # noqa: E402
SAMPLE_THRESHOLD = 1_000_000
GRID = [(4, 8), (8, 16), (16, 16), (32, 32), (64, 32), (128, 64), (256, 64)]
def synth_matrix(n, m, seed):
"""合成 n×m 整数得分矩阵：值域 [0,1000)，用自实现 PRNG。"""
st = seed % ashlib.RNG_MOD or 1
rows = []
for _ in range(n):
row = []
for _ in range(m):
st = ashlib.rng_next(st)
row.append(st % 1000)
rows.append(row)
return rows
def main() -> int:
t0 = time.perf_counter_ns()
rows_out, warnings = [], []
for n, m in GRID:
pairs, cmps, _ = naive(synth_matrix(n, m, 20261001 + n * 100 + m))
bound = n * (n - 1) * m
ok = cmps <= bound
if not ok:
warnings.append({"code": "BOUND_VIOLATED", "severity": "soft", "n": n, "m": m,
"measured": cmps, "bound": bound,
"message": f"|S|={n} |Ω|={m} 实测 {cmps} > 上界 {bound}，判据自身可疑"})
if bound > SAMPLE_THRESHOLD:
warnings.append({"code": "SHOULD_SAMPLE", "severity": "soft", "n": n, "m": m,
"bound": bound,
"message": f"|S|={n} |Ω|={m} 上界 {bound} 已超 {SAMPLE_THRESHOLD}，"
f"应改用采样估计支配缺失度"})
rows_out.append({"strategies": n, "envs": m, "bound": bound, "elemCompares": cmps,
"strictPairs": len(pairs), "ratioPermille": cmps * 1000 // bound,
"withinBound": ok})
report = {"id": "gd_play_02_detection_bench", "tier": "B", "hardFail": False,
"note": "B 档软告警：实测比较次数须 ≤ |S|(|S|-1)|Ω|；超阈值提示改用采样",
"sampleThreshold": SAMPLE_THRESHOLD, "rows": rows_out, "warnings": warnings,
"elapsedMs": (time.perf_counter_ns() - t0) // 1000000}
os.makedirs(OUT, exist_ok=True)
with open(os.path.join(OUT, "play02_bench.json"), "w", encoding="utf-8") as f:
json.dump(report, f, ensure_ascii=False, indent=2, sort_keys=True)
f.write("\n")
print(f"{'|S|':>5}{'|Ω|':>6}{'上界':>12}{'实测比较':>12}{'占比‰':>7}{'严格对':>7} 守界")
for r in rows_out:
print(f"{r['strategies']:>5}{r['envs']:>6}{r['bound']:>12}{r['elemCompares']:>12}"
f"{r['ratioPermille']:>7}{r['strictPairs']:>7} {'是' if r['withinBound'] else '否'}")
for w in warnings:
print(f"SOFT WARN {w['code']}: {w['message']}")
print(f"allWithinBound={all(r['withinBound'] for r in rows_out)} "
f"warnings={len(warnings)} hardFail=false elapsed={report['elapsedMs']} ms")
print("wrote out/play02_bench.json")
return 0
if __name__ == "__main__":
sys.exit(main())
本机实跑 /opt/homebrew/bin/python3 sim/gd_play_02_detection_bench.py：
|S| |Ω| 上界 实测比较 占比‰ 严格对 守界
4 8 96 22 229 0 是
8 16 896 94 104 0 是
16 16 3840 445 115 0 是
32 32 31744 1961 61 0 是
64 32 129024 8127 62 0 是
128 64 1040384 32171 30 0 是
256 64 4177920 133293 31 0 是
SOFT WARN SHOULD_SAMPLE: |S|=128 |Ω|=64 上界 1040384 已超 1000000，应改用采样估计支配缺失度
SOFT WARN SHOULD_SAMPLE: |S|=256 |Ω|=64 上界 4177920 已超 1000000，应改用采样估计支配缺失度
allWithinBound=True warnings=2 hardFail=false elapsed=31 ms
wrote out/play02_bench.json
allWithinBound=True：七个尺寸上实测比较次数全都守住上界——上界不是估计，是硬约束。SHOULD_SAMPLE 是软告警：|S|=128、|Ω|=64 时上界已过 10^6，纯枚举开始变慢，应换成采样估计「支配缺失度」（1 − 被支配策略占比）这类代理指标。B 层按纪律软告警不硬失败：它给的是「该换算法了」的提示，不是「算法错了」的判决。
自检表
| 检查项 | 合格标准 |
|---|---|
| 多实现互证 | naive / pruned / iesds 的严格对逐字一致 |
| 剪枝合法 | pruned 只跳过 sum(s) ≤ sum(t) 的对，不丢解 |
| 上界明确 | 元素比较 ≤ |
| 换算法有据 | 上界超阈值时提示改用采样，且给出替代指标 |
| 软告警不硬失败 | B 层永远 exit 0，只提示规模风险 |
算法有了，2.1 的结论（slot4 被彻底支配、slot0/1/2 互不支配）就成了可复算的产物。下一节处理最实际的问题：当一条策略确实被支配、而它本该是个有意义的选择时，怎么修。
阅读导航：上一节：2.1 支配关系：严格与弱 · 下一节：2.3 支配策略的修复 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。