### 博弈论算法讲义知识点详解
#### 一、博弈的战略式表述及纳什均衡的定义
**1.1 博弈的战略式表述**
在博弈论中，战略式表述是一种重要的模型化手段，用于描述静态博弈场景。该表述方式假设所有参与者在同一时间做出决策，而且每个人的选择不会影响其他玩家的选择时机。
- **参与人集合**：用数学符号表示为\(\mathcal{N}\)，代表所有参与者的集合。
- **战略空间**：对于每一个参与者\(i\)，其可能采取的战略集合记作\(S_i\)。
- **支付函数**：对于每一个参与者\(i\)，根据所有参与者的战略选择，其获得的收益由支付函数\(u_i:S_1 \times S_2 \times \ldots \times S_n \rightarrow \mathbb{R}\)给出。
战略式表述的博弈可以表示为\((\mathcal{N}, S_1, S_2, \ldots, S_n, u_1, u_2, \ldots, u_n)\)。
**1.2 纳什均衡的定义**
纳什均衡是在战略式表述博弈中的一个重要概念。它指的是这样一种状态，在此状态下，没有任何参与者可以通过单方面改变自己的战略而获得更高的支付。
对于一个包含\(n\)个参与者的博弈，一个战略组合\(s = (s_1, s_2, \ldots, s_n)\)被称为纳什均衡，如果对于每一个参与者\(i\)，有：
\[u_i(s_i, s_{-i}) \geq u_i(s'_i, s_{-i})\]
其中\(s_{-i}\)代表除了参与者\(i\)之外的所有参与者的选择。
另一种表述方式是：对于每个参与者\(i\)，战略\(s_i\)是以下最大化问题的解：
\[\max_{s'_i} u_i(s'_i, s_{-i})\]
**1.3 囚徒困境**
囚徒困境是一个典型的博弈论例子，用来说明即使合作对双方都有利，但由于信任缺失，参与者也可能选择不合作。
- **参与人**：两个囚犯（嫌疑人）。
- **战略**：坦白或抵赖。
- **支付矩阵**：
- 如果两个囚犯都抵赖，则每人坐牢一年。
- 如果两个囚犯都坦白，则每人坐牢八年。
- 如果一个囚犯坦白另一个抵赖，则坦白者释放，抵赖者坐牢十年。
囚徒困境中，(坦白, 坦白)是唯一的纳什均衡，尽管(抵赖, 抵赖)对双方更有利。
#### 二、矩阵对策
**2.1 纯零和对策**
零和对策是博弈论中的一种特殊情形，其中一方的收益必定等于另一方的损失。具体来说：
- **参与者**：通常为两个。
- **策略集**：每个参与者有一组有限的策略可以选择。
- **支付矩阵**：对于每一个可能的策略组合，都定义了一个支付矩阵\(A\)，对于矩阵中的每个元素\(a_{ij}\)，表示第一个参与者选择策略\(i\)，第二个参与者选择策略\(j\)时，第一个参与者的支付。
在零和对策中，支付矩阵\(A\)与\(-A\)互为对方的支付矩阵。
**2.2 零和对策的混合策略**
在零和对策中，参与者可以选择纯策略（即只选择一个确定的策略），也可以选择混合策略（即按照一定的概率分布随机选择不同的策略）。
- **混合策略**：参与者\(i\)以概率\(p_i\)选择策略\(s_i\)，则混合策略为\(\sum p_i s_i\)。
- **期望赢得**：对于混合策略，可以计算出每个参与者的期望赢得。
对于混合策略对策问题，如果存在概率向量\(x\)和\(y\)，使得对所有的概率向量\(x'\)和\(y'\)有：
\[x^T A y \leq x'^T A y' \leq x^T A y\]
则\((x, y)\)被称为混合策略对策问题的鞍点。
**2.3 零和对策的线性规划解法**
当参与者数目较少时，可以通过线性规划的方法来求解零和对策问题。这种方法利用了极大极小原则，寻找参与者之间的最优策略组合。
- **极大极小原则**：参与者的目标是找到最小化对手最大收益的策略。
- **线性规划模型**：通过构建适当的线性规划模型，可以找到满足极大极小原则的最优策略组合。
此外，还有一些关于零和对策解集的定理，如加法律、乘法律和对称律，这些定理为解决具体的零和对策问题提供了理论依据。
