Integrative Negotiation Among Agents Situated in Organizations

IntegrativeNegotiationAmongAgentsSituatedin

Organizations

XiaoqinZhang

ComputerandInformationScienceDepartmentUniversityofMassachusettsatDartmouth

x2zhang@umassd.edu

VictorLesser

ComputerScienceDepartmentUniversityofMassachusettsatAmherst

lesser@cs.umass.edu

TomWagner

AutomatedReasoningGroupHoneywellLaboratoriesTom.Wagner@honeywell.com

Abstract—Thispaperaddressestheproblemofnegotiationinacomplexorganizationalcontext.Anintegrativenegotiationmechanismisintroduced,whichenablesagentstodynamicallyselectanegotiationattitudebasedonthedegreeofexternaldirectedness.Experimentalworkexploresthequestionofwhetheritalwaysimprovestheorganization’ssocialwelfaretohaveanagentbecompletelyexternally-directedwhennegotiatingandmakingchoices.Resultsshowthattherearesituationsinwhichitisbetterfortheorganizationifagentsarepartiallyexternally-directedintheirnegotiationswithotheragentsratherthancompletelyexternally-directed.Thepaperdiscussesthedrivingfactorsbehindthisunexpectedresult.

Keywords:integrativenegotiation,motivation,groupandorganizationaldynamics

I.INTRODUCTION

InMulti-Agentsystems(MAS),agentsnegotiateovertaskallocation,resourceallocationandconflictresolutionprob-lems.Untilnowalmostallrelatedworkonnegotiationcanbecategorizedasfallingintooneoftwogeneralclasses:ne-gotiationinmarket-likesystemsandnegotiationindistributedproblemsolvingsystems.Inmarket-likesystems,agentsareself-interestedandnegotiatetomaximizetheirownlocalutility[1],[2],[3],[4],[5],[6];indistributedproblemsolvingsystems,agentsnegotiatetofindasolutionthatincreasestheirjointutility[7],[8],[9].Thislatterapproachisbasedontheassumptionthatfullcooperation,atthelocalagentlevel,willleadtoanoverallincreaseinthesocialwelfareofthesystem.

ThismaterialisbaseduponworksupportedbytheNationalScienceFoundationunderGrantNo.IIS-9812755andtheAirForceResearchLab-oratory/IFTDandtheDefenseAdvancedResearchProjectsAgencyunderContractF30602-99-2-0525.TheU.S.GovernmentisauthorizedtoreproduceanddistributereprintsforGovernmentalpurposesnotwithstandinganycopy-rightannotationthereon.Disclaimer:Theviewsandconclusionscontainedhereinarethoseoftheauthorsandshouldnotbeinterpretedasnecessarilyrepresentingtheofficialpoliciesorendorsements,eitherexpressedorimplied,oftheDefenseAdvancedResearchProjectsAgency,AirForceResearchLaboratory/IFTD,NationalScienceFoundation,ortheU.S.Government.

Littleworkhasbeendonetostudynegotiationbetweenthesetwoextremecases.

Whenanagentisnegotiatingwithotheragentsovertaskperformanceand/orresourceconsumption,itmustexplicitlyreasonaboutthevalueofperforming/not-performingthetasksorallocating/not-allocatingtheresource.Thewayinwhichthevalueiscomputeddiffersdependingonhowtheagentchoosestoevaluateitsnegotiationswiththeotheragents.Welabelanagentcompletelyself-directedifitdoesnottakeintoconsiderationhowmuchutilitytheotheragentcanpotentiallygainwhenthelocalagentmakesacommitmenttocompletetherequestedtaskasaresultofnegotiation.Inotherwords,theagentiscompletelydrivenbythevaluesthatitlocallyattachestotaskperformanceorresourceconsumption.Incontrast,anagentiscompletelyexternally-directedifitseestheotheragent’sgainasitsownina1:1fashion.Notethattheselabelsidentifyhowvalueorutilityiscomputedanddonotrelatetotheagent’soverallobjectives.Wedistinguishthenotionofagentsbeingself-interestedorcooperativefromthenotionofanagentbeingself-directedorexternally-directed.Wecallanagentself-interestedifitsorganizationalgoalistomaximizeonlyitslocalutilityandanagentiscooperativeifitisintentonmaximizingtheoverallsocialutility.Whereasthe“direction”terminologydefineshowvalueiscomputedbytheagent,theself-interested/cooperativeterminologyspecifiestheagent’soverallgoal.Withrespecttonegotiation,thedegreeofanagent’sself-interestedness/cooperativenessdefinesitsmeta-goalintermsofitsoverallrelationshiptotheagentsociety,whilethedegreeofself-directness/externally-directnessde-finesthelocalmechanismusedbyanagenttohelpachieveitsmeta-goal.Forinstance,iftheagentiscooperativeandexternallydirected,itwillworktomaximizesocialwelfareandwillbaseitscomputations,duringnegotiation,onthevaluescommunicatedtoitbyotheragents.However,anagentwhoiscooperativeandself-directedwillalsoworktomaximizesocialwelfare,butbaseditsowncalculation/predictionof

socialwelfare.Itdoesnotconsiderhowmuchtheotheragentwouldpotentiallygainasaresultofaspecialcommitment,becausetheotheragent’spotentialgainisnotthoughtbythisagentasareliablefactorthatindicatesofsocialwelfare,thisagentratherleavestheinformationoutofitsconsideration.Wefeelthatasthesophisticationofmulti-agentsystemsincreases,MASwillbeneithersimplemarketsystemswhereeachagentispurelyself-interested,seekingtomaximizeitslocalutility,nordistributedproblemsolvingsystemswhereallagentsarecompletelycooperativeworkingtomaximizetheirjointutility.Thiswilloccurforthefollowingreasons.First,agentsfromdifferentseparateorganizationalentitieswillcometogethertodynamicallyformvirtualorganizations/teamsforsolvingspecificproblemsthatarerelevanttoeachoftheirorganizationalentities[10].Howtheseagentsworkintheirteamswilloftenbedependentontheexistenceofbothlong-termandshort-termrelationshipsthatarebasedonthegoalsoftheirunderlyingorganizationalentities.Secondly,evenforagentsfromorganizationswithmeta-goalsthatindicateself-interestedness,itmightbebeneficialforthemtobepartiallyexternally-directedwhentheyareinthesituationswheretheywillhaverepeatedtransactionswithotheragentsfromotherorganizationalentities.Additionally,evenagentsworkingsolelywithagentsoftheirownorganizationalentitieswilltakevaryingnegotiationattitudesinthespectrumofcompletelyexternally-directedtocompletelyself-directedinorderfortheorganizationtobestachieveitsoverallgoal.Thelatterperspectiveisbasedonabounded-rationalargument:itisnotpossiblefromacomputationalorcommunicationalperspectiveforanagenttobefullycooperative,becausetheagentneedstotakeintoaccountthecurrentandexpectedchangeintheutilitiesofallagentsintheorganizationandthestateofachievementofallorganizationalgoalstobefullycooperative.Thus,itmaybebestfortheorganizationtohaveagentsbeingpartiallyexternally-directedintheirlocalnegotiationwithotheragentsratherthanbeingcompletelyexternally-directedinordertodealmoreeffectivelywiththeuncertaintyofnothavingamoreinformedviewofthestateoftheentireagentorganization.Wefeelasimilarargumentcanbemadeforself-interestedagents.Itmaynotalwaysbeadvantageousforthemtotakethenegotiationattitudeofcompletelyself-directed.Rather,insomecontext,themoreexternal-directedattitudewillleadtoanincreaseintheirownlocalutility.

Notethatthisworkpertainstodeliberateagentssituatedinanagentsocietywherethereareorganizationalrelationshipsamongagents.Theagentscanmakechoicesaboutwithwhomtocollaborate,howtonegotiate,whattochargeforservices,etc.Further,thenegotiationattitudewillbedependentontherelationshipsamongthenegotiatingpartiesandtheparticularnegotiationissue,andthestateofachievementofrelevantorganizationalgoals.Intheexperimentalworkreportedinthispaper,wearealsoassumingthatagentsarenotactinginahostilemannernorgamingthesituationbasedonthemeta-levelinformationtransferredamongagents.However,wefeelthatbyaddingsomeadditionalmechanismsthatallowanagenttoadjustthecharacterofthemeta-levelinformationthatisexchanged,hostile/gamingagentscanbehandledwithinthe2

