# Collaborative Problem-Solving in an Optimization Game

arXiv: https://arxiv.org/abs/2505.15490 · HTML: https://mlsanity.com/paper/2505.15490/

## Key facts

- Cited by 1 papers 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 (most cited first, 11 of 11)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [On the Utility of Learning about Humans for Human-AI Coordination](https://mlsanity.com/paper/1910.05789/) (2019)
- [Deal or No Deal? End-to-End Learning for Negotiation Dialogues](https://mlsanity.com/paper/1706.05125/) (2017)
- [NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions](https://mlsanity.com/paper/2303.08233/) (2023)
- [Exploring Large Language Model based Intelligent Agents: Definitions, Methods, and Prospects](https://mlsanity.com/paper/2401.03428/) (2024)
- [NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes](https://mlsanity.com/paper/2312.14890/) (2023)
- [Robust Planning with LLM-Modulo Framework: Case Study in Travel Planning](https://mlsanity.com/paper/2405.20625/) (2024)
- [Grounded Agreement Games: Emphasizing Conversational Grounding in Visual Dialogue Settings](https://mlsanity.com/paper/1908.11279/) (2019)
- [The slurk Interaction Server Framework: Better Data for Better Dialog Models](https://mlsanity.com/paper/2202.01155/) (2022)
- [A Dialogue Game for Eliciting Balanced Collaboration](https://mlsanity.com/paper/2406.08202/) (2024)
- [A Survey on Complex Tasks for Goal-Directed Interactive Agents](https://mlsanity.com/paper/2409.18538/) (2024)

## Built on by (most cited first, 1 of 1)

- [Characterizing Language Use in a Collaborative Situated Game](https://mlsanity.com/paper/2512.03381/) (2025)

## 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.