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

李虎陽(yáng)，常永虎

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

0 引言

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

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

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

表1

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

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

1 博弈與可信度

1. 1 博弈

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

G={P，S，U}

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

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

重復(fù)博弈是動(dòng)態(tài)博弈的一種特殊情況，是指在收益相同的情況下進(jìn)行多次博弈的過(guò)程。參與人在每次博弈前，都知道歷史博弈結(jié)果，且參與人的行動(dòng)是同時(shí)進(jìn)行的，因此參與者在選擇策略時(shí)，會(huì)根據(jù)其他參與者的歷史策略進(jìn)行選擇，同時(shí)還會(huì)考慮當(dāng)前自己的行動(dòng)策略對(duì)后續(xù)博弈的影響，因?yàn)樽约旱哪骋粋€(gè)背叛或者違約行為，都可能被其他參與人在未來(lái)進(jìn)行報(bào)復(fù)。

1. 2 Nash均衡點(diǎn)

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

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

Nash均衡屬于非合作博弈均衡，博弈雙方都不會(huì)改變自己的策略，因?yàn)閱畏矫娓淖冏约翰呗詴r(shí)，會(huì)導(dǎo)致自己的收益下降。囚徒困境中，坦白策略是每個(gè)參與者的嚴(yán)格優(yōu)勢(shì)策略，它是指無(wú)論對(duì)方采取何種策略，自己采取坦白這種策略總比其他任何策略要好，因此（坦白，坦白）成為本博弈的Nash均衡點(diǎn)，但是在重復(fù)博弈中，該Nash均衡點(diǎn)將可能被打破，最終會(huì)趨向于集體最優(yōu)。

1. 3 可信度

在實(shí)際生活中，人們更希望與誠(chéng)信的博弈方進(jìn)行博弈，最終以實(shí)現(xiàn)雙贏，參與者認(rèn)為博弈方是否誠(chéng)信，往往根據(jù)博弈方的歷史策略，或者第三方的推薦建立對(duì)博弈方的信任程度，即可信度。可信度是指參與者對(duì)其他參與者的相信程度，根據(jù)其他參與者的歷史選擇相信為真的程度。在重復(fù)博弈中，每個(gè)參與者都相信自己的每次行動(dòng)策略會(huì)影響到自己的可信度，且博弈方會(huì)根據(jù)自己的可信度在下輪博弈中采取對(duì)自己有利或者不利的行動(dòng)策略。

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

λ=-1，表示A對(duì)B選擇某個(gè)策略完全不信任；λ=0，表示A對(duì)B選擇某個(gè)策略一無(wú)所知，無(wú)法確定；λ=1，表示A對(duì)B選擇某個(gè)策略完全信任。

2 算法分析

2. 1 原始博弈

在囚徒困境的單次博弈中，我們分析知道，對(duì)每個(gè)參與者來(lái)說(shuō)，選擇坦白的收益永遠(yuǎn)大于抵賴的收益。我們可以通過(guò)圖像更直觀地表示，以參與人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]，通過(guò)圖 1可知，f(d)＜f(h)在 x∈[0,1]上恒成立，即無(wú)論參與人B選擇何種策略，參與人A選擇坦白的收益恒大于選擇抵賴時(shí)的收益，與之前的分析一致。

圖1參與人選擇坦白與抵賴時(shí)的收益

2. 2 帶可信度的重復(fù)博弈

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

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

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

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

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

圖2參與人A的收益

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

3 結(jié)語(yǔ)

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

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