basicframeworklaidoutinthispaper.

Let’sconsiderthesupplychainexampleinFigure1.Therearedifferentorganizationalrelationshipsamongagents.Forinstance,thereisanagent(agentIBM2)whoproducesharddrives,belongingtotheIBMCompany.Itprovidesharddrivesforthreedifferentagents,withthefollowingorganizationalrelationshipstoit:

1)AgentIBM2providesharddrivesfortheotheragent(agentIBM1),whichalsobelongstoIBMbutassem-2)blesAgentPCs.

IBM2providesharddrivestoanNECagent(agentNEC),andasthetransactionsbetweenthembecomemorefrequentandregular,theyformavirtual3)organizationAgentIBM2basedoccasionallyontherecentprovidestransactions.

harddrivesforadistributorcenter(agentDIS)basedonasimplemarket-likemechanism.

WhenagentIBM2negotiateswiththesethreeagents,itshouldusedifferentnegotiationattitudesthatreflectsthedifferentrelationships.Forinstance,whenitnegotiateswithagentIBM1,itmayneedtobemoreexternally-directedthanitistowardstheothertwoagentsifitsmostimportantmeta-goalistoincreasetheutilityofIBM.However,evenforthegoodofIBM’sbenefit,itmaynotbethebestchoiceforagentIBM2alwaystobecompletelyexternally-directedto-wardsagentIBM1.SometimesitmaybringIBMmoreprofitforagentIBM2toprovideharddrivestoagentDISratherthantoagentIBM1,ifagentIBM1isnotcertainwhetheritreallyneedstheharddrive.

WhenagentIBM2negotiateswithagentNEC,itmayneedtobemoreexternally-directedthanitistowardsagentDISgiventhevirtualorganizationithasformedwithagentNEC.TheappropriateleveloflocalcooperationdependsonhowimportanttheutilityincreaseofthisvirtualorganizationistoagentIBM2,howthegoaltoincreasetheutilityofthisvirtualorganizationrelatestoitsothergoals,andhowcertaintheinformationprovidedbyagentDIScomparestotheinforma-tionreceivedfromothersources.Also,aswenoticedbefore,theformationofthisvirtualorganizationisdynamic;itmayalsodisappearsometimelaterastheenvironmentchanges,soagentIBM2shouldadaptitsnegotiationattitudedynamicallytoo.

Fromtheaboveexampleswefinditnecessarytohaveamechanismthatsupportsagentschoosingfromamongmanydifferentnegotiationattitudesinthespectrumfromcompletelyself-directedtocompletelyexternally-directed,andeasilyswitchingfromoneattitudetoanother.Thechoiceofne-gotiationattitudeshoulddependontheagent’sorganizationalgoals,thecurrentenvironmentalcircumstance,whichagentitisnegotiatingwith,andwhatissueisundernegotiation.Thereshouldalsobenorequirementofacentralizedcontrollerthatcoordinatestheagent’sbehavior.

Sofar,therehasbeennosuchnegotiationmechanismwhichprovidestheabovecapabilitiesforagents(seerelatedworkinSectionVI).Inthispaper,weintroduceannegotiationmech-anismwhichenablesagentstoconstructnegotiationattitudesinthespectrumfromcompletelyself-directedtocompletelyexternally-directedinauniformreasoningframeworkcalled

3

Fig.1.Supplychainexample

theMotivationalQuantities(MQ)framework[11].TheMQframeworkprovidestheagentwithanappropriateutilitymodelforquantitativelyreasoningabouthowspecifictaskallocationdecisionrelatestosatisfyingitsorganizationalgoals.Intheremainderofthepaper,theMQframeworkisreviewedinSectionII.SectionIIIdescribestheintegrativenegotiationmechanism.SectionIVusesexamplestoexplaintheideasmorefully.SectionVpresentsexperimentalresultsthatex-plorehowdifferentnegotiationattitudesaffecttheagent’sperformanceandthesocialwelfareoftheoverallsystem.SectionVIdiscussesrelatedworkandSectionVIIconcludesandidentifiesfurtherwork.

II.MQFRAMEWORKS

TheMQframework[11]isanagentcontrolframeworkthatprovidestheagentwiththeabilitytoreasonaboutwhichtasksshouldbeperformedandwhentoperformthem.Thereasoningisbasedontheagent’sorganizationalconcerns.Thebasicassumptionisthatagentsarecomplex,withmultiplegoalsrelatedtothemultiplerolestheyplayintheagentsociety.Theprogresstowardsonegoalcannotsubstitutefortheprogresstowardsanothergoal.MotivationalQuantities(MQs)areusedtorepresenttheprogresstowardsorganizationalgoalsquanti-tatively.EachagenthasasetofMQswhichitisinterestedinandwantstoaccumulate.EachMQiinthissetrepresentstheprogresstowardoneoftheagent’sorganizationalgoals.EachMQiisassociatedwithapreferencefunction(utilitycurve),Ufi,thatdescribestheagent’spreferenceforaparticularquantityoftheMQi.Theagent’soverallutilityisafunctionofthedifferentutilitiesassociatedwiththeMQsittracks:Uagent=γ(Ui,Uj,Uk,..).Thestructureoffunctionγrepresentstheagent’spreferenceandemphasisondifferentorganizationalgoals.TheMQframeworkthusprovidesanapproachtocomparetheagent’sdifferentmotivationalfactorsthroughamulti-attributefunction.Notallagentshavethesame

MQset.Iftwoagentsneedtoconstructacommitmentthroughcoordinationornegotiation,anduseMQasanexchangemedium,theyneedtohaveatleastoneMQincommon,orbewillingtoformonedynamically.DifferentagentsmayhavedifferentpreferencesforthesameMQ.

MQsareconsumedandproducedbyperformingMQtasks.Theagent’soverallgoalistoselecttaskstoperforminordertomaximizeitslocalutilitythroughcollectingdifferentMQs.Thisdoesnotmeanthattheagenthastobe“self-interested”;itonlymeansthattheagentselectsitsactionstocontributetoitsmultipleorganizationgoals.If“tohelpagentB”isoneofthegoalsofagentA,thenagentAwillactinacooperativemannerwithrespecttoagentB.IftwoormoreagentshaveagoalincommonandhencehavethesameMQincommon,theyactasagrouporateamworkingcollaborativelytowardthisgoal.MQtasksareabstractionsoftheprimitiveactionsthatanagentmayperform.Theagentcomparesandselectstasksthatareassociatedwithdifferentorganizationalgoals.EachMQtaskTihasthefollowingcharacteristics:

••••

•

Earlieststarttime(est),esti.TheperformanceofTibeforethistimedoesnotgeneratevalidresults.

Deadline,dli.TheaccomplishmentofTiafterthistimedoesnotgeneratevalidresults.

MQtaskTineedssomeprocesstimetobeaccomplished,denotedasdi.

MQtaskTiproducescertainquantitiesofoneormoreMQs,denotedasMQPS(MQproductionset).TheproductionofMQsreflectstheprogressmadeinac-complishingtheorganizationalgoalassociatedwiththisspecificMQ.

MQtaskTiconsumescertainquantitiesofoneormoretypesofMQs,denotedasMQCS(MQconsumptionset).TheconsumptionofMQsrepresentsresourcescon-sumedbyperformingthistask,orfavorsowedtootheragentsforsubcontractingwork.

UiQ3Q2Q1123MQiFig.2.

MotivationalQuantitiesandUtilitiesTheMQschedulerschedulescurrentpotentialMQtasks,andproducesascheduleofasetofMQtasks,specifyingtheirstarttimes,andfinishtimes.Theschedulertakesthefollowingfactorsintoconsideration:theMQPS,MQCS,durationdi,theearlieststarttimeestiandthedeadlinedliofeachMQtask,andtheagent’scurrentaccumulationofMQs.NoticethatMQisalwaysbeingevaluatedinthecontextofagent’scurrentMQaccumulationstate.Forexample,Figure2showsasingleutilitycurveforasingleMQi.ThefirstoneunitMQibringstheagentQ1unitsofutilityUi.Aftertheagenthascollected2unitsofMQi,theadditionaloneunitofMQibringstheagentadditional(Q3necessarilyequal−toQ2)unitsofutilityUi.(Q3Q−Q2)isnot1,theyarecalculatedbasedontheutilitycurveassociatedwithMQi.

