基于可信度的多次重复博弈研究*

李虎阳， 罗　旭， 常永虎

(遵义医学院 医学信息工程系, 贵州 遵义 563003)



基于可信度的多次重复博弈研究*

李虎阳， 罗旭**， 常永虎

(遵义医学院 医学信息工程系, 贵州 遵义 563003)

摘要：提出了一种基于可信度的多次重复博弈算法，通过参与人在每轮博弈中采取的行动策略统计其可信度，参与人下一轮的行动策略与其可信度有关，根据可信度建立相应奖惩机制，单方面提高参与人收益会造成可信度下降，同时证明了在重复博弈中最终趋向于帕累托最优.

关键词：重复博弈；Nash均衡；可信度；帕累托最优

“囚徒困境”模型是非合作博弈中的经典案例，参与人的不合作行动导致双方坦白，该模型展示了个体利益与群体利益的冲突，说明了个体收益最优并不能带来整体最优.如果双方通过多次重复博弈，建立起足够的信任关系，或者说每个参与者都有机会去“惩罚”另一个参与者前一回合的不合作行为，则合作可能会作为均衡的结果出现，这时欺骗的动机可能会被受到惩罚的威胁有所克服，从而可能导向一个较好的、合作的结果.反复博弈次数接近无限时，纳什均衡趋向于帕累托最优.

重复博弈可以是完全信息博弈，也可以是非完全信息博弈.在“囚徒困境”模型中，每个参与者都知道所有其他参与者的特征、策略及效用函数等方面的准确信息，并了解之前博弈的所有情况.参与者每轮采取的行动决定其可信度，并根据其他参与者的可信度决定行动策略.

1可信度

可信度方法是E.H.Shortliffe等人在确定性理论的基础上，结合概率论提出的一种不确定性推理方法，人们在长期的实践活动中，对客观世界的认识积累了大量的经验，当一个新事物或新情况出现时，往往根据以往的经验对问题的真、假或为真的程度做出判断，判断一个事物的为真或假的程度称为可信度[1].

关于定义1的几点说明：

1)Cij(a)=0，表示i对j选择a完全不信任；Cij(a)=1，表示i对j选择a完全信任；Cij(a)=0.5，表示i对j选择a完全不可知；

2) 当A由多个元素组成时，C(A)不包括对A子集的信任度，而且也不知道该对它如何进行分配.如设Ω={a,b}，C(∅)=0，C(a)=0.3，C(b)=0.1，C(a,b)=0.6，其中C(a,b)=0.6不包括对a的信任度0.3，也不包括对b的信任度0.1，而且也不知道把0.6分配给a还是b.

可信度的定义类似于证据理论里的概率分配函数，表示对每个元素确定或者不确定情况的一种描述.

2博弈与Nash均衡

博弈论(Game Theory)是指在一定条件下，参与人根据允许的规则选取相应的行动策略，并从中获取相应收益的过程.

定义2在一个n人的博弈标准式表述中，参与人的策略空间为S1,S2,…,Sn，收益函数为u1,u2,…,un，用G={S1,S2,…,Sn;u1,u2,…,un}表示此博弈[2].

在博弈中，假设每个参与人都是理智并且都是自私的，每个参与人都会选择有利于自己的行动策略，因此在博弈中最终会达到一个稳定的状态——Nash均衡，即在该状态下，所有其他人都不改变策略时，没有人会改变自己的策略.

如两家企业合作生产某产品，如果两家都按照合同执行，则双方获利5万元，如果一方按照合同执行，一方违反合同生产，则前者亏损2万元，或者获利8万 元；如果双方都毁约，则双方获利都为0元(表1).

表1　厂家博弈收益矩阵

通过表1所示的双矩阵描述，习惯上将(a，b)中a代表行参与人的收益，b代表列参与人的收益.在上述单次博弈中，依据定义3，表1中(d，d)是其唯一的Nash均衡，其收益为(0，0)，即每个厂家都担心对方欺诈而选择欺诈，最终导致每个参与人的收益均为0，说明了个体收益最优并不能带来集体最优，即典型的囚徒困境模型.但现实中(h，h)才是双赢的选择，出现(d，d)的原因在于单次博弈中，每个参与人都是足够自私和理智的，是一种非合作状态下的博弈.

3重复博弈与子博弈精练Nash均衡

3.1重复博弈

改变(d，d)状态的一个更常用的模型是重复博弈，在该模型下，各参与人都满足[3]：

1) 博弈G在进行第T次博弈时，参与者都能够观察到T次以前博弈的结果；

2) 参与人是同时行动的；

3) 博弈关系被打破是随机的.

不失一般性，令u(h,h)=θ，u(h,d)=-ω，u(d,h)=μ，u(d,d)=0，且参数满足诚实的双方受益总和大于一方诚实一方欺诈的收益和2θ>μ，其中μ>θ>ω>0.每轮博弈前，参与人依据对对方的可信度选择诚实还是欺诈的行动策略.

各个参与人在每轮博弈前，更新其可信度，并依据可信度决定对其他参与人进行奖励或者惩罚，当C(h)<0或C(h)

由定义4和定义5可知，诚实次数越多，对其可信度越高，反之可信度越低.

3.2子博弈精练Nash均衡

1) 它是原博弈的Nash均衡；

2) 它在每一个子博弈上构成Nash均衡.

如果博弈无限进行下去，博弈双方都会采用相互合作的策略进行博弈，合作策略成为唯一的Nash均衡，即子博弈精练Nash均衡，是得到证明存在的.

4证明

下面给出厂家无限重复博弈中诚实策略为子博弈精炼Nash均衡的具体证明.

因此，通过多次重复博弈最终趋向帕累托最优.

5总结

提出了一种基于可信度的重复博弈算法，参与人的每一轮博弈都直接影响到下一轮博弈的收益，参与人依据对其他参与人的可信度而采取相应的行动策略，通过完美信息重复博弈，最终趋向帕累托最优.同时发现，当欺诈带来的利益足够大时，需要建立有效的惩罚措施.由于没有考虑到间接可信度，所以在下一步工作中将考虑第三方的推荐可信度，采用数据融合算法使结论更完善.

参考文献(References)：

[1]王万良.人工智能及其应用[M].北京：高等教育出版社，2005

WANG W L.Artifical Intelligence Principles and Applications[M].Beijing:Higher Education Press,2005

[2] 陈武，周敏，李虎阳.一种基于回答集程序的三方协商新机制[J].西南大学学报：自然科学版，2014,36(5)：1-6

CHEN W,ZHOU M,LI H Y.A New Three-party Negotation Mechanism Based on Answer Set Program[J].Journal of Southwest University(Natural Science Edition),2014,36(5):1-6

[3] 陈波，朱卫东，张洪涛.基于证据理论的多Agent重复囚徒困境博弈研究[J].系统工程学报，2009,24(6):653-659

CHEN B,ZHU W D,ZHANG H T.Iterated Prisoner’s Dilemma Game with Multi-agent Based on Evidence Theory[J].Journal of Systems Englineering,2009,24(6):653-659

[4]王保玉，高承实，戴青，等.基于无限重复博弈的P2P网络信任模型研究[J].计算机应用研究，2013,30(9):2802-2804

WANG B Y,GAO CH SH,DAI Q,et al.Research on Trust Model Based on Infinitely Games Theory in P2P Networks[J].Application Research of Computers,2013,30(9):2802-2804

[5] 陈晶，杜瑞颖，王丽娜，等.网络环境下一种基于概率密度的信任博弈模型[J].电子学报，2010(2):427-433

CHEN J,DU R Y,WANG L N,et al.A Trust Game Method Basing on Probability Model in Networks[J].ACTA ELECTRONICA SINICA,2010(2):427-433

责任编辑：李翠薇

Research on Multiple Repeat Games Based on Credibility

LI Hu-yang, LUO Xu, CHANG Yong-hu

(Department of Medical and Information Engineering, Zunyi Medical University, Guizhou Zunyi 563003, China)

Abstract：This paper proposes a multiple repeat game algorithm based on credibility, calculates the credibility through the acting strategy of participators in each round of game, indicates that the acting strategy of the participators of next round is related to their credibility and that the unilaterally increasing of the participators’ gain can result in the decrease of their credibility according to the relative rewards and punishment mechanism based on the credibility, and proves that the repeat games ultimately trend to Pareto Optimality.

Key words：repeat game; Nash Equilibrium; credibility; Pareto Optimality

中图分类号：TP181

文献标志码：A

文章编号：1672-058X(2016)01-0070-04

作者简介：李虎阳(1986-)，男，湖南邵阳人，硕士，从事不确定性推理研究.**通讯作者：罗旭(1986-)，男，湖北人，副教授，博士，从事无线传感器网络研究．E-mail:henry163@swu.edu.cn.

*基金项目：国家自然科学基金(61463053).

收稿日期：2015-05-12；修回日期：2015-09-24.

doi:10.16055/j.issn.1672-058X.2016.0001.015