資源描述:
《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.1IntroductionArecentcon?uenceofresultsfromgametheoryandlearningtheorygivesasimpleexplanationforwhygoodoutcomesinlargefamiliesofstrategically-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,butsuchmarketplaceshavehighenoughvolumetobethe?nancialbasisoflargeindustries.ThisonlineauctionenvironmentisbestmodeledbyarepeatedBayes