TheMQframeworkprovidesthecomparisonoftasksthatneedtobeperformedfordifferentreasons:fordifferentorganizationalgoals,forotheragentstogainsomefinancialbenefitorfavorsinreturn,forcooperationwithotheragents,etc.Italsosupportsdifferentutilityfunctionsthatrelatetheexecutionoftaskstotheimportanceoforganizationalgoals.TheMQframeworkisrelatedtotheworkonjointintentions[12]andjointgoals[13].Inthiswork,theagentreasonslogicallyabouttheexistenceofjointgoals(basedoninformationexchangedanditslocalknowledgedatabase)andthendecideswhichactivitiestoperformandhowitshouldinteractwiththeotheragentsunderjointgoals.However,thisworkdiffersfromtheMQframeworkinthefollowingway.Thejointgoalworkdoesnotaddresshowtheagentchoosesfrommultiplecandidategoals,orhowtheagentdecideswhichactivitiestoperformatagiventime.Instead,itfocusesonfindingtheexistenceofthejointgoals.Incontrast,theMQworkfocusesondecidingwhichgoals(ortasks)toperform,whentoperformthemandhowtoperformthemfromaquantitativeperspectiveratherthanfromalogicalone.

Insummary,themotivationalqualities(MQ)frameworkprovidesanagentwiththecapabilitytoreasonaboutdifferentgoalsinanopen,dynamicandlarge-scaleMAS,hencetheagentcanevaluateanegotiationissuefromanorganizationalperspective.

III.INTEGRATIVENEGOTIATION

Inacomplexagentsociety,anagentwillneedtoworkwithotheragentsfromavarietyofdifferentorganizationalpositions.Forexample,anagentfromitsowngroup,anagent

4

Degree of Concerncompletelycompletelyfor Own Outcomesself−directedexternallydirectedmixingdirectedAvoidantAccommodativeDegree of Concern for Other’s OutcomesFig.3.

Thedualconcernmodel

whohasahigherpositionandthusmoreauthority,anagentfromacooperativecompany,oranagentfromacompetingcompanyandsoforth.Theagent’sattitudetowardnegotiationisnotjustsimplyeitherself-directedorexternally-directed,theagentneedstoqualitativelyreasonabouteachnegotiationsession,andsoitcanchooseanappropriatenegotiationattitude.

Figure3describesthisdualconcernmodel.Whentheagentonlyattachesimportancetoitsownoutcome,itsattitudetowardnegotiationiscompletelyself-directed;whenanagentattachesthesamedegreeofimportancetoitsownoutcomeasitdoestotheoutcomesoftheotheragent,itsattitudeiscompletelyexternally-directed;whentheagentattachesmoreimportancetotheoutcomesofotheragentsandnoimportancetoitsownoutcome,itsattitudeisaccommodative;iftheagentattachesnoimportancetoanyoutcomes,itsattitudeisavoidant(thenegotiationisnotworthitstimeandeffort).Fromthismodel,wefindthattherearepotentiallymanyoptionsbetweenthetwoextremesofcompletelyself-directedandcompletelyexternally-directed.Theseotheroptionsdependontheimportancetheagentattachestotheincreaseofitsownutilityrelativetotheimportanceitattachestotheincreaseoftheotheragents’utility.

Let’susetaskallocationasanexampleofnegotiationwhereforeachtasktthatagentAwantsagentBtocomplete,certainMQsaretransferredfromagentAtoagentBifagentBagreestocompletethetask.TheconceptualmodelhereisthatagentBismotivatedbythepotentialincreaseinitsMQstoperformtasksforagentA(notethatthisdoesnotconverttheMQstocurrencyasnotallagentsmaybeinterestedinsaidMQs).Wewillstartwithasimple,abstractexample.Inthismodel,whenagentBcommitstoaccomplishingtaskt,basedonacontractthatismutuallyagreeduponbythetwoagents(formedeitherdynamicallyorpre-defined),itisthenobligatedtoperformthetask,otherwiseitmayincurapenalty.WhenBsuccessfullyaccomplishest,theagreeduponamountoftheMQwillbetransferredfromagentAtoagentB.NotethatagentBmustactuallydecidewhetherornotitisinterestedinperformingt.ThisevaluationisdoneviatheMQframeworkandtheassociatedMQscheduler.TheevaluationusesagentB’spreferencefortheMQinquestiontodeterminetherelativevalueofperformingtforagentAcomparedtoothercandidatetasksagentBmayhave.Thisevaluationprocess,inturn,determinesagentB’sattitudetowardthenegotiationoftask

t.

Intermsofspecifics,therearetwotypesofMQsthatcouldbetransferredwiththesuccessfulaccomplishmentoftaskt:goalrelatedMQandrelationalMQ.Theseclassesareconceptualandusedtoclearlydifferentiatemotivationsfortaskperformancefromattitudestowardnegotiationissues–inreality,theyarebothsimplyMQs.GoalrelatedMQsareassociatedwithanagent’sorganizationalgoals,generallyincreasesinMQvolume,andhencehavepositivebenefitstotheagent’sutility.Notethattheagent’sdesignerdetermineswhichkindsofMQstheagenttracks(andisinterestedin),definestheagent’spreferenceforeachviatheutilityfunctionsdiscussedearlier,anddetermineshowtheserelatetotheagent’sorganizationalgoals.WhendealingwithgoalrelatedMQs,theagentcollectsMQsforitsownutilityincrease.Inthissense,agentB’sperformanceoftasktismotivatedby“self-interested”reasonsifpaymentisviaagoalrelatedMQ.Forexample,taskthas3unitsofMQxtransferredwithit,andforagentB,theutilitycurveofMQxis:u(x)=2x,thatmeans,theutilityofagentBwillincreaseby6unitsbycollecting3unitsofMQxthroughperformingtaskt.AgentBdecideswhethertoaccepttasktbyreasoningaboutitsvaluerelativetothecostoftheresourcesitwillexpendintheperformanceoftandtheopportunitiesitwillforgobytakingthistaskt.Inthiscase,asthetaskdoesn’tconsumeanyMQs,theresourceexpenditureistimeorintermsofopportunitycost.BecausethisreasoningprocesspertainstogoalrelatedMQs,itis“self-directed”fortheagent’sonlyconcernsisitsownutilityincrease.Consideramodifiedcase.SupposethatbyhavingtasktaccomplishedbyagentB,agentA’sownutilityincreasesby20units.IfagentBtakesthisfactintoconsiderationwhenitmakesitsdecisionabouttaskt,agentBisexternally-directedwithagentAbecauseagentBisalsoconcernedaboutagentA’soutcome(inadditiontoitsown).IfwewantagentBtoconsiderA’sutility,weneedtointroduceanotherMQdesignedtomodelB’s(revised)preferenceforAtohaveautilityincreasealso.ToreflecttheB’sattitudetowardA’soutcome,weintroducearelationalMQ,thepreferenceforwhichrepresentshowexternally-directedagentBiswithagentAconcerningtaskt.LetMQba/tbetherelationalMQtransferredfromagentAtoagentBwhenagentBperformstasktforagentA.SinceMQba/tisarelationalMQ,itsonlypurposeistomeasuretheattitudeofagentBtowardsagentAconcerningtaskt.theutilityofagentBtowardproblemsolving,wewillnotconsidertheutilityproducedbyanyrelationalMQssuchasMQba/t.LikewisewithagentA.WhenagentAtransfersMQba/ttoagentB,wewillnottabulatethenegativechangeinutilityofagentAbecausethechangeinutilityisnotrelatedtoproblemsolvingprogressbutisinsteadrelatedtothetransferofarelationalMQ.Thereasonforthisapproachisthatinthispaperourperformancemetricissocialwelfareasitisconventionallyused,whichisintermsofprogresstowardjointgoals.Fromthisview,theutilityproducedbyarelationalMQcanbeseenasvirtualutility.ThoughMQba/tproducesvirtualutility,isimportantbecauseitcarriestheinformationofhowimportanttasktis

5

