Day 16 成本分攤賽局（Cost Allocation Game）

昨日我們看了「市場遊戲」，主要是探討交易者之間結盟，彼此互通有無，則可以創造更大的效益。大家合作是為了「賺更多錢」。今天我們來考慮另一類賽局，大家合作是為了「省下成本」，叫做成本分攤賽局（Cost Allocation Game）

從一個機房租用問題開始

有三間公司 A, B, C，需要租用伺服器機房來擺放設備、維護網路服務。若各自租一間，以下是估計成本（單位皆為萬元）：

他們發現若能合租一個空間，雖然空間要大一點，租金可能會較高，但總價可能比三人分開租要便宜：

A, B 合租：

A, C 合租：

B, C 合租：

A, B, C 大家一起租：

好，但是關鍵是，如果是三人合租，要怎麼分攤成本？

轉換為節省賽局（Saving Game）

注意到上面使用的符號是 c( { ... } ) 而不是 v( { ... } ) 。過去我們談論到特徵函數 v(S) 時，通常是把它當作一種效益，而非成本。上面這些「成本」顯然並不是具有效益性質的量。不過事情也好解決，這裡我們可以定義以下的特徵函數

表示「相比於每個人單獨租機房，合租可以省下多少錢？」。

機場問題（Airport Game）

「Airport Game」是成本分攤賽局中的一個經典範例。假設一座機場需要興建跑道、航站設施，而不同航線或航空公司對跑道長度的需求不一樣。有些只需要 1,000 公尺（輕型飛機即可降落），有些需要 2,000 公尺，甚至 3,000 公尺。跑道要做得越長，成本越高，但航空公司若各自修建，就會浪費更多資源。

假設 N 為所有的航空公司

然後令

（意思就是可能第一間公司只有小飛機， d_1 = 1000 ，第二間有火箭（？），要 d_2 = 5000 ）

如果說有一個聯盟 S 要一起修建跑道，那需要修建長度為

的跑道。那 S 裡面的人使用這條超長跑道的時後，大家應該分擔多少成本呢？

問題建模

假設長度為 l 的跑道修建起來需要 f(l) 的成本，則聯盟 S 的成本函數為

轉換為節省賽局就會是

成本分擔賽局常見的特性

次加性成本 與 超加性節省

若狀況是「兩個聯盟合併在一起所需的成本不會超過各自分開之和」，則可寫出：對於任意兩個無交集的聯盟 S 與 T

這可以推導出「節省賽局為超加性賽局」

反之亦然。

凹性成本 與 凸性節省

若成本函數呈現凹性（玩家加入越多，邊際成本增量越小），也就是對於任意兩個聯盟 S 與 T

這可以推導出「節省賽局為凸性賽局」

反之亦然。

Takeaway

• 成本型賽局可轉換為「節省型」賽局，從而利用效益的角度來分配 v(S)
• 次加性 ↔ 超加性
• 凹性 ↔ 凸性的對應

Reference

Peleg, Bezalel, and Peter Sudhölter. _Introduction to the theory of cooperative games_. Vol. 34. Springer Science & Business Media, 2007.