Algorithms & Game Theory

Approximation Algorithm

许多重要的优化问题（如旅行商问题、集合覆盖问题）都是NP-hard问题。这意味着，除非 P=NP，否则不存在一个能在多项式时间内找到这些问题的最优解的算法。

然而，在实际应用中，我们并不总是需要绝对的最优解。一个“足够好”的解，如果能在可接受的时间内找到，通常也具有很高的实用价值。近似算法应运而生，它的目标是在多项式时间内找到一个有质量保证的次优解。

核心定义：近似比 (Approximation Ratio)

一个算法的解质量通常通过其近似比来衡量。

• 对于一个最大化问题 (Maximization Problem)，如果一个算法对于任何输入实例，返回的解 S 的值 $f(S)$ 和最优解 O 的值 $f(O)$ 满足以下关系，那么它被称为一个 $\alpha$-近似算法 ($ \alpha \le 1 $)： $$ \frac{f(S)}{f(O)} \ge \alpha $$

• 对于一个最小化问题 (Minimization Problem)，如果算法返回的解 S 满足以下关系，那么它被称为一个 $\alpha$-近似算法 ($ \alpha \ge 1 $)： $$ \frac{f(S)}{f(O)} \le \alpha $$

近似比 $\alpha$ 越接近 1，算法的性能就越好。

a) 背包问题 (Knapsack Problem)

背包问题是经典的组合优化问题：给定一组物品，每个物品有成本 $c_i$ 和价值 $v_i$，以及一个总成本预算 $B$。目标是找到一个物品子集 $S$，使得总成本不超过 $B$，并且总价值最大化。 $$ \max \sum_{i \in S} v_i \quad \text{s.t.} \quad \sum_{i \in S} c_i \le B $$

动态规划解法及其局限性

背包问题可以通过动态规划求解，但是复杂度是伪多项式时间 (pseudo-polynomial)。

动态规划方法通常定义状态 $dp[i][w]$ 表示前 $i$ 个物品在总成本不超过 $w$ 时能获得的最大价值。状态转移方程为： $$ dp[i][w] = \max\left( dp[i-1][w],\; dp[i-1][w - c_i] + v_i \right) $$ 其中 $w$ 的取值范围为 $0$ 到 $B$，因此总时间复杂度为 $O(nB)$。由于 $B$ 是输入的数值而非其位数长度，该算法在 $B$ 很大时并非真正意义上的多项式时间算法。

多项式时间近似方案 (PTAS)

通过牺牲一定的精度，可将上述伪多项式时间的动态规划算法转化为多项式时间近似方案 (Polynomial-Time Approximation Scheme, PTAS)。PTAS 是一类特殊的近似算法，它允许我们任意控制近似比，只要我们愿意付出相应的计算时间。

PTAS 算法步骤：

1. 选择一个小的误差参数 $\epsilon > 0$，目标近似比为 $(1 - \epsilon)$。
2. 定义一个缩放因子 $k = \dfrac{\epsilon V^\ast}{n}$，其中 $V^\ast$ 是不超过预算的物品中的最大价值。
3. 对每个物品的价值进行缩放和取整，得到新的价值：$v'_i = \lfloor \dfrac{v_i}{k} \rfloor$。
4. 使用新的价值 $\{v'_i\}$ 运行动态规划算法，找到最优的物品子集 $S$。
5. 返回子集 $S$ 作为原问题的近似解。

分析：

时间复杂度：经过缩放后，最大的新价值 $V'_{max}$ 约为 $\lfloor \dfrac{V^\ast}{k} \rfloor = \lfloor \dfrac{n}{\epsilon} \rfloor$。DP 算法的运行时间变为 $O(n^2 \cdot V'_{max}) = O\left(\dfrac{n^3}{\epsilon}\right)$。这个复杂度是关于输入规模 $n$ 和 $1/\epsilon$ 的多项式，因此是真正的多项式时间算法。

近似比：可证明该算法是一个 $(1-\epsilon)$-近似算法。令 $O$ 为原问题的最优解，$OPT = v(O)$ 。

• 对任意解 $S$，其真实价值 $v(S)$ 与缩放后价值 $v'(S)$ 满足 $v(S) \ge k \cdot v'(S)$。
• 由于 $S$ 是在缩放后价值 $v'(\cdot)$ 下的最优解，有 $v'(S) \ge v'(O)$。
• 在取整过程中，每个物品的价值至多损失 $k$，因此总损失不超过 $k \cdot |O| \le k \cdot n$，即： $$ v(O) - k \cdot v'(O) \le k \cdot n $$
• 将上述不等式串联： $$ v(S) \ge k \cdot v'(S) \ge k \cdot v'(O) \ge v(O) - k \cdot n $$
• 代入 $k = \dfrac{\epsilon V^\ast}{n}$ 及 $OPT = v(O) \ge V^\ast$，得： $$ v(S) \ge OPT - \epsilon V^\ast \ge OPT - \epsilon \cdot OPT = (1 - \epsilon) \cdot OPT $$
• 因此，该算法实现了 $(1 - \epsilon)$ 的近似比。

b) 顶点覆盖问题 (Vertex Cover Problem)

问题定义：给定一个无向图 $G = (V, E)$，寻找一个最小s的顶点子集 $S \subseteq V$，使得图中每条边至少有一个端点属于 $S$。

这是一个经典的 NP-hard 最小化问题。

简单的 2-近似算法

算法步骤：

1. 初始化顶点覆盖集 $C = \emptyset$。
2. 当图中仍存在未被覆盖的边（即 $E \ne \emptyset$）时： a. 任选一条未被覆盖的边 $(u, v) \in E$。
   b. 将其两个端点加入覆盖集：$C = C \cup \{u, v\}$。
   c. 删除图中所有与 $u$ 或 $v$ 相关联的边。
3. 返回 $C$ 作为近似解。

分析：

该算法返回的解 $C$ 确为一个顶点覆盖，因为循环终止时所有边均已被覆盖。

近似比为 2：

• 令算法在循环中选取的边构成集合 $M$。由于每次选取边后即删除与其端点相连的所有边，$M$ 中任意两条边无公共顶点，故 $M$ 构成一个匹配 (matching)。
• 任意顶点覆盖（包括最优解 $OPT$）必须覆盖 $M$ 中的所有边。
• 因 $M$ 为匹配，覆盖其 $|M|$ 条边至少需要 $|M|$ 个顶点，故 $|OPT| \ge |M|$。
• 算法输出的解 $C$ 的大小为 $|C| = 2|M|$。
• 因此，$|C| = 2|M| \le 2|OPT|$，即该算法为 2-近似算法。

基于 LP-Rounding 的 2-近似算法

对于带权重的顶点覆盖问题，可以使用线性规划松弛 (LP Relaxation) 和舍入 (Rounding) 技术。

问题的 ILP (整数线性规划) 版本：

为每个顶点 $i \in V$ 引入二元变量 $x_i \in \{0, 1\}$，其中 $x_i = 1$ 表示顶点 $i$ 被选入覆盖集。 $$ \begin{aligned} \min \; & \sum_{i \in V} w_i x_i \\ \text{ s.t. } & x_i + x_j \ge 1, \quad \forall (i, j) \in E \\ & x_i \in \{0, 1\}, \quad \forall i \in V \end{aligned} $$ LP-Rounding 算法步骤：

