<style> .reveal .slides { text-align: left; font-size:28px; } </style> # On Tree Equilibria in Max-Distance Network Creation Games Author: Qian Wang 論文連結: [link](https://arxiv.org/pdf/2106.15961) 01257132 陳宏勝、01157122 胡智涵 --- ## Network Creation Game 一開始有 $n$ 個 agent (點)，且每個 agent 能選一個不包含自己的 agent 集合 $S$，且與這個集合內的 agent 建邊，建一條邊的花費是 $\alpha > 0$，且為無向邊，邊權為 $1$，每個 agent 的目標是最小化自己到所有其他 agent 的最短路徑和加上建邊花費和，沒有辦法走到其他 agent 就是 $\infty$ 。 ---- 換句話說: $n$ 個 agent，且他們的編號為 $1 ... n$，每個 agent $i$ 可以選一個 $\{1 ... n\} \setminus \{i\}$ 的 subset $s_i$ ，即為 agent $i$ 的 strategy，如下圖例子，agent $i$ 買了連向 $a,b,c$ 的三條邊。  所以 strategy profile $s=(s_{1},s_{2},...,s_{n})$ ---- 根據上頁的 $s$ 可以得到一個邊的集合 $E_{s}$，對於所有的 $i$ 如果 $j \in s_{i}$，則邊 $(i,j) \in E_{s}$ (邊權為 $1$ )。 所以我們得到一張圖 $G_{s}=<V,E_{s}>$ 其中$V=\{1 ... n\}$。  ---- $d_{G_{s}}(i,j)=$ 在圖 $G_{s}$ 上 $i$ 到 $j$ 的最短路徑長，若到不了則為 $\infty$。 則對於 agent $i$ 的 cost function 為: $c'_{s}(i)=\alpha|s_{i}|+\sum_\limits{j\in V}d_{G_{s}}(i,j)$ 每個 agent $i$ 目標最小化 $c'_{s}(i)$。 ---- ### 舉個例子 假設 agent 數量為5,以下是每個 agent $i$ 花錢與其他點的建邊，可以建出右方的圖 <div style="position: absolute; left: 0%; top:90%;"> | $i$ | $s_i$ | $\alpha \vert s_{i} \vert + \sum_\limits{j\in V}d_{G_{s}}(i,j)$ | | --- | ----- | -------------------------- | | 1 | {2} | $\alpha \cdot 1 + 9$ | | 2 | {} | $\alpha \cdot 0+8$ | | 3 | {5} | $\alpha \cdot 1+8$ | | 4 | {} | $\alpha \cdot 0+8$ | | 5 | {2,4} | $\alpha \cdot 2+5$ | </div> <div style="position: absolute; right: 0%; top:70%;">  </div> ---- ## Max-distance Network Creation Game 在這篇論文中討論的 cost function 較不一樣。 $c_{s}(i)=\alpha|s_{i}|+ D_{G_{s}}(i)$ 其中 $D_{G_{s}}(i) = max_{j\in V} \ d_{G_{s}}(i,j)$ 同樣地，每個 agent $i$ 目標也是最小化 $c_{s}(i)$ 總體成本: $Cost(s) = \sum_\limits{i \in V}c_{s}(i) =\alpha|E_{s}|+\sum_{i \in V}D_{G_{s}}(i)$ ---- ### 再舉個例子 在 Max-distance Network Creation Game 中 ，假設 agent 數量為5,以下是每個 agent $i$ 花錢與其他點的建邊，可以建出右方的圖 <div style="position: absolute; left: 0%; top:90%;"> | $i$ | $s_i$ | $\alpha \vert s_{i} \vert + \max_\limits{j\in V}d_{G_{s}}(i,j)$ | | --- | ----- | -------------------------- | | 1 | {2} | $\alpha \cdot 1 + 3$ | | 2 | {} | $\alpha \cdot 0 + 2$ | | 3 | {5} | $\alpha \cdot 1 + 3$ | | 4 | {} | $\alpha \cdot 0 + 3$ | | 5 | {2,4} | $\alpha \cdot 2 + 2$ | </div> <div style="position: absolute; right: 0%; top:70%;">  </div> ---- ## Nash Equilibria 令 $\mathcal{S}$ 為全部strategy profile形成的集合。 則稱 $s$ 是一個 Nash Equilibria 如果對於所有的 $i \in V$ $c_{s}(i) \leq c_{s'}(i)$ $\forall s' \in \mathcal{S}$。 --- ## PoA (Price Of Anarchy) 評估自私的 agent 造成全體效益的比值 (越大越差)。 在這個 Max-distance 版本的 Game 下，他的 PoA 定義為: 令 $\mathcal{N}$ 為全部Nash Equilibria 形成的集合。 $s^{*}$為最小化總體成本的strategy profile， 也就是$Cost(s^{*}) = min_{s \in \mathcal{S}}Cost(s)$。 則: $PoA=\frac{max_{s \in \mathcal{N}}Cost(s)}{Cost(s^*)}$ --- ## 論文研究結論 這篇論文的目標是證明當 $\alpha > 19$ 時，Max-distance Network Creation Game 當$s$ 是 Nash Equilibria 時，$G_{s}$會是一顆樹。 但在這篇論文之前，就已經有其他篇證明過當 $\alpha > 129$ 時所有的 Equilibria 都會是一顆樹，所以這邊的主要工作是降低 $\alpha$ 的下界。 並且還給出了在不同 $\alpha$ 值範圍下的 $PoA$ 的上界。  --- ## Definition - $diam(G)$ : 對於所有的 $v \in G$，最大的 $D_G(v)$ 。 - $rad(G)$ : 對於所有的 $v \in G$，最小的 $D_G(v)$ 。 - Central Vertex : 中心點，中心點 $v$ 滿足 $rad(G) = D_G(v)$ 。 - Antipodal Vertex : 對蹠點，令 $C$ 為一個環長為 $k$ 的 cycle，且令 $u,v$ 為 $C$ 上的點。如果 $d_C(u, v) \ge \lfloor \frac{k}{2} \rfloor$ ，則 $u$ 的對蹠點為 $v$ ，換句話說，環上離 $u$ 最遠的點。 <center>  </center> ---- - Cut vertex : 割點，割掉這個點可以使得圖不連通。 - Biconnected Subgraph : 一張不包含割點的子圖。 - Biconnected Component(BCC) : 最大的 Biconnected Subgraph。 - Average degree : 平均度數，表示為 $deg(H)$，用來計算BCC $H$的平均度數，計算方法為 $\frac{1}{\vert V (H) \vert} \sum_{v \in V(H)} deg_H(v)$ 。 - Min Cycle : 一張圖 $G$ 中的一個min cycle $C$，任意兩點 $x_1,x_2 \in V(C)$，皆滿足 $d_C (x_1,x_2) =d_G (x_1,x_2)$ 。 <center>  </center> --- ## Proof Road Map 大目標是證出，當 $\alpha > 19$ 時，所有的 Equilibrium Graph 都是一顆樹 (Theorem 1)。 要達成這個目標，這篇論文用的方式是討論 BCC 的 Average Degree: - 根據樹的定義，樹是一張連通無環圖。 1. 那麼由於非連通時是必會存在 agent 他的 Cost 為 $\infty$，所以非連通圖絕對不是均衡圖。 2. 有環等價有 BCC ，把圖變成一塊塊的 BCC 會更容易討論，所以本篇論文著重在 BCC。 3. 透過限制 Average Degree 使得 BCC 不存在，等價圖上沒有環，證明就結束了。 ---- <center>  </center> --- ## 4.1 Cycles in the Equilibrium Graph 本部分證明非樹的 Equilibrium Graph 中任意的 min-cycle $C$ 有以下性質： 1. $C$ 為 Directed Cycle 2. $\vert C \vert \ge 2 \alpha - 1$ 註:如果 vertex $a$ 買了 $b$ 則在 $G$ 上會有一條 $a \rightarrow b$ 的邊 denoted as $(a,b)$ <center>  Directed Cycle </center> ---- ## Lemma 1. 本篇論文的一個重要引理，後面很多證明都會用到這個引理。 在 Equilibrium Graph上，一個以 $b$ 為根的最短路徑樹 $T$ 中，$a$ 買了 $a_1$ 所以有 $(a,a_1)$ 這條邊，其中 $\ a\neq b$。 如果 $(a,a_1)$ 不在 $T$上或 $a_1$ 是 $a$ 在 $T$ 上的父節點，則 $D_G(a) \leq D_G(b) + 1$。 且如果 $a$ 再買一個到 $a_2$ 的邊，且 $(a,a_2)$ 不是 $T$ 上的邊，則 $D_G(a) \leq D_G(b) + 1 - \alpha$。 ----  ---- $pf.$ 這其實是個策略，讓 $a$ 考慮把 $(a,a_1)$ 賣掉換成 $(a,b)$ 得到的圖我們叫 $G'$ 其中 $D_G'(b) \leq D_G(b)$。 <center>  </center> 如圖可以很直觀的看出 $D_G'(a) \leq D_G'(b) + 1 \leq D_G(b) + 1$，但 $a$ 沒有使用這種策略但 $G$ 是平衡圖，可知 $D_G(a) \leq D_G(b)+1$。 ---- <center>  </center> 接下來 $a$ 可以把　$(a,a_2)$ 這條邊賣掉使得他的 Cost 從 $D_G'(a) \ \rightarrow \ \leq D_G(b) + 1 - \alpha$。 同樣的 $a$ 沒有採取這種策略，因此 $D_G(a) \leq D_G(b) + 1 - \alpha$。 ---- ## More Lemma 2. 對於每個 Equilibrium Graph ，每個 Cycle 的長度皆 $\ge \alpha + 2$ 。 3. 對於 $\alpha > 2$ ，在非樹的 Equilibrium Graph 中，每個 \*Min Cycle 都是 Directed Cycle 。 4. 令 $H$ 為非樹Equilibrium Graph 中的 biconnected component ， 對用 $H$ 中的所有邊 $e$ ，都能找到一個 Min Cycle包含 $e$。 5. 對於每個 Equilibrium Graph ，每個 Cycle 的長度皆 $\ge 2\alpha - 1$ 。 ---- ## Corollary 1. 對於 $\alpha > 2$，則$H$為非樹的Equilibrium Graph中的 biconnected component，則對於$H$中的所有點，都至少買了一條邊(Lemma 3、4)。 --- ## 4.2 Lower Bound for Average Degree 本部分可證明BCC $H$ 的 $deg(H)$ 有下界 $2+ \frac{1}{5}$ 。 主要想法為證明任意 $2$-degree path 的長度皆不大於 $3$ ，因此可使得 $2$-degree 點數量可被限制(數量有上界)，所以大 degree 的點數量就會有下界。 - 2-degree path 是指在一個 biconnected component $H$ 裡，對於一條路上的任意點 $x$ ，其中 $deg_H(x)=2$，所以他會是一條沒有分岔的路。 <center>  </center> ---- ## More Definition $\begin{split}S(v) = \{ w\in V \ | \ v=arg \ \min_{v\in V(H)}d_G(u,w)\} \end{split}$ - $\cup_{v \in V(H)}S(v)=V$ - $for \ u,v \ \in V(H), S(u)\cap S(v) = \emptyset$ - $for \ v \ \in V(H), S(v)\cap V(H) = \{ v \}$ ---- <center>  </center> - 黃色的範圍為 biconnected component <font style="color:yellow">$H$</font> - 紅色的範圍為 以 $w$ 為根的最短路徑樹 <font style="color:red">$T$</font> ---- ## More Lemma 6. 對於 $\alpha > 2$ ， $H$ 為非樹equilibrium graph $G$ 中的 BCC，對於點$v \in V(H)$ ，滿足 $D_G(v)\le rad(G)+2$。 7. 對於 $\alpha > 2$ ， $H$ 為非樹equilibrium graph $G$ 中的 BCC，對於點$v \in V(H)$ 和點 $w \in S(v)$，滿足$d_G(v,w) \le D_G(v) + 2 - \alpha$。 8. 對於 $\alpha > 5$ ， $H$ 為非樹equilibrium graph $G$ 中的 BCC，而在 $H$ 中能找到每條路徑 $[x_0,x_1,...,x_k,x_{k+1}]$ 且 $deg_H(x_i)=2$ for $(1 \le i \le k)$，滿足 $k \leq 3$。此外，如果 $k=3$ ，滿足 $D_G(x_0)=rad(G)$ 且 $D_G(x_{k+1}) \neq rad(G)$ ---- ## Corollary 2. 對於 $\alpha > 5$，$H$ 為非樹的 Equilibrium Graph中的 biconnected component，則對於 $H$ 中的所有點 $v$ ，滿足以下兩點其一 - (a) 存在一點 $u \in N_1(v)$ 滿足 $deg_H(u) \ge 3$ - (b) $deg_H(u) = 2$ for $u \in N_1(v)$ 且 $deg_H(u) \ge 3$ for $u \in N_2(v) \backslash N_1(v)$ $N_k(v) = \{ u \in H | d_H(u,v) \le k \}$ <center>  </center> ---- ## Lemma 9 對於 $\alpha > 5$ ， $H$ 為非樹equilibrium graph $G$ 中的 BCC，$deg(H) \ge 2+ \frac{1}{5}$ 在這裡將根據前面的Lemma 6,7,8 和 Corollary 2 ，將一個 BCC $H$ 的 Average degree 的下界找出來。 ---- $pf.$ 在這邊的prove 我們將考慮利用 BCC $H$ 的點的 degree，創造出新的圖，並利用新圖去計算 Average degree 。 可以將整個 BCC $H$ 裡面的點分成兩類，一類為其 $deg_H = 2$，一類是 $deg_H \ge 3$。 ---- 接下來要建新圖，首先滿足 $deg_H \ge 3$ 的點將 assigned 到自己，而對於點 $v \in V(H)$ 且 $deg_H(v)=2$，如果： - 存在一點 $u \in N_1(v)$ 滿足 $deg_H(u) \ge 3$，則讓 $v$ 與其中一個點 $u$ 連邊 - 否則assigned 到自己 根據以上規則，將得到 $m$ 個星狀點集 $\{V_i\}_{i=1}^m$，每個星狀點集的中心點 $(v_i | 1 \le i \le m)$，和 assigned 到自己的 $deg=2$ 點集 $V_0$ <center>  </center> ---- 接下來需要去數每一個連通塊的 degree ，分為以下三個部分計算 1. 每個星狀點集中心點的 degree 總和 : $\sum_{i=1}^m deg_H(v_i)$ 2. 每個星狀點集的外側 2-degree 點總和 ： $2 \sum_{i=1}^m (\vert V_i \vert -1)$ 3. 剩餘的 2-degree 點總和：$2\vert V_0 \vert$ 因此 $deg(H) = \frac{\sum_{i=1}^m deg_H(v_i)+2 \sum_{i=1}^m (\vert V_i \vert -1)+2\vert V_0 \vert}{\sum_{i=1}^m \vert V_i \vert + \vert V_0 \vert}$ ---- 接下來就是化簡 <center>  </center> 化簡後將得到 $deg(H)$ 的下界 --- ## Definition of $\ T_H$ $T$ 是一顆以 $v_0$ 為根的最短路徑樹 ($v_0$ 是 Central Vertex )，$T_H$ 是一個 $T \cap H$的子圖，其中 H 是一個BCC。 則 $T_H$ 也是一顆樹。 這邊簡單反證一下 (論文中沒提到，論文說這是個簡單的觀察。) 如果 $T_H$ 不是樹 (同下圖)  那會有至少兩條邊連到這個 BCC 內，那此時這張 Biconnected subgraph 就不是最大的，也就是非 Maximum ，那這樣他就不是 BCC ， 所以 $T_H$ 是顆樹。 ---- ## Definition of shopping vertex 對於一顆最短路徑樹 $T$ 上的點 $u$，如果他買了一條非樹邊 (non-tree-edge)，我們就說 $u$ 是 shopping vertex。 ---- ## 4.3 Upper Bound on Average Degree 本部分可證明BCC $H$ 的 $deg(H)$ 有上界 $$2+\frac{2}{\lceil (\alpha-1)/2 \rceil}$$ $T_H$ 是以 $v_0$ 為根的最短路徑樹 $T$，和 BCC $H$ 的交集，其中 $v_0$ 是中心點。 大致上的證明方向是利用這條式子 $$deg(H) = \frac{2(|E(T_H)| + |E(H) \setminus E(T_H)|)}{|V(T_H)|}$$ 其中由於 $T_H$ 是一顆樹， 所以 $|E(T_H)| = |V(T_H)|- 1$，剩下後面的 $|E(H) \setminus E(T_H)|$，也就是 BCC 內的非樹邊個數，只要把這個壓下來，上界就找到了。 ---- ## Lemma 10. 對於 $\alpha > 2$ ， $H$ 為非樹equilibrium graph $G$ 中的 BCC，對於兩個 Shopping vertex $u_1,u_2 \in V(H)$，令 $x$ 為 $u_1,u_2$ 在 $T_H$ 上的最近共同祖先(lowest common ancestor 簡稱 lca)，滿足下列式子$max\{d_{T_H}(u_1,x),d_{T_H}(u_2,x)\} \ge \frac{\alpha-1}{2}$ 。 ----  ---- 11. 對於 $\alpha > 2$ ， $H$ 為非樹 Equilibrium graph $G$ 中的 BCC，滿足 $deg(H)< 2 + \frac{2}{\lceil (\alpha-1)/2 \rceil}$ ---- $pf.$ $u$ 是一個 shopping vertex，我們定義 $A(u)=\{w \ | \ (\ w \ = \ u )$ 或 $w \ 是 \ u \ 在 \ T_H \ 的 祖先 \ 且 d_{T_H}(u,w) < (\alpha-1)/2 \ \}$， 其中 $|A(u)| = \lceil (\alpha-1)/2 \rceil$。 註，由於 Lemma 2 告訴我們，環長至少會有 $2 \alpha - 1$ 這麼長，又由於這條 $A(u)$ 構出來的路會落在某個環上，所以一定能保證 $|A(u)|$ 能蒐集到 $\lceil (\alpha-1)/2 \rceil$ 這麼多個點。 如果，對於任意兩個不同的 shopping vertex $u_1$、$u_2$，他們的 $A(u_1) \cap A(u_2) = \phi$ 則BCC H 內的 shopping vertex 的數量會有 $\frac{|V(H)|}{\lceil (\alpha-1)/2 \rceil}$ 這麼多個。 ---- 因為這代表每個 shopping vertex 都要有一條到 $v_0$ 且不跟他人重疊的道路 (BCC內)，而道路最小必須得長 $\lceil (\alpha-1)/2 \rceil$ ，所以會至多有 $\frac{|V(H)|}{\lceil (\alpha-1)/2 \rceil}$ 這麼多條路，等價就是有至多這麼多 shopping vertex。 <center>  </center> ---- 既然 shopping vertex 的數量被壓制住了，我們就能來壓 degree，你會發現，shopping vertex 買的那條非樹邊，會連到另一個 shopping vertex上，所以湊出最多 degree 的辦法就是，所有 shopping vertex 都連到同一個 shopping vertex 上，假設 shopping vertex 有 $n$ 個，那這樣湊出的 degree 就會是 $2(n-1)$ ，也就是 $< 2|V(H)|/\lceil (\alpha-1)/2 \rceil$。 $\begin{multline*}deg(H) = \frac{2(|E(T_H)| + |E(H) \setminus E(T_H)|)}{|V(T_H)|}\\ < 2 \ + \frac{2}{\lceil (\alpha-1)/2 \rceil} \end{multline*}$ ---- 前一頁提到的連到同一個點 (vertex 0) <center>  </center> ---- 結束了嗎? 還沒。 前面說，對於任意兩個不同的 shopping vertex $u_1$、$u_2$，他們的 $A(u_1) \cap A(u_2) = \phi$，假設 $A(u_1) \cap A(u_2) \neq \phi$，則會有個 $x \in A(u_1) \cap A(u_2)$，且 $x$ 為 $u_1、u_2$ 的 lca，然後 by lemma 10， $max\{d_{T_H}(u_1,x),d_{T_H}(u_2,x)\} \ge \frac{\alpha-1}{2}$ 所以 $x$ 不能屬於 $A(u_1) \cap A(u_2)$，這違反了 $A(u)$ 的定義，所以矛盾。 也就是 $A(u_1) \cap A(u_2) = \phi$ ，所以根據上一頁，上界就被找出來了。 --- ## 4.4 Tree Nash Equilibria and Price of Anarchy 最後了 - Theorem 1 : 對於 $\alpha > 19$ ， 任意 equilibrium graph 皆為一棵樹。 $pf.$ $\alpha > 19 \Rightarrow \frac{\lceil \alpha - 1\rceil}{2} \ge 10$，By Lemma 11 對於任意的 BCC $H$ $deg(H)<2+\frac{1}{5}$ 這和 Lemma 9 矛盾，所以沒有 BCC，equilibrium graph 是一顆樹。 ---- ## Lemma 12. $For \ \alpha \le \frac{2}{n-2}$ 則完全圖會是社會福利最大化。 $For \ \alpha \ge \frac{2}{n-2}$ 則星狀圖會是社會福利最大化。 ## Lemma 13. $\begin{split} For \ \alpha < \frac{1}{n-2}, PoA = 1 \\For \ \alpha < \frac{2}{n-2},PoA \le 2\end{split}$ 註:Lemma 12、13 來自 Demaine, E.D., Hajiaghayi, M., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games.ACM Transactions on Algorithms (TALG) 8(2), 1–13 (2012)。 ---- - Theorem 2 : 如果所有是樹的 equilibrium graph ，其 $PoA < 3$ 。 $pf.$ 略... --- 謝謝大家