Automated Negotiation and Decision Making in Multi

AutomatedNegotiationandDecisionMakinginMultiagentEnvironments
SaritKraus1Dept.ofMathematicsandComputerScienceBar-IlanUniversityRamat-Gan,52900Israel2InstituteforAdvancedComputerStudiesUniversityofMaryland,CollegePark,MD20742,[e-mail]:strategicnegotiation,auctions,coalitionfor-mation,market-orientedprogrammingandcontracting.Italsopresentslogicalbasedmechanismsforargumentations.Thefocusofthesurveyisonnegotiationofself-interestedagents,butseveralmechanismsforco-operativeagentswhoneedtoresolveconflictsthatarisefromconflictingbeliefsaboutdifferentaspectsoftheirenvironmentarealsomentioned.Forspacereasons,wecouldn’tcoveralltherelevantworks,andthepa-persthatarementionedonlydemonstratethepossibleapproaches.Wepresentsomeofthepropertiesoftheapproachesusingourownpreviouswork.1IntroductionNegotiationhasbeenasubjectofcentralinterestinmulti-agentsystems,asithasbeenineconomicsandpoliticalscience.Thewordhasbeenusedinavari-etyofways,thoughingeneralitreferstocommunicationprocessesthatfurthercoordinationandcooperation.Negotiationscanbeusedtoresolveconflictsinawidevarietyofmulti-agentdomains[28].Examplesofsuchapplicationsincludeconflictsovertheusageofjointresourcesortaskassignments,conflictsconcern-ingdocumentallocationinmulti-serverenvironmentsandconflictsbetweenabuyerandasellerinelectroniccommerce.Whenbuildinganautonomousagentwhichiscapableofflexibleandsophis-ticatednegotiation,themainquestionsthatshouldbeconsideredare:(i)what
ThisworkissupportedinpartbyNSFundergrantNo.IIS-9820657.ThispaperisbasedonchaptersinS.Kraus.StrategicNegotiationinMulti-AgentEnvironments,MITPress,Cambridge,USA,2001andonS.Kraus,K.SycaraandA.Evenchik.Reachingagreementsthroughargumentation:alogicalmodelandimplementation,ArtificialIntelligenceJournal,104(1-2):1-69,1998.M.Lucketal.(Eds.):ACAI2001,LNAI2086,pp.150–172,2001.c
Springer-VerlagBerlinHeidelberg2001AutomatedNegotiationandDecisionMakinginMultiagentEnvironments151negotiationprotocolwillbeused?(ii)whatreasoningmodel,decisionmakingproceduresandstrategieswilltheagentsemploy?Severalprotocolsforauctions,strategicnegotiationandcoalitionformationareconsideredandwediscusstheirapplicabilityinvariousmulti-agentdomains.Wewillpresentformalmodelsforagentreasoningandwewilldiscussmethodsforidentifyingstrategiesforagentsinteractingusingaspecificprotocol.Evaluationoftheresultsofmulti-agentprotocolsisnotaneasytask.Sincetheagentsareself-interested,whensaying,forexample,a“negotiationwassuc-cessful”thequestion“successfulforwhom?”mustbeasked,sinceeachagentisconcernedonlyaboutitsownbenefitsorlossesfromtheresolutionofthenego-tiation.Nevertheless,therearecertainparametersthatcanbeusedtoevaluatedifferentprotocols.NegotiationTime:Negotiationswhichendwithoutdelayarepreferredovernegotiationswhicharetime-consuming.Itisassumedthatadelayinreachinganagreementcausesanincreaseinthecostofcommunicationandcomputationtimespentonthenegotiation.Wewanttopreventtheagentsfromspendingtoomuchtimeonnegotiationsresultingindeviationfromtheirtimetablesforsatisfyingtheirgoals.Efficiency:Anefficientoutcomeofthenegotiationsispreferred.Inotherwords,anoutcomethatincreasesthenumberofagentswhichwillbesatisfiedbythenegotiationresultsandtheagents’satisfactionlevelsfromthenegotiationresults.Thus,itispreferredthattheagentsreachParetooptimalagreements1Inaddition,ifthereisanagreementthatisbetterforalltheagentsthanoptingout,thenitispreferredthatthenegotiationswillendwithanagreement.Simplicity:Negotiationprocessesthataresimpleandefficientarebetterthancomplexprocesses.Beinga“simplestrategy”meansthatitisfeasibletobuilditintoanautomatedagent.A“simplestrategy”alsopresumesthatanagentwillbeabletocomputethestrategyinareasonableamountoftime.Stability:Asetofnegotiationstrategiesarestableif,giventhatalltheotheragentsincludedinthesetarefollowingtheirstrategies,itisbeneficialtoanagenttofollowitsstrategytoo.Negotiationprotocolswhichhavestablestrategiesaremoreusefulinmultiagentenvironmentsthanprotocolswhichareunstable.Iftherearestablestrategies,wecanrecommendtoallagentdesignerstobuildtherelevantstrategiesintotheiragents.Nodesignerwillbenefitbybuildingagentsthatuseanyotherstrategy.Moneytransfer:Moneytransfermaybeusedtoresolveconflicts.Forexam-ple,aservermay“sell”adataitemtoanotherserverwhenrelocatingthisitem.Thiscanbedonebyprovidingtheagentswithamonetarysystemandwithamechanismforsecurepayments.Sincemaintainingsuchamone-tarysystemrequiresresourcesandefforts,negotiationprotocolsthatdonotrequiremoneytransfersarepreferred.1AnagreementisParetooptimalifthereisnootheragreementthatdominatesit,i.e.,thereisnootheragreementthatisbetterforsomeoftheagentsandnotworsefortheothers.152SaritKrausTheremainderofthispaperisstructuredasfollows.InthenextsectionwewillpresentashortsurveyofnegotiationapproachesinDistributedArtificialIntelligence(DAI)andinsocialsciences.Thenwewilldiscussthestrategic-negotiationmodel(section2.3)whichisba