讨论 10：零和博弈与归约

完整题面

零和博弈（Zero Sum Game）：对局双方分别为最大化者（maximizer）与最小化者（minimizer）。收益矩阵 \(M\) 从最大化者视角写出：每一行对应最大化者的一个动作，每一列对应最小化者的一个动作，正元表示最大化者获胜。\(M\) 是 \(n \times m\) 矩阵，\(n\) 为最大化者的选择数，\(m\) 为最小化者的选择数。

固定最大化者选择为概率分布、记选择第 \(i\) 行的概率为 \(p_i\) 的线性规划如下：

\[ \begin{aligned} \max\ & z \\ \text{s.t.}\ & M_{1,1} p_1 + \cdots + M_{n,1} p_n \ge z \\ & M_{1,2} p_1 + \cdots + M_{n,2} p_n \ge z \\ &\ \vdots \\ & M_{1,m} p_1 + \cdots + M_{n,m} p_n \ge z \\ & p_1 + p_2 + \cdots + p_n = 1 \\ & p_1, p_2, \ldots, p_n \ge 0 \end{aligned} \]

其对偶（dual）固定最小化者为概率分布，记选择第 \(j\) 列的概率为 \(q_j\)：

\[ \begin{aligned} \min\ & w \\ \text{s.t.}\ & M_{1,1} q_1 + \cdots + M_{1,m} q_m \le w \\ & M_{2,1} q_1 + \cdots + M_{2,m} q_m \le w \\ &\ \vdots \\ & M_{n,1} q_1 + \cdots + M_{n,m} q_m \le w \\ & q_1 + q_2 + \cdots + q_m = 1 \\ & q_1, q_2, \ldots, q_m \ge 0 \end{aligned} \]

由强对偶性（strong duality），无论先固定最小化者的分布还是最大化者的分布，博弈的最优值相同。

(a) 设某零和博弈的收益矩阵 \(M\) 满足 \(M = -M^{\top}\)。行玩家的期望收益是多少？

(b) 判断真假并证明：若收益矩阵的每个元素均为 \(1\) 或 \(-1\)，且任意一行中 \(1\) 的最大个数为 \(k\)，则对于任意含 \(1\) 的个数少于 \(k\) 的行，行玩家的最优策略以概率 \(0\) 选择该行。

(c) 判断真假并证明：记 \(M_i\) 为收益矩阵的第 \(i\) 行。若 \(M_1 = \frac{M_2 + M_3}{2}\)，则存在行玩家的一个最优策略以概率 \(0\) 选择第 \(1\) 行。

完整题面

置换博弈（Permutation Game）是零和博弈的一种特殊形式。其收益矩阵为 \(n \times n\)，且满足：每一行与每一列都恰好以某种顺序包含元素 \(m_1, m_2, \ldots, m_n\)。例如：

\[ M = \begin{bmatrix} m_1 & m_2 & m_3 \\ m_2 & m_3 & m_1 \\ m_3 & m_1 & m_2 \end{bmatrix} \]

给定任意一个置换博弈，描述行玩家与列玩家的最优策略，论证它们为何是最优的，并给出行玩家的期望收益（即行、列玩家所选元素的期望值）。

完整题面

Alice 与 Bob 对局一个零和博弈，收益矩阵如下。第 \((i,j)\) 个元素表示 Alice 选策略 \(i\)、Bob 选策略 \(j\) 时 Alice 获得的收益。Alice 是行玩家，试图最大化收益；Bob 是列玩家，试图最小化 Alice 的收益。

\[ \begin{array}{c|cc} \text{Alice} \setminus \text{Bob} & 1 & 2 \\ \hline 1 & 4 & 1 \\ 2 & 2 & 5 \end{array} \]

现构造线性规划求最大化 Alice 收益的策略。设变量为 \(x_1, x_2\) 与 \(p\)，其中 \(x_i\) 为 Alice 选第 \(i\) 行的概率，\(p\) 为 Alice 的收益。

(a) 写出为 Alice 选择策略以最大化其收益的线性规划。

(b) 从 Bob 的视角写出一个最小化 Alice 收益的线性规划。设变量为 \(y_1, y_2\) 与 \(p\)，其中 \(y_i\) 为 Bob 选第 \(i\) 列的概率，\(p\) 为 Alice 的收益。