1. LP 松弛：将整数约束 $x_i \in \{0, 1\}$ 放松为 $0 \le x_i \le 1$（等价于 $x_i \ge 0$，因目标函数最小化且约束为覆盖型，最优解自动满足 $x_i \le 1$）。该线性规划可在多项式时间内求解，得到最优解 $x^\ast$。
2. 舍入：若 $x^\ast_i \ge \dfrac{1}{2}$，则将顶点 $i$ 加入顶点覆盖解 $S$。

分析：

可行性：对于任意边 $(i, j) \in E$，LP 约束保证 $x^\ast_i + x^\ast_j \ge 1$。这意味着 $x^\ast_i$ 和 $x^\ast_j$ 不可能同时小于 $1/2$。因此，至少有一个顶点会被我们的舍入规则选中，保证了所有边都被覆盖。

近似比为 2：

• 令 $OPT_{LP}$ 为 LP 松弛的最优目标值，$OPT_{ILP}$ 为原整数规划的最优值（即带权顶点覆盖的最优解）。由于 LP 可行域包含 ILP 可行域，有 $OPT_{LP} \le OPT_{ILP}$。
• 算法解的总权重为 $W(S) = \sum_{i \in S} w_i$。
• 对任意 $i \in S$，由舍入规则 $x^\ast_i \ge \dfrac{1}{2}$，可得 $w_i \le 2 w_i x^\ast_i$。
• 因此： $$ W(S) = \sum_{i \in S} w_i \le \sum_{i \in S} 2 w_i x^\ast_i \le \sum_{i \in V} 2 w_i x^\ast_i = 2 \cdot OPT_{LP} $$
• 结合 $OPT_{LP} \le OPT_{ILP}$，最终有： $$ W(S) \le 2 \cdot OPT_{ILP} $$
• 故该算法为 2-近似算法。

Online Algorithms

离线算法 (Offline Algorithm): 一次性获得所有输入

在线算法：在信息不完整的情况下立即做出决策，并且这些决策通常是不可撤销的。

现实世界中许多问题本质上都是在线的，例如：

• 资源分配：如在线广告投放、任务调度。
• 金融交易：根据实时市场变化决定买入或卖出。
• 路由决策：在网络中为数据包选择路径，而不知道未来的网络拥堵情况。

竞争比 (Competitive Ratio)

由于在线算法无法获得全部信息，不能期望它总能做出像离线算法（知道全部输入）那样最优的决策。因此，我们使用“竞争比”来衡量其性能。

定义：竞争比是一个在线算法在最坏情况下的成本（或收益）与同一输入下最优离线算法成本（或收益）的比率。

• 对于最小化问题：竞争比 = $\max_{I} \frac{ALG(I)}{OPT(I)} \geq 1$
• 对于最大化问题：竞争比 = $\max_{I} \frac{OPT(I)}{ALG(I)} \geq 1$

其中 ALG(I) 是在线算法在实例 (instance) I 上的成本，OPT(I) 是最优离线算法的成本。

目标：设计一个竞争比尽可能接近 1 的算法。

与近似比 (Approximation Ratio) 的区别：

• 竞争比：衡量的是因“信息缺失”而导致的性能差距。
• 近似比：衡量的是因“计算能力有限”（例如，为了在多项式时间内解决 NP-hard 问题）而导致的性能差距。

a) Rent-or-buy Problem

问题描述：冬天到了，你每天都可以选择滑雪。你可以每天花 $1 租用雪具，或者一次性花 \$10 购买雪具。你不知道这个冬天总共会滑雪多少天。目标是让总花费最小。

决策困境：

• 如果只滑几天，租用更划算。
• 如果滑很多天，购买更划算。
• 你必须每天做决定，而不知道未来是否还会滑雪。

简单策略分析：

1. 始终租用 (Always Rent)：如果滑了 $d$ 天，成本就是 d。如果 d 非常大（例如 20 天），最优策略是花 $10 购买，此时策略成本是离线最优成本的 2 倍（20 vs 10），竞争比很差。
2. 第一天就买 (Always Buy)：成本固定为 $10。如果只滑了 1 天，最优策略是租用（成本 \$1），此时策略成本是离线最优成本的 10 倍（10 vs 1），竞争比同样很差。

确定性算法的最优策略：

策略：连续租用 9 天，如果在第 10 天仍然需要滑雪，则购买。

分析：

• 如果滑雪天数 d <= 9，成本为 d。最优离线成本也是 d。竞争比为 1。
• 如果滑雪天数 d > 9，成本为 19。最优离线成本是 $10（在第一天购买）。竞争比为 1.9。

结论：该策略的竞争比为 1.9。可以证明，对于购买成本为 B，租赁成本为 1 的一般情况，租 B-1 天然后在第 B 天购买的策略可以达到 2 - 1/B 的竞争比。

对于给定的一次性购买费用 B，任何策略都可以写成在 X 天之前租赁，在 X+1 天当天购买。

b) 在线二分图匹配 (Online Bipartite Matching)

问题描述：有一个二分图 $G = (U \cup V, E)$。U 中的顶点是固定的，而 V 中的顶点逐一在线到达。每当一个 V 中的顶点 v 到达时，会揭示它与 U 中顶点的所有边。你必须立即决定是否将 v 与其相邻的某个尚未匹配的 U 中顶点匹配，一旦决定无法更改。目标是最大化匹配的边的数量。

应用：在线广告（广告商 U vs 用户查询 V）、任务分配（任务 U vs 工作人员 V）。

贪心算法 (Greedy Algorithm)：当一个顶点 v 到达时，如果它有任何未匹配的邻居 u，就任意选择一个进行匹配。

竞争比：贪心算法的竞争比是 0.5。

核心结论：没有任何确定性在线算法的竞争比能好于 0.5。

原因：对手可以构造一个让贪心算法做出短视决策的实例。例如，先让一个 v1 到达，它连接到一个 u1 和 u2。算法匹配 (u1, v1)。然后对手让 v2 到达，它只连接到 u1 。此时 u1 已被匹配，算法无法做出更优的选择。而最优离线算法可以看到全局，会有两个匹配。

d) 在线背包问题 (Online Knapsack Problem)

一般情况（任意 $v_i, w_i$），物品 $i$ 有价值 $v_i$ 和重量 $w_i$，不存在任何具有恒定竞争比（constant competitive ratio）的确定性算法。因为总能构造对抗性的实例使得算法的竞争比为0。

当 $v_i=w_i$ 时，也被称为 subset sum 问题。

如果不能丢弃，那么贪心算法能达到0.5的竞争比：当物品 $i$ 到达时，如果 $W_{\text{current}}+w_i \leq K$，则接受该物品；否则，拒绝该物品。

概率性问题

a) 秘书问题 (Secretary Problem)

b) 先知不等式 (Prophet Inequality)

$$ E[X_T] \geq \frac{1}{2}E\left[X_\max\right] $$

Randomized Algorithms

随机化算法不仅依赖输入，还依赖随机数生成器。根据性能和运行时间的特点，主要分为两类：

• Monte Carlo 算法：
  • 特点：运行时间固定，但给出的结果有一定概率是不正确的（或者是近似解）。
  • 目标：在有限时间内给出一个“平均表现良好”的解。
