资源描述:
《No-Regret Learning in Bayesian Games贝叶斯博弈中的无后悔学习》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、No-RegretLearninginBayesianGamesJasonHartlineVasilisSyrgkanisNorthwesternUniversityMicrosoftResearchEvanston,ILNewYork,NYhartline@northwestern.eduvasy@microsoft.comEvaTardos´CornellUniversityIthaca,NYeva@cs.cornell.eduAbstractRecentprice-of-anarchyanalyse
2、sofgamesofcompleteinformationsuggestthatcoarsecorrelatedequilibria,whichcharacterizeoutcomesresultingfromno-regretlearningdynamics,havenear-optimalwelfare.Thisworkprovidestwomaintech-nicalresultsthatliftthisconclusiontogamesofincompleteinformation,a.k.a.,
3、Bayesiangames.First,near-optimalwelfareinBayesiangamesfollowsdirectlyfromthesmoothness-basedproofofnear-optimalwelfareinthesamegamewhentheprivateinformationispublic.Second,no-regretlearningdynamicsconvergetoBayesiancoarsecorrelatedequilibriumintheseincomp
4、leteinformationgames.TheseresultsareenabledbyinterpretationofaBayesiangameasastochasticgameofcompleteinformation.1IntroductionArecentconfluenceofresultsfromgametheoryandlearningtheorygivesasimpleexplanationforwhygoodoutcomesinlargefamiliesofstrategically-c
5、omplexgamescanbeexpected.Theadvancecomesfrom(a)arelaxationtheclassicalnotionofequilibriumingamestoonethatcorrespondstotheoutcomeattainedwhenplayers’behaviorensuresasymptoticno-regret,e.g.,viastandardonlinelearningalgorithmssuchasweightedmajority,and(b)ane
6、xtensiontheoremthatshowsthatthestandardapproachforboundingthequalityofclassicalequilibriaautomaticallyimpliesthesameboundsonthequalityofno-regretequilibria.ThispapergeneralizestheseresultsfromstaticgamestoBayesiangames,forexample,auctions.Ourmotivationfor
7、consideringlearningoutcomesinBayesiangamesisthefollowing.Manyimpor-tantgamesmodelrepeatedinteractionsbetweenanuncertainsetofparticipants.Sponsoredsearch,andmoregenerally,onlinead-auctionmarketplaces,areimportantexamplesofsuchgames.Plat-formsarerunningmill
8、ionsofauctions,witheachindividualauctionslightlydifferentandofonlyverysmallvalue,butsuchmarketplaceshavehighenoughvolumetobethefinancialbasisoflargeindustries.ThisonlineauctionenvironmentisbestmodeledbyarepeatedBayes