Collaborative Problem-Solving in an Optimization Game

Isidora Jeknić, Alex Duchnowski, Alexander Koller · 2025

Read Collaborative Problem-Solving in an Optimization Game by Isidora Jeknić, Alex Duchnowski, Alexander Koller (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15490.txt.

Introduction

Isidora Jeknić, Alex Duchnowski, and Alexander Koller built a dialogue game in twenty twenty-five where two agents solve a traveling salesman problem together. Many tasks dialogue agents help with are hard optimization problems needing careful joint exploration, not one-shot answers. Their game makes partners negotiate a route through cities, turn by turn.

Their agent combines language model prompting with symbolic machinery that tracks the game state and grounds the conversation in the actual graph. In self-play it solved forty-five percent of games optimally. It also collaborated successfully with human partners and generalized to graphs it had never seen. The work offers a testbed for studying how conversational agents can genuinely co-reason about combinatorial problems instead of merely chatting about them.

Catalog record

CREATORIsidora Jeknić, Alex Duchnowski, Alexander Koller
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15490

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Collaborative Problem-Solving in an Optimization Game Isidora Jeknić, Alex Duchnowski, Alexander Koller Abstract 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. 1 Introduction Humans frequently face the challenge of solving hard combinatorial problems in their daily lives, from planning to scheduling to resource allocation, and they often struggle to solve these problems well ( Hidalgo-Herrero et al. 2013 ) . LLMs are surprisingly good at solving these problems Fan et al. 2024 , but only when the human user has full knowledge of the problem and can spell it out in detail. One of the great promises of LLMs is that they can help humans solve such problems collaboratively Khan and Hamad 2024 , through a dialogue in which the human and the system take turns working out the problem and proposing increasingly complete and correct solutions. AI agents for collaborative problem-solving must have a number of fundamental skills to be effective. In addition to the ability to solve NP-hard problems themselves, they also need to perform conversational grounding (tracking the details of the problem and which part of the solution have we agreed on), remember what their partner wants and knows, and negotiate and revise partial solutions. All of these are established problems in the dialogue literature, and it is not obvious that LLMs will solve them easily. In this paper, we make two contributions to the development of collaborative agents for solving complex problems. 1 1 1 Our code and data are available at: https://github.com/coli-saar/collaborative-problem-solving . First, we introduce TRAVELING ADVENTURERS , a game in which two agents collaboratively solve a Traveling Salesman problem. This game serves as a testbed for collaborative problem-solving, as each agent only has partial information about the problem initially and must communicate and collaborate in order to negotiate an optimal solution. Furthermore, because it builds on an NP-hard optimization problem, TRAVELING ADVENTURERS is difficult enough that humans could not immediately find optimal solutions even with access to their partner’s knowledge, necessitating the incremental construction of a solution that we expect in a collaborative problem-solving dialogue. Second, we present an artificial agent that performs well on playing TRAVELING ADVENTURERS . We find that a purely LLM-based baseline struggles with tracking its partner’s knowledge and with conversational grounding; it is outperformed decisively by a neurosymbolic agent which combines the LLM with symbolic components for these skills and an exact symbolic optimizer. The neurosymbolic agent solves 98% of its games correctly and 45% optimally in self-play with itself, and still achieves a high optimality score in 32% of games with human partners. We conclude with a discussion of conversational skills that would be required to push the optimality rate even higher. Figure 1: The perspectives of the two players - the left and right figures depict the distinct graphs of each player, whereas the middle illustrates the shared information, i.e., the chat. 2 Background In order to facilitate collaboration, interlocutors must engage in dialogue so as to ensure a shared set of intentions Dafoe et al. 2021 . Collaboration in dialogue is realized through negotiation, i.e., effort to establish common ground and a joint purpose Clark 1996 . It is often identified through a set of dialogue acts, defined as “meaning[s] of [utterances] at the level of illocutionary force” ( Stolcke et al. 2000 , 2) , such as presenting a solution, as well as accepting or rejecting a proposal Georgila and Traum 2011 . Therefore, a collaborative agent must successfully process and produce such acts. Task-oriented collaborative dialogue is primarily studied through collaborative games which foster negotiation by incentivizing goal-driven conversation Schlangen 2019 . This often includes simple problem-solving tasks Zarrieß et al. 2016 ; Lewis et al. 2017 ; Kim et al. 2019 . Most of these environments—even those which are more complex, such as TRAINS Allen et al. 1995 —are typically asymmetric, assigning players fixed roles. This limits the scope of collaboration that can be studied and prevents organic role-taking, despite human players preferring a more balanced role distribution, which often improves performance on symmetric tasks Jeknic et al. 2024 . LLMs have shown promising results and further potential on very complex tasks (for overview, see Cheng et al. 2024 ; Mialon et al. 2023 ; Hartmann and Koller 2024 ). However, previous work has shown that even the most advanced models (at the time, GPT-4) severely under-performs humans on strategic thinking tasks Zhou et al. 2024 . Similarly, when dealing with complex tasks, human input can be beneficial for agent performance and make up for certain model-specific failures Lin et al. 2024 . Additionally, most previous work investigating LLMs and NP-hard problems is focused on single-agent optimization Ramamonjison et al. 2023 ; Tang et al. 2025 . 3 The Game Figure 2: Different perspectives of the same move: the left and middle panels show two players’ individual greedy optimal move; the right panel shows the joint greedy optimal move, which does not match either player’s individual optimum. We present TRAVELING ADVENTURERS , a symmetric two-player game environment for collecting task-oriented collaborative dialogue. Players A and B observe a fully connected undirected graph G : the set of nodes ( V ) and edges ( E ) are identical for both players, whereas the weights ( w ) are unique ( w_{A},w_{B} ) and only known to the respective player. The goal is to find a single path that visits all nodes exactly once and returns to the starting node while maximizing the sum of players’ weights along the way. The pairs communicate exclusively through written text and have access to the entire chat history throughout the game. Story The players are told that an evil wizard imprisoned them in two parallel dimensions of the same house: the light and ghost dimensions. They observe the same layout, where each room is connected to all the others via hallways. In order to break the curse, the players are instructed to visit each room together and return to the start. Moreover, each player collects their respective type of coin (the light and ghost coins) in the hallways between rooms. In the end, the sum of coins collected by each player are given to them as joint loot. 3.1 Features The game mechanics are based on a classical NP-hard optimization problem, the Traveling Salesman Problem (TSP), which we adjust for two players and “dress up” Duchnowski et al. 2025 into the familiar game setting of collecting coins. In relation to the TSP, the rooms represent cities and the coins distances (Figure 1 ), with the coin maximization analogous to distance minimization. The curse-breaking ritual follows the rules of the TSP, and the coin reward in the end measures the overall optimality of the selected

Read the complete text