数学重学 - 30 博弈论入门

数学重学
,

这是 数学重学路线图 阶段六的子页面

📌 前置知识：05-基础统计思维 中的概率基础即可

📌 博弈论不只是”数学游戏”，它是理解竞争、合作、策略设计的核心工具

博弈论是什么

一句话定义

研究理性决策者之间策略互动的数学

关键词：理性（每个人都想最大化自己的利益）、互动（你的选择影响我的结果）

比喻

下棋不只看自己的棋子，还要猜对方怎么走

博弈论就是把这种”我想他想我想他想…”的思考数学化

博弈的基本要素

参与者（Players）：谁在博弈

策略（Strategies）：每个参与者可以选什么

收益（Payoffs）：每种策略组合下每个人得到什么

囚徒困境 —— 博弈论最经典的模型

故事设定

两个嫌疑人 A 和 B 被分开审讯，不能沟通

每人可以选择：合作（沉默）或 背叛（招供）

规则：

双方都沉默 → 各判 1 年（证据不足）

一方招供一方沉默 → 招供的释放，沉默的判 10 年

双方都招供 → 各判 5 年

收益矩阵

1
2
3
4
5
6
7
8
9
┌─────────────┬──────────────────┬──────────────────┐
│             │  B 合作（沉默）    │  B 背叛（招供）    │
├─────────────┼──────────────────┼──────────────────┤
│ A 合作（沉默）│  A:-1, B:-1      │  A:-10, B:0      │
│             │  (双方小亏)        │  (A大亏, B全赢)    │
├─────────────┼──────────────────┼──────────────────┤
│ A 背叛（招供）│  A:0, B:-10      │  A:-5, B:-5      │
│             │  (A全赢, B大亏)    │  (双方中亏)        │
└─────────────┴──────────────────┴──────────────────┘

为什么”都背叛”是结局？

A 的思考：”不管 B 怎么选，我背叛都比合作好”

如果 B 合作：我背叛得 0，合作得 -1 → 背叛好

如果 B 背叛：我背叛得 -5，合作得 -10 → 背叛好

B 也一样 → 双方都选背叛 → (-5, -5)

但(-1, -1) 明明更好！这就是个体理性导致集体非最优

现实中的囚徒困境

价格战：两家公司都想降价抢客户 → 利润都下降

军备竞赛：两国都想多造武器 → 都花了巨资但安全感没增加

开源 vs 闭源：所有人都用不贡献 → 开源项目缺维护

广告投放：竞争对手加大投放 → 你也得加 → 成本上升利润不变

安全领域：每家公司都不想先花钱修漏洞（”又不一定被攻击”）

纳什均衡

定义

一组策略，使得没有任何参与者能通过单方面改变自己的策略来获得更好的结果

以约翰·纳什（电影《美丽心灵》的原型）命名

关键性质

纳什均衡可能不止一个

纳什均衡不一定是最优解（囚徒困境中双方背叛是纳什均衡但不是最优）

每个有限博弈至少存在一个纳什均衡（可能是混合策略的）

例子：交通选择

所有人开车 → 堵车，但没有一个人愿意单独换公交（公交也慢+不方便）

这就是纳什均衡：没人能通过单方面改变获益

但如果大家一起换公交，所有人都更快 → 需要政策干预（限号、收拥堵费）

例子：协调博弈

两个人约见面，选 A 咖啡馆或 B 咖啡馆

两个纳什均衡：都去 A 或都去 B

关键是协调，而不是对抗

零和博弈 vs 非零和博弈

零和博弈

一方的收益恰好等于另一方的损失，总和为零

例子：

象棋：一方赢 = 另一方输

扑克：赢的钱 = 别人输的钱

零和市场：市场份额总共 100%，你多我就少

安全中的零和思维：攻击者得手 = 防御者失败

非零和博弈

双方收益之和不固定，可以双赢或双输

例子：

商业合作：联合开发降低成本，双方获利

国际贸易：比较优势理论，各国专精各有所长

开源社区：贡献者和使用者都受益

安全中的非零和思维：漏洞披露合作（厂商修复+研究者声誉）

