基于可信度方法在嚴格優勢策略中的算法研究

李虎陽，常永虎

（遵義醫科大學醫學信息工程學院，遵義563000）

0 引言

文獻[1]在限定收益的情況下，討論可信度對重復博弈的影響，要求雙方在選擇忠誠策略時的總收益大于一個選擇忠誠，一個選擇背叛時的總收益。但重復博弈更多的是對單次博弈的重復，本文不失一般性地討論重復博弈，分析了在可信度方法下，參與人能夠從嚴格優勢策略中選擇其他策略。

囚徒困境是博弈中經典的案例之一，對它的描述如下：警察在案發現場逮捕了兩位嫌疑人，但沒有足夠的證據對他們進行判罰，警察將他們關押在不同的房間進行審訊，以保證他們之間不能溝通。警察分別告訴每個人采取的策略及其收益：如果兩個人都坦白，因為證據充分，每個人將會被判處8年的監禁；如果兩個人中有一個坦白，一個抵賴，則坦白的會被立刻釋放，抵賴的被判處10年監禁；如果兩個人都抵賴的話，因為證據不足，每個人將被判處1年監禁。根據以上描述，我們使用二維矩陣表1表示。

如表1所示，參與人A與參與人B的收益一致。以參與人A為例，在單次博弈中，作為理性的參與者，選擇“坦白”策略時，其收益分別為-8（B選擇坦白）和0（B選擇抵賴）總是大于A選擇“抵賴”的收益-10（B選擇坦白）和-1（B選擇抵賴），同理于參與者B，因此最后兩個參與人都會選擇“坦白”策略，且（坦白，坦白）是該博弈的Nash均衡點，但實際上（抵賴，抵賴）能夠使兩個參與人的收益最大，該案例說明個人最優策略并不會導致集體最優。

表1

但如果多次進行上述博弈的話，結果可能不太一樣。在重復博弈中，每個參與人都能夠知道其他參與人的歷史策略，因此會根據其他參與人的歷史策略，在下輪博弈中，懲罰或者獎勵其他參與人，最終可能會打破單次博弈的均衡，獲取全局最優。

可信度是對人或者事物的信任程度，其往往由經驗或歷史行動策略決定。在實際生活中，參與人對于懲罰和獎勵總是不對稱的，當發現其他參與人選擇背叛時，往往會選擇比較嚴厲的懲罰策略，并迅速降低其可信度，但其他參與人選擇忠誠時，并不能迅速提高其可信度。

1 博弈與可信度

1. 1 博弈

定義1：博弈（Game Theory）是指參與人在一定的條件下，采取規則允許的行動策略，并從中獲得相應收益的過程，可以用一個三元組表示：

G={P，S，U}

其中P是參與者集合，P中的每一個元素表示一位參與者；S是行動策略集合，每個參與者可供選擇的策略集；U是收益集合，表示在博弈中，所有參與者在選擇某個行動策略后，各個參與者的收益。

以囚徒困境為例，P={A，B}，S={坦白，抵賴}，U={Ua{坦白，抵賴}=Ub{抵賴，坦白}=0，Ua{抵賴，坦白}=Ub{坦白，抵賴}=-10，Ua{坦白，坦白}=Ub{坦白，坦白}=-8，Ua{抵賴，抵賴}=Ub{抵賴，抵賴}=-1}。在該博弈中，參與者都完全了解對方的行動策略以及收益函數且該博弈只進行一次，因此該博弈是完全信息靜態博弈，其中（坦白，坦白）是該博弈的Nash均衡點。

重復博弈是動態博弈的一種特殊情況，是指在收益相同的情況下進行多次博弈的過程。參與人在每次博弈前，都知道歷史博弈結果，且參與人的行動是同時進行的，因此參與者在選擇策略時，會根據其他參與者的歷史策略進行選擇，同時還會考慮當前自己的行動策略對后續博弈的影響，因為自己的某一個背叛或者違約行為，都可能被其他參與人在未來進行報復。

1. 2 Nash均衡點

在博弈中，假設每個參與者都是理智且是自私的，參與者之間不存在利益承諾等其他外部因素，每個參與者在選擇行動策略總是考慮是自己的收益最大。

定義2：在一個n人博弈中，如果存在行動策略s={s1,s2,…,si,…,sn}，在其他參與者不改變策略的情況下，對每一個參與者i，不存在s’i策略使得參與者i的收益大于si的策略，則s稱為該博弈的Nash均衡點。

