界定Stackelberg博弈下的混合平衡交通网络效率损失

《界定Stackelberg博弈下的混合平衡交通网络效率损失》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第19卷第3期2010年6月运筹与管理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．19，No．3Jun．2010界定Stackelberg博弈下的混合平衡交通网络效率损失罗文昌(宁波大学理学院，浙江宁波315211)摘要：考虑一个受控制的交通网络，一类用户属于领导者，按照系统最优原则选择出行路径；另一类用户属于跟随者且具有不完全信息，按照Logit型随机用户平衡原则选择出行路径．建立了描述这种Stackelberg博弈下的混合平衡出行行为的变分不等式模型，给出

2、了满足此种混合平衡的交通网络的效率损失上界，结果表明，效率损失上界与被研究的交通网络拓扑结构，交通需求及控制系数有关．关键词：Stackelberg博弈；效率损失；变分不等式；混合平衡中图分类号：0225文章标识码：A文章编号：1007-3221(2010)03-0035-06BoundingtheEfficiencyLosswithMixedEquilibriumAssociatedwithStackelbergGameinTransportationNetworkLUOWen—chang(Fac

3、ultyofScience，NingboUniversity，Ningbo315211，China)Abstract：Inatransportationnetworkwithuser8classifiedintotwocategories，thefirstcategorycalledleaderschoosetherouteaccordingtosystemoptimumprincipleandthesecondcategorycalledfollowerswithincompleteinforma

4、tionchoosetherouteaccordingtoLogit-basedstochasticuserequilibriumprinciple．Inthispaper，avari-ationalinequalityisproposedtoformulatethemixedequilibriumtravelbehaviorassociatedwithSmckelberggame．Likewise．theupperboundofefficiencylossforthemixedequilibriu

5、misdescribeda8ageneralformula．Theresultshowsthattheupperboundisrelatedtothetopologicalstructure，transportationdemandandthecon-trolledparameterinthespecifiedtransportation．Keywords：Stackelberggame；efficiencyloss；variationalinequality；mixedequilibrium0引言

6、在现实交通网络中，为了使整个网络效率达到最优，管理者通常对网络中的部分用户采取一些有效措施加以控制．考虑一个受控制的交通网络，根据每个用户是否被管理者控制，可将用户分为两类，一类用户被集中控制，我们称为领导者(1eader)，其在路径选择上表现为选择有助于使整个网络总费用最小的出行路径；另一类用户不被控制且具有不完全信息，我们称为跟随者(follower)，其在路径选择上表现为随机性选择自身感知到的出行费用最小的路径(并不一定是实际出行费用最小的路径)．这两类用户的出行行为我们称之为Stackelb

7、erg博弈，其最终的选择结果是导致网络上的部分系统最优及随机用户平衡下的混合平衡．那么与完全的系统最优相比，如何对这种Staekelberg博弈导致的混合平衡效率损失进行估计?对这类问题的回答，最早可追溯到1999年，Koutsoupias和Papadimitriou⋯首次引进与近似算法分析收稿日期：2009·03—06基金项目：浙江省教育厅科研项目(20070967)作者简介：罗文昌(1975-)。男，讲师，博士生，研究方向：算法博弈论。36运筹与管理2010年第19卷中的近似比及在线算法分析中的

8、竞争比相类似的概念，提出用合作比率(coordinationratio)或无政府代价(thepriceofanarchy)来对网络博弈中局中人的自私行为而导致的效率损失进行界定．Roughgarden和Tar-dos¨“1将此概念引入到网络路径博弈的研究中，从而开创了对网络路径博弈中的平衡解效率损失进行分析这一新的研究方向，成为新的研究热点．随后，众多学者，如Chau和Sire∞1，Correa等¨’7’，黄等¨1，分别从不同的假设条件对网络路径博弈作了相应的扩展研究