資源描述：
《No-Regret Learning in Bayesian Games貝葉斯博弈中的無(wú)后悔學(xué)習(xí)》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
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
