DOC PREVIEW
Modeling the Process of Collaboration and Negotiation with Incomplete Information

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Modeling the Process of Collaboration and Negotiation with Incomplete InformationSlide 2ProblemContributionsPOMDP: Partially Observable Markov Decision ProcessWhy POMDP based modeling ?Output of POMDPSimplified ExampleExample: State SpaceExample: POMDP StateExample: Action & TransitionSlide 12Building Initial Simplified POMDPPOMDP constructionCodes usedSample Grocer-Florist TranscriptGrocer POMDP generatedNegotiation GameInitial results – Classification of FloristModeling Cultural FactorsCulture and POMDPOther’s typeSlide 23Slide 24Slide 25Plans for Next YearSlide 27Thank YouModeling the Process of Collaboration and Negotiation with Incomplete InformationKatia Sycara, Praveen Paruchuri, Nilanjan ChakrabortyCollaborators: Roie Zivan, Laurie Weingart, Geoff Gordon, Miro DudikMURI 14 Program Review-- September 10, 20092TheoryFormationIdentify Cultural FactorsCUNY, Georgetown, CMUComputational ModelsCMU, USCVirtual HumansUSCImplementationCMURESEARCHPRODUCTSSurveys & InterviewsCUNY, CMU, U Mich, GeorgetownCross-Cultural InteractionsU Pitt, CMUData AnalysisCUNY, Georgetown,U Pitt, CMUvalidationvalidationvalidationValidated TheoriesModelsModeling ToolsBriefing MaterialsScenariosTraining SimulationsCommon taskSubgroup taskMURI 14 Program Review-- September 10, 20093Problem•Computational model of reasoning in Cooperation and Negotiation (C&N)•Capture the rich process of C&N–Not just outcome–Not just offer-counteroffer but additional communications•Account for cultural, social factors •Rewards of other agents not known•Uncertain and dynamic environment MURI 14 Program Review-- September 10, 2009MURI 14 Program Review-- September 10, 20094Contributions•Created an initial model from real human data. The model:–Applicable in a uniform way to both collaboration and negotiation –Derives sequences of actions for an agent from real transcripts, as opposed to state of the art work where action selection is constructed heuristically–Adapts its beliefs during the course of the interaction–Learns elements of the negotiation (e.g. other party type) as the interaction proceeds–Produces optimal activity sequences considering also the other agents–Has only incomplete information about othersPOMDP: Partially Observable Markov Decision Process•Agent has initial beliefs•Agent takes an action •Gets an observation•Interprets the observation•Updates beliefs•Decides on an action•RepeatsAgent takes optimal action considering world/other agentsElements: {States, Actions, Transitions, Rewards, Observations }MURI 14 Program Review-- September 10, 2009The World(Other agents)The World(Other agents)AgentActionObservationMURI 14 Program Review-- September 10, 20096Why POMDP based modeling ?–Decentralized algorithm–Incorporated in an agent that interacts with others–Can represent communication (arguments, offers, preferences etc)–Many conversational turns –Learns e.g. the model of the other player–Adaptive best response –Computationally efficient for realistic interactions–Extendable to more the two agents Natural way to represent cultural and social factors in C and NMURI 14 Program Review-- September 10, 2009MURI 14 Program Review-- September 10, 20097Output of POMDP•The output is a policy matrix•Policy: Optimal action to take, given current state (observations and other’s model)•At run-time, agent consults the matrix and takes appropriate actionMURI 14 Program Review-- September 10, 20098Simplified Example•Two agents negotiating–Seller S (POMDP Agent)–Buyer B (Other player)•Single item negotiation•Initially buyer at 0 price and seller at max = 10MURI 14 Program Review-- September 10, 2009MURI 14 Program Review-- September 10, 20099Example: State Space•State composed of 2 parts ––Seller Type, Buyer type–Negotiation status: current offers•Agent types: cooperative or non-cooperative•Negotiation modeled from Seller’s perspective–Initially high uncertainty of Buyer type•Seller’s belief about Buyer, and state of negotiation are dynamicMURI 14 Program Review-- September 10, 2009MURI 14 Program Review-- September 10, 200910Example: POMDP State•Agent Type: cooperative vs non-cooperative–0  cooperative, 1  non-cooperative–Discretized to {0, .5 , 1}•Price discretized to the set {0,1,..,9,10}•Sample state:•State space = Number of Buyer types * Negotiation states = 363Me (Seller) Type= CoopYou (Buyer) = UnknownNegotiation status: <S price, =$10; B price=$0>MURI 14 Program Review-- September 10, 2009MURI 14 Program Review-- September 10, 200911Example: Action & Transition•Action set: {Concede 2, Concede 1, Concede 0, Accept, Reject}•Transition: Probability of ending in some state if agent takes a particular action in current stateMURI 14 Program Review-- September 10, 2009MURI 14 Program Review-- September 10, 200912Me = CoopYou = UnknownMy price = $10Your price = $0Me = CoopYou = Coop( $9, $0 )Me = CoopYou = Coop( $9, $1 )Me = CoopYou = Coop( $9, $2 )Me = CoopYou = Ncoop( $9, $0 )Me = CoopYou = Ncoop( $9, $1 )Me = CoopYou = Ncoop( $9, $2 )Concede 1Concede 00.10.7 0.2 0.6 0.35 0.05Concede 20.50.50.350.65( $4, $6) ( $6, $4)Concede 1 0.750.25Me = CoopYou = Coop( $8, $0 )Me = CoopYou = Coop( $8, $1 )Me = CoopYou = Coop( $8, $2 )0.10.70.2Me = CoopYou = Coop( $7, $0 )Me = CoopYou = Coop( $7, $1 )Me = CoopYou = Coop( $7, $2 )0.10.40.5Concede 2Concede 0( $5, $5)Concede 1Concede 0AgreeMURI 14 Program Review-- September 10, 200913Building Initial Simplified POMDP•Human negotiation transcripts –2 players (Grocer and Florist) with 4 issues•Mapped dialogues to 14 base codes (actions)•Other player’s type known for each transcript–Used for training and validation of the model•Transition: Frequency of reaching some state, given a code•Observation: Frequency of observing a code given some negotiation stateMURI 14 Program Review-- September 10, 2009MURI 14 Program Review-- September 10, 200914POMDP constructionMURI 14 Program Review-- September 10, 200914Grocer-Florist Transcript<Player, Action code>Model GeneratorModel generatedReasoning over modelPrescription of optimal actions given state of interaction (Empty)LearnsMURI 14 Program Review-- September 10, 200915Codes usedCode Definition Code Definition Code DefinitionOFFER REACTIONS MiscMiscellaneousOSSingle-IssueRPOAgreement to offer madeSBFSubstantiationOMMulti-IssueRPSAgreement with statementQQuestionPROVIDE INFORMATIONRNODisagreement with


Modeling the Process of Collaboration and Negotiation with Incomplete Information

Download Modeling the Process of Collaboration and Negotiation with Incomplete Information
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Modeling the Process of Collaboration and Negotiation with Incomplete Information and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Modeling the Process of Collaboration and Negotiation with Incomplete Information 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?