隨機演化博弈Petri網模型與算法設計*

任大勇

(渭南師范學院　渭南　714099)

?

隨機演化博弈Petri網模型與算法設計*

任大勇

(渭南師范學院渭南714099)

摘要針對社會經濟生活中參與主體間存在的競爭合作關系,以有限理性條件下二人合作博弈為問題對象,借助隨機Petri構建了隨機演化博弈Petri網模型SEGPN,并通過對模型SEGPN演化博弈分析,提出了對應的隨機演化推理算法,實現了對二人合作博弈演化過程的圖形化表示,勾勒出了局中人演化博弈路徑,為管理決策提供了科學依據。

關鍵詞隨機Petri網; 演化博弈; 演化建模

Class NumberTP391.9

1引言

在之前關于經濟社會生活問題研究中,長期以來假定局中人是完全理性的,局中人之間的博弈是在完全信息下進行的[1],但隨著經濟社會生活復雜性的不斷增加,局中人之間、外部環境、問題本身都存在著較多的不確定性和不完全性。局中人之間更多的時候表現出有限理性條件下的重復博弈,相互間也不是簡單的競爭關系,存在著一種競爭合作的關系形式[2]。對于這樣一種新型的組織合作競爭關系,眾多學者從不同的實際問題出發開展了大量富有成效的研究工作,其中文獻[3]在有限理性條件下,應用進化博弈論模仿者動態模型分析了企業合作競爭博弈的演化過程,用進行穩定策略描述了合作競爭博弈的長期演化趨勢,探討了對稱和非對稱合作競爭博弈的進化均衡與穩定性;文獻[4]從博弈參與人的有限理性出發,探討了合作競爭博弈中復雜性存在的根源,構建了合作競爭博弈的演化模型,分析了一個水平差異化產品的合作競爭博弈的演化均衡;文獻[5]綜述了網絡群體行為和隨機演化博弈模型與分析方法,介紹了可用于網絡群體行為分析評價的指標和模型,探討了應用隨機演化博弈模型進行網絡群體行為研究的可行性。

縱觀以上研究發現,對于社會經濟生活中參與主體間存在的競爭合作的關系,學者們基于不同的問題背景應用演化博弈理論進行了研究,分析了演化博弈的均衡性與穩定性,但對演化路徑的分析特別是對演化路徑的圖形化表示的研究尚有不足。隨機Petri網作為一種具有并行處理能力、圖形化問題描述工具[6～8],受到了越來越多的關注,為此將以有限理性條件下二人合作博弈為問題對象,借助隨機博弈Petri網[9～10]構建隨機演化博弈Petri網模型,通過模型演化博弈分析提出對應的隨機演化推理算法,使用圖形化工具對二人合作博弈演化博弈過程進行描述,為演化路徑的分析研究和管理決策提供科學依據。

2問題描述

有限理性條件下,演化博弈方會通過模仿、學習、策略調整的過程進行動態重復博弈,最終達到博弈的穩定均衡狀態。在現實經濟社會生活中,參與主體往往是隨機變動的,相互之間也不是簡單的競爭的關系,更多的時候還存在著競爭之上的合作關系,多參與主體間的競爭合作關系則屬于一種有限理性下的演化博弈。

在二人合作博弈過程中,局中人A、B出于自身博弈收益最大化的考慮,不大可能在一開始選擇“合作”策略,而會以某一概率值w選擇“合作”策略,則對“不合作”策略的選擇概率為1-w。有限理性的局中人A、B在經過多次博弈后會對博弈收益進行統計分析和事后判斷,收益較差的局中人當發現收益差異時,便會模仿學習收益相對較高的局中人,對博弈策略進行調整。隨著時間的延續局中人會在自身收益最大化的趨勢下,不斷地調整“合作”、“不合作”策略的選擇概率,并最終經過多次的重復博弈雙方達到博弈穩定均衡狀態。在單次二人合作博弈中,局中人A、B的收益矩陣[11]如表1所示。

表1　二人單次合作博弈收益矩陣

3隨機演化博弈模型

3.1模型的定義

隨機演化博弈Petri網模型SEGPN定義為7元組:

SEGPN=(K,P,T,I,O,Θ,W)

