Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.15490 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915716242866176 |
|---|---|
| author | Jeknic, Isidora Duchnowski, Alex Koller, Alexander |
| author_facet | Jeknic, Isidora Duchnowski, Alex Koller, Alexander |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15490 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Collaborative Problem-Solving in an Optimization Game Jeknic, Isidora Duchnowski, Alex Koller, Alexander Computation and Language 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. |
| title | Collaborative Problem-Solving in an Optimization Game |
| topic | Computation and Language |
| url | https://arxiv.org/abs/2505.15490 |