Day 19 介紹三種與圖論有關的合作賽局
Minimum Cost Spanning Tree Game
想像有一座離島，島上分布著好幾個小漁村（玩家）。島的中央還有一座海水淡化廠（供應端，節點 0），可以提供淡水。現在，漁村們討論是否要一起出資鋪設輸水管線，好把淡化廠的淡水供應到所有村莊。
節點：
我們用節點 0 代表海水淡化廠
用節點 1, 2, 3,... 代表各個漁村
邊與成本：
假設這些點 {0, 1, 2, ...} 形成一個完全圖（意思是每兩個節點之間都有連起來），且每個邊上都有一個成本
現在看看以下的成本圖：
如果村莊二跟村莊三分別自己連線到淡化廠的話，那需七十單位的成本。但是如果他們結盟，並設計出一條更好的路徑（上圖藍色），則總成本變成三十單位。於是，這就變成一個經典的成本分攤賽局（Cost Allocation Game）
我們來把數學寫得更精確一點：
數學模型
考慮一個完全圖
其中每條邊都有一個成本
對於每個 N 中的聯盟 S ，我們定義聯盟成本函數
這種合作賽局就稱為 Minimum Cost Spanning Tree Game
Shortest Path Game
有三家物流公司，各自負責不同區域的貨物運送。現在，他們都想把貨物從「港口」(起點) 運到「市中心」(終點)，但沿途的高速公路或鐵路建設需要成本維護。要是三家公司都各自蓋自己的路段，可能很貴；而若彼此能共享部分路線，總費用就能大幅降低。
假設地理位置如下：三家公司分別要從 s1, s2, s3 送貨到 t1, t2,t3
若三家公司都蓋自己的路段，那結果大概會是：
但是如果三家公司結盟，並修建一個幹道：
則潛在的可能降低所需要的總成本。又是一個 Cost Allocation Game
數學模型
考慮一個完全圖
其中每條邊都有一個成本
有一組玩家 N，其中每位玩家 i 有自己的「路徑需求」：想從 si ∈ V 到 ti ∈ V 連通
對任意子聯盟 S ⊆ N，令他們合力「同時滿足」所有 i ∈ S 的起點—終點連線需求。若不同玩家部分路徑重疊，只需支付一次成本。
於是，聯盟成本函數就可以定義成
這種合作賽局就稱為 Shortest Path Game
## Steiner Tree Game
讓我們回顧第一個賽局中的案例，假設現在兩個漁村與淡水處理廠的地理分布如下。藍色指得是河流，如果搭建的輸送管道通過河流，那個成本會非常高（紅色），可是如果在山上選一著中繼站，然後再送到兩個村莊的話（綠色路徑），則可能總成本還便宜一點。
這種包含中繼站可能性的最小成本賽局就是 Steiner Tree Game，與第一個例子的不同之處就在於這裡有「可能的中繼站」
數學模型
考慮一個完全圖
其中每條邊都有一個成本
而玩家 N 是節點 V 的子集，也就是要被連起來的所有頂點。
我們於是可以定義對於聯盟 S ⊆ N，其聯盟成本為
在這裡 V' 可以包含一些中繼節點，並一定要包含 S 中的玩家。
Reference
Peleg, Bezalel, and Peter Sudhölter. _Introduction to the theory of cooperative games_. Vol. 34. Springer Science & Business Media, 2007.
