混合策略均衡范文(精选3篇)
混合策略均衡 第1篇
均衡是博弈论一个重要研究对象。均衡是一种策略组合, 使得同一时间内每个参与人的策略是对其他参与人策略的最优反应。1951年纳什提出著名的纳什定理, 即在矩阵博弈中一定存在均衡。这里的均衡可能是纯策略均衡, 也可能是混合策略均衡。
2×2矩阵博弈是一类最基本且被广泛应用的重要博弈类型, 它是指在博弈过程中只有两个参与人 (参与人1和参与人2) , 且每个参与人只有两个可选策略。经典博弈诸如囚徒困境、性别战争、古诺双寡头垄断、贝特兰德双寡头垄断等博弈都可以归为此类博弈。
本文分析了2×2矩阵博弈中的混合策略均衡, 讨论了此类博弈的严格优势策略和纯策略均衡, 得到了在没有严格优势策略且存在唯一均衡的2×2矩阵博弈中, 均衡必为混合策略均衡。
考虑2×2矩阵博弈。对于参与人1和参与人2, 参与人1的可选策略为U和D, 参与人2的可选策略为L和R。他们的收益情况如下:
(1) 当参与人1选择策略U且参与人2选则策略L时, 他们的收益分别为a和b;
(2) 当参与人1选择策略U且参与人2选则策略R时, 他们的收益分别为c和d;
(3) 当参与人1选择策略D且参与人2选则策略L时, 他们的收益分别为e和f;
(4) 当参与人1选择策略D且参与人2选则策略R时, 他们的收益分别为g和h。
我们可以用如下的矩阵表示:
其中第一列表示参与人1的可选策略, 第一行表示参与人2的可选策略, 收益中前者为参与人1的收益, 后者为参与人2的收益。
设参与人1选取策略U的概率为x, 参与人2选取策略L的概率为y。这样, 参与人1选取策略D的概率为1-x, 参与人2选取策略R的概率为1-y。
可见, 对参与人1而言, 选取策略U的期望收益为ay+c (1-y) , 选取策略D的期望收益为ey+g (1-y) , 于是参与人1选取策略U和策略D无差异当且仅当ay+c (1-y) =ey+g (1-y) 。令r1 (y) 表示参与人1对参与人2随机化概率y的反应函数。则
类似地, 对参与人2而言, 选取策略L的期望收益为bx+f (1-x) , 选取策略R的期望收益为dx+h (1-x) , 于是参与人2选取策略L和策略R无差异当且仅当bx+f (1-x) =dx+h (1-x) 。令r2 (x) 表示参与人2对参与人1随机化概率x的反应函数。则
在博弈中, 参与人的严格优势策略是使得参与人选取该策略所获收益严格大于选取其他策略所获收益。在2×2矩阵博弈中, 严格优势策略具有如下特征:
对参与人1而言, 策略U严格优于策略D当且仅当ay+c (1-y) >ey+g (1-y) ;策略D严格优于策略U当且仅当ay+c (1-y) <ey+g (1-y) 。
对参与人2而言, 策略L严格优于策略R当且仅当bx+f (1-x) >dx+h (1-x) ;策略R严格优于策略L当且仅当bx+f (1-x) <dx+h (1-x) 。
由于均衡是每个参与人对其对手策略选择的最优反应, 则在2×2矩阵博弈中, 纯策略均衡具有如下特征:
(U, L) 是均衡当且仅当a≥e且b≥d; (U, R) 是均衡当且仅当c≥g且d≥b; (D, L) 是均衡当且仅当e≥a且f≥h; (D, R) 是均衡当且仅当g≥c且h≥f。
定理在2×2矩阵博弈中, 如果不存在严格优势策略, 且存在唯一的均衡, 则此均衡必为混合策略均衡。
证明 (反证法) 假设此博弈中唯一的均衡是纯策略组合, 设为 (s1*, s2*) , 不失一般性, 取 (s1*, s2*) = (U, L) , 对策略组合 (U, R) , (D, L) 和 (D, R) 可类似地讨论。由于 (U, L) 是均衡当且仅当a≥e且b≥d。对此分情况进行讨论。
(1) a>e且b>d。由于对参与人1而言, 策略U不严格优于策略D, 则ay+c (1-y) ≤ey+g (1-y) , 于是c≤g;对参与人2而言, 策略L不严格优于策略R, 则f≤h。于是策略组合 (D, R) 是博弈中的一个均衡, 这与 (U, L) 是唯一的均衡矛盾。
(2) a=e且b>d。此时b-d>0, 则 (b-d) + (h-f) >h-f, 于是存在θ∈[0, 1]使得θ[ (b-d) + (h-f) ]>h-f, 即θb+ (1-θ) f>θd+ (1-θ) h, 从而令参与人1选取策略U的概率为θ, 可见混合策略组合σ= (σ1, σ2) 是博弈的一个均衡, 其中σ1表示参与人1以概率θ选取策略U, 以概率1-θ选取策略D, σ2表示参与人2选取策略L。这与 (U, L) 是唯一的均衡矛盾。
(3) a>e且b=d。此时a-e>0, 则 (a-e) + (g-c) >g-c, 于是存在θ∈[0, 1]使得θ[ (a-e) + (g-c) ]>g-c, 即θa+ (1-θ) c>θe+ (1-θ) g, 从而令参与人2选取策略L的概率为θ, 可见混合策略组合σ= (σ1, σ2) 是博弈的一个均衡, 其中σ1表示参与人1选取策略U, σ2表示参与人2以概率θ选取策略L, 以概率1-θ选取策略R。这与 (U, L) 是唯一的均衡矛盾。
(4) a=e且b=d。此时若策略组合 (U, R) 不是均衡, 则c<g;若策略组合 (D, L) 不是均衡, 则f<h。这样策略组合 (D, R) 是博弈的一个均衡, 与 (U, L) 是唯一的均衡矛盾。
综上可知, 策略组合 (U, L) 不是此博弈的均衡, 从而此2×2矩阵博弈的均衡必为混合策略组合。
摘要:本文分析了2×2矩阵博弈中的混合策略均衡, 讨论了此类博弈的严格优势策略和纯策略均衡, 得到了在没有严格优势策略且存在唯一均衡的2×2矩阵博弈中, 均衡必为混合策略均衡。
关键词:矩阵博弈,严格优势策略,均衡
参考文献
[1]车竞, 钱炜祺, 和争春.基于矩阵博弈的两机攻防对抗空战仿真[J].飞行力学, 2015, 33 (2) :173-177.
[2]马国勇, 石春生.基于博弈矩阵模型的企业研发策略[J].统计与决策, 2012, 1:54-55.
[3]R.Gibbons.A Primer in Game Theory[M].Prentice Hall, 1994.
[4]D.Fudenberg, J.Tirole.Game Theory[M].MIT Press, 1991.
混合策略均衡 第2篇
用博弈论对电力市场进行理论研究时[1,2,3,4,5,6,7],通常都会对纯策略纳什(Nash)均衡进行详细的求解和描述。纯策略Nash均衡有着良好的性质,对市场具有指导性的作用[2,3]。然而,在很多市场条件下,纯策略Nash均衡并不存在,但这并不意味市场没有均衡。博弈论提供了一种很好的分析思路[1],当博弈参与者没有一种绝对占优的纯策略,也就意味着他们必须在可供选择的纯策略中找到一个组合,使得自己可能获得的收益最大,这个组合称为混合策略。当所有的参与者在一组组合策略下可能获得的收益都达到最大时,他们将不会单独偏离这组组合,这组组合称为他们的混合策略纳什均衡(MSNE)。
目前已有一些学者对MSNE做了研究[8,9,10,11]。这些研究中在求解MSNE时所用的方法一般都是将发电商报价策略简化为2个~3个离散的纯策略(报低价、报高价等)。这种方法虽然简单,但对于整个报价策略空间的连续性破坏较大,应用受到一定局限。
为了不破坏报价策略的连续性,分析了按报价支付(PAB)机制下市场中不存在纯策略Nash均衡的情况,建立了适用于求解连续策略MSNE的双层优化模型。为了增加模型的实用性,研究了报价策略为一种指数分布[12]时市场的MSNE,按照循序渐进的方式,从2机系统逐渐拓展到了多机系统。最后用一个算例验证了该模型的合理性和有效性。
1 市场混合策略分析
1.1 不存在纯策略Nash均衡的条件和区间
文献[4]中定理1已证明:在PAB市场中,机组装机容量为强约束(即存在发电厂商k,满足
1.2 市场MSNE模型
显然,区间Φ是一个连续的报价策略区间,不存在纯策略Nash均衡时,不妨用概率密度函数f(x)来表示发电商的报价组合策略,由此得到MSNE的市场模型为:
Pk(fk(x),f-k(x))fk(x)dx (4)
s.t. pk∈Φ (5)
∫+∞-∞fk(x)dx=1 (6)
式中:
本模型中假设:
1.3 均衡概念
对式(4)进行分析可知,策略空间确定后E(πk)是所有厂商决策变量(fk(x),f-k(x))的函数,从而式(4)可以表述为:
求解式(7)可得到fk(x)的最优响应函数为:
而Nash均衡的意义为没有发电商会单方面偏离均衡点而获得更多利润,即
式中:f*k,f*-k为均衡解。
由最优响应函数确定了最优响应曲线,显然,f*k位于最优响应曲线上,所有最优响应曲线的交点即为均衡点,即f*k=rk(f*-k)。
上述问题求解起来比较困难,因此可采用循序渐进的方法,从2机系统推广到多机系统。
22机系统均衡分析
2.1 取值空间标准化与数值换算
区间Φ的表达式较为繁琐,不利于对其进行计算,因而首先按照下式将其进行标准化,转换成标准区间Φ′=[0,1],即
显然,只要将所有的价格参数都按照上述格式统一转换,对市场分析结果不会产生任何影响。将统一边际成本换算为:
2.22机系统MSNE通解
在区间[0,1]中,令机组A和B的概率密度函数分别为f(x)和g(y),按照分布函数的定义,有
且∫+∞-∞f(x)dx=∫10f(x)dx=1。对g(y)同样成立。
根据容量约束,有2种可能:
1)2台机组均处于强容量约束下,即
按照混合策略Nash均衡的定义,假定机组A采用Nash均衡混合策略f*(x),机组B申报价格为y时,其利润为:
Nash均衡即要寻求一个最优分布策略g*(y)使得E(πB)达到最大,在g(y)的条件下,易求得:
要使E(πB)达到最大,对式(14)关于g(y)求导并令导数为0,可得到Nash均衡混合策略f*(x):
同样可求得:
可得到在连续策略情况下的2机系统博弈的MSNE(f*(x),g*(y))。
2)只有1台机组处于强容量约束下,不妨设
经计算,得出:
同样可得到MSNE(f*(x),g*(y))。但是,隐函数形式的(f*(x),g*(y))表达式在理论研究和工程应用中并不受欢迎,能得到解析形式的表达式则更好。下面给出一种较为常见的分布函数为指数形式的MSNE求解过程。
2.3 指数分布
令分布函数为f(x)=axλ+b(λ>0),当λ=1时为线性分布,其余情况则为非线性分布,称a为分布系数,其曲线如图1所示。
由于报价策略只在标准区间[0,1]中分布,即∫
考虑到实际市场运行中,发电商报价类型可分为3种:风险规避型(偏向于报低价)、风险爱好型(偏向于报高价)和风险中性(高、低价均匀分布)。由分布函数定义可知:a>0对应风险爱好型,a<0对应风险规避型,而a=0(虚线)对应风险中性。
2.42机系统MSNE的解析解
从概率密度函数f(x)的表达式很容易看出,当λ确定之后,f(x)由a唯一确定。为方便起见,只需求出a即可。在2机系统中易求得分布函数为:
对应于同样的g(y)可求得:
至此,F(x),G(y),f(x),g(y)的解析表达式已全部得到。对于2机系统中可能出现的2种强容量约束情况,只需将式(20)~式(22)代入通解表达式中即可求得解析表达式。
以λ=1为例。
对于可能情况1,将上述表达式分别代入式(14)~式(17)中,可求得:
对于可能情况2,计算后得到:
至此,2机系统连续策略的MSNE解析解(a*A,a*B)已得出。
3 多机系统拓展
上述方法同样可用于多机系统,以3机系统为例。机组A,B,C装机容量分别为
同样可得到E(πA),E(πB)的表达式,与E(πC)联立,将各参数代入其中,可得到E(πi)关于ai(i=A,B,C)的方程组。
仍以λ=1为例,将方程组中E(πi)关于ai(i=A,B,C)求导并令其导数为0,整理后可得到关于Nash均衡解的方程组如下:
对于3机组容量约束的其他情形,由于篇幅所限,在此不再赘述。
在n机系统中,E(πi)(i=1,2,…,n)的表达式为:
将E(πi)关于ai(i=1,2,…,n)求导并令其导数为0,联立成方程组,在实际运行中将各参数用数值代入即可进行求解。
4 算例分析
以IEEE 3机9节点系统为例,不考虑网络约束时,可简化为如图2所示的3机4节点系统。图中,A,B,C为发电商节点,D为负荷节点,其边际成本为20美元/MW,报价上限为100美元/MW,其装机容量和负荷如表1所示。
表1中各种情形都属于强容量约束,不存在纯策略Nash均衡。当λ=1(即线性分布)和λ=2(即二次分布)时,其MSNE的计算结果如表2所示。
对表2中数据进行观察分析可知,机组报价策略的分布与自身装机容量、总装机容量以及系统总负荷相关。机组容量越高,在总装机容量中占的比重越大,则其报价策略分布函数的系数越大,表示其更喜欢报高价,相当于市场竞争中的价格领导者(price-maker),这一类机组的存在会抬高市场的出清价格;机组容量越低,在总装机容量中占的比重越低,则其分布系数越小,更倾向于报低价,相当于市场竞争中的价格接受者(price-taker)。
而对第1种情况进行分析可以发现,当各机组均处于均等地位时,作为边际机组的收益远小于下边际机组,因而所有机组都采取较为保守的策略;而对比第1种和第2种情况节点B机组的装机容量,可以发现,即使在市场中所占份额同为1/3,但是当所有机组份额均相同时仍会采取比份额不同时更保守的策略,即份额相同时会更倾向于申报低价。市场管理者若要限制大发电商行使市场力,通常可以采用拆分的手段降低其市场份额,而通过本文的研究可以进一步发现,等额拆分的效果更好,与文献[13]中结论相互验证。
5 结语
本文建立了PAB市场机制下基于概率分布的Bertrand博弈模型,以求解不存在纯策略Nash均衡时市场的MSNE。研究结果表明:市场中装机容量越高、所占市场份额越大的机组,会更倾向于申报较高价格,成为价格领导者,抬高市场出清价格;而当发电商所占份额趋向于平均化时,即使所占份额仍然很大,但是都会采取较为保守的策略,申报较低的价格,有利于降低市场出清价格。因而通过拆分可以达到降低市场出清价格的目的,而等额拆分的效果更好。
摘要:针对按报价支付(PAB)机制下市场中不存在纯策略纳什(Nash)均衡的情形,建立了基于概率分布的连续策略伯川德(Bertrand)博弈模型,以求解其混合策略纳什均衡(MSNE)。将报价策略区间标准化之后,求出了MSNE的通解。随后针对一类指数分布的报价策略,求出了MSNE的解析表达式。最后通过一个简单算例验证了该模型的有效性。研究结果表明:市场份额越大的发电商越倾向于申报高价,成为价格领导者,抬高市场出清价格;通过等额拆分可以有效减少市场力,降低市场出清价格。
混合策略均衡 第3篇
随着现代化通信发展节奏的加快,人们对于移动通信网络的传输速率的要求不断提高,而频谱资源的局限性使得传统蜂窝模式通信已经逐渐无法满足系统所要承载的系统容量,D2D通信可以通过复用蜂窝资源进行短距离的通信,具有时延小、速率高的优点,更重要的是该通信模式可以不用像蜂窝模式那样必须经过基站转发,对减小基站的负载量具有很大的帮助。目前,对于如何提高引入D2D通信的混合网络的总吞吐量以及系统的公平性成为业界研究的一大重点。
文献[1]中提出了一种基于干扰感知的无线资源分配方案,但是该方案只允许一对D2D用户复用一个蜂窝用户的资源。文献[2]中提出了一种基于不同Qo S需求的资源分配方案,通过该方案可以实现一对D2D用户复用多个RB,但是该方案不能够将系统内可复用的RB进行最优的分配。文献[3-4]研究了D2D通信技术引入LTE-A系统后,D2D对的发现、连接和通信过程,以及D2D对之间的距离对吞吐量的影响。D2D用户在复用模式下,选择复用资源的过程,实际上是D2D用户和蜂窝用户的匹配问题。由于用户之间的干扰和它们之间的距离是密切相关的,因此针对此问题,一些文献首先提出了基于地理位置信息的资源分配算法。
本文通过拉格朗日乘数法结合图论中的匈牙利匹配算法,提出一种循环匹配的资源分配方案,以最大化蜂窝信道的复用增益为前提条件,每一轮匹配完成时,每条蜂窝信道将接入一条D2D链路。为了防止算法最后没有足够的D2D链路与蜂窝信道匹配,本文在系统中加入虚拟D2D用户,使系统D2D用户数N与蜂窝用户数M呈整数倍关系,每条蜂窝信道可以被N/M条D2D链路复用。该方法不但适用于稀疏D2D网络,更适用于密集D2D网络,而且在接入D2D链路对时同时使系统的负载均衡化,提升系统公平性。
1 系统场景
如图1所示,在一个小区中存在M个蜂窝用户、N条D2D链路和M条正交子带宽,蜂窝用户满载,D2D链路只能通过复用蜂窝上行信道接入网络中。蜂窝用户的集合为C={ci|i=1,2,3,...M},D2D链路的集合为D={dj|j=1,2,3,...P}。设定以基站为中心,半径的R的区域为D2D限制区域以保护蜂窝用户的Qo S,即此区域内不得存在D2D用户。
假设小区通信环境稳定,在资源调度周期内,小区的CSI不会发生改变,所有用户以及信道资源通过基站的控制在资源调度周期内进行分配。
2 数据分析
设定蜂窝用户的最低信干比为sinrcmin,D2D链路的最低信干比为sinrdmin;蜂窝用户与D2D链路的门限功率分别为Pcmax和Pdmax;设定D2D发射端到基站以及蜂窝用户到D2D接收端的门限信道增益分别为和。
则D2Dj与蜂窝信道可以进行匹配的条件为:
D2Dj接入蜂窝信道的功率限制条件为:
其中,jPi表示D2Dj发射端的发射功率,表示其发射端与接收端之间的信道增益,kPi表示已经接入蜂窝信道上除D2Dj以外的其他D2D对的发射端对D2Dj接收端的发射功率,Iei表示邻近小区里同频用户对D2Dj的干扰,IEi表示邻近小区里共用的用户对基站的干扰,N0表示高斯噪声。
3 负载均衡化的循环匹配算法
在初始状态时,规定所有的蜂窝用户均以最大功率接入蜂窝网络,可得各个蜂窝信道上吞吐量为:
使用拉格朗日算法求出满足匹配条件的蜂窝用户与D2D用户共用信道时达到最大传输速率的功率解:
由此,可得子信道的复用增益为:
进而可得整个系统内的复用增益矩阵,中不满足匹配条件的元素置为零。使用KM加权匹配算法进行一次最优匹配,使系统总的复用增益最大化:
KM匹配算法步骤如下:(1)由以上拉格朗日乘数法求出满足接入条件的D2D用户接入各个蜂窝信道的复用增益,此一步完成权值的初始化过程;(2)根据匈牙利匹配算法寻找蜂窝信道的一个完备匹配;(3)修改顶标继续寻找完备匹配;(4)重复(2)(3)操作,直到所有蜂窝信道均匹配到一条D2D链路为止。本算法将整个匹配周期分为多个匹配时隙,每一个时隙完成一轮匹配过程,每一轮匹配结束后,每条蜂窝子信道接入一条D2D链路。对于稀疏D2D蜂窝网,第一轮匹配结束即可完成整个系统的资源分配与功率分配过程,但是,对于密集D2D网络,蜂窝用户数小于D2D数目,则需要进行多轮匹配,由于第一轮匹配已经接入了M个D2D用户,所以此时令:
重复以上算法步骤,只是在以后的匹配过程中必须考虑前面几次匹配过程已经接入的D2D链路所带来的干扰,直到所有D2D用户均接入系统为止。假定在第q轮匹配时,最大吞吐量求解如下:
子信道的复用增益为:
整体算法流程如图3所示。
4 公平性分析
其中,Nd表示系统总共有Nd个用户,ϕd(∆t)表示用户在时间间隔∆t内实际的吞吐量,公平性因子越高,整个系统的公平性就越好。本文将D2D链路均匀分配到每一条子信道上,使每条蜂窝子信道上的负载均衡化,相比于传统匈牙利匹配算法可以有效提升系统的公平性。
5 仿真结果
为了验证以上理论所述,本文在LTE-TDD蜂窝系统小区场景下,使用维也纳仿真平台进行系统级仿真。仿真参数如表1所示。
本文采用循环匹配算法进行资源分配,其目的一是解决传统匹配算法的局限性;二是使蜂窝信道上可以接入多条满足接入条件的D2D对,使频谱资源得到充分利用。由图4可知系统频谱资源利用率相对于文献[9]所使用的匈牙利算法以及文献[11]所使用的根据信道状况随机选择满足接入条件的D2D对接入的算法具有部分提升。图5是系统总吞吐量的累积分布状况,由图可知本文算法与文献[9]在蜂窝吞吐量对比而言,当系统D2D数目较少时,两种算法为蜂窝小区带来的吞吐量不相伯仲,但是,对于密集D2D蜂窝网络而言,本文算法则具有一定的优越性,这是由于本算法将系统内所有D2D终端平均的分配到每一条子信道上,使每条子信道的信道容量尽可能最大化而不是单独使链路上的数据率最大化,所以该算法可以有效提升系统的总吞吐量,尤其对于密集D2D蜂窝网络而言。
6 结束语
【混合策略均衡】相关文章:
混合策略09-07
一个混合策略问题多解研究09-12
基于混合优化策略的结构损伤识别方法07-03
解排列组合混合问题的十种策略09-10
混合对策05-08
混合水泥05-15
混合免疫05-16