title: 博弈論 斯坦福game theory stanford week 2-0

tags: note

notebook: 6- 英文課程-15-game theory

---

博弈論 斯坦福game theory stanford week 2-0

混合政策和納什均衡

一個例子

我們從一個例子說起，我們說美國人為了保護自己的利益，在索馬裡設卡安檢，我們不妨考慮這樣的博弈問題，說在索馬裡有很多的路段，安檢者和恐怖襲擊者是博弈者。如果襲擊和安檢發生在同一地點，那麼襲擊者會受到損失，如果不是，襲擊者會得到好處。對于檢查者問題正好相反。

但是由于沒有相應的情報支援，兩者的決策隻能依靠随機進行，并不會産生固定的決策，這樣的政策稱為混合政策。

混合政策，

Kv

就像上面的例子一樣，我們考慮這個決策問題：

兩個人的利益看起來并不能通過固定的選擇方式進行分割，隻能通過随機的選擇，這樣就是混合政策。

下面我們定義下這種決策，

• 決策：

  

  ，決策是行動

  

  的一個随機變量
• 純政策： 在機率中隻有一個行為可以采用。

• 混合政策： 在我們的政策中，可以采用多種政策。

  在這些政策中，所有的行為稱為政策的支撐。

我們還要定義所有的政策

我們還要定義所有政策的收益

在上述的情況下，我們可以對我們的收益和支出進行機率性的讨論。

我們可以定義期望的收益如下：

第一行的公式是說，目前的收益是所有的行為帶來的利益的權重平均值，第二行說我們可以使用貝葉斯公式來計算每一個的可能性。

最優響應和納什均衡

借助最優相應的機率，我們将上述的機率化思想融入進來，

得到一個定理：

每一個完整的博弈都有一個納什均衡

完整的博弈的定義是什麼：隻要一個博弈，擁有一定的數量的博弈者，有着一定的行為，有着完整的收益矩陣，那麼就是一個完整的博弈。

做一個說明：我們之前說的沒有納什均衡是說沒有純粹的納什均衡，但是它可以有混合的納什均衡。

比如我們前面提到的例子，如下圖：

我們的混合的納什均衡就是：

這個樣子的

要強調混合的機率是随着不同的問題決定的，那麼混合的機率是如何決定的呢，我們可以認為當所有的博弈者都不願意再改變他們的機率的時候，就陷入了納什均衡。

納什均衡的計算

通過這樣的一個示例我們讨論納什均衡的計算方法：

我們不得不說再一般的條件下，納什均衡是十分難以計算的，不過如果你合一對支援進行猜測的情況下，我們可以相對容易的計算納什均衡。

再上圖情況下，我們假設讓一個人選b的機率為

，選F的機率就是

再這個情況下，另外一個決策者用混合政策來考慮這個問題，他需要保證對方這兩種博弈行為對自己來說是一種平衡的收益，因為隻有這樣，另外一個博弈者的收益才不會因為對方的選擇而發生改變。是以我們采用如下的政策列出方程:

使用混合政策的原因

• 通過随機性來迷惑你的對手
• 通過随機性來應對不确定性

多方博弈問題

兩個例子

線性補充問題（linear complementarity problem）

支援計數方法（support enumeration method）

PPAD問題

美國加州大學伯克利分校的克裡斯托斯·帕帕迪米特裡歐(Christos Papadimitriou) 教授定義了PPAD（polynomial parity arguments on directed graphs，有向圖的多項式校驗參數）計算複雜類來描述經濟學中的計算問題。并與其合作者一起證明了在4 人及以上的博弈中，納什均衡的計算是屬于PPAD-Complete 的。

通過上述的圖檔可以看到，PPAD問題是一類NP問題。

簡要的發展曆史

1. 1928：von 提出兩個人的零和博弈的均衡問題
2. 1950：nash 再所有博弈種類提出多人博弈的均衡問題

lemke-howson 算法

LCP問題，線性補充方程問題

其中

代表了第i個人使用方案k的機率。

Ai代表了每一個博弈者的行為，那麼

就表達當博弈者1采用j政策的平均獲得。

代表了納什均衡中的獲得，進而

代表了兩者的差距

好吧這裡我們先跳過去。

~~

納什均衡的用例

點球問題

我們可以将點球問題當作是一個博弈的問題，對于一個點球來說，守門員撲球的方向和球員踢球的方向是一種博弈，如果兩者方向相同，那麼球有更大的幾率被撲出。

問題簡化成上述圖檔

上述問題是我們已經讨論過的了，機率是0.5 0.5，不過如果問題程式設計了這個樣子呢，如圖：

我們将其中一個，也就是我們認為踢球者的右腳水準比較差，可能不會百分百進球，那麼博弈的納什均衡會發生什麼呢？

我，我們發現納什均衡點發生了移動，守門員傾向于撲向右邊。而球員傾向于撲向左邊。

分别是3/7 4/7 和4/7 3/7