其中,K={A,B}為二人合作博弈中的局中人集合;P={p1,p2,p3,…,pn}是庫所的有限集合,表示二人合作博弈中局中人的狀態集;T={t1,t2,t3,…,tm}是變遷的有限集合,表示二人合作博弈中局中人的行為集合。二人合作博弈中局中人可選擇“合作”或“不合作”策略,若TY表示局中人選擇“合作”策略行為,TN表示局中人選擇“不合作”策略行為,則T=TY∪TN,TY∩TN=?;I:P→T為n×m階輸入矩陣,反映了局中人A、B對博弈行為TY、TN的選擇;O:T→P為m×n階輸出矩陣,反映了博弈行為TY、TN對局中人博弈收益的影響,且P∩T=?,P∪T≠?;Θ=(θ1,θ2,…,θn)是局中人A、B在隨機演化博弈狀態pi時的合作收益值,是局中人采取不同行為所產生的合作收益;W:P→T為n×m階pi對tj的輸入權值系數矩陣,W={wij},wij=[0,1],反映了二人合作博弈節點pi對博弈行為tj的選擇概率。若wij=0,表示局中人在狀態節點pi與博弈行為tj間不存在選擇關系;若wij=(0,1],表示局中人在pi狀態節點以概率wij選擇博弈行為tj,且局中人在pk狀態節點對后繼變遷行為的選擇概率滿足wk1+wk2+…+wkm=1。

3.2模型的Petri網表示

圖1　二人合作博弈SEGPN模型圖

3.3模型演化分析

其中,局中人A選擇“合作”策略的期望收益:

E(θYA)=WYBMCA+(1-WYB)UCA

(1)

局中人A選擇“不合作”策略的期望收益:

E(θNA)=WYBUDA+(1-WYB)MDA

(2)

由式(1)、(2)可知,局中人A選擇混合策略的期望收益:

(3)

局中人B選擇“合作”策略的期望收益:

(4)

局中人B選擇“不合作”策略的期望收益:

E(θNB)=WYAUDB+(1-WYA)MDB

(5)

由式(4)、(5)可知,局中人B選擇混合策略的期望收益:

E(θB)=WYBE(θYB)+WNBE(θNB)

(6)

F(WYA)=dWYA/dt=WYA[E(θYA)-E(θA)]

(7)

G(WYB)=dWYB/dt=WYB[E(θYB)-E(θB)]

(8)

4隨機演化推理算法

二人合作博弈隨機演化博弈Petri網模型中,局中人從初始狀態點出發以隨機概率選擇“合作”、“不合作”博弈策略,再次博弈時局中人會依據上次博弈收益對再次博弈策略選擇概率進行調整,以達到自身收益最大化的目標。通過上文的演化博弈分析,我們發現局中人對博弈策略的選擇概率隨時間的變化率與初始合作意愿成正比,與采取“合作”策略博弈收益和混合策略的差異也成正比例關系,為此我們提出可在Matlab下仿真模擬的模型SEGPN隨機演化推理算法。

Step1:根據實際問題得到如表1所示的收益矩陣。

Step3:

For(i=1;i

else

End IF

else

End IF

End For

Step4:使用Matlab繪圖函數描述PL(1,∶)、PL(2,∶),即可發現經過R步的演化博弈后局中人狀態的變化以及局中人演化路徑變化情況。

5結語

有限理性條件下的演化博弈局中人會通過模仿、學習等行為進行動態重復博弈,局中人之間存在著一種競爭合作關系,隨著博弈的持續進行局中人會適時地調整各自博弈策略的選擇概率,以使博弈收益向著有利于自己的方向發展。本文以二人合作博弈為問題對象,借助隨機博弈Petri網對問題進行了建模分析,構建了隨機演化博弈Petri網模型SEGPN,對模型進行了演化博弈分析,提出了對應的隨機演化博弈推理算法,使用圖形化工具描述了演化博弈過程,勾勒了局中人演化博弈路徑,為管理決策提供了科學依據。后續研究可進一步擴展博弈問題類型,或針對實際問題對模型參數進行修正,提出更具針對性的隨機演化博弈模型工具。

參 考 文 獻

[1] 謝識予.有限理性條件下的進化博弈理論[J].上海財經大學學報,2001,3(5):3-9.

XIE Shinyu. Evolutionary Game Theory Under Bounded Rationality[J]. Journal of Shanghai University of Finance and Economics,2001,3(5):3-9.

[2] 王長峰.基于演化博弈理論的產業集群中競爭與合作關系分析[J].科技管理研究,2011(1):176-179.

WANG Changfeng. Analysis on Cooperation and Competition of Clustering Enterprises Based on Evolutionary Game Theory[J]. Science and Technology Management Research,2011(1):176-179.

[3] 程德華.有限理性下的企業合作競爭的進化博弈分析[J].計算機與數字工程,2005,33(5):44-47.

CHENG Dehua. Evolutionary Game Theory Analysis of Cooperation and Competition of Enterprises under Bounded Rationality[J]. Computer & Digital Engineering,2005,33(5):44-47.

[4] 吳昊,楊梅英,陳良猷.合作競爭博弈中的復雜性與演化均衡的穩定性分析[J].系統工程理論與實踐,2004,(2):90-94.

WU Hao, YANG Meiying, CHEN Liangyou. An Analyzes on Complexity and Evolutionary Stability in Co-petition Games[J]. System Engineering Theory and Practice,2004,(2):90-94.

[5] 王元卓,于建業,邱雯,等.網絡群體行為的演化博弈模型與分析方法[J].計算機學報,2015,38(2):282-300.

WANG Yuanzhuo, YU Jianye, QIU Wen, et al. Evolutionary Game Model and Analysis Methods for Network Group Behavior[J]. Chinese Journal of Computers,2015,38(2):282-300.

[6] 施江勇,鮮明,王會梅,等.基于隨機Petri網模型的降質服務攻防效果評估[J].計算機科學,2014,41(7):58-61.

SHI Jiangyong, XIAN Ming, WANG Huimei, et al. RoQ Defense Effect Evaluations Based on SPN Model[J]. Computer Science,2014,41(7):58-61.

[7] 秦益霖,劉坤.基于隨機Petri網的性能與可靠性評價[J].工礦自動化,2004,(3):20-22.

QIN Yilin, LIU Kun. Evaluation of Performance and Reliability Based on Stochastic Petri Nets[J]. Industry and Mine Automation,2004,(3):20-22.

[8] 林闖,李雅娟,單志廣.基于隨機Petri網的系統性能評價[J].清華大學學報(自然科學版),2003,43(4):475-479.

LIN Chuang, LI Yajuan, SHAN Zhiguang. Performance Evaluation of Systems Using Stochastic Petri Nets[J]. Journal of Tsinghua University(Science and Technology),2003,43(4):475-479.

[9] 任大勇.軍民融合視角下資源共享的隨機演化博弈模型[J].渭南師范學院學報,2014,29(7):78-83.

REN Dayong. A Stochastic Model Based on Evolutionary Game about the Sharing of Resource in Civil-military Integration[J]. Journal of Weinan Normal University,2014,29(7):78-83.

[10] 王純子,黃光球.基于粗糙貝葉斯博弈的網絡攻防策略[J].計算機應用,2011,31(3):784-789.

WANG Chunzi, HUANG Guangqiu. Network Attack-defense Strategy Based on Rough Bayesian Game[J]. Journal of Computer Applications,2011,31(3):784-789.

[11] 吳昊,陳良猷.水平差異化產品的市場競爭戰略分析[J].北京航空航天大學學報(社會科學版),2002,15(1):38-41,58.

WU Hao, CHEN Liangyou. Competition Strategy Analyses of Horizontal Differential Market[J]. Journal of Beijing University of Aeronautics and Astronautics(Social Sciences),2002,15(1):38-41,58.

Stochastic Evolutionary Game Petri Net Model and Algorithm Design

REN Dayong

(Weinan Normal University, Weinan714099)

AbstractIn view of the competition and cooperation between the main bodies in the social economic life, the two people are involved in the problem of limited rationality, and the model SEGPN is constructed by random Petri. The stochastic evolutionary reasoning algorithm is proposed. In order to realize the graphical representation of the evolution process of the cooperative game of the two people, the game path of human evolution is sketched out, which provides a scientific basis for management decision.

Key Wordsstochastic Petri net, evolutionary game, evolutionary modeling

* 收稿日期:2015年11月8日,修回日期:2015年12月27日

基金項目:渭南師范學院特色學科建設資助項目(編號:14TSXK03);陜西省教育廳科學研究資助項目(編號:2013JK0115);渭南師范學院校級人文社科研究資助項目(編號:14SKYB10);陜西省軍民融合產業發展研究資助項目(編號:15JMR03);渭南市2015年度基礎研究計劃資助項目(編號:2015JCYJ-11)資助。

作者簡介:任大勇,男,博士研究生,講師,研究方向:Petri網原理及應用等。

中圖分類號TP391.9

DOI:10.3969/j.issn.1672-9722.2016.05.004