硕士论文-策略性分布式系统中机制设计问题的研究

上海交通大学硕士学位论文策略性分布式系统中机制设计问题的研究姓名：徐志成申请学位级别：硕士专业：计算机应用与技术指导教师：伍民友20081201I,(Incentive)(MechanismDesign)VCGstrategyproofValue-basedstrategyproofwebcachep2padhocIIMcAfeeVCG,strategyproofABSTRACTIIIMechanismDesigninStrategicallydistributedsystemABSTRACTStrategicallydistributedsystemhasbecomemoreandmoreimportanttheseyearasthecomputernetworkgrowsrapidly.Amongthetraditionalresearchofdistributedsystem,theagentsinsuchsystemareallregardedasobedient.Thisassumptionignoresthedifferentbenefitsbetweendifferentagentswhichmeanwhenvariousagentswhichbelongtodifferentorganizationsdonotfollowthesocialprotocolbutacttoachievethemaximumoftheirbenefits,incentivebecomesanurgentproblemtosolve.Mechanismdesign,whichcomesfromeconomicsandgametheoryhavesuchconceptofstrategicalagentsandprovidetheincentivesolution,Itcouldhelpusachievingthegoalthatsocialbenefitcouldbemadewheneachselfishagentpurchasetheirprofits.However,intraditionaldefinitionofmechanismdesign,peopleusuallyjustconsiderthepriceaffordedbyuserorthecostofserviceprovider.Thedifferencesbetweendifferentusersanddifferentserviceproviderhavebeenignored.Actually,oneserviceprovidermaybeconsideredtobedifferentbydifferentuserduetothedifferentparameters.Meanwhile,differentserviceprovidermayalsotradewiththesameuserdifferently.ThetraditionalVCGbasedmechanismbecomeuselessandcouldnotholdStrategyproofanylonger.Wewillprovideavalue-basedVCGmechanismtosolvethiskindofproblem.Themechanismdiffersindifferentscenariounderthesamerationalassumption.Inthispaper,wewilldiscussthecorrespondingmechanismwhichneedstobeStrategyproof.Wewillalsoapplythesemechanismstodifferentdistributedsystemtojustifythem,includingthewebcache,distributedstoragesystem,distributedcomputing,p2pfilesharing,wirelessad-hocnetworkandthecognitiveradiowirelessnetwork.OurmechanismABSTRACTIVwillaimatsolvingtheincentiveproblemandlettheagenttelltheirtunefultyperationally.Besides,wewillalsointroducedoubleauctiontodiscussthemostcomplexscenario,manyvs.many.Wewillintroducethebackground,therunningenvironmentandthecorrespondingbiddingstrategyofbothbuyerandsellers.Wewillproposedual-VCGbasedonthemechanismwhichisproposedbyMcAfeeandprooftheStrategyproofcharacterofourmechanism.Intheend,wetakethestrategyofforeignexchangesystemforexampletointroducethematchingmethodasthethirdparty.Keywords:MechanismDesign,distributedsystem,doubleauction535411.1QoSIncentiveMironLivny1Condor...(MechanismDesignMD)22AndersonandKubiatowicTheWorldwideComputer3...strategyproof(secondaryuser)(primaryuser)P2Pad-hoc3onestageauctionrepeatedauction(Discrete-timeAuction)(Continuous-timeAuction),dualVCGstrategyproof1.2(gametheory)4NisanRonenAlgorithmicMechanismDesignAMD)56-8VCG9DistributedAlgorithmicMechanismDesignDAMD10DAMDBGP111.21.342.12.2--MisesHayek19741213LangeLerner14-18.(LeoHurwicz)1920(5)5niYiUiiW(,,)iiiieWUY=12(,,...,)neeee=ECalsamiglia197762.3(utilityfunction)51N(agents),()iittT∈212(,,...,)nooaaa=3u:OR,uiiaiu2.3.1Rationaliaiuquasi-linear72.3.2(,)mop=()o12(),(),...,()nppp1.iiAiiaA∈2.12(,,...,)nooaaa=3.12(,,...,)niippaaa=2.3.31112(,,,,...,)iiinaaaaaa−+−=12)(,,...,)(,niiaaaaa−=(Dominantstrategyi()iittT∈'iiaA∈(,)iiooaa−=,''(,)iiooaa−=(,)iiiippaa−=''(,)iiiippaa−='(,)(,')iiiiiitoptopvv+=+iaaNashEquilibrium''(,(,),(,))(,(,),(,))iiiiiiiiiiiiiiutoaapaautoaapaa−−−−≥'iiaa≠2.3.4direct-revelationIncentivecompatiblestrategyproof()iittT∈iticiia12(,,...,)nooaaa=u:OR,uiia8iuF:UNOO12(,,...,)niippaaa=iiv(,)iiivvto=2.3.4VCGVickreyGrovesClarkeVCGstrategyproofVCG{}{}0ssiipapa=∞−={}ia=∞{}0ia=i0VCGstrategyproof2.4strategyproofVCG9Selfish3.1VCGVCGiuisivisiuic.VCG:truthful3.2.GameSponsorStrategyproof103.2.1Uisivivis(1)iM≤≤iviciicvicic.uiciicv−,iicv−is,ijjipcvv=−+jjcv−iicv−is-jjiCVV+iC---iijjjjiiCVCVCVVC⇒+-jjiCVV+iv-0-iijjiiCVCVVV⇒+,Strategyproofiv,icisicic,iicv−isiicv−11iCisiicv−isicic.iicv−iijjC-VC-V,jjcv−iCiijjC-VC-Vis-jjiCVV+iCisiCStrategyproof3.2.2,,,:,,Chord,CAN,OceanStore,PAST,CFS,Napster,BitTorrent21222324iiC12ip0(01)iiiiCCkpp=+≤≤0iCkipiViiS0iiiVVgS=+0iViiigiSiV11CV−CV−Vi1234k100iC13108ip0.10.20.10.3iC251011g0.50iV10203025iSp20304050iV20355050iiCV−-18-30-40-39Pay111133.2.312(Non-cooperative)Strategyproofis(1)iN≤≤ic(ic).uisiv,,icivukkIsIcv∈−∑()I()()kkikJkIisJsIpcvcvc∈∈=−−−+∑∑kkJsJcv∈−∑JiiIsIpv∈∑ikkivikikisWsVpffC∈∈=−+∑∑,N1iVkkivikikisWsVpffC∈∈=−+∑∑kkikikivisVsWffpC∈∈⇒∑∑.()(1)()ikkikJkIIsIsJsIpncvncvv∈∈∈=−−−−+∑∑∑iiIsIpv∈∑,1()kkkJkIsJsIncvcvn∈∈−−−∑∑.kkJsJcv∈−∑kkIsIcv∈−∑0()kkkJkIsJsIcvcv∈∈−−∑∑N1iiIsIpv∈∑truthful14isicickkIsIcv∈−∑,kkIsIcv∈−∑is()()kkikJkIisJsIpcvcvc∈∈=−−−+∑∑icisicickkIsIcv∈−∑kkIsIcv∈−∑ic3.2.4(Cognitiveradio)252627:M(secondaryuser)12{,,...,}MuuuN(primarynodes)12{,,...,}MvvvL12{,,...,}l(secondaryuser)iv.()isic,1s2s1s2sCV−5s6s7s1523.3.GameSponsorStrategyproof3.3.1siuic,iciu(1)iM≤≤iciviicviviv.siviivc−,iivc−iu,ijjipvcc=−+jjvc−iivc−channel1234is1s2s3s4s5s6s7s8sic369456210iv711812kkIsIcv∈−∑-5-9(2ndmin)-11(min)-2ip(pay)----784-16sjjivcc−+iC-0-jjjjiivcvccc⇒+iujjivcc−+iv---iijjjjiivcvcvccv⇒+,.Strategyproofic,iviuiviv,iivc−iivc−iu,juiijjV-CV-C-jjiVCC+iviuiviviivc−ii