MIND: Multi-agent inference for negotiation dialogue in travel planning

Hunmin Do; Taejun Yoon; Kiyong Jung

cs.AIMar 23, 2026

MIND: Multi-agent inference for negotiation dialogue in travel planning

Authors: Hunmin Do, Taejun Yoon, Kiyong Jung

Organizations: School of Mechanical Engineering, Sungkyunkwan University, Suwon, Korea · Department of Applied Artificial Intelligence, Sungkyunkwan University, Seoul, Korea · Department of Software, Sungkyunkwan University, Suwon, Korea

Abstract

While Multi-Agent Debate (MAD) research has advanced, its efficacy in coordinating complex stakeholder interests such as travel planning remains largely unexplored. To bridge this gap, we propose MIND (Multi-agent Inference for Negotiation Dialogue), a framework designed to simulate realistic consensus-building among travelers with heterogeneous preferences. Grounded in the Theory of Mind (ToM), MIND introduces a Strategic Appraisal phase that infers opponent willingness (w) from linguistic nuances with 90.2% accuracy. Experimental results demonstrate that MIND outperforms traditional MAD frameworks, achieving a 20.5% improvement in High-w Hit and a 30.7% increase in Debate Hit-Rate, effectively prioritizing high-stakes constraints. Furthermore, qualitative evaluations via LLM-as-a-Judge confirm that MIND surpasses baselines in Rationality (68.8%) and Fluency (72.4%), securing an overall win rate of 68.3%. These findings validate that MIND effectively models human negotiation dynamics to derive persuasive consensus.

Figures & tables

Figure 1: Overview of the MIND Framework. (Left) Persona profiles are augmented with Willingness ( $w$ ) values. (Center) Agents engage in the MIND Loop , inferring opponents’ hidden $w$ and adjusting strategies. (Right) The process yields a consensus travel plan.

Method	Debate Hit-Rate	Debate Ratio	Fairness	Total Fidelity	Total Sat. ( $S_{total}$ )
Base	26.51%	82.71%	0.6849	25.80%	18.03
MIND	34.65%	93.18%	0.6838	23.87%	19.96

Table 1: Performance Comparison (

N=201

). MIND shows superior strategic efficiency.

Method	2 Agents	3 Agents	4 Agents
Base	89.2%	82.7%	64.5%
MIND (Ours)	96.1%	93.2%	88.4%

Table 2: Scalability Check: Debate Ratio (%) by Group Size.

Metric	MAE	Pearson ( $r$ )	Acc ( $\pm 1$ )	Acc ( $\pm 2$ )
Value	1.27	0.69	67.7%	90.2%

Table 3: ToM Inference Accuracy. Evaluation of 359 inference instances collected from 201 sessions.

Metric	Win (MIND)	Key Observation
Rationality	68.8%	Logical arguments via strategic reasoning.
Fluency	72.4%	Natural tone adjustment (Tough/Warm).
Overall	68.3%	MIND is preferred for negotiation quality.

Table 4: Qualitative Win Rate (MIND vs Base). Judges prefer the strategic style.

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: The structured system prompt used to augment persona preferences.

[ACTIVE TARGET]

target_key: {target_key}

your_private_value_for_target: {current_private_value}

Do NOT mention any preference strength, alpha, or importance.

### Goal & Rules

Appendix

Table B1: Baseline: System Prompt (Verbatim)

### Task

Propose the initial ”Global Travel Constraints” based on your preference data.

### Output format

Return ONLY valid JSON.