Ub(MQ )ba/t3b (k>1)a (k=1)2c (0differentmappingfunctionsofMQba/tba/tforagentA1andmakesitpossibleforagenttoconsideragentA’soutcomewhenitmakesitsowndecisions.Actually,howMQba/tismappedintoagentB’s(virtual)utility,meaningutilitythatisnotincludedinthesocialwelfarecomputation2dependsonhowexternally-directedagentBiswithagentA.Supposethat20unitsMQba/taretransferredwithtaskt,representingtheutilityagentAgainedbyhavingagentBperformtaskt,Figure4showsfourdifferentfunctionsformappingMQba/ttoagentB’svirtualutility.

Functiona,bandcarelinearfunctions:Ua(MQba/t)=k∗MQba/t.

Ifk=1(a),Ub(MQba/t)=MQba/t=Ua(t)(Ua(t)denotestheutilityagentAgainedbytransferringt),thenagentBiscompletelyexternally-directedtoagentA;

Ifk>1(b),Ub(MQba/t)>MQba/t=Ua(t),thenagentBisaccommodativetoagentA3;

Ifk<1(c),Ub(MQba/t)Ifk=0,Ub(MQba/t)=0,thenagentBiscompletelyself-directedwithrespecttoagentA.Inthiscase,ifagentAwantsagentBtodotaskt,itneedstotransferanotherkindofMQ(thegoalrelatedMQ)toagentB,agentBandagentAcannegotiateaboutwhattypeofgoalrelatedMQtotransferandhowmuchofitshouldbetransferred,regardinghowandwhenagentBcouldaccomplishtaskt.Inthefollowingexamplesandtheexperimentalwork,weassumethatthetypeandamountofthetransferredgoalrelatedMQsarefixedandagentsdonotnegotiateaboutthem,sowecanfocusondemonstratinghowtherelationalMQworks.

1It

isassumedthatagentsarehonestanddon’tlieabouttheimportanceoftaskt.Werecognizethatthisassumptionmaynotholdinallapplications.Itisworthnoting,however,thatitisactuallydifficulttolieeffectivelyintheMQframeworkbecausetheagentsdonotnecessarilyknoweachother’smappingfunctionforrelationalMQs.ConsiderFigure4.IfagentAisinteractingwithagentBandagentAdoesnotknowwhichmappingfunction(a,b,c,d)thatagentBisusing,itwillbedifficultforagentAtoknowtheimpactthatitslocalchoiceswillhaveonagentB’sresponse.

2Inremainderofthepaper,wemayomittheword“virtual”beforeutility,butweknowthatthisrelationalMQ.onlymapsintovirtualutilitythatisnotrealutility.Intheexperimentalwork,neithertheagent’sutilitynorthesocialwelfareincludesthevirtualutilityfromrelationalMQ.

3Thisfunctioncanbeusedtorepresentauthorityrelationshipbetweenagents.Whenkissettoaverylargenumber,agentAactuallyhasauthorityoveragentB-thetaskfromagentAhashighpriorityinagentB’sagenda.AnotherwaytoexpresstheauthorityrelationshipinMQframeworkistousethegoalrelatedMQ.AsimilarpreferenceutilityfunctionlikethisoneassociatedwithagoalrelatedMQcanrepresenttheauthority.However,thedifferenceisthatthereisno“real”utilitytransferredbetweenagentsinthefirstapproach.

Themappingfunctioncouldalsobeanonlinearfunction(d)thatdescribesamorecomplicatedattitudeofagentBtoagentA,i.e.,agentBbeingcompletelyexternally-directedwithagentAuntilcertainorganizationalgoalismetindicatedbythelevelofMQ,andthenbecomingself-directed.Anagentcanadjusttheutilitymappingfunctiontoreflectitsrelationshipwithanotheragent,whichcouldbeitsadministra-tor,colleague,friend,clientorcompetitor.Byadjustingsomeparametersinthemappingfunction,moresubtlerelationshipscouldbemanaged.Theagentcoulddifferentiateafriendlycolleaguefromanunfriendlycolleague,alsoitcoulddrawdistinctionsbetweenabestfriendandanordinaryfriend.Thestructureofthefunctionreflectsthatforhowlongandtowhatextenttheagentwouldliketobeexternally-directed.

DifferentfromthegoalrelatedMQs,whicharebuiltbytheagent’sdesignerandwhoseutilitycurvesarenotchanging,theutilitycurvesoftherelationalMQscanbeadjustedbytheagentdynamicallytoreflectitsdynamicrelationshipswithotheragents.Additionally,theagent’sattitudetowardsanotheragentcouldbe“issue-specific”;givenanagentcouldplaymultipleroles,therecouldbedifferentissuesnegotiatedbetweenagents,andtheagentsshouldselectdifferentattitudeaccordingtowhatissueisnegotiated.Forexample,forthecolleague’srequesttocontributetoasharedprofessionaljobandforthesamecolleague’srequestforaride,eventhoughbothrequestscomefromthesameagent,theagent’sattitudecouldbedifferent.

Byintroducingthisagent-oriented,issue-specificrelationalMQintonegotiation,theagent’sattitudetowardanotheragentconcerningaspecificissuecanberepresentedastheutilitycurveassociatedwiththerelationalMQ.Thismechanismiscalledanintegrativenegotiationmechanism,whichsupportstheagent’schoosinganegotiationattitudeofanytypefromcompletelyself-directedtocompletelyexternally-directed.Theagent’sattitudetowardsanegotiationissueisaffectedbytheutilitymappingfunctionofthetransferredMQwiththisissue.IntheMQframework,theMQschedulerenablestheagenttooptimizeitsscheduleandmaximizeitslocalutility.WhiletheframeworkdirectlysupportstheconceptofrelationalMQsandbeingmotivatedtocooperateonthatbasis,theuseofMQtransferenceinthispaperextendstheMQframeworktointerconnectthelocalschedulingproblemsoftwoormoreagentsinadynamicfashion(basedonthecurrentcontext).Priortothiswork,nomeaningfulworkhadbeendoneinMQtransferenceortheimplicationsofit.

Howcananagentchooseitsattitudetowardotheragentsinsuchacomplexorganizationcontext?Wearenotplanningtopresentasolutiontothisquestioninthispaper,butwefeelthattheagentshoulddynamicallyadjustitsattitudebyanalyzingtheotherparty,theissueinnegotiationanditscurrentproblem-solvingstatus.InSectionIV,weshowthatforasimplescenariotheoptimalattitudecanbeformallyspecifiedandforthatscenariowecanlearnthroughlocalobservationwhatarethebestattitude.Thefollowinginformationshouldbeconsideredinthisdecisionmakingprocess:“Whoistheotheragent?”“Howisitsorganizationalgoalsrelatedtomine?”“Whatisitsobjective?”“Whatisitsrelationshiptome?”andsoforth.Someofthisinformationcanbelearnedfrom

6

experience[14].In[15],wepresentedaformalizedanalyticalmodelandshowedthatthebestnegotiationattitudecanbedriventhroughthecalculationbasedonthismodelandtheavailableinformationoftheenvironmentalcontext.

IV.THESCENARIO

Inthissection,weintroduceasimpleexampleofanagentsocietyandshowhowtheintegrativenegotiationmechanismworksusingtheMQframework.TherearethreeagentsinthissocietyasshowninFigure5.

1)TheComputer-ProducerAgent(c):receivesPur-chaseComputertasksfromanoutsideagent(whichisnotconsideredinthisexample).Figure5showsthattoaccomplishaPurchaseComputertask,theComputer-ProducerAgentneedstogenerateanexternalrequestforhardware(GetHardwaretask),andalsoneedstoshipthecomputer(DeliverComputer)throughatransportagent.2)TheHardware-ProducerAgent(h):receivesGetHardwaretasksfromtheComputer-ProducerAgent,italsoreceivesPurchasePartstasksfromanoutsideagent.

3)TheTransportAgent(t):receivesDeliverComputertasksfromtheComputer-ProducerAgent,italsore-ceivesDeliverProducttasksfromanoutsideagent.Inthisexample,everyagentcollectsthesametypeofgoalrelatedMQ:MQ$.TheutilitycurveforMQ$is:utility(x)=xandeveryagentusesthissamefunction.Eachtaskthattheagentreceivesincludesfollowinginformation:•Itsbeforeearliestthisstarttimetimedoesnot(est),generatetheperformancevalidresults.ofthetask•Itsdeadline(dl):theagentrewardwill(r):getifrewardthetasklatestr(whichisfinishfinishedtimeisrunitsbyforthethetask.

•Itsofdeadline,MQthe$).

