The Evolution of Probabilistic Reciprocity in a Mu

TheEvolutionofProbabilisticReciprocityinaMulti-agentEnvironmentwithNeighborhoodsEndaRidge,MichaelG.MaddenandGerardJ.LyonsNationalUniversityofIreland,Galway,{enda.ridge,michael.madden,gerard.lyons}@nuigalway.ieAbstract.Previousworkbyotherresearchershasinvestigatedtheevol-utionandstabilityofa‘probabilisticreciprocity’strategyinapackagedeliverydomainwhereallagentscouldcommunicatereputationstoeveryotheragent.Weextendthatworktothemorerealisticsituationofspa-tiallydistributedagentswithneighborhoodsthatrestrictagentinterac-tionandcommunication.Weimprovetheoriginalprobabilisticrecipro-citystrategywithamodificationthattarnishesthereputationsofagentsthatrepeatedlyrefuserequestsforhelp.Wetheninvestigatetheeffectofreducingneighborhoodsizefromthegeneralcaseofthe‘globalneighbor-hood’usedinpreviouswork.Ourexperimentsshowthatneighborhoodscanbereducedtoacriticalsizewithoutasignificantdegradationintheevolutionarystabilityoftheimprovedprobabilisticreciprocitystrategy.Wealsoshowthatlocatinglikeagentswithinanichecanmitigatethisdegradation.Fromamulti-agentdesignperspective,thismeansthatforapopulationwithagivenproportionofselfishanddishonestagents,communicationmaybereducedtowithinasubsetofthepopulationwhileretainingthesamesuccessofthereciprocativestrategy.Wealsoshowhowtoextendtheproblemdomaintoabstractawiderrangeofinteractionsituationsasdefinedintheliterature.1IntroductionandMotivationTheimportanceofthefieldofMulti-AgentSystem(MAS)researchiswellre-cognizedandtheemergenceofworkshopsandconferencessuchasCooperativeInformationAgents(CIA)andCooperativeInformationSystems(CoopIS)ac-knowledgescooperationasacriticalareaofinvestigationwithinthefield.Cooperationandinteractionarecommontotheverydefinitionsofagencyintheliterature.AmongFerber’s[1]minimalcommonpropertiesofanagentistheabilitytocommunicatedirectlywithotheragents.Maes[2]talksaboutautonomousagentsbeing“engagedinacooperativeprocess”withauser.InWooldridgeandJennings’weaknotionofagency[3],anagenthas“socialabil-ity”.AccordingtoWeiss[4],thekeyquestionforMASresearchis“Whenandhowshouldwhichagentsinteract—cooperateandcompete—tosuccessfullymeettheirdesignobjectives?”.Hementionsabilitiessuchasimprovingthestateofcoordination,reconcilingdisparateviewpointsandconflicts,negotiatingandformingorganizationalstructures.Clearly,interactionandspecificallycoopera-tionareveryimportanttothedesignofamulti-agentsystem.PopularMASframeworkssuchasJADE[5]reducetheagentenvironmenttoapassivemessagetransportsystem.TheadvantagestoaMASofarichandactiveenvironmentbeyondamessagetransportsystemareevidencedbysuc-cesswithexperimentsonalgorithmsinspiredbysocialinsects[6].Thesehavedemonstratedthatvirtualgradientfieldsandchemicaltrailscanaidagentcom-municationandcoordination[7].Researchtowardabetterunderstandingofsuchagent-environmentinterplayisinitsinfancy.Oneworthwhileendeavorisinvestigatingunderwhichenvir-onmentalconditionstherearebenefitstotheagentsocietyandunderwhichconditionstheimpositionofanenvironmentmaybedetrimentaltothedesiredsocietallevelbehavior.Inparticular,weareinvestigatingtheeffectofintroducingspatialdistribu-tionandneighborhoodstoSenandDutta’swork[8]ontheevolutionandsta-bilityofagentstrategiesemployingaprobabilisticreciprocitydecisionrule[9].Aspatiallydistributedenvironmentcouldarisewhereeitheragentsareactuallyphysicallydispersedorwhereagentsrepresentspatiallydispersedusers.Ubiquitouscomputingmaybeanexampleoftheformercase.Imagineashoppingmallwheresometenantshopshavesituatedagentsconnectedtoawirelessnetwork.Onepossiblecommercialdirectionforagentresearchistowardtheideaoftheseagentssharinginformationonpotentialcustomersandtheirrequirementsandtailoringservicestothoserequirements.Agentsrepresentingdifferentcategoriesofoutletshouldliketoestablishareciprocalrelationshipforidentifyingpotentialcustomersintheirvicinityanddirectingthosecustomerstooneanother.Couldsucharelationshipdevelopandbesustained?Secondly,caseswillarisewhereagentsarepooledinasoftwareenvironmentbutrepresentphysicallydispersedusers.ThisistrueintheVLABsystem[10]whichoffersabrokerageservicetohauliersrepresentedbyagents.Themod-ernhaulageindustryispan-continentalandofferscooperationopportunitiesforsharinghaulageresourcessuchasidletractorcabsandemptytrailerspace.However,overlargegeographicaldistancesandforinfrequentlyvisiteddeliverylocations,therewouldbefewerinteractionoccasionsforhauliers.Underwhatconditionswouldparasiticagentstrategiesdominatesuchasystem?Thispaperhasthefollowingoutline.Wefirstcoverthepreviousrelatedworkoncooperationandprobabilisticreciprocity.Section3describesourexperimentsetupandhowtheproblemdomainweusecouldbemodifiedtofitwithinmanyrecognizedcategoriesofinteractionsituation.Section4detailstheexperimentswehaverunandtheirresults.Section5drawsconclusionsfromtheseresultsandsuggestssomedirectionsforextendingourwork.2RelatedWork2.1DeterministicStrategiesAmongthemostfrequentlycitedworkoncooperationisthatofAxelrod[11–13].ThisworkinvestigatedtherobustnessofvariousdeterministicstrategiesinplayingthePrisoner’sDilemma[14].Ithasbeencriticizedonseveralfronts.Gametheor