• Las Vegas 算法：
  • 特点：总是给出正确的结果，但运行时间是一个随机变量。
  • 目标：平均运行时间较短。
  • 例子：在一个含 $n$ 个元素的数组中（一半是 "a"，一半是 "b"），寻找一个 "a"。随机选择并检查，平均需要尝试 2 次，但最坏情况可能很久。

经典案例分析

Shuffling an Array

• Knuth Shuffle (Fisher-Yates)：
  • 正确做法：遍历 $i$ 从 $n$ 到 1，随机选取 $0$ 到 $i-1$ 之间的一个索引 $j$ 与 $i-1$ 交换。
  • 性质：产生的所有排列是等概率的（Uniformly distributed）。
• 错误做法：遍历 $i$ 从 0 到 $n-1$，每次从整个数组长度 $n$ 中随机选一个 $j$ 交换。这种方法不能产生均匀分布的排列。

随机选择 m 个元素

• 朴素方法：随机选位置，如果已选过则重试。效率较低。
• Knuth 的方法 (Reservoir Sampling 变体)：
  • 遍历 $0$ 到 $n-1$，对于当前索引 $i$，以概率 $\dfrac{m}{n-i}$ 选择该元素。如果选中，则 $m$ 减 1。
  • 此方法能保证正好选出 $m$ 个元素且概率均等。

StupidSort (Bogosort)

• 算法：检查数组是否有序，如果不是，则随机洗牌（Shuffle），重复直到有序。
• 分析：
  • $n$ 个不同元素的排列总数为 $n!$。
  • 假设元素唯一，只有 1 种排列是有序的。单次洗牌有序的概率为 $1/n!$。
  • 平均需要尝试 $n!$ 次洗牌。
  • 每次洗牌和检查耗时 $O(n)$。
  • 期望运行时间：$O((n+1)!)$。这是一个效率极低的算法反例。

Minimum Cut Problem

问题定义：给定一个无向连通多重图 $G=(V, E)$，找到一个割 $(V_1, V_2)$，使得两个集合间的边数最少。

Karger 算法 (随机收缩算法)：

1. 当 $|V| > 2$ 时：
   • 随机从 $E$ 中选择一条边 $(x, y)$。
   • 收缩 (Contract) 该边：将 $x$ 和 $y$ 合并为一个节点，保留多重边，移除自环。
2. 剩下的两个节点代表了割的两个集合，它们之间的边即为割集。

数学分析：

• 假设 $C$ 是图的一个最小割，$|C| = k$。
• 图 $G$ 中每个节点的度数至少为 $k$（否则切断该节点即为更小的割）。
• 图的总边数 $|E| = \frac{\sum \text{deg}(v)}{2} \ge \frac{nk}{2}$。
• 随机选一条边属于 $C$ 的概率： $$ P(e \in C) = \frac{|C|}{|E|} \le \frac{k}{nk/2} = \frac{2}{n} $$
• 收缩过程不破坏 $C$ 的概率：
  • 第 1 次迭代不选中 $C$ 中边的概率 $P_1 \ge 1 - \frac{2}{n}$。
  • 第 2 次迭代（剩 $n-1$ 个点）不选中 $C$ 的概率 $P_2 \ge 1 - \frac{2}{n-1}$。
  • ...
  • 第 $n-2$ 次迭代（剩 3 个点）概率 $P_{n-2} \ge 1 - \frac{2}{3}$。
• 找到最小割的总概率： $$ P(\text{success}) \ge \prod_{i=0}^{n-3} (1 - \frac{2}{n-i}) = \frac{n-2}{n} \cdot \frac{n-3}{n-1} \cdot \frac{n-4}{n-2} \cdots \frac{2}{4} \cdot \frac{1}{3} = \frac{2}{n(n-1)} = \Omega(\frac{1}{n^2}) $$

概率提升：

• 单次失败概率 $\le 1 - \frac{2}{n^2}$。
• 如果重复运行 $k = c n^2$ 次，失败概率降为： $$ (1 - \frac{2}{n^2})^{cn^2} \approx (e^{-2})^c = \frac{1}{e^{2c}} $$ 通过多次重复，可以将失败概率降得非常低。

Streaming Algorithms

• 背景：数据量巨大，无法全部存入内存。数据项逐个到达。
• 限制：存储空间极其有限（通常为对数级或常数级），通常只能对数据进行一次扫描（One Pass）。
• 目标：近似计算某些查询结果，如：
  • 去重后元素个数（Distinct elements）。
  • 出现频率最高的元素。

Toy Example

• 问题：$1$ 到 $n$ 的整数乱序到达，其中缺失了一个数字。设计算法找到它。
• 解法：
  • 计算期望总和 $S_{expected} = \frac{n(n+1)}{2}$。
  • 计算流中所有到达数字的累加和 $S_{actual}$。
  • 缺失数字 $= S_{expected} - S_{actual}$。
  • 空间复杂度：$O(\log n)$（用于存储和的比特数）。

摊还分析 (Amortized Analysis)

摊还分析关注的是一系列操作的平均成本，而不是单次操作。它保证在最坏情况下，一系列操作的平均成本（摊还成本）是低的，即使其中某些个别操作成本很高。

注意：摊还分析不涉及概率（不同于平均情况分析 Average Case Analysis）。

聚合分析 (Aggregate Analysis)

• 定义：对于 $n$ 个操作的序列，总成本为 $T(n)$，则摊还成本为 $T(n)/n$。
• 示例：栈操作 (Stack Operations)
  • 操作：PUSH ($O(1)$), POP ($O(1)$), MULTIPOP($k$) (弹出 $k$ 个或直到栈空，成本 $\min(s, k)$)。
  • 直觉：MULTIPOP 最坏 $O(n)$，但这并不意味着 $n$ 次操作是 $O(n^2)$。
  • 分析：每个元素最多被 PUSH 一次，也最多被 POP 一次（无论是在 POP 还是 MULTIPOP 中）。
  • 总成本 $\le 2n$，所以平均（摊还）成本是 $O(1)$。
• 示例：二进制计数器 (Binary Counter)
  • 操作：INCREMENT (将二进制数加 1)。
  • 翻转次数分析：
    • 第 0 位（最低位）每次都翻转：$n$ 次。
    • 第 1 位每 2 次翻转 1 次：$\lfloor n/2 \rfloor$ 次。
    • 第 $i$ 位翻转 $\lfloor n/2^i \rfloor$ 次。
  • 总翻转次数：$\sum_{i=0}^{k-1} \lfloor \frac{n}{2^i} \rfloor < n \sum_{i=0}^{\infty} \frac{1}{2^i} = 2n$。
  • 最坏情况 $n$ 次操作总成本 $O(n)$，摊还成本 $O(1)$。

核算法 / 会计法 (Accounting Method)

• 核心思想：
  • 为每种操作分配一个摊还成本 (Amortized Cost, $\hat{c}_i$)。
  • 当 $\hat{c}_i > \text{Actual Cost } (c_i)$ 时，多余的部分作为信用 (Credit) 存起来。
  • 当 $\hat{c}_i < c_i$ 时，使用存款支付差额。
  • 条件：$\sum \hat{c}_i \ge \sum c_i$ 对任何前缀序列都成立（信用不能为负）。
