P. Experimental evaluation of a heuristic approach

ExperimentalEvaluationofaHeuristicApproachforP2PNegotiationStefaniaCostantini,AriannaTocchio,andPanagiotaTsintzaDip.diInformatica,UniversitµadiL'Aquila,Coppito67100,L'Aquila,Italyfstefcost,tocchio,[e-mail]orkshoponCooperativeInfor-mationAgents(CIA2003),MarcoCadoliproposedanapproachwheretheprocessofnegotiationisconsideredasadistributedconstraintsat-isfactionproblem,andthenegotiationspacesasconvexregions:i.e.,allpointsincludedintheindividualregioncorrespondstoacceptableagree-ments.Inthispaper,weevaluateanextensionthatwehaveproposedin[1].Theproposedalgorithmovercomessomeproblemsoftheapproach,andinperspectivealsoovercomesthelimitationtopolyhedralnegoti-ationareas.Weshowbyanumberofexperimentsthattheextendedapproachworksproperlyandthattheinteractioncomplexityisaccept-able1IntroductionNegotiationisadecision-makingprocessinwhichmultiplepartiesjointlymakedecisionstoresolvecon°ictinginterests.Inparticular,automatednegotiationcanbeconsideredasaparticularkindofinteractioninwhichagroupofagents,withadesiretocooperatebutwithcon°ictinginterests,workstogetherinaimtoreachacommongoal.Aparticularmechanismofnegotiationistheproposal-basednegotiation.Inthiscase,theprocessinvolvesanumberofagentswhichusuallyhavealimitedcommonknowledgeontheotheragentsconstraints,i.e.,aboutthenegotiationspaces.Inproposal-basednegotiation,theinformationexchangebetweenthepartiesisinformofo®ers(internalpointsofthenegotiationspaces)ratherthanconstraints,preferencesorargumentation.Eachagentisabletocomputethepointsoftheindividualareasandtousetheminordertoreachanagreement.Theresearchreportedinthispaperpresentsanddiscussesasetofexperi-mentsconcerninganextension,introducedin[1],toapreviousworkbyMarcoCadoli,introducedin[2].TheapproachbyMarcoCadoliconcernsproposal-basednegotiation,fromthepointofviewofminimizingthenumberoftheinter-actionsbetweentheautomatedagentsinvolvedintheprocess.Thisinordertoreducethecomputationalcomplexityandthusspeed-upthesearchofanagree-ment.Negotiationspacesareconsideredasconvex,i.e.,allpointsbetweentwoacceptablevariableassignmentsareacceptableaswell.Theadmissibleo®ersareinternalpointsofthenegotiationareas,andthosewillbetheonlyinformationexchangedbetweentheagents.Themainpointisthatagentsaresupposedtobeabletoreasonintermsofprojections.Thiskindofreasoningcanhelptheagentscomputesubsequento®ers:infact,asdiscussedlater,theyarethusabletoexcludecertainpointsoftheindividualnegotiationareas.Therestofthispaperisstructuredasfollows.Section2givesanoverviewofthetheoreticalbackgroundanddiscussesthemotivationsofthiswork.Insection3weshortlypresenttheproposedextensionandthealgorithmthatwehaveadoptedfortheimplementation.Section4isdedicatedtoillustratetheexperimentsthatwehaveperformedandtoexplaintheresultsofthetestingphase.InSection5wecomparetheextendedstrategyandtheoriginalone.ConclusionsandfutureworkarepresentedinSection6.2ReasoningbymeansofprojectionsInthissectionwe¯rstpresentthebasicapproachbyMarcoCadoliandthendiscusswhysomeextensionsareneededanduseful.2.1TheapproachbyMarcoCadoliinanutshellInMarcoCadoli'sapproach,negotiationisconsideredasadistributedconstraintsatisfactionproblem,andthenegotiationspacesasconvexregions(i.e.allpointsincludedintheindividualregionsareacceptableaswell).Theapproachprovesthatreasoningintermsofprojectionscanleadtoaprotocolthatalwayscon-vergesand,insomecases,allowsonetoobtainlargesavingsintermsofnumberofproposedvertices:intheworstcaseinfact,thenumberofagent'sinteractionsitisexponentialinthenumberofvariablesandinthenumberofconstraints.Inmathematics,aprojectionisanyoneofseveraldi®erenttypesoffunctions,mappings,operations,ortransformations.Inthispaper,weconsideraprojectionastheimageofageometric¯gurereproducedonaline,plane,orsurface.Morespeci¯cally,weconsidertheprojectionofalinesegmentoveranotherone.Werecallthisconceptbymeansofanexample(Figure1).Intheexample,weconsiderthefourpointsA1,A2,B1,B2.The¯gurehighlightstwoprojections:1.theprojectionofthesegmentA1A2overB1B2(denotedwith¦(B1B2;A1A2)anddelimitedbyr2B1B2r1),and2.theprojectionofB1B2overA1A2(denotedwith¦(A1A2;B1B2)andde-limitedbys1A1A2s2).InMarcoCadoli'sapproach,whenano®eroccursthereceivingagentiscapa-bleofconstructingaprojection(i.e.,newconstraintsobtainedbyconnectingtheproposalsmadesofar)whichhelpshercomputetheo®ers.Aftertheprojectionconstruction,theagentperceivesthefactthatallpointsincludedintheprojec-tionareacannotbeacceptedfromtheopposer.Thereasonsarediscussedin[2].Inthisway,theagentexcludesfromthepotentialsubsequento®ersallpoints(Β1Β2,Α1Α2)B1B2A2A1r2r1s1s2Π(A1A2,B1B2)ΠFig.1.Linessegmentsprojectionswhichbelongtothisparticulararea,thusavoidingunnecessaryproposals.Marcocadoliconsidersonlytheverticesofthenegotiationspaceaspossibleo®ers.Asthenumberofverticesofconvexregionsis¯nite,theprocessofnegotiationisguaranteedtoterminate.Inparticular,terminationoccurseitherwhenapointofagreementintheintersectionofthenegotiationareasisfound,orwhenitisprovedthatthereisnosuchpoint.BelowweillustrateMarcoCadoli'sbasicapproachbymeansofanexample