重复博弈 —— 时间改变一切

一次性 vs 重复

一次性博弈：背叛是理性的（囚徒困境）

重复博弈：今天背叛 → 明天对方报复 → 长期合作更有价值

比喻：你会欺骗只见一次的陌生人，但不会欺骗天天见面的邻居

以牙还牙策略 (Tit for Tat)

规则极简：

第一轮：合作

之后每轮：模仿对手上一轮的行为

特点：

善良：从不主动背叛

可报复：对方背叛一次，立刻回敬

可宽恕：对方回到合作，立刻恢复合作

简单：不需要复杂分析

Axelrod 锦标赛（1980年代经典实验）

征集各种策略让它们循环对战

结果：以牙还牙赢了！ 击败了所有复杂策略

教训：

不要贪心（主动背叛短期赢但长期输）

要有报复能力（否则被人欺负）

要能宽恕（否则陷入永久对抗）

简单透明的策略更容易建立信任

应用

互联网协议设计：TCP 拥塞控制就是一种”以牙还牙”

API 限流：渐进惩罚策略（第一次超限警告，重复则封禁）

信用体系：初始信任 + 根据行为调整

拍卖设计

四种经典拍卖

英式拍卖（公开递增）：

竞价者公开出价，价格逐步升高

最后一个出价的人赢得商品，支付自己的出价

最常见：eBay、传统拍卖行

荷兰式拍卖（公开递减）：

拍卖师从高价开始，逐步降低

第一个喊”停”的人赢得商品，支付当时的价格

用于鲜花、鱼市（需要快速成交的场景）

密封首价拍卖：

每人写下出价密封提交

最高出价者赢，支付自己的出价

Vickrey 拍卖（密封次价）：

每人写下出价密封提交

最高出价者赢，但只支付第二高的出价

优势：真实出价是最优策略（不需要猜别人出多少）

Google 广告就用类似机制

赢家的诅咒

赢得拍卖的人往往是对物品估价最高（可能过高）的人

结果：赢了拍卖但付了超过实际价值的钱

对策：在估值上打折后再出价

收益等价定理

在理论条件下（独立私人估值、风险中性），四种拍卖方式卖方的期望收入相同

实际中因为风险偏好、信息结构等原因会有差异

安全领域应用

攻防博弈

攻击者选择攻击向量（SQL注入、XSS、社工…）

防御者分配有限资源（WAF、培训、监控…）

这是一个不完全信息博弈：双方都不完全了解对方的策略

最优防御：混合策略（随机化防御，让攻击者无法预测）

安全投资 ROI

花多少钱防御才”够”？

Gordon-Loeb 模型：最优安全投资 ≤ 预期损失的 37%（1/e）

过度投资安全和投资不足安全都是不理性的

社会工程学

利用人的博弈心理弱点：

紧迫感：”你的账户马上被锁定！” → 压缩决策时间

权威感：”我是 IT 部门的” → 改变信任博弈的收益矩阵

互惠心理：先给你好处 → 你不好意思不配合

后端应用

动态定价算法

打车、机票的价格随供需实时变化

本质是商家和消费者之间的博弈

Uber surge pricing：高需求时涨价 → 吸引更多司机 → 达到均衡

资源竞争策略

乐观锁 vs 悲观锁就是博弈策略选择：

乐观锁：”赌冲突少” → 冲突少时高效

悲观锁：”赌冲突多” → 冲突多时避免浪费

选择取决于你对”对手”（其他请求）行为的判断

API 限流与惩罚机制

渐进惩罚（以牙还牙思维）：超限 → 警告 → 限速 → 短暂封禁 → 长期封禁

一刀切：超限直接封禁

渐进惩罚更公平但实现复杂，一刀切更简单但可能误伤

缓存击穿是囚徒困境

缓存过期的一瞬间，大量请求同时打到数据库

每个请求的”理性”选择：直接查数据库（最快得到结果）

但所有请求都这么做 → 数据库崩溃 → 大家都得不到结果

解决：互斥锁（只让一个请求重建缓存）、提前异步刷新

大数据应用

