Collaborative Problem-Solving in an Optimization Game
Not on the map. Why?
Abstract (arXiv)
Dialogue agents that support human users in solving complex tasks have received much attention recently. Many such tasks are NP-hard optimization problems that require careful collaborative exploration of the solution space. We introduce a novel dialogue game in which the agents collaboratively solve a two-player Traveling Salesman problem, along with an agent that combines LLM prompting with symbolic mechanisms for state tracking and grounding. Our best agent solves 45% of games optimally in self-play. It also demonstrates an ability to collaborate successfully with human users and generalize to unfamiliar graphs.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 11 of its 26 references that are in the map. First posted on arXiv 21 May 2025.
Builds on
11 of 26 references.
References · 11
- 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
- 2019On the Utility of Learning about Humans for Human-AI Coordinationcited by 349
- 2017Deal or No Deal? End-to-End Learning for Negotiation Dialoguescited by 209
- 2023NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptionscited by 135
- 2024Exploring Large Language Model based Intelligent Agents: Definitions, Methods, and Prospectscited by 132
- 2023NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classescited by 79
- 2024Robust Planning with LLM-Modulo Framework: Case Study in Travel Planningcited by 34
- 2019Grounded Agreement Games: Emphasizing Conversational Grounding in Visual Dialogue Settingscited by 10
- 2022The slurk Interaction Server Framework: Better Data for Better Dialog Modelscited by 7
- 2024A Dialogue Game for Eliciting Balanced Collaborationcited by 4
- 2024A Survey on Complex Tasks for Goal-Directed Interactive Agentscited by 2
Built on by
Citing papers per year: 2025: 1.
1 paper.