• 栈操作分析：
  • 设定摊还成本：PUSH = 2, POP = 0, MULTIPOP = 0。
  • PUSH 时：支付 1 实际成本，存 1 信用在该元素上。
  • POP/MULTIPOP 时：每个被弹出的元素用其自带的 1 信用支付弹出费用。
  • 总摊还成本 $2n = O(n)$，成立。
• 二进制计数器分析：
  • 设定摊还成本：将位从 0 置为 1 (Set) 收费 2 美元。
  • Set 操作：1 美元支付实际翻转成本，1 美元存作信用。
  • Reset 操作（1 变 0）：使用该位上的 1 美元信用支付，不需要额外收费。
  • 每次 INCREMENT 操作只会发生一次 0 到 1 的翻转（及若干次 1 到 0 的翻转）。
  • 摊还成本 $\le 2$，总成本 $O(n)$。

势能法 (The Potential Method)

• 核心思想：定义一个势能函数 $\Phi(D)$ 映射数据结构的状态 $D$ 到实数。

• 公式：第 $i$ 次操作的摊还成本定义为： $$ \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) $$ 其中 $c_i$ 是实际成本。

• 总成本关系： $$ \sum_{i=1}^n \hat{c}_i = \sum_{i=1}^n c_i + \Phi(D_n) - \Phi(D_0) $$ 如果 $\Phi(D_n) \ge \Phi(D_0)$，则 $\sum \hat{c}_i$ 是 $\sum c_i$ 的上界。通常定义 $\Phi(D_0) = 0$ 且 $\Phi(D_i) \ge 0$。