•Thethetaskearlybyfinishtimerewardftasrateitpromised(e):iftheinagentthecontract,canfinishitwillreceiveanadditionalearlyfinishreward.Therewardsumisadjustablesothatiftheagentfinishesevensooner,additionalrewardsaregiven.Therelationshipisexpressedmathematicallyas:max(e*r*(dl-ft),r).Themaximumadditionalrewardisrsothatthetotalrewardpossiblefortaskperformance,includingbothbasicre-wardandadditionalreward,is2*r.

AsFigure6shows,theHardware-ProducerAgentreceivesPurchasePartstaskfromanoutsideagentwithxunitsofMQ$,wherexisarandomnumbervaryingfrom2to10.TheComputer-ProducerAgenthaslong-termcontractrelationshipwiththeHardware-ProducerAgentandtheTransportAgent:itsGetHardwaretaskalwaysgoestotheHardware-ProducerAgentwithafixedrewardof3unitsofMQ$,anditsDe-liverComputertaskalwaysgoestotheTransportAgentwithafixedrewardof3unitsofMQ$.EveryPurchaseComputertaskcomestotheComputer-ProducerAgentwitharewardof20unitsofMQ$ifitisfinishedbyitsdeadline(therewardcanbehigherifthetaskisfinishedearlier,seethefollowingexample).TheComputer-ProducerAgentwouldhaveitslocalutilityincreasedby14unitsafterpayingtherewardtothe

7

Consumer AgentConsumer AgentConsumer AgentPurchase_ComputerPurchase_PartsminDeliver_ProductDeliver_ComputerGet_HardwareProduce_ComputerminenablesDeliver_ComputerGet_SoftwareenablesInstall_SoftwareGet_HardwareFig.5.

AgentSociety

enablesHardware−Producer AgentComputer−Producer AgentDeliver_ProductMQ$: [2, 10]Transport AgentPurchase_ComputerMQ$: 20Deliver_ComputerMQ$:3, MQtc/t:7Transport AgentComputer Producer Agentutility increase: 14Purchase_PartsMQ$: [2, 10]Hardware Producer AgentFig.6.TaskswithDifferentMQsGet_HardwareMQ$:3, MQhc/t:7Hardware-ProducerAgentandtheTransportAgent).AssumethetasksGetHardwareandDeliverComputerhavethesameimportance,theaccomplishmentofeachtaskwouldresultin7unitsutilityincreasefortheComputer-ProducerAgent.Thisinformationisreflectbythe7unitsofMQhc/ttransferredwithtaskGetHardwareand7unitsofMQtc/ttransferredwithtaskDeliverComputer.MQhc/t4isarelationalMQintroducedtoreflecttherelationshipoftheHardware-ProducerAgentwiththeComputer-ProducerAgentconcerningtaskt.ThetransferredMQhc/twiththetaskrepresentstheutilityincreaseoftheComputer-ProducerAgentbyhavingthistaskaccomplished.HowitismappedintotheHardware-ProducerAgent’svirtualutilitydependsontheHardware-ProducerAgent’sattitudetowardstheutilityincreaseoftheComputer-ProducerAgentregardingtaskGetHardware.IfthePurchaseComputertaskcouldbefinishedearlierthanitsdeadline,theComputer-ProducerAgentcouldgetmorethan20unitsreward.Theextrautilityincreasecouldbeestimatedandreflectedbymorethan7unitstransferredMQhc/torMQtc/ttotheothertwoagents.SupposetheComputer-ProducerAgentreceivesthefollowingtask:•Taskname:PurchaseComputerA•Earliest-start-time:10•Deadline:70

•Reward:20unitsMQ$

•Earlyfinishrewardrate:e=0.01

ThroughthereasoningoftheMQscheduler,theComputer-ProducerAgentdecidestoacceptitandfinishitbytime

MQtc/tisarelationalMQthatreflectstherelationshipof

theTransportAgentwiththeComputer-ProducerAgentconcerningtaskt.Detaileddiscussionaboutitisomittedhere.

4Similarly,

40(itleaves4unitsslacktime)toearnextraearlyreward6((70−40)∗0.01∗20)unitsMQ$.Itslocalutilityincreasesby20(20+6-6,afterpayingthesub-contractoragents)unitsaftertheaccomplishmentofthistask.Hencethefollowingtwotaskrequests:GetHardwareAandDeliverComputerAaresenttotheHardware-ProducerAgentandtheTransportAgentrespectively:

tasknameestdeadlinerewardGetHardwareA10203unitsMQ$10unitsMQhc/t

DeliverComputerA30403unitsMQ$10unitsMQtc/t

Inthisexample,welookatthreedifferentattitudes,forhowtheHardware-ProducerAgentnegotiateswiththeComputer-ProducerAgentoverthetaskGetHardware.Thediffer-entattitudesarespecifiedintermsofalinearfunction:Uha(MQhc/t)=k∗MQhc/t.

1)k=1,theHardware-ProducerAgentiscompletelyexternally-directed.

2)k=0.5,theHardware-ProducerAgentispartiallyexternally-directed.

3)k=0,theHardware-ProducerAgentiscompletelyself-directed.NowwecanlookathowthesedifferentattitudesaffectthenegotiationprocessoftheHardware-ProducerAgent.SupposetherearetwoothertasksPurchasePartsAandPurchasePartsBreceivedbytheHardware-ProducerAgentbesidestaskGetHardwareA,thisresultsinthethreetasksbeingsenttotheMQScheduler(supposetheinitialMQset

isempty):

tasknameestdeadlineprocessMQPStimeGetHardwareA102010[MQ$,3][MQhc/t,10]PurchasePartsA103010[MQ$,4]PurchasePartsB102010[MQ$,9]Thedecisionsmadebytheagentdependontheattitudetaken:

•IfdirectedtheHardware-ProducertotheComputer-ProducerAgentiscompletelyAgent(kexternally-=1),thebestMQscheduleproducedis:

[10,20]GetHardwareA[20,30]PurchasePartsAtheHardware-ProducerAgentwillhave7unitsutilityincreaseaftertheaccomplishmentofthisschedule.

•IfdirectedtheHardware-ProducertotheComputer-ProducerAgentisAgentcompletely(k=0),self-thebestMQscheduleproducedis:

[10,20]PurchasePartsB[20,30]PurchasePartsAtheHardware-ProducerAgentwillhave13unitsutilityincreaseaftertheaccomplishmentofthisschedule.

•IfdirectedtheHardware-ProducertotheComputer-ProducerAgentispartiallyAgent(kexternally-=0.5),thebestMQscheduleproducedisthesameasabove.However,ifthetaskPurchasePartsBcomeswith6unitsMQ$insteadof9units,thenthebestMQscheduleproducedis:

[10,20]GetHardwareA[20,30]PurchasePartsAtheHardware-ProducerAgentwillhave7unitsutilityincreaseaftertheaccomplishmentofthisschedule.AsimilarreasoningprocessalsoappliestotheTransportAgent.

Theaboveexampleshowshowanagentreactsinanegoti-ationprocessdependsonitsattitudetowardstheotheragentregardingthisissue,andalsoisaffectedbytheothertasksonitsagenda.Themoreexternally-directedanagentis,themoreitwillsacrificeitsownutilityfortheotheragent’sutil-ityincrease.Thisintegrativenegotiationmechanismenablestheagenttomanageandreasonaboutdifferentnegotiationattitudesitcouldhavewithanotheragentregardingacertainissue.

V.EXPERIMENTALRESULTS

TheexampleinSectionIVshowsthatanagentneedstosacrificesomeofitsownutilitygaintobeexternally-directedwithanotheragent.Oneimportantquestionis:canexternally-directedagentsimprovesocialwelfare?5Anotherimportantquestionis:whenshouldanagentbeexternally-directedandhowexternally-directeditshouldbe?Toexplorethesequestions,thefollowingexperimentalwork6wasdone

5Social

welfarereferstothesumoftheutilitiesofalltheagentinthe

