For example, consider the Trading Agent Competition

  • 格式:pdf
  • 大小:527.60 KB
  • 文档页数:4

MethodsforEmpiricalGame-TheoreticAnalysis(ExtendedAbstract)MichaelP.WellmanUniversityofMichiganComputerScience&EngineeringAnnArbor,MI48109-2121USAwellman@umich.edu

AbstractAnemergingempiricalmethodologybridgesthegapbetweengametheoryandsimulationforpracticalstrategicreasoning.

Game-TheoreticAnalysisGame-theoreticanalysistypicallytakesatitsstartingpoint,mostnaturally,adescriptionofitssubject—thegame,afor-malmodelofamultiagentinteraction.TherecentsurgeininterestamongAIresearchersingametheoryhasledtonu-merousadvancesingamemodeling(Gal&Pfeffer2004;Kearns,Littman,&Singh2001;Koller&Milch2003;Leyton-Brown&Tennenholtz2003)andsolutiontech-niques(Gilpin&Sandholm2006;Porter,Nudelman,&Shoham2004),substantiallyexpandingtheclassofgamesamenabletocomputationalanalysis.Nevertheless,agreatmanygamesofinterestliewellbeyondtheboundaryoftractablemodelingandreasoning.Complexitymaybeman-ifestinthenumberofagentsorthesizeoftheirstrategysets(policyspaces),orthedegreeofincompleteandimperfectinformation.Theissuehereisnotmerelycomputationalcomplexityoftheanalysistask(e.g.,findingequilibrium),butactuallytheapparentimpracticalityofproducinganex-plicitgamemodelamenabletoautomatedreasoning.

Forexample,considertheTradingAgentCompetitionSupplyChainManagement(TAC/SCM)game(Eriksson,Finne,&Janson2006).Thisisawell-definedsix-playersymmetricgameofimperfectinformation,withinteractionrulesandexogenousstochasticprocessesdescribedinabriefspecificationdocument.Thereisnothingparticularlyun-usualaboutthisgame,neverthelessitpresentsadifficultchallengeforgame-theoreticanalysis.Thepolicyspacesandpayofffunctionsareclearlyinducedbythespecifiedrules,butthedescriptionisquiteindirect.Evengivencom-pletepoliciesforallsixagents,thereisnoapparentmeanstoderivetheexpectedpayoffs,shortofsamplingfromthestochasticenvironmentusinganavailablegamesimulator.Inthiscase,eachsamplepointtakesanhourtocompute.

Copyrightc󰀎2006,AmericanAssociationforArtificialIntelli-gence(www.aaai.org).Allrightsreserved.EmpiricalGamesTheapproachwehavebeenpursuinginmyresearchgroupforthepastfewyears1istotakethegamesimulatorasthefundamentalinput,andperformstrategicreasoningthroughinterleavedsimulationandgame-theoreticanalysis.Theba-sicobjectofanalysisisanempiricalgame,adescriptionoftheinteractionscenariowherepayoffinformationcomesintheformofdatafromobservationsorsimulations.Con-structingandreasoningaboutsuchgamespresentsmanyin-terestingsubproblems,whichcanbeaddressedbyexistingaswellasnewmethodsfromsimulation,statistics,search,andofcourse,standardgame-theoreticanalysis.Ifinditusefultodecomposeempiricalgame-theoreticanalysisintothreebasicsteps.Manyoftheresearchcon-tributionsinthisareamanifestastechniquesapplicabletooneofthesesubproblems,orresultsfromapproachestakentotheminagivendomain.ParametrizeStrategySpaceOftenthecomplexityofagameresidesinvastpolicyspacesavailabletoagents.Largespacescanarise,forexample,fromcontinuousormulti-dimensionalactionsets,aswellasfromimperfectinformation(whenactionsareconditionedonobservationhistories).Itisoftenusefulinsuchcasestoapproximatethegamebyrestrictingthestrategyspace,andstructuringthespacetoadmitasensiblesearchprocedure.Resultsfromanalysisofrestrictedsubgamesoftenprovideinsightintotheoriginalgame.Arguably,allapplicationsofgametheoryinthesocialsciencesemploystylizedabstrac-tions,whicharemanuallydesignedrestrictedversionsofac-tualgames.Fromourperspectivetheinterestingquestionishowtoautomatetheabstractionprocessstartingfromarichbutintractablegamespecification.Onegenericapproachtogeneratingcandidatestrategiesistostartfromsomebaselineorskeletalstructure,andsys-tematicallyintroduceparametricvariations.Someexamplesofnaturalbaselinesinclude:1.Truthfulrevelation.Forexample,inanauctiongame,thebaselinewouldbetobidone’struevalue.Inthefirst-1Similaroridenticaltechniqueshavealsobeenemployedbyotherresearchers,especiallythoseworkingexperimentallywithmultiagentsystems.Ourmainclaimisinsystematizingthemethodology,inexplicitgame-theoreticterms.