• 栈操作分析：

  • 定义势能 $\Phi(D) =$ 栈中元素个数。$\Phi(D_0)=0, \Phi(D_i) \ge 0$。
  • PUSH：$c_i = 1$，$\Phi$ 增加 1。 $$ \hat{c}_{push} = 1 + (s+1) - s = 2 $$
  • MULTIPOP(k)（设实际弹出 $k'$ 个）：$c_i = k'$，$\Phi$ 减少 $k'$。 $$ \hat{c}_{multipop} = k' + (s-k') - s = k' - k' = 0 $$
  • 所有操作摊还成本 $O(1)$。

• 二进制计数器分析：

  • 定义势能 $\Phi(D_i) = b_i$，即第 $i$ 次操作后计数器中 1 的个数。
  • 假设第 $i$ 次操作将 $t_i$ 个位从 1 重置为 0，并将 1 个位从 0 设置为 1。
  • 实际成本 $c_i = t_i + 1$。
  • 势能变化：
    • 重置 $t_i$ 个 1 $\rightarrow$ 势能减少 $t_i$。
    • 设置 1 个 1 $\rightarrow$ 势能增加 1。
    • $\Phi(D_i) - \Phi(D_{i-1}) = 1 - t_i$。
  • 摊还成本： $$ \hat{c}_i = (t_i + 1) + (1 - t_i) = 2 $$
  • 结论：最坏情况总成本 $O(n)$。

平滑分析 (Smoothed Analysis)

• 概念：介于最坏情况分析和平均情况分析之间。
• 场景：有些算法在最坏情况下性能很差（如 Simplex 算法），但在实际应用中表现很好。
• 定义：分析在最坏情况输入上添加微小随机扰动（noise）后的期望性能。形象描述为“平滑后的峰值”。
• 它解释了为什么某些算法虽然理论最坏情况很差，但在含有少量噪声的真实数据中运行很快。

Basics of Mechanism Design

机制设计（Mechanism Design）的核心在于制定游戏规则，使得在参与者均采取自身利益最大化的策略时，系统能够达到预期的理想状态（如帕累托最优）。

基本概念

• 参与者 (Player)：做出决策的代理人。
• 行动 (Action)：参与者的选择。这里假设参与者同时且仅做一次决策。
• 效用 (Utility)：基于所有参与者行动组合的结果，给予每个参与者的价值衡量（数值越大越好）。
• 准线性效用 (Quasi-linear utility)： 假设代理人的效用定义为分配到的物品的估值（Evaluation Value）与支付金额（Payment）之差。 $$ u_i = v_i(x) - p_i $$ 其中 $v_i(x)$ 是代理人 $i$ 对结果 $x$ 的估值，$p_i$ 是其支付的金额。

Pareto Efficiency

一个状态被称为帕累托有效（Pareto efficient），当且仅当不存在另一个状态满足：

1. 至少对一个代理人来说更好；
2. 对其他所有代理人来说没有变得更差。

在准线性效用的假设下，如果一个状态是帕累托有效的，那么社会剩余 (Social Surplus)（即所有代理人的效用之和）必须是最大化的。

Risk Attitude

• 风险中性 (Risk neutral)：只关心期望效用（Expected Utility）。例如：对“获得0或100各50%概率”与“确定的50”无偏好差异。
• 风险规避 (Risk averse)：更偏好确定的结果。即使期望效用较低，也倾向于避免风险（参考圣彼得堡悖论，人们不愿意花无限的钱去玩期望收益无限的游戏）。

机制设计的目标

设计规则使得：

1. 对每个代理人，存在一个占优策略 (Dominant Strategy)（无论对手如何行动，该策略都是最优的），或至少构成贝叶斯纳什均衡。
2. 在均衡状态下，实现理想的属性（如帕累托效率）。
3. 机制对各种欺诈（如间谍行为）具有鲁棒性。
   • 激励相容 (Incentive Compatibility, IC)：诚实（Truth-telling）是最佳策略。

Auction

拍卖是电子商务中的重要技术。对于卖方，目标是设计协议以实现社会合意结果或收益最大化；对于买方，目标是寻找最佳竞价策略。

单物品拍卖 (Single-Item Auction)

第一价格拍卖 (First-Price Auction)

• 规则：出价最高者得，支付其出价金额。
• 策略：买方不仅考虑自己的估值，还需要推测对手的出价。
  • 若估值为100，出价100则效用为0。
  • 为了获得正效用，买方必须进行“报价修饰”（Shading），即出价低于真实估值。
  • 贝叶斯纳什均衡：如果对手的出价在 $[0, 100]$ 均匀分布，你的最佳策略是出价你自己估值的一半（风险与收益的平衡）。这是一种较弱的均衡概念，依赖于对对手分布的假设。

第二价格拍卖 (Second-Price / Vickrey Auction)

• 规则：出价最高者得，但只需支付第二高的出价金额。
• 策略：诚实是占优策略 (Truth-telling is a dominant strategy)。
  • 支付金额由第二名决定，与自己的出价无关。
  • 降低出价不会降低支付，只会减少获胜概率；提高出价超过估值可能导致以高于估值的价格买入（负效用）。
  • 该性质不需要知道对手的策略或估值分布。

组合拍卖 (Combinatorial Auction)

当多个物品的价值存在相互依赖关系（互补或替代）时，单独拍卖效率低下。

• 互补品 (Complementary)：PC 和内存（$1+1 > 2$）。
• 替代品 (Substitutable)：VAIO 和 ThinkPad（$1+1 < 2$）。

胜者确定问题 (Winner Determination Problem, WDP)

• 目标：拍卖人分配物品以最大化社会剩余（买方出价之和）。
• 复杂性：这是一个加权集合包装问题 (Weighted Set Packing Problem)，属于 NP-hard 问题。
• 解决方法：
  • 搜索树 (Search Tree) 与 分支定界法 (Branch & Bound)。
  • 利用线性规划（Linear Programming）松弛来获得乐观估计以进行剪枝。
  • 启发式方法：优先考虑出价高的、或是更早形成可行解的分支。

VCG 机制 (Vickrey-Clarke-Groves Mechanism)

VCG 是第二价格拍卖在一般社会选择问题（如组合拍卖、公共品建设）中的推广。

对于组合拍卖，会存在物品的互补和替代关系，因此不适用多次 Vickrey Auction 来解决。

规则：

1. 分配规则：选择能使社会剩余最大化的分配方案 $x^\ast$。 $$ x^\ast = \arg\max_{x} \sum_{i} v_i(x) $$

2. 支付规则：代理人 $i$ 的支付等于“因 $i$ 的参与而导致其他代理人社会剩余的减少量”。 $$ p_i = \left( \max_{x} \sum_{j \neq i} v_j(x) \right) - \sum_{j \neq i} v_j(x^\ast) \geqslant 0 $$ 即：（没有 $i$ 参与时的最大社会剩余）-（有 $i$ 参与并达成最优解时，其他人的剩余之和）。

   这个数的相反数，就代表 $i$ 对社会做出的贡献，也是 $i$ 收到的 transfer。

   Agent 的总效用是 $$ u_i(x) = \tilde{v}_i(x) - p_i = \tilde{v}_i(x) + \sum_{j \neq i} v_j(x) - \left( \max_{x} \sum_{j \neq i} v_j(x) \right) $$ 第三项是一个常数，不会改变结果，换成任意的 $h(v_{-i})$ 都可以。根据 VCG 的分配规则，当 $\tilde{v}_i=v_i$ 时，$i$ 的效用最大化，因此无论 $v_j\; (j\neq i)$ 是什么，代理人 $i$ 都会如实报告自己的效用函数，因此 DSIC。

性质：

• Strategyproof
• 实现帕累托效率（Pareto Efficiency）。

局限性：

• 计算昂贵（需要解决NP-hard问题）。
• 易受失败者合谋（Collusion of losers）影响。
• 卖方收入可能低甚至为零。

克拉克税 (Clarke Tax)：

是 VCG 机制的一种形式（如上），它使得 VCG 是个体理性并且所有的价格 $p_i \geqslant 0$ 。

Matching Theory

匹配旨在寻找两方（Two-sided）之间的理想组合，例如：学生 $\Leftrightarrow$ 学校，医生 $\Leftrightarrow$ 医院。

一对一匹配：稳定婚姻问题 (Stable Marriage Problem)

定义：

• 两组参与者（如男性和女性），每人对另一组有严格的偏好排序。
• 阻碍对 (Blocking Pair)：假设 Alice 与 Ken 配对，John 与 Becky 配对。如果 Alice 更喜欢 John 而不是 Ken，且 John 更喜欢 Alice 而不是 Becky，那么 (Alice, John) 就是一个阻碍对。他们会倾向于打破现有关系并重组。
• 稳定性 (Stability)：不存在任何阻碍对的匹配。

延迟接受算法 (Deferred Acceptance, DA / Gale-Shapley)

算法流程（以女性向男性求婚为例）：

1. 每一轮，所有单身女性向其偏好列表中未拒绝过她的最喜欢的男性求婚。
2. 男性在收到的所有提议中，暂定接受（Deferred Accept）最喜欢的那位，并拒绝其他人。如果男性已有未婚妻但遇到了更好的，他会放弃前任接受新人。
3. 被拒绝的女性在下一轮向列表中的下一位求婚。
4. 当没有女性再求婚时，暂定关系变为最终匹配。

DA 的性质：

• 稳定性：结果一定是稳定的。
• 策略证明性 (Strategy-proofness)：对于求婚方（proposing side），说真话（按真实偏好列表求婚）是占优策略。但对于被求婚方（accepting side）不是策略证明的。
• 最优性：该算法产生的匹配是所有稳定匹配中对求婚方最优的。

多对一匹配 (Many-to-One Matching)

应用于学生与学校（或实验室）的匹配，学校有容量配额（Quota, $q_c$）。

扩展 DA 算法：

• 学生向学校申请。
• 学校在不超过配额的前提下，暂定保留优先级最高的学生，拒绝多余的学生。
• 被拒学生继续申请下一所学校。

性质：

• 公平性 (Fairness) / 无正当嫉妒 (No Justified Envy)：如果学生 $s$ 被学校 $c$ 拒绝，那么 $c$ 录取的所有学生在 $c$ 看来都比 $s$ 优秀。
• 非浪费性 (Nonwastefulness)：没有学生在学校 $c$ 有空位时被该校拒绝。
• 稳定性 (Stability) = 公平性 + 非浪费性。

带有约束的匹配 (Matching with Constraints)

现实中常存在分布约束 (Distributional Constraints)，例如为了保证偏远地区的医生数量，可能会设置区域最大配额 (Regional Maximum Quotas)。

问题：

• 当引入区域配额时，可能不存在同时满足公平性和非浪费性的稳定匹配。
• 必须在公平性和效率（非浪费性）之间权衡。

灵活 DA 机制 (Flexible DA, Kamada & Kojima 2015)

• 为了解决区域配额问题，提出了一种改进的 DA。
• 机制：在每个区域内定义学校的轮询顺序（Round-robin）。学校按顺序暂定接受学生，只要不违反个人或区域配额。
• 特性：
  • 保证策略证明性和公平性。
  • 牺牲了非浪费性（可能出现学生想去某校，该校有空位且未达区域上限，但因算法限制无法录取的情况）。
  • 在满足特定稳定性定义（Hatfield-Milgrom stability）的所有匹配中是最优的。

更一般的约束：

• 如果可行向量集合满足遗传性 (Heredity) 和 $M^\natural$-凸性 ($M^\natural$-convexity)，则可以使用广义 DA 算法处理。
• 区域配额、软下限配额满足 $M^\natural$-凸性。
• 项目-学生-房间分配问题通常破坏 $M^\natural$-凸性。

顶级交易循环 (Top Trading Cycle, TTC)

最初用于住房市场（单边匹配），也可用于双边匹配。

机制流程：

1. 每个学生指向最喜欢的学校，每个学校指向最喜欢的学生。
2. 图中必然存在至少一个环（Cycle）。
3. 环中的学生和学校互相匹配，并从市场中移除（学校配额减少）。
4. 重复此过程直到结束。

性质：

• 帕累托有效 (Pareto Efficient)。
• 策略证明 (Strategy-proof)。
• 注意：TTC 保证帕累托效率，但不保证稳定性（可能产生阻碍对）；DA 保证稳定性，但对求婚方来说只是在稳定匹配中帕累托最优，并非全局帕累托最优。

Fair Division

公平资源分配旨在将资源分配给若干代理人（Agents），使得分配结果满足特定的公平性标准。

• 可分资源 (Divisible): 如土地、时间、蛋糕。可以用连续区间 $[0, 1]$ 表示。
• 不可分资源 (Indivisible): 如画作、珠宝、房屋。由离散的物品集合 $M$ 表示。

可分资源：切蛋糕问题 (Cake Cutting)

模型定义：

• 资源： 单一异质商品，表示为区间 $[0, 1]$。
• 代理人集合： $N = \{1, 2, \dots, n\}$。
• 估值函数 (Valuation Function): $V_i: 2^{[0,1]} \to \mathbb{R}$，满足：

  • 加性 (Additive): $V_i(A \cup B) = V_i(A) + V_i(B)$ (若 $A, B$ 不相交)。

  • 归一化 (Normalized): $V_i([0, 1]) = 1$。

  • 可分性 (Divisible): 对任意 $\lambda \in [0, 1]$ 和区间 $I$，存在 $I' \subseteq I$ 使得 $V_i(I') = \lambda V_i(I)$。这意味着可以对任意小的蛋糕进行估值。

    或者是，可分性保证了切的“蛋糕”一定是连续的，不会存在某个点的估值为严格正数的情况。

