一个新颖的策略用来在复杂的环境中高效谈判

一个新颖的策略用来在复杂的环境中高效谈判AnovelstrategyforefficientnegotiationincomplexenvironmentsOutlineIntroductionRelatedWorkNegotiationEnvironmentEMARExperimentalAnalysisConclusionAutomatedBilateralMulti-IssueNegotiationTwo-agentsProfitableContractMultipleIssuesConflictiveImportanceIntroduction第三次高潮IntroductionRealisticScenariosForBilateralMulti-IssueNegotiationsAreComplexNoinformationabouttheiropponentNopriorknowledgeaboutthenegotiationdomainDeadlineanddiscountComputationalefficiency第三次高潮IntroductionEMAR(EmpiricalModeDecompositionandAutoRegressiveMovingAverage)1.

EfficientOpponentModelingPredictingtheutilitiesoftheopponent’sfuturecounter-offers2.

AdaptiveConcessionMakingDynamicallyadaptingtheconcessionrate第三次高潮RelatedWorkMainIdea:Generatingandutilizingopponentmodelsinordertooptimizeanagent’snegotiationbehaviorLearningtheopponent’spreferenceprofileLearningtheopponent’snegotiationstrategy第三次高潮RelatedWorkLearningtheopponent’spreferenceprofileBayesianlearningtoapproximatetheopponentpreferenceprofileR.Lin,S.Kraus,J.Wilkenfeld,andJ.Barry.Negotiatingwithboundedrationalagentsinenvironmentswithincompleteinformationusinganautomatedagent.Artif.Intell.,172:823–851,April2008.KerneldensityestimationisusedasanapproximationtechniqueR.M.CoehoornandN.R.Jennings.Learningonopponent’spreferencestomakeeffectivemulti-issuenegotiationtrade-offs.InProceedingsofthe6thInt.conf.onElectroniccommerce,ICEC’04,pages59–68,NewYork,NY,USA,2004.ACM.Drawback：computationallyintractablefordomainshavingalargeoutcomespace(especiallyifreal-timeconstraintsapply)第三次高潮RelatedWorkLearningtheopponent’snegotiationstrategyChebychevpolynomialstoestimatethechancethatthenegotiationpartneracceptsanofferinrepeatedsingle-issuenegotiationsPredictfuturecounter-offersonlineonthebasisofthepreviousnegotiationhistoryNon-linearregressiontopredicttheopponent’stacticGaussianprocessestopredictthefutureopponentconcessionDrawback：Theyareoftenbasedonunrealisticassumptions

(single-issuenegotiation;tacticsarefixed)第三次高潮NegotiationEnvironmentSetting:Basicbilateralmulti-issuenegotiationProtocol:AvariantofthealternatingoffersprotocolTheutilityofanofferforagentiisobtainedbytheutilityfunction:第三次高潮NegotiationEnvironmentConstraints:DeadlineAndDiscountedFactorAndThresholdTheymusthavecompletedorwithdrawthenegotiationbythedeadline;ThenumberofremainingroundsisnotknownTheutilityisdiscountedwithtime

discountingfactorδ(δ∈[0,1])AcceptOrReject:第三次高潮EMAROpponentmodelingAdaptiveConcessionMakingResponsetocounter-offers第三次高潮OpponentmodelingAimatpredictingthefuturebehaviorofthenegotiatingopponentsEMDisemployedtodecomposethetimeseriesgivenbytheutilitiesofpastcounter-offersintoafinitenumberofcomponentsARMAisappliedtopredictfuturevaluesofthesesub-components第三次高潮AdaptiveConcessionMakingAdjusttheconcessiononthebasisofthegeneratedopponentmodelAdynamicconservativeexpectationR(t)isusedtoavoid“irrationalconcession”R(t)guaranteesthedesiredminimumutilityateachstep第三次高潮Responsetocounter-offersThe

expected

utility

u’

has

been

determined,howtoresponsetothecounter-offerAccept,ifsatisfyeitherofthesetwoconditions:Thecounter-offerU(Oopp)isbetterthanu’IthasalreadyproposedthisofferearlierinthenegotiationprocessOtherwise,theagentconstructsanewofferwhichhasanutilitywithinsomerangearoundu’第三次高潮TheAlgorithmFlow第三次高潮ExperimentalAnalysisEnvironmentalsettingExperimentalresults第三次高潮EnvironmentalsettingGENIUS:InthisenvironmentanagentcannegotiatewithotheragentsinavarietyofdomainsFive

standard

domainsFiveopponentsfrombestwinnersofANAC2011Theagentsdonothaveanyinformationabouttheiropponent;Thedurationofanegotiationsessionis180seconds第三次高潮Experimentalresults第三次高潮Experimentalresults第三次高潮ConclusionThisworkintroducedaneffectivestrategyforautomatedbilateralnegotiationincomplexscenarios(multi-issue,time-