1552pricesealed-bidauction,thisstrategyguaranteeszerosur-plus(!),butitturnsoutthattheone-dimensionalfamilyofstrategiesdefinedbyshadingone’sbidbyamultiplicativefactorincludesexcellentstrategies,includingtheuniquesymmetricequilibrium(Reeves2005).2.Myopicbestresponse.Forexample,insimultaneousauc-tions(SAAs),anaturalstartingpointisstraightforwardbidding(Milgrom2000),wheretheagentbidsasthoughthecurrentpricesarefinal.WehaveexploredanextensivefamilyofbiddingstrategiesforSAAsstartingfromthisbaseline,ultimatelyproducingwhatweconsiderthelead-ingcontenderinthisdomain(Osepayshvilietal.2005).3.Gametreesearch.Thestartingpointformostprogramsdesignedtoplaycomplete-informationturn-takingzero-sumgamesisminimaxsearch.Inarecentstudyofa4-playerchessgame(Kiekintveld,Wellman,&Singh2006),wedefinedthestrategyspaceasasetofparamet-ricvariationsonthebasicgamesearcharchitecture(e.g.,controlknobsforsearchdepthandevaluationfunctionweights).EstimateEmpiricalGameToillustratesomeconceptsassociatedwithempiricalgames,weemployanexamplefromarecentanalysisofagentsfromthe2005TAC/SCMtournament(Wellmanetal.2006).Fig-ure1displaystheempiricalgame,estimatedfromasampleofover2000gameinstancesplayedwithvariouscombina-tionsofsixagentstrategies.Wedescribetheinterpretationofthisdiagraminthecourseofexplainingthegameestima-tionandanalysis.DirectEstimationThemoststraightforwardapproachtoestimateanempiricalgamefromdataistotreattheobserva-tionsasdirectevidenceforthepayoffsofthestrategypro-filesplayed.TowardthisendwecanbringtobearallthetoolsofMonteCarloanalysis,andrelatedstatisticaltech-niques.Wehavefoundespeciallyusefulthemethodofcon-trolvariates(L’Ecuyer1994)forreducingvariancebasedonadjustingforobservablefactorswithknowneffectsonpay-offs.InthecaseofTAC/SCM,themostimportantfactoriscustomerdemand,whichcansignificantlyinfluenceprofitsregardlessofagentstrategy.Applyingcontrolvariates,wederiveameasureofdemand-adjustedprofit,whichwethenemployasaproxyforpayoffsintheempiricalgameestima-tion(Wellmanetal.2005a).EachnodeinthegraphofFigure1representsapro-fileofagentstrategies.TAC/SCMisa6-playersymmetricgame,andsowithsixpossiblestrategiesthereareatotalof󰀁115󰀂=462distinctstrategyprofilestoconsider.Wecanre-ducethegametoasmallerversionbyrequiringmultiplesofplayerstoplaythesamestrategy.Specifically,byrestrictingattentiontocaseswherestrategiesareassignedtopairsofagents,wegetaneffective3-playergame,whichwedenoteSCM↓3.Thisgameiscombinatoriallysmaller,comprisingonly󰀁83󰀂=56profilesoverthesame6-strategyset.ThepayofftoastrategyinanSCM↓3profileisdefinedastheaveragepayofftothetwoagentsplayingthisstrategyintheoriginal6-playergame.Inseveralcontexts,wehavefoundexperimentallyandtheoreticallythatthisformofhierarchicalgamereductionproducesresultsapproximatingwelltheoriginalunreducedgame,withgreatcomputationalsavings(Reeves2005;Well-manetal.2005b).AlthoughwehavenotvalidatedthisspecificallyinTAC/SCM,intuitivelywewouldexpectthatpayoffsvarysmoothlywiththenumberofotheragentsplay-ingagivenstrategy.Our2110samplegameinstances(eachrequiringsevenprocessor-hourstogenerate,notcountingsetuptimeandoverheadduetofailures)aredistributedroughlyevenlyoverthe56SCM↓3profiles.Ingeneral,onemaywishtode-ploysamplesinamuchmoreactivelytargetedmanner.Inotherstudies,weallocatesampleswithaviewtowardcon-firmingorrefutingcandidateequilibria.Theideaistofocusonpromisingprofiles,andtheirneighborsinprofilespace—profilesthatdifferinthestrategychoiceofoneagent.Walshetal.(2003)haveproposedinformation-theoreticcriteriaforselectingprofilestosample,andotherapproachesfromMonteCarloanalysisandactivelearningshouldbeapplica-bleaswell.Onespecialissueforempiricalgamesistheneedtohan-dlepartialcoverageofobservationdata.Althoughinourillustrativeexamplewehavepayoffestimatesforallpossi-bleprofiles,inmanycasesthiswillnotbepossible.Wehavefounditusefulinsuchcasestoclassifyaprofilesintooneoffourdisjointcategories: