ABSTRACT

The paper researches the refined Bayesian Nash equilibrium of determining traveler’s route choice behavior under imperfect information. The opaque information between two players becomes an important factor which decides the final path choice. Let the route choice process under the imperfect information be the dynamic game process under the incomplete information, first, we analyze the gains obtained in the traveler route choice, then by using the knowledge of the game tree, the Nash equilibrium in dynamic game is determined under the condition of incomplete information, and furthermore whether the Nash equilibrium is the refined Bayesian Nash equilibrium is determined.

Keywords:Route Choice, Dynamic Game, Incomplete Information, Refined Bayesian Nash Equilibrium

出行路径选择的精炼贝叶斯纳什均衡

王茹心，孙军霞，陈京荣

兰州交通大学数理学院，甘肃 兰州

收稿日期：2016年10月27日；录用日期：2016年11月9日；发布日期：2016年11月18日

摘 要

本文研究在不完美信息下确定出行者路径选择行为的精炼贝叶斯纳什均衡。博弈双方之间的信息不透明成为决定最终路径选择的重要因素。将不完美信息下博弈双方路径选择过程视为不完全信息下的动态博弈过程，首先对出行者出行路径选择获得的收益进行分析，然后运用博弈树的知识，在不完全信息条件下确定动态博弈中的纳什均衡，进而确定纳什均衡是否为精炼贝叶斯纳什均衡。

关键词 :路径选择，动态博弈，不完全信息，精炼贝叶斯纳什均衡

1. 引言

随着社会经济的发展和城市化水平的不断提高，城市交通的拥挤状况日益严重，经常会出现交通拥堵现象，因此出行者的路径选择显得尤为重要。路径选择行为是出行选择行为中的重要内容，路径的选择不仅关系着出行者的切身利益也关系着路网状况的拥挤程度。对于一般出行者的路径选择而言，路径选择的目标是尽量满足不同出行者的需求，达到省时高效，避免拥挤，使得整个路网状态最优化。传统的基于博弈论的路径选择行为模型是在一定的诱导信息下把任意两位出行者看成博弈双方，在整个交通过程中双方进行重复博弈，以使交通系统最优化，双方收益最大化 [1] ，也就是纳什均衡状态。而不完全信息博弈就是博弈双方不能获得对方的任何信息，只能靠猜测，即就是一种在不确定条件下个人决策行为分析的理论。然而人们对于模型的准确性还不能满足于纳什均衡，那么就有了纳什均衡之上的精炼贝叶斯纳什均衡 [2] 的研究。

到目前为止，在博弈论方面，国内外学者将演化博弈论应用于动态路径优化的相关研究相对较少，主要的成果基本上是关于博弈论的应用。Rosenthal [3] 利用合作博弈讨论了给定节点到其余节点的最短路问题；Su [4] 等人通过建立一个简化的博弈模型对城市公共交通网络的运行过程进行了仿真；谢晓倩 [5] 以管理者系统最优与出行者的用户最优之间为矛盾点，利用博弈论在诱导的管理模式下，建立了管理者和出行者之间的博弈模型；董斌杰 [1] 等通过分析出行者在出行中选择路径的过程，提出了静态诱导信息下的出行路径选择模型，并引入求解纳什均衡的划线法求解；王耀 [6] 等建立了以军方运输部门和敌方打击力量为双方的博弈模型，构建各自的目标函数，并根据博弈均衡理论，选择总收益值最大的路径为军用油料运输最优路径。在精炼贝叶斯纳什均衡方面，王伟 [7] 等分析了在市场效率原则下纳税人与纳税主体，纳税人与纳税人之间，围绕纳税与征税，纳税与漏税所展开的一系列较量，构成一个完整的博弈以寻找精炼贝叶斯纳什均衡；曾庆群 [8] 等分析了移动商务竞价行为中企业购买行为所涉及的基本信息及其抽象表示，对进行博弈分析的基本假设进行定义，然后引入自然人对目标企业收益的不确定性进行贝叶斯先验概率设定，在此基础上对购买竞价过程进行精炼贝叶斯纳什均衡研究。在路径选择方面，葛颖恩 [9] 等分析了诱导信息对路径选择行为的影响，给出了不可分的路段费用函数，把诱导信息影响下的路线选择问题组织成一个非对称网络均衡问题，并给出了用嵌入遗传算法的对角化算法求解的算例；范文博 [10] 等分析了基于参考依赖法的出行者日常路径选择的行为建模，构建了与随机用户路径选择均衡的不动点模型，设计了一个基于相继平均法MSA和Logit配流技术的启发式算法来求解该模型。上述的学者都未曾将博弈论中的精炼贝叶斯均衡与出行者路径选择相互连接起来进行研究与应用，本文就将二者联系起来做简单研究。

