方教授首先從動態規劃的背包問題(knapsack game)談起，此問題屬於
NP-hard的問題，可假設有個人發現一堆寶藏，但他身邊只有一個有限大的
袋子，要如何裝才能使價值最大？聽完這情境，我則聯想到有個小偷要偷
保險箱內的東西，其中有n種不同大小和價值不同的東西可偷，但是他只有
一個大小容量為m的小背包可把東西搬走。「背包問題」便是找出這個小偷
該偷些什麼，裝入他的背包中，使得偷到的東西價值最高。
接著，有一就有二，繼續介紹延伸出來的雙方競爭模式，如此一來問
題變得複雜許多。首先雙方競爭的方式可分為：1. 以自我為中心，2. 差
異最大， 3. 總和最大等三種策略，而問題所關注的焦點為：1. 競爭過程
中，雙方如何相互影響對方的決策？以及2. 是否有可能到達穩態(stable)
系統？
後者可以賽局理論的Nash Equilibrium來測試，但同時又牽扯到一個
新的問題：如何找fitness function？方教授又導入1和2兩個新指標
，表示競爭者雙方對價值的主觀認定。若Δ1Δ2 ≧ 0 (同號)，表示雙方
看法一致，也就代表stable存在；反之，若Δ1Δ2 < 0(異號)，則它並非
穩定賽局。
以上討論是假設無政府干預的前提。另外，若以社會的總體角度來看
，社會代價(price of anarchy)是必須列入考量的重要指標，它與現實生
活亦存在極大的關聯。根據方教授多年研究，導出一個有趣的結論：當兩
家廠商都以自我為中心，不管對方死活時，所需付出的社會成本為1/3，而
當兩家廠商採差異最大或總和最大時，相互影響之下，造成社會成本付出
增為1/2，龍爭虎鬥的結果必然付出代價，道理雖然憑直覺就能猜想，但我
卻沒想過理論上竟然也有方法可證明。這也給了我一個新概念，說明user
optimal和system(social) optimal間可謂魚與熊掌不可兼得。
那麼進一步再延伸，若競爭者為三方以上，又形成怎樣的情勢？方教
授留下了想像空間。不過這複雜度應該會暴增吧，就好比五子棋大家都玩
過，不過六子棋可能就比較?為人知。印象中規則是：除了第一次黑方下
一顆子外，之後黑白雙方輪流每次各下兩子，先連成６子者獲勝。這規則
的一個重要特性是，每當一方下出一步（兩子）時，該方一定比對方多出
一顆子。很自然使得六子棋具有相當的公平性，不會偏向某個玩家。但相
較於五子棋，策略運用更多元，盤面變化性更複雜。
除了將問題擴大延伸，訂定更有效的指標，找出更快速的方法求解外
，方教授結尾時還說：「定義新問題」層次更高！引人深思。
2007/10/29
沒有留言:
張貼留言