Day 1 從囚徒困境談到合資購物：淺談合作賽局

簡介

顧名思義，「合作賽局理論」（Cooperative Game Theory）應該是「賽局理論」（Game Theory）中的一個主題，與「非合作賽局理論」相對。

而當人們談到「賽局理論」時，必定會出現的一個經典案例就是 囚徒困境（Prisoner’s Dilemma），這是非合作博弈中的經典案例。

假設在囚徒困境中的兩名嫌疑犯能「簽訂可執行的協議」並共同保持緘默，便能雙雙獲釋；然而在隔離偵訊下，他們無法信任對方不會背叛，各自理性盤算後都選擇招供，最終結果是兩人都被判刑。

這個例子說明：在缺乏可執行合約的非合作情境下，玩家可能作出對自己當下最有利的策略，卻造成整體效益不佳。若能「允許囚犯之間真正合作」，使承諾具有約束力，或許就能避免這種兩敗俱傷的結局（當然從社會正義上兩個都被逮捕是好事是吧😀）。

我們所介紹的「合作博弈理論」就是藉由玩家之間的合作機制，使得他們能夠簽訂具有約束力的協議，並協調如何分配整體合作所產生的效益。藉此，玩家不再各自為政，而是考慮組成聯盟以追求更大的共同利益，同時透過公平且穩定的分配方式，確保所有成員都願意留在聯盟中，避免有人中途退盟或另起爐灶。

潛在的應用場景

區塊鏈治理：礦工或節點可能組成聯盟，共同維護網路並分享挖礦收益或治理權。

企業合併：企業組成策略聯盟、合併或收購，如何分配利潤、決策權或資源。

政治聯盟：政黨或政治人物組成執政聯盟，協商政策或席次分配。

特徵函數遊戲 Characteristic Function Game

我們需要使用數學模型來建構出「合作賽局」，而最常見的就是「特徵函數遊戲（Characteristic Function Game）」這個建模方式。

但在進入抽象的數學描述前，我們不妨從一個合資購物的例子出發，並思考看看一個「合作賽局」需要哪些元素。透過此案例，我們將觀察哪些因素會影響聯盟形成與價值分配，最後再抽象成數學形式

舉例：合資購物

想像有三位同學：A、B 和 C。他們都想要買一台總價 90 元的裝置（例如某款新上市的電子產品）。假設每個人的預算如下：

• A 擁有 30 元
• B 擁有 60 元
• C 擁有 50 元

誰能單獨購買？

• A 單獨只有 30 元，不足以支付 90 元 → 買不下來
• B 單獨有 60 元，也不足以支付 90 元 → 買不下來
• C 單獨有 50 元，也不足以支付 90 元 → 買不下來

因此，任何一人單獨行動都無法購買。

組隊合作的情況：

• A + B：合計 30 + 60 = 90 元：剛好可以買到這台裝置。→ 買得起
• A + C：合計 30 + 50 = 80 元：仍然不足以支付 90 元 → 買不下來
• B + C：合計 60 + 50 = 110 元：足以購買這台裝置。→ 買得起
• A + B + C：合計 30 + 60 + 50 = 140 元：當然也買得起這台裝置。

購買後的「效益」（Value）：

為了專注在「能否合作買下裝置」這件事，我們可以假設裝置本身對玩家帶來的「使用價值」是 100（可以想像成對他們的總滿意度、或是用此裝置能創造的收益）。只要那個聯盟能成功湊到 90 元買下裝置，就能獲得 100 的總價值；如果無法買下，就只獲得 0。

抽象化為特徵函數遊戲

在「特徵函數遊戲（Characteristic Function Game）」的模型中，我們有：

玩家集合：

特徵函數：

對於 N 的任意子集合 S（稱作「聯盟（Coalition）」），v(S) 表示該聯盟能夠「保證獲得」或「創造」的效益或收益。

在此例中，v(S) 的值如下：

任何單人聯盟 {A}, {B}, {C} 都無法單獨買下裝置，因此

多人聯盟的情況下：

{A, B} 雙人聯盟，合資 30 + 60 = 90 ，夠買，因此

{A, C} 雙人聯盟，合資 30 + 50 = 80 ，不夠買，因此

{B, C} 雙人聯盟，合資 60 + 50 = 110 ，夠買，因此

{A, B,C} 三人聯盟，合資 30 + 60 + 50 = 140 ，夠買，因此

一般定義

一個特徵函數遊戲 G 由兩個元素組成：

其中 N 為所有玩家的集合，而 v 是特徵函數

對於每個聯盟 S （即 N 的子集合）都指定出一個效用 v(S)。

細節上，我們通常也定義

表示無人合作就創造不出收益。

合作賽局中的效用分配問題

延續上面舉的合資購物的例子，你可以看到 AB 聯盟、BC 聯盟、以及 ABC 聯盟都可成功購買到價值一百的裝置，可是接下來呢？他們要怎麼分配這個一百的效用？

這個問題廣義來說，一個聯盟 S 得到聯盟的效用 v(S) 後，他們如何在這個聯盟中分配這個效用 v(S)？這將會是我接下來幾天要討論的主題

Takeaway

合作博弈理論：和非合作博弈不同，核心在於玩家能簽訂具有約束力的協議，並關注「聯盟的形成」與「收益分配」如何進行。

特徵函數遊戲 (Characteristic Function Game) ：包含玩家集合 N 與特徵函數 v ，其中特徵函數會給每個聯盟 S （玩家 N 的子集）指定出一個效用

Reference

Chalkiadakis, Georgios, Edith Elkind, and Michael Wooldridge. _Computational aspects of cooperative game theory_. Morgan & Claypool Publishers, 2011.