本文在博弈论的基础上以完全但不完美信息动态博弈模型为分析工具，构建出行路径选择的模型，对出行者选择出行路径的收益进行分析，找出纳什均衡，进而判断在不完美信息下的纳什均衡解是否为精炼贝叶斯纳什均衡，以进一步确定出行者的较优路径选择。

2. 博弈模型分析

2.1. 基本定义

在动态博弈中出行者获得的信息都是不完美信息与不完全信息，博弈论的基本概念包括局中人，战略，行动，信息，支付函数，结果，均衡等。其中局中人，策略，支付函数构成了博弈的三个基本要素，局中人，行动次序，结果统称为博弈规则，而博弈分析的目的就是使用博弈规则来确定均衡。

决策结：参与人选择的种类个数；

信息集：指某一参与人在某一阶段的行动时由博弈历史信息反应的那一组都有可能是真实位置的决策结的集合；

不完美信息：有一部分已行动者所选行动的信息，但又不能完全确定先行者选择了什么；又指决策结为单一结的情况；

完美信息：某个人参与行动前，有足够的信息来确定已经行动的参与人选择了什么行动；又指决策结不是单结；

不完全信息：自然首先选择参与人类型，而且参与人自己知道自己的真实类型，其他参与人不能确切知道，但有关于参与人类型的概率分布的公共；不完全信息是一类不完美信息；

博弈树：连通的无圈的无向图称为树，开始于初始点，结束于终止点(即再没有箭头从此延伸)。

纳什均衡：是一种策略组合，使得同一时间内每个参与人的策略是对其他参与人策略的最优反应。

精炼贝叶斯纳什均衡：不完全信息动态博弈的均衡称之为精炼贝叶斯纳什均衡。

博弈树规则 [11] ：

1) 每一个节点都是初始点的后续节点，同时，初始点是唯一没有这一特性的节点。

2) 除初始点之外的任一节点都只有一个直接前置点。初始点没有前置点。

3) 从同一个节点引出的多个分支具有不同的行动标签。

4) 每一个信息集只包含一个参与人的决策点。

5) 某个信息集中的所有节点必须具有相同数量的直接后继点，而且其中的所有节点是通过具有相同集合行动标签的分支而到达这些后继点。

2.2. 博弈模型及求解算法

观察下列图1所描述的不完美信息博弈

如图1所示，该博弈有两个参与人，参与人1先行动，如果选择L，则博弈结束。如果不选择L，则在参与人1选择后由参与人2在不知道参与人1选择结果的情况下进行选择。所以L得选择可区分，没有参与人2选择的机会就意味着参与人1选了L，而参与人2在轮到他选择时，知道参与人1已选择了M或R，但没有更多的信息，所以有一个两个决策结构成的信息集。

这个博弈有两个纯策略纳什均衡和，这可以用纳什均衡的定义直接验证。下面判断和是否构成精炼贝叶斯均衡？

首先考虑；若战略组合是精炼贝叶斯均衡，则参与人2没有机会选择，及参与人2选择

图1. 两个参与人策略选择之间的博弈

的信息集不在均衡路径上。按定义只要有与战略相容的后验概率，但任何后验概率都不会使参与人2选B是最优的，若参与人选择M的概率为，选择R的概率为，则在参与人2选择的信息集为起点的博弈中，参与人2选B的收益应该比选的收益大。然而选B时的收益是，而选U时的收益是：由于。这表明参与人2在他选择的信息集为起点的博弈中，他的选择不是最优的，按定义不是精炼贝叶斯均衡。

再考虑；给定参与人2选择U，则参与人1选M是最优的，因此参与人1不会偏离。在参与人2选择的信息集中，既然参与人1选M，则贝叶斯法则决定左边一个决策结的概率是1，则参与人选B的收益为0，选U的收益为1。因此参与人2不会偏离。因此是一个精炼贝叶斯均衡。

对此博弈，也可以分析一下混合策略均衡。实际上参与人2在其选择的信息集中，任何后验概率下，选U比选B好，所以只要有选择的机会，只会选U而不会选B。而在此基础上参与人1以任何正的概率选L或R都会比选M时的收益少。所以不会有混合策略精炼贝叶斯均衡。具体的，若参与人1以的概率选择L，的概率选择M，以的概率选择R，参与人2以与的概率选择U和B时，如果是最优

