Using Similarity Criteria to Make Issue Trade-offs

UsingSimilarityCriteriatoMakeIssueTrade-OffsinAutomatedNegotiationsP.FaratinLaboratoryforComputerScienceMassachusettsInstituteofTechnologyCambridge,MA02139,[e-mail]-CSIC,CampusUAB,Bellaterra,08193Barcelona,[e-mail]Science,UniversityofSouthampton,SouthamptonSO171BJ,[e-mail]iationisakeyformofinteractioninsystemsthatarecomposedofmulti-pleautonomousagents.Theaimofsuchinteractionsistoreachagreementsthroughanitera-tiveprocessofmakingoffers.Thecontentofsuchproposalsare,however,afunctionofthestrategyoftheagents.Herewepresentastrategycalledthetrade-offstrategywheremultiplenegotiationdecisionvariablesaretraded-offagainstoneanother(e.g.,payingahigherpriceinordertoobtainanearlierdeliverydateorwaitinglongerinordertoobtainahigherqualityser-vice).Suchastrategyiscommonlyknowntoincreasethesocialwelfareofagents.Yet,todate,mostcomputationalworkinthisareahasignoredtheissueoftrade-offs,insteadaimingtoincreasesocialwelfarethroughmechanismdesign.Theaimofthispaperistodevelopaheuristiccomputationalmodelofthetrade-offstrategyandshowthatitcanleadtoanincreasedsocialwelfareofthesystem.Anovellinearalgorithmispresentedthatenablessoftwareagentstomaketrade-offsformulti-dimensionalgoodsfortheproblemofdistributedresourcealloca-tion.Ouralgorithmismotivatedbyanumberofreal-worldnegotiationapplicationsthatwehavedevelopedandcanoperateinthepresenceofvaryingdegreesofuncertainty.Moreover,weshowthatonaveragethetotaltimeusedbythealgorithmislinearlyproportionaltothenumberofnegotiationissuesunderconsideration.Thisformalanalysisiscomplementedbyanempiricalevaluationthathighlightstheoperationaleffectivenessofthealgorithminarangeofnegotiationscenarios.Thealgorithmitselfoperatesbyusingthenotionoffuzzysimilaritytoapproximatethepreferencestructureoftheothernegotiatorandthenusesahill-climbingtech-niquetoexplorethespaceofpossibletrade-offsfortheonethatismostlikelytobeacceptable.keywords:MultiAgentSystems,AutomatedNegotiation,FuzzySimilarity,Trade-offAlgorithm1IntroductionAutomatednegotiationisakeyformofinteractioninsystemscomposedofmultipleautonomousagents.Itissoimportantbecausetheagentsareautonomous(thatis,theydecideforthemselveswhatactionstheyshouldperform,atwhattime,andunderwhattermsandconditions[20])andcanhaveconflictingpreferencesoverstateoftheworld.Giventhefactsthatsuchagentshavenodirectcontroloveroneanotherandthereareofteninterdependenciesbetweentheiractions,conflictsneedtoberesolvedbytheprocessofmakingproposalsand/ortradingoffers,withtheaimoffindingamutuallyacceptableagreement.Inshort,bynegotiating.Morespecifically,weviewnegotiationasabargainingprocessbywhichajointdecisionismadebytwoparties.Thepartiesfirstverbalisecontradictorydemandsandthenmovetowardsagreements.Theprevalenceandimportanceofautomatednegotiationcanbeseeninthelargenumberofpro-posedmodels[8,18]:rangingfromauctionsinwhichtheagents’pricingdecisionproblemissolvedthroughshowingthedominanceofatruthfulbiddingstrategy[57],tomodelsinwhichtheagents’argueforpositionsandaimtopersuadetheiropponentsofthevalueofparticularactions[37].Inthisworkweareinterestedinconflictingpreferencesovercomplexmulti-dimensionaldecisionproblemsinvolvedinthebi-lateralresourceallocationnegotiationofservices[50].Insuchduopolisticnegotia-tions,oneproducerandoneconsumerhavetobargainandcometoamutuallyacceptableagreementoverthetermsandconditionsunderwhichtheproducerwillexecutesomeactivity(service)fortheconsumer.1Specificdecisionvariablesthattypicallyneedtobemutuallyagreedincludethepriceoftheservice,thetimeatwhichitisrequired,thequalityofthedeliveredservice,andthepenaltytobepaidforrenegingupontheagreement.Thegenerativemodelofbargainingpresentedhereshareswithothermechanismdesignmodelstheexplicitdesignofprotocolswhoseexecutionisafunctionoftheagent’sstrategy[3].Aprotocolisasetof“rulesofencounter”[43]betweenthenegotiationparticipants;thatis,whocansaywhat,towhom,atwhattime.Givenaprotocol,anagentstrategythendefinesthemodelthattheindividualparticipantsapplytoactinlinewiththeprotocolinordertoachievetheirnegotiationobjectives.How-ever,thegoalsmotivatingthedesignoftheprotocolandstrategyinthisworkaredifferentfromthoseofclassicmechanismdesign.Thelatteraremoreinterestedinsolvingthestrategicmis-representationproblemthatoccurswheneveragentshaveanincentivetomis-representtheirtruepreferencesinor-dertomaximisetheirownutility.Amechanismdesignsolutiontothisproblemconsistsofcentrallydesigningdirectincentivecompatibleorstrategyproofdecisionrulesthathavecertainproperties[29,43].Althoughweacknowledgestrategicmisrepresentationisaconcerninmulti-agentsystems,wearealsointerestedinthetypesofdecisionproblemsthatarenotonlyhighlycomplexindimen-sionality(ratherthansimplydividingthecake)butthatalsoplaceboundinglimitsontheperformanceoftheagentbythevirtueoftheircomplexity.Indeed,thecombinationofthesetwofactorscanleadtosub-optimaldecisions,therebythreateningclassicsolutionconceptsfrommechanismdesign[8].Therefore,wemaketheimplicitassumptionthatsocialagreementstoco