复杂性模型 (Robertson-Webb Model): 输入是函数，难以用有限位表示。通常使用查询复杂性：

1. Eval$(x, y)$: 返回 $V_i([x, y])$。
2. Cut$_i(x, \alpha)$: 返回 $y$，使得 $V_i([x, y]) = \alpha$。

公平性标准：

1. 比例公平 (Proportionality): 每个代理人认为自己分到的部分至少占总价值的 $1/n$。 $$ \forall i \in N, V_i(A_i) \ge \frac{1}{n} $$
2. 无妒忌 (Envy-freeness, EF): 没有任何代理人想要其他人的份额。 $$ \forall i, j \in N, V_i(A_i) \ge V_i(A_j) $$
   • Envy-freeness 蕴含了 Proportionality。

经典协议：

• Cut and Choose ($n=2$): 一人切，一人选。满足 EF。
• Dubins-Spanier (Moving Knife): 刀从左向右移，任何人一旦觉得刀左边的蛋糕价值达到了总价值的 $1/n$ 就喊停然后拿走这块。 满足比例公平，但不一定 EF。

诚实性 (Truthfulness/Incentive):

在执行协议时，参与人可能会通过谎报 (manipulation) 自己的估值来获得更好的结果。

在 Robertson-Webb 模型下，不存在一个确定性的、真实的、无嫉妒的、且查询次数有界的蛋糕切割机制。

不可分资源 (Indivisible Resources)

定义：

• 物品集： $M = \{1, 2, \dots, m\}$。
• 分配： $A = (A_1, \dots, A_n)$，其中 $\cup A_i = M, A_i \cap A_j = \emptyset$。
• 加性估值： $V_i(A_i) = \sum_{g \in A_i} V_i(g)$。

公平性概念的松弛 (Relaxations): 由于物品不可分，严格的 EF 通常无法实现（例如 2 人分 1 个宝物）。

1. EF1 (Envy-free up to one good): $$ \exists g \in A_j \quad \text{ s.t. } V_i(A_i) \ge V_i(A_j \setminus \{g\}) $$ （移除被妒忌者捆绑包中的某一个物品后消解妒忌）
   • Round-Robin 算法： 轮流挑选最好的物品，结果满足 EF1。
2. EFX (Envy-free up to any good): $$ \forall g \in A_j, \quad V_i(A_i) \ge V_i(A_j \setminus \{g\}) $$ （移除被妒忌者捆绑包中的任意物品后消解妒忌）
   • EFX 比 EF1 更强，是否存在 EFX 分配是目前的开放问题。

效率与公平的结合：

• 纳什社会福利 (Nash Welfare): $\displaystyle\prod_{i} V_i(A_i)$。
• MNW (Maximum Nash Welfare) 解： 最大化纳什福利的分配总是 Pareto 最优且满足 EF1。

混合资源 (Mixed Goods)

模型： 同时包含 $m$ 个不可分物品和 1 个可分的蛋糕。

公平性概念 - EFM (Envy-free for mixed goods): 对于任意代理人 $i, j$：

• 若 $j$ 的捆绑包仅包含不可分物品：满足 EF1 条件。 $$ \exists g \in M_j \quad \text{ s.t. } V_i(A_i) \ge V_i(A_j \setminus \{g\}) $$
• 否则（$j$ 的捆绑包包含蛋糕）：满足完全 EF 条件。 $$ V_i(A_i) \ge V_i(A_j) $$
• 性质： 只有蛋糕时退化为 EF，只有物品时退化为 EF1。
• An EFM allocation always exists for any number of agents and can be found in polynomial time.

存在性证明工具：妒忌图 (Envy Graph)

• 节点： 代理人。
• 妒忌边 (Envy edge): $i \to j$ 若 $i$ 妒忌 $j$。
• 相等边 (Equality edge): $i \dashrightarrow j$ 若 $V_i(A_i) = V_i(A_j)$。
• 关键引理： 在任意妒忌图中，要么存在一个可加集合 (Addable Set)（无内部妒忌且无外部传入边，可给其分配蛋糕），要么存在一个妒忌环 (Envy Cycle)（可通过交换消除妒忌）。
• 结论： EFM 分配总是存在且可在多项式时间内找到。

负担分配 (Chores)

模型：

• 成本函数 $c_i(X): 2^M \to \mathrm{R}^+$，代理人希望成本最小化。
• 目标：
  • 功利主义 (Utilitarian): 最小化总成本 $\sum_i c_i(X_i)$。
  • 平均主义 (Egalitarian): 最小化最大成本 $\max_i c_i(X_i)$。

公平性概念（针对 Chores）：

• PROP (Proportional): $c_i(X_i) \le \dfrac{1}{n} c_i(M)$。
• EF1 (for Chores): 移除自己捆绑包中的一个最大坏事后不妒忌别人。 $$ \exists e \in X_i, \;\; c_i(X_i \setminus \{e\}) \le c_i(X_j) $$
• EFX (for Chores): 移除自己捆绑包中的任意坏事后不妒忌别人。 $$ \forall e \in X_i, \;\; c_i(X_i \setminus \{e\}) \le c_i(X_j) $$
• PROPX: 移除任意一个坏事后满足比例公平。 $$ \forall e \in X_i, \;\; c_i(X_i \setminus \{e\}) \le \frac{1}{n} c_i(M) $$

算法与近似

Round-robin 算法在该情境下只能解决加性的 cost function 的情况（$c_i(X)=\sum_{j\in X} c_{ij}$）

Top-Envy-Cycle Elimination Algorithm:

• 一种智能贪心算法。在每一轮，让不被其他人妒忌的代理人挑选物品。
• 若没有源节点，说明存在妒忌环，进行交换以消除边。
• 对于单调和组合成本函数，该算法能返回 EF1 分配。
• 对于 IDO (Identical Ordinal) 实例（所有代理人对物品排序一致），该算法返回 EFX 分配。

Identical Ordinal (IDO): $c_{i1} \geq c_{i2} \geq \cdots \geq c_{im}$ for all $i$

Maximin Share (MMS):