策略，则进入参与人2的信息集左边决策结的概率是，右边决策结的概率是，参与人2的收益是

所以时是最优的，即最优的混合策略是，。这时，参与人1收益是

所以时取最大，，，，因此，没有混合策略均衡。

当然对于此例没有混合策略的均衡，并不代表所有的例子中都没有混合策略，混合策略的求解我们放到出行者路径选择实例中讲解。

3. 实例分析

在出行者路径选择的博弈模型中有博弈双方进行路径的选择使得自身收益获得最大值，即就是在动态的博弈中达到精炼贝叶斯均衡。博弈论的研究和应用需要某些基本的假设，在路径选择中，假设从A地到B地有L，M，R三条不同的路径可供大家选择，并且由于每个人的主观意识不同使得每个人选择每条路径的概率不同。现假设参与人1选择L，M，R三条路径的概率分别为，，，参与人2选择路径L，M，R三条路径的概率分别为，，，出行者的收益为(其中)。且易知,。那么可以得出下列图2。

对于图2，用静态博弈来分析，很容易可以看出，，均为纳什均

衡，其中前两个解可以用纳什均衡的定义直接验证，而对于混合策略纳什均衡，我们这里作进一步的求解。

考虑混合策略知，出行者1的收益为，出行者2的收益为。可能存在的混合策略必然都是出行者1和出行者2在路径L,M, R上都有正概率的混合策略。对于出行者1而言，要取混合策略，则需要，，均不为0，所以为出行者1的混合策略纳什均衡时需成立，联立上式解得，，。同理，对于出行者2而言，要取混合策略，则需要，，均不为0，所以为出行者2的混合策略纳什均衡时需成立，联立上式解得，，；即；为一组混合策略纳什均衡。

下面我们检验在不完美信息博弈下三个解是否为精炼贝叶斯均衡；

情况一：检验路径是否构成精炼贝叶斯均衡：给定出行者2选择路径R，则出行者1选择路径L是最优的，因此出行者1不会偏离。在出行者2选择的信息集中，既然出行者1选择路径L，则贝叶斯法则决定最左边一个决策结的概率是1，则出行者2选路径的收益为0，选路径M的收益为1，选择路径R的收益为1，因此出行者2不会偏离。因此是一个精炼贝叶斯均衡。

情况二：检验路径是否为精炼贝叶斯均衡：类似的给定出行者2选择L，则出行者1选择路径M是最优的，因此出行者1不会偏离。在出行者2选择的信息集中，既然出行者1选择路径M，则贝叶斯法则决定中间决策结的概率为1，则出行者2选路径L的收益为3，选择路径M的收益为0，选择路径R的收益为1，因此出行者2不会偏离。因此是一个精炼贝叶斯均衡。

图2. 出行者对路径的选择

情况三：混合策略，若，，即出行者1选择路径L的概率为，则最左边决策结的概率为，选择路径的概率为，则中间决策结的概率为，选择路径R的概率为，则最左边的决策结的概率为。如果出行者2选择路径L的概率为，选择路径M的概率为，选择路径的概率为。

对出行者2，他选择路径L的收益为

(1)

他选择路径M的收益为

(2)

他选择路径R的收益为

(3)

联立式子(1) (2) (3)解得：，即；

对于出行者1，他选择路径L的收益为

(4)

他选择路径M的收益为

(5)

他选择路径R的收益为

(6)

联立式子(4) (5) (6)解得：，即；

则可知上述不完美信息博弈中，即混合策略也是精炼贝叶斯均衡。

4. 结束语

本文基于博弈论，将博弈双方的出行路径选择行为抽象为不完全信息动态博弈，建立博弈模型并求解其纳什均衡，进而判断模型中的纳什均衡是否为精炼贝叶斯纳什均衡，并利用案例进行验证，为出行者出行路径的选择提供最佳的方法和依据。在以后的研究中，我们会进一步深入研究精炼贝叶斯纳什均衡，在不完全动态信息下考虑已知自己类型可获得其他人类型的先验概率，战略空间，信息集，以及后验概率等因素，使得所求解得精炼贝叶斯纳什均衡更加准确。

基金项目

国家自然科学基金(61463027)，教育部博士点(新教师)基金(20136204120007)。

文章引用

王茹心,孙军霞,陈京荣. 出行路径选择的精炼贝叶斯纳什均衡
Refined Bayesian Nash Equilibrium of Traveler Route Choice[J]. 应用数学进展, 2016, 05(04): 639-645. http://dx.doi.org/10.12677/AAM.2016.54074

参考文献 (References)