Collaborative Problem-Solving in an Optimization Game (2025)

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 memory, state tracking and problem-solving. 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.

## 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 @xcite . llms are surprisingly good at solving these problems @xcite , but only when the human user has full knowledge of the problem's contributing variables and constraints, and can spell it out in detail. one of the great promises of llms is that they can help humans solve such problems collaboratively @xcite , through a dialogue in which the human and the system take turns exploring 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 nphard problems, they also need to perform conversational grounding (tracking the details of the problem and the parts of the solution that have been agreed upon), 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 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 the agents must communicate and collaborate in or-der 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 problemsolving 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 conversational grounding; it is decisively outperformed 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, 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. ## background in order to facilitate collaboration, interlocutors must engage in dialogue so as to ensure a shared set of intentions @xcite . collaboration in dialogue can take the form of a negotiation, carried out through a set of dialogue acts such as presenting, accepting, or rejecting a proposal @xcite . a collaborative agent must successfully process and produce such acts, at least implicitly. task-oriented collaborative dialogue is primarily studied through collaborative games which foster negotiation by incentivizing goal-driven conversation @xcite . this often includes simple problem-solving tasks @xcite @xcite . these tasks stand in contrast to np-hard optimization problems, which ensure that no player can easily come to an optimal solution alone, therefore prompting negotiation and collaboration. examples of more complex tasks include trains @xcite and overcooked @xcite . the former involves collaboration between a human manager and an artificial assistant to regulate a railway and satisfy constraints, whereas in the latter, players must coordinate various steps of the cooking process in order to make dishes. we of-fer an environment of high complexity in terms of problem-solving and negotiation that is minimal enough to be addressed by prompting and crowdsourcing. llms have shown promising results and further potential on very complex tasks (see @xcite ; @xcite ; @xcite for an overview). however, previous work has shown that even one of the most advanced models (at the time, gpt-4) severely underperforms humans on strategic thinking tasks @xcite . similarly, when dealing with complex tasks, human input can be beneficial for agent performance and compensate for certain model-specific failures @xcite . finally, most previous work investigating llms and np-hard problems is focused on single-agent optimization @xcite @xcite . ## the game we present traveling adventurers, a twoplayer game environment for collecting taskoriented collaborative dialogue. players a and b observe a fully connected, undirected graph g: the nodes (v ) and edges (e) are identical for both players, whereas the weights w a , w b are unique and only known to the respective player. the goal is for the players to agree on a single, identical path that visits all nodes exactly once and returns to the starting node while maximizing the sum of a's and b's weights along the way. the players communicate exclusively through written text and have access to the entire chat history throughout the game. ## game-playing agents we introduce a series of agents for playing traveling adventurers. we start with a simple baseline agent which performs a variant of fewshot chain-of-thought (cot) reasoning @xcite and then extend it with symbolic modules for partner coin tracking, state tracking, and problem solving. we evaluate the agents on self-play (section 5) and on gameplay with human partners (section 6). action description suggest(x) agent suggests x agree-inner(x) agent agrees with own suggestion x agree-outer(x) agent agrees with other agent's suggestion x reject(x) agent rejects suggestion x ask(y) ask other agent the questions y inform(y) tell other agent the information (y) visit(v) both agents agree to visit node v solve(x) thought-draft produced a successful solution (only baseline and coin-tracking agents) end(x) ## human-agent experiments we complement the self-play evaluation from section 5 with an evaluation in a more natural environment: one in which the agent plays traveling adventurers with a human. we test the baseline and problem-solving agents. ## qualitative examples we illustrate the abilities and limitations of our agents with a few qualitative examples. fig. 5 shows a multi-turn negotiation example from selfplay of the problem-solving agent, in which b (purple) rejects a (green)'s suggested path and offers its local optimal move as a counterproposal. in the subsequent turn, a manages to persuade b to reconsider their decision in favor of the joint optimum, which b accepts. this shows that the agent is capable of nontrivial negotiations about the path. the most prominent remaining issue is that the agents with symbolic elements have no backtracking ability. this is illustrated in fig. 6 . because of the current design of the symbolic state-tracking structures (visited, remaining) and the actions for updating them, the problem-solving agent (purple) cannot process the human's (blue) attempt to we've already been to the playroom next, so let's proceed to the garden from here to gather more coins. does that sound okay to you? what would the coin situation look like for you between the playroom and garden, bathroom, or attic? we have made significant progress by visiting the kitchen and the playroom according to our best path strategy. let's proceed with this path by moving to the garden from the playroom. can you let me know the coin distribution for moving from the playroom to the garden, bathroom, or attic? lets go kitchen, then attic then, its more coins we can reset the graph no, this isnt the best path though human agent figure 6 : an example interaction between human (blue) and agent (purple). the dialogue illustrates the agent's inability to backtrack and revise the agreed-upon path. the agent has the structure of the problem-solving agent described in section 4. ## conclusion and future work we have presented traveling adventurers, a novel two-player collaborative game environment based on the tsp, where players' individual optima might not be identical to one another, or the joint optimum, encouraging negotiation and collaboration. we presented an agent that plays the game and find that combining an llm with neurosymbolic modules improves the performance compared to a baseline in self-play. we also tested the agents with human participants and find that, while the performance is lower than in self-play, the neurosymbolic agent is able to foster successful cooperation through dialogue and negotiation, outperforming the baseline agent. in the future, it would be informative to see if the agent structure from section 4 generalizes well to other problems, and whether it is sufficiently robust to handle larger graphs. another possible avenue for future work is investigating the agents' social reasoning. for example, whether, when presented with a discrepancy between own, partner's and joint optima, the agent sticks to its own plan and tries to convince its partner, or vice versa. ghost town games. 2016. overcooked. https: //www.ghosttowngames.com/overcooked . video game developed by ghost town games, published by team17. jana götze, maike paetzel-prüsmann, wencke liermann, tim diekmann, and david schlangen. 2022. the slurk interaction server framework: better data for better dialog models. in proceedings of the thirteenth language resources and evaluation conference, pages 4069-4078, marseille, france. european language resources association. atharva gundawar, mudit verma, lin guan, karthik valmeekam, siddhant bhambri, and subbarao kambhampati. 2024. robust planning with llm-modulo framework: case study in travel planning. preprint, arxiv:2405.20625. gurobi optimization, llc. 2024. gurobi optimizer