Computing Bayes-Nash equilibria through support enumeration methods in Bayesian two-player strategic-form games

《Computing Bayes-Nash equilibria through support enumeration methods in Bayesian two-player strategic-form games》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ComputingBayes-NashEquilibriathroughSupportEnumerationMethodsinBayesianTwo-PlayerStrategic-FormGamesSofiaCeppi,NicolaGatti,andNicolaBasilicoDipartimentodiElettronicaeInformazionePolitecnicodiMilanoMilano,ItalyEmail:{ceppi,ngatti,basilico}@elet.polimi.itAbstract—T

2、hecomputationofequilibriaingamesisachal-Nashequilibriaincomplete-informationgames[7],howeverlengingtask.TheliteraturestudiestheproblemoffindingNashtheseresultscannotbegeneralizedtotheBayesiancase.equilibriawithcomplete-informationgamesindepth,butnotWeexplainthere

3、asons.Ontheonehand,BayesiangamesenoughattentionispaidtosearchingforequilibriainBayesiancanpresentcharacteristicsdifferentfromthoseofcomplete-games.Customarily,thesegamesarereducedtocomplete-informationgamesandstandardalgorithmsforcomputingNashinformationgames,wh

4、ichusuallyadmitequilibriawithsmallequilibriaareemployed.However,noworkstudiedhowthesesupports[8].1Ontheotherhand,thereductiontocomplete-algorithmsperformwithBayesiangames.Inthispaperwefocusinformationgamesraisesseveralproblemsintheapplicationontwo-playerstrategi

5、c-formgames.WeshowthatthemostofalgorithmsforcomputingNashequilibria.Theexactal-efficientalgorithmforcomputingNashequilibriawithGAMUTgorithmsfortwo-playercomplete-informationstrategic-formdata(i.e.,Porter-Nudelman-Shoham)isinefficientwithBayesiangames,weprovideanex

6、tension,andweexperimentallyevaluategamesare:Lemke-Howson(LH)[9],basedonlinearcom-itsperformance.plementarityproblem,Porter-Nudelman-Shoham(PNS)[10],IndexTerms—Algorithmicgametheory,Bayes-Nashequilib-basedonsupportenumeration,andSandholm-Gilpin-Conitzerrium,enume

7、rationalgorithm2(SGC)[7],basedonmixedintegerlinearprogramming.Itisknownthatthemostefficientreduction(i.e.,thesequenceI.INTRODUCTIONform[12])makesLHinapplicable,requiringalternative(lessNon-cooperativegametheoryprovideselegantmodelsandefficient)algorithmsforlinearc

8、omplementarityproblems.Insolutionconceptsforsituationswhereinrationalagentscanthispaper,weshowthatsuchreductionmakesthemosteffi-strategicallyinteract[1].Thecentralsolu