• 定义： 代理人 $i$ 将物品分成 $n$ 份，取其中对自己价值最小的一份的最大值。即“最坏情况下的最好份额”。 $$ MMS_i = \max_{(X_1, \dots, X_n) \in \Pi} \;\;\min_{j \in [n]} c_i(X_j) $$
• MMS 公平： $c_i(X_i) \le MMS_i$ (针对 Chores) 或 $V_i(A_i) \ge MMS_i$ (针对 Goods)。
• 存在性： 严格的 MMS 分配不一定存在。
• 近似算法 (Approximations) - 针对 Chores:
  • Round-Robin: $(2 - 1/n)$-MMS。
  • PROPX 分配是 2-MMS。
  • Top-Envy-Cycle Elimination: 4/3-MMS。
  • 当前最佳结果: 11/9-MMS (Huang and Lu, 2021)。

其他拓展

部分信息 (Partial Information - Ordinal)

仅知道代理人对物品的排序（Ordinal），不知道具体数值（Cardinal）。

• 观察： 仅利用序数信息通常无法达到最优的近似比。
• MMS 近似比下界：
  • $n=2$: 无法优于 4/3。
  • $n=3$: 无法优于 7/5。
• 算法： 改进的 Round-Robin（如 Repeated pre-fixed sequence 1, 2, 2, 1...）。
  • $n=2$: 序列 [1, 2, 2] 可达 4/3-MMS (最优)。
  • $n=3$: 序列 [1, 2, 3, 3, 2] 可达 7/5-MMS (最优)。

Strategyproof Algorithms

连续挑选算法 (Consecutive Picking):

• 固定一个序列 $k_1, \dots, k_n$，代理人 $i$ 从剩余物品中挑选 $k_i$ 个。
• 性质： 只要每个代理人只有一次挑选机会，该机制就是策略防范的（SP）。
• 近似比： 能保证 $O(\log \frac{m}{n})$ 的近似比。

Asymmetric Agents

设定： 代理人具有不同的权重 $s_i \in [0, 1]$，且 $\sum s_i = 1$。

• 加权 MMS (Weighted MMS): $WMMS_i = s_i \cdot V_i(M)$ (加性估值下的简单定义，严格定义涉及加权划分)。
• 加权 PROPX: 能够通过 Bid-and-Take 算法找到。

Open Problems

1. 设计 RW 模型下有界的 EFM 协议。
2. EFX 分配在加性估值下是否存在？
3. 是否存在常数近似比的加权 MMS 分配算法？
4. 在策略防范（SP）机制下，能否获得比 $O(\log n)$ 更好的近似比？

Facility Location Games

Algorithmic Mechanism Design

算法机制设计是算法设计与经济学博弈论的交叉领域。其核心目标是设计一个系统（机制），即使在所有参与者（代理人，Agents）都自利的情况下，系统整体也能达到一个理想的社会目标。

• Mechanism $M$：一个函数，它接收所有代理人报告的信息 $R$，并输出一个社会结果 (Social Outcome) $O$。
• Agent：系统中的参与者。每个代理人 $i$ 拥有自己的私有信息 (Private Information) $s_i$（例如，在设施选址问题中，就是他们的真实位置）。
• Report：代理人向机制提交的信息 $r_i$。代理人可能会为了自身利益而谎报信息，即 $r_i \neq s_i$。
• Valuation $v_i(O)$：代理人 $i$ 对社会结果 $O$ 的评价或喜好程度。
• Utility $u_i$：代理人 $i$ 从机制中获得的最终满足度。
  • 带支付的机制 (Mechanism with Payment)：效用 = 估值 - 支付。$$u_i(O, P) = v_i(O) - p_i$$
  • 不带支付的机制 (Mechanism without Payment)：效用 = 估值。$$u_i(O) = v_i(O)$$

核心问题在于：自利的代理人会为了最大化自身效用而操纵他们提交的报告。

为了解决这个问题，我们希望设计出具有策略性 (Strategyproof) 或激励相容 (Incentive Compatible) 的机制。

定义 (策略性 Strategyproofness)

一个机制是 strategyproof 的，如果对于任何一个代理人来说，诚实地报告其私有信息（说真话）总是一个最优策略，即便他知道其它代理人的私有信息。

Strategyproofness (also known as dominant-strategy incentive compatibility) is a property of a mechanism wherein reporting one's true preferences (or type) is a weakly dominant strategy for every participant.

Formally, a direct mechanism defined by a social choice function $f$ is strategyproof if, for every agent $i$, every true type $\theta_i$, every possible deviation $\hat{\theta}_i$, and every profile of other agents' types $\theta_{-i}$, the following utility condition holds:

$$u_i(f(\theta_i, \theta_{-i}), \theta_i) \geq u_i(f(\hat{\theta}_i, \theta_{-i}), \theta_i)$$

This implies that no agent can strictly increase their utility by lying, regardless of the actions taken by other agents.

A comparison between DSIC and Bayesian Nash Incentive Compatiblity.

Feature	Strategyproofness (DSIC)	Incentive Compatibility (BIC)
Optimal Strategy	Best regardless of what others do.	Best assuming others are truthful.
Information Needed	None (you only need to know your own type).	Requires beliefs/priors about others.
Strength	Stronger (subset)	Weaker (superset).

Facility Location Games with a Single Facility

这是设施选址博弈中最经典的模型。

模型设定

• 场景: 一个决策者（Principal）希望在一条直线上放置一个公共设施（如基站、图书馆）。
• 代理人: 每个代理人 $i$ 在直线上有一个私有的真实位置 $x_i \in \mathbb{R}$。
• 成本 (Cost): 如果设施被放置在位置 $y$，代理人 $i$ 的成本 $c_i$ 是其到设施的距离。 $$ c_i(y, x_i) = \text{dist}(y, x_i) = |y - x_i| $$ 这里的成本与估值是负相关的关系，代理人的目标是最小化自己的成本。
• 目标: 设计一个策略性的机制 $f$，它根据代理人报告的位置集合 $x = (x_1, ..., x_n)$ 来决定设施的位置 $f(x)$，同时优化（或近似优化）某个社会目标。

目标 1: 最小化社会成本 (Minimizing Social Cost)

社会成本 (Social Cost) 定义为所有代理人成本的总和。

$$ SC_f(x) = \sum_{i} c_i(f(x), x_i) = \sum_{i} \text{dist}(f(x), x_i) $$

机制 1：中位数机制 (Median Mechanism)

将设施放置在所有报告位置的中位数 (Median) 所在的位置。