探索-利用权衡 (Explore vs Exploit)

也叫多臂老虎机问题 (MAB)

你面前有 10 台老虎机，每台回报率不同但你不知道

利用：一直拉目前看起来回报最高的（安全但可能错过更好的）

探索：尝试其他机器（短期可能亏但能发现更好的）

常用算法：

epsilon-贪心：90% 选最优，10% 随机探索

UCB（上置信界）：选”可能很好但不确定”的

Thompson 采样：用贝叶斯方法平衡

应用：推荐系统（推荐新内容 vs 推荐已知受欢迎的）、A/B 测试

广告竞价 (RTB)

你每次打开网页，后台几十家广告商在毫秒内竞价

本质是一个实时的 Vickrey 拍卖（第二高价格计费）

策略：如何出价使得 ROI 最大化？ → 博弈论最优出价策略

Python 代码实战

囚徒困境锦标赛模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import random
from itertools import combinations

# 收益矩阵：(我的收益, 对手收益)
# C=合作, D=背叛
PAYOFFS = {
('C', 'C'): (3, 3),   # 双方合作：各得3分
('C', 'D'): (0, 5),   # 我合作对方背叛：我0对方5
('D', 'C'): (5, 0),   # 我背叛对方合作：我5对方0
('D', 'D'): (1, 1),   # 双方背叛：各得1分
}

# --- 五种策略 ---
def always_cooperate(my_history, opp_history):
"""永远合作"""
return 'C'

def always_defect(my_history, opp_history):
"""永远背叛"""
return 'D'

def tit_for_tat(my_history, opp_history):
"""以牙还牙：第一轮合作，之后模仿对手上一轮"""
if not opp_history:
    return 'C'
return opp_history[-1]

def random_strategy(my_history, opp_history):
"""随机：50% 合作 50% 背叛"""
return random.choice(['C', 'D'])

def grudger(my_history, opp_history):
"""记仇：一旦对方背叛过一次，永远背叛"""
if 'D' in opp_history:
    return 'D'
return 'C'

def play_match(strategy1, strategy2, rounds=200):
"""两个策略对战若干轮，返回各自总分"""
history1, history2 = [], []
score1, score2 = 0, 0

for _ in range(rounds):
    move1 = strategy1(history1, history2)
    move2 = strategy2(history2, history1)
    
    s1, s2 = PAYOFFS[(move1, move2)]
    score1 += s1
    score2 += s2
    
    history1.append(move1)
    history2.append(move2)

return score1, score2

def tournament():
"""锦标赛：所有策略两两对战"""
strategies = {
    '永远合作': always_cooperate,
    '永远背叛': always_defect,
    '以牙还牙': tit_for_tat,
    '随机策略': random_strategy,
    '记仇策略': grudger,
}

total_scores = {name: 0 for name in strategies}

print("=== 囚徒困境锦标赛 (每场200轮) ===\n")

for (name1, s1), (name2, s2) in combinations(strategies.items(), 2):
    score1, score2 = play_match(s1, s2)
    total_scores[name1] += score1
    total_scores[name2] += score2
    print(f"  {name1} vs {name2}: {score1} - {score2}")

# 自己 vs 自己也要打
for name, s in strategies.items():
    score1, score2 = play_match(s, s)
    total_scores[name] += score1  # 只加一次（对手也是自己）