(c) 课上讲过 Bob 的线性规划是 Alice 的对偶。你写的这一对线性规划如何体现这一点？请机械地取对偶，或给出简要论证。（提示：可先把线性规划化成便于取对偶的形式。）

(d) 最优解与博弈的值（value of the game）各是多少？

完整题面

归约（Reduction）：若我们已有求解问题 A 的算法，如何用它求解问题 B？

本课程反复出现的若干例子包括：

• 用线性规划（LP）解最大流（max flow）；

• 用最大流解 \(s\)-\(t\) 最小割（min s-t cut）；

• 用最小生成树（MST）解最大生成树；

• 用 Huffman 树解二十个问题（twenty questions）。

在每种情况下，我们都把要求解的问题 B 的实例 \(I\) 变换成问题 A 的实例 \(I'\)，再把 \(I'\) 的解变换回 \(I\) 的解。重要的是该变换必须是高效的（多项式时间）。若能做到，则称将问题 B 归约（reduce）到问题 A。

直观上，高效归约意味着：若能高效求解 A，则也能高效求解 B；反过来，若我们认为 B 不能高效求解，则 A 也不能。简言之，我们认为 A "至少一样难" 于 B。

为证明归约成立，需同时证明两点：(1) 若问题 A 的实例 \(I'\) 有解，则问题 B 的实例 \(I\) 必有解；(2) 若问题 B 的实例 \(I\) 有解，则问题 A 的实例 \(I'\) 必有解。

以下每一部分都给出一个关于归约的错误论断，请分别解释为何该论断是错误的。

(a) 非负边权的最短简单路径问题可通过把所有边权取负归约到最长简单路径问题。由于非负边权最短简单路径有多项式时间算法，因此最长简单路径也存在多项式时间算法。

(b) 我们有一个从问题 B 到问题 A 的归约：将大小为 \(n\) 的 B 实例变换为大小为 \(n^2\) 的 A 实例。存在一个算法在二次时间内求解 A。因此该归约也给出了在二次时间内求解 B 的算法。

(c) 我们有一个从问题 B 到问题 A 的归约：在 \(O(n^2)\) 时间内将大小为 \(n\) 的 B 实例变换为大小为 \(n\) 的 A 实例。存在一个算法在线性时间内求解 A。因此该归约也给出了在线性时间内求解 B 的算法。

(d) 最小点覆盖（minimum vertex cover）可如下归约到最短路径：给定图 \(G\)，若其最小点覆盖大小为 \(k\)，则构造新图 \(G'\)，使得 \(G'\) 中从 \(s\) 到 \(t\) 的最短路径长度为 \(k\)。\(G'\) 的最短路径长度等于 \(G\) 的最小点覆盖大小，因此若最短路径存在高效算法，则点覆盖也存在高效算法。

完整题面

无向图 \(G = (V, E)\) 称为 \(k\)-可染（k-colorable）的，若能为每个顶点分配来自集合 \(\{1, 2, \ldots, k\}\) 的一种颜色，使得任意两个相邻顶点颜色不同。在 \(k\)-染色问题（k-coloring problem）中，给定图 \(G\)，若它是 \(k\)-可染的则输出 "Yes"，否则输出 "No"。

(a) 说明如何把 2-染色问题归约到 3-染色问题。即描述一个算法，输入图 \(G\) 输出图 \(G'\)，使得 \(G'\) 是 3-可染的当且仅当 \(G\) 是 2-可染的。为证明算法的正确性，请描述如何从 \(G\) 的 2-染色构造 \(G'\) 的 3-染色，以及如何反过来。（无需运行时间分析。）

(b) 2-染色问题存在 \((|V| + |E|)\) 时间算法。上述归约是否意味着 3-染色问题也存在高效算法？若是，求出所得算法的运行时间；若否，请论证你的回答。

完整题面

回顾旅行商问题（Traveling Salesman Problem, TSP）的下列定义，我们称之为 Search-tsp：给定一个边带权的完全图 \(G\) 和一个预算 \(b\)，我们希望找到一条经过 \(G\) 所有节点的回路（tour），使其长度 \(\le b\)（若存在）。

该问题的优化版本（我们称之为 Min-tsp）直接要求最短的回路。

(a) 证明：若 Search-tsp 可在多项式时间内求解，则 Min-tsp 也可在多项式时间内求解。

(b) 反之，证明：若 Min-tsp 可在多项式时间内求解，则 Search-tsp 也可在多项式时间内求解。