势博弈理论及在移动通信中的应用

2012，，，、，，，。；；；；1,2，3，1,2，1,2，3（1.网络体系构建与融合北京市重点实验室北京100876；2.北京邮电大学信息与通信工程学院北京100876；3.中国电力科学研究院北京100192）11.1MondererShapley1996。，，，[1]（generalizedordinal）、（ordinal）、（exact）（weighted）。Voorneveld，[1，2]，。，。？，，：（FIP）。，。FIP，。“”，“”“”，“”，“”，“”，，，，。NeelJ“AllroadsleadtoRome()”[4]，，，。，，，。，，、、。1.2，，，，，，5512012，τ=N,Y,u。，N，Yiuii（payofffunction），，[5]。1.2.1普通势博弈τ，。P∶Y→R，i∈Ny-i∈Y-i（i）：ui(y-i,x)-ui(y-i,z)0,ifP(y-i,x)-P(y-i,z)0x,z∈Yi（1），i（），（）。τ，：P，：eui(y)eyi0,ifeP(y)eyi0,i∈N,y∈Y（2）1.2.2加权势博弈w=(wi,…,wN)，i∈Ny-i∈Y-i，τ：ui(y-i,x)-(y-i,z)=wi(P(y-i,x)-P(y-i,z)),x,z∈Yi（3）P:Y→R，τ。，τ，：eui(y)eyi=wieP(y)eyi∈∈,i∈N,y∈Y（4）1.2.3完全势博弈，wi=1,i∈N，P:Y→R，：ui(y-i,x)-ui(Y-i,z)=P(y-i,x)-P(y-i,z),Ax,z∈Yi（5）τ，。，，。，。1.2.4伪势博弈P:Y→R，i∈Ny-i∈Y-i：argmaxyi∈Yiui(yi,y-i)∩argmaxyi∈YiP(yi,Y-i)（6），τ*=〈N,Y,P〉τ=〈N,Y,ui〉。ττ*，τ，P，。1。2，，。，，。，，：—、、、、，，。2.1—（7）：ui(y)=C(y)+Di(y-i)（7）C:Y→R，Di:Y-i→R，-[4]。P=C(y)。C(y)，y，Di(y-i)，i，。（8）：ui(yi,y-i)-u(xi,y-i)=C(yi,y-i)-C(xi,y-i)i,j∈N,y∈Y（8）15522012C(y)[1]。，—。（9）：ui(y)=C(y)（9）C:Y→R，，—di=0i∈N。—C(y)=0,y∈Y，。2.2（10），。ui(y)=Si(yi)（10）Si:Yi→R，，，[4]。[1]：P=ΣSi(yi)（11）2.3（12）：ui(y)=j∈NΣΣiΣwijj(yi,yj)-Si(yi)（12），wij:Yi×Yj→R，，Si:Yi→R，，(yi,yj)∈Yi×Yjwij(yi,yj)=wij(yj,yi)，。（BSI）（13）[4]：P=Σi-1Σwij(yi,yj)-ΣSi(yi)（13）33.1，。1Pτ=〈N,Y,{ui}ieN〉，ττ*=〈N,Y,{P}ieN〉，。，，。，。2。2，τ=〈N,Y,{ui}ieN〉，1，P(y)y*∈Yτ，。。τ=〈N,Y,{ui}ieN〉，P，P，P，，2。，，。y*=maxy∈YP(y)，，，y*Y'∈Y，iui(y')ui(y*)，，P(y')P(y*)，P，，。3.2，，，—（Gauss-Seidel）(Jacobi)。γ=（y0,y1,...）Y，yk=(y-ik-1,x)（x∈Yi），-y0。，k，，ik。k≥1，ui(yk)ui(yk-1)，γτ2i∈Ni∈Ni∈Nj∈15532012。τ，τ。，。FIP。γ=（y0,y1,...），，：P(y0)P(y1)P(y2)...（14）Y，γ，。，，，，。，，，。3.3，，。。。，，，，，[6]。，，。：(bestresponse)、(betterresponse)(gradientprojectionresponse)。（15）：Di(y-i)=yi*∈Yi(y-i):y*i=argmaxyiui(yi,y-i∈∈)（15）（16）：Di(y)=yi*∈Yi(y-i):ui(yi*，y-i)ui(yi,y-i∈∈)（16），ui(yi,y-i)Yi，，，〈·,·〉，·。，△iui(y):=eui(yi-y-i)eyi，，Yi，：Di(x)=yi+ρi△iui(yi,y-i，，)yi(y-i)（17），，ρi，，，cYi(y-i)Yi(y-i)C：，，cYi(y-i)=argminyi∈Yic-yi22（18）4，。，，，。，，。，，。，，[7]。，，，，。，，，。，，，[8]：P，=Objective（19），，“”[8]，，、，“”，。“”1，。Ye，Y*，（20）：POA=Fobj(Ye)Fobj(Y*)（20）55420125、。。，3。5.1[5,9]，，。，。m。piti，gijji。，ijpijr=gijpj。ηii。i（SINR）：αi=giipitΣi≠jgij+pjtηi=priiΣi≠jpijr+ηi（21），，，。，i：ui(αi,pit)。Iii：Ii=j≠iΣgijpjt=j≠iΣpijr（22）·：·；·（）；·：ui(αi,pit)=Ri(αi)-cpit，C。RiSlog(1+αi)。：P=log1+i∈NΣhi2pi∈∈-i∈N∑cpi（23）5.2[4,10]，。：·；·Yi，Yi=[0,ymax]；·：ui(Y)=-γ＾-giyi1k∑j≠igiyi+∑∑η（24）yii，gii，η，K，γ＾。[9]，τ=〈N,P,ui∑∑i∈N〉，：p=2γ＾K(∑i∑k＞igigkpipk)+i∑(-gi2pi2+2γ＾gipi/K)（25），，。。1VoorneveldM.Best-responsepotentialgames.EconomicsLetters,2000(66):289~2952DubeyP,HaimankoO,ZapechelnyukA.Strategiccomplementsandsubstitutesandpotentialgames.GamesandEconomicsBehavior,2006(54):77~943MondererD,ShapleyL.Potentialgames.GamesandEconomicsBehavior,1996(14)4NeelJO.Analysisanddesignofcognitiveradionetworksanddistributedradioresourcemanagementalgorithms.VirginiaPolytechnicandStateUniversityDissertation,20065ScutariG,BarbarossaS,PalomarDP.Potentialgames:aframeworkforvectorpowercontrolproblemswithcoupledconstraints.ProceedingsofICASSP2006,Toulouse,France,20066JohnsonDS,PapadimitriouCH,YannakakisM.Howeasyislocalsearch?JComputerSystemSci,1988(37):79~1007PapadimitriouFC,TalwarK.Thecomplexityofpurenashequilibria.ProcACMSympofTheoryofComputing,2004:604~6128VoorneveldM.Equilibriaandapproximateequilibriaininfnitepotentialgames.EconomicsLetters,1997(56):163~1699HeikkinenT.Apotentialgameapproachtodistributedpowercontrolandscheduling.ComputerNetworks,2006(50)：2295~231110NeelJ,ReedJ,GillesR.Convergenceofcognitiveradionetworks.ProcofWirelessCommunicationsandNetworkingConference,Phoenix,AZ,USA,Nov200411，，..，2011，27(8):63~6712，，.LTE-A.，2011，27(12):39~43（收稿日期：2012-11-15）555