5 Game Theory Basics
博弈论基础 Game Theory Basics¶
博弈论（game theory）用数学模型描述多个决策者之间的策略互动。一个模型通常需要明确参与者、每位参与者可采取的行动，以及行动组合对应的收益。博弈论可以用于分析竞争、协作、市场、网络、拍卖和多智能体系统。
简要发展¶
- 1913 年，恩斯特·策梅洛（Ernst Zermelo）发表关于国际象棋的结果，说明在完全信息、有限且无平局的形式化模型中，先手必胜、后手必胜或双方可保和其中之一成立。
- 1928 年，约翰·冯·诺依曼（John von Neumann）证明了极小极大定理（minimax theorem）。
- 1944 年，冯·诺依曼与奥斯卡·摩根斯特恩（Oskar Morgenstern）出版《博弈论与经济行为》。
- 1950 至 1953 年，约翰·纳什（John Nash）提出纳什均衡（Nash equilibrium）。
理性与效用¶
博弈模型常假设参与者是理性的（rational）：给定自己掌握的信息和对其他人的判断，参与者会选择对自己最有利的行动。这个假设能缩小需要分析的行为范围，并帮助预测策略互动；它是建模工具，并不意味着现实中的人总能准确计算或始终如此行动。
效用理论（utility theory）用效用函数（utility function）表示参与者对结果的偏好。效用是偏好的数量化表示，不一定与收入或财富成线性关系。例如，风险厌恶者对财富增加的效用可能呈递减边际增长。
在有限策略的标准模型中，通常将收益记为实数。若原始数据是成本或惩罚（如监禁年数），要先说明参与者是希望最小化该数值，或将其转换成负效用，以免把“收益越大越好”的约定与成本混淆。
标准式博弈 Normal-Form Game¶
一个有 \(n\) 位参与者的标准式博弈可由以下对象描述：
- 参与者集合 \(P=\{1,2,\ldots,n\}\)；
- 参与者 \(i\) 的纯策略集合 \(S_i\)；
- 策略组合集合
$\(S=S_1\times S_2\times\cdots\times S_n;\)$
- 参与者 \(i\) 的收益函数
$\(u_i:S\to\mathbb R.\)$
策略组合 \(s=(s_1,\ldots,s_n)\) 指每位参与者各自选择一个策略后形成的联合结果。两人博弈通常用收益矩阵表示，单元格中的有序对 \((u_1,u_2)\) 依次给出两位参与者的收益。
占优策略 Dominant Strategy¶
若参与者 \(i\) 的策略 \(s_i\) 对其他参与者的每种策略组合都至少与自己的任何其他策略一样好，则称 \(s_i\) 为弱占优策略（weakly dominant strategy）：
若对任意 \(s_i'\ne s_i\) 都严格大于，则称 \(s_i\) 为严格占优策略（strictly dominant strategy）。占优策略不依赖对手具体选择什么。
帕累托支配与最优性¶
设 \(s,t\in S\) 是两个策略组合：
- 若 \(u_i(s)\ge u_i(t)\) 对所有参与者 \(i\) 成立，则 \(s\) 弱帕累托支配（weakly Pareto-dominates）\(t\)；
- 若上述不等式对所有参与者成立，且至少一位参与者严格改善，则称 \(s\) 帕累托支配（Pareto-dominates）\(t\)；
- 若每位参与者都严格改善，则称 \(s\) 强帕累托支配（strongly Pareto-dominates）\(t\)。
若不存在帕累托支配 \(t\) 的策略组合，则 \(t\) 是帕累托最优（Pareto-optimal）。若不存在强帕累托支配 \(t\) 的组合，则称 \(t\) 弱帕累托最优（weakly Pareto-optimal）。帕累托最优只描述参与者之间是否还能同时改善，并不要求该组合是稳定的。
纳什均衡 Nash Equilibrium¶
给定其他参与者的策略 \(s_{-i}\)，参与者 \(i\) 的最佳回应（best response）是使自己的收益最大的策略：
如果一个策略组合 \(s^*=(s_1^*,\ldots,s_n^*)\) 中，每位参与者的策略都是对其他人策略的最佳回应，则 \(s^*\) 是纯策略纳什均衡（pure-strategy Nash equilibrium）：
在均衡处，没有参与者能通过单方面改变策略提高自己的收益。严格纳什均衡（strict Nash equilibrium）要求每位参与者在该组合下都严格偏好当前策略，而不是任何不同的单方面偏离策略。纳什均衡可以不唯一，也不一定是帕累托最优。
囚徒困境 Prisoner’s Dilemma¶
两名囚徒分别选择“指控”或“不指控”。课件用监禁年数表示结果，因此数值越小越好：
| 囚徒 1 / 囚徒 2 | 指控 | 不指控 |
|---|---|---|
| 指控 | \((10,10)\) | \((0,20)\) |
| 不指控 | \((20,0)\) | \((1,1)\) |
对每位囚徒而言，无论另一人怎么选，指控都带来更短的刑期，所以指控是严格占优策略。唯一纳什均衡是双方指控，结果为 \((10,10)\)。然而双方都不指控时结果为 \((1,1)\)，两人都更好。因此，稳定的非合作均衡可能差于双方协调后的结果。
Chicken 博弈¶
Chicken 博弈也称鹰鸽博弈。两位参与者选择强硬对抗（Fight）或退让（Dodge）：
| 玩家 1 / 玩家 2 | Fight | Dodge |
|---|---|---|
| Fight | \((-1000,-1000)\) | \((1,-1)\) |
| Dodge | \((-1,1)\) | \((0,0)\) |
两种纯策略纳什均衡分别是 \((\text{Fight},\text{Dodge})\) 和 \((\text{Dodge},\text{Fight})\)。双方都强硬会造成极差结果；双方都退让虽然安全，但对任意一方而言，单独改为强硬可以获得更高收益。
石头剪刀布 Rock–Paper–Scissors¶
在零和博弈（zero-sum game）中，一方的收益与另一方的损失相等，即 \(u_1+u_2=0\)。标准石头剪刀布是零和博弈：胜者得 \(1\)，败者得 \(-1\)，平局得 \(0\)。
不存在纯策略纳什均衡：对手选定任何一种手势，都有另一种手势可以击败它。混合策略纳什均衡中，两位玩家都以 \(1/3\) 的概率选择石头、剪刀和布。
足球点球模型¶
若射手和守门员都在左、中、右中选择一个方向，射手进球得 \(1\)，被扑出得 \(0\)，守门员扑出得 \(1\)，则两人的收益之和恒为 \(1\)，这是常和博弈（constant-sum game）。双方收益各减去 \(1/2\) 后得到等价的零和博弈，不会改变最佳回应或均衡。双方均匀随机选择三个方向时，射手与守门员方向相同的概率为 \(1/3\)，射手进球的概率为 \(2/3\)，因此射手的期望收益为 \(2/3\)，守门员为 \(1/3\)。
混合策略 Mixed Strategies¶
纯策略要求参与者确定地选择一个行动。混合策略（mixed strategy）则是在纯策略集合上的概率分布。例如，石头剪刀布中的策略 \((1/3,1/3,1/3)\) 表示对三种手势各以 \(1/3\) 的概率随机选择。
若参与者 \(i\) 使用概率分布 \(x_i\)，策略组合的期望收益按各行动组合的概率加权计算。对固定的其他玩家策略，最佳回应是最大化期望收益。
纳什存在定理（Nash’s theorem）指出：每个有限参与者、有限纯策略的标准式非合作博弈，至少存在一个混合策略纳什均衡。纯策略均衡可能不存在，但允许随机化后，总能找到均衡。
博弈的常见分类¶
博弈可从多个互相独立的角度分类：
- 同时行动与顺序行动：同时行动通常用标准式收益矩阵描述；顺序行动可用扩展式博弈（extensive-form game）描述，参与者按次序行动，如国际象棋、围棋和 Nim 游戏。
- 零和与非零和：零和博弈中一方收益增加对应另一方收益等量减少；非零和博弈允许双方同时获益或同时受损。
- 一次性与重复博弈：一次性博弈只进行一轮；重复博弈会进行有限次或无限多次，声誉、报复和协商可能改变均衡行为。
- 完全信息与不完全信息：完全信息博弈中参与者了解相关规则和收益；不完全信息博弈中至少一方的类型或收益信息未知。
- 合作与非合作博弈：合作博弈允许联盟协调并讨论联盟价值如何分配；非合作博弈直接分析个体策略互动。
均衡效率与计算¶
Price of Anarchy 与 Price of Stability¶
价格无政府状态（Price of Anarchy，PoA）衡量最差纳什均衡相对社会最优结果有多差；价格稳定性（Price of Stability，PoS）衡量最好纳什均衡相对社会最优结果有多差。
若社会福利要最大化，一种常见定义是
若目标是最小化成本，则常将比值写成均衡成本除以最优成本。比较数值前必须确认采用的目标方向和定义约定。
纳什均衡的计算难度¶
有限两人零和博弈可以通过线性规划（linear programming，LP）求解。极小极大定理把一方最大化自身最坏情况收益的问题转化为线性规划，因此可在多项式时间内求得均衡策略。
一般标准式博弈中的均衡计算则更难。计算纳什均衡的经典复杂度类别是 PPAD，即有向图多项式奇偶论证（Polynomial Parity Arguments on Directed graphs）。PPAD 完全性表明该问题与一类“从已知源点寻找另一个源点或汇点”的搜索问题同等困难；它并不意味着问题不可计算，也不等同于 NP 完全。
计算博弈论（computational game theory）或算法博弈论（algorithmic game theory）结合计算机科学与博弈论，关注博弈的表示、均衡概念的计算与评价，以及博弈模型在实际问题中的应用。
不完全信息与贝叶斯博弈¶
贝叶斯博弈（Bayesian game）用于描述参与者不知道其他人的类型或收益信息，但掌握关于类型的概率分布的情形。类型（type）可以表示成本、需求、偏好或竞争者的行为倾向。
Harsanyi 转换¶
Harsanyi 转换（Harsanyi transformation）把不完全信息博弈表示为扩展式博弈：引入一个虚拟的自然（Nature），按共同已知的分布抽取每位玩家的类型。玩家只知道自己的类型，并据此形成对其他玩家类型的条件概率判断。
设类型组合为 \(t=(t_1,\ldots,t_n)\)，联合分布为 \(p(t)\)。参与者 \(i\) 知道自己的类型 \(t_i\) 后，对其他玩家类型 \(t_{-i}\) 的条件概率为
一份完整策略需要为每一种可能的自身类型指定行动，因此参与者 \(i\) 的策略写作 \(a_i(t_i)\)。
贝叶斯纳什均衡¶
策略组合 \(a^*=(a_1^*,\ldots,a_n^*)\) 是贝叶斯纳什均衡（Bayesian Nash equilibrium），如果每位参与者在观察到自身类型后，给定其他参与者的类型依策略 \(a_{-i}^*\) 行动，都无法通过改变自己的行动提高条件期望收益：
例如，若两位玩家的类型为强硬 \(a\) 或温和 \(f\)，并且共同已知的类型分布为
则玩家 1 为强硬型时，玩家 2 为强硬型的条件概率是
玩家 1 为温和型时，玩家 2 为强硬型的条件概率同样为 \(0.4\)。计算均衡时，各类型的行动要根据这些条件概率比较期望收益。
例子¶
- 蒙提霍尔问题（Monty Hall problem）：在主持人知道奖品位置、总是打开一扇未选且没有奖品的门，并提供换门机会的经典规则下，换到另一扇未开门后的中奖概率为 \(2/3\)，坚持原门的概率为 \(1/3\)。结论依赖主持人的规则。
- 新产品竞争：企业可能不知道市场需求，也不知道竞争企业是否会推出同类产品。类型分布和条件期望收益会影响进入或退出决策。
- 不完全信息 Chicken 博弈：玩家的强硬程度可作为类型，行动策略依类型而变。均衡要求每种类型在对其他类型的后验判断下都选择期望收益最高的行动。
合作博弈与 Shapley Value¶
合作博弈（cooperative game）研究联盟能够创造多少价值，以及联盟成员如何分配该价值。Shapley 值（Shapley value）根据玩家在所有可能加入顺序中的平均边际贡献，公平地分配联盟的总价值。
手套博弈¶
玩家 1 和玩家 2 各持有一只左手手套，玩家 3 持有一只右手手套。配成一双的价值为 \(1\)。只有联盟 \(\{1,3\}\)、\(\{2,3\}\) 和 \(\{1,2,3\}\) 能创造价值 \(1\)，其他联盟价值为 \(0\)。
计算玩家 1 的 Shapley 值时，考虑三位玩家的 \(3!=6\) 种加入顺序。只有顺序 \((3,1,2)\) 中，玩家 1 加入时玩家 3 已在联盟中，而玩家 2 尚未加入，因此玩家 1 此时带来边际价值 \(1\)。其余顺序中玩家 1 的边际贡献为 \(0\)，所以
由玩家 1 和 2 的对称性，\(\phi_2=1/6\)。价值守恒给出
Stackelberg 博弈¶
Stackelberg 博弈（Stackelberg game）是领导者—跟随者模型。领导者先公开承诺自己的行动，跟随者观察后作出最佳回应，领导者再根据跟随者会如何回应来选择行动。相应的均衡称为 Stackelberg 均衡（Stackelberg equilibrium）。
考虑如下收益矩阵，玩家 1 先选择行，玩家 2 观察后选择列：
| 玩家 1 / 玩家 2 | 左列 | 右列 |
|---|---|---|
| 上行 | \((2,1)\) | \((4,0)\) |
| 下行 | \((1,0)\) | \((3,1)\) |
若玩家 1 承诺上行，玩家 2 会选左列，因为自己的收益 \(1>0\)，玩家 1 得到 \(2\)。若玩家 1 承诺下行，玩家 2 会选右列，因为自己的收益 \(1>0\)，玩家 1 得到 \(3\)。因此领导者选择下行，结果为 \((3,1)\)。
博弈论应用¶
最短路径拍卖¶
考虑一位买家要在图中购买一条从 \(s\) 到 \(t\) 的路径，每条边由一个自利代理人拥有，真实成本只有该代理人知道。买家希望在采购最短路径时控制支付给获胜代理人的总金额。
一种方案是所有边提交报价，买家选择报价总和最低的路径，并向每条获胜边支付其阈值报价（threshold bid）：在其他报价固定时，该代理人仍能留在中标路径中的最高报价。这种阈值支付可以保证如实报价是占优策略，但总支付可能很高。
课件中的例子包含一条由 \(m\) 条零报价边组成的长路径，以及两条成本为 \(1\) 的替代边。长路径获胜时，每条中标边的阈值报价都是 \(1\)，总支付为 \(m\)。如果禁止长路径中的任意一条边参与，成本为 \(1\) 的替代路径会获胜，其阈值支付为 \(1\)。因此删除一条边可以把支付从 \(m\) 降至 \(1\)，支付比可达到 \(m\)。这个结果说明，限制参与者有时会削弱竞争并降低阈值支付。
自私路由与 Braess 悖论¶
在自私路由（selfish routing）中，每位用户选择一条从起点到终点的路径以最小化自己的延迟。道路延迟可以依赖使用该道路的流量 \(x\)，例如 \(\ell(x)=x\)；也可以是常数延迟 \(\ell(x)=1\)。
课件中的网络有两条原始路线：一条的道路延迟依次为 \(x\) 和 \(1\)，另一条依次为 \(1\) 和 \(x\)。若总流量为 \(1\)，纳什均衡会将流量平均分到两条路线，每位用户的延迟为 \(1+1/2=3/2\)。加入一条零延迟的中间连接后，每位用户都可能选择包含该连接的混合路线，使流量集中到两条拥堵道路上，个人延迟升至 \(2\)。
新增道路反而加重拥堵，这种反直觉现象称为 Braess 悖论（Braess’s paradox）。它展示了个体理性选择形成的均衡可能低于系统整体的表现。
隔离博弈¶
隔离博弈（isolation game）描述参与者在一个空间中选择位置，希望与其他参与者保持距离或获得更大的专属区域。应用场景包括商店选址、产品差异化和 Voronoi 图博弈（Voronoi game）。
模型需要定义：
- 游戏空间及每位玩家可选择的位置；
- 所有玩家位置组成的配置；
- 用于衡量隔离程度的距离向量或权重向量；
- 根据位置计算收益的效用函数。
收益可以基于最近邻距离，也可以基于到所有其他玩家的距离；也可以定义为随距离递增或递减的函数。空间可以是非对称的，也可以是对称的；对称空间又可分为连续空间和有限离散空间，例如超立方体或圆环。
非对称空间中的纯策略纳什均衡可能不存在。许多有限对称空间中的隔离博弈具有势函数（potential function），因此至少存在一个纯策略均衡；但在特定空间中判断给定配置是否为均衡，计算难度仍可能很高。
总距离博弈与势函数¶
在总距离博弈中，\(m\) 位玩家各自选择图上的一个顶点，玩家 \(i\) 的收益为其位置到其他玩家位置的距离总和：
定义全局势函数
当只有玩家 \(i\) 改变位置时，势函数的变化恰好等于该玩家自身收益的变化：
因此这是一个精确势博弈（exact potential game）。若图上位置有限，势函数取值也有限；任何严格改善的单边偏离都会使势函数上升，所以改善路径不能无限循环，最终会到达纯策略纳什均衡。
均衡动态与势博弈¶
对于纯策略均衡，可以粗略区分三种情况：
- 纯策略纳什均衡不存在；
- 均衡存在，但某些改善路径会形成循环；
- 均衡存在，且每条严格改善路径都会终止。
势博弈提供第三种情形的重要充分条件：每次单边严格改善都会让势函数严格增加。若策略空间有限，势函数不可能无限递增，因此改善动态必然终止在一个纯策略纳什均衡。
计算博弈论中的问题¶
对给定博弈表示和均衡概念（如纳什均衡），常见计算问题包括：
- 存在性与构造：均衡是否存在？能否找到一个或全部均衡？
- 唯一性：该博弈是否有唯一均衡？
- 社会福利：是否存在社会福利至少为 \(k\) 的均衡？
- 个体收益：是否存在使玩家 \(i\) 的期望收益至少为 \(v\) 的均衡？
- 计算复杂度：找到均衡需要多少时间与空间？
当一般问题难以求解时，可以研究具有特殊结构的博弈、暴力搜索、小规模实例、近似均衡和启发式算法。也可以改变研究目标，考虑不同于纳什均衡的解概念。
博弈中的学习¶
计算均衡策略是一种分析方式。另一种方式是让参与者反复进行博弈，并根据经验更新策略，这称为博弈学习（learning in games）。
学习方法适用于收益函数未知、对手未必遵循均衡策略，或直接计算均衡过于困难的情况。重复博弈中的代表性方法包括虚拟博弈（fictitious play）和无悔学习（no-regret learning）。研究问题包括：学习过程是否收敛、收敛到什么解，以及在有限时间内能否达到近似均衡。
使用博弈论建立模型¶
将博弈论应用到具体问题时，可以依次完成：
- 识别参与者、行动和收益函数，并让收益依赖模型参数与其他参与者的行动；
- 选择需要研究的均衡概念，明确要回答的计算或评价问题；
- 使用真实参数或实例进行模拟，观察均衡行为和算法表现。
领域模型可以覆盖安全资源配置、网络影响、影响力最大化、公共品贡献、Schelling 居住隔离和投票等问题。计算机科学的贡献通常包括建立领域模型、分析和计算均衡，以及进行算法实验。
小结¶
- 标准式博弈由参与者、策略集合和收益函数构成；纳什均衡要求每位参与者的策略都是对其他人策略的最佳回应。
- 占优策略不依赖对手行动；帕累托最优关注能否让所有人同时改善。两类概念和纳什均衡刻画的是不同性质。
- 混合策略允许参与者随机化。有限标准式博弈一定存在混合策略纳什均衡。
- 不完全信息模型通过类型分布和条件概率描述信念，贝叶斯纳什均衡要求每种类型都最大化条件期望收益。
- 合作博弈可用 Shapley 值按加入联盟时的平均边际贡献分配价值；Stackelberg 博弈则分析领导者先承诺、跟随者再回应的策略顺序。
- 均衡可能损失社会效率，也可能难以计算。拍卖、自私路由、隔离博弈和重复学习展示了博弈论与算法设计的联系。