基于可信度方法在嚴格優(yōu)勢策略中的算法研究

李虎陽，常永虎

（遵義醫(yī)科大學醫(yī)學信息工程學院，遵義563000）

0 引言

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

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

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

表1

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

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

1 博弈與可信度

1. 1 博弈

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

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}。在該博弈中，參與者都完全了解對方的行動策略以及收益函數(shù)且該博弈只進行一次，因此該博弈是完全信息靜態(tài)博弈，其中（坦白，坦白）是該博弈的Nash均衡點。

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

1. 2 Nash均衡點

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

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

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

1. 3 可信度

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

定義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，則可以得到如下內(nèi)容：

參與人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 帶可信度的重復博弈

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

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

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

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

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

圖2參與人A的收益

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

3 結語

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

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