society,i.e.thesumoftheutilitiesofthethreeagents:theComputer-ProducerAgent,theHardware-ProducerAgent,andtheTransportAgent.Socialwelfareiscollectedintheexperimentsjustforustocomparedifferentpolicies.Itisneverbeingusedbyindividualagentsintheirlocaldecisionmakingprocesses,becausethisinformationisnotavailableforthematall.Forindividualagent,theonlyavailableinformationbesidesitslocalinformationistherelationalMQfromtheotheragentwithwhomitisnegotiating.

6TheexperimentsareperformedintheMASSsimulatorenvironment[16],andtheagentswerebuiltusingtheJAFagentframework[17]

8

basedonthescenariodescribedinSectionIV.TheHardware-ProducerAgenthasachoiceofthreedifferentattitudestowardtheComputer-ProducerAgent:completelyexternally-directed(C)(k=1.0),partiallyexternally-directed(H)(k=0.5),andcompletelyself-directed(S)(k=0),theTransportAgenthasthesamethreechoices,sothereare9combinations:SS(bothagentsarecompletelyself-directed),SC(theHardware-ProducerAgentiscompletelyself-directedwhiletheTransportAgentiscompletelyexternally-directed),SH(theHardware-ProducerAgentiscompletelyself-directedwhiletheTransportAgentispartiallyexternally-directed),HS,HC,HH,CS,CH,CC.Thedataisgeneratedbyrunning48groupsofexperiments;ineachgrouptheagentsworkonthesameincomingtasksetundertheninedifferentsituations.Thetasksineachsetforeachgroupexperimentarerandomlygeneratedwithdifferentrewardsanddeadlineswithincertainranges.TableIshowsthecomparisonofeachagent’sutilityandthesocialwelfareunderthesedifferentsituations.Thepercentagenumbersarethenormalizedutilitynumbersbasedontheutilitygainedwhenagentiscompletelyself-directed.WhenboththeHardware-ProducerAgentandtheTransportAgentarecompletelyexternally-directedwithrespecttotheComputer-ProducerAgent(CC),thesocietygainsthemostsocialwel-fare.Evenwhenbothagentsareonlypartiallyexternally-directed(HH),thesocialwelfareisstillverygood.However,whenoneagentiscompletelyexternally-directedandtheotheragentiscompletelyself-directed(CS,SC),thesocialwelfaredoesnotimprovemuchcomparedtothecompletelyself-directed(SS)case7.Thereasonforthislackofsignificantimprovementisthat,inthisexample,toaccomplishtaskPurchaseComputerrequiresthatboththetaskGetHardwareandthetaskDeliverComputerneedsaresuccessfullycom-pleted.Whenoneagentiscompletelyexternally-directed,itsacrificesitownutility,buttaskPurchaseComputermaystillfailbecausetheotheragentdoesnotcooperateonthesubtask,thustheutilityoftheComputer-ProducerAgentdoesnotincreaseasexpected,andtheglobalutilitydoesnotimprove.Thishappenswhenthecompletionofataskisspreadovermorethantwoagents–thustheinformationfromtheComputer-ProducerAgentaboutitsutilityincreaseisonlyanestimationbecauseitdependsnotonlyontaskGetHardwarefortheHardware-ProducerAgent,butalsoreliesontaskDeliverComputerfortheTransportAgent.Inthissituation,iftheHardware-ProducerAgenthasnoknowledgeabouttheattitudeoftheTransportAgent(andwhatothertasksitwillbereceivingincludingtheirworthandfrequency),thenitmaynotbeagoodideatobecompletelyexternally-directedtowardstheComputer-ProducerAgent.

TableIIshowstheresultsofstatisticalsignificance(t-test)testingaboutthesocialwelfareunderthedifferentcooperativesituations.Forexample,thefirstlineinTableIIshowsthatwiththe0.01Alpha-level,wecanrejectthehypothesisHothatthedifferencebetweenthesocialwelfarewhenbothagentsarecompletelyexternally-directedandthesocialwelfarewhen

7Results

fromt-testhaveshownthatthedifferenceofthesocialwelfare

betweenCCandSS,alsobetweenHHandSS,arestatisticallysignificant.

9

SSCCHHSCCSHSSHHCCHUtilityofComputerProducerAgent

218842587301469390292632761Percentage1.0004.082.841.412.241.871.363.063.68UtilityofHardwareProducerAgent

571935873467585500405Percentage1.0000.720.861.020.630.811.020.870.70UtilityofTransportAgent

856766806798839845815772802Percentage1.0000.900.940.930.980.990.950.900.94SocialWelfare1920221886168616721702169219051967Percentage1.0001.231.141.021.011.031.031.161.19TABLEI

COMPARISONOFPERFORMANCE

DifferenceofSocialWelfareCC-SSHH-SSSC-SSCS-SSNumbertoCompare33018000Ho=330=180=0=0Ha>330>180>0>0ResultRejectHoRejectHoFailtorejectHoFailtorejectHoAlpha0.010.010.010.01p0.0080.00080.01790.0965TABLEII

RESULTSFROMSTATISTICALTESTS

CompletelySelf-DirectedCompletelyExternally-DirectedPartiallyExternally-DirectedUtilityofHardwareProducerAgent

5833987Percentage1.00.680.83SocialWelfare167918871831Percentage11.131.09TABLEIII

UTILITYOFHARDWARE-PRODUCERAGENTANDSOCIALWELFARE

bothagentsarecompletelyself-directedisequalto3308,comparedtothehypothesisHathatthedifferencebetweenthesocialwelfarewhenbothagentsarecompletelyexternally-directedandthesocialwelfarewhenbothagentsarecom-pletelyself-directedisgreaterthan330.

TableIIIshowstheexpectedutilitiesoftheHardware-ProducerAgentandtheexpectedsocialwelfareunderthethreepossiblesituations:whentheHardware-ProducerAgentiscompletelyself-directed,completelyexternally-directedandpartiallyexternally-directed.WhentheHardware-ProducerAgentchoosesoneattitude,theTransportAgentmayadoptoneofthethreedifferentattitudes.Forexample,whentheHardware-ProducerAgentchoosestobecompletelyself-directed,theglobalsituationcouldbeSS,SC,orSH.Theutilitynumbersinthetablearetheexpectedvaluesoftheutilitiesunderthesethreedifferentsituations.TableIIItellsusthatwhenacooperativetaskinvolvesmorethantwoagentsandwhentheotheragents’attitudesareunknown,beingcompletelyexternally-directedmeanssacrificingitsownutilitysignificantlyandthus,atleastinthisscenario,isnotagoodidea.

Werecognizedthattheaboveconclusionmightrelatetotheparametersoftheexperiments.TableIVshowstheseparameters.Forexample,thethirdrowofthetableshowsthattheHardware-ProducerAgentreceivestwoPurchasePartstaskevery15timeclicks,therewardforeachPurchasePartsis20%ofsocialwelfareundertheSSsituation(19),and180is

11%ofsocialwelfareundertheSSsituation.

8330

AgentchhttTaskPurchaseComputerGetHardwarePurchasePartsDeliverComputerDeliverProductReward203[2,10]3[2,10]Frequencyevery15timeclicks

11212d167667TABLEIV

EXPERIMENTPARAMETERS

fallsintherangeof[2,10],andthedurationofthetaskis6.EveryPurchaseComputertaskcomestotheComputer-ProducerAgentwitharewardof20unitsofMQ$,ifitisfinishedbyitsdeadline,theComputer-ProducerAgentwouldhaveitslocalutilityincreasedby14units(Withthedeductionofthe6unitsofMQ$transferredtotheHardware-ProducerAgentandtheTransportAgent).ThisinformationissenttotheHardware-ProducerAgent(andalsotheTransportAgent)byattaching7(14dividedby2agents)unitsofrelationalMQ(MQhc/tfortheHardware-ProducerAgent)withthetask-announcingproposal.ThisinformationistakenintoconsiderationbytheMQschedulerwhentheHardware-ProducerAgentmakesitsdecisiononthisproposal.However,thisinformationisnotnecessarilyaccuratebecauseitisbasedontheassumptionthatthetaskProduceComputerwillbefinishedontime.Whetherthisassumptionisappropriate

dependsonwhethertheHardware-ProducerAgentandtheTransportAgentwouldacceptthesubcontractsandfulfillthemontime.Theuncertaintyassociatedwiththisinformationcomesfromtheuncertaintyoftheothercontractoragent’s(theTransportAgent)decision,wheretheothercontractoragent’sdecisionisbasedonthefollowingissues:

1)Theagent’sattitudetowardtheComputer-ProducerAgent(howexternally-directeditis);themoreexternally-directeditis,themorelikelythissubcontractwillbeaccepted.

2)Theoutsideofferstheagentreceives:howgoodtheyare,howfrequenttheyareandhowtheyaffectthesubcon-tracttask.Iftheoutsideofferisnothighercomparedtotherewardfromthesubcontract,oriftheyarenotveryfrequent,oriftheydonotconflictwiththesubcontracttask,thesubcontractwillbemorelikelytobeaccepted.BecausetheseissuesareunknownbytheComputer-ProducerAgentandtheHardware-ProducerAgent,theuncer-taintyassociatedwiththeinformationaboutthelocalutilityincreasecannotberesolved.Thisiswhywemakethestate-mentatthebeginningofthispaper:itisnotpossiblefromacomputationalorcommunicationalperspectiveforanagenttobefullycooperative,becausetheagentneedstohavecompleteglobalinformationtobefullycooperative.Thus,itmaybebestfortheorganizationtohaveagentsbeingpartiallyexternally-directedintheirlocalnegotiationwithotheragentsratherthanbeingcompletelyexternally-directedinordertodealmoreeffectivelywiththeuncertaintyofnothavingamoreinformedviewofthestateoftheentireagentorganization9.Generally,anagentshouldputappropriateweightonexternalinformationprovidedbyotheragentsinanuncertainenvironmentinordertodealwithdistraction.Whenthereismoreuncertaintyrelatedtotheexternalinformation,anagentshouldbemoreself-directed,anditshouldbemoreexternally-directediftheexternalinformationismorecertain.

Additionalexperimentshavebeendoneusingdifferentparameters.TableVshowsthesocialwelfareunderdifferentconditions.Whentherewardsofoutsideoffersfallintotherangeof[11,19],forthebestsocialwelfare,bothagentsshouldbecompletelyself-directed.

However,ifthereisnouncertaintyorlessuncertainty,itmaybethebestfortheagenttobecompletelyexternally-directedormoreexternally-directedtowardthegrouptaskinordertoincreasethesocialwelfare.Thisdoesnotmeantheagenthastogranteverysubcontractofthegrouptask,thedecisionalsodependsontheoutsideoffer.Iftheoutsideofferissignificantlybetterthanthesubcontractevenwithtakingintoconsiderationofthecontracteeagent’sutilityincrease,andifthecontractoragentcanonlychooseonebetweenthesubcontractofthegrouptaskandtheoutsideroffer,thecontractoragentwilltaketheoutsideofferanddropthesubcontractevenifit

9This

issueofdistractioninadistributedinterpretationsystem[18],[19]

iscausedbyanonymousevaluationofthevalidityoflocallygeneratedhypothesis.Theproblemcausedbysubsequentintegrationintothereasoningofanotheragentisverysimilartotheissuesdescribedintheexperiments.Thesolutiontothisprobleminadistributedinterpretationsystemistomodifylocalreasoningprocesstoonlypartiallyexploretheinformationreceivedfromanotheragent.Thisapproachissimilarincharactertotheideasuggestedinthispaper.

10

RewardfromSSCCHHoutsideoffer[2,10]1.01.231.14[11,19]1.00.930.98TABLEV

SOCIALWELFAREUSINGDIFFERENTPARAMETERS

iscompletelyexternally-directed.Andinfact,thischoiceincreasesthesocialwelfare.

Basedontheaboveexperimentalresults,wefeelthereareatleasttwodifferentwaysforagentstochoosetheappropriatelevelofcooperation.Oneapproachisthattheagentwhohasmoreglobalview/knowledgecaninformotheragentsabouthowlikelytheestimatedutilityincreasewillbetrue,andtheotheragentscanadjusttheircooperationlevelsbasedonthereliabilityofthisinformation.Anotherapproachisthattheindividualagentcanlearnfromthepastexperiencetoadjustthelevelofcooperation.

VI.RELATEDWORK

GlassandGrosz[20]developedameasureofsocialcon-sciousnesscalled“browniepoints”(BP).TheagentearnsBPeachtimeitchoosesnottodefaultagrouptaskandlosesBPwhenitdoesdefaultforabetteroutsideoffer.Thedefaultofagrouptaskmaycausetheagenttoreceivegrouptaskswithlessvalueinthefuture,hencereducingitslongtermutility.TheagentcountsBPaspartofitoverallutilitybesidethemonetaryutility.AparameterBPweightcanbeadjustedtocreateagentswithvaryinglevelsofsocialconsciousness.ThisrelatestoourutilitymappingfunctionassociatedwiththerelationalMQwhichcanbeadjustedtoreflecttheagent’sdifferentattitudeinnegotiation.However,therelationalMQisagent-orientedandissuespecific,sotheagentcanmodeldifferentattitudestowardseachagentandnegotiationissue.Additionally,themappingfunctioncanbeanonlinearfunctionanddescribeamorecomplicatedattitude.Theirworkassumesthereisacentralmechanismcontrollingtheassignmentofgrouptasksaccordingtoagent’srank(agent’spreviousdefaultbehavior),whichisnotalwaysappropriatedforanopenagentenvironment.Instead,inourassumption,agentsareallindependentandthereisnocentralcontrolinthesociety.Axelrod[21]hasshownstablecooperativebehaviorcanarisewhenself-interestedagentsadoptareciprocatingattitudetowardeachother.Theagentcooperateswithanotheragentwhohascooperatedwithitinpreviousinteractions.TheideaofthereciprocityisrelatedtoourworkiftherelationalMQisusedbi-directionallybetweenagents,agentAcollectsomerelationalMQfromagentBandinthefuturetheaccumulatedrelationalMQcouldbeusedtoaskagentBdosomeworkforit,inthisway,therelationalMQactuallyworksasaquantitativemeasureofreciprocity.Sendevelopedaprobabilisticreciprocitymechanism[14]inwhichtheagentKchoosestohelpagentJwithcertainprobabilitypandpiscalculatedbasedontheextracostofthiscooperationbehaviorandhowmucheffortitowesagentJbecauseagentJhashelpeditbefore.Therearetwoparametersintheformula

forcalculatingpwhichcanbeadjustedsothattheagentcanchooseaspecificcooperationlevel.However,thisworkassumesthatcooperationalwaysleadstoaggregategainsforthegroup,anditwasbasedonaknowncostfunction-thatis,theyknowhowmuchextraitwillcostthemtodoXforanotheragent.Neitherofthesetwoassumptionsarenecessaryinourwork.Alsoourworkdealswithmorecomplexandrealisticdomainswheretaskshavereal-timeconstraintsandtherearepotentiallycomplexinterrelationshipsamongtasksdistributedacrossdifferentagents.

Ourexperimentalworkhasshownthateveninacooperativesystemitmaynotbethebestforthesocialwelfaretohaveagentsbecompletelyexternally-directed.Similarresultisalsoshownin[22],whichusesadistributedconstraintsatisfactionmodelthatismuchdifferentfromtheunderlyingmodelinthiswork.Vidal[23]hasalsostudiedtheteamingandselflessnesswhenusingmulti-agentsearchtosolvetask-orientedproblems.Hisstudyalsoshowsthefactthatneitherabsoluteselfishnessnorabsoluteselflessnessresultinbetterallocations,andthefactthattheformationofsmallteamsusuallyleadstobetterallocations.Thisworkexploresasimilarissueasinourwork,however,itisinarelativelysimplifieddomainandthereisnocomplexinteractionamongagents.Otherrelatedworkincludesthecooperativenegotiationworkontaskallocation[24],wheretheagentsusethemarginalutilitygainandmarginalutilitycosttoevaluateifitworthtoacceptataskcontractinordertoincreasetheglobalutility.Howeverinthiswork,theagentactsasina“completely-cooperative”modeandthereisnochoiceonhowcooperativeitwantstobe.Thispaperisanextendedversionof[25].Comparedwiththeconferencepaper,thisextendedpaperhasthefollowingimprovements.Inthispaper,weintroducetwonewconcepts“self-directed”and“externally-directed”,whicharedifferentfrom“self-interested”and“cooperative”.ThispaperprovidesamorecompletedescriptionoftheMQframework.Thispaperalsoincludesmoreexperimentalresult.Weperformedadditionalexperimentsusingdifferentparameters,theresultsshowthatthebestpolicydependsontheenvironmentalcontextsuchastheoutsideoffer,soitisimportanttohaveagentstodynamicallychoosethelevelofcooperation.