定理 1 [Procaccia and Tennenholtz '09]:

中位数机制是策略性的 (strategyproof)，并且它能实现最优的（最小的）社会成本。

• 策略性解释: 对于任何一个代理人，如果他单方面地谎报位置，中位数要么不变，要么会向远离他真实位置的方向移动，这两种情况都不会降低他的成本。因此，说真话是最佳策略。

目标 2: 最小化最大成本 (Minimizing Maximum Cost)

最大成本 (Maximum Cost) 定义为所有代理人成本中的最大值，也称为公平性 (Fairness) 目标。 $$ MC_f(x) = \max_{i} c_i(f(x), x_i) = \max_{i} \text{dist}(f(x), x_i) $$

• 一个失败的尝试: 将设施放在能最小化最大成本的位置（即最左和最右代理人位置的中间点）不是策略性的。代理人可以通过谎报位置来将中心点拉向自己。

机制 2：独裁机制 (Dictatorship Mechanism) / 首位代理人机制

将设施总是放置在第一个（或任意一个预先指定的）代理人报告的位置上。

定理 2 [Procaccia and Tennenholtz '09]:

机制 2 是策略性的，并为最大成本问题提供了一个 2-近似 (2-approximation)。任何确定性的策略性机制都无法做到比 2-近似更好。

• 策略性解释: 对于指定的代理人，说真话显然最优。对于其他代理人，他们的报告完全不影响结果，所以谎报无益。
• 近似比解释: 最优的最大成本至少是 (最右位置 - 最左位置) / 2。而该机制下的最大成本最多是 (最右位置 - 最左位置)，因此近似比为 2。

机制 3：随机化机制 (Randomized Mechanism) 将设施以 1/4 的概率放在最左代理人位置，1/4 概率放在最右代理人位置，1/2 概率放在中心位置。

定理 3 [Procaccia and Tennenholtz '09]: 机制 3 是策略性的，并为最大成本问题提供了 3/2-近似。

模型的扩展与变种

1. 厌恶型设施 (Obnoxious Facilities)

代理人希望远离设施（如垃圾场、监狱）。他们的目标是最大化自己到设施的距离。

• 机制: 将线段一分为二，统计两边的代理人数量，将设施放在代理人数量较少的一端。该机制的近似比为 3。

2. 非同质代理人 (Non-identical Agents)

a) 带权重的代理人 (Weighted Agents)

每个代理人 $i$ 除了位置 $x_i$ 外，还有一个权重 $w_i$，两者都是私有信息。成本定义为： $$ c_i(y, x_i) = w_i \cdot \text{dist}(y, x_i) $$

结论: 对于这个问题，最好的策略性机制是那些完全忽略权重的机制。例如，对于社会成本目标，中位数机制仍然是最好的；对于最大成本目标，首位代理人机制仍然是最好的。

b) 基于阈值的代理人 (Threshold-based Agents)

每个代理人 $i$ 有一个可容忍的区间 $I_i$。如果设施建在区间内，其成本为 0；否则成本为 1。 $$ c_i(y, x_i, w_i, \theta_i) = \begin{cases} 0, & \text{if } y \in [x_i - \frac{\theta_i}{w_i}, x_i + \frac{\theta_i}{w_i}] \\ 1, & \text{otherwise} \end{cases} $$

机制 4: 选择一个最优位置，最小化社会成本（即成本为1的代理人数量）。如果最优位置有多个，选择最左边的一个。

结论: 该机制是策略性的。

改变代理人的偏好函数

1. 双峰偏好 (Double Peak Preferences)

代理人的偏好不再是单峰的（离某个点越近越好），而是有两个“峰值”（例如，家附近有两个学校，去哪个都可以）。其成本函数呈现 "W" 形。

• 挑战: 中位数等传统机制在双峰偏好下不再是策略性的。
• 机制:
  • 确定性机制: 总是选择第 1 个代理人的左峰，或者总是选择第 n 个代理人的右峰。这是策略性的。
  • 随机化机制 (为社会成本): 以 1/2 的概率选择中位数代理人的左峰，1/2 的概率选择其右峰。这个机制是期望真实性 (truthful-in-expectation) 的，并有 2-近似比。

2. 双重偏好 (Dual Preference)

在一个场景中，有些代理人喜欢设施（如农贸市场），而另一些则讨厌它（因为它带来噪音和拥堵）。

• 模型: 代理人 $i$ 的效用函数 $u(c_i, y)$
  • 如果讨厌设施 ($p_i=0$): $u(c_i, y) = d(x_i, y)$ (希望距离远)
  • 如果喜欢设施 ($p_i=1$): $u(c_i, y) = l - d(x_i, y)$ (希望距离近, $l$ 是线段总长)
• 机制: 针对不同情况（只谎报偏好、或同时谎报偏好和位置）设计了不同的策略性机制，可以达到最优或近似最优的社会效用。

3. 利他主义 (Altruism)

代理人不仅关心自己的成本，还关心其所在群组 (Group) 的成本。

• 利他成本: 可以是群组的总成本 (Altruistic Total Cost) 或最大成本 (Altruistic Maximum Cost)。
• 策略性概念: 引入了帕累托策略性 (Pareto Strategyproof, PSP) 的概念，即一个代理人的谎报不能在不损害任何其他群组利益的前提下，让自己所属的至少一个群组受益。
• 结论: 针对利他主义代理人，设计策略性机制非常困难。通过对代理人报告进行预处理 (Profile Preprocessing)，可以设计出一些具有常数近似比的机制。

多设施与复杂场景

1. 两个异构设施 (Two Heterogeneous Facilities)

例如，同时建造一个警察局（受欢迎）和一个看守所（被厌恶）。

• 模型: 代理人效用 = 到看守所的距离 - 到警察局的距离。通常还会有两个设施之间距离的限制。
• 机制: 针对代理人数量为偶数和奇数的情况，分别设计了群策略性 (Group Strategy-proof) 的机制，并给出了近似比。

2. 改变目标函数 (Change Objectives)

除了社会成本和最大成本，还研究了更复杂的目标：

• 最小化最大嫉妒 (Minimax Envy): $\min(\max \text{cost} - \min \text{cost})$
• 社会幸福度 (Social Happyness): $1 - \text{Actual}/\text{Worst}$
• 群组公平性 (Group Fairness): 如最大化总群组成本 (mtgc) 或最大化平均群组成本 (magc)。
• 组间与组内公平性 (Intergroup and Intragroup Fairness, IIF) $$ \begin{aligned} & \operatorname{IIF}_1(y, r)=\max _{\mathrm{j}}\left\{\operatorname{avg dist}\left(\mathrm{G}_{\mathrm{j}}\right)\right\}+\max _{\mathrm{j}}\left\{\operatorname{max dist}\left(\mathrm{G}_{\mathrm{j}}\right)-\operatorname{min dist}\left(\mathrm{G}_{\mathrm{j}}\right)\right\} \\ & \operatorname{IIF}_2(y, r)=\max _{\mathrm{j}}\left\{\operatorname{avg dist}\left(\mathrm{G}_{\mathrm{j}}\right)+\operatorname{max dist}\left(\mathrm{G}_{\mathrm{j}}\right)-\operatorname{min dist}\left(\mathrm{G}_{\mathrm{j}}\right)\right\} \end{aligned} $$

3. 增加约束 (Adding Constraints)

• 多赢家设施选址 (Multiwinner Facility Location Games): 将问题看作是多赢家投票，代理人对“设施-位置”对有赞同半径 (approval radius)。
• 容量限制设施 (Capacitated facilities): 每个设施能服务的代理人数量有限。
• 带入场费的设施选址 (Facility location with entrance fee): 建造和使用设施本身有成本。
• 分组代理人 (Grouped agents): 代理人分布在不同区域 (district)，需要分步决策。

总结

设施选址博弈是一个非常丰富和活跃的研究领域。从最简单的单设施、单峰偏好模型出发，可以扩展到多设施、复杂偏好、利他主义、新的社会目标和各种现实约束。

核心思想:

1. 识别冲突: 代理人的自利行为与社会整体目标之间存在冲突。
2. 设计机制: 通过巧妙地设计规则（机制），引导代理人诚实地报告其私有信息。
3. 权衡: 在策略性、计算复杂性和社会目标的优化程度（近似比）之间做出权衡。