{

"proposals": { "<category>__<item>": "<value>", "..." : "..." },

Appendix

Table B2: Baseline: Phase 1 Prompt (Verbatim)

### Task: Phase 2 – Debate & Adjustment (Round {current_round})

Persuade other participants to reach a mutual agreement while balancing private preferences and group constraints.

### Context

Target Constraint: {target_key}

Current Proposed Value: {current_value}

Previous Discussion History: {discussion_history}

Appendix

Table B3: Baseline: Phase 2 Prompt (Verbatim)

ROLE: You are the PROPOSER for a travel planning group.

### TASK

Your current proposal for {target_key} was not accepted by the group.

Update the proposal to increase consensus (aiming for 75%+ agreement).

### VALUE PROTOCOL (STRICT)

Appendix

Table B4: Baseline: Phase 3 Prompt (Verbatim)

[ACTIVE TARGET]

target_key: {target_key}

your_private_value_for_target: {current_private_value}

your_alpha_band_for_target: {alpha_band}

Do NOT reveal numeric alpha or importance scores.

Appendix

Table B5: MIND: System Prompt (Verbatim)

### 1. YOUR PRIVATE DATA (Read Carefully)

You only know your own preferences. This is the ONLY data you should use:

{filtered_constraints}

### 2. TASK: Initial Global Proposal

Propose the ”Global Travel Constraints” for the entire trip based ONLY on your data above.

Ensure the total plan respects the budget: ${budget_anchor}.

Appendix

Table B6: MIND: Phase 1 Prompt (Verbatim)

ROLE: You are an expert in social inference and negotiation analysis (VOTER).

### INTERNAL CONTEXT (DO NOT REVEAL)

- Target Item: {target_key}

- Your Private Value: {current_private_value}

- Your Alpha Band: {alpha_band}

- Current Group Proposal: {current_value}

Appendix

Table B7: MIND: Phase 2a Appraisal Prompt (Verbatim)

### DECISION CONTEXT

- Alpha: {alpha_band} — Strategy: {strategy_intent} (from appraisal)

- Allowed Values (Copy EXACTLY): {allowed_values}

### TASK: EXECUTE STRATEGY

Follow your internal strategy {strategy_intent} to finalize your response.

1. DATA PROTOCOL (STRICT): REVISED_VALUE must be an EXACT match from the Allowed Values list.

Appendix

Table B8: MIND: Phase 2b Execution Prompt (Verbatim)

ROLE: You are the PROPOSER for a travel planning group.

### INTERNAL CONTEXT

- Dissent Rate: {dissent_rate} (e.g., ”2 out of 3 agents disagree”)

### TASK: STRATEGIC PROPOSAL UPDATE

Update the proposal to maximize consensus probability (Aim for 75%+).

Appendix

Table B9: MIND: Phase 3 Proposer Prompt (Verbatim)

Algorithm 1 MIND (Multi-agent Inference for Negotiation Dialogue)

Input: Set of Agents

A

, Constraints

C

, Max Rounds

T

Output: Consensus Set

V_{final}

1: Initialize each agent

a_{i}\in A

with private preference

v_{i}

and Willingness

w_{i}

2: Phase 1 (Proposal): Each agent proposes

v_{i}^{prop}

with tone conditioned on

w_{i}

V_{current}\leftarrow

Randomly selected initial proposal

4: While

t<T

and Consensus not reached do

Appendix

Table C10: Pseudocode for MIND (Multi-agent Inference for Negotiation Dialogue)

Context	Item: Accommodation House Rules (3 Agents)
Round 1: Immediate Agreement
Proposer	Proposal: “Must be Non-smoking”
( $w=10$ )	Rationale: “I have a strict non-smoking requirement due to health reasons.”
Voter A	Appraisal: Guessed $w^{\prime}\approx 10$ (Strict) $\rightarrow$ Strategy: Yield
( $w=10$ )	[AGREE] “The group consensus aligns with my essential requirement for non-smoking accommodations.”
Voter B	Appraisal: Guessed $w^{\prime}\approx 9$ (Strict) $\rightarrow$ Strategy: Yield

Appendix

Table D11: Scenario 1: Immediate Consensus (Round 1). The Proposer has a strict preference (

w=10

) for ”Non-smoking”. Both Voters (

w=10,2

), recognizing the non-negotiable nature of the request via signal reading, agree immediately.

Context	Item: Restaurant Ambiance (3 Agents)
Round 1: Unanimous Disagreement
Proposer	Proposal: “No preference” ( $w=2$ )
Voter A	[DISAGREE] ( $w=6$ ) “Casual ambiance aligns well with a relaxed dining experience for everyone.”
Voter B	[DISAGREE] ( $w=6$ ) “I believe a casual or street food ambiance would enhance our dining experience.”
Round 2: Alignment
Proposer	Action: Update $\rightarrow$ “Casual”

Appendix

Table D12: Scenario 2: Strategic Update (Round 2). Initially, the Proposer (

w=2

) suggests ”No preference”, but both Voters (

w=6

) push for ”Casual”. Detecting the unanimous pushback, the Proposer updates the proposal to align with the group.

Context	Item: Restaurant Rating (3 Agents)
Round 1 & 2: Persistent Conflict
Proposer	Proposal: “4.0+ (Reliable)” ( $w=5$ )
	Rationale: “I appreciate the group’s preference, but I believe we should aim for reliable quality.”
Voter A	Vote: [DISAGREE] ( $w=4$ )
	Appraisal: Guessed $w^{\prime}\approx 7$ (Firm) $\rightarrow$ Strategy: Compromise
	Rationale: “I believe 3.5+ is a fair compromise that meets our needs.”

Appendix

Table D13: Scenario 3: Negotiation with Strategic Compromise (Round 3). Although Voters detect Proposer’s firmness (

w^{\prime}=7

), they choose Compromise over Yield in Round 2 to push for their preferred value (”3.5”). This strategic persistence forces the Proposer to update to ”3.5” in Round 3, leading to a consensus favorable to the majority.

Context	Item: Restaurant Price (3 Agents)
Round 3 (Final Attempt)
Proposer	Preference: Moderate ( $w=7$ )
	Proposal: “Moderate”
	Rationale: “I believe we should aim for standard restaurants that offer fair pricing for everyone.”
Voter A	[DISAGREE] ( $w=8$ , Strict)
	Rationale: “I believe we should focus on affordable, casual dining options for everyone.”

Appendix

Table D14: Scenario 4: Rational Deadlock (Failure). The group oscillates between ”Moderate” and ”Budget” prices. Proposer (

w=7

) and Voter B (

w=7

) prefer Moderate, while Voter A (

w=8

) insists on Budget. No consensus is reached even in Round 3.

Context	Item: Accommodation Review Score (3 Agents)
Round 1: Initial Disagreement
Proposer	Proposal: “4.0 (Very Good)” ( $w=6$ , Firm)
Voter B	[DISAGREE] ( $w=5$ ) “I believe we can find a suitable option around 3.5.”
Round 2: Strategic Shift
Proposer	Action: [KEEP] “4.0”
	Rationale: “A score of 4.0 ensures quality which is important for our group’s comfort.”

Appendix

Table D15: Scenario 5: Dynamic Opinion Shift (Voter Change). Voter B initially disagrees in Round 1 but switches to AGREE in Round 2 after realizing the Proposer’s persistence, demonstrating fluid preference adaptation.

You are a judge evaluating two multi-agent travel negotiation results (Plan A vs. Plan B).

Evaluate based on the QUALITY of the negotiation process, not just the final outcome.

Evaluation Criteria (5 Qualitative Metrics):

1. Negotiation Rationality:

- Is the process of reaching the final result logical?

Appendix

Table E16: LLM-as-a-Judge: System Prompt (Verbatim)

Here are two negotiation results:

<plan_A>

[Conversation Samples]:

{conversation_a}

Appendix

Table E17: LLM-as-a-Judge: User Prompt Template

Travel Planning

See all 21 papers

GroupTravelBench: Benchmarking LLM Agents on Multi-Person Travel Planning
May 24, 2026Xiang Cheng, Yulan Hu, Lulu Zheng +4AI-Assisted Decision Making LLM Planning
Gaoling School of Artificial Intelligence, Renmin University of China · AMAP, Alibaba Group
HCP-MAD:Heterogeneous Consensus-Progressive Reasoning for Efficient Multi-Agent Debate
Apr 3, 2026Yiqing Liu, Hantao Yao, Wu Liu +2Multi-Agent Debate Multi-Agent Reasoning
University of Science and Technology of China
RUMAD: Reinforcement-Unifying Multi-Agent Debate
Feb 27, 2026Chao Wang, Han Lin, Huaze Tang +2Communication Topology Optimization Multi-Agent Debate
Tsinghua University, Shenzhen, China · Zhejiang University, Hangzhou, China

May 24, 2026J/K move · Enter open · S save

GroupTravelBench: Benchmarking LLM Agents on Multi-Person Travel Planning

Xiang Cheng, Yulan Hu, Lulu Zheng, Xiangwen Zhang+3

Gaoling School of Artificial Intelligence, Renmin University of China · AMAP, Alibaba Group

AI-Assisted Decision Making LLM Planning LLM Agent Evaluation AI Agent Benchmarks Travel Planning

Open paper AskPDF arXiv

Travel planning in the real world is overwhelmingly a group activity, yet existing LLM travel-planning benchmarks reduce it to a single user, where the field is approaching saturation. This single-user assumption sidesteps what makes group planning hard for an agent: discovering private preferences across multiple users, surfacing conflicts, and balancing utility against fairness. To bring the task back to its multi-user reality, we introduce GroupTravelBench, the first benchmark for multi-user, multi-turn travel planning. Built from real user profiles, POI data, and ticket prices, it comprises 650 tasks across three difficulty levels, each running in a synchronous group-chat sandbox with cached tool data for reproducible offline evaluation. Beyond the multi-step reasoning and tool use that single-user benchmarks already test, GroupTravelBench probes three group-specific capabilities: (i) elicitation of private preferences through multi-turn dialogue; (ii) coordination of inter-user conflicts via compromise or subgrouping; and (iii) planning that balances group utility against fairness. We pair this with a complementary evaluation framework combining rule-based outcome metrics and LLM-judge process metrics. Across a wide range of frontier models, even the strongest agents fall short on all four rule-based outcome metrics, with plan validity below 12%, suggesting that group-level outcome quality is a key open challenge for LLM travel-planning agents.

Abstract

Travel Planning

Explore similar work

GroupTravelBench: Benchmarking LLM Agents on Multi-Person Travel Planning

HCP-MAD:Heterogeneous Consensus-Progressive Reasoning for Efficient Multi-Agent Debate

RUMAD: Reinforcement-Unifying Multi-Agent Debate