VII.CONCLUSIONANDFUTUREWORK

Weintroduceanintegrativenegotiationmechanismthatenablesagentstointeractoveraspectrumofnegotiationatti-tudesfromcompletelyself-directedtocompletelyexternally-directedinauniformreasoningframework,namelytheMQframework.Theagentcannotonlychoosetobeself-directedorexternally-directed,butalsocanchoosehowexternally-directeditwantstobe.Thisprovidestheagentwiththecapabilitytodynamicallyadjustitsnegotiationattitudeinacomplexagentsociety.Introducingthismechanismintheagentframeworkalsostrengthensthecapabilityofmulti-agentsystemstomodelhumansocieties.Multi-agentsystemsareimportanttoolsfordevelopingandanalyzingmodelsandtheoriesofinteractivityinhumansocieties.Therearemanycomplicatedorganizationalrelationshipsinhumansociety,andeverypersonplaysanumberofdifferentrolesand

11

isinvolvedindifferentorganizations.Amulti-agentsystemwiththisintegrativenegotiationmechanismisanidealtest-bedtomodelhumansocietyandtostudynegotiationandorganizationtheories.Experimentalworkshowsitmaynotbeagoodideatoalwaysbecompletelyexternally-directedinasituationinvolvinganunknownagent’sassistance;inthatcase,choosingtobepartiallyexternally-directedmaybeappropriateforboththeindividualagentandalsoforthesociety.

Werecognizethattheexperimentalresultsarescenariospecificandtheydonotanswerthequestionabouthowexternally-directedanagentshouldbeinagivensituation.In[15],wepresentedananalyticalmodeloftheenvironmentthatenablestheagenttopredicttheinfluenceofitsnegotiationattitudeonitsownperformanceandalsoonthesocialwelfare,hencetoselecttheappropriatelevelofcooperationtobalanceitsownutilityachievementandthesocialwelfare.Weplantodeveloplearningtechniquesthatenableanagenttolearnfromitspreviousinteractionswithotheragentsabouthowtoadjustitsnegotiationattitudeparameter.

REFERENCES

[1]T.SandholmandV.Lesser,“Advantagesofaleveledcommitmentcon-tractingprotocol,”inProceedingsoftheThirteenthNationalConferenceonArtificialIntelligence,1996,pp.126–133.

[2]——,“Issuesinautomatednegotiationandelectroniccommerce:Ex-tendingthecontractnetframework,”inProceedingsoftheFirstIn-ternationalConferenceonMulti-AgentSystems(ICMAS95),1995,pp.328–335.

[3]M.AnderssonandT.Sandholm,“LeveledCommitmentContracting

amongMyopicIndividuallyRationalAgents,”inProceedingsoftheThirdInternationalConferenceonMulti-AgentSystems(ICMAS98),Paris,France,1998,pp.26–33.

[4]——,“LeveledCommitmentContractswithMyopicandStrategic

Agents,”inProceedingsoftheFifteenthNationalConferenceonAr-tificialIntelligence,Madison,WI,July1998,pp.38–45.

[5]——,“Time-QualityTradeoffsinReallocativeNegotiationwithCom-binatorialContractTypes,”inProceedingsoftheSixteenthNationalConferenceonArtificialIntelligence,Orlando,FL,1999,pp.3–10.[6]T.SandholmandN.Vulkan,“Bargainingwithdeadlines,”inNational

ConferenceonArtificialIntelligence(AAAI),1999.

[7]S.E.Conry,K.Kuwabara,V.R.Lesser,andR.A.Meyer,“Multistage

negotiationfordistributedconstraintsatisfaction,”IEEETransactionsonSystems,Man,andCybernetics,vol.21,no.6,Nov.1992.

[8]S.LanderandV.Lesser,“Understandingtheroleofnegotiationin

distributedsearchamongheterogeneousagents,”inProceedingsoftheThirteenthInternationalJointConferenceonArtificialIntelligence,1993,pp.438–444.

[9]S.SenandE.H.Durfee,“Aformalstudyofdistributedmeeting

scheduling,”GroupDecisionandNegotiation,vol.7,pp.265–2,1998.[10]A.P.R.EugenioOliveira,BookonEuropeanperspectivesonAMEC.

Springer-Verlag,June2000,ch.AgentsadvancedfeaturesfornegotiationinElectronicCommerceandVirtualOrganisationsformationprocess.[11]T.WagnerandV.Lesser,“Evolvingreal-timelocalagentcontrolfor

large-scalemas,”inIntelligentAgentsVIII(ProceedingsofATAL-01),ser.LectureNotesinArtificialIntelligence,J.MeyerandM.Tambe,Eds.Springer-Verlag,Berlin,2002.

[12]P.CohenandH.Levesque,“Intentionischoicewithcommitment,”

ArtificialIntelligence,vol.42,1990.

[13]N.R.JenningsandE.H.,“Usingjointresponsibilitytocoordinate

collaborativeproblemsolvingindynamicenvironments,”inProceedingstheTenthNationalConferenceonArtificialIntelligence,1992.

[14]S.Sen,“Reciprocity:afoundationalprincipleforpromotingcooperative

behavioramongself-interestedagents,”inProc.oftheSecondInterna-tionalConferenceonMultiagentSystems.MenloPark,CA:AAAIPress,1996,pp.322–329.

[15]J.Shen,X.Zhang,andV.Lesser,“DegreeofLocalCooperationandits

ImplicationonGlobalUtility,”ProceedingsofThirdInternationalJointConferenceonAutonomousAgentsandMultiAgentSystems(AAMAS2004),July2004.[Online].Available:http://mas.cs.umass.edu/paper/359

12

[16]B.Horling,R.Vincent,andV.Lesser,“Multi-agentsystemsimulation

framework,”in16thIMACSWorldCongress2000onScientificCompu-tation,AppliedMathematicsandSimulation.EPFL,August2000.[17]B.HorlingandV.Lesser,“AReusableComponentArchitecturefor

AgentConstruction,”UniversityofMassachusettsatAmherst,ComputerScienceTechnicalReportTR-98-30,May1998.

[18]V.R.LesserandD.D.Corkill,“Thedistributedvehiclemonitoring

testbed,”AIMagazine,vol.4,no.3,pp.63–109,Fall1983.

[19]V.R.Lesser,“AretrospectiveviewofFA/Cdistributedproblemsolving,”

IEEETransactionsonSystems,Man,andCybernetics,vol.21,no.6,pp.1347–1363,Nov.1991.

[20]A.GlassandB.Grosz,“Sociallyconsciousdecision-making,”inPro-ceedingsofAgents2000Conference,Barcelona,Spain,June2000,pp.217–224.

[21]R.Axelrod,TheEvolutionofCooperation.BasicBooks,1984.

[22]H.Jung,M.Tambe,andS.Kulkarni,“Argumentationasdistributed

constraintsatisfaction:applicationsandresults,”inProceedingsoftheFifthInternationalConferenceonAutonomousAgents,J.P.M¨uller,E.Andre,S.Sen,andC.Frasson,Eds.Montreal,Canada:ACMPress,May2001,pp.324–331.

[23]J.M.Vidal,“Theeffectsofcooperationonmultiagentsearchintask-orienteddomains,”JournalofExperimentalandTheoreticalArtificialIntelligence,2003,toappear.

[24]X.Zhang,R.Podorozhny,andV.Lesser,“Cooperative,multistepne-gotiationoveramulti-dimensionalutilityfunctionmulti-agentsystemsnegotiation,”inProceedingsoftheIASTEDInternationalConference,ArtificialIntelligenceandSoftComputing(ASC2000),2000,pp.136–142,http://dis.cs.umass.edu/󰀁xqzhang/pub/tr00-02.ps.

[25]X.Zhang,V.Lesser,andT.Wagner,“Integrativenegotiationincomplex

organizationalagentsystems,”intheProceedingsoftheIEEE/WICInternationalConferenceonIntelligentAgentTechnology(IAT2003),Halifax,Canada,Oct13-162003,pp.140–146.