print(f"\n=== 最终排名 ===")
ranking = sorted(total_scores.items(), key=lambda x: -x[1])
for rank, (name, score) in enumerate(ranking, 1):
    bar = '█' * (score // 50)
    print(f"  {rank}. {name}: {score} {bar}")

tournament()

简单拍卖模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import random

def simulate_auctions(n_bidders=5, true_value=100, n_sims=10000):
"""
比较英式拍卖和 Vickrey 拍卖的结果
假设：每个竞拍者对物品有独立的私人估值 ~ N(true_value, 20)
"""
english_prices = []
vickrey_prices = []

for _ in range(n_sims):
    # 生成每个竞拍者的私人估值
    valuations = [random.gauss(true_value, 20) for _ in range(n_bidders)]
    sorted_vals = sorted(valuations, reverse=True)
    
    # 英式拍卖：价格升到第二高估值时，第二高的人退出
    # 赢家（估值最高的人）支付 ≈ 第二高的估值
    english_price = sorted_vals[1]
    english_prices.append(english_price)
    
    # Vickrey 拍卖：最高出价赢，支付第二高出价
    # 最优策略是真实出价，所以结果和英式拍卖理论上相同
    vickrey_price = sorted_vals[1]
    vickrey_prices.append(vickrey_price)

avg_english = sum(english_prices) / len(english_prices)
avg_vickrey = sum(vickrey_prices) / len(vickrey_prices)

print(f"=== 拍卖模拟 ({n_sims} 次, {n_bidders} 个竞拍者) ===")
print(f"物品真实价值: {true_value}")
print(f"英式拍卖  平均成交价: {avg_english:.2f}")
print(f"Vickrey   平均成交价: {avg_vickrey:.2f}")
print(f"→ 收益等价定理验证：两种拍卖平均成交价接近")

# 赢家的诅咒
winner_overpay = sum(
    max(v) - true_value
    for v in ([random.gauss(true_value, 20) for _ in range(n_bidders)]
               for _ in range(n_sims))
) / n_sims
print(f"\n赢家平均高估: {winner_overpay:.2f} (赢家的诅咒)")

simulate_auctions()

以牙还牙 vs 永远背叛 vs 随机 对战可视化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# 如果有 matplotlib 可以画图，否则用文本可视化

def text_visualize_match(strategy1, strategy2, name1, name2, rounds=30):
"""文本可视化两个策略的对战过程"""
history1, history2 = [], []
scores1, scores2 = [], []
cum1, cum2 = 0, 0

for r in range(rounds):
    m1 = strategy1(history1, history2)
    m2 = strategy2(history2, history1)
    s1, s2 = PAYOFFS[(m1, m2)]
    cum1 += s1
    cum2 += s2
    scores1.append(cum1)
    scores2.append(cum2)
    history1.append(m1)
    history2.append(m2)

print(f"\n{'='*50}")
print(f"{name1} vs {name2} ({rounds} 轮)")
print(f"{'='*50}")

# 显示行为序列
print(f"{name1}: {''.join(history1)}")
print(f"{name2}: {''.join(history2)}")
print(f"(C=合作, D=背叛)")

# 文本折线图
max_score = max(max(scores1), max(scores2))
chart_height = 10
for row in range(chart_height, 0, -1):
    threshold = max_score * row / chart_height
    line = ""
    for r in range(rounds):
        c1 = scores1[r] >= threshold
        c2 = scores2[r] >= threshold
        if c1 and c2:
            line += "X"
        elif c1:
            line += "1"
        elif c2:
            line += "2"
        else:
            line += "."
    print(f"  {threshold:5.0f}|{line}")
print(f"       {''.join(str(i % 10) for i in range(rounds))}")
print(f"  最终: {name1}={cum1}, {name2}={cum2}")
winner = name1 if cum1 > cum2 else (name2 if cum2 > cum1 else "平局")
print(f"  赢家: {winner}")

# 需要从上面的锦标赛代码导入策略函数和 PAYOFFS
# 这里假设已经定义好了
text_visualize_match(tit_for_tat, always_defect, "以牙还牙", "永远背叛")
text_visualize_match(tit_for_tat, random_strategy, "以牙还牙", "随机策略")
text_visualize_match(always_defect, random_strategy, "永远背叛", "随机策略")

练习题

题1：找纳什均衡

两家公司选择定价策略：高价(H)或低价(L)

1
2
3
4
5
6
7
┌───────┬──────────┬──────────┐
│       │ 公司B: H  │ 公司B: L  │
├───────┼──────────┼──────────┤
│公司A:H│  (5, 5)  │  (1, 7)  │
├───────┼──────────┼──────────┤
│公司A:L│  (7, 1)  │  (3, 3)  │
└───────┴──────────┴──────────┘

找出纳什均衡，并判断这是不是囚徒困境
答案
检查每个格子：

(H,H): A 换到 L 得 7>5 → A 想换 → 不是均衡

(H,L): A 换到 L 得 3<1? 不对，得 3>1 → A 想换

(L,H): B 换到 L 得 3>1 → B 想换

(L,L): A 换到 H 得 1<3 不想换，B 换到 H 得 1<3 不想换 → (L,L) 是纳什均衡

这就是囚徒困境：(H,H)=(5,5) 对双方都更好，但均衡点在 (L,L)=(3,3)

题2：策略设计

你要设计一个 API 限流系统。用户超过限额后你有三种惩罚策略：

a) 直接封禁 1 小时

