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-近似算法。

总结

设计和分析近似算法需要深刻理解问题的结构、复杂性以及各种算法范式。通过这些案例可以看到，即使面对 NP-hard 问题，我们依然有强大的理论工具来设计出高效且有性能保证的算法。

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] $$

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 是第二价格拍卖在一般社会选择问题（如组合拍卖、公共品建设）中的推广。

规则：

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) $$ 即：（没有 $i$ 参与时的最大社会剩余）-（有 $i$ 参与并达成最优解时，其他人的剩余之和）。

性质：

• 满足激励相容（Incentive Compatibility）：诚实报价是占优策略。
• 实现帕累托效率（Pareto Efficiency）。

局限性：

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

克拉克税 (Clarke Tax)： 在公共决策中（如是否延长课程），如果个体的出价改变了集体决策的结果，则该个体需要支付“改变结果所需的最小金额”（即他对他人造成的外部性成本）。

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)

一个机制是策略性的，如果对于任何一个代理人来说，诚实地报告其私有信息（说真话）总是一个最优策略，无论其他代理人报告什么。换句话说，谎报信息不会带来比说真话更好的结果。

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. 权衡: 在策略性、计算复杂性和社会目标的优化程度（近似比）之间做出权衡。