博弈论课程导读

这组笔记从有限策略式博弈开始，逐步进入零和博弈、线性规划、扩展式博弈、图上的博弈、随机博弈、拥塞博弈、拍卖与机制设计。整体脉络可以理解为：先定义“理性玩家如何选择”，再研究“均衡是否存在、如何计算、效率如何”，最后进入“如何设计规则让理性行为产生好结果”。

Lecture 2 混合策略、期望收益与纳什均衡

这一讲建立有限博弈的基本语言：纯策略、混合策略、策略组合、期望收益和最优反应。最后给出纳什均衡的定义：没有玩家能通过单方面偏离来提高自己的收益。

这一讲证明每个有限 $n$ 人策略式博弈都有混合纳什均衡。核心工具是 Brouwer 不动点定理，并进一步讨论纳什均衡的支撑集性质、帕累托最优和进化稳定策略。

这一讲聚焦 2 人零和博弈，介绍 minmaximizer、maxminimizer 和 minimax 值。Minimax 定理说明，在零和博弈中，纳什均衡、最坏情况保证和最优对抗值会汇合到同一个值。

这一讲引入线性规划问题：目标函数、约束、可行性、无界性和最优可行解。它还介绍 Fourier-Motzkin 消元法，为后面用 LP 计算博弈解做准备。

这一讲从几何角度解释单纯形算法：在凸可行域的顶点之间移动，直到无法继续改进。重点概念包括松弛变量、字典、基、基本可行解和 pivoting。

这一讲介绍原始 LP 与对偶 LP，以及弱对偶性、强对偶性和互补松弛。最后把 LP 对偶性和 Minimax 定理联系起来，说明零和博弈值也可以通过对偶性理解。

这一讲讨论策略支配关系：占优策略、严格占优策略、被严格支配策略和被弱支配策略。它还引入共同知识和迭代删除被严格支配策略，作为简化博弈的第一类方法。

这一讲回到纳什均衡的计算。核心思想是：如果能猜到每个玩家混合策略的支撑集，就可以把寻找 NE 转化为一个约束系统或 LP 问题。

这一讲把博弈从“一次性选择策略”的策略式形式，扩展到“沿着博弈树逐步行动”的扩展式形式。重点包括博弈树、信息集、机会节点、完美信息、不完美信息、完美记忆、行为策略和子博弈完美均衡。

这一讲研究有限完美信息博弈，并用 Kuhn 定理说明这类博弈存在纯策略子博弈完美均衡。之后讨论零和完美信息博弈的决定性、国际象棋、minimax 搜索和 alpha-beta 剪枝。

这一讲说明为什么博弈图比博弈树更适合表示会重复出现的状态。它引入历史无关收益、有限式收益、无记忆策略和无记忆决定性，并给出胜负情形下的固定点算法。

这一讲从图上的博弈进入随机环境：先介绍 MDP，再讨论平均收益、折扣总收益和到达目标概率。随后介绍 Bellman 最优性方程、值迭代、简单随机博弈和无记忆决定性。

这一讲研究自私个体在网络中选择路径时会发生什么。拥塞博弈通过势函数保证纯 NE 存在，而无政府代价衡量自私均衡相对于社会最优的效率损失。

这一讲把拍卖看作博弈，介绍单物品密封报价拍卖和 Vickrey 二价拍卖。随后引入贝叶斯博弈来处理私人估值和不完全信息，并讨论贝叶斯纳什均衡与收入等价原理。

这一讲先从交换经济和市场均衡说起，再进入社会选择理论中的不可能定理。最后把货币带回模型，介绍 VCG 机制，并证明真实报告估值是激励相容的。

这一讲原始笔记只保留了主题入口：匹配市场、单需求拍卖、VCG、Myerson 收入最优拍卖以及机制设计形式化框架。目前内容主要指向稳定婚姻问题的参考链接。