b) 降速（请求延迟增加），5分钟后恢复

c) 渐进惩罚：第1次警告，第2次降速，第3次封禁1小时

从博弈论角度分析各策略的优缺点，推荐哪个？
答案
a) 类似”永远背叛”：惩罚重但不可宽恕，可能误伤正常突发流量

b) 类似”以牙还牙”：有惩罚但可恢复，对偶然超限友好

c) 最接近”以牙还牙+记忆”：善良(先警告)、可报复(升级惩罚)、可宽恕(恢复后重置)

推荐 c)，因为它区分了”偶尔失误”和”恶意滥用”

题3：MAB 问题

你有3个推荐算法，测试10次的点击率分别是：

A: [0.3, 0.2, 0.4, 0.1, 0.3, 0.2, 0.3, 0.4, 0.2, 0.3] 平均 0.27

B: [0.5, 0.6, 0.4, 0.5, 0.6] 平均 0.52（只测了5次）

C: [0.8, 0.1] 平均 0.45（只测了2次）

用 epsilon=0.1 贪心策略，下一次应该选哪个？为什么 C 值得再探索？
答案
epsilon=0.1 意味着 90% 选当前最优，10% 随机探索

当前平均最优是 B(0.52) → 90% 概率选 B

C 虽然平均 0.45，但只测了 2 次，方差很大

C 可能真实点击率很高（那个 0.8 可能才是真实水平）

UCB 策略会给 C 更高的优先级：因为它的不确定性最大

题4：缓存击穿博弈

用 Python 模拟：100 个并发请求，缓存刚过期，每个请求可以选择”查缓存”或”直接查DB”
提示

1
2
3
4
5
6
7
8
9
10
11
12
13
import random

n_requests = 100
db_capacity = 10  # DB 最多同时处理 10 个请求

# 没有锁的情况
db_queries = n_requests  # 所有请求都打到 DB
success = min(db_queries, db_capacity)
print(f"无锁: {db_queries} 请求打到DB, 成功 {success}, 失败 {n_requests - success}")

# 有互斥锁
db_queries = 1  # 只有一个请求重建缓存
print(f"有锁: {db_queries} 请求打到DB, 其余 {n_requests-1} 等待缓存重建")

题5：编程挑战

实现一个 Thompson 采样算法来解决 3 臂老虎机问题：

3 台老虎机的真实获奖概率分别是 0.3, 0.5, 0.7（你不知道）

模拟 1000 次选择，统计每台被选次数和累计奖励
提示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import random

true_probs = [0.3, 0.5, 0.7]
# Beta 分布参数
alpha = [1, 1, 1]  # 成功次数 + 1
beta_param = [1, 1, 1]   # 失败次数 + 1
pulls = [0, 0, 0]
rewards = [0, 0, 0]

for t in range(1000):
# Thompson 采样：从每台机器的 Beta 分布中采样
samples = [random.betavariate(alpha[i], beta_param[i]) for i in range(3)]
choice = samples.index(max(samples))

# 拉选中的老虎机
reward = 1 if random.random() < true_probs[choice] else 0
pulls[choice] += 1
rewards[choice] += reward

# 更新 Beta 分布
alpha[choice] += reward
beta_param[choice] += (1 - reward)

for i in range(3):
print(f"老虎机{i}: 真实概率={true_probs[i]}, "
      f"被选{pulls[i]}次, 奖励{rewards[i]}")
上一章 目录 下一章
29-费米估算实战 数学重学路线图 31-数学建模思维