附录 A · 速查
这是查阅页,不用从头读完。 可用浏览器查找,也可按当前问题进入:
每组先写模型范围,再给结论。需要推导时点回原章,不靠一句口诀补全所有前提。
🗺️ 一、哪个概念在哪一章
| 概念 | 章 |
|---|---|
| 命题逻辑 · 真值表 · 恒真/可满足 | 03 |
| 模型集 · 语义蕴含 ⊨ · 可靠性/完备性 · 爆炸原理 | 04 |
| NNF · CNF · 分辨率 · 反证法 · SAT | 05 |
| 一阶逻辑 · 量词顺序 · Skolem 化 · 合一(MGU) · 不可判定 | 06 |
| 偏好关系 · 完全性/传递性 · 钱泵 · 序数效用 | 07 |
| 彩票 · 连续性/独立性 · vNM 定理 · 风险态度 | 08 |
| 正常形博弈 · 囚徒困境/性别之争/石头剪刀布 · 帕累托最优 | 09 |
| 严格支配/弱支配 · 占优策略 · IESDS | 10 |
| 最佳响应 · 纳什均衡 · Nash 存在性 · PPAD · 强 NE | 11 |
| 混合策略 · 支撑集 · 无差异原理 · 支撑枚举 | 12 |
| 安全水平 · maximin · 零和 · 极大极小定理 · 鞍点 | 13 |
| 博弈树 · 树上的策略 · 空威胁 · SPNE · 逆向归纳 · Zermelo | 14 |
| 拥塞博弈 · Rosenthal 势函数 · 最佳响应动态 · Braess · PoA | 15 |
| 机制设计框架 · 策略防伪 SP · IR · 效率 · 一价/二价拍卖 | 16 |
| 阻挡对 · 稳定匹配 · DA/SPDA/CPDA · 可达搭档 · 乡村医院定理 · Roth 1982 | 17 |
| 住房市场 · 核心(阻挡联盟版) · TTC · Ma 1994 · 肾脏交换 | 18 |
| 可加估值 · USW/ESW/Leximin/Nash 福利 · EF / EF1 / PROP / PROP1 / MMS | 19 |
| Round-Robin · 嫉妒图 · MNW ⟹ EF1+PO · ½-MMS | 20 |
| 准线性效用 · 可无嫉妒化 · 带权嫉妒图/正权环 · RSD / PS · SD · AW | 21 |
| TU 博弈 · 简单博弈/WVG · Core · 超额 · 否决者 · Least Core · Nucleolus | 22 |
| Shapley 值 · 四条公理 · 凸博弈 · Banzhaf · 图博弈/MC-nets · SHAP | 23 |
| SWF/SCF/SCC/SDS · 位置计分规则 · Borda · IRV · 两轮决选 | 24 |
| 多数图 · Condorcet 赢家/悖论 · Fishburn · Copeland/TC/UC/Banks · Kemeny | 25 |
| 公理(匿名/中立/单调/IIA/非独裁) · Arrow · Gibbard–Satterthwaite · 单峰 · 随机独裁 | 26 |
| 五个基础项目与两个挑战(扩展任务另列依赖) | 27 |
📖 二、定义速查:先看适用范围
单人决策(07–08)
- 理性偏好:完全性保证任两项可比较;传递性保证排序一致。这里“理性”不是道德评价。
- 效用表示:$x\succsim y$ 当且仅当 $u(x)\ge u(y)$。在一般无限结果空间中,存在性还需条件。
- 序数效用:只表示排序,任意严格递增变换表示同一偏好。
- 彩票:结果集上的概率分布。
- 独立性公理:以相同比例把两个彩票分别与同一个彩票混合,不改变原来的偏好比较。
- vNM 效用:标准彩票空间上满足理性、连续、独立公理时,可用期望效用表示;唯一到正仿射变换 $\alpha u+\beta$,其中 $\alpha>0$。
- 风险厌恶:在对金额的递增期望效用模型中,偏好确定均值而非同均值彩票,对应效用函数凹;不是任意序数效用“看起来弯”就能判风险态度。
- 确定等价:效用等于彩票期望效用的确定金额。递增连续且相关期望存在时可据此求解。
非合作博弈(09–15)
出处:正常形至拥塞博弈。以下以有限行动集、收益最大化为主;拥塞段改用成本最小化。
行动、偏离与均衡
- 正常形博弈:$G=(N,(A_i),(u_i))$;收益 $u_i$ 取决于全体行动组合,不只取决于自己的行动。正常形是一种表示法,不保证真实过程同时发生。
- 帕累托支配:一个可行结果使每个人不差、至少一人严格更好。
- 帕累托最优:没有另一个可行结果帕累托支配它。必须先指定可行集;它不单独保证公平。
- 严格支配:固定被比较的两个策略,对每一种对手策略,前者收益都严格更高;支配者也可能是混合策略。
- 弱支配:每一种对手策略下都不差,且至少一种严格更好。
- 占优策略:相对于其他所有自身策略都占优;需说明严格还是弱占优。
- 最佳响应:固定对手策略后,使自己收益最大的策略,可能不止一个。
- 纳什均衡 NE:每个人都在最佳响应,没人能单独改变策略获得严格改善。
- 强纳什均衡:不存在一个联盟共同偏离,使联盟内每个人都严格改善;一般不保证存在。
随机策略、保底与博弈树
- 混合策略 / 支撑集:行动上的概率分布;支撑是概率严格大于零的行动集合。
- 无差异原理:在混合 NE 中,支撑内行动都达到同一最高期望收益,支撑外不能更高;配合合法概率也是最佳响应的判据。
- 安全水平 / maximin:自己先选策略,使对手最不利应对下的收益尽可能高。纯策略与混合策略的保底可能不同,不要求对手真的恶意。
- 零和博弈:本页指二人、每个行动组合的收益和为零。
- 博弈的值:有限二人零和博弈在允许混合策略时,maximin 与 minimax 的共同值。
- 鞍点:纯策略层面的 maximin 与 minimax 已相等,对应纯策略均衡。
- 树上的策略:给自己的每个信息集指定行动;完美信息时信息集是单节点,没走到的节点也要规定。
- 子博弈:一般扩展式中必须从单点信息集开始,且不切断信息集。完美信息树中的完整子树满足该条件。
- SPNE:在每个子博弈上的限制都是 NE。
- 空威胁:到达对应决策处时不符合后续理性的威胁,不能用它解释子博弈完美结果。
拥塞与社会成本
- 拥塞博弈:本页基本模型中,每个玩家选一组资源;资源成本仅依赖使用人数,玩家成本为所选资源成本之和。
- 势函数:用一个标量记录单人改变。在本页成本模型,严格改善使势下降;Rosenthal 的精确势还满足“势的变化 = 改动者成本变化”。收益模型常用上升约定。
- Price of Anarchy(PoA):在同一实例、指定的均衡集合中,最坏均衡社会成本与集中最优成本之比。通常要求最优成本为正。
机制设计 · 匹配 · 分配(16–21)
出处:机制设计、稳定匹配、TTC、公平判据、算法、支付与随机分配。
报告、匹配与禀赋
- 机制:规定参与者能报告什么,以及报告如何决定结果;有些机制还规定支付。
- 策略防伪 SP:在规定的报告域内,固定别人报告,如实报告是弱占优策略,单独谎报不能改善结果。
- 个体理性 IR:参与结果不比规定的退出选项差;先明确初始禀赋或不参与收益。
- 阻挡对:一对未匹配对象愿意相互改配。严格一对一、全部可接受时,双方都严格偏好对方胜过当前搭档;有空位、不可接受对象时须补相应条件。
- 稳定匹配:匹配可行、个体理性且没有阻挡对;不是人人拿到第一志愿。
- 可达搭档:在某个稳定匹配中能与自己配对的人;提案方最优只在这些搭档里比较。
- 住房市场的强核心:联盟仅用自己最初拥有的房屋,不能重分配到“所有成员不差、至少一人严格更好”。严格偏好、一人一房下 TTC 给出唯一强核心分配;仅排除全员严格改善的弱核心未必唯一。
不可分物品:默认非负可加估值、完整分配
- 可加估值:$v_i(S)=\sum_{g\in S}v_i(g)$,空集价值为零。
- USW / ESW / Nash 福利:分别看效用总和、最小效用、效用乘积;比较不同人数时,Nash 福利常用几何平均。
- Leximin:把每人效用从小到大排,再比较字典序。跨人比较需先说明效用刻度。
- EF(无嫉妒):每个人按自己的估值看,自己的整堆不比任何别人的整堆差。
- EF1:对每一对人,要么本来不嫉妒,要么能从对方非空整堆中去掉一件,使自己不再嫉妒。空堆不能要求“存在一件”。
- PROP(比例性):每人至少得到自己眼中全部物品总值的 $1/n$。
- PROP1:要么已经达到 PROP,要么能从自己整堆之外添一件达到它;不是重新给一件自己已有的物品。
- MMS:自己把物品完整分成 $n$ 堆(允许空堆),比较最差那堆,再选择能使最差堆最好的分法。
- 嫉妒图:人是节点,$i\to j$ 表示 $i$ 按自己的估值更喜欢 $j$ 的整堆。无边等价于 EF。
支付与抽签:不要与实物份额混用
- 准线性效用:本页 $p_j$ 表示补贴,比较另一人的完整结果时为 $v_i(X_j)+p_j$。若符号表示付款,方向要改成减号。
- 可无嫉妒化:对固定实物分配,存在一组允许的支付,使包含支付的结果无嫉妒。
- 重分配稳定:只交换当前整堆的所有者,不能提高总估值;这里效用刻度须可加总。
- 随机分配:标准 $n$ 人 $n$ 物、每人一件时,用非负双随机矩阵表示,每行、每列之和均为 1。
- SD(一阶随机支配):按当前这个人的真实排序逐层累计,$p$ 的每个前缀概率都不低于 $q$;两行也可能互不可比。
合作博弈(22–23)
出处:核心与核仁、Shapley 与表示法。以下为有限可转移效用(TU)博弈。
- TU 博弈:$(N,v)$,联盟 $S$ 的值为 $v(S)$,默认 $v(\varnothing)=0$。
- 简单博弈:值只有 0/1、单调,且大联盟值为 1;值为 1 的联盟叫获胜联盟。
- 加权投票博弈 WVG:$[q;w_1,\ldots,w_n]$;非负权重和达到配额 $q$ 就获胜。不是所有简单博弈都能这样表示。
- 效率(分配):全体所得之和等于 $v(N)$。
- 核心 Core:效率成立,且每个联盟获得的总和不少于它独立合作的值。
- 超额 / 联盟余额:本页沿用 $e(x,S)=x(S)-v(S)$,越大越满意;不少文献用相反号。
- 否决者:任何不含他的人群都不能获胜。
- Least Core:本页沿用第 22 章的非负松弛版:保持效率和个人单干底线,最小化允许的联盟亏欠 $\varepsilon\ge0$;先要求该分配域非空。
- Nucleolus(核仁):在效率且个体理性的分配域 $I(v)$ 中,把联盟余额升序排序,取字典序最大的分配。只要求效率时通常称为前核仁。
- Shapley 值:对所有加入顺序等权平均边际贡献。
- 凸博弈:对 $B\subseteq A$、$i\notin A$,加入大联盟的边际贡献不小于加入小联盟;不能漏掉 $i\notin A$。
- Banzhaf 指数:先数关键次数 $\eta_i$。绝对指数除以 $2^{n-1}$,总和未必为 1;归一化指数除以所有人的关键次数之和,总和为 1。
社会选择(24–26)
出处:投票规则、多数图、公理与不可能性。默认有限候选集、选民报告严格完整排序。
- 偏好轮廓:所有人的偏好排序组成的输入。
- SWF / SCF / SCC / SDS:分别输出集体排序、一个赢家、非空候选子集、候选项上的概率分布。
- 位置计分规则 PSR:由非增、非恒定的计分向量决定;并列时还要说明输出集合还是固定破平规则。
- 多数关系:把 $x$ 排在 $y$ 前的人严格更多,才画 $x\to y$。
- 锦标赛:任意两个不同节点之间恰有一条有向边。奇数选民、严格完整选票保证多数图无平票。
- Condorcet 赢家:逐一严格击败其他所有候选项;存在时唯一,但可能不存在。
- Condorcet 一致:有这样的全胜者时就选它。
- 覆盖:$x$ 击败 $y$,而且 $y$ 击败的每个对象也被 $x$ 击败。
- 匿名性 / 中立性:交换选民名字不改结果;交换候选项名字,结果相应换名。
- 单调性:固定其他候选项的相对顺序,只把当选者往上提,它仍应当选。需明确并列处理。
- IIA:SWF 对 $a,b$ 的社会排序只由各人对这两项的比较决定;不要直接套成“删去候选项后赢家不变”。
- 满射(onto):每个候选项至少在一个合法轮廓中能当选。
- 单峰偏好:有共同轴,每人从自己的峰向同一侧移动时偏好递减;不要求左右等距离同样喜欢,也不要求由欧氏距离决定。
✏️ 三、手算方法:每次只选一项
先按小标题找你正在做的题。每项保留步骤和检验条件;它们不是需要从头勾完的任务列表。
🃏 vNM 效用标定
📍 出处:08
- 把每条无差异关系写成期望效用相等的方程
- 整理出一条把三个 $u$ 串起来的等式
- 做差判断排序;例如已知 $u(a)>u(b)$,且得到 $u(c)-u(a)=3(u(a)-u(b))$,才能推出 $c\succ a\succ b$
- ⭐ 最好的定 1、最差的定 0(正仿射变换恰好 2 个自由度),代回解出中间那个
- 验:把数字代回原式两边算一遍,且排序要和第 3 步一致
🃏 圈最佳响应,找纯策略 NE
📍 出处:11
- 每格写「行玩家收益, 列玩家收益」,顺序固定
- 逐列看:圈出这一列里第一个数最大的那格
- 逐行看:圈出这一行里第二个数最大的那格
- 两个数都被圈的格子 = 纯策略 NE
- 一个双圈都没有 → 没有纯 NE,去混合
⚠️ 并列最大要全圈 —— 漏圈并列值 = 漏掉整个均衡,手算最常见的错。
🃏 2×2 混合 NE(无差异法)
📍 出处:12
- 先用圈法找纯 NE,顺手删掉严格劣势的动作
- ⭐ 令列玩家对两个动作无差异,解出 $p$(行玩家的概率)—— 用每格第二个数
- ⭐ 令行玩家无差异,解出 $q$(列玩家的概率)—— 用每格第一个数
- 验 $p,q$ 是否严格在 $(0,1)$ 内,再回代期望收益;端点要按缩小支撑检查,分母为零时另查退化情形
⭐ 口诀:求谁的概率,就翻到对面的收益去列方程。 还要防止漏检概率范围、支撑外更好动作与退化情形;无差异方程本身不是完整答案。
🃏 支撑枚举(动作 ≥ 3)
📍 出处:12
- 猜一个支撑组合
- 分别列两人的支撑内无差异等式与各自概率归一化;两边支撑尺寸可以不同,方程也可能奇异或有连续多解
- 解出概率
- 验三条:① 支撑内期望全相等(记为 $v_i$)② 支撑外期望 $\le v_i$ ③ 所猜支撑内概率严格为正,支撑外为零,总和为 1
概率为零意味着该动作不在实际支撑中;删掉它后剩余策略仍可能是混合策略,不一定变纯。数值求解时说明容差,别把一次线性求解失败当作没有均衡。
🃏 IESDS(迭代删除严格劣势)
📍 出处:10
- 行玩家看每格第一个数、按列比较;列玩家看第二个数、按行比较
- 找到一个严格劣势的行/列,整行整列划掉
- 在更小的表里重复,直到删不动
- 删到只剩一格 → 那格是唯一的 NE
有限博弈中,在固定纯策略支配或允许混合支配的检查约定下,穷尽删除严格劣势策略有顺序无关性,也不会删掉均衡中被使用的策略。只比较纯动作可能漏掉混合支配;弱支配删除则可能依赖顺序并删掉部分 NE。
🃏 maximin 与鞍点
📍 出处:13
- 只看自己的收益,每行取最小值,再在这些最小值里取最大 → 纯策略安全水平
- 列玩家同理:每列取最小、再取最大(用他自己的收益)
- 零和矩阵的捷径:算「行最小的最大」和「列最大的最小」—— 相等 → 鞍点,纯策略解完;不相等 → 老实混合
- 2×2 求混合 maximin:写出对每个对手纯动作的期望收益,取两条直线下包络的最高点。比较 $p=0$、$p=1$ 和落在区间内的交点;最大值未必在交点。
🃏 逆向归纳
📍 出处:14
- 找一个所有子节点都已标好收益向量的节点
- 看这个节点轮到谁
- 挑他自己那一维最大的那条边
- ⭐ 把选中那条边的整个收益向量搬到这个节点上
- 回到第 1 步,直到根
范围是有限完美信息博弈。搬整个收益向量;遇到并列最佳分支,保留各分支才能列出全部 SPNE。存在信息集时,不能直接按任意子树这样倒推。
🃏 拥塞博弈求纯均衡
📍 出处:15。先分清离散玩家还是连续流量。
- 每人只选一条独立并行路时,等耗时方程可帮助找连续候选,再检查人数非负与守恒;离散模型不能只凭它认定 NE。
- 对每条有人走的旧路 $y$,检查每条不同的新路 $x$:
$$t_x(n_x+1)\ge t_y(n_y)$$ 3. 一次只让一人进行严格成本改善,有限拥塞博弈的势严格下降,最终停止在纯 NE。 4. 一条路径若含多种资源,要按改动后的整条路径算;新旧路径共有的资源人数不变,不能每处都加 1。
Rosenthal 势不是总成本。PoA 也必须比较同一网络:第 15 章新 Braess 网络的最优平均成本是 64.6875,均衡为 80,因此 PoA 为 $256/207$;$80/65$ 是改路前后的均衡比。
🃏 SPDA / CPDA
📍 出处:17
- 每个没被暂收的提案方,向自己列表里还没拒过自己的最高一位提案
- 接受方把「手里的 + 新来的」排序,只暂时握住最好的 $b_c$ 个
- 被挤下来的回到第 1 步(此后不再提这一家)
- 没人能再提案时停
验:逐对查阻挡对,并检查可接受性与容量。严格一对一模型中,每个提案方拿到自己可达的最佳搭档。
多对一 DA 需学校对学生有响应性偏好等条件;学生向学校提案时学校暂留容量内最好的人,学校向学生提案时须相应改写。拆座位也需一致优先序与择校偏好约定,不能对互补偏好直接照搬。
🃏 TTC
📍 出处:18
- 每个人指向当前图里他最想要的那套房;每套房指向它的主人
- 从任意一点沿边走,一定会走出一个环(每点出度都是 1)
- 环上成交:每人拿走他指着的那套;把环上的人和房整个删掉
- 剩下的人重新指向剩余房里最想要的,回到第 2 步
范围:严格偏好、一人一房、初始禀赋固定的住房市场。每轮可以同时移除所有环。
验 IR:每个人拿到的不比自己的原房差;房主离开时原房也同时移除,因此人在场时自己的原房仍可选。
🃏 Round-Robin
📍 出处:20
- 定一个人的顺序
- 轮流叫号,轮到谁就从剩下的物品里挑自己估值最高的一件
- 一圈叫完从头再来,直到分完
⚠️ 并列时怎么取会改结果(第 20 章那张表取 $g_4$ 得 135/45、取 $g_3$ 得 140/45,两个都是 EF1)。 在非负可加估值、全部物品分完的条件下,结果保证 EF1、PROP1,以及件数平衡:每人件数相差至多 1。这里“平衡”不是纳什均衡,且不保证 PO。
🃏 嫉妒图算法
📍 出处:20
- 所有人空手开始
- 找一个 source(没有入边、谁都不眼红他),把任意一件物品发给他
- 发完检查是否成环;成环就沿环轮换整堆,重复到无环
- 回到第 2 步直到发完
每次沿严格嫉妒环轮换,环上各人的价值严格改善,其他人自己的整堆不变。按“整堆重新归属”比较,总边数严格减少,但某一对人之间仍可能出现新边。逐次消环会终止;发新物品时边数可以增加。
在标准单调物品估值和价值查询模型下可保证 EF1,不必可加;但不保证每个人件数平衡,不是每次输出一定不平衡。
🃏 EF1 / PROP1 / MMS 怎么验
📍 出处:19
- EF1:逐对比较。若不嫉妒或对方空手,直接通过该对;可加估值下,若嫉妒就从对方整堆中去掉对自己最值钱的一件再比较。一般单调估值不能只按单件价值选。
- PROP1:先看是否已达到总值的 $1/n$;没达到时,从 $M\setminus A_i$ 选对自己最值钱的一件添上(非负可加条件),再检查。
- MMS:枚举把 $M$ 分成 $n$ 堆的所有方式,取「最小那堆」的最大值;⭐ 总有 $\mathrm{MMS}_i \le \frac1n v_i(M)$
🃏 带权嫉妒图 → 算出该补多少钱
📍 出处:21
- 边权 $w(i,j)=v_i(X_j)-v_i(X_i)$
- 查有没有正权环(边权取反跑 Bellman–Ford)。有 → 这个分法救不回来
- 无正权环时,令 $p_i=\ell(i)$ 为从 $i$ 出发的最大路径权重,允许权重为 0 的空路径;这是无限制非负补贴模型
- 验:逐对查 $v_i(X_i)+p_i\ge v_i(X_j)+p_j$;最长路给出逐分量最小的非负补贴。有预算、支付上限或不同符号约定时要另检查。
🃏 PS「吃蛋糕」与 SD 比较
📍 出处:21
- 每件物品是一块重量 1 的蛋糕;所有人同时、同速吃自己当前最想要且没吃完的那件
- 一件被吃光,正在吃它的人立刻转向列表里下一件还没吃完的
- 全部吃光时停,每人吃掉的份额就是概率
- 比两张概率表用 SD:⭐ 从最爱往下累计概率,每一层都不少才叫支配;⚠️ 常常互不可比
🃏 Core 验证(n = 3)
📍 出处:22
- 空集恒成立;大联盟由效率取等号;3 个单点给下限
- ⭐ 3 个两人联盟翻成上限:因为 $x(N)=v(N)$,有 $x(S)\ge v(S) \iff x(N\setminus S)\le v(N)-v(S)$
- 记上下限为 $l_i,r_i$。不仅要每个 $l_i\le r_i$,还要下限之和不超过 $v(N)$、上限之和不低于 $v(N)$;满足这些才可凑出效率分配
- 相加不等式能给出空核心证据。例如合作总值 100,三个两人值为 50、70、$X$,必要条件是 $X\le80$;$X>80$ 就无解,$X\le80$ 仍需检查其他约束。
⭐ 简单博弈的捷径:核心非空 ⟺ 存在否决者;且核心里非否决者一律拿 0。
🃏 Least Core / Nucleolus
📍 出处:22。
- 先写效率和个体理性域 $I(v)$;非空条件为 $v(N)\ge\sum_i v(\{i\})$。
- 本页最小核心采用非负松弛:保持 $x\in I(v)$,允许 $x(S)\ge v(S)-\varepsilon$,最小化 $\varepsilon\ge0$。
- 核仁继续比较全部联盟余额 $x(S)-v(S)$:升序排列,按字典序最大化。核心非空时,核仁在核心内。
- 换资料先对齐三个口径:分配域、联盟范围、$\varepsilon$ 是否允许为负。去掉个体理性后的前核仁不是同一个定义。
若 $I(v)$ 为空,本页采用的最小核心和核仁都不能宣称“永远有解”。
🃏 Shapley 值(n = 3 的六排列法)
📍 出处:23
- 列出 6 个排列,每行从左到右依次结算增量 $v(S\cup\{i\})-v(S)$
- 每人的 6 个增量求和 ÷ 6
- ⭐ 两个自查:① 三人总和 $=v(N)$ ② 每一行也加起来 $=v(N)$(望远镜求和)
⭐ 简单博弈捷径:$\phi_i = \dfrac{i\ \text{把局面从输变赢的排列数}}{n!}$。 ⭐ 图博弈闭式解:$\phi_i=\frac12\sum_{j\ne i}w(\{i,j\})$ ——「每条边的价值两个端点一人一半」。 Banzhaf 要记清分母:绝对指数为 $\eta_i/2^{n-1}$,归一化指数为 $\eta_i/\sum_j\eta_j$。手套例子关键次数 (3,1,1),对应 (3/4,1/4,1/4) 与 (3/5,1/5,1/5)。
🃏 位置计分规则
📍 出处:24
- 写下打分向量:Plurality $(1,0,\dots,0)$、k-approval 前 $k$ 个 1、Borda $(m-1,\dots,1,0)$
- 逐格填表,按候选项求和
- ⭐ Borda 自查:总分必等于 $n\times\frac{m(m-1)}{2}$(14 人 5 候选 = 140)
🃏 IRV 与两轮决选
📍 出处:24
- 两轮决选:按第一名票数取前两名,直接一对一比
- IRV:反复删掉第一名票数最少的候选项,选票顺延
- 顺延必须跳过所有已淘汰候选项;得零首位票的仍是候选项,要参与最少票判定。
- 事先固定晋级、淘汰与最终并列规则;如允许不完整选票,还要定义耗尽票和多数分母。
🃏 多数图与 Condorcet
📍 出处:25
- $\binom m2$ 对逐对数票:把 $x$ 排在 $y$ 前面的人多,就画 $x\to y$
- 无平票锦标赛中,出度就是胜场版 Copeland 分;有平票时另定计分,例如胜 1 分、平 0.5 分
- 严格击败其他所有候选项才是 Condorcet 赢家。局部出现环不意味着全图没有全胜者:全胜者之外的人仍可能成环
🃏 锦标赛解
📍 出处:25
| 解 | 怎么手算 |
|---|---|
| Copeland | 出度最大的那些 |
| Top Cycle | 沿箭头(步数不限)能走到其他每一个 |
| Uncovered Set | ⭐ 两步之内能走到其他每一个(等价于「没被任何人覆盖」) |
| Banks | 取极大无环顶点导出子图,它的第一名就是一个 Banks 赢家 |
这里采用无平票锦标赛。Banks 的“极大”指不能再加入顶点而保持传递性,不是顶点数最多。
包含关系:$BA\subseteq UC$、$CO\subseteq UC$、$UC\subseteq TC$;有平票的多数图必须先说明扩展定义。
🃏 中位选民规则(单峰域)
📍 出处:26
- 先把候选项排成一条轴,验证每个人的偏好是单峰的(从峰出发两侧各自递减)
- 只问每个人的峰在哪
- 选出中位数那个峰
- ⭐ 奇数选民 + 单峰 ⟹ Condorcet 赢家一定存在,而且中位选民规则会选中它,还是策略防伪的
🃏 逻辑四章
- 真值表:⭐ 每个子公式各占一列,从最内层往外填;$n$ 个符号 $2^n$ 行
- 转 CNF:消去蕴含($\varphi\to\psi \equiv \neg\varphi\vee\psi$)→ 德摩根把 ¬ 赶到字母前(NNF)→ 分配律把 ∨ 赶到里面;⭐ 同时含 $L$ 和 $\neg L$ 的子句恒真,直接扔
- 分辨率反证四步:⭐ ① 否定结论 ② 全转 CNF ③ 反复分辨 ④ 推出空子句 □;⚠️ 终点必须是 □,中途推出了结论也不算完
- 一阶推理:还需标准化变量等步骤。Skolem 化时,见证函数依赖其作用域内的全称变量;扩展语言后保可满足性,不是原语言逻辑等价。合一需最一般合一与出现检查,任意特化代换可能丢失完备性。
📐 四、核心公式:符号与条件放在旁边
以下每组对应一种模型,不能把同一个 $u$、$v$ 或“效率”跨模型直接混用。
帕累托 / 支配
比较同一个可行集中的 $o,o'$。$o$ 帕累托支配 $o'$,需要同时满足:
$$u_i(o)\ge u_i(o')\quad\text{对所有 }i$$
$$u_j(o)>u_j(o')\quad\text{对至少一人 }j$$
前一条保护每个人,后一条排除“完全一样也叫严格改善”。
纳什均衡与无差异原理
$s_i$ 为自己的策略,$s_{-i}$ 为其他人策略;$t_i$ 是自己任意可选偏离:
$$u_i(s_i,s_{-i})\ge u_i(t_i,s_{-i})$$
这必须对每个人、每个合法偏离都成立。
若 $a_i,b_i$ 在正概率支撑内,$c_i$ 在支撑外:
$$u_i(a_i,s_{-i})=u_i(b_i,s_{-i})=v_i$$
$$u_i(c_i,s_{-i})\le v_i$$
支撑内等式帮助求对手概率;支撑外不等式负责排除“其实另有更好动作”。
极大极小定理(von Neumann 1928)
有限二人零和博弈,$s_1,s_2$ 均允许混合策略:
$$\max_{s_1}\min_{s_2}u_1=\min_{s_2}\max_{s_1}u_1=v$$
若只允许纯策略,不保证这两个数相等。
Rosenthal 势函数
在基本离散拥塞模型中,$n_x(a)$ 为策略组合 $a$ 下资源 $x$ 的使用人数:
$$\Phi(a)=\sum_{x\in R}\sum_{k=1}^{n_x(a)}c(x,k)$$
社会总成本是另一式:
$$C(a)=\sum_{x\in R}n_x(a)c(x,n_x(a))$$
一条路成本 $c(x,k)=k$、3 人在用时,势贡献为 $1+2+3=6$,总成本为 $3\times3=9$。
公平判据
默认非负可加估值、完整分配;$A_i$ 是 $i$ 得到的物品集合,$M$ 是全部物品。比较别人那堆也用 $i$ 自己的估值。
EF:对所有 $i,j$:
$$v_i(A_i)\ge v_i(A_j)$$
EF1:对每一对人,已满足上式就通过;否则须能从非空 $A_j$ 中找到一件 $g$:
$$v_i(A_i)\ge v_i(A_j\setminus\{g\})$$
PROP:
$$v_i(A_i)\ge\frac{v_i(M)}n$$
PROP1:已达比例线就通过;否则须存在 $g\in M\setminus A_i$:
$$v_i(A_i\cup\{g\})\ge\frac{v_i(M)}n$$
MMS:$\mathcal P_n(M)$ 是把物品分成 $n$ 堆的所有分割,允许空堆:
$$\mathrm{MMS}_i=\max_{B\in\mathcal P_n(M)}\min_jv_i(B_j)$$
在上述物品模型下:
- EF 推出 EF1,EF1 推出 PROP1。
- EF 推出 PROP;PROP 推出 PROP1。
- 这些箭头不能随意反向;一般 EF1 与 MMS 互不推出。
核心与 Shapley
记 $x(S)=\sum_{i\in S}x_i$。核心需要效率和全部联盟约束:
$$x(N)=v(N),\qquad x(S)\ge v(S)$$
第二个条件对所有 $S\subseteq N$ 成立,包含个人单干底线。
Shapley 的排列版:
$$\phi_i=\frac1{n!}\sum_{\pi\in\Pi_N}\Delta_\pi(i)$$
$\Delta_\pi(i)$ 是顺序 $\pi$ 中,$i$ 加入时带来的增量。按先于 $i$ 的集合 $S$ 分组,也能写成联盟版:
$$\phi_i=\sum_{S\subseteq N\setminus\{i\}}w_S\Delta_i(S)$$
$$w_S=\frac{|S|!(n-|S|-1)!}{n!}$$
$$\Delta_i(S)=v(S\cup\{i\})-v(S)$$
两个阶乘数的是“恰好由 $S$ 中的人排在 $i$ 前面”的排列数。手算常用排列版,编程可用联盟版;后者仍有指数多个子集,不是自动多项式。
一阶随机支配
固定某个人 $i$ 的真实排序。从最喜欢的往下取任意前缀 $T$:
$$\sum_{o\in T}p_i(o)\ge\sum_{o\in T}q_i(o)$$
每个前缀都成立,才记作 $p\succeq_i^{SD}q$;至少一处严格时为严格支配。
等价读法:对每个与该排序相容的 vNM 效用函数,$p$ 的期望效用都不低于 $q$。只比第一志愿概率不够。
⚠️ 五、常见陷阱:先找你正在做的那类题
均衡、支配与博弈树
- “帕累托最优就是公平。” 不对。若可行集规定两人分 3 单位价值,$(3,0)$ 也可能 PO;若允许 $(4,0)$,原点就不是 PO。不能脱离可行集单看坐标。
- “PO 的结果自然会发生。” 囚徒困境的 NE 可被共同合作支配。PO 说有无共同改善,不预测如何实现。
- “NE 就是人人最好。” 它只排除单边严格改善,不保证所有人满意。
- “NE 不能再改善。” 多人一起变动仍可能都改善,强 NE 才检查联盟偏离。
- “严格支配只比纯动作。” 在 $U=(3,0)$、$M=(0,3)$、$D=(1,1)$ 中,混合 $\frac12U+\frac12M$ 两列都得 1.5,严格支配 $D$。
- “弱劣势也能放心删。” 弱支配迭代可能删掉部分 NE,而且依赖删除顺序。
- “用自己的收益解自己的混合概率。” 完全混合候选中,自己的概率是让对手无差异的;仍要回查合法概率与最佳响应。
- “某动作收益提高就应多用。” 混合 NE 中未必。第 12 章只把指定一格从 1 改成 3 时,踢左概率由 $1/2$ 变 $1/3$;若另一格也从 −1 改为 0,才得到旧的 $2/5$。必须对齐实际输入矩阵。
- “maximin 就是 NE。” 有限二人零和中,两人的最优保底策略可组成 NE;一般和博弈没有此保证。第 13 章性别之争行玩家保底 $p=1/3$,混合 NE 为 $p=2/3$,但“按保底策略做”不等于会被读出本次抽样动作。
- “树上策略只写实际路径。” 必须给每个信息集规定行动;完美信息时,走不到的节点也要写。
- “逆向归纳只搬当前人的收益。” 要搬整个收益向量,上一层的其他人才能据此选择。
拥塞、匹配与公平分配
- “换路看新路原来的人数。” 单一并行路中,新路要把自己算进去;多资源路径则只改变实际加入、离开的资源。
- “势函数就是总耗时。” 势是帮助证明单人改善终止的量,不等于社会总成本。
- “加路不会更差。” Braess 的指定网络中,4000 人的均衡平均耗时从 65 变 80;这不表示每条新路都有坏处。
- “稳定匹配等于都满意。” 指定的三人循环例子里,学生全拿第三志愿仍可能稳定;双方偏好必须一起看。
- “换个稳定算法能填满乡村医院。” 在标准响应性偏好等条件下,乡村医院定理约束所有稳定匹配的招生数;未满额学校甚至得到同一批人。不是对任意现实招生模型都成立。
- “EF 只是算法暂时没找到。” 两人都正向评价一件不可分物品、又必须完整分配时,EF 就不存在。一般 EF 存在性判定还可能强 NP-难。
- “乘一个 $\alpha$ 总能实现近似 EF。” 若要求 $v_i(A_i)\ge\alpha v_i(A_j)$,上述一物反例对任何 $\alpha>0$ 都不满足。因此没有全实例保证,不是所有实例都失败,也不是只允许 EF1 一种放松。
- “PROP1 意味着分得不少。” 空手也可能 PROP1:只需假想添一件就跨过比例线。它是有限保证,不是质量目标。
- “MMS 总能兑现。” 非负可加物品模型中,$n\ge3$ 有不存在精确 MMS 分配的实例;3 人 9 物是已知反例规模,计算个人 MMS 也一般 NP-难。
- “Round-Robin 保证 PO。” $v_1=(1,1)$、$v_2=(1,0)$,若先手 1 号并列时选第一件,则交换两件可让 2 号改善而 1 号不变。
- “补贴总能修好嫉妒。” 固定分法有正权嫉妒环时,无论给多少自由补贴都无解;换实物分法可能解决。
- “SD 总能比出高下。” 按共同顺序看 $(1/2,0,1/2)$ 与 $(1/3,1/2,1/6)$:第一前缀前者高,前两项后者高,因此互不可比。
合作博弈的解与计算
- “核心一定存在。” 三人单干值 0、任意两人及大联盟值 1 时,三人各至多拿 0,却必须总计 1,核心为空。
- “Shapley 一定在核心里。” 手套博弈 Shapley 为 $(4/6,1/6,1/6)$,核心却只有 $(1,0,0)$。贡献平均与联盟稳定是不同目标。
- “Banzhaf 都不满足总和为 1。” 绝对指数未必;归一化指数按定义总和为 1。不能把两个分母混起来比较公理。
- “概念简单就容易算。” 允许负边权的图博弈可快速算 Shapley,但核心非空判定一般 coNP-完全;二进制权重 WVG 的 Shapley 一般 NP-难,核心非空反而可检查否决者。先说明表示法。
投票与不可能性
- “多数全胜者一定有。” 理性、传递的个人偏好也能组成多数循环;个人没有自相矛盾,并不保证集体传递。
- “Borda 失败,换另一套名次分就一定好。” 在至少三候选的无限制严格偏好域上,位置计分不能普遍保证 Condorcet 一致。单个轮廓选对不等于一般保证。
- “提高支持不会害到 IRV 当选者。” IRV 不保证该单调性。
- “Arrow 只说现有算法不够好。” 它对给定域、输出与公理组合中的所有规则作不可能性陈述;改前提后要重新判断。
- “G–S 只针对有漏洞的程序。” 至少三候选、无限制严格完整偏好域上的确定单赢家规则,满射、非独裁和策略防伪无法同时保证。
- “所以选什么规则都无所谓。” 反而应明确哪些性质最重要、愿意承担哪类失败。
- “分配公平等于机器学习公平。” 分配页比较份额、估值与机会;ML 公平还可能比较群体错误率、选择率、校准或个体待遇,不能只用一个词替代指标定义。
🧮 六、存在性、唯一性与计算:条件先于标签
“一定存在”是对指定模型的保证,“不保证”不是每个实例都无解。 多项式是相对输入编码长度,不是相对玩家数的口头承诺。
有限博弈与匹配
| 对象 | 存在性 | 唯一性 | 计算 |
|---|---|---|---|
| 纯策略 NE | 不保证 | 不保证 | 小表可枚举 |
| 混合 NE | 有限博弈保证 | 不保证 | 两人有理数收益矩阵:PPAD-完全 |
| 二人零和博弈的值 | 保证 | 值唯一 | 线性规划 |
| 纯策略 SPNE | 有限完美信息保证 | 不保证 | 逆向归纳 |
| 基本拥塞博弈纯 NE | 保证 | 不保证 | 一般 PLS-完全 |
| 加权拥塞纯 NE | 一般不保证 | 不保证 | 依成本函数与模型 |
| 稳定匹配 | 标准严格偏好模型保证 | 不保证 | 一对一 DA:$O(n^2)$ |
| 住房市场强核心 | 严格一人一房保证 | 唯一 | TTC,多项式 |
Nash(1950)给有限博弈的混合均衡存在性;性别之争可有两纯一混合共三个 NE。von Neumann(1928)对应零和极大极小;Selten 的 SPNE 概念要求每个子博弈都理性。
逆向归纳的成本要按显式树大小计算,树本身可能随回合数指数增长。三人及以上的精确混合均衡计算也不能直接照搬两人 PPAD 标签。
加权模型并非一加权就无解:常见加权资源成本模型在仿射成本等特殊情形仍保证纯 NE,参见第 15 章边界。
不可分物品
以下默认非负可加估值、完整分配。
| 对象 | 存在性 | 唯一性 | 计算 |
|---|---|---|---|
| EF 分配 | 不保证 | 不保证 | 一般判存在性强 NP-难 |
| EF1 分配 | 保证 | 不保证 | 多项式算法 |
| 精确 MMS 分配 | 三人起可能不存在 | 不保证 | 个人 MMS 一般 NP-难 |
| MNW 最优分配 | 有限可行集上存在 | 不保证 | 精确求解一般 NP-难 |
直接 Round-Robin 每轮扫描剩余物品,可用 $O(m^2)$ 次估值比较;先为每个人排序再维护指针,可以用 $O(nm\log m)$ 预处理、$O(nm)$ 后续扫描。不能不交代数据结构就一律写 $O(mn)$。
MNW 的常数近似必须说明目标口径:几何平均存在常数因子近似;这不是说同一个常数也近似原始乘积。固定人数时二者最大点相同,近似比换算却不同。Cole–Gkatzelis 原论文
零乘积时,MNW 的公平保证还需先最大化正效用人数,再在相应集合上最大化乘积等规则;不能任选一个乘积为零的分配就宣称 EF1 + PO。
联盟解与投票
| 对象 | 存在性 | 唯一性 | 计算 |
|---|---|---|---|
| 核心 Core | 可能空 | 可能多点 | 显式联盟约束 LP |
| 本页 Least Core | $I(v)$ 非空时保证 | 不保证 | 同域上的 LP |
| Nucleolus | $I(v)$ 非空时保证 | 唯一 | 按序固定约束的一系列 LP |
| Shapley 值 | 有限 TU 博弈保证 | 公理唯一刻画 | 取决于表示法 |
| Condorcet 赢家 | 不保证 | 存在时唯一 | 逐对计票 |
| Banks 赢家 | 非空锦标赛保证 | 不保证 | 找一个可多项式,成员判定 NP-完全 |
| Kemeny 排序 | 有限候选集保证 | 不保证 | 精确优化一般 NP-难 |
Schmeidler(1969)的核仁与 Shapley(1953)的公理刻画回答不同问题。显式列出的 $2^n$ 个联盟值本来就是指数规模输入;写成 LP 不意味着对 $n$ 多项式。
Shapley 可枚举 $n!$ 个排列,也可枚举 $2^{n-1}$ 个联盟;图博弈有闭式解,基本合取 MC-nets 可按规则长度线性次数做算术。Condorcet 检查是每对候选项统计 $n$ 张选票,直接复杂度为 $O(nm^2)$。
🚫 七、不可能性与刻画:先核对输入和输出
这里不是“不好的性质清单”,而是每个具体模型中哪些要求无法同时保证。列举两种算法各有缺点,不构成所有算法都不行的证明。
稳定匹配与住房交换
Roth(1982)· 稳定与双边策略防伪。 标准双边严格偏好匹配域上,不能保证稳定的同时让两边都策略防伪。提案方的保证不能直接推广到接受方。第 17 章
Ma(1994)· TTC 刻画。 严格偏好、一人一房、固定初始禀赋的标准住房市场中,SP + IR + PO 刻画 TTC。这是正面唯一性结果,不是不可能性。第 18 章
多份私有禀赋交换。 一个明确的不可能性模型允许隐藏部分自有物品;“如实”同时要求真实偏好和完整披露禀赋。在这个模型下,即使字典序偏好,策略防伪与 PO 也不能兼得,且其策略防伪要求已蕴含 IR。不能把它泛写成所有多物品分配都“三选二”。原论文模型;背景仍见第 18 章。
实物公平与随机分配
不可分物品。 两人都正向评价唯一一件物品、又要求完整分配时,EF 不存在;对任意 $\alpha>0$ 的乘性 $\alpha$-EF,也没有覆盖所有实例的保证。第 19 章
Bogomolnaia–Moulin(2001)。 标准严格排序的 $n$ 人 $n$ 物随机分配、$n\ge4$ 时,SD-有效、SD-策略防伪、同偏好同待遇无法同时保证;SD-无嫉妒会推出同偏好同待遇,因而更强的三项也不能兼得。
RSD 保证策略防伪及事后效率,一般不保证 SD-有效与 SD-无嫉妒;PS 保证后两项,却不保证强 SD 策略防伪。“不保证”不能读成每次都失败。第 21 章 / 原论文
Zhou(1990)。 这是 $n\ge3$、每人一件的单边随机匹配模型,报告基数效用;事前帕累托效率、策略防伪、同类型对称待遇不能兼得。它不是任意可分物品或两人 AW 的定理。第 21 章 / 原论文摘要
集体排序与确定赢家
Arrow(1951)。 至少三候选、无限制偏好域、输出完整传递社会排序的 SWF,帕累托、IIA、非独裁不能同时满足。不能省略输出必须是理性排序这一项。第 26 章
Gibbard–Satterthwaite。 至少三候选、无限制严格完整偏好域、确定单赢家 SCF,满射、策略防伪、非独裁不能同时满足。它不是直接针对随机输出的同一条结论。第 26 章
Fishburn(1973)。 至少三候选的无限制严格偏好域上,位置计分规则不能普遍满足 Condorcet 一致。第 25 章
改变哪些前提,能得到什么?
限制偏好域。 固定共同轴、奇数选民、严格单峰偏好时,中位峰是 Condorcet 赢家;中位峰规则在该受限报告域内策略防伪。先确认两侧各自递减,不把“一维”直接当成“所有人单峰”。
允许随机输出。 在至少三候选、无限制严格排序域上,同时要求强 SD 策略防伪和事后帕累托效率,会得到固定权重的随机独裁;再加匿名性,才得到唯一的均匀随机独裁。换成弱防伪、允许并列或别的效率定义,不能直接套此结论。第 26 章的精确条件
知道有哪些取舍之后,还要由使用者决定哪些失败最不能接受;数学定理不能替你完成价值判断。
📖 八、术语对照
英文与解释放在同一条里,不需要左右找对应。只查当前遇到的词;精确定义见第二节。
表示法与策略
- 正常形博弈 · normal-form game:用行动集和收益函数表示相互作用;不等于真实过程同时发生。
- 扩展式博弈 · extensive-form game:用博弈树和信息集表示行动顺序与可见信息。
- 严格支配 · strict dominance:固定两个自身策略,前者对每种对手行动的收益都严格更高。
- 占优策略 · dominant strategy:支配其他所有自身策略;先说明严格还是弱占优。
- 纳什均衡 · Nash equilibrium:没有人能单边改变策略提高自己的期望收益。
- 混合策略 · mixed strategy:动作上的概率分布。
- 支撑集 · support:概率大于 0 的那些动作。
保底、博弈树与成本
- 安全水平 · security level:选定策略后,不管别人怎么打,自己至少拿多少。
- 子博弈完美 · subgame perfect:在每个子博弈上都是 NE。
- 势函数 · potential function:成本版严格单人改善使其下降;收益版常用上升约定。
- 无政府状态的代价 · Price of Anarchy:同一实例中最坏均衡成本与最优成本之比。
规则、匹配与交换
- 机制设计 · mechanism design:设计把参与者报告变成结果与支付的规则,并检查由此产生的激励。
- 策略防伪 · strategyproof (SP):说真话是弱占优策略。
- 激励相容 · incentive compatible:需区分占优策略激励相容(DSIC)与贝叶斯激励相容(BIC),不能一概等同 SP。
- 个体理性 · individual rationality (IR):参与不比规定的退出选项差。
- 稳定匹配 · stable matching:可行、个体理性且没有阻挡对。
- 延迟接受 · deferred acceptance (DA):接受方只暂时保留当前最合意的提案。
- 顶级交易环 · top trading cycle (TTC):人指房、房指主人,找环成交。
公平与随机分配
- 无嫉妒 · envy-free (EF):按自己的估值,不会因换成别人的整堆而更好。
- 比例性 · proportionality:至少拿到自己眼中全部物品总值的 $1/n$。
- 最大最小份额 · maximin share (MMS):自己分 $n$ 堆、最后拿最差一堆时能保住的最高价值。
- 最大 Nash 福利 · maximum Nash welfare:最大化乘积(也常用几何平均);零值情形另定规则。
- 一阶随机支配 · stochastic dominance (SD):按自己的排序累计,概率每一层都不少。
联盟价值与贡献
- 联盟博弈 · coalitional / cooperative game:用各联盟能实现的结果或价值描述合作;本页主要讨论可转移效用模型。
- 核心 · core:本页 TU 模型中,效率成立,且没有联盟能靠自身价值让成员全都严格改善。
- 核仁 · nucleolus:把联盟余额从小到大排列,逐层提高最不满意者的余额;需先指定分配域。
- Shapley 值 · Shapley value:所有加入顺序等权平均后的边际贡献。
- 边际贡献 · marginal contribution:$v(S\cup\{i\})-v(S)$。
集体选择与选票
- 社会选择 · social choice:把多人的偏好聚合成集体排序、赢家或其他指定输出。
- 偏好轮廓 · preference profile:全体选民的排序组成的输入。
- 位置计分规则 · positional scoring rule:把名次换成分数,再按候选项加总。
- 即时决选 · instant runoff (IRV):反复淘汰首位票最少者,选票顺延;并列规则提前固定。
- 独立于无关选项 · IIA:SWF 对 a、b 的社会比较,只由大家对 a、b 的比较决定。
- 单峰偏好 · single-peaked:同一轴上,从峰往同一侧移动时偏好递减。
🔗 九、跨教程速查:类比不等于模型相同
- Shapley 与 SHAP:SHAP 能做什么不能做什么。基准输出加贡献之和等于解释的模型输出,前提是背景分布、缺失特征处理与输出空间一致;不是因果证明。
- 边际贡献与特征重要性:特征重要性的三种谎言。不同归因定义回答不同问题。
- 机制设计与拍卖:广告:从推荐到竞价。比较二价拍卖、GSP、VCG 与 eCPM;不要把单物品二价拍卖的防伪保证直接套给 GSP。
- 帕累托与多目标:长期效应与代理指标、重排与多样性。准确性和多样性可形成取舍,但是否处于帕累托前沿仍要检验。
- 个体理性与集体最优:IR 是参与约束,不等于“各自最大化”。长期效应与代理指标里的单优化者代理漂移,也不自动构成多方囚徒困境。
- 单智能体与博弈:MDP显式建模一个决策者和环境动态;把对手当固定环境时,不能忽略其策略改变可能带来的非平稳性。
- 期望收益与效用:价值函数与贝尔曼方程对累计奖励取期望。把奖励解释为 vNM 效用还要说明偏好公理,二者不是自动同义。
- 随机化的目的:探索与利用关注获取信息;博弈中的混合策略可防止被利用,二者目的不必相同。
- 多智能体工程:多 Agent 协作关注协调实现;是否构成利益冲突的博弈,要看目标、信息和规则。
- 拥塞与服务调度:推理服务化提供负载分配背景。只有参与者独立择路、成本满足模型条件时,才能直接使用拥塞博弈的结论。
- 不可能性与没有免费的午餐:数学原理第 11 章。共同练法是先核对量词和问题域,不是断言具体任务无法做好。
- “公平”的指标:合规审计与模型卡。群体错误率、选择率、校准、个体待遇和资源份额并非同一个判据。
- 继续动手:ML 基础手撕代码速查,或回到博弈实战项目。
👉 回到首页 | 动手练:27 · 实战与挑战项目