Nash均衡屬于非合作博弈均衡，博弈雙方都不會改變自己的策略，因為單方面改變自己策略時，會導致自己的收益下降。囚徒困境中，坦白策略是每個參與者的嚴格優勢策略，它是指無論對方采取何種策略，自己采取坦白這種策略總比其他任何策略要好，因此（坦白，坦白）成為本博弈的Nash均衡點，但是在重復博弈中，該Nash均衡點將可能被打破，最終會趨向于集體最優。

1. 3 可信度

在實際生活中，人們更希望與誠信的博弈方進行博弈，最終以實現雙贏，參與者認為博弈方是否誠信，往往根據博弈方的歷史策略，或者第三方的推薦建立對博弈方的信任程度，即可信度。可信度是指參與者對其他參與者的相信程度，根據其他參與者的歷史選擇相信為真的程度。在重復博弈中，每個參與者都相信自己的每次行動策略會影響到自己的可信度，且博弈方會根據自己的可信度在下輪博弈中采取對自己有利或者不利的行動策略。

定義3：λ是博弈中參與人A對參與人B選擇某個策略的可信度，其中λ∈[-1,1]。

λ=-1，表示A對B選擇某個策略完全不信任；λ=0，表示A對B選擇某個策略一無所知，無法確定；λ=1，表示A對B選擇某個策略完全信任。

2 算法分析

2. 1 原始博弈

在囚徒困境的單次博弈中，我們分析知道，對每個參與者來說，選擇坦白的收益永遠大于抵賴的收益。我們可以通過圖像更直觀地表示，以參與人A為例，假如B以x的概率選擇坦白（h），那么B選擇抵賴（d）的概率為1-x，則可以得到如下內容：

參與人A選擇坦白的收益：f(h)=-8x-0*(1-x)；

參與人A選擇抵賴的收益：f(d)=-10x-1*(1-x)。

其中 x∈[0,1]，通過圖 1可知，f(d)＜f(h)在 x∈[0,1]上恒成立，即無論參與人B選擇何種策略，參與人A選擇坦白的收益恒大于選擇抵賴時的收益，與之前的分析一致。

圖1參與人選擇坦白與抵賴時的收益

2. 2 帶可信度的重復博弈

在原始博弈中，任何一個參與者選擇坦白的收益均大于選擇抵賴時的收益，因此在單次博弈中，最終導致參與者們并不能達到集體最優，但是在重復博弈中，上述情況可能會得到改善。

依然以囚徒困境為例進行重復博弈，在每輪博弈前，參與人都了解其他博弈方的歷史決策，并依據博弈方的歷史決策建立可信度。λ是參與人A對參與人B選擇坦白策略時的可信度，λ=-1表示參與人A完全不相信B會選擇坦白；λ=0表示參與人A對B選擇何種策略一無所知；λ=1表示參與人A完全相信B會選擇坦白。且當A以λ的可信度相信B會選擇坦白時，則同時以-λ的可信度相信B會選擇抵賴，則可以得到以下內容：

參與人A選擇坦白的收益：

參與人A選擇抵賴的收益：

如果希望參與人A在重復博弈中選擇抵賴時的收益大于坦白時的收益，則需要滿足 f(d)>f(h)，即：

圖2參與人A的收益

通過分析可知，在重復博弈中，參與人在選擇策略時，不僅僅會考慮在每輪博弈中自己的收益，會更多考慮博弈方的可信度，依據歷史情況動態修改可信度，以便在下輪博弈中選擇更合適的策略，使自己收益最大，同時也會考慮自己的選擇對后續博弈的影響，因此可信度的出現，將會約束參與人更加理性地選擇自己的策略。

3 結語

在單次囚徒困境博弈中，（坦白，坦白）策略是該博弈的Nash均衡點，在沒有其他參與人改變策略的情況下，該策略使得參與人的收益最大，每個參與者都僅僅只考慮當前策略對自己收益的影響，盡可能使自己的收益最大化。在基于可信度方法的重復博弈中，參與人不僅僅只關系當前策略對自己收益的影響，會更多考慮博弈方在后續博弈中采取的策略，而博弈方采取有利或者不利于自己的策略又與自己的歷史策略有關。

本文集中討論了在重復博弈中，利用可信度方法將打破單次博弈中的Nash均衡點，最終使整個系統趨向整體最優，但本文沒有考慮根據其他參與人的歷史策略如何修正可信度，以體現博弈方的策略在未來的博弈中給予獎勵或者懲罰措施，下一步工作將討論如何修正可信度的方法。