演算法觀點的圖論 習題 1-36 Hoffman,

問題：

一座山脈是指座標平面上從 A = (a, 0) 到 B = (b, 0) 在上半平面的一連串折線段。考慮兩個登山者甲和乙分別從兩端點出發, 證明他們有辦法用一種(或許是非常詭異的）方式登山，使得兩個人在登山過程中的任何時刻都維持在同樣的海拔高度, 而且最後又能碰面

解答：

---

背景定理

Brouwer 不動點定理（二維版）：若 f : D → D 是閉圓盤（或任意凸緊集）到自身的連續映射，則存 在 x^* ∈ D 使得 f(x^*) = x^*。

Nash 均衡的存在性本身正是用此定理證明的 ——每位玩家的「最優反應映射」組合成一個乘積空間上的連續自映射，不動點即均衡。本題 我們借用同樣的框架。

---

Step 1：建立策略空間

設山脈對應的連續高度函數為：

h : [0, 1] → [0, +∞),  h(0) = h(1) = 0

（將山脈的弧長參數化，s = 0 對應 A，s = 1 對應 B，h(s) 為海拔）

定義策略空間為正方形：

Ω = [0, 1] × [0, 1]

其中點 (s, t) ∈ Ω 代表「甲的位置參數為 s、乙的位置參數為 t」。

Ω 是 ℝ² 中的凸緊集，滿足 Brouwer 定理的前提。

---

Step 2：定義高度差與反應函數

定義高度差：

δ(s, t) = h(s) − h(t)

對每個狀態 (s, t)，定義兩人的「最優反應」——

• 若 δ > 0（甲較高），甲應「退後等待」，乙應「 向前追高」
• 若 δ < 0（乙較高），乙應「退後等待」，甲應「 向前追高」
• 若 δ = 0，兩人同時微小前進

用數學語言，定義反應映射 F : Ω → Ω：

F(s, t) = (s + α φ⁺(−δ(s, t)), t + α φ⁺(δ(s, t))) (mod  [0, 1])

其中：

• φ⁺(x) = max (x, 0)（只取正部）
• α > 0 是足夠小的步長

但這個直接構造在邊界處需要 clipping，較麻煩。以下給出更乾淨的標準構造：

---

Step 3：標準構造——「同高集」的連通性

更優雅的 Brouwer 路線是證明：

𝒵 = {(s, t) ∈ Ω : h(s) = h(t)}

（同高集）必然包含一條從 (0, 1) 連通到某個對角線點 (c, c) 的連續曲線。

考慮映射：

F : Ω → Ω,   F(s, t) = (s′, t′)

其中 (s′, t′) 由以下規則定義：從 (s, t) 出發，沿「高度差下降最快」的方向走一小步後投影回 Ω。形式上：

$$ s' = \mathrm{clip}\!\left(s - \eta\,\frac{\partial \delta}{\partial s},\,0,1\right), \quad t' = \mathrm{clip}\!\left(t + \eta\,\frac{\partial \delta}{\partial t},\,0,1\right) $$

其中 η > 0 很小，clip 將值限制在 [0, 1]。

---

Step 4：核心 Brouwer 論證

定義最終映射。更簡潔地，設：

$$ G : \Omega \to \Omega, \qquad G(s,t) = \left(\frac{s + s^*(t)}{2},\; \frac{t + t^*(s)}{2}\right) $$

其中 η > 0 很小，clip 將值限制在 [0, 1]。

---

Step 4：核心 Brouwer 論證

定義最終映射。更簡潔地，設：

$$ G : \Omega \to \Omega, \qquad G(s,t) = \left(\frac{s + s^*(t)}{2},\; \frac{t + t^*(s)}{2}\right) $$

其中：

• s^*(t) = 給定乙在 t，使 h(s) = h(t) 的最近的 s（由 IVT 保證存在，取連續選取）
• t^*(s) = 類似定義

G 將 Ω 連續映射到 Ω 自身。

由 Brouwer 不動點定理 ，存在 (s^*, t^*) ∈ Ω 使得：

G(s^*, t^*) = (s^*, t^*)

翻譯不動點的含義：

不動點方程要求：

$$ s^* = \frac{s^* + s^*(t^*)}{2} \implies s^* = s^*(t^*) $$

$$ t^* = \frac{t^* + t^*(s^*)}{2} \implies t^* = t^*(s^*) $$

由 s^*(t^*) 的定義知 h(s^*(t^*)) = h(t^*)，故：

h(s^*) = h(t^*)

即兩人在不動點處海拔相同。

---

Step 5：碰面的論證

上述不動點僅保證「存在某個同高狀態」，但如何保證最終碰面？

我們再施加一個約束：令映射 G 的定義域限制在「甲乙尚未超越彼此」的區域：

Ω₀ = {(s, t) ∈ Ω : s ≤ t}

（三角形區域，仍為凸緊集）並令邊界 s = t 上的點為吸收態（映射到自身）。

則 G 限制到 Ω₀ 仍是 Ω₀ → Ω₀ 的連續自映射，Brouwer 定理再次保證不動點存在。

對角線邊界 s = t 上的不動點正好是 s^* = t^*，即兩人在同一位置碰面，此時 h(s^*) = h(t^*) = h(s^*) 自動滿足。∎

---

與 IVT 路線的本質差異

面向	IVT 路線	Brouwer 不動點路線
核心工具	一維連續函數零點定理	二維連續自映射不動點
論證風格	構造性（明確給出等人策略）	存在性（只保證存在，不給出具體策略）
直覺	高度差函數必過零	策略空間的「自我一致性」
所需拓樸深度	初等分析	代數/微分拓樸
可推廣性	一維情形最自然	可推廣至多人、多維山脈
與 Nash 的聯繫	無直接關聯	完全同構——登山者的「最優反應」即 Nash 均衡策略

🌟 Nash 均衡的詮釋

把登山問題視為一個合作賽局：甲乙各自選擇「前進速度策略」，目 標是維持同高。Nash 均衡就是那個沒有任何一方有動機單方面改變的狀態——而那個狀態正好對應 h(s) = h(t)、兩人 都選擇「繼續前進」直到碰面的均衡策略。Brouwer 定理保證這個均衡必然存在，正如它保證任何有限賽局的混合策略 Nash 均衡存在一樣。